Adding DenseMap::FindAndConstruct with a default value

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

Adding DenseMap::FindAndConstruct with a default value

matthijs
Hi All,

I've been fiddling around with a DenseMap to store cached copies of some
result. In short, I'm doing the following:

It = Map.find(Key)
if (It != Map.end() && It->second != Unknown)
        Return It->second;

// do_stuff

return Map[Key] = Result;

However, I this requires two lookups in the hash table, which is not so nice.
Currently, there is no way to write this down so you only do one lookup.
Intuitively, you'd write:

ValueT &Value = Map[Key];
if (Value != Unknown)
        return Value;

// do_stuff

return Value = Result;

However, I'm using an enum as a map value, so when you do Map[Key] while Key
is not yet in the map, the new value will be unitialized (I can't define a
constructor on an enum, right?).

So, to solve this, I propose adding a second version of
DenseMap::FindAndConstruct, which has an extra argument for the default value.
So, it would do the same thing as the original (return a reference to the
value from the map, adding it if it's not already in), but instead of using
ValueT() as a default value, it would use an argument.

Any objections to adding this? Suggestions for alternatives?

Gr.

Matthijs

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

signature.asc (196 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Adding DenseMap::FindAndConstruct with a default value

Owen Anderson-2
Assuming the default value is not a valid entry in your map (for  
instance, if you're using pointers), you can do:

Foo& entry = DenseMap[Key]
if (entry == DefaultValue)
        entry = constructNewValue();

... // Use entry

--Owen


On Jun 5, 2008, at 7:49 AM, Matthijs Kooijman wrote:

> Hi All,
>
> I've been fiddling around with a DenseMap to store cached copies of  
> some
> result. In short, I'm doing the following:
>
> It = Map.find(Key)
> if (It != Map.end() && It->second != Unknown)
> Return It->second;
>
> // do_stuff
>
> return Map[Key] = Result;
>
> However, I this requires two lookups in the hash table, which is not  
> so nice.
> Currently, there is no way to write this down so you only do one  
> lookup.
> Intuitively, you'd write:
>
> ValueT &Value = Map[Key];
> if (Value != Unknown)
> return Value;
>
> // do_stuff
>
> return Value = Result;
>
> However, I'm using an enum as a map value, so when you do Map[Key]  
> while Key
> is not yet in the map, the new value will be unitialized (I can't  
> define a
> constructor on an enum, right?).
>
> So, to solve this, I propose adding a second version of
> DenseMap::FindAndConstruct, which has an extra argument for the  
> default value.
> So, it would do the same thing as the original (return a reference  
> to the
> value from the map, adding it if it's not already in), but instead  
> of using
> ValueT() as a default value, it would use an argument.
>
> Any objections to adding this? Suggestions for alternatives?
>
> Gr.
>
> Matthijs
> _______________________________________________
> 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

smime.p7s (5K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Adding DenseMap::FindAndConstruct with a default value

Ted Kremenek-2
In reply to this post by matthijs

On Jun 5, 2008, at 7:49 AM, Matthijs Kooijman wrote:

> So, to solve this, I propose adding a second version of
> DenseMap::FindAndConstruct, which has an extra argument for the  
> default value.
> So, it would do the same thing as the original (return a reference  
> to the
> value from the map, adding it if it's not already in), but instead  
> of using
> ValueT() as a default value, it would use an argument.

This sounds fine to me.  I believe that member functions of template  
classes are not instantiated until they are used, so it shouldn't pose  
a problem  for existing clients of DenseMap, nor have an impact on  
code size of existing clients, etc.
_______________________________________________
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: Adding DenseMap::FindAndConstruct with a default value

Chris Lattner
In reply to this post by matthijs
On Jun 5, 2008, at 7:49 AM, Matthijs Kooijman wrote:
> However, I'm using an enum as a map value, so when you do Map[Key]  
> while Key
> is not yet in the map, the new value will be unitialized (I can't  
> define a
> constructor on an enum, right?).

DenseMap should be initializing new values with x = ValueT();  This  
will properly zero initialize for ints, enums etc. AFAIK.

-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: Adding DenseMap::FindAndConstruct with a default value

matthijs
In reply to this post by Owen Anderson-2
> Assuming the default value is not a valid entry in your map (for instance,
> if you're using pointers), you can do:
>
> Foo& entry = DenseMap[Key]
> if (entry == DefaultValue)
> entry = constructNewValue();
The problem here is that the DefaultValue is undefined. However, Chris
suggested that the default value, ValueT(), is not undefined but simply zero.
However, on IRC someone was quite positive that it would become undefined.
Anyone that knows for sure (preferably from the language standard, not only
from experience :-)

Gr.

Matthijs

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

signature.asc (196 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Adding DenseMap::FindAndConstruct with a default value

Eli Friedman-2
On Fri, Jun 6, 2008 at 12:27 AM, Matthijs Kooijman <[hidden email]> wrote:
>> Assuming the default value is not a valid entry in your map (for instance,
>> if you're using pointers), you can do:
>>
>> Foo& entry = DenseMap[Key]
>> if (entry == DefaultValue)
>>       entry = constructNewValue();
> The problem here is that the DefaultValue is undefined. However, Chris
> suggested that the default value, ValueT(), is not undefined but simply zero.

This is correct; from the standard: "The expression T(), where T is a
simple-type-specifier (7.1.5.2) for a non-array complete object type
or the (possibly cv-qualified) void type, creates an rvalue of the
specified type, which is value-initialized."  (Section 5.2.3
[expr.type.conv] in the C++0x draft standard; I don't have the
published standard on hand.) And value-initialization is defined to be
zero-initialization for scalar types. (Section 8.5 [dcl.init] in the
C++0x draft.)

> However, on IRC someone was quite positive that it would become undefined.

The reason this is kind of confusing is that in a lot of places, the
standard says something along the lines of "if this object is a
non-POD type, value-initialize it; otherwise, leave it uninitialized"
(examples include automatic variables and class members).

-Eli
_______________________________________________
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: Adding DenseMap::FindAndConstruct with a default value

matthijs
Hi Eli,

thanks for the clarification, this saves me from implementing extra code :-)

Gr.

Matthijs

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

signature.asc (196 bytes) Download Attachment