On 2015/05/26 17:42:00, adamk wrote:
I'm worried that this over-fits our hashing strategy to the implementation
details of these particular data structures. If objects added to a Map or
Set
are later added to a WeakMap, they'll end up with exactly the bad
behavior you
describe in the CL description for open-addressed hash tables (though I
suppose
we could use different private symbols for hashing in an ObjectHashTable
vs an
OrderedHashTable).
This hashing strategy may also be over-fit to the microbenchmark, since
new
objects are created and inserted once, meaning that the ordering of the
hash
codes always matches the ordering of the container. In more varied
workloads
(such as adding and removing the same objects from a set), I'd this to be
a
wash.
If you disagree with the above, can you help me overcome these concerns?
I had a different more complicated version that was less likely to cause
problems
for an open addressing hash. I put it here for reference:
https://codereview.chromium.org/1158083002
It also gives a good speedup on the modified example from bug 4086. Where
this
CL
lowers runtime by 62% the 1158083002 change above gives only gives about 53%
reduction. I don't think there's anything special about the example from
4086
other
than that it's a big table. If you look at the spreadsheet I shared you
can see
that
benefits are visible even on 10-element collections, and for each order of
magnitude the collection grows, the benefit becomes clearer. The benefits
are
seen even if objects are not inserted in the exact order that they were
given
hash
codes: I think that follows from the fact that 1158083002 works too - check
out
the codes it gives out.
There are other solutions. We could give out different hash codes for
different
purposes,
as you say, or fix weak map to use the same strategy as Map() and Set().
At this point I'm more than running out of time to spend on this, so
probably
I'll just leave
these two CLs there as inspiration. The implementation of Map() and Set() is
rather neat
in terms of how it keeps track of insertion order and how it handles
collisions,
but it has
some cache locality issues with the current hash code.
https://codereview.chromium.org/1157073002/
--
--
v8-dev mailing list
[email protected]
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 [email protected].
For more options, visit https://groups.google.com/d/optout.
