Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Closed
rhettinger opened this issue Feb 20, 2015 · 19 comments
Closed

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

rhettinger opened this issue Feb 20, 2015 · 19 comments
Assignees
Labels
extension-modules C modules in the Modules dir performance Performance or resource usage

Comments

@rhettinger
Copy link
Contributor

rhettinger commented Feb 20, 2015

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
    Copy link
    Contributor Author

    rhettinger commented Feb 20, 2015

    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).

    @rhettinger rhettinger self-assigned this Feb 20, 2015
    @rhettinger rhettinger added performance Performance or resource usage extension-modules C modules in the Modules dir labels Feb 20, 2015
    @vstinner
    Copy link
    Member

    vstinner commented Feb 20, 2015

    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
    Copy link
    Member

    vstinner commented Feb 20, 2015

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

    @pitrou
    Copy link
    Member

    pitrou commented Feb 20, 2015

    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
    Copy link
    Member

    serhiy-storchaka commented Feb 20, 2015

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

    @mdickinson
    Copy link
    Member

    mdickinson commented Feb 23, 2015

    Here is a patch.

    Where?!

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

    @serhiy-storchaka
    Copy link
    Member

    serhiy-storchaka commented Feb 23, 2015

    Oh, sorry, here is it.

    @serhiy-storchaka
    Copy link
    Member

    serhiy-storchaka commented Feb 23, 2015

    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
    Copy link
    Member

    vstinner commented Feb 23, 2015

    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
    Copy link
    Member

    mdickinson commented Feb 27, 2015

    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
    Copy link
    Member

    serhiy-storchaka commented Mar 27, 2015

    Updated patch addresses some Victor's comments.

    @serhiy-storchaka
    Copy link
    Member

    serhiy-storchaka commented May 13, 2015

    Ping.

    @pitrou
    Copy link
    Member

    pitrou commented May 13, 2015

    You should fix the comment as mentioned in the review, otherwise looks good to me.

    @rhettinger
    Copy link
    Contributor Author

    rhettinger commented May 13, 2015

    This is good to go.

    @rhettinger
    Copy link
    Contributor Author

    rhettinger commented May 13, 2015

    This would have gone quicker if the size bug-fix hadn't been commingled with the optimization.

    @python-dev
    Copy link
    Mannequin

    python-dev mannequin commented May 13, 2015

    New changeset 4b5461dcd190 by Serhiy Storchaka in branch 'default':
    Issue bpo-23488: Random generator objects now consume 2x less memory on 64-bit.
    https://hg.python.org/cpython/rev/4b5461dcd190

    @python-dev
    Copy link
    Mannequin

    python-dev mannequin commented May 18, 2015

    New changeset 16d0e3dda31c by Zachary Ware in branch 'default':
    Issue bpo-23488: Fix a syntax error on big endian platforms.
    https://hg.python.org/cpython/rev/16d0e3dda31c

    @serhiy-storchaka
    Copy link
    Member

    serhiy-storchaka commented May 18, 2015

    Thanks Zachary for fixing this.

    @rhettinger
    Copy link
    Contributor Author

    rhettinger commented May 25, 2015

    Should this be backported? IMO, it is a bug.

    @ezio-melotti ezio-melotti transferred this issue from another repository Apr 10, 2022
    Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
    Labels
    extension-modules C modules in the Modules dir performance Performance or resource usage
    Projects
    None yet
    Development

    No branches or pull requests

    5 participants