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 concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id CBFADBCA2 for ; Thu, 18 Aug 2005 04:45:07 +0200 (CEST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j7I2j70f010214 for ; Thu, 18 Aug 2005 04:45:07 +0200 Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id EAA30747 for ; Thu, 18 Aug 2005 04:45:06 +0200 (MET DST) Received: from postfix3-2.free.fr (postfix3-2.free.fr [213.228.0.169]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j7I2j6h8009873 for ; Thu, 18 Aug 2005 04:45:06 +0200 Received: from [192.168.0.1] (rke75-3-82-229-183-156.fbx.proxad.net [82.229.183.156]) by postfix3-2.free.fr (Postfix) with ESMTP id 3E91BC06A; Thu, 18 Aug 2005 04:45:06 +0200 (CEST) Message-ID: <4303F52B.8010400@inria.fr> Date: Thu, 18 Aug 2005 04:40:43 +0200 From: Alain Frisch User-Agent: Debian Thunderbird 1.0.2 (X11/20050331) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Nathaniel Gray Cc: Bardur Arantsson , caml-list@inria.fr Subject: Re: [Caml-list] Cost of register_global_root References: In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 4303F633.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 4303F632.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; frisch:01 frisch:01 caml-list:01 runtime:01 wrote:01 data:02 roots:02 roots:02 alain:03 alain:03 root:03 root:03 structure:04 inria:05 complexity:07 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.3 Nathaniel Gray wrote: > One thing that the FM doesn't mention is how expensive it is to > register a global root. Can I register thousands of them or will > there be performance problems? The runtime system stores the global roots in a skip list. One should expect probabilistic O(log n) complexity with a small constant for each insertion and deletion, where n is the number of already registered global roots. Another option is to manage the roots yourself (e.g. you put them in an array and store indexes into this array in your custom data structure). This might be necessary if the custom blocks are under the control of another memory management system which can moves blocks around. -- Alain