On Wednesday 02 April 2008 20:52:32 Sylvain Le Gall wrote:
> On 02-04-2008, Jon Harrop <[EMAIL PROTECTED]> wrote:
> > I think this is a bit unfair. Functors in OCaml incur a crippling
> > performance penalty here because OCaml does not inline functions across
> > functor boundaries. You're looking at an order of magnitude slowdown on
> > integer addition!
>
> I am not sure of this... I think this penalty can be removed by
> providing .cmxa and .cmx files (but i am not sure). I think this point
> should need a little more attention to be sure. Frankly, i would like to
> test this before saying that there is an 'order of magnitude'.
You cannot circumvent this problem by suppling extra files to the current
OCaml compilers. You used to be able to circumvent this problem using the
ocamldefun tool which uses whole program transformation to remove the
functors before the OCaml compilers see the code. However, I believe
ocamldefun has not been updated and no longer works (since OCaml 3.06 or so,
IIRC).
Here is a simple program to benchmark the costs of these abstractions:
open Printf
module type INumeric = sig
type t
val add : t -> t -> t
val zero : t
val one : t
end
module Int : INumeric = struct
type t = int
let add n m = n + m
let zero = 0
let one = 1
end
module Bench3(Numeric : INumeric) = struct
let bench3 n =
for i=1 to n do
ignore(Numeric.add Numeric.zero Numeric.one)
done
end
let bench1 n =
for i=1 to n do
ignore(0 + 1)
done
let bench2 add zero one n =
for i=1 to n do
ignore(add zero one)
done
include Bench3(Int)
let time f x =
let t = Sys.time() in
let f_x = f x in
printf "Took %gs\n%!" (Sys.time() -. t);
f_x
let () =
let n = 100000000 in
printf "Direct\n";
time bench1 n;
printf "Functional abstraction\n";
time (bench2 (+) 0 1) n;
printf "Functor abstraction\n";
time bench3 n;
On my machine, I get:
$ ocamlopt -inline 1000 functor.ml -o functor
$ ./functor
Direct
Took 0.304019s
Functional abstraction
Took 1.30408s
Functor abstraction
Took 1.80811s
So using a functor is 6x slower in this case.
> > This makes the ability to factor primitive numeric types using functors
> > practically useless in OCaml. The effect is compounded by OCaml's
> > inability to handle many numeric types either not at all (e.g. int16,
> > float32) or just very inefficiently (e.g. int8, int32, int64). Finally,
> > you could use functional abstraction to achieve the same effect but this
> > is also practically useless in OCaml because it does not support
> > arbitrary inlining which is, ironically, exactly what you were saying.
> > :-)
>
> Need to check this also ;-) (i was not under this impression, but i can
> do mistake).
Functors are certainly a very powerful form of abstraction but, having been
using F# professionally for 18 months now, I believe functors are not the
best solution to the problems that I have. F# does not have functors and I do
not miss them.
> > C++ is no better, of course. But F# really does provide the best of both
> > worlds with a variety of features:
> >
> > . A wealth of built-in types including int8, int16, int32, int64 and
> > float32 that are efficient.
> >
> > . Typeful inlining of functions including higher-order functions to
> > remove all costs associated with passing function arguments (which is
> > slow in OCaml) without the hideous obfuscation of error messages impose
> > by C++ templates.
> >
> > . Type specialization during JIT compilation, removing the run-time cost
> > associated with polymorphism (which is slow in OCaml).
>
> Are you talking about polymorphic variant? I am not sure you can find
> real polymorphism at runtime anywhere else.
Look at the way OCaml compiles Array.fold_left, for example. For most values,
the run-time representation uses the conventional approach of a
previous-generation FPL (like SML/Haskell implementations) whereby values are
always fitted into a machine word (with tag bits) and anything else is
represented as a pointer to a boxed value. So most polymorphic functions
simply hand around word-sized data and don't need to know or care about the
type.
But arrays are different in OCaml. The default representation of boxed floats
in arrays under this methodology is hugely inefficient. So the creators of
the current OCaml compilers started to special case certain types such as
float arrays and strings to use custom representations and the ended up
creating the motley crew of incompatible types and containers that we have
today. However, this introduces a real run-time distinction that must be
accounted for in the generated code. So the Array.fold_left function must now
check to see if it is handling a float or non-float array. This run-time type
check slows the OCaml code down.
F# inherits a completely different approach to polymorphism and code
generation from the .NET platform. Compilation is now split into two separate
stages. The first stage generates a (high-level) intermediate representation
that makes all type information available at run-time. The second stage
converts this compiled code into native code using a JIT compiler at
run-time. An obvious solution to polymorphism is to simply JIT compile a new
implementation of a function every time it is used with a new type and this
is exactly what happens to F# code.
This JIT foundation gives F# enormous practical benefits over the current
OCaml implementation:
. Complete run-time access to types, e.g. for generic printing.
. No run-time performance cost for using polymorphism thanks to type
specialization at JIT compile time.
. Optimization representations of all types in all data structures without the
need to manually special case in the compiler.
. Arbitrary unboxing of types, e.g. FFTs over complex arrays are 5.5x faster
in F# than OCaml because OCaml boxes complex numbers in arrays which is very
inefficient.
. No multitude of incompatible types and containers, just nice uniform
representations of everything.
. Richer variety of types because adding new types is easy whereas it was
prohibitively tedious with OCaml and, hence, there is still no float32 type.
. No need to write C stubs to interface to native code: all FFI code is
autogenerated by F# at run-time.
. Vastly improved performance for certain problems that can leverage run-time
code generation, like regular expression matching and FFT codelet generation.
I have spent a long time studying and using F# now and, I believe, it is
clearly the way to go for functional programming languages. I would love to
see something similar available to Linux users but, sadly, I have completely
failed in my attempts to inspire the OCaml community to build something
better, e.g. using LLVM.
> > We have some of the world's largest OCaml and F# codebases having
> > migrated from C++. I agree completely that OCaml is far better than C++
> > in practice for any non-trivial work. However, OCaml does leave room for
> > improvement and, to date, the only competitive language is F# not least
> > because it provides many of the features touched upon in this thread but
> > without sacrificing the core features of OCaml.
>
> Indeed, but F# has its own boundary (which we will discover in the
> future).
I have already discovered many problems with F# but they are very minor
compared to the main problems with OCaml. While there is no theoretical
reason why OCaml cannot catch up (e.g. by leveraging tools like LLVM and
maybe the JVM's concurrent GC) I do not believe this will ever happen.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?e
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"ocaml-developer" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/ocaml-developer?hl=en
For other OCaml forums, see http://caml.inria.fr/resources/forums.en.html
-~----------~----~----~----~------~----~------~--~---
