Faster index range checks

[serhiy-storchaka]

BPO	28397
Nosy	@rhettinger, @vstinner, @skrah, @socketpair, @serhiy-storchaka, @sir-sigurd
PRs	Micro-optimize list index range checks #9784
Files	check_index.patch check_index.cocci issue28397-2.c

^{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 2016-10-11.14:25:25.607>
created_at = <Date 2016-10-09.12:32:05.573>
labels = ['extension-modules', 'interpreter-core', '3.7', 'performance']
title = 'Faster index range checks'
updated_at = <Date 2018-10-10.12:03:32.312>
user = 'https://github.com/serhiy-storchaka'

bugs.python.org fields:

activity = <Date 2018-10-10.12:03:32.312>
actor = 'serhiy.storchaka'
assignee = 'none'
closed = True
closed_date = <Date 2016-10-11.14:25:25.607>
closer = 'serhiy.storchaka'
components = ['Extension Modules', 'Interpreter Core']
creation = <Date 2016-10-09.12:32:05.573>
creator = 'serhiy.storchaka'
dependencies = []
files = ['45034', '45035', '45055']
hgrepos = []
issue_num = 28397
keywords = ['patch']
message_count = 22.0
messages = ['278355', '278397', '278408', '278410', '278469', '278471', '278472', '278473', '278474', '278475', '278476', '278477', '278478', '278479', '278481', '278484', '278485', '278486', '278489', '278491', '278492', '327467']
nosy_count = 6.0
nosy_names = ['rhettinger', 'vstinner', 'skrah', 'socketpair', 'serhiy.storchaka', 'sir-sigurd']
pr_nums = ['9784']
priority = 'normal'
resolution = 'rejected'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue28397'
versions = ['Python 3.7']

[serhiy-storchaka]

The expression for testing that some index is in half-open range from 0 to limit can be written as

index >= 0 && index < limit

or as

(size_t)index < (size_t)limit

The latter form generates simpler machine code. This is idiomatic code, it is used in many C and C++ libraries (including C++ stdlib implementations). It already is used in CPython (in deque implementation).

Proposed patch rewrites index range checks in more efficient way. The patch was generated automatically by coccinelle script, and then manually cleaned up.

[rhettinger]

Don't change the code in the collections module. While semantically valid, the change obfuscates the code. The meaning of maxlen < 0 is that there is no maximum length. I don't want this test hidden; otherwise, I would have changed it long ago as was done elsewhere in the module where it made sense.

Elsewhere, consider making a macro with clear name and comment (as was done with NEEDS_TRIM) in the collections module. Otherwise, you're just leaving behind constipated and tricky code with no indication of why a signed variable is being coerced to unsigned.

[skrah]

Serhiy, could you please take out _decimal.c?

I thought we had been through that before. :) :) :)

[skrah]

The same applies to memoryview.c and _testbuffer.c -- I doubt that there's any measurable speed benefit and the clarity is reduced (I also don't want macros there).

[skrah]

In the following program, with gcc-5.3 doit() is significantly faster than doit2() in 64-bit Linux:

================================================================

#include <stdint.h>

int
doit(int64_t index, int64_t nitems)
{
    return index < 0 || index >= nitems;
}

int
doit2(int64_t index, int64_t nitems)
{
    return (uint64_t)index >= (uint64_t)nitems;
}

int
main(void)
{
    int count, i;

    for (i = 0; i < 1000000000; i++) {
        count += doit(832921, i);
    }

    return count;
}

================================================================

[skrah]

The difference in favor of doit() is even more pronounced with this
loop (also sorry for the uninitialized variable, but that does not
make a difference for benchmarking):

=====================================

for (i = 0; i < 10000; i++) {
        for (j = 0; j < 10000; j++) {
            count += doit(i, j);
        }
    }

======================================

[socketpair]

I have tested. performace differs in about of two times.
gcc -O3

0.22 nanoseconds per comparison.
vs
0.58 nanoseconds per comparison.

Does it cost a time that we spent to discuss here ?

[skrah]

Which version is faster in your tests?

[socketpair]

Much more conveniet way is to use unsigned variables in appropriate places.

[socketpair]

oh shi....doit() i.e.

return index < 0 || index >= nitems;

is faster!

[socketpair]

Without optimisation in compiler (-O0) speed is the same.