Re: [Gc] weak maps and libgc
ivmai at mail.ru
Wed Oct 26 22:18:17 PDT 2011
25 10 2011, 14:07 Andy Wingo <wingo at pobox.com>:
> Hi Ivan,
> Thanks for the response!
> On Fri 21 Oct 2011 16:40, Ivan Maidanski <ivmai at mail.ru> writes:
> > Could you please summarize your past writings about the
> > implementations difficulties? Thanks.
> Last weekend I rewrote Guile's weak maps and weak sets, and so these
> things are fresh in my mind.
> 1. You can't reliably use the "buckets and chains" strategy to
> implement weak hash tables with libgc.
> The reason is that with this strategy, creating an entry in the
> table allocates memory: typically one spine segment and one rib
> segment. Typically you would allocate the rib with a GC kind that
> only marks the value if the key has not been nulled out.
> However, if the GC collects the key and nulls out one or both parts
> of the rib, or even the link from the spine to the rib, you are
> still left with at least an extra spine segment.
> You can lazily collect spine segments, but that will only happen
> when your hash table gets full, relatively speaking. Or you can go
> over the whole table and remove dead ribs and their corresponding
> spine segments, but this is expensive. However, when would you do
> this? The right time to do it is after GC, when disappearing links
> are nulled out, but there is no after-GC hook. More on this
To remove an extra spine segment,
I've added a finalizer to the key which unchains the element (spine segment) no longer referring to key (the field is cleared by GC before running finalizers).
> Consider a use pattern like:
> foo = new_weak_table ();
> while (1)
> weak_table_set (foo, new_key (), new_value());
> If you never go over the whole table to remove links, *there is
> practically no upper bound on your memory usage* because you will
> keep adding entries to the table, GC happens less and less
> frequently relative to the insertion rate because of the rising
> heap size (due to spines, ribs, and the keys and values that
> haven't yet been collected), and the dead mappings still take up
> memory (via the spines and ribs). It is actually worse if you have
> the ability to resize tables, for some loads.
> I haven't proven that result mathematically but I'm convinced that
> weak maps implemented as buckets-and-chains hash tables is a bad
> idea with libgc. So the new weak maps I used in Guile are
> open-addressed linear-probe tables with robin hood collision
> resolution. That solves this dead-entries-occupying-memory issue.
> 2. Keeping an accurate idea of the load factor of the table is
> important to know when to resize the table, either up or down.
> However if the GC is constantly removing entries, then your idea of
> how many elements are in the table is imprecise. In a
> multithreaded program there is no way to know how many elements are
> actually in your table. You can know the upper bound but not the
> number of those elements that have been removed.
> This is important in the workload for (1). Say your load has
> reached the point at which you would resize up. But what if you
> actually don't need to do so, because there are enough nulled out
> entries? Unfortunately you can't know that.
> Also it's not a good idea to traverse the table looking for nulled
> entries before making the resize decision, and not only because
> it's expensive to visit each entry. The real reason is that if a
> large portion of your keys are really alive, you could get into
> tortoise-and-hare races in which reaping the dead entries in the
> table does allow you to move forward, but you end up traversing the
> whole table more times than you would if you just resized anyway.
> The only way to keep an accurate count in a weak table is to have
> integration with the GC. If the GC nulls out an element in a
> particular memory region, it could decrement a counter. But there
> is no support for this in libgc.
> 3. The proper time to update the count for a weak table is after GC,
> as I have said. But there libgc does not have any notifiers that
> GC has happened. It has the start_callback, but you can't
> generally do anything there; what I need is a stop_callback that
> happens outside the alloc lock, in which I can allocate memory.
> Currently with newer GC I use the start_callback to tell Guile to
> register a procedure to be called "whenever", which will happen
> after GC. With older GC I have to play a trick with finalizers;
> it's in the attached code, and is terrible.
> 4. Moving items in an open-addressed table requires moving
> disappearing links. There is no way to do this currently in libgc:
> you have to unregister one and register another. This allocates
> 5. Accessing elements of a weak table is very expensive, as it has to
> happen in the alloc lock. If weak tables were part of GC, it could
> make it cheaper to access elements, maybe. But I won't push this,
> as I also need custom equality predicates. Currently traversing a
> set with an occupancy of about 4000 of 7000 slots, and reshuffling
> the table as nulled elements are removed, takes about 100
> nanoseconds per element. I'm estimating that based on the total of
> about 300 or 500 microseconds to reap the table, which is a lot.
> As you can imagine there is a fair amount of variance depending on
> the number of items that need to be moved.
> 6. There is no way around the fact that values in a weak-key map are
> strong references, and can thus keep their keys alive
> indefinitely. This issue is covered in the ephemeron paper I
> linked to, and could also be solved by the GC.
I don't understand what do you mean in 6.
> I have attached my new weak set implementation, as it shows most of the
> issues. Weak maps are the same except the entry has a value as well,
> and for singly-weak tables (key-weak or value-weak, but not
> doubly-weak), we have to use a special GC kind to get the marking
> right. (Doubly weak tables can just use atomic memory regions.)
> Thanks for reading. The implementation follows. It's pretty
> straightforward but you'll need a couple of typedefs to get it:
> /* Function that returns nonzero if the given object is the one we are
> looking for. */
> typedef int (*scm_t_set_predicate_fn) (SCM obj, void *closure);
> /* Function to fold over the elements of a set. */
> typedef SCM (*scm_t_set_fold_fn) (void *closure, SCM key, SCM result);
More information about the Gc