[issue10044] small int optimization

STINNER Victor added the comment: Issue #21955 is a spin-off of this issue. -- ___ Python tracker ___ ___ Python-bugs-list mailing lis

[issue10044] small int optimization

Mark Dickinson added the comment: > Do we need to keep this issue open while this research is being > carried out? I'd say not. -- resolution: -> rejected status: open -> closed ___ Python tracker ___

[issue10044] small int optimization

Martin v. Löwis added the comment: Zitat von Serhiy Storchaka : >> 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)

[issue10044] small int optimization

Martin v. Löwis added the comment: > Why 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

[issue10044] small int optimization

Serhiy Storchaka added the comment: > 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 howe

[issue10044] small int optimization

Mark Dickinson added the comment: 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

[issue10044] small int optimization

Serhiy Storchaka added the comment: > Why is that permissible but _PyLong_IS_SMALL_INT is not? Touchér! -- ___ Python tracker ___ ___

[issue10044] small int optimization

Larry Hastings added the comment: 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 quot

[issue10044] small int optimization

Martin v. Löwis added the comment: > "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 expre

[issue10044] small int optimization

Serhiy Storchaka added the comment: 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

[issue10044] small int optimization

Mark Dickinson added the comment: 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? -- ___

[issue10044] small int optimization

Changes by STINNER Victor : -- nosy: +loewis ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python

[issue10044] small int optimization

STINNER Victor added the comment: 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

[issue10044] small int optimization

Changes by Serhiy Storchaka : -- components: +Interpreter Core nosy: +storchaka versions: +Python 3.4 -Python 3.3 ___ Python tracker ___ _

[issue10044] small int optimization

Changes by STINNER Victor : -- nosy: +haypo ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.

[issue10044] small int optimization

Changes by Andrew Svetlov : -- nosy: +asvetlov ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.pyth

[issue10044] small int optimization

Steffen Daode Nurpmeso added the comment: Now me. (http://gcc.gnu.org/onlinedocs/gcc/Arrays-and-pointers-implementation.html#Arrays-and-pointers-implementation) > When casting from pointer to integer and back again, the resulting > pointer must reference the same object as the original pointer,

[issue10044] small int optimization

Changes by Antoine Pitrou : -- versions: +Python 3.3 -Python 3.2 ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe:

[issue10044] small int optimization

Meador Inge added the comment: > How is the compiler supposed to know whether a and b belong to the same > array when compiling ptr_compare? 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

[issue10044] small int optimization

Xuanji Li added the comment: 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. -- nosy

[issue10044] small int optimization

Mark Dickinson added the comment: > 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? Technically, it's still dodgy: as the gcc manual notes in: http://gcc.gnu.org/onl

[issue10044] small int optimization

Antoine Pitrou added the comment: 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? -- ___ Python tracker

[issue10044] small int optimization

Antoine Pitrou added the comment: > 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. But this assumption doesn't bring *anything*, right? That is, there is no shortcut way to compute "p - q"

[issue10044] small int optimization

Antoine Pitrou added the comment: > 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. Which array? You ca

[issue10044] small int optimization

Mark Dickinson added the comment: > How is the compiler supposed to know whether a and b belong to the same > array when compiling ptr_compare? 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

[issue10044] small int optimization

Antoine Pitrou added the comment: > 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 differen

[issue10044] small int optimization

Mark Dickinson added the comment: 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 *pe

[issue10044] small int optimization

Eric Smith added the comment: 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

[issue10044] small int optimization

Antoine Pitrou added the comment: > > 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. :-) That doesn't very clear or understandable. -- _

[issue10044] small int optimization

Mark Dickinson added the comment: > 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. :-) -- ___ Python tracker

[issue10044] small int optimization

Antoine Pitrou added the comment: > 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 cr

[issue10044] small int optimization

Mark Dickinson added the comment: > I can't say anything about the standard, but p > q looks like it should > be the same as (p - q) > 0 Yep. > 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

[issue10044] small int optimization

Mark Dickinson added the comment: > 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 i

[issue10044] small int optimization

Antoine Pitrou added the comment: > 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). -- ___

[issue10044] small int optimization

Antoine Pitrou added the comment: > 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

[issue10044] small int optimization

Changes by Aahz : -- nosy: -Aahz, aahz ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/

[issue10044] small int optimization

Changes by Eric Smith : -- nosy: +eric.smith ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python

[issue10044] small int optimization

Daniel Stutzbach added the comment: > 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.) Technically arbitrary relational comparisons

[issue10044] small int optimization

Antoine Pitrou added the comment: > 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 val

[issue10044] small int optimization

Mark Dickinson added the comment: 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 li

[issue10044] small int optimization

Mark Dickinson added the comment: +#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 (beca

[issue10044] small int optimization

Mark Dickinson added the comment: 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! -- _

[issue10044] small int optimization

Daniel Stutzbach added the comment: How does performance change if you adjust NSMALLPOSINTS and NSMALLNEGINTS, but make no other changes? -- ___ Python tracker ___

[issue10044] small int optimization

Amaury Forgeot d'Arc added the comment: Arithmetic with void* pointers is not allowed by the Microsoft compilers. char* should be used instead. -- nosy: +amaury.forgeotdarc ___ Python tracker

[issue10044] small int optimization

New submission from Antoine Pitrou : 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