GeezerVison

The World Wide Web, restored to 800 pixels of glory.

GeezerVison is showing github.com — Micro-optimize list index range checks by rhettinger · Pull Request #9784 · python/cpython

Conversation

rhettinger commented Oct 10, 2018

Copy link

Copy Markdown

Contributor

Old code

_list_item:
    testq   %rsi, %rsi 
    js  L282
    cmpq    %rsi, 16(%rdi)
    jg  L283
    ...
L283:
    movq    24(%rdi), %rax
    movq    (%rax,%rsi,8), %rax
    addq    $1, (%rax)
    ret

New code

_list_item:
    cmpq    16(%rdi), %rsi
    jb  L282
    ...
L282:
    movq    24(%rdi), %rax
    movq    (%rax,%rsi,8), %rax
    addq    $1, (%rax)
    ret

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

rhettinger added 2 commits

October 9, 2018 20:31


          Optimize list_item

d152678


          Convert the other range checks as well

65b589b

rhettinger added performance

Performance or resource usage

skip issue skip news labels

Oct 10, 2018

rhettinger assigned serhiy-storchaka

Oct 10, 2018

the-knights-who-say-ni added the CLA signed label

Oct 10, 2018

bedevere-bot added the awaiting merge label

Oct 10, 2018

serhiy-storchaka commented Oct 10, 2018 •

edited by bedevere-bot

Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link

Copy Markdown

Member

Is not this like bpo-28397?

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

serhiy-storchaka requested review from serhiy-storchaka, skrah and vstinner

October 10, 2018 04:41

serhiy-storchaka removed their assignment

Oct 10, 2018

pablogsal commented Oct 10, 2018

Copy link

Copy Markdown

Member

It would be interesting to run Linux perf on some representative examples to understand how the function call is affecting cache misses, references and branch predictions. (See #6493 as an example).

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

vstinner reviewed

Oct 10, 2018

View reviewed changes

Comment thread

Objects/listobject.c

		optimization manual found at:
		https://www.agner.org/optimize/optimizing_cpp.pdf
		*/
		return (size_t) i < (size_t) limit;

vstinner Oct 10, 2018

Copy link

Copy Markdown

Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I'm not sure that the behaviour is well defined in C. I fear that it's Undefined Behaviour. @benjaminp @gpshead: What do you think ?

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

vstinner Oct 10, 2018

Copy link

Copy Markdown

Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

If it's well defined, why should we hack such micro optimization? Why compilers would not implement the optimization themself?

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

sir-sigurd Oct 10, 2018 •

edited

Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link

Copy Markdown

Contributor

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think because they don't know that Py_SIZE(op) is non-negative.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

serhiy-storchaka Oct 10, 2018

Copy link

Copy Markdown

Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It is well defined. It is used for example in the STL implementations.

But there was not found any difference in microbenchmark results on 64-bit platforms in previous discussion in bpo-28397.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

gpshead approved these changes

Oct 10, 2018

View reviewed changes

gpshead left a comment

Copy link

Copy Markdown

Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Regardless of if this change is measurable, i like the way the code looks afterwards, getting rid of the repeated verbose i < 0 || i >= Py_SIZE(spam) everywhere. so +1 from me.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

Comment thread

Objects/listobject.c

		}

		static inline int
		valid_index(Py_ssize_t i, Py_ssize_t limit)

gpshead Oct 10, 2018

Copy link

Copy Markdown

Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Why not just define this as taking two size_t parameters instead of doing the casting below. The casts then happen implicitly at all call sites.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

rhettinger merged commit f1aa8ae into python:master

Oct 11, 2018

bedevere-bot removed the awaiting merge label

Oct 11, 2018

lgeiger mentioned this pull request

Sep 23, 2020

Add optimised 'Indirect BGEMM' binary convolution kernels. larq/compute-engine#516

Merged

This was referenced Jun 6, 2024

Use shared helper function for faster index range checks #120176

Closed

gh-120176: Reduce number of compares in index range checks #120181

Closed

Reviewers

vstinner

vstinner left review comments

gpshead

gpshead approved these changes

serhiy-storchaka

Awaiting requested review from serhiy-storchaka

skrah

Awaiting requested review from skrah

+1 more reviewer

sir-sigurd

sir-sigurd left review comments

Reviewers whose approvals may not affect merge requirements

Uh oh!

There was an error while loading. Please reload this page.

Assignees

No one assigned

Labels

performance

Performance or resource usage

skip issue skip news

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

Uh oh!

There was an error while loading. Please reload this page.

8 participants

Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.

You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.

GeezerVison

Conversation

rhettinger commented Oct 10, 2018

Old code

New code

Uh oh!

serhiy-storchaka commented Oct 10, 2018 • edited by bedevere-bot Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

pablogsal commented Oct 10, 2018

Uh oh!

vstinner Oct 10, 2018

Choose a reason for hiding this comment

Uh oh!

vstinner Oct 10, 2018

Choose a reason for hiding this comment

Uh oh!

sir-sigurd Oct 10, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

serhiy-storchaka Oct 10, 2018

Choose a reason for hiding this comment

Uh oh!

gpshead left a comment

Choose a reason for hiding this comment

Uh oh!

gpshead Oct 10, 2018

Choose a reason for hiding this comment

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

8 participants

serhiy-storchaka commented Oct 10, 2018 •

edited by bedevere-bot

Loading

Uh oh!

There was an error while loading. Please reload this page.

sir-sigurd Oct 10, 2018 •

edited

Loading

Uh oh!

There was an error while loading. Please reload this page.