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 70627BDCB for ; Sat, 10 Sep 2005 09:04:53 +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 j8A74qhH004934 for ; Sat, 10 Sep 2005 09:04:53 +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 JAA00967 for ; Sat, 10 Sep 2005 09:04:52 +0200 (MET DST) Received: from mallaury.nerim.net (smtp-106-saturday.noc.nerim.net [62.4.17.106]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j8A74qGb011263 for ; Sat, 10 Sep 2005 09:04:52 +0200 Received: from [192.168.1.2] (xleroy.net1.nerim.net [62.212.116.147]) by mallaury.nerim.net (Postfix) with ESMTP id EA0CA4F3A0; Sat, 10 Sep 2005 09:04:46 +0200 (CEST) Message-ID: <43228592.1040800@inria.fr> Date: Sat, 10 Sep 2005 09:04:50 +0200 From: Xavier Leroy User-Agent: Mozilla Thunderbird 1.0.2 (X11/20050317) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Bardur Arantsson Cc: caml-list@inria.fr Subject: Re: [Caml-list] Re: announce: callbacks-0.1 References: <43206744.5090907@univ-savoie.fr> <4320A68E.1060608@xs4all.nl> <4320ABF7.7020009@univ-savoie.fr> In-Reply-To: X-Enigmail-Version: 0.91.0.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-Miltered: at nez-perce with ID 43228594.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 43228594.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 globroots:01 hashtable:01 hash:01 enumeration:01 descriptors:01 callbacks:01 callbacks:01 hashtable:01 ocaml:01 generational:01 minor:01 unregistered:98 roots:02 roots:02 > 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