Repository navigation
small int optimization #54253
Description
| BPO | 10044 |
|---|---|
| Nosy | @loewis, @rhettinger, @amauryfa, @mdickinson, @pitrou, @vstinner, @larryhastings, @ericvsmith, @asvetlov, @meadori, @IIIIllllIIIIllllIIIIllllIIIIllllIIIIll, @serhiy-storchaka |
| Files |
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 2013-03-31.12:49:48.595>
created_at = <Date 2010-10-07.11:56:27.745>
labels = ['interpreter-core', 'performance']
title = 'small int optimization'
updated_at = <Date 2016-02-06.00:59:30.742>
user = 'https://github.com/pitrou'bugs.python.org fields:
activity = <Date 2016-02-06.00:59:30.742>
actor = 'vstinner'
assignee = 'none'
closed = True
closed_date = <Date 2013-03-31.12:49:48.595>
closer = 'mark.dickinson'
components = ['Interpreter Core']
creation = <Date 2010-10-07.11:56:27.745>
creator = 'pitrou'
dependencies = []
files = ['19148']
hgrepos = []
issue_num = 10044
keywords = ['patch']
message_count = 38.0
messages = ['118103', '118109', '118111', '118113', '118114', '118118', '118120', '118121', '118127', '118131', '118132', '118133', '118135', '118136', '118137', '118138', '118139', '118140', '118142', '118143', '118144', '118145', '118146', '124955', '125006', '135024', '170940', '170972', '170977', '170986', '170998', '171004', '171005', '171007', '171014', '171016', '185626', '259705']
nosy_count = 14.0
nosy_names = ['loewis', 'rhettinger', 'amaury.forgeotdarc', 'mark.dickinson', 'pitrou', 'vstinner', 'larry', 'eric.smith', 'stutzbach', 'asvetlov', 'meador.inge', 'xuanji', 'sdaoden', 'serhiy.storchaka']
pr_nums = []
priority = 'normal'
resolution = 'rejected'
stage = None
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue10044'
versions = ['Python 3.4']
Activity
pitrou commentedon Oct 7, 2010
That doesn't very clear or understandable.
ericvsmith commentedon Oct 7, 2010
In the bad old days of 386 segment:offset memory architectures this was a problem. You could have overlapping segments but pointers inside an object were always in the same segment, so the segment selectors never had to be inspected. Pointers to different objects could indeed have the same offset and would compare equal.
We should follow the standard here: no comparisons between pointers to different arrays (basically).
mdickinson commentedon Oct 7, 2010
See the example above: suppose that a compiler is looking at a (p >= q) comparison of pointers. Suppose furthermore that in a particular case that compiler is smart enough to figure out that q is a pointer to the start of an array. Then the compiler is *permitted to assume* that p also points into the same array, since if it didn't then the code would introduce undefined behaviour. And since q is the start of the array, and p is (by assumption) a pointer into the same array, p >= q will automatically be true, so the compiler is free to replace the expression with the integer '1' (i.e., true).
gcc does similar things with checks like (x + 1 > x): if x is a (signed) int, then gcc can and will optimize (x + 1 > x) to 'true', on the basis that x + 1 can never overflow, because such overflow would be undefined behaviour and therefore can't occur in a valid C program.
pitrou commentedon Oct 7, 2010
AFAIK it caused lots of other problems much more annoying than just
pointer compares, and programmers had to juggle by hand with various
addressing modes (near, far, etc.).
ISTM that all C programs nowadays assume some kind of flat, paged memory
model, CPython included; I don't think we have to fear some i386-like
segmentation model.
Again, what is an "array" supposed to be? In memory there are no
"arrays".
Let's say I have the following function in a module:
and another module, the following function
How is the compiler supposed to know whether a and b belong to the same
array when compiling ptr_compare?
Otherwise, we could cast to Py_uintptr_t.
mdickinson commentedon Oct 7, 2010
It doesn't need to know. So long as the compiler can guarantee that its code will produce correct results in the case that a and b *do* both point to the same array, that's enough. In other words, when producing code for ptr_compare, the compiler is allowed to *assume* that a and b point into the same array, and act accordingly.
pitrou commentedon Oct 7, 2010
Which array? You can have arrays everywhere in memory, at any address,
ending anywhere.
Which is an array, and which is not? is &ch1 an array? and arr1? and
arr2+1? Why would the compiler choose one over another? And what about
arrays defined in other modules?
pitrou commentedon Oct 7, 2010
But this assumption doesn't bring *anything*, right?
That is, there is no shortcut way to compute "p - q" or "p > q" when
both point into the same "array".
pitrou commentedon Oct 7, 2010
For the record, a Py_uintptr_t version works and has the same performance. Would you agree to it or is there still some menacing oddity from the i386 days lurking around?
mdickinson commentedon Oct 7, 2010
Technically, it's still dodgy: as the gcc manual notes in:
http://gcc.gnu.org/onlinedocs/gcc/Arrays-and-pointers-implementation.html#Arrays-and-pointers-implementation
". That is, one may not use integer arithmetic to avoid the undefined behavior of pointer arithmetic as proscribed in C99 6.5.6/8."
I can't see as much scope for problems with the uintptr_t version. But just because I can't anticipate the problems, it doesn't mean they don't exist.
It really would be better to avoid the undefined behaviour if at all possible.
IIIIllllIIIIllllIIIIllllIIIIllllIIIIll commentedon Dec 31, 2010
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.
meadori commentedon Jan 1, 2011
I agree with Mark, it doesn't need to know. However, many compilers [1,2] support whole program optimization and could in theory figure the address out using that technique.
[1] GCC -flto - http://gcc.gnu.org/onlinedocs/gcc-4.5.2/gcc/Optimize-Options.html#Optimize-Options
[2] VC++ LTCG - http://msdn.microsoft.com/en-us/library/xbf3tbeh.aspx
sdaoden commentedon May 3, 2011
Now me.
(http://gcc.gnu.org/onlinedocs/gcc/Arrays-and-pointers-implementation.html#Arrays-and-pointers-implementation)
Say - isn't that a joke about farts of armchair crouchers.
All it says is that if you dereference garbage you get a crash.
If you're concerned, use volatile, and go shoot the compiler
programmer if she dares to optimize just anything.
And on ARM, isn't the interrupt table at ((void*)(char[])0x0)??
La vie est une rose beside that.
And all i need is atomic_compare_and_swap().
vstinner commentedon Sep 22, 2012
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.
mdickinson commentedon Sep 22, 2012
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?
serhiy-storchaka commentedon Sep 22, 2012
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 commentedon Sep 22, 2012
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.
larryhastings commentedon Sep 22, 2012
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:
This test is implemented as the following macro:
Why is that permissible but _PyLong_IS_SMALL_INT is not?
serhiy-storchaka commentedon Sep 22, 2012
Touchér!
mdickinson commentedon Sep 22, 2012
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.
serhiy-storchaka commentedon Sep 22, 2012
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 commentedon Sep 22, 2012
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 commentedon Sep 22, 2012
Zitat von Serhiy Storchaka <report@bugs.python.org>:
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.
mdickinson commentedon Mar 31, 2013
I'd say not.
vstinner commentedon Feb 6, 2016
Issue bpo-21955 is a spin-off of this issue.