CODEWITHSUNDEEP
pythonperformancemultiprocessingpython-multiprocessing
Drise
Drise

Reputation: 4388

Multi-thread the Birthday Paradox

I've been playing with the Birthday Problem, and came up with the code below. The problem is that, even for a small 1 million runs, it can take up quite some time. Since tick() is the most expensive function, and is well isolated (I think), how would I multi-thread the while loop section?

Coming from a background, I would probably be using #pragma omp parallel, but I don't know how to do that in , especially with the GIL issue

Are there any other ways I can increase the performance?

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
  1000000   10.320    0.000   21.736    0.000 sim.py:29(tick)
 24617823    6.931    0.000    9.209    0.000 sim.py:8(getday)
 24617823    2.278    0.000    2.278    0.000 {method 'randint' of 'mtrand.RandomState' objects}
 23617823    2.115    0.000    2.115    0.000 {method 'add' of 'set' objects}
        1    0.983    0.983   22.967   22.967 sim.py:12(main)
   999999    0.105    0.000    0.105    0.000 {method 'append' of 'list' objects}

import numpy as np

def getday():
    return np.random.randint(1, 366)

def main():
    # Multithread this section
    popSize = [tick()]
    while len(popSize) < 1000000:
        popSize.append(tick())

    print "Iterations %d" % len(popSize)
    print "Average pop size %d" % (sum(popSize) / len(popSize))
    print "Min pop size %d" % min(popSize)
    print "Max pop size %d" % max(popSize)

def tick():
    days = set()
    day = getday()
    while day not in days:
        days.add(day)
        day = getday()

    return len(days)

if __name__ == '__main__':
    main()

Upvotes: 0

Views: 114

Answers (1)

bivouac0
bivouac0

Reputation: 2560

Try this code where the if clause under main() selects original or mp versions...

import numpy as np
import multiprocessing as mp

def getday():
    return np.random.randint(1, 366)

def main():
    size = 1000000
    if 0:   # original version
        popSize = [tick()]
        while len(popSize) < size:
            popSize.append(tick())
    else:   # multithreaded
        pool = mp.Pool()
        popSize = pool.map(tick, range(size))

    print "Iterations %d" % len(popSize)
    print "Average pop size %d" % (sum(popSize) / len(popSize))
    print "Min pop size %d" % min(popSize)
    print "Max pop size %d" % max(popSize)

def tick(dummy=None):
    days = set()
    day = getday()
    while day not in days:
        days.add(day)
        day = getday()
    return len(days)

if __name__ == '__main__':
    main()

On my 14 core machine run-time goes from 21 seconds to 1.75 seconds which is fairly close to the theoretical max.

There's a few different parallel methods in multiprocessing that you can try. See https://docs.python.org/2/library/multiprocessing.html 16.6.2.9. Process Pools

Note that the optional chunksize parameter can greatly impact performance. With map it doesn't seem to be required for a speedup but if you use imap you need to set chunksize to something like 100 to see the speedup.

Upvotes: 2

Related Questions