GV

GeezerVison

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

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — bpo-33234 Improve list() pre-sizing for inputs with known lengths by pablogsal · Pull Request #6493 · python/cpython

Conversation

@pablogsal

@pablogsal pablogsal commented Apr 17, 2018 •
edited by bedevere-bot
Loading

Uh oh!

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

Copy link
Copy Markdown
Member

The list() constructor isn't taking full advantage of known input
lengths or length hints. This commit makes the constructor
pre-size and not over-allocate when the input size is known or
can be reasonably estimated.

A new test is added to test_list.py and a test needed to be modified
in test_descr.py as it assumed that there is only one call to
__length_hint__() in the list constructor.

https://bugs.python.org/issue33234

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
@the-knights-who-say-ni the-knights-who-say-ni added the CLA signed label Apr 17, 2018
@bedevere-bot bedevere-bot added the awaiting review label Apr 17, 2018
@pablogsal
pablogsal force-pushed the bpo33234 branch 2 times, most recently from 55b6bd9 to 8703946 Compare April 17, 2018 00:30
rhettinger
rhettinger reviewed Apr 17, 2018
View reviewed changes
Comment thread Lib/test/test_list.py Outdated

@rhettinger rhettinger Apr 17, 2018

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.

This should be marked as a CPython only test.

Sorry, something went wrong.

Uh oh!

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

@pablogsal pablogsal Apr 17, 2018 •
edited
Loading

Uh oh!

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

Copy link
Copy Markdown
Member Author

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.

@rhettinger Amended in 7602879

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
@pablogsal
Improve list() pre-sizing for inputs with known lengths
7602879 
The list() constructor isn't taking full advantage of known input
lengths or length hints. This commit makes the constructor
pre-size and not over-allocate when the input size is known or
can be reasonably estimated.

A new test is added to test_list.py and a test needed to be modified
in test_descr.py as it assumed that there is only one call to
__length_hint__() in the list constructor.
@pablogsal
pablogsal force-pushed the bpo33234 branch from 8703946 to 7602879 Compare April 17, 2018 20:51
vstinner
vstinner reviewed Apr 30, 2018
View reviewed changes
Comment thread Objects/listobject.c
(void)_list_clear(self);
}
if (iterable != NULL) {
Py_ssize_t iter_len = PyObject_LengthHint(iterable, 0);

@vstinner vstinner Apr 30, 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.

list_extend() uses PyObject_LengthHint(iterable, 8): we may also use 8 here.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
@pablogsal

pablogsal commented Sep 14, 2018 •
edited
Loading

Uh oh!

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

Copy link
Copy Markdown
Member Author

I have collected more metrics. This are the L1 and L2 cache misses and related information:

THIS PR
Performance counter stats for './python -c for _ in range(10000): list([0]*10000)' (200 runs):

      75916384      cache-references                                              ( +-  2.52% )
        659899      cache-misses              #    0.869 % of all cache refs      ( +-  3.55% )
    4242376466      cycles                                                        ( +-  0.84% )
    5316694198      instructions              #    1.25  insn per cycle           ( +-  0.02% )
    1086705824      branches                                                      ( +-  0.01% )
         71006      faults                                                        ( +-  0.00% )
             0      migrations

   1.708574749 seconds time elapsed                                          ( +-  0.86% )

MASTER
Performance counter stats for './python -c for _ in range(10000): list([0]*10000)' (200 runs):

      91939960      cache-references                                              ( +-  1.98% )
        730659      cache-misses              #    0.795 % of all cache refs      ( +-  2.53% )
    4595555189      cycles                                                        ( +-  0.95% )
    5383346835      instructions              #    1.17  insn per cycle           ( +-  0.02% )
    1097849443      branches                                                      ( +-  0.02% )
         91006      faults                                                        ( +-  0.00% )
             0      migrations

   1.851745158 seconds time elapsed                                          ( +-  0.96% )

As you can see, this shows a great improvement in cache efficiency and branch predictions. As there is some concern regarding what happens with the overhead of calling __len_hint__ I have collected more metrics in that regard:

root@ubuntu-s-2vcpu-4gb-sfo2-01:~/cpython# ./python -m perf timeit "list(iter([0]*11))" -o old.json
root@ubuntu-s-2vcpu-4gb-sfo2-01:~/cpython# ./python -m perf timeit "list(iter([0]*10000))" -o old_big.json
root@ubuntu-s-2vcpu-4gb-sfo2-01:~/cpython# ./python -m perf timeit "list(iter([0]*11))" -o new.json
root@ubuntu-s-2vcpu-4gb-sfo2-01:~/cpython# ./python -m perf timeit "list(iter([0]*10000))" -o new_big.json

And these are the results:

root@ubuntu-s-2vcpu-4gb-sfo2-01:~/cpython# ./python -m perf compare_to old.json new.json -vv
Mean +- std dev: [old] 1.55 us +- 0.11 us -> [new] 1.66 us +- 0.11 us: 1.07x slower (+7%)
Significant (t=-5.31)
root@ubuntu-s-2vcpu-4gb-sfo2-01:~/cpython# ./python -m perf compare_to old_big.json 
new_big.json
Mean +- std dev: [old_big] 206 us +- 18 us -> [new_big] 155 us +- 11 us: 1.33x faster (-25%)

As you can see the only case when this patch is slow is for very small iterables without __len__, but we are talking about 7% difference (0.11us) vs the chunked linear improvement that you get for the preallocation.
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@pablogsal
pablogsal requested a review from serhiy-storchaka September 27, 2018 14:58
@pablogsal

pablogsal commented Sep 28, 2018

Copy link
Copy Markdown
Member Author

CC: @rhettinger
All reactions

Sorry, something went wrong.

Uh oh!

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

vstinner commented Sep 28, 2018

Copy link
Copy Markdown
Member

I'm not sure about this change because of the possible slowdown for short datasets. Raymond and me proposed to add a slot for length hint. I would suggest to work in two steps:

  • Optimize list allocation only using the length if it's available (not the length hint)
  • Later add a slot for length hint and use it for list allocation
pablogsal reacted with thumbs up emoji
All reactions
  • 👍 1 reaction

Sorry, something went wrong.

Uh oh!

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

pablogsal commented Sep 28, 2018

Copy link
Copy Markdown
Member Author

Agreed. Will open a new PR with the version that only uses lenght if it is available.
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
This was referenced Oct 10, 2018
Micro-optimize list index range checks #9784
Merged
bpo-33234 Improve list() pre-sizing for inputs with known lengths (no __length_hint__) #9846
Merged
@pablogsal pablogsal closed this Oct 28, 2018
@pablogsal
pablogsal deleted the bpo33234 branch October 28, 2018 20:50
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@vstinner vstinner vstinner left review comments
@rhettinger rhettinger rhettinger left review comments
@serhiy-storchaka serhiy-storchaka Awaiting requested review from serhiy-storchaka

Uh oh!

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

Assignees

No one assigned

Labels

awaiting review

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.

5 participants

@pablogsal @vstinner @rhettinger @the-knights-who-say-ni @bedevere-bot
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.