Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
Efficency of varient types
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2005-11-28 (09:27)
From: Christophe Raffalli <christophe.raffalli@u...>
Subject: Re: [Caml-list] Obj or not Obj
Nicolas Cannasse a écrit :
>> Just a small word about one of my bad experiment with Obj about tail rec
>> map ... it is easy to get a tail
>> rec map using Obj to make ocaml's list mutable ... it is just slower
>> that the original map and using roughly the same
>> amount of memory, because every cons cell  you gain ... is now in the
>> list of grey val as soon as your list does not
>> fit in the minor heap anymore !! So even writing you own mutable_list
>> type would be as bad !
>> Explanation: the list of grey val is a list of pointers from the major
>> heap to the minor heap which
>> are created when using mutable data structure and which would break
>> incremental GC if each minor GC did not scan
>> the list of grey val) ...
> This is not correct.
> When you're building a mutable list you're allocating first in the minor
> heap, then all cons go into the major heap at once, so only the "last"
> cons before a GC cycle is greyed. It is indeed true that for short
> lists, using the stack is better than using mutable structures.
> But using the stack is getting speed against correctness, since it will
> overflow for big lists.

I did timing for big lists with mutation using object and rev +  rev_map
and the later was faster ...

If the list is big, and there is allocating computation for the car of
each list in map, then I think a lot of cons cells can be greyed once
... even all if each computation in the car triggers at least one minor
collection ... but then the complexity of map does not matter ... so my
explanation for the observed timing was wrong ...

may be this is just the test to know if one have to grey the cons-cell
that's costly ?

any way I now think rev + rev_map is better than dirty Obj for that pb.

remark: I only tested on my athlon 32 ...

> Nicolas