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 14988BD74 for ; Thu, 18 Aug 2005 07:19:12 +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 j7I5JBcs021270 for ; Thu, 18 Aug 2005 07:19:11 +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 HAA32744 for ; Thu, 18 Aug 2005 07:19:11 +0200 (MET DST) Received: from zproxy.gmail.com (zproxy.gmail.com [64.233.162.193]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j7I5JAZX022339 for ; Thu, 18 Aug 2005 07:19:10 +0200 Received: by zproxy.gmail.com with SMTP id x3so224052nzd for ; Wed, 17 Aug 2005 22:19:09 -0700 (PDT) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; b=e3RfHwFAaF/bU5hw1hoTn97jb9Civ5h2kqEXHf7/hxiMy7UzJ1QY4Z33O1c38ntCcfsZXRTwGkH6HpdLHB75sdCZkEDCu4Z/7c4aornCKytZBicONwEvhFXNxELpCn7kqndqASmtE0FzRuJX7tqdQCe0GxXlo/rn4aE+Y+rT75w= Received: by 10.36.158.3 with SMTP id g3mr1176393nze; Wed, 17 Aug 2005 22:19:09 -0700 (PDT) Received: by 10.36.17.2 with HTTP; Wed, 17 Aug 2005 22:19:09 -0700 (PDT) Message-ID: Date: Wed, 17 Aug 2005 22:19:09 -0700 From: Nathaniel Gray To: Alain Frisch Subject: Re: [Caml-list] Cost of register_global_root Cc: Bardur Arantsson , caml-list@inria.fr In-Reply-To: <4303F52B.8010400@inria.fr> Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline References: <4303F52B.8010400@inria.fr> X-Miltered: at nez-perce with ID 43041A4F.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 43041A4E.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 frisch:01 frisch:01 runtime:01 wrote:01 wrote:01 caltech:02 caltech:02 data:02 roots:02 roots:02 alain:03 alain:03 root:03 root:03 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=RCVD_BY_IP autolearn=disabled version=3.0.3 On 8/17/05, Alain Frisch wrote: > 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? >=20 > 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. Sounds reasonable. > 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). That's exactly what I was planning, but I wasn't entirely sure it was actually necessary. > This might be necessary if the custom blocks are under the control of > another memory management system which can moves blocks around. Thanks, -n8 --=20 >>>-- Nathaniel Gray -- Caltech Computer Science ------> >>>-- Mojave Project -- http://mojave.cs.caltech.edu -->