Raj Bandyopadhyay said:
> Hi folks
>
> I was performing a little experiment to try and quantify some of the
> overhead of memory allocation in OCaml. Here is a the kind of little
> program that I am using for timings:

This experiment does not make much sense. Ocaml has its own memory
management for the memory it got from the OS in large blocks using malloc
(or mmap in some cases). Generally, memory allocation is very fast and
often only an integer addition, but checking which memory parts are still
reachable, and cleaning up unneeded memory takes time. You should better
look at the cost of memory management as a whole, and not to allocation
only.

> let rec alloc3 n l =
>     if n = 0 then l
>     else alloc3 (n-1) ((1,2,n)::l)
>
> The alloc3 function allocates a tuple of size 3 at every call (n is
> initially 100,000).

No. It allocates alwyas a pair (for the list cell), and for t=1 nothing
else, and for t>1 another t-tuple (where t is the tuple size).

> I have similar functions alloc1 through alloc10, to allocate tuples of
> size 1 (just an integer) through 10.
> Here are my timing results (each time is the average of 100 runs):
>
>  __Tuple sz 1 ________________ 100x avg= 1.964404E+01 msec
> __ Tuple sz 2 ________________ 100x avg= 4.699384E+01 msec
> __ Tuple sz 3 ________________ 100x avg= 4.232895E+01 msec
> __ Tuple sz 4 ________________ 100x avg= 4.265683E+01 msec
> __ Tuple sz 5 ________________ 100x avg= 4.442121E+01 msec
> __ Tuple sz 6 ________________ 100x avg= 4.723042E+01 msec
> __ Tuple sz 7 ________________ 100x avg= 5.168987E+01 msec
> __ Tuple sz 8 ________________ 100x avg= 5.234274E+01 msec
> __ Tuple sz 9 ________________ 100x avg= 5.504287E+01 msec
> __ Tuple sz 10 _______________ 100x avg= 5.836166E+01 msec
>
> As expected, the larger the size of the tuple, the longer it takes.
> However, there is a spike for tuple size 2. I am seeing this on multiple
> platforms (linux and mac).

I cannot fully explain this, but you should consider:

For t=2 you allocate 200000 pairs. The minor heap has space for 32k words,
and you need 600000 words for the pairs. After every 32k the allocated
pairs are moved to the major heap (the so-called minor collection). Most
of the runtime of your program is probably required for this (but I havent
checked).

If you look at this for various t:

- t=1: 300000 words needed, 9 minor collections

- t=2: 600000 words needed, 18 minor collections

- t=3: 700000 words needed, 21 minor collections

etc.

That at least roughly explains the doubled runtime for t=2 vs. t=1. There
might be another effect in the memory manager that explains the peak, but
it is not obvious.

Gerd



>
> I was wondering if someone has a good explanation for this. I assume it
> has to do with some overhead of malloc, but I'm not sure. Why is it that
> a tuple of size 2 is more expensive to allocate than size 3-5 in this
> case? Are there other factors involved that I am not considering?
>
> Thanks
> Raj
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
>


------------------------------------------------------------
Gerd Stolpmann * Viktoriastr. 45 * 64293 Darmstadt * Germany
gerd@gerd-stolpmann.de          http://www.gerd-stolpmann.de
------------------------------------------------------------