Rand and Goroutines

December 22, 2017Damian Czaja

Hello guys!

At first, I would like to welcome you here! I decided to create this blog to share my thoughts, solutions and all the things I consider interesting. It will be mainly about computer science, programming, computer security, but I will see how it evolves. 🙂

I currently doing M.Sc degree on Wroclaw University of Science and Technology, at the Department of Computer Science. In this semester I’m having labs on the course Probabilistic Methods of Algorithms. Long story short – we are doing some simulations to analyze several statistics of algorithms, like quick sort, etc. After I attended William Kennedy’s talks on CodeDive conference I got fascinated by GoLang and I decided to do a few simulations in this language.

The task was:

Simulate the process of throwing n balls to n bins. Analyze the numbers of balls in the bin with the highest number of balls (average and concentration). Compare it with theoretical calculations

So I launched VSCode and started coding. My first approach was to write a single goroutine program, which solves this task. Number of bins/balls for which I did the simulation ranged from 50 to 1000 with step 50. For each number I repeated the experiment 100000 times to calculate some statistics. I launched it and…

Hurray! It works and the results are good. The average (expected value) is O(log(n)). The Chebyshev’s inequality for k = 2 tells, that at minimum 75% of experiments should be between those bound lines. It’s +/- 1 from the expected value, so it’s pretty well concentrated. Those two other lines show the bounds, where the probability, that the max load will be higher/lower is negligible low. Works also.

OK, but let’s switch to something more interesting… How long did the simulation run?

Nice, but hey, I’ve got here a i5-4460 with 4 cores. It can be better! Let’s use goroutines!

 Doesn’t it look great? Just add a few lines and you have all your cores working. But after I’ve run it, I was a bit surprised…

4 times slower?! I was expecting the otherway… and I had no idea what’s wrong. OK, no worries, that looks like a case for the profiler. Let’s try it out. I added this to main

This steps allowed to generate a graph, which shows, which calls are most time consuming. A quick look shows the main problem: mutex in rand.Int63. Ahh, right, there’s a linear congruential generator, so the next random value depends on the previous one. Two goroutines cannot use it at one time. But the overhead in locking and unlocking the mutex is really huge…

OK, then let’s create a seperate generator for each goroutine, so they don’t have to compete for it.

It’s 3 times faster than the single Goroutine version! If we now look at the call graph, we can see that above 50% of the time the CPU spends at generating random numbers.

Things to remember:

  1. Don’t use the global random generator in goroutines. Create a seperate generator for each
  2. If you have performance issues but don’t know why – use Golang’s pprof

Comments (3)

  • Kaveh Shahbazian

    December 23, 2017 at 8:52 am

    Nice post! A thing about rand package is, it generate the same sequence, with the same seed. In all programming languages the default rand works this way. This will allow for generating pseudo-random series which can be used (as an example) for tests.

    For a true random number, one should use the cryptographic version.

    In this code the same seed is used for all random generators which results the same pseudo-random series of numbers (can be checked): https://play.golang.org/p/bndGv9LhPWv

    1. Damian Czaja

      December 24, 2017 at 3:41 pm

      Sure, in crypto math/rand shouldn’t be used.

      For this simulation I needed only some generator, which output has uniform distribution. I could get the seed for math/rand generators from crypto/rand, but getting it from time.Now() and incrementing worked here and the simulation results were OK.

      BTW. How to predict numbers from default rand: https://www.mathstat.dal.ca/~selinger/random/

  • Jan Zac

    January 19, 2018 at 3:01 pm

    Hello ,

    I saw your tweets and thought I will check your website. Have to say it looks very good!
    I’m also interested in this topic and have recently started my journey as young entrepreneur.

    I’m also looking for the ways on how to promote my website. I have tried AdSense and Facebok Ads, however it is getting very expensive. Was thinking about starting using analytics. Do you recommend it?
    Can you recommend something what works best for you?

    Would appreciate, if you can have a quick look at my website and give me an advice what I should improve: http://janzac.com/
    (Recently I have added a new page about FutureNet and the way how users can make money on this social networking portal.)

    I have subscribed to your newsletter. 🙂

    Hope to hear from you soon.

    Maybe I will add link to your website on my website and you will add link to my website on your website? It will improve SEO of our websites, right? What do you think?

    Jan Zac

Leave a comment

Your email address will not be published. Required fields are marked *

Next Post