Tuple allocation overhead

Tuple allocation overhead

[Raj Bandyopadhyay]

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:

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).

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 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

Re: [Caml-list] Tuple allocation overhead

[Gerd Stolpmann]

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
------------------------------------------------------------

Re: [Caml-list] Tuple allocation overhead

[Matthew William Cox]

[-- Attachment #1: Type: text/plain, Size: 1052 bytes --]

On Tue, Aug 12, 2008 at 11:08:58AM -0500, Raj Bandyopadhyay wrote:
> 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.

I doubt it's anything to do with malloc. The ocaml runtime does its own
memory management, which includes allocation of caml objects and garbage
collection. Storage is obtained from the system en masse.

> 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?

I can't explain this. Have you tried both 32 and 64 bit archs, or at
least CPUs with different cache characteristics?

There might be architecture dependent parameters in the GC. IIRC,
allocation in ocaml is increment and test of a pointer. If the pointer
extends beyond the heap, it's necessary to perform a GC.

Your code also allocates a list cell at each step. Maybe the combination
of list cell and tuple cell is triggering cache misses differently?

Matt

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 197 bytes --]