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