OCaml efficiency/optimization?

OCaml efficiency/optimization?

[Tato Thetza]

I've been reading over
http://caml.inria.fr/pub/docs/manual-ocaml/index.html and have learned
two things:
-lists are immutable and singly linked, which explains why 1::[2;3] is
valid while [2,3]::1 is not, and why its efficient.
-the proper way to ensure tail-recursive optimization

question: are these and other optimizations documented somewhere
officially? I find it a little uncomfortable I've been learning OCaml
without knowning such internal details. Any secrets I should definitely
know if I were to use this language in production?

thanks, 
Tato Thetza

Re: OCaml efficiency/optimization?

[Tato Thetza]

sorry I meant 
Ocaml for Experienced Programmers: 
http://www.bogonomicon.com/bblog/book/html/book1.html

On Fri, 28 Oct 2005 03:21:43 -0700, "Tato Thetza" <thetza@sent.com>
said:
> I've been reading over
> http://caml.inria.fr/pub/docs/manual-ocaml/index.html and have learned
> two things:
> -lists are immutable and singly linked, which explains why 1::[2;3] is
> valid while [2,3]::1 is not, and why its efficient.
> -the proper way to ensure tail-recursive optimization
> 
> question: are these and other optimizations documented somewhere
> officially? I find it a little uncomfortable I've been learning OCaml
> without knowning such internal details. Any secrets I should definitely
> know if I were to use this language in production?
> 
> thanks, 
> Tato Thetza

Ant: [Caml-list] Re: OCaml efficiency/optimization?

[Martin Chabr]

The second reference you mentioned (Ocaml for
Experienced Programmers by Brian Hurt) is an excellent
and very detailed introduction to functional
programming in OCaml for C/C++/Java etc. programmers.
It explaines a lot on the subject of optimization
which I have not found elsewhere:
It makes clear how OCaml uses the built-in singly
linked lists, the role of data sharing in these and
what should be avoided for fast performance.

I think that this book contains more "secrets to be
used in production" than any other tutorial I know.

Another tutorial you might have a look at is the one
by Rich Jones of Merjis Co. at:

http://www.ocaml-tutorial.org/

It contains a chapter on performance and profiling at:

http://www.ocaml-tutorial.org/performance_and_profiling


Martin



--- Tato Thetza <thetza@sent.com> schrieb:

> sorry I meant 
> Ocaml for Experienced Programmers: 
>
http://www.bogonomicon.com/bblog/book/html/book1.html
> 
> On Fri, 28 Oct 2005 03:21:43 -0700, "Tato Thetza"
> <thetza@sent.com>
> said:
> > I've been reading over
> >
>
http://caml.inria.fr/pub/docs/manual-ocaml/index.html
> and have learned
> > two things:
> > -lists are immutable and singly linked, which
> explains why 1::[2;3] is
> > valid while [2,3]::1 is not, and why its
> efficient.
> > -the proper way to ensure tail-recursive
> optimization
> > 
> > question: are these and other optimizations
> documented somewhere
> > officially? I find it a little uncomfortable I've
> been learning OCaml
> > without knowning such internal details. Any
> secrets I should definitely
> > know if I were to use this language in production?
> > 
> > thanks, 
> > Tato Thetza
> 
> _______________________________________________
> 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
> 



	

	
		
___________________________________________________________ 
Gesendet von Yahoo! Mail - Jetzt mit 1GB Speicher kostenlos - Hier anmelden: http://mail.yahoo.de

Ocaml for Experienced Programmers

[Brian Hurt]

On Fri, 28 Oct 2005, Tato Thetza wrote:

> sorry I meant
> Ocaml for Experienced Programmers:
> http://www.bogonomicon.com/bblog/book/html/book1.html

This link wasn't really intended for public consumption, so it's been 
removed.  I forgot to put it in the robots.txt file, so it got out.  My 
apologies for the inconvience.

The good news is that the Pragmatic Programmers have expressed interest in 
publishing the book.  They have a "beta book" deal:
http://pragmaticprogrammer.com/starter_kit/faqs/beta_faq.html

I'll see how quickly I can get the book into the program.  I probably need 
to finish writting it first, however.  This is, however, my new job.

Thanks for the good feedback, however.

Brian

Re: [Caml-list] Ocaml for Experienced Programmers

[Yaron Minsky]

For what it's worth, I've looked at the book too, and found it to be
the best thing of its kind out there.  When it's released, we will
definitely buy a few copies.

Yaron

On 10/31/05, Brian Hurt <bhurt@spnz.org> wrote:
>
>
> On Fri, 28 Oct 2005, Tato Thetza wrote:
>
> > sorry I meant
> > Ocaml for Experienced Programmers:
> > http://www.bogonomicon.com/bblog/book/html/book1.html
>
> This link wasn't really intended for public consumption, so it's been
> removed.  I forgot to put it in the robots.txt file, so it got out.  My
> apologies for the inconvience.
>
> The good news is that the Pragmatic Programmers have expressed interest in
> publishing the book.  They have a "beta book" deal:
> http://pragmaticprogrammer.com/starter_kit/faqs/beta_faq.html
>
> I'll see how quickly I can get the book into the program.  I probably need
> to finish writting it first, however.  This is, however, my new job.
>
> Thanks for the good feedback, however.
>
> Brian
>
> _______________________________________________
> 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
>

Re: [Caml-list] Re: OCaml efficiency/optimization?

[Brian Hurt]

On Fri, 28 Oct 2005, Tato Thetza wrote:

> sorry I meant
> Ocaml for Experienced Programmers:
> http://www.bogonomicon.com/bblog/book/html/book1.html
>
> On Fri, 28 Oct 2005 03:21:43 -0700, "Tato Thetza" <thetza@sent.com>
> said:
>> I've been reading over
>> http://caml.inria.fr/pub/docs/manual-ocaml/index.html and have learned
>> two things:
>> -lists are immutable and singly linked, which explains why 1::[2;3] is
>> valid while [2,3]::1 is not, and why its efficient.
>> -the proper way to ensure tail-recursive optimization
>>
>> question: are these and other optimizations documented somewhere
>> officially? I find it a little uncomfortable I've been learning OCaml
>> without knowning such internal details. Any secrets I should definitely
>> know if I were to use this language in production?

Answering the original question (somewhat belatedly), I present Brian's 
steps to optimizing code:

1) Get it to work.  I don't care how fast your program returns the wrong 
answer, get it returning the right answer in all cases before doing 
anything else.  This also includes making the code maintainable- if you 
can't figure out how the code works, you won't be able to figure out how 
to make the code work faster.  And in general, optimizers work better on 
clean, maintainable code- generally maintainable code is also faster code.

2) Measure.  Is the code fast enough?  If so, you can stop now.

3) Optimize.  This includes compiling to native, and using ocamldefun, 
the Ocaml Defunctorizor.  This is stuff that is "easy" to do 
(comparatively), and can have dramatic effects on performance.

4) Buy a faster computer.  No, really- what's the programmer time worth? 
>From here on out it'll start being really easy to rack of tens, if not 
hundreds, of thousands of dollars of programmer time improving the code. 
At which point simply buying a faster machine might be signifigantly 
cheaper.  This isn't always the case, but generally it is- you definately 
shouldn't assume it isn't the case.

5) Profile.  If the code isn't fast enough, what's taking the time? 
Making a program 10x faster can be completely worthless- if the program 
takes 100ms to fire off a database query that takes 15 minutes to 
complete, making that program only take 10ms to fire off the same database 
query isn't going to help.  Also, optimizing initilization loops is 
generally not usefull.  Where is the time going?

6) Look for large-scale optimizations.  Are you doing things you don't 
need to do?  No operation completes faster than the operation you don't 
do.  What is the big-O notation of your core algorithms?  Replacing an 
O(n^2) algorithm with an O(n log n) algorithm can yield huge performance 
gains (10,000x or more).  This is where maintainable code comes in real 
handy.  This is also the point where I consider adding imperitive code to 
my program, replacing O(log N) tree lookups with O(1) array lookups.  Note 
that this is an *optimization*- applicative datastructures are more 
maintainable (IMHO), and thus should be the default approach taken until 
it is proven that performance requirements demand imperitive data 
structures.  But I'd definately go through Okasaki's book before making 
that decision.

One comment here: implicit in this step is you being conversant with the 
current literature- which generally means doing new searches on a regular 
basis.  You might think "Hey, I've been using red-black trees for decades, 
and it's not like they're exactly new technology.  Why do a literature 
search on them?"  But you'd miss this paper, which was only published six 
years ago:
http://citeseer.ist.psu.edu/hinze99constructing.html

7) Measure again.  Actually, I take that back- you should be measuring 
constantly (to show that you are, in fact, making things go faster), and 
profiling regularly, from here on out.

8) Now you're into the tweak stage.  Generally (not always, but 
generally), using recursive functions and arguments, if it's less than 
five arguments, will be faster than loops and references (the arguments 
will just live in registers, while the reference assignments have to get 
written out to memory).  Replace tuples of all floats with structures of 
all floats, and unbox the floats.

9) If it still isn't fast enough, rewrite core routines in C, or even 
assembly language.  But these are Hail Mary passes of optimization- if 
they aren't enough, you're screwed.

Brian

Re: [Caml-list] Re: OCaml efficiency/optimization?

[Matt Gushee]

Brian Hurt wrote:

> 3) Optimize.  This includes compiling to native, and using ocamldefun,
> the Ocaml Defunctorizor.

What's the status of ocamldefun? I tried to install it a few months ago,
but the version I downloaded wouldn't compile with Ocaml 3.08, and it
didn't appear that the package was being actively maintained.

> 4) Buy a faster computer.  No, really- what's the programmer time worth?

But if you're developing desktop software, please, please, at least
regularly test the product on machines comparable to what your users use.

--
Matt Gushee
Englewood, CO, USA

Re: [Caml-list] OCaml efficiency/optimization?

[Jon Harrop]

On Friday 28 October 2005 11:21, Tato Thetza wrote:
> I've been reading over
> http://caml.inria.fr/pub/docs/manual-ocaml/index.html and have learned
> two things:
> -lists are immutable and singly linked, which explains why 1::[2;3] is
> valid while [2,3]::1 is not, and why its efficient.
> -the proper way to ensure tail-recursive optimization
>
> question: are these and other optimizations documented somewhere
> officially?

I don't know if it classifies as "official", but my OCaml book has a chapter 
on optimisation that covers tail recursion.

> I find it a little uncomfortable I've been learning OCaml 
> without knowning such internal details. Any secrets I should definitely
> know if I were to use this language in production?

We write high-performance OCaml programs for various different applications, 
including scientific computing and graphics. IMHO, OCaml is just like any 
other language with regard to optimisation. One important difference is that 
the OCaml community are very friendly and helpful, which makes it much easier 
to get accurate information when you need it.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Re: [Caml-list] OCaml efficiency/optimization?

[Jon Harrop]

On Friday 28 October 2005 13:15, Jon Harrop wrote:
> I don't know if it classifies as "official", but my OCaml book has a
> chapter on optimisation that covers tail recursion.

There are also a couple of official pages on INRIA's site that I forgot about:

  http://pauillac.inria.fr/ocaml/speed.html
  http://pauillac.inria.fr/ocaml/numerical.html

and the books:

  "Introduction to algorithms" by Cormen et al. for general information.
  "Purely functional data structures" by Chris Okasaki for MLized data 
structures.

The latter is also freely available as a PhD thesis.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Re: [Caml-list] OCaml efficiency/optimization?

[Thomas Fischbacher]

On Fri, 28 Oct 2005, Tato Thetza wrote:

> I've been reading over
> http://caml.inria.fr/pub/docs/manual-ocaml/index.html and have learned
> two things:
> -lists are immutable and singly linked, which explains why 1::[2;3] is
> valid while [2,3]::1 is not, and why its efficient.
> -the proper way to ensure tail-recursive optimization
> 
> question: are these and other optimizations documented somewhere
> officially? I find it a little uncomfortable I've been learning OCaml
> without knowning such internal details. Any secrets I should definitely
> know if I were to use this language in production?

These are not really "OCaml internal details or optimizations", but rather 
ideas and techniques which have been around very long, and are relevant 
in virtually any (non-lazy) functional language.

I think you might benefit from reading the one book most often used in 
courses on the subject: Abelson & Sussman's "Structure and Interpretation 
of Computer Programs". The complete text is available online at

http://mitpress.mit.edu/sicp/

-- 
regards,               tf@cip.physik.uni-muenchen.de              (o_
 Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
(lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)           V_/_
(if (= x 0) y (g g (- x 1) (* x y)))) n 1))                  (Debian GNU)