> From the implementation in globroots.c it would seem that
> register_global_root is at least O(n) in the number of roots, and that
> it has a large constant overhead compared to e.g. adding something to a
> hashtable.

You should look harder.  register_global_root is insertion in a skip
list, which is probabilistic O(log n) with a low constant.  I don't
think a hash table would perform significantly better for the mix of
operations we need to do on the set of global roots (insertion,
deletion, and enumeration for the GC).

> That depends hugely on what kind of library you're wrapping. I did a
> wrapper for libevent (events on file descriptors and other similar stuff
> like alarms, etc.) and what ended up happening was that a 1) lot of the
> time a relatively large amount of callbacks were registered, orm 2)
> callbacks would be registered/unregistered a lot. I did try using
> *_global_roots in my libevent wrapper, but the performance was awful
> until I changed it to use an (fd->callback) hashtable on the OCaml side.

I would have been very interested in a profiling of your initial
implementation.  The only reason why the Caml hashtable can beat the
global roots is that the latter are not generational: since the
contents of registered global roots can change at any time without
notifying the GC, all global roots must be scanned at every minor
collection.

- Xavier Leroy