Re: [Caml-list] HLVM stuff

[Jon Harrop <jon@ffconsultancy.com>]

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 
specialize those functions by hand to get the best performance OCaml has to 
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