On 2015/04/28 09:32:34, Erik Corry wrote:
Not happy with this change.
Using addresses for hashes is nasty because it adds work to the atomic
phases
of
the GC. This is the opposite way to the one we want to go. If the
argument
is
that we won't use this feature heavily, then I wonder if we can find a
cleaner
way to implement this rarely used feature.
Ideally there would be no extra work, but that's not really workable. We
might
reduce this by splitting up the storage into many smaller regions that don't
have to be atomically scanned as roots (i.e. could be incrementally
marked), but
I foresee nothing but complexity for little real benefit. In comparison to
the
other roots we are scanning, e.g. the stack and string tables, a couple
32-word
regions of pointers is miniscule.
Can we calculate the hash from the objects themselves instead of their
address.
As I understand it, they are often maps, which are largely immutable.
No, because that would mean not only dereferencing the handle, but
dereferencing
the object address; there is no stable hash for an arbitrary object, and
yes,
the compiler absolutely wants to canonicalize objects based on their
identity.
Are thread-safe handles created on the compiler thread? If yes, does it
read
concurrently from objects on the single-threaded heap to create them and
is
that
not dangerous. If no, can we put a stable hash in the thread-safe
handle, eg
the address of the object at the time the handle was created?
At the moment, no. Canonicalizing object references is step 0. But yes, in
the
future we will want to read from objects on the heap concurrently
eventually, in
particular the map and then start reading data from the map. Each of those
steps
will require careful thought to make sure it is safe and properly fenced.
Putting a "stable" hash in the thread-safe handle is exactly what Unique<T>
does. That's not enough. We need to canonicalize based on object-identity.
One could consider a special handle scope that canonicalizes handle
locations,
and then use the location of the handle as the uniqueness. But that's
essentially just making this IdentityMap<T> itself into a handlescope. Maybe
something for the future.
https://codereview.chromium.org/1105693002/diff/20001/src/heap/identity-map.cc
File src/heap/identity-map.cc (right):
https://codereview.chromium.org/1105693002/diff/20001/src/heap/identity-map.cc#newcode72
src/heap/identity-map.cc:72: Resize(); // Should only have to resize
once,
since we grow 4x.
On 2015/04/27 16:32:50, titzer wrote:
> On 2015/04/27 15:39:13, Erik Corry wrote:
> > That's very aggressive. Was 2x too slow?
> > Also this heuristic for growing will make the timing of the growing
dependent
> on
> > ASLR, which is rather unpredictable for my taste.
>
> 4x guarantees that there are no chains that size_ / 2 the next time
through
the
> loop, because now size_ is 4x as big.
>
> The backstory here is that we expect these tables to be sparse and
rather
than
> go for a complex hashing scheme, start with one that's much easier to
get
right.
> Thus I wanted to avoid doing buckets and chains which would require a
more
> complex interface to the GC.
>
> I considered doing cuckoo hashing (e.g. after a collision, use some more
bits
> from the hash for the next search location). Without any data about the
> collision frequency, the complexity doesn't seem justified yet.
Rather than cuckoo I would go with Robin Hood hashes, but I agree it's not
necessarily worth it.
https://codereview.chromium.org/1105693002/diff/40001/src/heap/identity-map.cc
File src/heap/identity-map.cc (right):
https://codereview.chromium.org/1105693002/diff/40001/src/heap/identity-map.cc#newcode13
src/heap/identity-map.cc:13: static const int kInitialIdentityMapSize =
32;
I just reduced the similar constant for element dictionaries from 32 to 4
at
no
cost in performance. Let's not burn memory if we can avoid it.
https://codereview.chromium.org/1105693002/diff/40001/src/heap/identity-map.cc#newcode14
src/heap/identity-map.cc:14: static const int kResizeFactor = 4;
Add a comment that the correctness of the table depends on this being >= 4
Alternatively change from a consecutive-collisions based growing
heuristic to
a
more conventional fullness-based heuristic. This would prevent the growth
from
being dependent on a source of randomness (ASLR).
https://codereview.chromium.org/1105693002/diff/40001/src/heap/identity-map.cc#newcode172
src/heap/identity-map.cc:172: CHECK_LE(size_, (1024 * 1024 * 16)); //
that
would be extreme...
You really want to deliberately crash the release mode VM for this?
Also capital 't'.
https://codereview.chromium.org/1105693002/diff/40001/src/heap/identity-map.cc#newcode188
src/heap/identity-map.cc:188: heap_->RegisterStrongRoots(keys_, keys_ +
size_);
Where do we free the keys and values?
https://codereview.chromium.org/1105693002/diff/40001/src/heap/identity-map.h
File src/heap/identity-map.h (right):
https://codereview.chromium.org/1105693002/diff/40001/src/heap/identity-map.h#newcode65
src/heap/identity-map.h:65: // The value type {V} must be
reinterpret_cast'able
to void*.
Add comment that V should not be a heap object type or a pointer to a heap
object type. Ideally also a static assert.
https://codereview.chromium.org/1105693002/diff/40001/test/cctest/test-identity-map.cc
File test/cctest/test-identity-map.cc (right):
https://codereview.chromium.org/1105693002/diff/40001/test/cctest/test-identity-map.cc#newcode121
test/cctest/test-identity-map.cc:121: CHECK_NULL(t.map.Find(t.smi(i)));
Is there a missing assert, since you can look up Smi 0, which is an
illegal
key?
https://codereview.chromium.org/1105693002/
--
--
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.
