Tomas Petricek

Searching for new ways of thinking in programming & working with data

I believe that the most interesting work is not the one solving hard problems, but the one changing how we think about the world. I follow this belief in my work on data science tools, functional programming and F# teaching, in my programming languages research and I try to understand it through philosophy of science.

The Gamma

I'm working on making data-driven storytelling easier, more open and reproducible at the Alan Turing Institute.

Consulting

I'm author of definitive F# books and open-source libraries. I offer my F# training and consulting services as part of fsharpWorks.

Academic

I published papers about theory of context-aware programming languages, type providers, but also philosophy of science.

Tomas Petricek
  • Tomas Petricek
  • Home
  • F# Trainings
  • Talks and books
  • The Gamma
  • Academic

Keep your multi-core CPU busy with F#

The growth of computer CPU speed is slowly being replaced by the growth of number of CPUs (or cores) in the computer at least for the close future. This causes a revolution in the way software is written, because traditional and most widely used way of writing concurrent applications using threads is difficult and brings several serious issues. Some predictions say that within a few years, almost every computer will have about 16 cores, so there is a huge need for programming paradigms or idioms that help developers write concurrent software easily (see also The Free Lunch Is Over [^] written by Herb Sutter).

Functional programming languages (especially pure functional languages) are interesting from this point of view, because the program doesn't have side-effects which makes it very easy to parallelize it (programs in pure functional languages can't have any side-effects by design, in other functional languages like F# the side-effects can be eliminated by following functional programming style).

Finding primes example

Let's say I want to find all prime numbers between 1 million and 1.1 million (this is example of an operation that can be nicely divided between more processors). First we will need function to test whether n is a prime:

// Tests whether n is prime - expects n > 1
let is_prime n =
  // calculate how large divisors should we test..
  let max = int_of_float (Math.Sqrt( float_of_int n ))
  // try to divide n by 2..max (stops when divisor is found)
  not ({ 2 .. max } |> Seq.filter ( fun d -> n%d = 0) |> Seq.nonempty)

To find all primes in the specified range we could use the following code:

let primes = [1000000 .. 1100000] |> List.filter is_prime

This code subsequently executes the is_prime function for all numbers that we want to test, but with multiple CPU cores it would be nice if the function divided the numbers into several parts and executed every part on different thread, so application would take benefit from multiple cores available in the system. The is_prime function doesn't have any side-effects so executing it several times in parallel can't change the result of operation (if the order of primes in the returned list doesn't change).

I wrote a function that does exactly what I described in the previous paragraph. To execute the operation in parallel, you can use the following code (the only difference is that I replaced List module with my ParallelList module):

let primes = [1000000 .. 1100000] |> ParallelList.filter is_prime

On my notebook (with Intel Core Duo processor) the first code (using List.filter) takes about 2,3sec and using ParallelList.filter the operation takes only 1.3sec. The program isn't 2 times faster, because there is some overhead for creating and synchronizing threads, but in this case the speed increase is significant.

Aside from the filter function, the ParallelList module contains also the map function (which does the same thing as the List.map). There is also a function set_thread_count that you can use to configure how many threads should be used when executing parallel operations (the default value is 2).

Performance and future work

The performance of these functions is the key issue. Currently the ParallelList functions work can't be used for small number of repetitions of simple function, because the overhead is larger than the profit from parallel execution. If the operation takes less than 0.01ms and the number of repetitions is less than 1000 the List functions are usually better, but for operations taking longer time the results of ParallelList are better even with smaller number of repetitions. For operation taking about 0.1ms the ParallelList gives better results for more than 200 repetitions and for operation taking more than 1ms the number of repetitions is not very important (ParallelList is better even for 10 repetitions). These are inaccurate results that I got on my notebook, so if you're thinking of using the ParallelList, be sure to do some tests in your scenario! You can see some tests that I did in the demo project in stats.fs source file.

As I said earlier, ParallelList supports only filter and map functions, so implementing more functions would be useful. It would be also useful to provide some alternatives for functions that can't be executed in parallel (like fold_left) that could be used in some situations. I'd also like to implement functions for working with other collection types like Seq (IEnumerable) and array in the future.

I'm interested in your ideas and suggestions, so if you find something that could be improved in the code, or if you have any other idea, let me know!

Downloads

  • Download demo application with source code (14 kB)
  • Download only ParallelList source (2 kB)

Published: Saturday, 24 March 2007, 11:13 PM
Author: Tomas Petricek
Typos: Send me pull request!
Tags: functional, parallel, f#

Contact & about

This site is hosted on GitHub and is generated using F# Formatting and DotLiquid. For more info, see the website source on GitHub.

Please submit issues & corrections on GitHub. Use pull requests for minor corrections only.

  • Twitter: @tomaspetricek
  • GitHub: @tpetricek
  • Email me: tomas@tomasp.net

Blog archives

November 2018 (1),  October 2018 (1),  May 2018 (1),  September 2017 (1),  June 2017 (1),  April 2017 (1),  March 2017 (2),  January 2017 (1),  October 2016 (1),  September 2016 (2),  August 2016 (1),  July 2016 (1),  May 2016 (2),  April 2016 (1),  December 2015 (2),  November 2015 (1),  September 2015 (3),  July 2015 (1),  June 2015 (1),  May 2015 (2),  April 2015 (3),  March 2015 (2),  February 2015 (1),  January 2015 (2),  December 2014 (1),  May 2014 (3),  April 2014 (2),  March 2014 (1),  January 2014 (2),  December 2013 (1),  November 2013 (1),  October 2013 (1),  September 2013 (1),  August 2013 (2),  May 2013 (1),  April 2013 (1),  March 2013 (1),  February 2013 (1),  January 2013 (1),  December 2012 (2),  October 2012 (1),  August 2012 (3),  June 2012 (2),  April 2012 (1),  March 2012 (4),  February 2012 (5),  January 2012 (2),  November 2011 (5),  August 2011 (3),  July 2011 (2),  June 2011 (2),  May 2011 (2),  March 2011 (4),  December 2010 (1),  November 2010 (6),  October 2010 (6),  September 2010 (4),  July 2010 (3),  June 2010 (2),  May 2010 (1),  February 2010 (2),  January 2010 (3),  December 2009 (3),  July 2009 (1),  June 2009 (3),  May 2009 (2),  April 2009 (1),  March 2009 (2),  February 2009 (1),  December 2008 (1),  November 2008 (5),  October 2008 (1),  September 2008 (1),  June 2008 (1),  March 2008 (3),  February 2008 (1),  December 2007 (2),  November 2007 (6),  October 2007 (1),  September 2007 (1),  August 2007 (1),  July 2007 (2),  April 2007 (2),  March 2007 (2),  February 2007 (3),  January 2007 (2),  November 2006 (1),  October 2006 (3),  August 2006 (2),  July 2006 (1),  June 2006 (3),  May 2006 (2),  April 2006 (2),  December 2005 (1),  July 2005 (4),  June 2005 (5),  May 2005 (1),  April 2005 (3),  March 2005 (3),  January 2005 (1),  December 2004 (3),  November 2004 (2), 

License

Unless explicitly mentioned, all articles on this site are licensed under Creative Commons Attribution Share Alike. All source code samples are licensed under the MIT License.

CC License logo