We threw around a lot of different ideas for avoiding complicated
weakness schemes for maps and iterators (which our GC guys would not
like). Here is what I now think is the easiest solution: a variant of
difference arrays. That's a technique from functional language
compilers for implementing non-destructive persistent arrays with
constant-time read & update.
Adapted to the iterator scenario it would work as follows:
- Every iterator references (a version of) the backing store of the
map directly, instead of just the map object.
- Normally, add and remove operations just modify the backing store in
place, deletes are marked by tombstones (as now).
- When compacting, create a new backing store, copy over, update the
map to point to that (as now).
- At the same time, the old backing store is marked as deprecated, and
amended with (1) a pointer to the new backing store, and (2) an
appropriate description of the diff.
- On .next, iterators can check for the deprecation mark and easily
resync using the extra info.
Note how in this scheme, versions of the backing store are forward
linked, forming a change log (the chains can be longer than 1, of
course). No weakness is involved. If no iterator references the old
version of a backing store it becomes garbage immediately; otherwise
it does after all iterators have either resynced or become garbage
themselves.
https://codereview.chromium.org/259883002/
--
--
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.
