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 HAA30839; Tue, 6 Nov 2001 07:54:55 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f 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 HAA30581 for ; Tue, 6 Nov 2001 07:54:54 +0100 (MET) Received: from dpt-info.u-strasbg.fr (dpt-info.u-strasbg.fr [130.79.44.193]) by concorde.inria.fr (8.11.1/8.10.0) with ESMTP id fA66ss106308 for ; Tue, 6 Nov 2001 07:54:54 +0100 (MET) Received: (from luther@localhost) by dpt-info.u-strasbg.fr (8.9.3/8.9.3) id HAA10252; Tue, 6 Nov 2001 07:53:52 +0100 Date: Tue, 6 Nov 2001 07:53:51 +0100 From: Sven To: "Marcin 'Qrczak' Kowalczyk" Cc: caml-list@inria.fr Subject: Re: [Caml-list] Specialized dictionaries Message-ID: <20011106075351.A10137@dpt-info.u-strasbg.fr> References: <15334.27347.973997.129488@pc803> <9s6j7c$i6r$1@qrnik.zagroda> <9s6m53$k16$1@qrnik.zagroda> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Mailer: Mutt 1.0.1i In-Reply-To: ; from qrczak@knm.org.pl on Mon, Nov 05, 2001 at 08:56:40PM +0000 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Mon, Nov 05, 2001 at 08:56:40PM +0000, Marcin 'Qrczak' Kowalczyk wrote: > Mon, 5 Nov 2001 19:24:06 +0100, Nicolas George pisze: > > >> So updates are rare, dictionaries are > >> small and they contain small integers, but lookups are very frequent. > > > > What about using a simple array for that? > > Then usually contain small integers, but theoretically these integers > can go large. If many types are created in a program, then it would > be wasteful to allocate large arrays for each dispatched function > which uses a single type with a large number. > > Perhaps some heuristic could use an array for the initial segment > of numbers (which correspond to types created earlier) and another > dictionary for the rest, but it would complicate what is being > done purely for fun and for being simple. More importantly, small > differences such that loading modules in a different order could have > large effects; I don't like treating old types and young types in a > very different way. > > I've heard about packing multiple dispatch tables in a large array. > Well, it's complicated, and it's hard to perform dynamic updates if > slots are used by different functions. Updates are rare but they do > occur - for example if a dispatched function is used at a type for > the first time and the implementation was found at its supertype. What about using a datatype with several arrays, using a maximum number of entries per array or something like that, and then having a serie of such arrayys, or an array of arrays. You would just need to make a division and a modulo operation to get the right array and get the value, if you take the rigth max number, you could even get away with only bit shifts, which is not so expensive and two indirections instead of one. If you do it right, you could even have the datatype grow incrementally based on your needs. That will work only if you numbers are contigous though. That said, i had the impression that, as ocaml is optimized for functional datatypes, it will be more freindly to the GC that you use a functional datatype, and thus faster maybe. Friendly, Sven Luther ------------------- Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr