This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

HLVM stuff
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: -- (:) From: Jon Harrop Subject: Re: [Caml-list] HLVM stuff
```On Sunday 27 September 2009 18:43:24 David McClain wrote:
> ... as a specific example, I remember dealing with stacks of images
> taken from an infrared imaging sensor -- perhaps 256 images, each of
> which is, say 512 x 512 pixels. I needed to obtain median pixel values
> from the stack and produce one "median image", as well as perform
> thresholding, masking, perhaps some dilation and erosion. And, also
> get the image 2-D FFT image.
>
> So there we are dealing with an aggregate of 2^26 8-bit pixel values.
> Surely, the majority of time is spent processing pixels, and not
> dispatching over some polymorphic type...

No. That is actually an excellent example of exactly what I was talking about.

The solution most obvious to me would be something like:

let median_image (images: _ [,] []) =
let n = images.Length
assert(n > 0)
let h, w = images.[0].GetLength 0, images.[0].GetLength 1
Array2D.parallelInit n h w (fun x y ->
kthSmallest (n/2) (fun i -> images.[i].[y, x]))

where the "kthSmallest" and "Array2D.parallelInit" functions are both
polymorphic. The former handles implicit sequences of any comparable type and
the latter handles 2D arrays of any element type. This use of polymorphic
functions would be slow in OCaml: you would have to inline and type
offer. OCaml's representation and handling of ints is inefficient so your
performance will always be dire. Furthermore, OCaml cannot leverage
multicores efficiently because you're returning a non-trivial result that
would have to be marshalled in O(n) time.

In F#, you can mark the "kthSmallest" function "inline" to completely remove
the overhead of the higher-order function and its closure argument. The
parallelInit function uses the "n" to estimate a good initial batching for
the parallel tasks and uses exponential backoff to avoid spending too much
time spawning tasks. The result would be near optimal performance on my 8
core with minimal effort.

OCaml is a hugely productive high-level language but many abstractions do
incur severe performance penalties in OCaml and polymorphism is one of them.
This is highly relevant to technical computing where the ability to write
efficient code with minimal effort is extremely valuable.

--
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

```