Random objects twice as big as necessary on 64-bit builds

[rhettinger]

BPO	23488
Nosy	@rhettinger, @mdickinson, @pitrou, @vstinner, @serhiy-storchaka
Files	random_uint32.patch random_uint32_2.patch

^{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 = 'https://github.com/serhiy-storchaka'
closed_at = <Date 2015-05-13.12:06:17.213>
created_at = <Date 2015-02-20.10:18:42.410>
labels = ['extension-modules', 'performance']
title = 'Random objects twice as big as necessary on 64-bit builds'
updated_at = <Date 2015-05-25.22:03:43.850>
user = 'https://github.com/rhettinger'

bugs.python.org fields:

activity = <Date 2015-05-25.22:03:43.850>
actor = 'rhettinger'
assignee = 'serhiy.storchaka'
closed = True
closed_date = <Date 2015-05-13.12:06:17.213>
closer = 'serhiy.storchaka'
components = ['Extension Modules']
creation = <Date 2015-02-20.10:18:42.410>
creator = 'rhettinger'
dependencies = []
files = ['38208', '38707']
hgrepos = []
issue_num = 23488
keywords = ['patch']
message_count = 19.0
messages = ['236262', '236263', '236264', '236265', '236306', '236428', '236429', '236430', '236432', '236839', '239379', '243051', '243052', '243060', '243061', '243075', '243455', '243461', '244050']
nosy_count = 6.0
nosy_names = ['rhettinger', 'mark.dickinson', 'pitrou', 'vstinner', 'python-dev', 'serhiy.storchaka']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'resource usage'
url = 'https://bugs.python.org/issue23488'
versions = ['Python 3.5']

[rhettinger]

The Modules/_randommodule.c implements the 32-bit version of the MersenneTwister and its struct uses (unsigned long) for each of the 624 elements of the state vector.

On a 32-bit build, the unsigned longs are 4 bytes. However, on a 64-bit build, they are 8 bytes each eventhough only the bottom 32-bits are used. This causes the random object to be twice as big as necessary. sys.getsizeof(_random.Random()) reports 5016 bytes. This wastes memory, grinds the cache, and slows performance.

The (unsigned long) declaration should probably be replaced with (uint32_t).

[vstinner]

The (unsigned long) declaration should probably be replaced with (uint32_t)

Would it be possible to benchmark this change, to ensure that it doesn't kill performances?

A quick micro-benchmark using timeit should be enough ;)

I agree with the change, I already noticed the unused bits long time ago, when I took at look at the Mersenne Twister implementation.

[vstinner]

Oh, by the way, using 32 bits unsigned integers would avoid all the "& 0xffffffff" everywhere.

[pitrou]

Yes, I noticed this when reimplementing the random module in Numba.
*Theoretically*, I think you need "long" to ensure ints are at least 32 bits. But in practice, I think CPython already needs 32-bit C ints.

(note Numpy also uses C longs internally)

Would it be possible to benchmark this change, to ensure that it doesn't kill performances?

There is no way it can kill performance.

[serhiy-storchaka]

Here is a patch. It also optimizes getrandbit() and seed() as was originally proposed in bpo-16496.

[mdickinson]

Here is a patch.

Where?!

BYW, we might want to use PY_UINT32_T rather than uint32_t directly.

[serhiy-storchaka]

Oh, sorry, here is it.

[serhiy-storchaka]

Some microbenchmark results on 32-bit Linux:

$ ./python -m timeit -s "from random import getrandbits" -- "getrandbits(64)"
Before: 1000000 loops, best of 3: 1.41 usec per loop
After:  1000000 loops, best of 3: 1.34 usec per loop

$ ./python -m timeit -s "from random import getrandbits" -- "getrandbits(2048)"
Before: 100000 loops, best of 3: 5.84 usec per loop
After:  100000 loops, best of 3: 5.61 usec per loop

$ ./python -m timeit -s "from random import getrandbits" -- "getrandbits(65536)"
Before: 10000 loops, best of 3: 145 usec per loop
After:  10000 loops, best of 3: 137 usec per loop

[vstinner]

The patch looks good to me.

For utint32_t, see my old issue bpo-17884: "Try to reuse stdint.h types like int32_t".

[mdickinson]

see my old issue bpo-17884

... and you can also re-read my explanations in that issue about why simply using uint32_t and int32_t doesn't work! We need something like PY_UINT32_T (and co) for portability.

The only part of bpo-17884 that's still valid is that it may well make sense to insist that exact-width 32-bit and 64-bit signed and unsigned integer types are available when building Python.

[serhiy-storchaka]

Updated patch addresses some Victor's comments.

[serhiy-storchaka]

Ping.