Re: [Caml-list] stl?

[Brian Hurt <bhurt@spnz.org>]

On Wed, 4 Mar 2009, Jon Harrop wrote:

> On Wednesday 04 March 2009 06:11:18 Brian Hurt wrote:
>> On Wed, 4 Mar 2009, Jon Harrop wrote:
>>> Efficiency is only important in the context of functors when abstracting
>>> very fast and common functions like arithmetic without defunctorizing
>>> your code. I don't think that is why people avoid functors in OCaml.
>>
>> Arithmetic operators that are themselves very cheap.  The cost of
>> functorization is large compared to, say, floating point addition- but
>> small compared to the cost of, say, vector addition.
>
> Depends how big your vectors are.

Less than it might seem.  First of all, you have the allocation costs to 
hold the new vector- there's 3-5 clocks right there.  Let's say the 
vectors are 3 elements long.  So you have six loads and three stores- 
assume stores are free, and loads cost 1 clock apeice- they're in L1 
cache, and they're getting preloaded.  Plus the 3 clocks for the floating 
point adds.  So that's 12-15 clock cycles right there.  Say I'm being 
pessimistic by a factor of 2, and it's really only 6-8 clock cycles.  Vr.s 
10 clock cycles or so for the call via functor.  Now we're down into the 
realm of only doubling the cost of the operation, not an order of 
magnitude increase.  A single mispredicted branch or L1 cache miss that 
has to go out to L2 cache- not even main memory, just L2!- would blow the 
overhead of calling via functor out of the water.

Premature optimization is the root of all evil.

>
>> And it's expensive only because Ocaml lacks an obvious optimization
>> (defunctorization).
>
> If you neglect the enormous disadvantages: whole program analysis => no
> incremental compilation and no DLLs.
>
> You can resolve the abstraction as soon as possible, as Haskell, does but then
> you're on the slippery slope to wildly unpredictable performance that renders
> the language too risky for a lot of real work.

That explains why no one uses C++ for real work- since it resolves 
template abstractions as soon as possible, it' performance is so 
unpredictable that it renders the language too risky for a lot of real 
work.

>
>> And yet this whole discussion is simply proving my point- we're comparing
>> clock cycles here.
>
> A circular argument: you brought up clock cycles.

Yes.  Because it's only at the point where you're counting clock cycles 
that the overhead of calling via a functor matters.

>
>> But for the vast bulk of people
>> programming, performance (at least on the clock cycle level) simply isn't
>> that important
>
> For some definition of "programming" that includes website design, maybe.

Compare the number of people writing CRUD web applications in Ruby on 
Rails to the *entirity* of the professional Ocaml, SML, Haskell, and F# 
communities.  I dare you.

But no, not just web applications.  Most business logic applications. 
Large chunks of the embedded world.  Most desktop applications.  Most code 
doesn't need to be "as fast as possible", it simply needs to be "fast 
enough".

>
>> - as demonstrated by all the "real work" being done in hideously slow
>> languages like Ruby, Python, etc...
>
> Real work is done mostly in C++, Java and C# and proven predictable efficiency
> is a huge part of that.

You should have warned me before mentioning "Java" in the same sentence as 
"proven predictable efficiency".  I was drinking when I read that, and now 
I have to clean my keyboard.

It's a negligable part of that.  Try this experiment.  Go to J. Random 
software manager in Java/.Net/C++ shop.  Ask them to list the reasons they 
use the language of choice.  Don't prompt them, just let them list things 
in the order that comes to mind.  Wait and see how long it is before 
"performance" comes up as an issue.

Java currently has a decent- not great, but decent- performance story. 
Now.  But Java became popular, and got into all of these coding shops, 
back when Java was either hideously slow, or radically unpredictable in 
performance.

> F# can be much easier to work with than both OCaml and Haskell.

Yep.  And Ocaml can be much easier to work with than Haskell or F#.  And 
Haskell can be much easier to work with then F# or Ocaml.

> No, that is not overloading at all. You just replaced the functions wholesale.
>
> Operator overloading is about being able to reuse an identifier to refer to
> different functions where the resolution depends upon the argument types.

OK.  So now we have a definition of what operator overloading is.  Now, my 
question: what's it good for?  It's obviously not necessary to write 
generic code- for example, a Newton's method that works on both floats and 
ratios.

The only advantage I see is that you're able to use + instead of +. in 
many places.  OK, this is an advantage- but hardly a major one.

> You
> have not accomplished that at all and your solution is uselessly fragile,
> which is precisely it is practically unheard of in real OCaml code in this
> context.
>
> Look at another example, Knuth's algorithm for numerically robust variance:
>
>  let f (m, s, k) x =
>    let m' = m + (x - m) / float k
>    m', s + (x - m) * (x - m'), k + 1
>
> The "+" operator is used to mean both floating point addition and integer
> addition in the same expression. Functors cannot do that. You can replace "+"
> with float and int versions but only when they are in separate modules, so
> you not only end up breaking this simple expression into separate functions
> but even into separate modules. That's obviously crazy useless and, indeed,
> is precisely the motivation behind Christophe Troestlers's delimited
> overloading syntax extension.

So, let's rewrite the above code to use different operators for floating 
point and integer operations:

   let f (m, s, k) x =
     let m' = m +. (x -. m) /. float k
     m', s +. (x -. m) *. (x -. m'), k + 1

Oh yes, I see now.  How much better it is if only we had operator 
overloading.

>
> So OCaml adopted + for int and +. for float. Sounds good but it scales really
> badly when you introduce 2D and 3D homogeneous vectors and matrices,
> arbitrary-dimensional vectors and matrices, quaternions, complex numbers and
> even a 32-bit float type. You need something closer to genuine overloading.

My experience in general has been that operators don't scale in complex 
cases.  Number operators for number types scale better, but in any 
complicated case, and especially in most non-numeric cases, I prefer 
pseudo-english names.

And I note that by far the most popular language for writing numeric code 
in, the all time champ for numerics, is Fortran.  A language that didn't 
allow operator overloading or redefinition at all, and which forced you to 
use pseudo-english named functions if you wanted to add two matrixs 
together.  For a definition of pseudo-english which is loose enough to 
include names like "dgemm".

>
> Right.
>
>>> However, that is trivial to fix with run-time type information that can
>>> convey per-type functions. Both F# and my HLVM already do that.
>>
>> I suppose we could sit around and whine that Ocaml doesn't have type
>> classes, or reflection, or some other neat feature, that if it only had
>> it, we could all these neat things with them.
>>
>> Or we could use the equivalently powerfull features Ocaml *already* has...
>
> If you mean OCaml's objects, they also do not solve this problem.

Wow.  Just... wow.  I spend page after page, message after message, 
singing the praises of functors, with out nearly a peep about the objects 
the whole time.  And then, at the end of a message that was all about how 
great functors are, I mention "equivalently powerfull features", you 
immediately assume I'm refering to...

objects.

Truly, you have a dizzying intellect.

Brian