Repository navigation
small int optimization #54253
Description
Activity
This is an experimental patch to optimize some operations on small ints.
pystone is 5-10% faster, pybench 2-3% faster, and here are some relevant benchmarks from unladen swallow:### nbody ###
Min: 0.345136 -> 0.317502: 1.09x faster
Avg: 0.346827 -> 0.319561: 1.09x faster
Significant (t=79.50)
Stddev: 0.00140 -> 0.00198: 1.4084x larger### nqueens ###
Min: 0.339744 -> 0.313506: 1.08x faster
Avg: 0.342630 -> 0.315380: 1.09x faster
Significant (t=73.41)
Stddev: 0.00218 -> 0.00146: 1.4931x smallerIf the principle gets accepted, we could experiment with further optimizations such as dedicated opcodes for addition-with-int-constant, subscripting-with-int-constant, etc.
Arithmetic with void* pointers is not allowed by the Microsoft compilers. char* should be used instead.
stutzbach commented
on Oct 7, 2010 stutzbachmannequinMannequinHow does performance change if you adjust NSMALLPOSINTS and NSMALLNEGINTS, but make no other changes?
Looks like a nice idea, at first glance, though I haven't looked at the code in detail. I like the use of the macros to abstract away the long implementation details.
"INPLACE_SUBTRACT_end", not "INPLACE_SUBSTRACT_end", please!
+#define _PyLong_IS_SMALL_INT(v) \
+ (((PyLongObject *)(v)) >= _PyLong_small_ints && \
+ ((PyLongObject *)(v)) < _PyLong_SMALL_INTS_END)
+/* These macros purposedly avoid a cast to int, since it is most of time
+ useless, and sometimes detrimental (because of truncation).
+ XXX _PyLong_AS_SMALL_INT might be slower if sizeof(PyLongObject) is not
+ a power of two.
+ */Urk! This is nasty. :(
I don't think arbitrary comparisons of pointers give well-defined results, unless those pointers both happen to point into the same array. (Might be wrong; I don't have a copy of the C standard to hand.)
Maybe we could consider adding an extra field to a PyLong giving its 'small_int' value for small values, and some flag value for non-small longs. An extra field wouldn't actually enlarge the size of a PyLong for small values---on a 64-bit machine, a value like 23L takes 28 bytes, for which 32 bytes will actually be allocated (since Python always allocates in multiples of 8 bytes, I believe).
Maybe we could consider adding an extra field to a PyLong giving its
'small_int' value for small values, and some flag value for non-small
longs. An extra field wouldn't actually enlarge the size of a PyLong
for small values---on a 64-bit machine, a value like 23L takes 28
bytes, for which 32 bytes will actually be allocated (since Python
always allocates in multiples of 8 bytes, I believe).I actually had a patch for that. It declared a ob_digit[2] array instead
of ob_digit[1], and ob_digit[1] contained the small int. But the patch
still used the pointer comparison approach for PyLong_IS_SMALL_INT,
because I think it's faster (just two comparisons). So there didn't seem
to much point.Also, the pointer addition trick for addition (see BINARY_ADD) is
probably faster than the more intuitive method.stutzbach commented
on Oct 7, 2010 stutzbachmannequinMannequinI don't think arbitrary comparisons of pointers give well-defined
results, unless those pointers both happen to point into the same
array. (Might be wrong; I don't have a copy of the C standard to
hand.)Technically arbitrary relational comparisons of pointers are undefined, but in practice Antoine's assumptions here are very modest. They boil down to:
v >= &array[0] && v < &array[array_len]
It is hard for me to imagine a system designed such that the expression could evaluate to true when v is not in the array.
I suppose a system could be designed where relational comparisons of unrelated data pointers causes a segmentation fault or similar, but that also seems unlikely to me.
Technically arbitrary relational comparisons of pointers are
undefined, but in practice Antoine's assumptions here are very modest.
They boil down to:v >= &array[0] && v < &array[array_len]
I can't say anything about the standard, but p > q looks like it should
be the same as (p - q) > 0, which looks rather well-defined for
pointers.(at worse we could cast to _Py_uintptr_t, hopefully the compiler
wouldn't produce any different code)How does performance change if you adjust NSMALLPOSINTS and
NSMALLNEGINTS, but make no other changes?It makes a very small difference (which is understandable since it doesn't cut down on code execution a lot).
Technically arbitrary relational comparisons of pointers are undefined,
but in practice Antoine's assumptions here are very modest.I disagree: there's a very real practical danger here. Namely, optimizing compilers are free to assume that code doesn't involve any undefined behaviour and optimize accordingly. gcc for one is known to make extensive use of this freedom. I wouldn't be at all surprised to find some current or future version of gcc optimizing an (p >= start_of_array) check to 'always true', on the basis that it *will* always be true in legal code.
Please don't introduce undefined behaviour here---it's asking for trouble.
I can't say anything about the standard, but p > q looks like it should
be the same as (p - q) > 0Yep.
which looks rather well-defined for pointers.
Nope. It's only well-defined for pointers pointing into the same array (or to one past the end of an array). Otherwise it's undefined behaviour.
See section 6.5.6, paragraph 9, of
Nope. It's only well-defined for pointers pointing into the same
array (or to one past the end of an array). Otherwise it's undefined
behaviour.How can the compiler tell whether two pointers are "into the same
array"? That sounds like an undecidable criterion.How can the compiler tell whether two pointers are "into the same
array"? That sounds like an undecidable criterion.It doesn't have to be able to tell---it's allowed to assume. :-)
12 remaining items
If I understood correctly, the optimization proposed by Antoine was somehow rejected because _PyLong_IS_SMALL_INT() may be optimized "incorrectly".
If a compiler "miscompiles" this macro, can't we disable this optimization on this specific compiler, instead of missing an interesting optimization on all compilers? I bet that no compiler will do insane optimization on such test.
Where in CPython source code do we use directly references to small_ints? The common case is to write PyLong_FromLong(0). Can compiler call PyLong_FromLong() to detect that the result is part of the small_ints array? Or that it is not part of small_ints?
The corner case is very unlikely to me.
--
I tested Antoine's patch with GCC 4.6 and CFLAGS="-O3 -flto" (-flto: standard link-time optimizer): the test suite pass. I don't see any magic optimization here, sorry.
--
"fwiw I've always found this helpful for undefined behavior: http://blog.regehr.org/archives/213 and, just as it says "x+1 > x" will be optimized to a nop, by the same logic "v >= &array[0] && v < &array[array_len]" will also be optimized to a nop."
"x+1 > x" and "v >= &array[0]" are not the same checks. In the first test, x is used in both parts. I don't understand.
Victor: so you want to *deliberately* introduce undefined behaviour for the sake of a minor optimization, while crossing your fingers and *hoping* that that doesn't cause issues with any existing or future compilers?
Victor, the danger of this approach is that we can't verify that a particular compiler with certain options on a specific platform compiles the source code with undefined behavior in a certain way. If such a test were possible, if this aspect was guaranteed by the compiler manufacturer, or could be checked in the ./configure script, then such an approach would have some meaning.
Regardless of _PyLong_IS_SMALL_INT, the rest of patch looks a little cumbersome.
loewis commented
on Sep 22, 2012 loewismannequinMannequin"x+1 > x" and "v >= &array[0]" are not the same checks.
In the first test, x is used in both parts. I don't understand.The consequences of "undefined behavior" are really difficult to understand, it seems. A compiler which evaluates both relational expressions unconditionally to true would be conforming to the C language definition. The reason for that has been said several times before, but let me repeat them.
Mathematically, x+1 > x for any real number, so it seems natural to assume that this can be determined to be "true" statically. However, what if x+1 overflows? Shouldn't then it evaluate to "false"? Not necessarily if x is signed. Then the behavior of overflow is undefined, and *any* result of the comparison would be conforming to the standard: the overflow may trap, the expression may evaluate to "false", or the expression may evaluate to "true", or your hard disk may get erased - all of these would be conforming to the C language definition.
For v >= &array[0], this is the same issue. If v points into the array, the expression is true. If v doesn't point into the array, the behavior is undefined, so the compiler may chose to give false, or to give true, or to actually compare the pointers as integers, or to erase your hard disk.
Of these possible behaviors, only two are plausible. For x+1>x, it may be that the compiler actually generates code to perform the addition and the comparison, or it may statically decide that the expression is always true. For v > &array[0], the compiler may either generate code to perform the comparison, or statically decide that the expression is true. Either implementation would be correct - it's not that the compiler is optimizing "incorrectly".
In the specific case, a compiler might infer that _PyLong_IS_SMALL_INT is always true, which would give incorrect results in Python. However, it is the patch which is incorrect, not the compiler.
I recommend to close the issue as rejected.
I must be missing something--because I thought Python *already* depended on this apparently-undefined behavior. The small-block object allocator in Objects/obmalloc.c determines whether a pointer belongs to a particular arena using exactly this trick. I quote from the gigantic comment at the top of that file:
Let B be the arena base address associated with the pool, B = arenas[(POOL)->arenaindex].address. Then P belongs to the arena if and only if B <= P < B + ARENA_SIZE Subtracting B throughout, this is true iff 0 <= P-B < ARENA_SIZEThis test is implemented as the following macro:
#define Py_ADDRESS_IN_RANGE(P, POOL) \ ((arenaindex_temp = (POOL)->arenaindex) < maxarenas && \ (uptr)(P) - arenas[arenaindex_temp].address < (uptr)ARENA_SIZE && \ arenas[arenaindex_temp].address != 0)
Why is that permissible but _PyLong_IS_SMALL_INT is not?
Why is that permissible but _PyLong_IS_SMALL_INT is not?
Touchér!
Ah: nice catch, Larry.
I would say that the obmalloc case *shouldn't* be permissible; however, it's already there, and changing that would be an involved task that would also likely risk introducing new bugs. So I guess practicality beats purity on that one. I don't see that as an excuse for introducing *new* undefined behaviour though, especially for a small optimization.
I recommend to close the issue as rejected.
I think _PyLong_IS_SMALL_INT can be rewritten in a safe style. For example, using a checking of several fields ((sdigit)(x)->ob_digit[0] < _MAX_SMALL_INT && PySIZE(x) <= 1) or a
special flag. It is possible however that shuch checking will fully destroy the effect of optimization. We need further research.loewis commented
on Sep 22, 2012 loewismannequinMannequinWhy is that permissible but _PyLong_IS_SMALL_INT is not?
It's *permissable* primarily because it is there. There are many places in Python which invoke undefined behavior already (most notably wrt. signed integers); we should strive to eliminate them.
OTOH, obmalloc clearly makes a lot of assumptions on the hardware architecture (including the assumption that there is page-based virtual memory, etc). It's a memory allocator, that gives permission to make such assumptions. If it turns out that they break on some system, obmalloc cannot be used there - hence usage of obmalloc is still a compile-time option.
In addition, for the specific macros: it's easy to see that a compiler may optimize _PyLong_IS_SMALL_INT as true by simple static analysis. For Py_ADDRESS_IN_RANGE, the same static analysis is not possible, since the memory doesn't come from a declared array. It would require whole-program analysis to determine that .address always points to a memory block with ARENA_SIZE bytes. If a compiler manages to figure it out, obmalloc cannot be used on that system (and if that happens, I'll recommend to drop or revise obmalloc altogether, perhaps in favor of a system pool allocator).
loewis commented
on Sep 22, 2012 loewismannequinMannequinZitat von Serhiy Storchaka <report@bugs.python.org>:
> I recommend to close the issue as rejected.
I think _PyLong_IS_SMALL_INT can be rewritten in a safe style. For
example, using a checking of several fields
((sdigit)(x)->ob_digit[0] < _MAX_SMALL_INT && PySIZE(x) <= 1) or a
special flag. It is possible however that shuch checking will fully
destroy the effect of optimization. We need further research.Do we need to keep this issue open while this research is being carried
out? This issue is already cluttered with the undefined-behavior discussion.Do we need to keep this issue open while this research is being
carried out?I'd say not.
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:
bugs.python.org fields: