From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.2 required=5.0 tests=AWL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by yquem.inria.fr (Postfix) with ESMTP id 6C983BC37 for ; Sun, 27 Sep 2009 21:25:14 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AsIDAK5Yv0rUnwckjmdsb2JhbACCIJhjAQEBAQkLCAkRBrZzhB4F X-IronPort-AV: E=Sophos;i="4.44,461,1249250400"; d="scan'208";a="47386310" Received: from relay.ptn-ipout02.plus.net ([212.159.7.36]) by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 27 Sep 2009 21:25:13 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AscIAHRYv0rUnw6U/2dsb2JhbACCINAYhB4F Received: from fhw-relay07.plus.net ([212.159.14.148]) by relay.ptn-ipout02.plus.net with ESMTP; 27 Sep 2009 20:25:13 +0100 Received: from [87.114.87.187] (helo=leper.local) by fhw-relay07.plus.net with esmtp (Exim) id 1MrzMu-0005UC-Pp for caml-list@yquem.inria.fr; Sun, 27 Sep 2009 20:25:12 +0100 From: Jon Harrop Organization: Flying Frog Consultancy Ltd. To: caml-list@yquem.inria.fr Subject: Re: [Caml-list] HLVM stuff Date: Sun, 27 Sep 2009 20:25:39 +0100 User-Agent: KMail/1.9.9 References: In-Reply-To: MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200909272025.39995.jon@ffconsultancy.com> X-Plusnet-Relay: 789ff1f69a12878e421c2ba31684f4d5 X-Spam: no; 0.00; dispatching:01 arrays:01 ocaml:01 ocaml:01 ocaml's:01 non-trivial:01 higher-order:01 high-level:01 polymorphism:01 2009:98 infrared:98 penalties:98 frog:98 polymorphic:01 polymorphic:01 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