Re: [Caml-list] Specialized dictionaries

[Sven <luther@dpt-info.u-strasbg.fr>]

On Mon, Nov 05, 2001 at 08:56:40PM +0000, Marcin 'Qrczak' Kowalczyk wrote:
> Mon, 5 Nov 2001 19:24:06 +0100, Nicolas George <nicolas.george@ens.fr> 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