Re: "ocaml_beginners"::[] Speed and mutable data.

Richard,

My original code was using a for-loop, and I have tried
Array.unsafe_get... but not both at the same time, which I will give
a shot, along with switching out pred and succ.

I am unsure about the references, though, since for every element of
array cur, I need the corresponding element from array pre and that
corresponding element's two neighbors (where pre is the previous
generation, and cur is the next) - I have to iterate over the array
no matter what to get those values (or do I?). Of course, I'm not
much of a programmer, so I'm sure I'm not seeing the whole picture.

Jon & Fabrice,

I should probably consider using a bigint, as that is pretty much
how Wolfram describes an implementation in the notes in his book
(and how some rules can be simplified to simple bitshift
operations), and he also provides a table of Boolean operations for
the elementary rules as well, like Fabrice describes. And my
implementation was so simple too... back to drawing board.

Thanks all, for the help.
Matthew T.

Messages in this topic (6) Reply (via web post) | Start a new topic

.

On Sat, Jun 14, 2008 at 11:19:01PM -0000, mhtraylor329 wrote:
> I am unsure about the references, though, since for every element of
> array cur, I need the corresponding element from array pre and that
> corresponding element's two neighbors (where pre is the previous
> generation, and cur is the next) - I have to iterate over the array
> no matter what to get those values (or do I?).

Sure, of course you have to iterate over the array. The difference is
that you may want to avoid fetching the same data out of the array
several times. ocamlopt is _not_ gcc. It doesn't do much in the way
of optimization at all, it very much literally translates the code you
write into machine code. If you write OCaml code to fetch the same
value twice, then it'll write machine code to fetch the same value
twice.

Consider the following rather dumb code:

let array = Array.make 100 0 in
for i = 0 to 99 do
let j = Array.unsafe_get array i in
let k = Array.unsafe_get array i in
Array.unsafe_set array i (j+k);
Array.unsafe_set array i (j+k)
done

A C compiler would optimize this in a number of ways: It would
probably recognize that j and k are the same. It would certainly
hoist the implicit computation of array+i out (turning it into a
simple counter variable). It would move the explicit code duplication
(j+k) into a single operation.

On the other hand, ocamlopt translates the above code pretty literally
into assembly (confirmed on my i386 laptop with 3.10.2). You should
therefore use profiling to find the 'hot' loops in your code and, if
your code runs too slow, optimize them by hand. Something of a pain,
but it makes ocamlopt much simpler & faster for the common case, and
hand optimization can usually get you within a few percentage points
of C anyway.

movl -2(%eax, %ebx, 2), %esi ; let j = Array.unsafe_get...
movl -2(%eax, %ebx, 2), %edx ; let k = Array.unsafe_get...
lea -1(%esi, %edx), %ecx ; j+k
movl %ecx, -2(%eax, %ebx, 2) ; Array.unsafe_set...
lea -1(%esi, %edx), %ecx ; j+k
movl %ecx, -2(%eax, %ebx, 2) ; Array.unsafe_set...

On the same subject:
http://camltastic.blogspot.com/2008/05/optimizing-memory-allocation-and-loops.html

Rich.

--
Richard Jones
Red Hat

Messages in this topic (7) Reply (via web post) | Start a new topic

.