[Caml-list] Where does Ocaml spend all the time?

[Caml-list] Where does Ocaml spend all the time?

[Florian Hars]

I have written an ocaml program, which is about an order of magnitude
slower than a similar C program, and now I am wondering what to do.
According to gprof, I have neiter written nor called most of the
top-scoring functions in my program:

  %   cumulative   self              self     total           
 time   seconds   seconds    calls  ms/call  ms/call  name    
  9.82      2.76     2.76  9822122     0.00     0.00  Verzeichnis_code_end
  9.00      5.29     2.53     3275     0.77     0.77  mark_slice
  8.15      7.58     2.29    17860     0.13     0.54  Stra$dfen_e_i_l_rec_129
  8.04      9.84     2.26 23232718     0.00     0.00  string_equal
  7.44     11.93     2.09     4088     0.51     0.62  sweep_slice
  5.73     13.54     1.61   390646     0.00     0.01  oldify
  4.16     14.71     1.17 22241546     0.00     0.00  Eintrag_code_begin
  3.88     15.80     1.09                             Stringhilfsfunktionen_code_begin

Only the third and fourth entry seem to do anything "useful", the rest
looks like administrative overhead to me. What are these functions
doing?
Are there any general hints on how to write ocaml programs for efficiency?
Like, don't use functional updates for records to reduce garbage?

Yours, Florian.
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Where does Ocaml spend all the time?

[Sven LUTHER]

On Thu, Jun 28, 2001 at 10:16:35AM +0200, Florian Hars wrote:
> I have written an ocaml program, which is about an order of magnitude
> slower than a similar C program, and now I am wondering what to do.
> According to gprof, I have neiter written nor called most of the
> top-scoring functions in my program:
> 
>   %   cumulative   self              self     total           
>  time   seconds   seconds    calls  ms/call  ms/call  name    
>   9.82      2.76     2.76  9822122     0.00     0.00  Verzeichnis_code_end
>   9.00      5.29     2.53     3275     0.77     0.77  mark_slice
>   8.15      7.58     2.29    17860     0.13     0.54  Stra$dfen_e_i_l_rec_129
>   8.04      9.84     2.26 23232718     0.00     0.00  string_equal
>   7.44     11.93     2.09     4088     0.51     0.62  sweep_slice
>   5.73     13.54     1.61   390646     0.00     0.01  oldify
>   4.16     14.71     1.17 22241546     0.00     0.00  Eintrag_code_begin
>   3.88     15.80     1.09                             Stringhilfsfunktionen_code_begin
> 
> Only the third and fourth entry seem to do anything "useful", the rest
> looks like administrative overhead to me. What are these functions
> doing?
> Are there any general hints on how to write ocaml programs for efficiency?
> Like, don't use functional updates for records to reduce garbage?

mmm, i am no expert, but the mark_slice and sweep_slice seems like
garbage_collector stuff.

I think there is a faq entry about efficiency and other such things, in
particular you have to know, please someone correct me if i am wrong, that the
updating of a reference or a mutable field can trigger a garbage collection.

Also ocaml is highly optimized for functional datatypes and curryified
function calls. 

Maybe this helps.

Friendly,

Sven Luther
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Where does Ocaml spend all the time?

[Xavier Leroy]

> I have written an ocaml program, which is about an order of magnitude
> slower than a similar C program, and now I am wondering what to do.
> According to gprof, I have neiter written nor called most of the
> top-scoring functions in my program:
> Only the third and fourth entry seem to do anything "useful", the rest
> looks like administrative overhead to me. What are these functions
> doing?

mark_slice and sweep_slice are the major garbage collector.
oldify is the minor garbage collector.
string_equal is the string comparison operator (i.e. Caml's = operator
at type string->string->bool).

> Are there any general hints on how to write ocaml programs for efficiency?
> Like, don't use functional updates for records to reduce garbage?

That might be a possibility, depending on the size of the records.
However, heap allocation of short-lived data structures is quite cheap,
while some forms of in-place updates can be quite expensive
(in particular, storing a pointer to a young object in an old object).
So, the answer is not clear-cut.

At any rate, the GC-related functions account for only 25% of the
running time (which is typical for symbolic processing, but a bit high
for numerical processing), so the "order of magnitude" slowdown that
you mention corresponds to other factors than just GC overhead.
My experience is that carefully written Caml code always deliver at
least 50% of the performance of equivalent, carefully written C code.

It is true, however, that tuning Caml code for performance is not
obvious without a good knowledge of the compiler internals.  However,
the "making code run fast" section of the OCaml Questions and Answers
might help:
        http://caml.inria.fr/ocaml/QandA.html

- Xavier Leroy
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Where does Ocaml spend all the time?

[Florian Hars]

On Thu, Jun 28, 2001 at 10:37:24AM +0200, Xavier Leroy wrote:
> string_equal is the string comparison operator (i.e. Caml's = operator
> at type string->string->bool).

Yes, that is one of the functions that I expected to take a lot of time,
since the program does a lot of string comparision and matching.
I was more surprised by the time spent in the <Modulename>_code_(begin|end)
functions, what are these? Why are they called and by whom?
 
> At any rate, the GC-related functions account for only 25% of the
> running time (which is typical for symbolic processing, but a bit high
> for numerical processing)

So this is OK (except that it is 25% of quite a lot of time :-)

> so the "order of magnitude" slowdown that
> you mention corresponds to other factors than just GC overhead

Once the functionality is complete, I'll work on some details of the
algorithms.

> My experience is that carefully written Caml code always deliver at
> least 50% of the performance of equivalent, carefully written C code.

Yes, that was my expectation, too, after reading some comparisions.
I'll try to see if the recomendations from the QandA help.
CAMLRUNPARAM='o=100' alone gives another two to three seconds,
this is a good start.


Yours, Florian Hars.
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Where does Ocaml spend all the time?

[Xavier Leroy]

> Yes, that is one of the functions that I expected to take a lot of time,
> since the program does a lot of string comparision and matching.
> I was more surprised by the time spent in the <Modulename>_code_(begin|end)
> functions, what are these? Why are they called and by whom?

It's an artefact of gprof.  For each module, ocamlopt generates two
code symbols <Modulename>_code_begin and <Modulename>_code_end
that bracket the code for this module.  (These symbols are used to
determine the address range for the compiled code during marshaling.)
So, if you have two modules A and B and the first function in B is f,
you'd get something like:

        A_code_begin:
          ...
        A_code_end:
        B_code_begin:
        B_f:
          ... code for B.f ..
        ...
        B_code_end

and gprof now has three names to refer to the entry point of B.f:
B_f, A_code_end and B_code_begin, hence a 2 in 3 chance that it will
pick the wrong name :-)  

This could be fixed by inserting "nops" around the _code_begin and
_code_end symbols, at least when compiling in profiling mode.

> > At any rate, the GC-related functions account for only 25% of the
> > running time (which is typical for symbolic processing, but a bit high
> > for numerical processing)
> 
> So this is OK (except that it is 25% of quite a lot of time :-)

It's for programs that allocate a lot.  A C or C++ program with the
same allocation behavior would typically spend 50 to 90% of its time
in malloc() and free()  :-)

- Xavier Leroy
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Where does Ocaml spend all the time?

[Chris Hecker]

>It's for programs that allocate a lot.  A C or C++ program with the
>same allocation behavior would typically spend 50 to 90% of its time
>in malloc() and free()  :-)

Except you can actually control when C allocates memory, as opposed to OCaml.  ;)

Just stopping by this thread to cause trouble,
Chris

-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Where does Ocaml spend all the time?

[Daniel de Rauglaudre]

Hi,

On Thu, Jun 28, 2001 at 10:16:35AM +0200, Florian Hars wrote:

> I have written an ocaml program, which is about an order of magnitude
> slower than a similar C program, and now I am wondering what to do.

Of course you compiled by ocamlopt, not ocamlc...?

-- 
Daniel de RAUGLAUDRE
daniel.de_rauglaudre@inria.fr
http://cristal.inria.fr/~ddr/
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Where does Ocaml spend all the time?

[Florian Hars]

On Thu, Jun 28, 2001 at 10:39:53AM +0200, Daniel de Rauglaudre wrote:
> Of course you compiled by ocamlopt, not ocamlc...?

Yes, and even -unsafe (which gives an performace increase of about 10 %).
-inline 0 and -inline 1 don't make a difference (the first might be 
marginally faster), -inline 2 undoes the effect of -unsafe (multilevel
cache architectures seem to be a funny thing...). So the problems seem
to be somewhere else.

Yours, Florian.
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Where does Ocaml spend all the time?

[Remi VANICAT]

Florian Hars <florian@hars.de> writes:

> I have written an ocaml program, which is about an order of magnitude
> slower than a similar C program, and now I am wondering what to do.
> According to gprof, I have neiter written nor called most of the
> top-scoring functions in my program:
> 
>   %   cumulative   self              self     total           
>  time   seconds   seconds    calls  ms/call  ms/call  name    
>   9.82      2.76     2.76  9822122     0.00     0.00  Verzeichnis_code_end
>   9.00      5.29     2.53     3275     0.77     0.77  mark_slice
>   8.15      7.58     2.29    17860     0.13     0.54  Stra$dfen_e_i_l_rec_129
>   8.04      9.84     2.26 23232718     0.00     0.00  string_equal
>   7.44     11.93     2.09     4088     0.51     0.62  sweep_slice
>   5.73     13.54     1.61   390646     0.00     0.01  oldify
>   4.16     14.71     1.17 22241546     0.00     0.00  Eintrag_code_begin
>   3.88     15.80     1.09                             Stringhilfsfunktionen_code_begin
> 
> Only the third and fourth entry seem to do anything "useful", the rest
> looks like administrative overhead to me. What are these functions
> doing?

only the third and fourth ? 

the Verzeichnis_code_end seem to be part of your program (Verzeichnis?
it is not English) The same for Eintrag_code_begin and
Stringhilfsfunktionen_code_begin. It left mark_slice, sweep_slice and
oldify, that are all part of the GC. As i don't know your code, it's
difficult to bettered it, but you should concentrate over the Eintrag
and Stringhilfsfunktionen functions.

by the way, have you read the ocaml FAQ on efficiency?
http://caml.inria.fr/FAQ/FAQ_EXPERT-eng.html#efficacite

-- 
Rémi Vanicat
vanicat@labri.u-bordeaux.fr
http://dept-info.labri.u-bordeaux.fr/~vanicat
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr