Skip to content

bpo-33234 Improve list() pre-sizing for inputs with known lengths (no __length_hint__) #9846

Merged
pablogsal merged 10 commits intopython:masterfrom
pablogsal:bpo33234-2
Oct 28, 2018
Merged

bpo-33234 Improve list() pre-sizing for inputs with known lengths (no __length_hint__) #9846
pablogsal merged 10 commits intopython:masterfrom
pablogsal:bpo33234-2

Conversation

@pablogsal
Copy link
Member

@pablogsal pablogsal commented Oct 13, 2018

This is a version of #6493 that only preallocates the list when __len__ is available to reduce memory overallocation and possible performance hit on big iterables.

This are the L1 and L2 cache misses and related information:

THIS PR

❯ perf stat -r 200 -B -e cache-references,cache-misses,cycles,instructions,branches,faults,migrations ./python -c "
for _ in range(1000):
    list([0]*10000)
"
 Performance counter stats for './python -c
for _ in range(1000):
    list([0]*10000)
' (200 runs):

         1,151,365      cache-references:u                                            ( +-  0.47% )
             5,686      cache-misses:u            #    0.494 % of all cache refs      ( +-  8.06% )
       370,237,437      cycles:u                                                      ( +-  0.05% )
       542,049,270      instructions:u            #    1.46  insn per cycle           ( +-  0.00% )
       134,146,925      branches:u                                                    ( +-  0.00% )
             8,031      faults:u                                                      ( +-  0.00% )
                 0      migrations:u

          0.122170 +- 0.000307 seconds time elapsed  ( +-  0.25% )

MASTER

❯ perf stat -r 200 -B -e cache-references,cache-misses,cycles,instructions,branches,faults,migrations ./python -c "for _ in range(1000):
    list([0]*10000)
"
 Performance counter stats for './python -c
for _ in range(1000):
    list([0]*10000)
' (200 runs):

         1,275,440      cache-references:u                                            ( +-  0.61% )
            21,895      cache-misses:u            #    1.717 % of all cache refs      ( +-  4.69% )
       392,293,096      cycles:u                                                      ( +-  0.22% )
       543,254,939      instructions:u            #    1.38  insn per cycle           ( +-  0.00% )
       134,549,173      branches:u                                                    ( +-  0.00% )
            10,039      faults:u                                                      ( +-  0.00% )
                 0      migrations:u

          0.133171 +- 0.000463 seconds time elapsed  ( +-  0.35% )

https://bugs.python.org/issue33234

Loading
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

6 participants