Question about optimization

Question about optimization

[Michał C]

Hi!

I'm working on a physical based ray(path) tracer and the performance  
is one of my top priorities (just after the image quality).
So I have a question about optimization: can You share some tips or  
maybe optimizing strategies to improve the speed of programs?

here is my code: http://neos1.ovh.org/ray3.ml,

and here is how I compile it:
ocamlopt -inline 100 -unsafe -ffast-math str.cmxa -I +lablgl  
lablgl.cmxa lablglut.cmxa -o ray ray.ml

Maybe You can take a look, sure I don't expect You to look through it  
in some hardcore way, but You know, maybe there are some obvious  
mistakes or unnecessary boxing which will spot your eye.

Thanks in advance,
oh and if you possibly want to see the development or how the program  
works - http://neos1.wordpress.com

Regards

Re: [Caml-list] Question about optimization

[Peng Zang]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

I have often found -inline 10 to be faster than -inline 100.  But YMMV,

Peng

On Saturday 01 November 2008 10:52:49 pm Michał C wrote:
> Hi!
>
> I'm working on a physical based ray(path) tracer and the performance
> is one of my top priorities (just after the image quality).
> So I have a question about optimization: can You share some tips or
> maybe optimizing strategies to improve the speed of programs?
>
> here is my code: http://neos1.ovh.org/ray3.ml,
>
> and here is how I compile it:
> ocamlopt -inline 100 -unsafe -ffast-math str.cmxa -I +lablgl
> lablgl.cmxa lablglut.cmxa -o ray ray.ml
>
> Maybe You can take a look, sure I don't expect You to look through it
> in some hardcore way, but You know, maybe there are some obvious
> mistakes or unnecessary boxing which will spot your eye.
>
> Thanks in advance,
> oh and if you possibly want to see the development or how the program
> works - http://neos1.wordpress.com
>
> Regards
>
> _______________________________________________
> 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
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.7 (GNU/Linux)

iD8DBQFJDZu5fIRcEFL/JewRAikYAJ4qaO/HbPoVVP9xl3bCoYc0A17vlwCfbFyJ
tkVitQkbANKQYhDxM2lfNQc=
=2ycS
-----END PGP SIGNATURE-----

Re: [Caml-list] Question about optimization

[Jon Harrop]

On Sunday 02 November 2008 02:52:49 Michał C wrote:
> Hi!
>
> I'm working on a physical based ray(path) tracer and the performance
> is one of my top priorities (just after the image quality).
> So I have a question about optimization: can You share some tips or
> maybe optimizing strategies to improve the speed of programs?
>
> here is my code: http://neos1.ovh.org/ray3.ml,
>
> and here is how I compile it:
> ocamlopt -inline 100 -unsafe -ffast-math str.cmxa -I +lablgl
> lablgl.cmxa lablglut.cmxa -o ray ray.ml

Looks good but get rid of -unsafe and use records to represent vectors instead 
of arrays and compile in 64-bit and get rid of -ffast-math.

I don't know if it affects performance but get rid of conditions returning 
bool constants:

  if hc2 < 0. then false else true

Should be:

  hc2 >= 0.

> Maybe You can take a look, sure I don't expect You to look through it
> in some hardcore way, but You know, maybe there are some obvious
> mistakes or unnecessary boxing which will spot your eye.
>
> Thanks in advance,
> oh and if you possibly want to see the development or how the program
> works - http://neos1.wordpress.com

May I have an example scene description file that I can use for profiling? 
Without it, I have no way to direct my effort...

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

Re: [Caml-list] Question about optimization

[Jon Harrop]

On Sunday 02 November 2008 02:52:49 Michał C wrote:
> Hi!
>
> I'm working on a physical based ray(path) tracer and the performance
> is one of my top priorities (just after the image quality).
> So I have a question about optimization: can You share some tips or
> maybe optimizing strategies to improve the speed of programs?
>
> here is my code: http://neos1.ovh.org/ray3.ml,

Now that I can profile it, the single biggest problem is obviously that seven 
of my cores are idle!

You have manually un-nested pattern matches which is not necessary. For 
example, this:

	| Leaf (prim, mat) ->
		match prim with
			| Triangle (tri) -> ray_triangle ro rd tri
			| Sphere (sph) -> ray_sphere ro rd sph

May be written:

  | Leaf (Triangle tri, mat) -> ray_triangle ro rd tri
  | Leaf (Sphere sph, mat) -> ray_sphere ro rd sph

The only obvious optimizations I can see are to use a faster random number 
generator and to inline the vector arithmetic by hand.

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

Re: [Caml-list] Question about Optimization

[Gregory Malecha]

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

Hi, Ben --

Thanks this is really helpful.

On Thu, Apr 21, 2016, 9:35 AM Ben Millwood <bmillwood@janestreet.com> wrote:

> You can see hints at the problems with rewrite rules by reading about the
> mechanisms GHC has to work around them:
>
>
> https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/pragmas.html#inline-pragma
>
> For example, rules can be prevented from matching if some subexpression is
> inlined first, but on the flipside, some rules need some inlining to occur
> before they can match. This leads GHC to support "phase specifications"
> that help you to control the order of inlinings and rules.
>
> On 21 April 2016 at 12:05, Daniel Bünzli <daniel.buenzli@erratique.ch>
> wrote:
>
>> Le jeudi, 21 avril 2016 à 18:02, Gabriel Scherer a écrit :
>> > useful in some situations but also very fragile.
>>
>> What kind of fragility ?
>>
>> Daniel
>>
> --
>> Caml-list mailing list.  Subscription management and archives:
>> https://sympa.inria.fr/sympa/arc/caml-list
>> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
>> Bug reports: http://caml.inria.fr/bin/caml-bugs
>>
>

[-- Attachment #2: Type: text/html, Size: 2551 bytes --]

Re: [Caml-list] Question about Optimization

[Ben Millwood]

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

You can see hints at the problems with rewrite rules by reading about the
mechanisms GHC has to work around them:

https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/pragmas.html#inline-pragma

For example, rules can be prevented from matching if some subexpression is
inlined first, but on the flipside, some rules need some inlining to occur
before they can match. This leads GHC to support "phase specifications"
that help you to control the order of inlinings and rules.

On 21 April 2016 at 12:05, Daniel Bünzli <daniel.buenzli@erratique.ch>
wrote:

> Le jeudi, 21 avril 2016 à 18:02, Gabriel Scherer a écrit :
> > useful in some situations but also very fragile.
>
> What kind of fragility ?
>
> Daniel
>
>
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

[-- Attachment #2: Type: text/html, Size: 1871 bytes --]

Re: [Caml-list] Question about Optimization

[Daniel Bünzli]

Le jeudi, 21 avril 2016 à 18:02, Gabriel Scherer a écrit :
> useful in some situations but also very fragile.

What kind of fragility ?  

Daniel

Re: [Caml-list] Question about Optimization

[Gabriel Scherer]

Another approach that might be worth trying (sorry for not thinking
about it earlier) is MetaOCaml. I tend of think of it as a tool to
explicitly specify and control partial evaluation strategies.

Jeremy Yallop teaches MetaOCaml and some optimization tricks using it.
See this excellent IOCaml notebook showing how to optimize a sequence
of operations on a simple stack machine using MetaOCaml, which is not
far from the discussed application.

  http://ocamllabs.github.io/iocamljs/staging2.html

(I don't have an opinion on effectiveness of user-defined rewriting
for OCaml code, I guess one should try to see how it goes. My
take-away from the usage in the Haskell community is that it's very
useful in some situations but also very fragile.)

On Thu, Apr 21, 2016 at 11:45 AM, Gregory Malecha <gmalecha@gmail.com> wrote:
> Thanks for the feedback. It sounds like there are reasonable ways to do this
> if you write your programs in such a way that everything can be done via
> inlining. While I agree that this works in many cases, it doesn't seem
> powerful enough to solve everything. For example, equations that are only
> provable by induction are not optimizable by this strategy (without some
> pretty fancy tricks).
>
> Do you believe that having a rewriting facility is unnecessary?
> Undersireable (it makes the compiler too complex, too slow, too
> unpredictable)? Or do you think that it would be useful, but no one has done
> anything on it?
>
> Thanks.
>
>
> On Thu, Apr 21, 2016, 4:45 AM Yaron Minsky <yminsky@janestreet.com> wrote:
>>
>> Also, Core_kernel's Sequence type fills a similar purpose.  And Flambda
>> does a good job of optimizing the iteration in Sequence, from what I've
>> overheard about our experiments.
>>
>> On Thu, Apr 21, 2016 at 5:32 AM, Jonas Jensen <jj@issuu.com> wrote:
>>>
>>> On 21 April 2016 at 09:13, Gregory Malecha <gmalecha@gmail.com> wrote:
>>> >
>>> > I'm wondering if there is any work (and interest) on supporting
>>> > user-defined optimizations similar to GHC's rewrite rules in the Ocaml
>>> > compiler. For example, a standard example would be specifying map fusion:
>>> >
>>> > map f (map g ls) = map (fun x -> f (g x)) ls
>>>
>>> A "boring" and practical answer is that you get this optimization by
>>> writing your long chain of map, filter, bind, etc. using Batteries'
>>> Enum
>>> (http://ocaml-batteries-team.github.io/batteries-included/hdoc2/BatEnum.html)
>>> or the stand-alone Gen package
>>> (http://cedeela.fr/~simon/software/gen/Gen.S.html). It looks
>>> superficially like list map, but the order of execution will be like
>>> after a fusion, which should improve cache locality and avoid
>>> allocations of intermediate lists.
>>>
>>> Cheers,
>>> Jonas
>>>
>>>
>>> --
>>> Caml-list mailing list.  Subscription management and archives:
>>> https://sympa.inria.fr/sympa/arc/caml-list
>>> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
>>> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
> --
>
> - gregory malecha
>   gmalecha.github.io

Re: [Caml-list] Question about Optimization

[Gregory Malecha]

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

Thanks for the feedback. It sounds like there are reasonable ways to do
this if you write your programs in such a way that everything can be done
via inlining. While I agree that this works in many cases, it doesn't seem
powerful enough to solve everything. For example, equations that are only
provable by induction are not optimizable by this strategy (without some
pretty fancy tricks).

Do you believe that having a rewriting facility is unnecessary?
Undersireable (it makes the compiler too complex, too slow, too
unpredictable)? Or do you think that it would be useful, but no one has
done anything on it?

Thanks.

On Thu, Apr 21, 2016, 4:45 AM Yaron Minsky <yminsky@janestreet.com> wrote:

> Also, Core_kernel's Sequence type fills a similar purpose.  And Flambda
> does a good job of optimizing the iteration in Sequence, from what I've
> overheard about our experiments.
>
> On Thu, Apr 21, 2016 at 5:32 AM, Jonas Jensen <jj@issuu.com> wrote:
>
>> On 21 April 2016 at 09:13, Gregory Malecha <gmalecha@gmail.com> wrote:
>> >
>> > I'm wondering if there is any work (and interest) on supporting
>> user-defined optimizations similar to GHC's rewrite rules in the Ocaml
>> compiler. For example, a standard example would be specifying map fusion:
>> >
>> > map f (map g ls) = map (fun x -> f (g x)) ls
>>
>> A "boring" and practical answer is that you get this optimization by
>> writing your long chain of map, filter, bind, etc. using Batteries'
>> Enum (
>> http://ocaml-batteries-team.github.io/batteries-included/hdoc2/BatEnum.html
>> )
>> or the stand-alone Gen package
>> (http://cedeela.fr/~simon/software/gen/Gen.S.html). It looks
>> superficially like list map, but the order of execution will be like
>> after a fusion, which should improve cache locality and avoid
>> allocations of intermediate lists.
>>
>> Cheers,
>> Jonas
>>
>
>> --
>> Caml-list mailing list.  Subscription management and archives:
>> https://sympa.inria.fr/sympa/arc/caml-list
>> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
>> Bug reports: http://caml.inria.fr/bin/caml-bugs
>>
> --

- gregory malecha
  gmalecha.github.io

[-- Attachment #2: Type: text/html, Size: 3751 bytes --]

Re: [Caml-list] Question about Optimization

[Yaron Minsky]

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

Also, Core_kernel's Sequence type fills a similar purpose.  And Flambda
does a good job of optimizing the iteration in Sequence, from what I've
overheard about our experiments.

On Thu, Apr 21, 2016 at 5:32 AM, Jonas Jensen <jj@issuu.com> wrote:

> On 21 April 2016 at 09:13, Gregory Malecha <gmalecha@gmail.com> wrote:
> >
> > I'm wondering if there is any work (and interest) on supporting
> user-defined optimizations similar to GHC's rewrite rules in the Ocaml
> compiler. For example, a standard example would be specifying map fusion:
> >
> > map f (map g ls) = map (fun x -> f (g x)) ls
>
> A "boring" and practical answer is that you get this optimization by
> writing your long chain of map, filter, bind, etc. using Batteries'
> Enum (
> http://ocaml-batteries-team.github.io/batteries-included/hdoc2/BatEnum.html
> )
> or the stand-alone Gen package
> (http://cedeela.fr/~simon/software/gen/Gen.S.html). It looks
> superficially like list map, but the order of execution will be like
> after a fusion, which should improve cache locality and avoid
> allocations of intermediate lists.
>
> Cheers,
> Jonas
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

[-- Attachment #2: Type: text/html, Size: 2357 bytes --]

Re: [Caml-list] Question about Optimization

[Jonas Jensen]

On 21 April 2016 at 09:13, Gregory Malecha <gmalecha@gmail.com> wrote:
>
> I'm wondering if there is any work (and interest) on supporting user-defined optimizations similar to GHC's rewrite rules in the Ocaml compiler. For example, a standard example would be specifying map fusion:
>
> map f (map g ls) = map (fun x -> f (g x)) ls

A "boring" and practical answer is that you get this optimization by
writing your long chain of map, filter, bind, etc. using Batteries'
Enum (http://ocaml-batteries-team.github.io/batteries-included/hdoc2/BatEnum.html)
or the stand-alone Gen package
(http://cedeela.fr/~simon/software/gen/Gen.S.html). It looks
superficially like list map, but the order of execution will be like
after a fusion, which should improve cache locality and avoid
allocations of intermediate lists.

Cheers,
Jonas

[Caml-list] Question about Optimization

[Gregory Malecha]

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

Hello --

I'm wondering if there is any work (and interest) on supporting
user-defined optimizations similar to GHC's rewrite rules in the Ocaml
compiler. For example, a standard example would be specifying map fusion:

map f (map g ls) = map (fun x -> f (g x)) ls

This works well in Haskell due to laziness and (mostly) purity but things
are obviously more complex in Ocaml since you can not pretend that things
are pure (due to exceptions, references, IO, and non-termination).

On a related note, this sort of optimization could require a reasonable
amount of static analysis for effects (or trying to reflect effects in the
type system). Has there been any work related to this?

Thank you.

-- 
gregory malecha
gmalecha.github.io

[-- Attachment #2: Type: text/html, Size: 1112 bytes --]