Version française
Home     About     Download     Resources     Contact us    
Browse thread
Re: Caml-list] Sets and home-made ordered types
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: CUOQ Pascal <Pascal.CUOQ@c...>
Subject: Re: Sets and home-made ordered types
> So what, one pointer more for each association 
> in the Map? That would be rather acceptable (but still not ideal, sorry 
> I'm very demanding).

You were already paying the price of "one pointer more"
many times over and were not even thinking about it. One
more will not make any difference.

You have to realize that each node already carries a height,
two pointers to subtrees, and take into account the one-word
overhead for the block header. We're not doubling the size of
each tree node here, we're increasing it from 5 to 6 words.

Pascal
PS: You make up for the overhead by having dynamic structures
that are just the right size, and by taking advantage of sharing,
of course.