Version française
Home     About     Download     Resources     Contact us    
Browse thread
announce: callbacks-0.1
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Bardur Arantsson <spam@s...>
Subject: Re: announce: callbacks-0.1
Xavier Leroy wrote:
>>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).
>

D'oh, don't know how I could have missed that... Sorry for the 
misinformation.

> 
>>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.
> 

Unfortunately I haven't kept any of the benchmark results. Of course I 
don't have old source to compile from either since this was before I put 
it into version control :(. I supposed there's a lesson in there somewhere.

I'm not really motivated to attempt to reconstruct a benchmark for this 
as 1) I've since moved to an event library which only uses short-lived 
callbacks at the C/OCaml interface. 2) I just don't have the time.

Cheers,

-- 
Bardur Arantsson
<bardur@imada.sdu.dk>
<bardur@scientician.net>

- I'm a well-wisher... in that I don't wish you any *specific*
harm.
                                               Moe, 'The Simpsons'