More questions on the suitability of Haskell (and FP) for simulation work
michael....@gmail.com
Another question following up on my previous ones:
What about doing a large simulation of say 1000's of entities each with
their own state, and the course of the simulation being (naturally)
highly sensitive to the details of each state:
It would seem to be that one is going to have to resort to passing
around the entire global state as a parameter in most of the functions
of the sim.
Anyone with any experience doing large scale simulations in an FP?
Are my concerns jusitified or of only apparent concern?
Your comments are appreciated,
cheers,
-Mike Goodrich
Matthias Kretschmer
> Greetings All,
>
> Another question following up on my previous ones:
>
> What about doing a large simulation of say 1000's of entities each with
> their own state, and the course of the simulation being (naturally)
> highly sensitive to the details of each state:
>
> It would seem to be that one is going to have to resort to passing
> around the entire global state as a parameter in most of the functions
> of the sim.
no - use a state monad or maybe some more advanced monad that does error
handling. Which may be handy if the simulation may fail in some way.
>
> Anyone with any experience doing large scale simulations in an FP?
>
> Are my concerns jusitified or of only apparent concern?
>
> Your comments are appreciated,
>
> cheers,
>
> -Mike Goodrich
>
--
Gruss
Matthias Kretschmer
michael....@gmail.com
Scheme, or ML?
Remi Vanicat
> How about for FP environments lacking such Monads such as Clean,
> Scheme, or ML?
>
I believe that clean have every thing that one need to define a monad
in it, even if there is none in the stdlib (Not completely sure, but it
is what I remember from the time when I use it). Scheme and ML are
impure FP, and have less use of monad (in ML at least, one could use
reference in place of state monad, exception for error monad, and
direct imperative feature in place of the IO monad for example). Note
that I've recently read of an ocaml library to use monad, see :
http://caml.inria.fr/pub/ml-archives/caml-list/2004/10/06593c8612be418e12a286faba979e96.en.html
and
http://caml.inria.fr/pub/ml-archives/caml-list/2004/10/f84296b1ffc2b384e98e801a33a5dbbb.en.html
--
Rémi Vanicat
Jens Axel Søgaard
> How about for FP environments lacking such Monads such as Clean,
> Scheme, or ML?
<http://schemecookbook.org/view/Cookbook/IdiomMonadicProgramming>
--
Jens Axel Søgaard
Jon Harrop
> How about for FP environments lacking such Monads such as Clean,
> Scheme, or ML?
Just use an imperative style. We do physical simulations with up to 10^7
entities in OCaml, BTW.
--
Dr Jon D Harrop, Flying Frog Consultancy
http://www.ffconsultancy.com
Dirk Thierbach
> Another question following up on my previous ones:
> What about doing a large simulation of say 1000's of entities each with
> their own state, and the course of the simulation being (naturally)
> highly sensitive to the details of each state:
> It would seem to be that one is going to have to resort to passing
> around the entire global state as a parameter in most of the functions
> of the sim.
As it has already been said several times, you can use a monad
to "hide the plumbing". Monads in itself are just a "FP programming
pattern"; you have them in every FP language.
Or, if each of the entities only depends on it's own state, and on a
fixed number of "inputs" from other entities, you can "tie the knot"
directly, without a monad. Circuit simulations for example can be
easily done this way.
Or, you can cheat and use imperative features (in Haskell, this
can only be done inside special monads). In Lisp, OCaml or other strict
languages this can be done directly.
> Anyone with any experience doing large scale simulations in an FP?
For really large scale simulations, Haskell might be a bit too slow.
Other FP languages are faster,.
> Are my concerns jusitified or of only apparent concern?
Why don't you just try a simplified experimental prototype
implementation? This should answer your question much better than
any abstract discussion.
With a bit of googling, it should also be possible to find examples
for simulations implented in a FP language, e.g. the circuit simulations
mentioned above.
- Dirk
Arjen van Weelden
> michael....@gmail.com writes:
>
>
>>How about for FP environments lacking such Monads such as Clean,
>>Scheme, or ML?
>>
>
>
> I believe that clean have every thing that one need to define a monad
> in it, even if there is none in the stdlib (Not completely sure, but it
> is what I remember from the time when I use it).
Your remembered correctly. Defining monads, such as the IO monad, in
Clean works as follows:
class Monad m where
return :: a -> m a
(>>=) infixl 1 :: (m a) (a -> m b) -> m b
(>>) infixl 1 :: (m a) (m b) -> mb
(>>) l r :== l >>= \_ -> r
:: ST s a = {runST :: !(s -> *(a, s))}
instance Monad (ST .s) where
return x = {runST = \st -> (x, st)}
(>>=) l r = {runST = bind}
where
bind st = let (x, st1) = l.runST st in (r x).runST st1
:: IO a :== ST *World a
Too bad that the names >> and return clash with functions defined in
Clean's StdEnv (if you import it).
michael....@gmail.com
Interesting.
What kind of performance are you seeing, both in terms of human
development effort and execution speed, memory usage, etc?
cheers,
-mg
Jon Harrop
> Jon Harrop wrote:
>> michael....@gmail.com wrote:
>> > How about for FP environments lacking such Monads such as Clean,
>> > Scheme, or ML?
>>
>> Just use an imperative style. We do physical simulations with up to
> 10^7
>> entities in OCaml, BTW.
>
>
> What kind of performance are you seeing, both in terms of human
> development effort and execution speed, memory usage, etc?
Human development: first working version is typically 10x faster to develop
in OCaml than C++.
Execution speed: varies enormously. Sometimes 3x faster in C++, sometimes
orders of magnitude faster in OCaml. C++ is much more difficult to optimise
than OCaml.
Memory usage: I didn't notice a difference on 32-bit but having just moved
to 64-bit, OCaml uses quite a bit more memory, probably just under 2x that
of C++ and this is likely to be difficult to improve (as it is probably due
to boxing inside the provided data structures). Careful use of GC.compact
may help.
Visualisation is our main concern, rather than the simulations themselves.
For this, code size is typically 2-5x smaller with OCaml than with C++ and
performance is often exactly the same. Lots of useful patterns which appear
in most OpenGL code can be factored out into higher-order functions.
Alwyn
>
> C++ is much more difficult to optimise than OCaml.
Do you optimise by hand or automatic optimisation by the compiler? It's my
experience that the O'Caml compiler does very little optimisation, and
much inlining and so on has to be done by hand.
My limited experience (mostly with numerical code) suggests to me that
the O'Caml optimising compiler produces code that runs faster than code
compiled by GCC without optimisations but cannot compete with GCC when
optimisations are turned on.
Alwyn
Jon Harrop
> On Sat, 09 Apr 2005 21:02:31 +0100, Jon Harrop wrote:
>> C++ is much more difficult to optimise than OCaml.
>
> Do you optimise by hand or automatic optimisation by the compiler?
I always have compiler optimisations on.
> It's my experience that the O'Caml compiler does very little optimisation,
Yes, ocamlopt does virtually no high-level optimisations. But it does an
excellent job of low-level optimisations (e.g. of numeric types, to recover
performance typically within 2x of C).
> and much inlining and so on has to be done by hand.
Inlining is one of the most unimportant (and uninteresting!) optimisations,
IMHO. When optimising you absolutely must start with the biggest possible
improvements. Typically, this means improving the asymptotic complexity.
For example, the STL set_union in C++ is slower than Set.union in OCaml. In
one of my programs, equivalent implementations show OCaml to be 100x faster
than C++. Optimising the C++ requires intricate knowledge of the STL and
the use of a different (destructive) programming style. The resulting code
is then twice as long, bears little resemblance to the underlying
mathematics and, consequently, is much more likely to be wrong but it is
now 2.4x faster than the OCaml. That was for only a few hundred lines of
C++.
For much bigger programs, say thousands of lines or more, it becomes
intractable to implement the necessary optimisations in C++, even if you
know what is required (it just requires so much effort, coding, debugging
etc.). So, in the end, the main reason my OCaml programs are so much faster
is that I can develop (optimise) them much more quickly, rather than
anything to do with the compiler itself. This is particularly true in the
case of hierarchical data structures like trees and certain types of graph,
where the asymptotic complexities are much better but the code is much more
complicated.
If the solutions to your problems are clear-cut and simple (e.g. if you're
only doing vector-matrix work) then this isn't true and OCaml won't be a
good choice. If you're modelling only 10^3 entities and are finding it
computationally expensive then my bet is that you're doing something
intrinsically complicated, in which case you'll almost certainly benefit
from using OCaml.
> My limited experience (mostly with numerical code) suggests to me that
> the O'Caml optimising compiler produces code that runs faster than code
> compiled by GCC without optimisations but cannot compete with GCC when
> optimisations are turned on.
I'm comparing ocamlopt 3.08.3 with g++ 3.3.5 and 3.4.4 with -O2.
--
Dr Jon D Harrop, Flying Frog Consultancy
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists
Joachim Durchholz
>> and much inlining and so on has to be done by hand.
>
> Inlining is one of the most unimportant (and uninteresting!) optimisations,
> IMHO.
Just to keep the record straight: this statement is true when applied to
manual optimisation.
For compilers, things are different: inlining is one of the more
important steps - not so much for its inner value (which isn't great but
not totally irrelevant either), but because it paves the way for a host
of other optimisations.
Regards,
Jo
Tony Finch
>Jon Harrop wrote:
>>
>> Inlining is one of the most unimportant (and uninteresting!) optimisations,
>> IMHO.
>
>important steps - not so much for its inner value (which isn't great but
>not totally irrelevant either), but because it paves the way for a host
>of other optimisations.
It's worth reading the paper about GHC's inliner, which includes some
empirical results about the effectiveness of inlining, and some discussion
of how it interacts with other optimisations.
http://research.microsoft.com/Users/simonpj/Papers/inlining/index.htm
Tony.
--
f.a.n.finch <d...@dotat.at> http://dotat.at/
ARDNAMURCHAN POINT TO CAPE WRATH INCLUDING THE OUTER HEBRIDES: SOUTHWEST
VEERING WEST 5 TO 7, OCCASIONALLY GALE 8. RAIN THEN SHOWERS VISIBILITY:
MODERATE OR GOOD. ROUGH OR VERY ROUGH.
Alwyn
>
> Inlining is one of the most unimportant (and uninteresting!) optimisations,
> IMHO.
Inlining by hand is a chore, certainly, but I have found that doing so in
O'Caml programs can give significant performance boosts. It would be nice
if it could be left to the compiler to do.
> When optimising you absolutely must start with the biggest possible
> improvements.
I couldn't possibly quarrel with that.
> Typically, this means improving the asymptotic complexity.
Well yes, where the opportunity arises.
> For example, the STL set_union in C++ is slower than Set.union in OCaml.
Is this by design, or are you referring to a particular implementation of
the C++ standard library? I am given to understand that there are huge
differences in quality of implementation in this area and that current
versions of GCC's libstdc++ are nothing like as well optimised as some
commercial products.
Alwyn
Jon Harrop
> On Sun, 10 Apr 2005 23:54:39 +0100, Jon Harrop wrote:
>> Inlining is one of the most unimportant (and uninteresting!)
>> optimisations, IMHO.
>
> Inlining by hand is a chore, certainly, but I have found that doing so in
> O'Caml programs can give significant performance boosts. It would be nice
> if it could be left to the compiler to do.
I've only ever seen manual inlining give big performance improvements on
artificial examples. I wrote an OCaml program which deliberately hit a weak
point of OCaml's inlining which showed a 15x performance improvement with
inlining. In contrast, I've only ever seen <10% performance improvement
from inlining OCaml functions in useful code.
>> Typically, this means improving the asymptotic complexity.
>
> Well yes, where the opportunity arises.
Which is all but the simplest cases. And even they are often dubious. :-)
>> For example, the STL set_union in C++ is slower than Set.union in OCaml.
>
> Is this by design, or are you referring to a particular implementation of
> the C++ standard library? I am given to understand that there are huge
> differences in quality of implementation in this area and that current
> versions of GCC's libstdc++ are nothing like as well optimised as some
> commercial products.
The poor performance of the STL compared to OCaml's library is, in this
case, directly due to the imperative design of the STL and the functional
design of OCaml's set implementation and not to do with any given
implementation. Functional programming is simply vastly more efficient in
this case.
Specifically, due to its imperative design, the STL's set_union function
must explicitly copy all elements in both sets as the originals are mutable
and, therefore, may be changed. In contrast, referential transparency
allows OCaml's Set.union function to refer back to branches of balanced
binary tree in the input sets whenever they can be reused.
Moreover, not only does the functional approach give huge performance
improvements over the straightforward imperative approach, it results in
vastly more succinct code (the STL implementation is literally 10x the
length of the OCaml implementation).
The code at the end of this post produces the following results on my
computer:
$ g++ -O2 -march=athlon-tbird union.cc -o union
$ ./union 1000000
631920 U 631704 = 864791 1.48059s
631920 U 632027 = 1063903 1.43702s
631920 U 631504 = 1263424 1.66908s
$ ocamlopt unix.cmxa union.ml -o union
$ ./union 1000000
632672 U 632366 = 864934 2.433055s
632672 U 631960 = 1064719 0.824161s
632672 U 631852 = 1264524 0.000076s
As you can see, computing the union of two densely overlapping sets is
slightly faster using the STL from C++ (1.48s vs 2.43s). However, when
computing the union of more distinct sets ([0, n) and [n/2, 3n/2)), OCaml
is slightly faster (0.82s vs 1.44s). Finally, when computing the union of
entirely distinct sets, OCaml is over four orders of magnitude faster
(0.000076s vs 1.70s).
To add insult to injury, the OCaml program is less than half the length of
the C++ program and much clearer.
-----
module Set = Set.Make(struct
type t = int
let compare (i:t) j = compare i j
end)
let () = match Sys.argv with
[| _; n |] ->
let n = int_of_string n in
let rec random_set set n rand =
if n=0 then set else
random_set (Set.add (rand ()) set) (n - 1) rand in
let s1 = random_set Set.empty n (fun () -> Random.int n) in
let aux rand =
let s2 = random_set Set.empty n rand in
let t = Unix.gettimeofday () in
let s3 = Set.union s1 s2 in
let t = Unix.gettimeofday () -. t in
let length s = Set.fold (fun _ n -> n+1) s 0 in
Printf.printf "%d U %d = %d %fs\n"
(length s1) (length s2) (length s3) t in
List.iter aux [(fun () -> Random.int n);
(fun () -> n/2 + Random.int n);
(fun () -> n + Random.int n); ];
| _ -> output_string stderr "Usage: union <n>\n"
-----
#include <set>
#include <iostream>
#include <string>
#include <sys/time.h>
#include <unistd.h>
using namespace std;
double gettime() {
timeval tv;
gettimeofday(&tv, NULL);
return double((long long)tv.tv_sec * 1000000LL +
(long long)tv.tv_usec) / 1e6;
}
typedef set<int> myset;
int n;
int myrand1() { return rand() % n; }
int myrand2() { return n/2 + rand() % n; }
int myrand3() { return n + rand() % n; }
template<typename F>
void aux(int n, myset &s1, F myrand) {
myset s2, s3;
for (int i=0; i<n; i++) s2.insert(myrand());
double t = gettime();
set_union(s1.begin(), s1.end(),
s2.begin(), s2.end(),
inserter(s3, s3.begin()));
double t2 = gettime() - t;
cout << s1.size() << " U " << s2.size() << " = " << s3.size() << " "
<< t2 << "s\n";
}
int main(int argc, char *argv[]) {
if (argc != 2) {
cerr << "Usage: union <n>\n";
return 1;
}
n = atoi(argv[1]);
myset s1;
for (int i=0; i<n; i++) s1.insert(rand() % n);
aux(n, s1, myrand1);
aux(n, s1, myrand2);
aux(n, s1, myrand3);
return 0;
}
-----
--
Dr Jon D Harrop, Flying Frog Consultancy
Alwyn
>
> The code at the end of this post produces the following results on my
> computer:
>
> $ g++ -O2 -march=athlon-tbird union.cc -o union
> $ ./union 1000000
> 631920 U 631704 = 864791 1.48059s
> 631920 U 632027 = 1063903 1.43702s
> 631920 U 631504 = 1263424 1.66908s
>
> $ ocamlopt unix.cmxa union.ml -o union
> $ ./union 1000000
> 632672 U 632366 = 864934 2.433055s
> 632672 U 631960 = 1064719 0.824161s
> 632672 U 631852 = 1264524 0.000076s
>
> As you can see, computing the union of two densely overlapping sets is
> slightly faster using the STL from C++ (1.48s vs 2.43s). However, when
> computing the union of more distinct sets ([0, n) and [n/2, 3n/2)), OCaml
> is slightly faster (0.82s vs 1.44s). Finally, when computing the union of
> entirely distinct sets, OCaml is over four orders of magnitude faster
> (0.000076s vs 1.70s).
I take the point. I get the following on my 5-year-old 400MHz PowerMac G4:
~/Developer/C++ $ g++ -v
Reading specs from /usr/libexec/gcc/darwin/ppc/3.3/specs
Thread model: posix
gcc version 3.3 20030304 (Apple Computer, Inc. build 1671)
~/Developer/C++ $ g++ -O2 -mcpu=7400 union.cc -o union
~/Developer/C++ $ ./union 1000000
632798 U 632412 = 865244 2.54414s
632798 U 632005 = 1064735 3.39771s
632798 U 632077 = 1264875 3.44152s
~/Developer/OCaml $ ocamlopt -v
The Objective Caml native-code compiler, version 3.08.3
Standard library directory: /usr/local/lib/ocaml
~/Developer/OCaml $ ocamlopt unix.cmxa union.ml -o union
~/Developer/OCaml $ ./union 1000000
632672 U 632366 = 864934 2.411603s
632672 U 631960 = 1064719 1.161019s
632672 U 631852 = 1264524 0.000153s
> To add insult to injury, the OCaml program is less than half the length
> of the C++ program and much clearer.
Indeed it is. This is the biggest advantage of all, in my opinion.
Alwyn
Mark Tarver
www.lambdassociates.org. It is
open source and includes an
extremely powerful type system
and pattern-directed programming.
It runs on top of Common Lisp and
is free under the GNU licence.
To answer your question, you can
do simulations of interacting entities
in Qi. See chapter 11 on structures
and chapter 17 on Intelligent Agents
in the online text "Functional Programming
in Qi".
Mark
Vincenzo Ciancia
> You may want to look at Qi from
> www.lambdassociates.org.
I have looked at the webpage, and found the typing system of Qi interesting,
but I can't really grasp the difference between ocaml types, haskell types
with type classes and sequent-calculus based types. Are the latter more
fine-grained? Can you show some simple example where the sequent-calculus
discipline is more expressive, more powerful or in other ways "better" than
haskell and ocaml types?
Thanks
Vincenzo
--
Please note that I do not read the e-mail address used in the from field but
I read vincenzo_ml at yahoo dot it
Attenzione: non leggo l'indirizzo di posta usato nel campo from, ma leggo
vincenzo_ml at yahoo dot it
Mark Tarver
book which gives some nice examples of how to
use Qi to type check programs involving natural
numbers. If you are not convinced I can send you
a program which expounds part of the type theory of
interval arithmetic - something I picked up and dropped.
I guess the most general answer is that when we are
dealing with types, we can often see that there are
certain logical properties which group around these
types and the functions that work with them. Sometimes
we can express these properties axiomatically or in
deductive form and sometimes we can see that the rules
we provide can be animated into a type checker.
What Qi does is give you the ability to say math'lly or
logically exactly what your theory is. The sequent
notation is compiled into fast code. So if you have
e.g. an idea of the type theory of eval or the type theory
of primes and composites, well you have the chance to
use it for a serious application and see it motor.
No other language gives you this kind of power.
The down side is that Qi is a very sharp tool and you
can cut yourself. In particular you can create axiom
sets which will generate infinite regresses or ones that
collapse the type system altogether! See the end of
chapter 13 for examples. You cannot do this in ML or
Haskell because you are denied this power.
Mark