[issue10044] small int optimization

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

[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 rep...@bugs.python.org

[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

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

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 expressions

[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

[issue10044] small int optimization

Serhiy Storchaka added the comment: Why is that permissible but _PyLong_IS_SMALL_INT is not? Touchér! -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue10044 ___

[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

[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 however

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

[issue10044] small int optimization

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

[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 STINNER Victor victor.stin...@gmail.com: -- nosy: +loewis ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue10044 ___ ___ Python-bugs-list

[issue10044] small int optimization

Changes by STINNER Victor victor.stin...@gmail.com: -- nosy: +haypo ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue10044 ___ ___ Python-bugs-list

[issue10044] small int optimization

Changes by Serhiy Storchaka storch...@gmail.com: -- components: +Interpreter Core nosy: +storchaka versions: +Python 3.4 -Python 3.3 ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue10044 ___

[issue10044] small int optimization

Changes by Andrew Svetlov andrew.svet...@gmail.com: -- nosy: +asvetlov ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue10044 ___ ___

[issue10044] small int optimization

Steffen Daode Nurpmeso sdao...@googlemail.com 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

[issue10044] small int optimization

Changes by Antoine Pitrou pit...@free.fr: -- versions: +Python 3.3 -Python 3.2 ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue10044 ___ ___

[issue10044] small int optimization

Meador Inge mead...@gmail.com 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

[issue10044] small int optimization

Xuanji Li xua...@gmail.com 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.

[issue10044] small int optimization

New submission from Antoine Pitrou pit...@free.fr: 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:

[issue10044] small int optimization

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

[issue10044] small int optimization

Daniel Stutzbach dan...@stutzbachenterprises.com added the comment: How does performance change if you adjust NSMALLPOSINTS and NSMALLNEGINTS, but make no other changes? -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue10044

[issue10044] small int optimization

Mark Dickinson dicki...@gmail.com 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

Mark Dickinson dicki...@gmail.com 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

[issue10044] small int optimization

Mark Dickinson dicki...@gmail.com 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

[issue10044] small int optimization

Antoine Pitrou pit...@free.fr 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

[issue10044] small int optimization

Daniel Stutzbach dan...@stutzbachenterprises.com 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

[issue10044] small int optimization

Changes by Eric Smith e...@trueblade.com: -- nosy: +eric.smith ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue10044 ___ ___ Python-bugs-list

[issue10044] small int optimization

Changes by Aahz a...@pythoncraft.com: -- nosy: -Aahz, aahz ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue10044 ___ ___ Python-bugs-list mailing

[issue10044] small int optimization

Antoine Pitrou pit...@free.fr 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

[issue10044] small int optimization

Antoine Pitrou pit...@free.fr 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

Mark Dickinson dicki...@gmail.com 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

[issue10044] small int optimization

Mark Dickinson dicki...@gmail.com 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

[issue10044] small int optimization

Antoine Pitrou pit...@free.fr 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

[issue10044] small int optimization

Mark Dickinson dicki...@gmail.com 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

[issue10044] small int optimization

Antoine Pitrou pit...@free.fr 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

Eric Smith e...@trueblade.com 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

[issue10044] small int optimization

Mark Dickinson dicki...@gmail.com 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

[issue10044] small int optimization

Antoine Pitrou pit...@free.fr 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

[issue10044] small int optimization

Mark Dickinson dicki...@gmail.com 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

[issue10044] small int optimization

Antoine Pitrou pit...@free.fr 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

[issue10044] small int optimization

Antoine Pitrou pit...@free.fr 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

[issue10044] small int optimization

Antoine Pitrou pit...@free.fr 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

Mark Dickinson dicki...@gmail.com 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: