"ocaml_beginners"::[] caml_fl_allocate

Hello

i've written a program that readsthe input and builds a large in
memory data strucutre using hashtable and lists. I think the
algorithm is O(n).

But if I double the size of the input the running time is much higher
as double.

Here are the outputs of gprof

Case I.

Flat profile:

Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
43.52 65.79 65.79 12354305 0.00 0.00 caml_fl_allocate
17.22 91.82 26.03 3290 0.01 0.01 mark_slice
3.72 97.44 5.62 1889519 0.00 0.00
camlMfhash__update_165
2.94 101.88 4.44 2115 0.00 0.00 sweep_slice
2.73 106.00 4.12 4933491 0.00 0.00
camlBlockList__add_84

Case II.

Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
61.26 263.62 263.62 23307171 0.00 0.00 caml_fl_allocate
12.27 316.44 52.82 6396 0.01 0.01 mark_slice
2.63 327.77 11.33 3785967 0.00 0.00
camlMfhash__update_165
1.94 336.10 8.33 9804156 0.00 0.00
camlBlockList__add_84
1.71 343.45 7.35 4199 0.00 0.00 sweep_slice

You can see that Mfhash.update and BlockList.add are called twice as
much in Case II than in Case I and the running time is linear.

But caml_fl_allocate that I think is related to memory allocation
slows down my program. What is this function for? Can I set the
initial heap size or something else?

peter

Messages in this topic (1) Reply (via web post) | Start a new topic

.

On Wed, Sep 27, 2006 at 12:15:20PM +0200, Peter Halacsy wrote:
> i've written a program that readsthe input and builds a large in
> memory data strucutre using hashtable and lists. I think the
> algorithm is O(n).
>;
> But if I double the size of the input the running time is much higher
> as double.
[...]

I would suggest narrowing this down to a simple test case and posting
the full code to caml-list ~at~ inria dot fr. Without actual code it
is impossible to see what might be going on.

>; But caml_fl_allocate that I think is related to memory allocation
> slows down my program. What is this function for? Can I set the
> initial heap size or something else?

caml_fl_allocate is the function which tries to allocate memory from
the "free list" (an internal list of blocks which have just been
freed). If it fails, then the heap is expanded. As such, all
allocation functions eventually turn into a call to caml_fl_allocate.

You can set the initial (major) heap site by using the 'h' option in
OCAMLRUNPARAM. See:
http://caml.inria.fr/pub/docs/manual-ocaml/manual024.html

Rich.

--
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Internet Marketing and AdWords courses - http://merjis.com/courses - NEW!
Merjis blog - http://blog.merjis.com - NEW!

Messages in this topic (2) Reply (via web post) | Start a new topic

.