Using getrandbits() in uuid.uuid4() is faster and more readable

[mattchaput]

BPO	12986
Nosy	@rhettinger, @terryjreedy, @pitrou, @vstinner, @tiran, @serhiy-storchaka
Files	fastuuid4.patch: A patch to use random.getrandbits() instead of os.urandom in uuid.uuid4()

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2012-10-06.23:00:22.711>
created_at = <Date 2011-09-15.16:30:16.906>
labels = ['library', 'performance']
title = 'Using getrandbits() in uuid.uuid4() is faster and more readable'
updated_at = <Date 2012-10-06.23:00:22.710>
user = 'https://bugs.python.org/mattchaput'

bugs.python.org fields:

activity = <Date 2012-10-06.23:00:22.710>
actor = 'pitrou'
assignee = 'none'
closed = True
closed_date = <Date 2012-10-06.23:00:22.711>
closer = 'pitrou'
components = ['Library (Lib)']
creation = <Date 2011-09-15.16:30:16.906>
creator = 'mattchaput'
dependencies = []
files = ['23163']
hgrepos = []
issue_num = 12986
keywords = ['patch']
message_count = 8.0
messages = ['144087', '144156', '144159', '157744', '157755', '172216', '172259', '172260']
nosy_count = 7.0
nosy_names = ['rhettinger', 'terry.reedy', 'pitrou', 'vstinner', 'christian.heimes', 'mattchaput', 'serhiy.storchaka']
pr_nums = []
priority = 'normal'
resolution = 'rejected'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue12986'
versions = ['Python 3.3']

[mattchaput]

Currently the 'uuid' module uses os.urandom (in the absence of a system UUID generation function) to generate random UUIDs in the uuid.uudi4() function. This patch changes the implementation of uuid4() to use random.getrandbits() as the source of randomness instead, for the following reasons:

• In my quick tests, using getrandbits() is much faster on Windows and Linux. Some applications do need to generate UUIDs quickly.

  >>> setup = "import uuid, os, random"
  >>> ur = "uuid.UUID(bytes=os.urandom(16), version=4)"
  >>> grb = "uuid.UUID(int=random.getrandbits(128), version=4)"
  >>> # Windows --------

  >>> timeit.Timer(ur, setup).timeit()
  22.861042160383903
  >>> timeit.Timer(grb, setup).timeit()
  3.8689128309085135
  >>> # Linux --------
  >>> timeit.Timer(ur, setup).timeit()
  29.32686185836792
  >> timeit.Timer(grb, setup).timeit()
  3.7429409027099609

• The patched code is cleaner. It avoids the try...finally required by the possibly unavailable os.urandom function, and the fallback to generating random bytes.

[terryjreedy]

You could help this along by both running Lib.test.test_uuid with your patch applied and reporting that it passes.

Raymond, I added you because this is about changing random functions.

Side note: This code in test_uuid.test_uuid4()

        uuids = {}
        for u in [uuid.uuid4() for i in range(1000)]:
            uuids[u] = 1
        equal(len(uuids.keys()), 1000)

could be updated to use sets rather than a fake dict:

        uuids = set()
        for u in [uuid.uuid4() for i in range(1000)]:
            uuids.add(u)
        equal(len(uuids), 1000)

[mattchaput]

Passed all tests OK.

[serhiy-storchaka]

    uuids = set()
    for u in [uuid.uuid4() for i in range(1000)]:
        uuids.add(u)

        uuids = {uuid.uuid4() for i in range(1000)}

However, I'm not sure of the legitimacy of replacement suitable for cryptographic use os.urandom on fast pseudo-random random.getrandbits. Especially for applications that need to generate a lot of uuids.

[pitrou]

However, I'm not sure of the legitimacy of replacement suitable for
cryptographic use os.urandom on fast pseudo-random
random.getrandbits. Especially for applications that need to generate
a lot of uuids.

Agreed. urandom() is supposed to incorporate "real" random, while getrandbits() uses a PRNG.
Also, as the OP shows, it's easy to inject your own random source:

>>> grb = "uuid.UUID(int=random.getrandbits(128), version=4)"

if you really need the speed.

[serhiy-storchaka]

I suggest to reject this proposal because of a deterioration in security.

[tiran]

If somebody is going to implement uuid based on the random module that somebody must take care of fork. Currently the PRGN in random isn't reseeded during fork(). This would lead to 100% collisions. The tempfile module contains a workaround for the issue.

I'm -1, see bpo-15206.

[pitrou]

Ok, let's reject the issue then.