llvm dev - Jun 2008 - [LLVMdev] Adding DenseMap::FindAndConstruct with a default value

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20080605/d8bfe66a/attachment.sig>

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
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 4260 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20080605/4de02921/attachment.bin>

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.

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

> 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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20080606/56837638/attachment.sig>