Tic-tac-toe in Erlang — parallel processing

This is part of an Erlang tutorial built around a tic-tac-toe program. The program is stuffed into one file, called tic.erl and available here. The source file and this tutorial are organized as follows:

Parallel processing

One of the great things about Erlang is how easy it is to experiment with multi-processing. Or multi-threading. In Erlang there’s not much difference because you don’t work with global variables and mutable data structures. So you don’t have to worry about locking. Most of the time.

In Erlang it’s easy and cheap to start a new “process”. Remember an Erlang process is not an operating system process. An Erlang process is much lighter weight. You can have tens of thousands of them running in parallel on your underpowered laptop and not even notice.

It starts to affect your thinking.

And since we’re looking at a tic-tac-toe sample program with next move calculations and predictions, let’s see how we can take the massively inefficient game space search and make it massively parallel too.

Original implementation

Remember the functions to search the game space chain like this:

The calc_all_outcomes(..) function is just waiting to be parallelized (is that a word?). It is where the search space branches. With comments and asserts stripped out the Erlang code looks like this.

calc_all_outcomes( Board, Xo, Countdown, Outcome_start ) ->
  [ given_move_predict_outcome(
        Board, Xo, Pos, Countdown, Outcome_start)
    || Pos <- lists:seq( 1, 9) ].

Or you might find it easier to read if expressed with map instead of as a list comprehension. I like map myself, I'm used it so long it's like an old friend. But the two forms are equivalent.

calc_all_outcomes( Board, Xo, Countdown, Outcome_start ) ->
  lists:map(
    fun( Pos ) ->
      given_move_predict_outcome(
        Board, Xo, Pos, Countdown, Outcome_start)
    end,
    lists:seq( 1, 9))

Parallel implementation

We can implement this as a function that starts up 9 processes, and then waits for them all to finish and send back results. This is a pretty standard transformative pattern: re-interpreting a map as a scatter to start the processes, and then a gather to bring all the results back home.

calc_all_outcomes( Board, Xo, Countdown, Outcome_start ) ->
  Pid_parent = self( ),

  Scatter_fn =
    fun( Pos ) ->
      spawn(
        fun( ) ->
          % Send results back to parent
          Pid_parent !
            { Pos,
              given_move_predict_outcome(
                Board, Xo, Pos, Countdown, Outcome_start)
            }
        end)
    end,

  Gather_fn =
    fun( Pos ) ->
      receive { Pos, Outcome_predicted } ->
        Outcome_predicted
      end
    end,

  % Start 9 processes
  lists:foreach( Scatter_fn, lists:seq( 1, 9)),

  % Gather and order 9 results
  lists:map( Gather_fn, lists:seq( 1, 9))

You can also express this as nested list comprehensions. The code is way cool even if it's a little more difficult to understand.

calc_all_outcomes( Board, Xo, Countdown, Outcome_start ) ->
  Pid_parent = self( ),
  [ receive {Pos, Outcome_predicted} ->
      Outcome_predicted
    end
    || Pos <-
       [ Pos
         || Pos <- lists:seq( 1, 9),
            is_pid(
              spawn(
                fun( ) ->
                  Pid_parent !
                    { Pos,
                      given_move_predict_outcome(
                        Board, Xo, Pos,
                        Countdown, Outcome_start)
                    }
                end)) ]]

Not-so parallel implementation

The thing to remember is to get all the processes going before listening for any return messages. When I first implemented this function I forgot that and came up with this wrong implementation.

% Incorrect implementation:
calc_all_outcomes( Board, Xo, Countdown, Outcome_start ) ->
  Pid_parent = self( ),
  lists:map(
    fun( Pos ) ->
      spawn(
        fun( ) ->
          Pid_parent !
            given_move_predict_outcome(
              Board, Xo, Pos, Countdown, Outcome_start)
        end),
      receive Outcome_predicted -> Outcome_predicted end
    end,
    lists:seq( 1, 9))

This spawns a process, and then waits for its results before spawing the next one. This actually works fine (and is barely slower than the original non-parallel implementation), but it never has more than 9 processes alive (and one running) at a time.

Analysis

So, how did this work? Wellllll, in game space search I mention that given_move_predict_outcome(..) is evaluated 2,653,002 times if you fully predict all outcomes for an empty board. Which means the parallel code above will spawn 2,653,002 Erlang processes, all of which can potentially be running at the same time. Which is a little breathtaking.

And it's a little too much. Erlang on my system can't do it. (It has no problem with the "wrong" implementation given above though. That also spawns 2,653,002 processes, but never more than 9 at a time.)

But the code in tic.erl never predicts an empty board. It only predicts after at least one mark is down. Which means it would never try to spawn more than 308,817 processes.

And, not surprisingly, that's still too many. Erlang chokes.

But you CAN run the above code with two marks (an X and an O) on the tic-tac-toe board. In that case Erlang only has to spawn 30 or 40 thousand processes, all running at the same time. That's still pretty impressive. On my setup I max out at about 80,000 simultaneous processes.

Final thoughts

Working with something like Erlang, where it's easy to spawn thousands of processes, influences how you think and how you experiment. It let's you ask how you can solve a problem using a bunch of communicating agents, or using a fabric of processes interconnected in a specific hardware architecture. It let's you test ideas and gain a clearer understanding of how a parallel solution might work. If I were designing a parallel system that I eventually going to implement in C and MPI/OpenMP/CUDA, I'd consider starting with prototyping and concept checking on an Erlang testbed. It'd help catch mistakes and highlight problems early on.

Comments

37 Responses to “Tic-tac-toe in Erlang — parallel processing”

  1. Nikolas Bowe on March 16th, 2009 8:02 am

    Hi. This is an interesting series on tic-tac-toe in Erlang. Thanks.

    Whats the performance difference on your machine between the parallel version and the non parallel one for a board with 2 marks?

    In this example processes spend a lot of the time waiting, so I think you might be better off spawning fewer processes and making them do more work. Maybe only spawn processes for the 9 initial moves. Its not particularly intelligent and doesnt scale past 9 cores but its dead easy to implement.

    Note: You can increase the process limit by using the +P command line switch to erl. The default is 32768 processes.

  2. Neal on March 17th, 2009 11:21 am

    Thanks. I didn’t know about +P. That’ll be interesting to play with.

    Hmm, and I must not have 80,000 simultaneous process running, like I guessed. Maybe 30,000.

    And yes, these processes spend almost all their lives just waiting for cycles. I’m running this on a somewhat underpowered machine with only 2 cores and 1G memory.

    The massively parallel runs were a little slower (about 25%) than the serial runs. So spawning all those processes, although not terribly expensive, is still enough to use up any gains from having 2 cores.

    And I’m not even sure I’m using 2 cores. When I start the Erlang shell it says:

    Erlang (BEAM) emulator version 5.6.5 [smp:2] [async-threads:0]

    Does this mean everything is running in a single operating-system thread? Sounds like it.

  3. http://criminalbackgroundchecked.com/ on July 4th, 2012 12:18 pm

    There have been some interesting points in time in
    this article on that the other hand I dont know if I see they all center to heart.
    There is some validity in spite of this I will take hold
    opinion until I look into it further. First-rate article
    , thanks and we want more! Added to FeedBurner because well

  4. scholarships for single mothers on July 8th, 2012 3:40 am

    Abnormal this put up is totaly unrelated to what I used
    to be looking google for, but it was indexed on the first
    page. I guess your doing something proper if Google likes you enough to place you at the first page of
    an non related lookup.

  5. scholarships for college students|scholarships for college students in texas|2011 scholarships for college students|scholarships for college students in california|scholarships for college students 2011|easy scholarships for college students|grants and se on July 8th, 2012 2:19 pm

    I really along the lines of your site. first-rate colorations & motif.
    Would people design and style this fabulous website your self or would you
    actually hire an attorney to acheive it available for
    you Plz answer while I!m trying to style my own website and would select to find out wherever ough acquired that the
    following coming out of. thank you

  6. free grants for single mothers on July 8th, 2012 3:34 pm

    drug addiction is usually a menace to the society, it destroys
    lives and it destroys the community

  7. daycare assistance for single mothers on July 8th, 2012 4:25 pm

    I such as what you guys are up also. Such intelligent work and reporting!
    Carry on the first-class works guys I have incorporated you guys to my blogroll.
    I think itll improve the value of my web site

  8. cell phone lookup on July 8th, 2012 4:45 pm

    Wow! that entry was basically pretty handy quite a ton of thanks.
    “Quoting that the act of repeating erroneously that the words of an
    alternative. by Ambrose Gwinett Bierce.

  9. scholarships and grants for single mothers on July 8th, 2012 5:02 pm

    Abnormal this put up is totaly unrelated to what I used
    to be looking google for, however it was indexed on the first page.
    I guess your doing something proper if Google likes you enough to
    place you at the first page of a non related search.

  10. cell phone lookup on July 10th, 2012 4:21 am

    It’s astounding, searching within that the time and work you place into your weblog and detailed specifics you furnish. Ill bookmark your web site and pay a visit to it weekly for the new posts.

  11. college grants for women on July 11th, 2012 4:33 am

    You made some decent points there. I looked on
    the net for the issue and found most people will go in addition to with your
    website.

  12. reverse number lookup on July 16th, 2012 1:03 pm

    I feel that is one of the such a lot vital info for me.
    And i am glad studying your article. But wanna statement on some common things, The
    site taste is ideal, the articles is in reality great : D. Just right process,
    cheers

  13. http://www.prlog.org/11161236-cell-phone-number-lookup-free-can-you-really-get-one-for-free.html on July 16th, 2012 2:11 pm

    I was recommended this web site by my cousin. Im now not positive whether
    this publish is written by him as no one else understand such targeted approximately my difficulty.
    You are wonderful! Thank you!

  14. http://ezinearticles.com/?Free-Reverse-Phone-Lookup---Answer-To-The-Myth-About-Free-Cell-Phone-Number-Lookups&id=5986059 on July 16th, 2012 2:28 pm

    I have been checking your blog site for any even though now,
    would seem like everyday I study some thing
    new Thanks

  15. http://www.prlog.org/11734648-criminal-background-check-public-records.html on July 16th, 2012 3:27 pm

    Right now it appears just like Drupal is that the preferred blogging platform available
    right now. out of what Ive read Is that what youre using on your blog

  16. http://www.prlog.org/11674605-reverse-phone-lookup-finders.html on July 16th, 2012 3:34 pm

    I got this site from my pal who shared with me on the topic
    of this site and at the moment this time I am browsing this web page and
    reading very informative posts at this place.

  17. reverse phone lookup on July 16th, 2012 4:58 pm

    Whoah this weblog is wonderful i love studying your articles.
    Stay up that the great work! You realize, quite a
    large amount of individuals have been seeking round for this info, you could help
    them vastly.

  18. phone number on July 16th, 2012 8:24 pm

    This is that the best blog Ive ever seen in my life!
    I actually appreciate you taking the time out of your busy day to share your this with everyone.

  19. http://www.prlog.org/11734625-reverse-cell-phone-directory-finds-anyone-with-telephone-number.html on July 16th, 2012 8:24 pm

    I visited several web sites but the audio quality for audio
    songs present at this site is truly wonderful.

  20. http://officialreversephonelookup.com/ on July 16th, 2012 9:13 pm

    I am sure this paragraph has touched all the internet people, its really really good paragraph on building up new webpage.

  21. http://www.prlog.org/11684341-reverse-cell-phone-lookup-number.html on July 16th, 2012 10:29 pm

    I pay a quick visit each day a few web sites and sites to read articles or reviews, except this web site
    provides feature based posts.

  22. reverse phone on July 17th, 2012 2:10 am

    Congratulations on having one of that the most sophisticated sites
    Ive come across in some time! Its just incredible how much you possibly can
    take away out of anything merely as of how visually beautiful it is.
    Youve put collectively a great blog space great graphics,
    videos, layout. This is unquestionably a mustsee blog!

  23. http://www.prlog.org/11734633-free-people-search-finder-directory.html on July 17th, 2012 2:37 am

    I believe that may be a captivating element, it made me think a
    bit. Thanks for sparking my pondering cap. Now
    and again I figure out so much in the rut that I merely
    really feel like a record.

  24. http://ezinearticles.com/?Phone-Number-Search---Stopping-a-Cheater-the-Easy-Way&id=5909547 on July 17th, 2012 2:39 am

    i love to listen on audiobooks while travelling on a bus, i could discover a ton out of
    it while travelling,

  25. reverse phone number lookup on July 17th, 2012 2:41 am

    He stares them down until he gets that the information he wants

  26. reverse phone lookup on July 18th, 2012 1:42 am

    It is laborious to find knowledgeable folks
    on this matter, in spite of this you sound for instance you realize
    what youre speaking about! Thanks

  27. http://www.prlog.org/11261550-phone-number-lookup-catch-cheater-quickly.html on July 25th, 2012 2:02 am

    Friday Night Lights is usually a great tv series,
    i love the game and i love the story

  28. make money online on July 27th, 2012 6:39 am

    you employ a excellent weblog here! do you want to develop
    invite posts on my weblog

  29. http://101watchmoviesonline.com/ on July 31st, 2012 8:08 am

    Fine blog here! after reading, i decide to buy a
    sleeping bag ASAP

  30. http://officialreversephonelookup.com/ on August 1st, 2012 5:26 am

    getting a masters degree is of course necessary whenever you want a wage increase and improvement in your career.

    ,

  31. Karri on August 13th, 2012 12:49 pm

    This one page has a tendency to redeem much page views.
    Exactly how do you market it

  32. Kandace on August 13th, 2012 2:48 pm

    Hello! I just now would just like to give a huge thumbs up for
    that the wonderful info you might have here on this post.
    I am returning to your website for additional soon.

  33. Anonymous on August 13th, 2012 3:07 pm

    I wanted to put you one very small word just to say thank you over again over that the spectacular
    ideas youve provided at this time. It was certainly
    surprisingly openhanded of people such as you to provide freely all quite a large amount of individuals wouldve sold for an ebook to help with making some buck for themselves, specifically
    seeing you to might have tried it in case you wanted.

    These concepts because well acted to be a great way to
    realize that most people have similar dream that the same because my very own to figure out somewhat more in regard to
    this matter. I am sure there have been some more enjoyable opportunities ahead for individuals
    who read carefully your blog post.

  34. best reverse cell phone lookup on August 20th, 2012 12:54 am

    Well im from Ireland, and throughout Ireland bono and that
    the lads have been unquestionably liked and also could
    certainly not do really much incorrect, we all love them.

  35. reverse phone lookup on August 23rd, 2012 9:34 pm

    Thanks a ton for sharing this with all of
    us you actually identify what you have been talking about!
    Bookmarked. Please also visit my website =. We could have
    a link exchange agreement between us!

  36. Tic-tac-toe in Erlang — full game space : Code Obscurata on August 24th, 2012 6:21 pm

    […] Parallel processing […]

  37. Tic-tac-toe in Erlang — top-level loop : Code Obscurata on August 24th, 2012 6:23 pm

    […] Parallel processing […]