Some enhancements to ImmutableSet and FoldingSet

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
13 messages Options
Reply | Threaded
Open this post in threaded view
|

Some enhancements to ImmutableSet and FoldingSet

Ben Laurie-3
I needed these for some work I'm doing in clang...

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

set.patch (2K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Some enhancements to ImmutableSet and FoldingSet

Ted Kremenek-2

On Feb 11, 2009, at 10:36 AM, Ben Laurie wrote:

> I needed these for some work I'm doing in clang...
> <set.patch>_______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

Looks good to me.  I'll apply these.
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Some enhancements to ImmutableSet and FoldingSet

Bill Wendling
In reply to this post by Ben Laurie-3
On Wed, Feb 11, 2009 at 10:36 AM, Ben Laurie <[hidden email]> wrote:
> I needed these for some work I'm doing in clang...
>
Yes sir! At least this message was informative. One thing:

+  int size() const {
+    int n = 0;
+    for(iterator i = begin() ; i != end() ; ++n, ++i)
+      ;
+    return n;
+  }
+  bool empty() const {
+    return size() == 0;
+  }

empty() here isn't a constant-time method. Can you make it's time
complexity O(1)?

-bw
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Some enhancements to ImmutableSet and FoldingSet

Ted Kremenek-2
In reply to this post by Ben Laurie-3
Ben,

This patch doesn't apply.  Can you update to TOT LLVM first and  
regenerate the patch?

Ted

On Feb 11, 2009, at 10:36 AM, Ben Laurie wrote:

> I needed these for some work I'm doing in clang...
> <set.patch>_______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Some enhancements to ImmutableSet and FoldingSet

Ted Kremenek-2
In reply to this post by Bill Wendling

On Feb 11, 2009, at 10:54 AM, Bill Wendling wrote:

On Wed, Feb 11, 2009 at 10:36 AM, Ben Laurie <[hidden email]> wrote:
I needed these for some work I'm doing in clang...

Yes sir! At least this message was informative. One thing:

+  int size() const {
+    int n = 0;
+    for(iterator i = begin() ; i != end() ; ++n, ++i)
+      ;
+    return n;
+  }
+  bool empty() const {
+    return size() == 0;
+  }

empty() here isn't a constant-time method. Can you make it's time
complexity O(1)?

-bw

Bill's right; empty can be made constant time.  e.g.,  "return Root == 0";

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Some enhancements to ImmutableSet and FoldingSet

Ted Kremenek-2
Actually, neither of these methods are needed for ImmutableSet.  ImmutableSet already has an 'isEmpty()' method and I have never really seen a case where "size()" needs to be explicitly calculated.  If you need size() itself, however, this seems like a perfectly valid addition.

On Feb 11, 2009, at 10:57 AM, Ted Kremenek wrote:


On Feb 11, 2009, at 10:54 AM, Bill Wendling wrote:

On Wed, Feb 11, 2009 at 10:36 AM, Ben Laurie <[hidden email]> wrote:
I needed these for some work I'm doing in clang...

Yes sir! At least this message was informative. One thing:

+  int size() const {
+    int n = 0;
+    for(iterator i = begin() ; i != end() ; ++n, ++i)
+      ;
+    return n;
+  }
+  bool empty() const {
+    return size() == 0;
+  }

empty() here isn't a constant-time method. Can you make it's time
complexity O(1)?

-bw

Bill's right; empty can be made constant time.  e.g.,  "return Root == 0";


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Some enhancements to ImmutableSet and FoldingSet

Ted Kremenek-2
In reply to this post by Ben Laurie-3

On Feb 11, 2009, at 10:36 AM, Ben Laurie wrote:

> I needed these for some work I'm doing in clang...
> <set.patch>_______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

Minor nit:

--- include/llvm/ADT/FoldingSet.h (revision 63488)
+++ include/llvm/ADT/FoldingSet.h (working copy)
@@ -225,6 +225,7 @@
    void AddInteger(unsigned long I);
    void AddInteger(long long I);
    void AddInteger(unsigned long long I);
+  void AddBoolean(bool B);
    void AddString(const std::string &String);
    void AddString(const char* String);

Index: lib/Support/FoldingSet.cpp
===================================================================
--- lib/Support/FoldingSet.cpp (revision 63488)
+++ lib/Support/FoldingSet.cpp (working copy)
@@ -61,6 +61,9 @@
    if ((uint64_t)(int)I != I)
      Bits.push_back(unsigned(I >> 32));
  }
+void FoldingSetNodeID::AddBoolean(bool B) {
+  AddInteger(B ? 1 : 0);
+}

"AddBoolean()" can just be defined inline, since it is so simple.

I've committed this change:

http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20090209/073619.html
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Some enhancements to ImmutableSet and FoldingSet

Chris Lattner-2
In reply to this post by Ted Kremenek-2

On Feb 11, 2009, at 12:24 PM, Ted Kremenek wrote:

> Actually, neither of these methods are needed for ImmutableSet.  
> ImmutableSet already has an 'isEmpty()' method and I have never  
> really seen a case where "size()" needs to be explicitly  
> calculated.  If you need size() itself, however, this seems like a  
> perfectly valid addition.

I agree, "size" should also return 'unsigned' not int.

-Chris
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Some enhancements to ImmutableSet and FoldingSet

Nick Lewycky
In reply to this post by Bill Wendling
Bill Wendling wrote:
> On Wed, Feb 11, 2009 at 10:36 AM, Ben Laurie <[hidden email]> wrote:
>> I needed these for some work I'm doing in clang...
>>
> Yes sir! At least this message was informative. One thing:
>
> +  int size() const {
> +    int n = 0;
> +    for(iterator i = begin() ; i != end() ; ++n, ++i)
> +      ;

Please only call end() once. We use this pattern a lot in LLVM:

for (iterator i = begin(), e = end(); i != e; ++n, ++i)
   ;

But really I think you should just have:
   return std::distance(begin(), end());

Nick

> +    return n;
> +  }
> +  bool empty() const {
> +    return size() == 0;
> +  }
>
> empty() here isn't a constant-time method. Can you make it's time
> complexity O(1)?
>
> -bw
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Some enhancements to ImmutableSet and FoldingSet

Ben Laurie-3
In reply to this post by Ted Kremenek-2
On Wed, Feb 11, 2009 at 8:24 PM, Ted Kremenek <[hidden email]> wrote:
> Actually, neither of these methods are needed for ImmutableSet.
>  ImmutableSet already has an 'isEmpty()' method and I have never really seen
> a case where "size()" needs to be explicitly calculated.  If you need size()
> itself, however, this seems like a perfectly valid addition.

I need to check for size() == 1 (in order to test whether a range set
has a single possible value).
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Some enhancements to ImmutableSet and FoldingSet

Ted Kremenek-2
On Feb 11, 2009, at 8:14 PM, Ben Laurie wrote:

> On Wed, Feb 11, 2009 at 8:24 PM, Ted Kremenek <[hidden email]>  
> wrote:
>> Actually, neither of these methods are needed for ImmutableSet.
>> ImmutableSet already has an 'isEmpty()' method and I have never  
>> really seen
>> a case where "size()" needs to be explicitly calculated.  If you  
>> need size()
>> itself, however, this seems like a perfectly valid addition.
>
> I need to check for size() == 1 (in order to test whether a range set
> has a single possible value).

Ah.  If that is the case, we can implement a 'isSingleton()' method  
with constant time performance (i.e., check if we have a root, and  
check that the root has no children).  Would that work?
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Some enhancements to ImmutableSet and FoldingSet

Ben Laurie-3
On Thu, Feb 12, 2009 at 4:47 AM, Ted Kremenek <[hidden email]> wrote:

> On Feb 11, 2009, at 8:14 PM, Ben Laurie wrote:
>
>> On Wed, Feb 11, 2009 at 8:24 PM, Ted Kremenek <[hidden email]> wrote:
>>>
>>> Actually, neither of these methods are needed for ImmutableSet.
>>> ImmutableSet already has an 'isEmpty()' method and I have never really
>>> seen
>>> a case where "size()" needs to be explicitly calculated.  If you need
>>> size()
>>> itself, however, this seems like a perfectly valid addition.
>>
>> I need to check for size() == 1 (in order to test whether a range set
>> has a single possible value).
>
> Ah.  If that is the case, we can implement a 'isSingleton()' method with
> constant time performance (i.e., check if we have a root, and check that the
> root has no children).  Would that work?

Sure would!
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Some enhancements to ImmutableSet and FoldingSet

Ted Kremenek-2

On Feb 11, 2009, at 8:53 PM, Ben Laurie wrote:

> On Thu, Feb 12, 2009 at 4:47 AM, Ted Kremenek <[hidden email]>  
> wrote:
>> On Feb 11, 2009, at 8:14 PM, Ben Laurie wrote:
>>
>>> On Wed, Feb 11, 2009 at 8:24 PM, Ted Kremenek <[hidden email]>  
>>> wrote:
>>>>
>>>> Actually, neither of these methods are needed for ImmutableSet.
>>>> ImmutableSet already has an 'isEmpty()' method and I have never  
>>>> really
>>>> seen
>>>> a case where "size()" needs to be explicitly calculated.  If you  
>>>> need
>>>> size()
>>>> itself, however, this seems like a perfectly valid addition.
>>>
>>> I need to check for size() == 1 (in order to test whether a range  
>>> set
>>> has a single possible value).
>>
>> Ah.  If that is the case, we can implement a 'isSingleton()' method  
>> with
>> constant time performance (i.e., check if we have a root, and check  
>> that the
>> root has no children).  Would that work?
>
> Sure would!


Hi Ben,

I think this should work:

http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20090209/073634.html

If you find it isn't doing the right thing just let me know.

Ted
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev