Why (in Python) is random.randint so much slower than random.random?

Question

I got curious about the relative speeds of some random integer generating code. I wrote the following to check it out:

from random import random
from random import choice
from random import randint
from math import floor
import time

def main():
    times = 1000000
    
    startTime = time.time()
    for i in range(times):
        randint(0,9)
    print(time.time()-startTime)
    
    startTime = time.time()
    for i in range(times):
        choice([0,1,2,3,4,5,6,7,8,9])
    print(time.time()-startTime)
    
    startTime = time.time()
    for i in range(times):
        floor(10*random())##generates random integers in the same range as randint(0,9)
    print(time.time()-startTime)

main()

The results of one trial of this code were

0.9340872764587402

0.6552846431732178

0.23188304901123047

Even after executing multiplication and math.floor, the final way of generating integers was by far fastest. Messing with the size of the range from which numbers were generated didn't change anything.

So, why is random way faster than randint? and is there any reason why (besides ease of use, readability, and not inviting mistakes) that one would prefer randint to random (e.g., randint produces more random pseudo-random integers)? If floor(x*random()) feels not readable enough but you want faster code, should you go for a specialized routine?

def myrandint(low,high):   ###still about 1.6 longer than the above, but almost 2.5 times faster than random.randint
    return floor((high-low+1)*random())+low  ##returns a random integer between low and high, inclusive. Results may not be what you expect if int(low) != low, etc. But the numpty who writes 'randint(1.9,3.2)' gets what they deserve.
  

Answer 1

Before I answer your question (and don't worry, I do get there), take note of the common programmer's idiom:

Premature optimization is the root of all evil.

While this isn't always the case, don't worry about micro-optimizations unless you need them.

This goes double for Python: if you're writing something where speed is critical, you'll usually want write it in a language that will run faster, like C. You can then write Python bindings for that C code if you want to use Python for the non-critical parts of your application (as is the case with, for example, NumPy).

Instead of focusing on making individual expressions or functions in your code run as fast as possible, focus on algorithms you use and the the overall structure of your code (and on making it readable, but you are already aware of that). Then, when your application starts running slowly, you can profile it to figure out what parts take the most time, and improve only those parts.

The changes will be easier to make to well-structured, readable code and optimizing the actual bottlenecks will generally give a much better speedup-to-time-coding ratio than most micro-optimizations. The time spent wondering which of two expressions runs faster is time you could have spent getting other things done.

As an exception, I'd say learning why one option is faster than the other is sometimes worth the time, because then you can incorporate that more general knowledge into your future programming, letting you make quicker calls without worrying about the details.

But enough about why we shouldn't waste time worrying about speed, let's talk about speed.

---

Taking a look at the source of the random module (for CPython 3.7.4), this line from the end of the opening comment provides a short answer:

* The random() method is implemented in C, executes in a single Python step,
  and is, therefore, threadsafe.

The first statement is the ones that matters the most to us. random is a python binding for a C function, so the complexity of its operation runs at the blinding speed of machine code rather than the relatively slow speed of Python.

randint, on the other hand, is implemented in Python, and suffers a significant speed penalty for it. randint calls randrange, which ensures that the range's bounds (and step size) are integers, that the range isn't empty, and that the step size isn't zero, before calling getrandbits, which is implemented in C.

This alone produces the majority of randint's slowness. However, there is one more variable in play.

Going a little deeper, into the internal function _randbelow, it turns out that the algorithm for getting a random number between 0 and n is very straightforward: it gets the number of bits in n, then generates that many bits at random repeatedly until the resulting number is no greater than n.

On average (across all possible values of n), this has little effect, but comparing the extremes, it is noticeable.

I wrote a function that tests the impact of that loop. Here are the results:

bits   2 ** (n - 1)   (2 ** n) - 1   ratio
  64   1.358526759    1.084741422    1.2523968675
 128   1.43073282     1.02119227     1.4010415688
 256   1.600253063    1.271662798    1.2583941793
 512   1.845024581    1.363168823    1.3534820852
1024   2.371779281    1.620392686    1.4637064839
2048   2.98949864     2.01788896     1.48149809

The first column is the number of bits, the second and third are the average time (in microseconds) to find a random integer with that many bits, over 1 000 000 runs. The last column is the ratio of the second and third columns.

You'll notice that average runtimes for the largest number with a given bit length are larger than for the smallest number with that bit length. This is because of that loop:

When looking for a n-bit number less than the largest n-bit number, a second attempt is needed only if that largest number is generated, which is unlikely except for very small n. But to find a number smaller than the smallest (2ⁿ⁻¹ is a single 1-bit followed by n−1 0-bits), half of the attempts fail.

---

Note: I didn't include tests for bit lengths from 1 to 32 because, upon inspection of the C source for getrandbits, I discovered that it uses a separate, faster, function for those numbers.