From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id D0F13BDCB for ; Sat, 10 Sep 2005 09:34:10 +0200 (CEST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j8A7YAG3006965 for ; Sat, 10 Sep 2005 09:34:10 +0200 Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id JAA01327 for ; Sat, 10 Sep 2005 09:34:09 +0200 (MET DST) Received: from ciao.gmane.org (main.gmane.org [80.91.229.2]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j8A7Y8HY013472 (version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=NO) for ; Sat, 10 Sep 2005 09:34:09 +0200 Received: from list by ciao.gmane.org with local (Exim 4.43) id 1EDzr8-0004sM-9q for caml-list@inria.fr; Sat, 10 Sep 2005 09:32:58 +0200 Received: from 0x50a5bb8d.odnxx9.adsl-dhcp.tele.dk ([80.165.187.141]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Sat, 10 Sep 2005 09:32:58 +0200 Received: from spam by 0x50a5bb8d.odnxx9.adsl-dhcp.tele.dk with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Sat, 10 Sep 2005 09:32:58 +0200 X-Injected-Via-Gmane: http://gmane.org/ To: caml-list@inria.fr From: Bardur Arantsson Subject: Re: announce: callbacks-0.1 Date: Sat, 10 Sep 2005 09:31:48 +0200 Message-ID: References: <43206744.5090907@univ-savoie.fr> <4320A68E.1060608@xs4all.nl> <4320ABF7.7020009@univ-savoie.fr> <43228592.1040800@inria.fr> Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Complaints-To: usenet@sea.gmane.org X-Gmane-NNTP-Posting-Host: 0x50a5bb8d.odnxx9.adsl-dhcp.tele.dk User-Agent: Mozilla Thunderbird 1.0.6 (X11/20050803) X-Accept-Language: en-us, en In-Reply-To: <43228592.1040800@inria.fr> Sender: news X-Miltered: at nez-perce with ID 43228C72.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 43228C70.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; globroots:01 hashtable:01 hash:01 enumeration:01 descriptors:01 callbacks:01 callbacks:01 hashtable:01 ocaml:01 generational:01 minor:01 ocaml:01 cheers:01 sdu:01 ...:98 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 - I'm a well-wisher... in that I don't wish you any *specific* harm. Moe, 'The Simpsons'