[issue33234] Improve list() pre-sizing for inputs with known lengths

[STINNER Victor]

STINNER Victor  added the comment:

See also bpo-14126: "Speed up list comprehensions by preallocating the list 
where possible".

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33234] Improve list() pre-sizing for inputs with known lengths

[Eric Snow]

Eric Snow  added the comment:

Possible backward incompatibility caused by this issue: issue39829

--
nosy: +eric.snow

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33234] Improve list() pre-sizing for inputs with known lengths

[Nicholas Musolino]

Change by Nicholas Musolino :


--
pull_requests: +14316
pull_request: https://github.com/python/cpython/pull/14432

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33234] Improve list() pre-sizing for inputs with known lengths

[miss-islington]

miss-islington  added the comment:


New changeset e182318e6a473e6e9341f1aab8e49f2b1035c674 by Miss Islington (bot) 
(Raymond Hettinger) in branch 'master':
bpo-33234: Add another attribution in Whatsnew (GH-11899)
https://github.com/python/cpython/commit/e182318e6a473e6e9341f1aab8e49f2b1035c674


--
nosy: +miss-islington

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33234] Improve list() pre-sizing for inputs with known lengths

[Raymond Hettinger]

Change by Raymond Hettinger :


--
pull_requests: +11926

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33234] Improve list() pre-sizing for inputs with known lengths

[Pablo Galindo Salgado]

Change by Pablo Galindo Salgado :


--
resolution:  -> fixed
stage: patch review -> resolved
status: open -> closed

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33234] Improve list() pre-sizing for inputs with known lengths

[Pablo Galindo Salgado]

Pablo Galindo Salgado  added the comment:


New changeset 0e5f771f38138714415f665651de7e674fcebc38 by Pablo Galindo (Sergey 
Fedoseev) in branch 'master':
bpo-33234: Simplify list_preallocate_exact() (GH-11220)
https://github.com/python/cpython/commit/0e5f771f38138714415f665651de7e674fcebc38


--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33234] Improve list() pre-sizing for inputs with known lengths

[Sergey Fedoseev]

Change by Sergey Fedoseev :


--
pull_requests: +10490

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33234] Improve list() pre-sizing for inputs with known lengths

[Pablo Galindo Salgado]

Pablo Galindo Salgado  added the comment:


New changeset c61e229d2a4c54ffb4153e1f0f48126ba33c9cbf by Pablo Galindo in 
branch 'master':
bpo-33234: Add exact allocation optimization to lists in What's New (GH-10200)
https://github.com/python/cpython/commit/c61e229d2a4c54ffb4153e1f0f48126ba33c9cbf


--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33234] Improve list() pre-sizing for inputs with known lengths

[Pablo Galindo Salgado]

Pablo Galindo Salgado  added the comment:

>Oh. Can you please document the optimization in the following doc as well?

Sure! Opened https://github.com/python/cpython/pull/10200 to address that. :)

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33234] Improve list() pre-sizing for inputs with known lengths

[Pablo Galindo Salgado]

Change by Pablo Galindo Salgado :


--
pull_requests: +9518

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33234] Improve list() pre-sizing for inputs with known lengths

[STINNER Victor]

STINNER Victor  added the comment:

> bpo-33234 Improve list() pre-sizing for inputs with known lengths (GH-9846)

Oh. Can you please document the optimization in the following doc as well?
https://docs.python.org/dev/whatsnew/3.8.html#optimizations

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33234] Improve list() pre-sizing for inputs with known lengths

[Pablo Galindo Salgado]

Pablo Galindo Salgado  added the comment:


New changeset 372d705d958964289d762953d0a61622755f5386 by Pablo Galindo in 
branch 'master':
bpo-33234 Improve list() pre-sizing for inputs with known lengths (GH-9846)
https://github.com/python/cpython/commit/372d705d958964289d762953d0a61622755f5386


--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33234] Improve list() pre-sizing for inputs with known lengths

[Raymond Hettinger]

Change by Raymond Hettinger :


--
nosy: +tim.peters

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33234] Improve list() pre-sizing for inputs with known lengths

[Pablo Galindo Salgado]

Change by Pablo Galindo Salgado :


--
pull_requests: +9218

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33234] Improve list() pre-sizing for inputs with known lengths

[Pablo Galindo Salgado]

Pablo Galindo Salgado  added the comment:

@serhiy.storchaka @rhettinger @vstinner Should we better make the 
pre-allocation if the length of the iterable is known (so we call 
PyObject_Length and not PyObject_LengthHint)? This will keep the logic simpler 
(so not shrinking if PyObject_LengthHint gives more than the real length) and 
it will not be as expensive as calling PyObject_LengthHint.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33234] Improve list() pre-sizing for inputs with known lengths

[STINNER Victor]

STINNER Victor  added the comment:

Should we shrink the list of the length hint was way too big? For example, if 
the length hint was 100 but the final list of only 10. Should we shrink in that 
case?

I'm asking because it seems like Pablo's PR doesn't shrink the list in that 
case.

I wasn't sure so I checked, del shrinks the list if needed:

>>> x=list(range(1000))
>>> import sys
>>> sys.getsizeof(x)
9112
>>> del x[1:]
>>> sys.getsizeof(x)
96

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33234] Improve list() pre-sizing for inputs with known lengths

[STINNER Victor]

STINNER Victor  added the comment:

See also http://bugs.python.org/issue26814#msg264003 and bpo-26828.

--
nosy: +vstinner

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33234] Improve list() pre-sizing for inputs with known lengths

[Pablo Galindo Salgado]

Pablo Galindo Salgado  added the comment:

Microbenchmarked with @vstinner's perf module:

python -m perf timeit "list([0]*10)" -o new.json

checkout master and build

python -m perf timeit "list([0]*10)" -o old.json
python -m perf compare_to new.json old.json
Mean +- std dev: [new] 241 ns +- 3 ns -> [old] 243 ns +- 18 ns: 1.01x slower 
(+1%)
Not significant!

--
nosy: +pablogsal

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33234] Improve list() pre-sizing for inputs with known lengths

[Serhiy Storchaka]

Serhiy Storchaka  added the comment:

Calling PyObject_LengthHint() adds an overhead. It is significant for short 
sequences. I work on a patch that reduces it. PR 6493 adds the second call of 
PyObject_LengthHint() and increases the overhead.

As for this issue, in-place repeat overallocates too.

>>> a = [0]; a *= 10; getsizeof(a)
200

I think it would be better to make it not preallocating.

And maybe it would be worth to avoid overallocating if newsize > allocated + 
allocated/8 or something like.

--
nosy: +serhiy.storchaka

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33234] Improve list() pre-sizing for inputs with known lengths

[Pablo Galindo Salgado]

Change by Pablo Galindo Salgado :


--
keywords: +patch
pull_requests: +6190
stage:  -> patch review

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue33234] Improve list() pre-sizing for inputs with known lengths

[Raymond Hettinger]

New submission from Raymond Hettinger :

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

Python 3.8.0a0 (heads/master:091e95e900, Apr  5 2018, 09:48:33)
[Clang 9.1.0 (clang-902.0.39.1)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> from sys import getsizeof
>>> getsizeof([0] * 10)
144
>>> getsizeof(list([0] * 10))
200
>>> getsizeof(list(range(10)))
200

--
components: Interpreter Core
messages: 315006
nosy: rhettinger
priority: normal
severity: normal
status: open
title: Improve list() pre-sizing for inputs with known lengths
type: performance
versions: Python 3.8

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com