From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id TAA03468; Sat, 11 May 2002 19:18:34 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f 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 TAA03691 for ; Sat, 11 May 2002 19:18:33 +0200 (MET DST) Received: from mailrelay1.inwind.it (mailrelay1.inwind.it [212.141.54.101]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id g4BHIWH16736 for ; Sat, 11 May 2002 19:18:32 +0200 (MET DST) Received: from dalamar.takhisis.org (62.98.147.80) by mailrelay1.inwind.it (6.5.015) id 3CAA37A301B611E2 for caml-list@inria.fr; Sat, 11 May 2002 19:18:30 +0200 Received: from lordsoth.takhisis.org (lordsoth.takhisis.org [192.168.1.119]) by dalamar.takhisis.org (8.12.3/8.12.3/Debian -7) with ESMTP id g4BHIJtY007816 (version=TLSv1/SSLv3 cipher=EDH-RSA-DES-CBC3-SHA bits=168 verify=FAIL) for ; Sat, 11 May 2002 19:18:22 +0200 Received: from lordsoth.takhisis.org (lordsoth.takhisis.org [192.168.1.119]) by lordsoth.takhisis.org (8.12.3/8.12.3/Debian -7) with ESMTP id g4BHIIai006399 (version=TLSv1/SSLv3 cipher=EDH-RSA-DES-CBC3-SHA bits=168 verify=NO) for ; Sat, 11 May 2002 19:18:18 +0200 Received: (from zack@localhost) by lordsoth.takhisis.org (8.12.3/8.12.3/Debian -7) id g4BHIImN006397 for caml-list@inria.fr; Sat, 11 May 2002 19:18:18 +0200 Date: Sat, 11 May 2002 19:18:18 +0200 From: Stefano Zacchiroli To: caml-list@inria.fr Subject: Re: [Caml-list] Suggestion about balanced trees in stdlib Message-ID: <20020511171818.GA6384@cs.unibo.it> Mail-Followup-To: caml-list@inria.fr References: <20020510185954.C635@ice.gerd-stolpmann.de> <20020510223110.GB31219@cs.unibo.it> <20020511174704.A632@ice.gerd-stolpmann.de> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20020511174704.A632@ice.gerd-stolpmann.de> User-Agent: Mutt/1.3.28i Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Sat, May 11, 2002 at 05:47:04PM +0200, Gerd Stolpmann wrote: > type 'a map = Empty | Node of 'a map * key * 'a * 'a map * int > > type set = Empty | Node of set * elt * set * int > > The difference is that every map node has 6 words, and every set node > consists of 5 words. My suggestion is to prefer the map representation, > and define set = unit map, wasting one word per node, and making sets > 20% larger. Ok, I agree that this is the "clean" way to the goal. Anyway I think that memory consumption is crucial for the standard library, this is why I'm proposing a dirty trick for the set/map matter. Usually I dislike tricks and prefer clean programming, but IMHO a standard library is somewhat a particular case. Why not use a single source file that implement both set and map using some campl4 tricks like pa_ifdef module? You may have two different definitions of tree and a pool of accessor functions working on a tree and returning single components (hoping that the compiler inline this kind of functions). In the set case you doesn't need to use the value component of a tree so you can avoid to compile the relative accessor function (poor gain) and you can also compile a tree tuple without a value component. [ Question: gurus, do you thinks this is a feasible solution or I'm missing something? ] I know, this is a really dirty trick. Also I don't know if is applicable because I have never looked at the implementations set.ml and map.ml but just as an idea it can work. Pros: - reduce memory consumption for Set - no code duplication Cons: - objects (.cm{a,o,x...}) duplication - really dirty! - last time I looked at it camlp4 pa_ifdef module doesn't permit multiple declaration using only one "if" construct so you incurs in situations like: ifdef FOO then let bar = ... ifdef FOO then let quux = ... ifdef FOO then let baz = ... Just a [dirty] idea. Cheers. -- Stefano Zacchiroli - undergraduate student of CS @ Univ. Bologna, Italy zack@cs.unibo.it | ICQ# 33538863 | http://www.cs.unibo.it/~zacchiro "I know you believe you understood what you think I said, but I am not sure you realize that what you heard is not what I meant!" -- G.Romney ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners