Re: [v8-dev] TemplateHashMap changes proposal

[Marja Hölttä]

Re: what Ross said.

Yes, exactly, we compute the hashes once when inserting into 
AstValueFactory and reuse them when internalizing the strings to avoid 
hashing twice. No other reason.

-- 
-- 
v8-dev mailing list
v8-dev@googlegroups.com
http://groups.google.com/group/v8-dev
--- 
You received this message because you are subscribed to the Google Groups 
"v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to v8-dev+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [v8-dev] TemplateHashMap changes proposal

[Leszek Swirski]

I've definitely seen cases of the hash function being passed in as
key->hash(). If that's the case, then the templated hash function could,
for example, look up the hash on the key object.

On Thu, Sep 15, 2016 at 9:43 AM, 'Ross McIlroy' via v8-dev <
v8-dev@googlegroups.com> wrote:

> On 15 Sep 2016 9:29 a.m.,  wrote:
> >
> > Hi all,
> >
> > We (ignition) are looking to use base/hashmap (TemplateHashMap), but
> there are a couple of things that I want to change/add for efficiency's
> sake. Because these changes would have far-reaching effects, I wanted to
> send out the proposed changes before trying to upload any CLs.
> >
> > My proposed changes are:
> > Template the value type, so that small types (e.g. ints) can be stored
> inline rather than allocated
> > Template the key type, for the same reason
> > This has some far reaching effects -- e.g. we can't store holes as
> nullptr keys anymore, but have to have a separate boolean existence flag. I
> suggest that we have an Entry class that is templated on the key, and
> specialised for pointer-typed keys to treat null keys as holes.
> > Template the hash function and remove the hash fields, because passing
> in our own hash values is asking for trouble
>
> AFAIK the hash arguments are used by the ast-value-factory such that AST
> value objects stores their hash as a field and pass it to lookups to avoid
> having to rehash the AST values. We would want something like this for any
> replacement. It might be possible to store the cached hash files on the
> hashmap entries themselves, but maybe there is some another reason we
> currently have them on the AST values.
>
> Marja, any thoughts?
>
> > Template the equals/matching function, since we'd be having to template
> it on the key type anyway, to skip that dereference
> > Move the allocator to a field, because passing different allocators
> around as parameters is super sketchy
> > More precisely, move it to a private base class to take advantage of the
> empty base-class optimisation
> > Add a function argument to LookupOrInsert which creates the value, since
> the Value type is templated and so we can't rely on null values to mean
> newly-inserted entries
> > And maybe, though I'm less convinced about these:
> > Return value references directly for Lookup/LookupOrInsert, rather than
> Entries, to make Entries non-public
> > Add an stl-like iterator interface rather than Start/Next, also to make
> Entries non-public
> > Most of these I could wrap in a particular 

Re: [v8-dev] TemplateHashMap changes proposal

['Ross McIlroy' via v8-dev]

On 15 Sep 2016 9:29 a.m.,  wrote:
>
> Hi all,
>
> We (ignition) are looking to use base/hashmap (TemplateHashMap), but
there are a couple of things that I want to change/add for efficiency's
sake. Because these changes would have far-reaching effects, I wanted to
send out the proposed changes before trying to upload any CLs.
>
> My proposed changes are:
> Template the value type, so that small types (e.g. ints) can be stored
inline rather than allocated
> Template the key type, for the same reason
> This has some far reaching effects -- e.g. we can't store holes as
nullptr keys anymore, but have to have a separate boolean existence flag. I
suggest that we have an Entry class that is templated on the key, and
specialised for pointer-typed keys to treat null keys as holes.
> Template the hash function and remove the hash fields, because passing in
our own hash values is asking for trouble

AFAIK the hash arguments are used by the ast-value-factory such that AST
value objects stores their hash as a field and pass it to lookups to avoid
having to rehash the AST values. We would want something like this for any
replacement. It might be possible to store the cached hash files on the
hashmap entries themselves, but maybe there is some another reason we
currently have them on the AST values.

Marja, any thoughts?

> Template the equals/matching function, since we'd be having to template
it on the key type anyway, to skip that dereference
> Move the allocator to a field, because passing different allocators
around as parameters is super sketchy
> More precisely, move it to a private base class to take advantage of the
empty base-class optimisation
> Add a function argument to LookupOrInsert which creates the value, since
the Value type is templated and so we can't rely on null values to mean
newly-inserted entries
> And maybe, though I'm less convinced about these:
> Return value references directly for Lookup/LookupOrInsert, rather than
Entries, to make Entries non-public
> Add an stl-like iterator interface rather than Start/Next, also to make
Entries non-public
> Most of these I could wrap in a particular 

Re: [v8-dev] TemplateHashMap changes proposal

[Leszek Swirski]

Good question, and one I tried at first.
Unfortunately, std::unordered_map<> has some disadvantages, namely
re-hashing my hashes (which I profiled and it had a noticeable performance
penalty), no support (that I could find) for a LookupOrInsert of a
non-default value, and prime-number bin counts rather than power of two,
where again I measured a performance penalty with the former.

On Thu, Sep 15, 2016 at 9:31 AM, Jochen Eisinger 
wrote:

> would replacing it with std::unordered_map<> gain the same advantages?
>
> On Thu, Sep 15, 2016 at 10:29 AM  wrote:
>
>> Hi all,
>>
>> We (ignition) are looking to use base/hashmap (TemplateHashMap), but
>> there are a couple of things that I want to change/add for efficiency's
>> sake. Because these changes would have far-reaching effects, I wanted to
>> send out the proposed changes before trying to upload any CLs.
>>
>> My proposed changes are:
>>
>>- Template the value type, so that small types (e.g. ints) can be
>>stored inline rather than allocated
>>- Template the key type, for the same reason
>>   - This has some far reaching effects -- e.g. we can't store holes
>>   as nullptr keys anymore, but have to have a separate boolean existence
>>   flag. I suggest that we have an Entry class that is templated on the 
>> key,
>>   and specialised for pointer-typed keys to treat null keys as holes.
>>- Template the hash function and remove the hash fields, because
>>passing in our own hash values is asking for trouble
>>- Template the equals/matching function, since we'd be having to
>>template it on the key type anyway, to skip that dereference
>>- Move the allocator to a field, because passing different allocators
>>around as parameters is super sketchy
>>   - More precisely, move it to a private base class to take
>>   advantage of the empty base-class optimisation
>>- Add a function argument to LookupOrInsert which creates the value,
>>since the Value type is templated and so we can't rely on null values to
>>mean newly-inserted entries
>>
>> And maybe, though I'm less convinced about these:
>>
>>- Return value references directly for Lookup/LookupOrInsert, rather
>>than Entries, to make Entries non-public
>>- Add an stl-like iterator interface rather than Start/Next, also to
>>make Entries non-public
>>
>> Most of these I could wrap in a particular 

Re: [v8-dev] TemplateHashMap changes proposal

[Jochen Eisinger]

would replacing it with std::unordered_map<> gain the same advantages?

On Thu, Sep 15, 2016 at 10:29 AM  wrote:

> Hi all,
>
> We (ignition) are looking to use base/hashmap (TemplateHashMap), but there
> are a couple of things that I want to change/add for efficiency's sake.
> Because these changes would have far-reaching effects, I wanted to send out
> the proposed changes before trying to upload any CLs.
>
> My proposed changes are:
>
>- Template the value type, so that small types (e.g. ints) can be
>stored inline rather than allocated
>- Template the key type, for the same reason
>   - This has some far reaching effects -- e.g. we can't store holes
>   as nullptr keys anymore, but have to have a separate boolean existence
>   flag. I suggest that we have an Entry class that is templated on the 
> key,
>   and specialised for pointer-typed keys to treat null keys as holes.
>- Template the hash function and remove the hash fields, because
>passing in our own hash values is asking for trouble
>- Template the equals/matching function, since we'd be having to
>template it on the key type anyway, to skip that dereference
>- Move the allocator to a field, because passing different allocators
>around as parameters is super sketchy
>   - More precisely, move it to a private base class to take advantage
>   of the empty base-class optimisation
>- Add a function argument to LookupOrInsert which creates the value,
>since the Value type is templated and so we can't rely on null values to
>mean newly-inserted entries
>
> And maybe, though I'm less convinced about these:
>
>- Return value references directly for Lookup/LookupOrInsert, rather
>than Entries, to make Entries non-public
>- Add an stl-like iterator interface rather than Start/Next, also to
>make Entries non-public
>
> Most of these I could wrap in a particular 

[v8-dev] TemplateHashMap changes proposal

[leszeks]

Hi all,

We (ignition) are looking to use base/hashmap (TemplateHashMap), but there 
are a couple of things that I want to change/add for efficiency's sake. 
Because these changes would have far-reaching effects, I wanted to send out 
the proposed changes before trying to upload any CLs.

My proposed changes are:

   - Template the value type, so that small types (e.g. ints) can be stored 
   inline rather than allocated
   - Template the key type, for the same reason
  - This has some far reaching effects -- e.g. we can't store holes as 
  nullptr keys anymore, but have to have a separate boolean existence flag. 
I 
  suggest that we have an Entry class that is templated on the key, and 
  specialised for pointer-typed keys to treat null keys as holes.
   - Template the hash function and remove the hash fields, because passing 
   in our own hash values is asking for trouble
   - Template the equals/matching function, since we'd be having to 
   template it on the key type anyway, to skip that dereference
   - Move the allocator to a field, because passing different allocators 
   around as parameters is super sketchy
  - More precisely, move it to a private base class to take advantage 
  of the empty base-class optimisation
   - Add a function argument to LookupOrInsert which creates the value, 
   since the Value type is templated and so we can't rely on null values to 
   mean newly-inserted entries

And maybe, though I'm less convinced about these:

   - Return value references directly for Lookup/LookupOrInsert, rather 
   than Entries, to make Entries non-public
   - Add an stl-like iterator interface rather than Start/Next, also to 
   make Entries non-public

Most of these I could wrap in a particular