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 mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by yquem.inria.fr (Postfix) with ESMTP id 0808DBC57 for ; Fri, 19 Mar 2010 11:12:47 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AscBAFfqokvZSMDdkGdsb2JhbACbMRUBAQEBCQkMBxMDH7p/gkuCLwQ X-IronPort-AV: E=Sophos;i="4.51,273,1267398000"; d="scan'208";a="47436294" Received: from fmmailgate01.web.de ([217.72.192.221]) by mail2-smtp-roc.national.inria.fr with ESMTP; 19 Mar 2010 11:12:46 +0100 Received: from smtp05.web.de (fmsmtp05.dlan.cinetic.de [172.20.4.166]) by fmmailgate01.web.de (Postfix) with ESMTP id 23AEF14EDDFDF; Fri, 19 Mar 2010 11:12:46 +0100 (CET) Received: from [78.43.204.177] (helo=frosties.localdomain) by smtp05.web.de with asmtp (TLSv1:AES256-SHA:256) (WEB.DE 4.110 #4) id 1NsZC9-0004Ij-00; Fri, 19 Mar 2010 11:12:46 +0100 Received: from mrvn by frosties.localdomain with local (Exim 4.71) (envelope-from ) id 1NsZC9-0006Mw-7L; Fri, 19 Mar 2010 11:12:45 +0100 From: Goswin von Brederlow To: Hugo Ferreira Cc: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Shared data space: How to manage Ancient keys? References: <4BA271D2.9030602@inescporto.pt> Date: Fri, 19 Mar 2010 11:12:45 +0100 In-Reply-To: <4BA271D2.9030602@inescporto.pt> (Hugo Ferreira's message of "Thu, 18 Mar 2010 18:32:50 +0000") Message-ID: <87hboc4o2q.fsf@frosties.localdomain> User-Agent: Gnus/5.110009 (No Gnus v0.9) XEmacs/21.4.22 (linux, no MULE) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Sender: goswin-v-b@web.de X-Sender: goswin-v-b@web.de X-Provags-ID: V01U2FsdGVkX18heZUvGER3/H/CZ33EOO7e4dAM49QZEV+d2wkQ z3fobgwk849UJdnHoL2dTshzZnRSqrWIc82xvhy57mUt2Bi/96 Vw2+K8JcY= X-Spam: no; 0.00; ocaml:01 mfg:98 dynamically:01 integer:01 caml-list:01 writes:01 reuse:01 algorithm:01 linear:02 data:02 data:02 tree:02 tree:02 binary:02 binary:02 Hugo Ferreira writes: > Hello, > > I am trying to implement a parallel algorithm and have opted to use > the Ancient module to share data across processes because it dynamically > reallocates memory when mapping data (I don't know the size of the > objects before hand). However I am having trouble managing its use of > keys. > > Maybe someone here has a solution to my problem. > > To make things clear - a little background. I have a set of worker > processes that cooperate to analyse a set of sequences. I assume > all sequences are in a global blackboard-type /LINDA-like data space. > Each worker removes a single sequence. It then scans all other existing > sequences and selects another one. It then a) removes the selected > sequence b) merges the 2 sequences at hand and generates 0, 1 or more > new sequences. The process repeats itself until no more sequences exist > in the global data space. > > In the above scenario all sequences would be assigned a unique id which > increases sequentially. If I used a common data structure such as a > binary tree I could simply increment a counter and use that as a key > for the insertion/deletion of sequences into/from the binary tree. > However I cannot do this here because I can only share linear memory > via mapped files in Ocaml. > > So far I have made a small experiment that allows me to insert data > into a shared memory space. Ancient allows one to copy various objects > into the memory space via an integer index. From the code it seems that > the indexing table is an array like structure. So when I add and object > I must identify an index (slot) that is empty (unused) and reuse that > otherwise memory will grow unchecked. > > My question is how can I generate and share keys for Ancient's use > without exceeding memory usage? > > TIA, > Hugo F. How about a simple solution. Only one thread handles indexes. You said you have worker processes. Add one controling process on top of it that spawns all the worker processes and keeps a communication line open with them, e.g. a pipe. Each worker would then tell the controller to remove an index or request an unused index to store a result. Its probably a good idea to request unused indexes in bunches, say 100 at a time to cut down on latenzy. MfG Goswin