random.randint() slow, esp in Python 3

[Chris Angelico]

The standard library function random.randint() seems to be quite slow
compared to random.random(), and worse in Python 3 than Python 2
(specifically that's 3.3a0 latest from Mercurial, and 2.6.6 that came
default on my Ubuntu install).

My test involves building a list of one million random integers
between 0 and ten million (for tinkering with sorting algorithms),
using a list comprehension:

import random
import time
sz=1000000
start=time.time()
a=[random.randint(0,sz*10-1) for i in range(sz)]
print("Time taken: ",time.time()-start)

The code works fine in either version of Python (although the display
looks a bit odd in Py2). But on my test system, it takes about 5
seconds to run in Py2, and about 10 seconds for Py3. (The obvious
optimization of breaking sz*10-1 out and storing it in a variable
improves both times, but leaves the dramatic difference.)

Replacing randint with random():
a=[int(random.random()*top) for i in range(sz)]
cuts the times down to about 1.5 secs for Py2, and 1.8 secs for Py3.

I suspect that the version difference is (at least in part) due to the
merging of the 'int' and 'long' types in Py3. This is supported
experimentally by rerunning the second list comp but using int() in
place of long() - the time increases to about 1.7-1.8 secs, matching
Py3.

But this still doesn't explain why randint() is so much slower. In
theory, randint() should be doing basically the same thing that I've
done here (multiply by the top value, truncate the decimal), only it's
in C instead of Python - if anything, it should be faster than doing
it manually, not slower.

A minor point of curiosity, nothing more... but, I think, a fascinating one.

ChrisA

 

[Steven D'Aprano]

The standard library function random.randint() seems to be quite slow
compared to random.random(), and worse in Python 3 than Python 2 [...]
But this still doesn't explain why randint() is so much slower. In
theory, randint() should be doing basically the same thing that I've
done here (multiply by the top value, truncate the decimal), only it's
in C instead of Python - if anything, it should be faster than doing
it manually, not slower.

What makes you think it's in C? I don't have Python 3.3a, but in 3.2 the
random module is mostly Python. There is an import of _random, which
presumably is in C, but it doesn't have a randint method:
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
AttributeError: type object '_random.Random' has no attribute 'randint'


I'm not seeing any significant difference in speed between 2.6 and 3.2:

[steve@sylar ~]$ python2.6 -m timeit -s "from random import
randint" "randint(0, 1000000)"
100000 loops, best of 3: 4.29 usec per loop

[steve@sylar ~]$ python3.2 -m timeit -s "from random import
randint" "randint(0, 1000000)"
100000 loops, best of 3: 4.98 usec per loop


(The times are quite variable: the above are the best of three attempts.)

 

[Chris Angelico]

What makes you think it's in C? I don't have Python 3.3a, but in 3.2 the
random module is mostly Python. There is an import of _random, which
presumably is in C, but it doesn't have a randint method:

True. It seems to be defined in cpython/lib/random.py as a reference
to randrange, which does a pile of error checking and calls
_randbelow... which does a whole lot of work as well as calling
random(). Guess I should have checked the code before asking!

There's probably good reasons for using randint(), but if you just
want a pile of more-or-less random integers, int(random.random()*top)
is the best option.

I'm not seeing any significant difference in speed between 2.6 and 3.2:

[steve@sylar ~]$ python2.6 -m timeit -s "from random import
randint" "randint(0, 1000000)"
100000 loops, best of 3: 4.29 usec per loop

[steve@sylar ~]$ python3.2 -m timeit -s "from random import
randint" "randint(0, 1000000)"
100000 loops, best of 3: 4.98 usec per loop

That might be getting lost in the noise. Try the list comp that I had
above and see if you can see a difference - or anything else that
calls randint that many times.

Performance-testing with a heapsort (and by the way, it's
_ridiculously_ slower implementing it in Python instead of just
calling a.sort(), but we all knew that already!) shows a similar
difference in performance. As far as I know, everything's identical
between the two (I use // division so there's no floating point
getting in the way, for instance), but what takes 90 seconds on Py2
takes 150 seconds on Py3. As with the randint test, I switched int()
to long() to test Py2, and that slowed it down a little, but still far
far below the Py3 time.

I've pasted the code I'm using here: http://pastebin.com/eQPHQhD0

Where's the dramatic performance difference? Or doesn't it matter,
since anything involving this sort of operation needs to be done in C
anyway?

ChrisA

 

[Steven D'Aprano]

True. It seems to be defined in cpython/lib/random.py as a reference
to randrange, which does a pile of error checking and calls
_randbelow... which does a whole lot of work as well as calling
random(). Guess I should have checked the code before asking!

There's probably good reasons for using randint(),

If you want unbiased, random (or at least pseudo-random) integers chosen
from an uniform distribution with proper error checking, you should use
randint or randrange.

but if you just
want a pile of more-or-less random integers, int(random.random()*top)
is the best option.

"I only need random-ish ints, but I need 'em yesterday!!!"

If you want biased, not-quite-uniformly distributed integers with no error
checking, then the above will save you a few nanoseconds per call. So if
your application needs a million such ints, you might save a full five
seconds or so. Sounds like premature optimization to me, but what do I
know? If you have an application where the quality of randomness is
unimportant and generating random ints is a genuine performance bottleneck,
then go right ahead.

I'm not seeing any significant difference in speed between 2.6 and 3.2:

[steve@sylar ~]$ python2.6 -m timeit -s "from random import
randint" "randint(0, 1000000)"
100000 loops, best of 3: 4.29 usec per loop

[steve@sylar ~]$ python3.2 -m timeit -s "from random import
randint" "randint(0, 1000000)"
100000 loops, best of 3: 4.98 usec per loop

That might be getting lost in the noise. Try the list comp that I had
above and see if you can see a difference - or anything else that
calls randint that many times.

If you want to measure the speed of randint, you should measure the speed of
randint. That's what the timeit call does: it calls randint 100000 times.

You can't measure the speed of:

[random.randint(0,sz*10-1) for i in range(sz)]

and draw conclusions about randint alone. Roughly speaking, you are
measuring the time taken to:

lookup range
lookup sz, twice
call range, possibly generating a massive list
iterate over the list/range object
lookup random
lookup random.randint
multiply sz by 10 and subtract 1
build a list of the results, repeatedly resizing it as you go

(in no particular order)

There is MUCH more noise in your suggestion, not my version. But for what
it's worth, I get these results:

[steve@sylar ~]$ python3.2 -m timeit -s "import random" -s "sz =
1000000" "[random.randint(0,sz*10-1) for i in range(sz)]"
10 loops, best of 3: 6.09 sec per loop
[steve@sylar ~]$ python2.6 -m timeit -s "import random" -s "sz =
1000000" "[random.randint(0,sz*10-1) for i in range(sz)]"
10 loops, best of 3: 4.67 sec per loop

So Python 3.2 is about 30% slower for the whole mess. (I would, however,
give little confidence in those results: at 4-6 seconds per loop, I expect
that OS-level noise will be significant.)

For what (little) it's worth, it seems that Python 3.2 should be a bit
faster than 2.6, at least if you consider the Pystone benchmark to mean
anything.

http://www.levigross.com/post/2340736877/pystone-benchmark-on-2-6-2-7-3-2

Performance-testing with a heapsort (and by the way, it's
_ridiculously_ slower implementing it in Python instead of just
calling a.sort(), but we all knew that already!) shows a similar
difference in performance.

You do know that Python's heap implementation is written in C? Don't be
fooled by the heapq module being in Python. About 2/3rds of the way down,
there's a sneaky little trick:

# If available, use C implementation
try:
from _heapq import *
except ImportError:
pass

 

[Ian Kelly]

If you want unbiased, random (or at least pseudo-random) integers chosen
from an uniform distribution with proper error checking, you should use
randint or randrange.



"I only need random-ish ints, but I need 'em yesterday!!!"

If you want biased, not-quite-uniformly distributed integers with no error
checking, then the above will save you a few nanoseconds per call. So if
your application needs a million such ints, you might save a full five
seconds or so. Sounds like premature optimization to me, but what do I
know? If you have an application where the quality of randomness is
unimportant and generating random ints is a genuine performance bottleneck,
then go right ahead.

Peeking under the hood, after all the error-checking and extra
features, randrange basically just does int(random.random() * top).
Any bias present in the latter will also be present in the former.

Cheers,
Ian

 

[Chris Angelico]

Chris Angelico wrote:

If you want unbiased, random (or at least pseudo-random) integers chosen
from an uniform distribution with proper error checking, you should use
randint or randrange.

"I only need random-ish ints, but I need 'em yesterday!!!"

All I want is some data to sort, so that I can verify that my
implementation is doing the same thing in every language that I write
it in. Doesn't have to be casino-level purity of randomness.

You can't measure the speed of:

[random.randint(0,sz*10-1) for i in range(sz)]

and draw conclusions about randint alone.

Sure, but by comparing the two lines of code (one with randint and one
with random()), the other aspects can be cancelled out.

For what (little) it's worth, it seems that Python 3.2 should be a bit
faster than 2.6, at least if you consider the Pystone benchmark to mean
anything.

http://www.levigross.com/post/2340736877/pystone-benchmark-on-2-6-2-7-3-2

That's what I would normally expect, that the new version outperforms
the old - regardless of the program and the context. Exceptions need
justification (as in the case of int/long vs just int - Py2 often
outperforms Py3 when all the numbers fit inside machine int).

You do know that Python's heap implementation is written in C? Don't be
fooled by the heapq module being in Python.

I didn't know, but it doesn't surprise me. But my purpose wasn't to
sort the integers, it was to play with a particular hand-rolled
implementation of a heap sort in multiple languages and make sure it
was producing consistent results.

ChrisA

 

[Mark Dickinson]

Peeking under the hood, after all the error-checking and extra
features, randrange basically just does int(random.random() * top).
Any bias present in the latter will also be present in the former.

Cheers,
Ian

In Python 2.x that's true, and indeed randrange has some fairly bad
behaviour for large arguments ( see http://bugs.python.org/issue9025
). In Python 3.2 and up, randrange is more careful: it doesn't
introduce any extra bias beyond that already present in the random
source (Mersenne Twister). If you look at the source, you'll see that
Python 2.x only calls _getrandbits for large arguments, while Python
3.2+ calls _getrandbits for *every* invocation of randrange. (All
assuming that we're using the default MT random number generator.)
This may well explain the difference in timings observed by the OP.