[Caml-list] Question about Optimization

[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 --]

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

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

[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

[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

[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

[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

[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 --]

[Caml-list] The fastest stream library [Was: Question about Optimization]

[Oleg]

> 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:

to which Gabriel Scherer commented on Thu, 21 Apr 2016 12:02:14 -0400

> 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.

Indeed. We'd like to point out an application of MetaOCaml, not just
to map fusion -- but also concat_map fusion and zip fusion, etc. We
present a streams library that supports the wide set of combinators --
from map and filter to concat_map (flat_map) and zip -- and produces
the hand-written quality code. It is faster than Batteries by up to more
than two orders of magnitude.

        http://okmij.org/ftp/meta-programming/strymonas.pdf
        http://strymonas.github.io/

Unlike GHC Rules, we guarantee the performance.

Re: [Caml-list] The fastest stream library [Was: Question about Optimization]

[Gregory Malecha]

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

Thanks. This is interesting, I'll have to take a closer look at it.

On Tue, Nov 8, 2016, 7:01 AM Oleg <oleg@okmij.org> 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:
>
> to which Gabriel Scherer commented on Thu, 21 Apr 2016 12:02:14 -0400
>
> > 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.
>
> Indeed. We'd like to point out an application of MetaOCaml, not just
> to map fusion -- but also concat_map fusion and zip fusion, etc. We
> present a streams library that supports the wide set of combinators --
> from map and filter to concat_map (flat_map) and zip -- and produces
> the hand-written quality code. It is faster than Batteries by up to more
> than two orders of magnitude.
>
>         http://okmij.org/ftp/meta-programming/strymonas.pdf
>         http://strymonas.github.io/
>
> Unlike GHC Rules, we guarantee the performance.
>
-- 

- gregory malecha
  gmalecha.github.io

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

Re: [Caml-list] The fastest stream library [Was: Question about Optimization]

[Gabriel Scherer]

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

Hi Oleg,

Thanks for the work, it does look very nice and I will have a look. My
remarks below concern the benchmarks.

I regret not being pointed to this work earlier, because I think that
measuring the performance of Enum as a representative OCaml stream library
performance is not the best choice : Enum is designed to be flexible in a
bit too many ways to be efficient on pure-streaming scenarios (it supports
a generic "clone", and effectful generators, that makes the codebase too
complex for its own good; I think that Batteries community is aware that
Enum is not as good as it should be right now). There are other, more
efficient streaming libraries out there, including BatSeq in Batteries that
should already be sensibly faster; Core and Containers also have more
efficient streaming libraries.

I think that it would be good to try to use at least BatSeq for your
benchmarks. I won't have time this week or the next one, but then maybe I
could look at it. I'm not surprised that neither POPL reviewing nor POPL
artifact evaluation caught this issue, but next time you benchmark using
Batteries, feel free to send an email to the batteries-users mailing-list
to point it out.

On Tue, Nov 8, 2016 at 7:05 AM, Gregory Malecha <gmalecha@gmail.com> wrote:

> Thanks. This is interesting, I'll have to take a closer look at it.
>
> On Tue, Nov 8, 2016, 7:01 AM Oleg <oleg@okmij.org> 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:
>>
>> to which Gabriel Scherer commented on Thu, 21 Apr 2016 12:02:14 -0400
>>
>> > 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.
>>
>> Indeed. We'd like to point out an application of MetaOCaml, not just
>> to map fusion -- but also concat_map fusion and zip fusion, etc. We
>> present a streams library that supports the wide set of combinators --
>> from map and filter to concat_map (flat_map) and zip -- and produces
>> the hand-written quality code. It is faster than Batteries by up to more
>> than two orders of magnitude.
>>
>>         http://okmij.org/ftp/meta-programming/strymonas.pdf
>>         http://strymonas.github.io/
>>
>> Unlike GHC Rules, we guarantee the performance.
>>
> --
>
> - gregory malecha
>   gmalecha.github.io
>

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

Re: [Caml-list] The fastest stream library [Was: Question about

[Oleg]

Gabriel wrote:

> I regret not being pointed to this work earlier, because I think that
> measuring the performance of Enum as a representative OCaml stream library
> performance is not the best choice : Enum is designed to be flexible in a
> bit too many ways to be efficient on pure-streaming scenarios (it supports
> a generic "clone", and effectful generators, that makes the codebase too
> complex for its own good; I think that Batteries community is aware that
> Enum is not as good as it should be right now). There are other, more
> efficient streaming libraries out there, including BatSeq in Batteries that
> should already be sensibly faster; Core and Containers also have more
> efficient streaming libraries.

Please do note that we make the double claim: wide expressivity *and*
guaranteed highest performance. We support not just the standard map and
filter, but zipping of streams with flat_maps in them, with both
finite and infinite streams. So we do want generality. From this
point, Enum was quite an appropriate.

Speaking of benchmarks, the real point of comparison is the
hand-written code for each benchmark, written with imperative loops,
references, etc. (We admit that some of that on several occasions
the hand-written baseline code was fine-tuned when it turned out that the
generated code outperformed it.) Please do feel free to suggest faster
versions.

Re: [Caml-list] The fastest stream library [Was: Question about

[Gabriel Scherer]

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

I think we are on the same wavelength, but given that you are an expert on
streaming library I'm going to expand on Enum as you might be interested.
There are many feature axes for streaming libraries and Enum tries to cover
a bit too much of them. It was designed, by the Extlib project, as a
go-between library to translate from one data structure to the other, and
to be as flexible as possible:

- It supports a wide variety of combinators common to stream libraries, on
both finite and infinite stream; there is also a notion of whether it's
easy/fast, for a given stream, to compute its size (without consuming the
stream), to eg. preallocate arrays when converting from enum to array, and
combinators try to preserve that information when they can
- In the style of the venerable Stream module, Enum is a "destructive
streaming" library, in that it mutates its internal state when you access
the next element. I think the idea is that in general this is more
memory-efficient (you cannot keep a reference to the start of the stream
that leaks memory), but it's also a bit error-prone in non-linear usage
scenarios.
- To still support non-linear usage scenarios, Enum streams have a "clone"
operation that duplicates a stream into two copies. The useful, interesting
and difficult thing about clone is that getting the same element on both
the original and the clone stream should not duplicate any side-effects
involved in computing the value: clone should duplicate the stream of
values, but keep threading the computation effect.

In my experience most of the complexity (and fragility) of the current Enum
implementation comes from the destructive aspects and cloning. The
implementation is in a fairly imperative style (enumerations are defined as
object-style record of *mutable* methods that close over the enumeration
state) and there is a fair amount of bookkeeping involved on each
update/next to support this feature set. This is not a big issue for the
original use-case, which is to convert between data structures (have 2*N
conversion functions, Foo.{to,of}_enum, instead of N^2 conversion
functions), where performance bottlenecks are usually on the
data-structure-processing side, but this means that using Enum for heavy
stream processing is known to be slow. Again, I would expect BatSeq (which
is neither destructive nor memoizing) to do much better on these workflows.

It is perfectly reasonable to question whether we need this complex feature
set for a central streaming library. I have mixed thoughts on this question:

- as a library developer, my experience is that the current implementation
is too fragile and too slow for its own good, and I think that users would
be better served by a simpler abstraction that does less in a more robust
way. The pragmatic choice is thus to use simpler stream libraries. Another
interesting point is that, if you develop those simpler, more robust stream
libraries, it is sometimes possible to reuse them to build more complex
streams on top of them (for example, a solid purely-functional stream
implementation can be turned into a destructive stream implementation by
passing references to functional streams around), so this decomposition of
concern would also help rebuilding a more robust Enum. Simon Cruanes did
good work in that direction in preliminary versions of his
Containers/Sequence libraries (I can't find specific references right now,
to the various streaming types with different feature support).

- as a language designer, I think that our inability to implement Enum
robustly on the first attempt is the sign of an interesting problem to be
solved. The feature set, from a user point of view, is *not* unreasonable,
and justifiably useful in some scenarios. As language designers, we know
that the cloning / non-duplication of effects is like playing with fire,
but that is still a problem that we should be able to solve. (We have
people properly design lock-free data structures, which are also
unreasonably complex; we should be demanding of our standard libraries!) If
I had a good way to *specify* the behaviour of a streaming library
respecting all these constraints, I think that would also clarify how to
give an simpler, more efficient, more robust implementation of it. (Another
concern that it could be interesting to throw in the mix is batching.) I
regret not being informed enough about the myriad of Haskell-side solutions
to the problem of effectful streaming, as there may also be interesting
inspiration to be taken. I tried to get François Pottier interested in the
problem of formalizing a specification for Enum, but he ran away screaming
before I finished enumerating the design points above.

On Tue, Nov 8, 2016 at 7:47 AM, Oleg <oleg@okmij.org> wrote:

>
> Gabriel wrote:
>
> > I regret not being pointed to this work earlier, because I think that
> > measuring the performance of Enum as a representative OCaml stream
> library
> > performance is not the best choice : Enum is designed to be flexible in a
> > bit too many ways to be efficient on pure-streaming scenarios (it
> supports
> > a generic "clone", and effectful generators, that makes the codebase too
> > complex for its own good; I think that Batteries community is aware that
> > Enum is not as good as it should be right now). There are other, more
> > efficient streaming libraries out there, including BatSeq in Batteries
> that
> > should already be sensibly faster; Core and Containers also have more
> > efficient streaming libraries.
>
> Please do note that we make the double claim: wide expressivity *and*
> guaranteed highest performance. We support not just the standard map and
> filter, but zipping of streams with flat_maps in them, with both
> finite and infinite streams. So we do want generality. From this
> point, Enum was quite an appropriate.
>
> Speaking of benchmarks, the real point of comparison is the
> hand-written code for each benchmark, written with imperative loops,
> references, etc. (We admit that some of that on several occasions
> the hand-written baseline code was fine-tuned when it turned out that the
> generated code outperformed it.) Please do feel free to suggest faster
> versions.
>

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

Re: [Caml-list] The fastest stream library [Was: Question about

[Oleg]

Gabriel, 

        Thank you for the detailed and thoughtful message and the
motivations behind Enum choices. The library and language design was
the central issue in our paper. We do have a different overall
approach, which you haven't yet touched. The approach is
meta-programming. 

        It is high-performance community who discovered for themselves
that the most promising way to increase or maintain performance is by
meta-programming. It was late Ken Kennedy (of High-Performance Fortran
fame) who came with telescoping languages and popularized the idea of
active libraries. It was again Ken Kennedy who coined the phrase
``abstraction without guilt''. The references (in old, by now) paper
make the case that become even clearer by now
        http://www-rocq.inria.fr/~acohen/publications/CDGHKP06.ps.gz

Thus we can have a very general interface and still very efficient
implementation. We can have a pure functional, a fully compositional
interface and a very tangled, imperative implementation with
reference cells all over. The strymonas library is an example of that.

Re: [Caml-list] The fastest stream library [Was: Question about

[Simon Cruanes]

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

Using meta-programming is very nice indeed, but until meta-OCaml is
merged into OCaml itself, it will be no use for most OCaml programmers
(at least, those I know of). So it still makes sense to write
alternative stream libraries that do not rely on metaprogramming nor on
features yet to come (effects…). For pure OCaml libraries, there is no
clear winner yet (depends on what API is exposed), Sequence is faster in
most cases but cannot implement zip/merge, BatSeq/Core.Sequence are good
in average and probably the best tradeoff overall, Enum is a bit
complicated but quite comprehensive…

Le Sat, 12 Nov 2016, Oleg a écrit :
> Gabriel, 
> 
>         Thank you for the detailed and thoughtful message and the
> motivations behind Enum choices. The library and language design was
> the central issue in our paper. We do have a different overall
> approach, which you haven't yet touched. The approach is
> meta-programming. 
> 
>         It is high-performance community who discovered for themselves
> that the most promising way to increase or maintain performance is by
> meta-programming. It was late Ken Kennedy (of High-Performance Fortran
> fame) who came with telescoping languages and popularized the idea of
> active libraries. It was again Ken Kennedy who coined the phrase
> ``abstraction without guilt''. The references (in old, by now) paper
> make the case that become even clearer by now
>         http://www-rocq.inria.fr/~acohen/publications/CDGHKP06.ps.gz
> 
> Thus we can have a very general interface and still very efficient
> implementation. We can have a pure functional, a fully compositional
> interface and a very tangled, imperative implementation with

-- 
Simon Cruanes

http://weusepgp.info/
key 49AA62B6, fingerprint 949F EB87 8F06 59C6 D7D3  7D8D 4AC0 1D08 49AA 62B6

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 801 bytes --]

Re: [Caml-list] The fastest stream library [Was: Question about

[Gabriel Scherer]

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

In case anyone on the list wonders about MetaOCaml (
http://okmij.org/ftp/ML/MetaOCaml.html ), an excellent resource to learn
about it is Jeremy Yallop's course on staging (as part of an Advanced
Functional Programming course at Cambridge,
https://www.cl.cam.ac.uk/teaching/1415/L28/materials.html ), presented as
an IOCamlJS notebook:

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

The last discussion about whether MetaOCaml could eventually be merged into
OCaml that I'm aware of happened in May 2015:
http://lambda-the-ultimate.org/node/5146 . At the time, Oleg replied that
there are still design aspects of (BER) MetaOCaml that he was not fully
satisfied with, and wanted to wait before proposing it for upstreaming.

(There is a virtuous interaction between MetaOCaml and modular implicits;
in particular, one pain point of MetaOCaml's design is cross-stage
persistence (should it be a language construct or a derived operation?),
and implicits make it much more convenient to define and use persistence
operators.)


On Sat, Nov 12, 2016 at 11:21 AM, Simon Cruanes <simon.cruanes.2007@m4x.org>
wrote:

> Using meta-programming is very nice indeed, but until meta-OCaml is
> merged into OCaml itself, it will be no use for most OCaml programmers
> (at least, those I know of). So it still makes sense to write
> alternative stream libraries that do not rely on metaprogramming nor on
> features yet to come (effects…). For pure OCaml libraries, there is no
> clear winner yet (depends on what API is exposed), Sequence is faster in
> most cases but cannot implement zip/merge, BatSeq/Core.Sequence are good
> in average and probably the best tradeoff overall, Enum is a bit
> complicated but quite comprehensive…
>
> Le Sat, 12 Nov 2016, Oleg a écrit :
> > Gabriel,
> >
> >         Thank you for the detailed and thoughtful message and the
> > motivations behind Enum choices. The library and language design was
> > the central issue in our paper. We do have a different overall
> > approach, which you haven't yet touched. The approach is
> > meta-programming.
> >
> >         It is high-performance community who discovered for themselves
> > that the most promising way to increase or maintain performance is by
> > meta-programming. It was late Ken Kennedy (of High-Performance Fortran
> > fame) who came with telescoping languages and popularized the idea of
> > active libraries. It was again Ken Kennedy who coined the phrase
> > ``abstraction without guilt''. The references (in old, by now) paper
> > make the case that become even clearer by now
> >         http://www-rocq.inria.fr/~acohen/publications/CDGHKP06.ps.gz
> >
> > Thus we can have a very general interface and still very efficient
> > implementation. We can have a pure functional, a fully compositional
> > interface and a very tangled, imperative implementation with
>
> --
> Simon Cruanes
>
> http://weusepgp.info/
> key 49AA62B6, fingerprint 949F EB87 8F06 59C6 D7D3  7D8D 4AC0 1D08 49AA
> 62B6
>

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

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