* Re: [Caml-list] why does hashtbl not use lists?
@ 2001-07-10 17:04 Charles Martin
0 siblings, 0 replies; 6+ messages in thread
From: Charles Martin @ 2001-07-10 17:04 UTC (permalink / raw)
To: caml-list
At 07:42 PM 7/10/01 +1000, Fergus Henderson wrote:
>If you have a compacting garbage collector, as I'm pretty sure Ocaml does,
>and a good compiler, then the compiler would be able to combine the two
>allocations into a single one. Does Ocamlopt do that?
In my experience, yes, every time: asmcomp/comballoc.ml
__________________________________________________
Do You Yahoo!?
Get personalized email addresses from Yahoo! Mail
http://personal.mail.yahoo.com/
-------------------
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
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Caml-list] why does hashtbl not use lists?
2001-07-10 9:42 ` Fergus Henderson
@ 2001-07-10 14:44 ` Xavier Leroy
0 siblings, 0 replies; 6+ messages in thread
From: Xavier Leroy @ 2001-07-10 14:44 UTC (permalink / raw)
To: Fergus Henderson; +Cc: caml-list
> I thought about mentioning the time saving from the reduced number of
> allocations, but then I wondered whether it would really save any time.
> If you have a compacting garbage collector, as I'm pretty sure Ocaml does,
> and a good compiler, then the compiler would be able to combine the two
> allocations into a single one. Does Ocamlopt do that?
Yes, it does. Still, you save two stores at allocation time with the
flat representation -- in addition to the more significant time
savings at access time (one fewer indirection).
- Xavier Leroy
-------------------
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
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Caml-list] why does hashtbl not use lists?
2001-07-10 9:05 ` Jean-Christophe Filliatre
@ 2001-07-10 9:42 ` Fergus Henderson
2001-07-10 14:44 ` Xavier Leroy
0 siblings, 1 reply; 6+ messages in thread
From: Fergus Henderson @ 2001-07-10 9:42 UTC (permalink / raw)
To: Jean-Christophe Filliatre; +Cc: Chris Hecker, caml-list
On 10-Jul-2001, Jean-Christophe Filliatre <Jean-Christophe.Filliatre@lri.fr> wrote:
>
> Chris Hecker writes:
> >
> > Why does hashtbl.ml (from the standard library) use the bucketlist
> > variant instead of just the built in lists with tuples? Is there an
> > efficiency thing going on here?
>
> Yes, it saves 33% of memory. Indeed, a list of tuples will give blocks
> like this:
>
> ______
> |X|.|.|......>
> ---.-- _______
> ......> |X|a|b|
> -------
>
> that is, 6 words for each binding, whereas the bucketlist type will
> give blocks like this:
>
> _________
> |X|a|b|.|....>
> ---------
>
> that is, 4 words. (X stands for the block header, which is 1 word and
> dots stand for pointers; sory for the ugly ASCII drawing).
No doubt you are right about it being 6 words vs 4 words,
rather than 4 words vs 3 words, as I said in my earlier mail;
I didn't recall that Ocaml used a header word here.
> (Beside saving memory, you also save time, by allocating one block
> instead of two and also when destructuring the block to look inside,
> since depth is 1 instead of 2.)
I thought about mentioning the time saving from the reduced number of
allocations, but then I wondered whether it would really save any time.
If you have a compacting garbage collector, as I'm pretty sure Ocaml does,
and a good compiler, then the compiler would be able to combine the two
allocations into a single one. Does Ocamlopt do that?
--
Fergus Henderson <fjh@cs.mu.oz.au> | "I have always known that the pursuit
The University of Melbourne | of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh> | -- the last words of T. S. Garp.
-------------------
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
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Caml-list] why does hashtbl not use lists?
2001-07-10 8:34 Chris Hecker
2001-07-10 9:00 ` Fergus Henderson
@ 2001-07-10 9:05 ` Jean-Christophe Filliatre
2001-07-10 9:42 ` Fergus Henderson
1 sibling, 1 reply; 6+ messages in thread
From: Jean-Christophe Filliatre @ 2001-07-10 9:05 UTC (permalink / raw)
To: Chris Hecker; +Cc: caml-list
Chris Hecker writes:
>
> Why does hashtbl.ml (from the standard library) use the bucketlist
> variant instead of just the built in lists with tuples? Is there an
> efficiency thing going on here?
Yes, it saves 33% of memory. Indeed, a list of tuples will give blocks
like this:
______
|X|.|.|......>
---.-- _______
......> |X|a|b|
-------
that is, 6 words for each binding, whereas the bucketlist type will
give blocks like this:
_________
|X|a|b|.|....>
---------
that is, 4 words. (X stands for the block header, which is 1 word and
dots stand for pointers; sory for the ugly ASCII drawing).
(Beside saving memory, you also save time, by allocating one block
instead of two and also when destructuring the block to look inside,
since depth is 1 instead of 2.)
--
Jean-Christophe Filliatre
mailto:Jean-Christophe.Filliatre@lri.fr
http://www.lri.fr/~filliatr
-------------------
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
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [Caml-list] why does hashtbl not use lists?
2001-07-10 8:34 Chris Hecker
@ 2001-07-10 9:00 ` Fergus Henderson
2001-07-10 9:05 ` Jean-Christophe Filliatre
1 sibling, 0 replies; 6+ messages in thread
From: Fergus Henderson @ 2001-07-10 9:00 UTC (permalink / raw)
To: Chris Hecker; +Cc: caml-list
On 10-Jul-2001, Chris Hecker <checker@d6.com> wrote:
>
> Why does hashtbl.ml (from the standard library) use the bucketlist variant
> instead of just the built in lists with tuples? Is there an efficiency thing
> going on here?
Yes. I didn't write the code, but I'm sure that's the reason.
A list of pairs will use two two-word cells per list element,
whereas a bucketlist will use one three-word cell; as well as reducing
the amount of memory allocated, it also avoids an indirection.
P.S. We happen to use the same kind of trick in the Mercury standard library,
for lists of tokens in the Mercury lexer:
% This "fat list" representation is more efficient than a list of pairs.
:- type token_list ---> token_cons(token, token_context, token_list)
; token_nil.
But note that we at least document why we do it! ;-)
--
Fergus Henderson <fjh@cs.mu.oz.au> | "I have always known that the pursuit
The University of Melbourne | of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh> | -- the last words of T. S. Garp.
-------------------
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
^ permalink raw reply [flat|nested] 6+ messages in thread
* [Caml-list] why does hashtbl not use lists?
@ 2001-07-10 8:34 Chris Hecker
2001-07-10 9:00 ` Fergus Henderson
2001-07-10 9:05 ` Jean-Christophe Filliatre
0 siblings, 2 replies; 6+ messages in thread
From: Chris Hecker @ 2001-07-10 8:34 UTC (permalink / raw)
To: caml-list
Why does hashtbl.ml (from the standard library) use the bucketlist variant instead of just the built in lists with tuples? Is there an efficiency thing going on here?
type ('a, 'b) t =
{ mutable max_len: int; (* max length of a bucket *)
mutable data: ('a, 'b) bucketlist array } (* the buckets *)
and ('a, 'b) bucketlist =
Empty
| Cons of 'a * 'b * ('a, 'b) bucketlist
instead of
type ('a, 'b) t =
{ mutable max_len: int; (* max length of a bucket *)
mutable data: ('a * 'b) list array } (* the buckets *)
Chris
-------------------
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
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2001-07-11 15:54 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2001-07-10 17:04 [Caml-list] why does hashtbl not use lists? Charles Martin
-- strict thread matches above, loose matches on Subject: below --
2001-07-10 8:34 Chris Hecker
2001-07-10 9:00 ` Fergus Henderson
2001-07-10 9:05 ` Jean-Christophe Filliatre
2001-07-10 9:42 ` Fergus Henderson
2001-07-10 14:44 ` Xavier Leroy
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).