art with code

2008-09-10 range iterators

Ported the parallel is_prime example from Keep your multi-core CPU busy with F# to OCaml, which gave me an excuse to write a Range module for iterating over number ranges. Here the current version of Also retired ($) and ($.) in favour of (|>) and (|>.) to make them more consistent with (@@) and (@.).

Here's the is_prime:

open Prelude

let is_prime n =
let max = int (sqrt (float n)) in
not ( (2 --> max) |> Range.find (fun d -> n mod d = 0) )

let primes = (1000000 --> 1100000) |> Range.pfilter is_prime

let () = puts (showInt (sum primes))

0.39s using Range.filter, 0.24s using Range.pfilter.

Oh right, added the following parallel functions too: pfilter, pfoldl1, pfoldr and pfoldr1. Most of the parallel combinators could be abstracted into splitInto process_count input |> par_map f |> combine, which is what I'll probably do next.

[edit] Did the refactoring, eliminating 70+ lines, here is the new version:

let par_mapReduce ?process_count ~rf ~mf l =
let process_count = process_count |? !global_process_count in
splitInto process_count l |> par_map ~process_count mf |> rf

let pmapReduce rf mf = par_mapReduce ~rf ~mf

let pfoldl r f init = pmapReduce (foldl1 r) (foldl f init)
let pfoldl1 f = pmapReduce (foldl1 f) (foldl1 f)
let pfoldr r f init = pmapReduce (foldr1 r) (foldr f init)
let pfoldr1 f = pmapReduce (foldr1 f) (foldr1 f)

let piter f = pmapReduce ignore (iter f)
let pmap f = pmapReduce concat (map f)
let pfilter f = pmapReduce concat (filter f)

If you have a collection module with splitInto and some of the other functions, you can basically paste this right in. With Range it wasn't quite that easy because par_map returns a list, so the foldls have to use List.foldl for the reduce fold. And I haven't made foldrs for Range, so couldn't add the pfoldrs.

It feels like a promising start towards generalizing the parallel iterators though.
Post a Comment

Blog Archive

About Me

My photo

Built art installations, web sites, graphics libraries, web browsers, mobile apps, desktop apps, media player themes, many nutty prototypes, much bad code, much bad art.

Have freelanced for Verizon, Google, Mozilla, Warner Bros, Sony Pictures, Yahoo!, Microsoft, Valve Software, TDK Electronics.

Ex-Chrome Developer Relations.