Skip to content

bpo-43574: Dont overallocate list literals #24954

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
chadnetzer wants to merge 11 commits into from
Closed

bpo-43574: Dont overallocate list literals #24954

Changes from 1 commit
Commits
Show all changes
11 commits
Select commit Hold shift + click to select a range
4dbee9a
Add testcase for bpo-43574 list overallocaton
chadnetzer Mar 21, 2021
5b31470
Don't overallocate when extending an empty list
chadnetzer Mar 21, 2021
172f2c0
Skip overallocation calc when not overallocating
chadnetzer Mar 21, 2021
d76ae2a
Fix list_extend() init list changes to PEP-7 form
chadnetzer Mar 22, 2021
7aad246
bpo-43574: Add NEWS
chadnetzer Mar 22, 2021
7c20c6c
Add more list overallocation regression tests
chadnetzer Mar 22, 2021
7be3ae8
Put common-case first in logical-or list_resize()
chadnetzer Mar 22, 2021
7436223
Adjust NEWS entry language based on PR feedback
chadnetzer Mar 23, 2021
657d51f
Allow empty list append/insert to overallocate
chadnetzer Mar 24, 2021
4336cc6
Update test_overallocation of empty list append()
chadnetzer Mar 26, 2021
19d4374
Add direct test of list-literal non-overallocation
chadnetzer Apr 5, 2021
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
Add more list overallocation regression tests 
Ensure that lists initialized from both list-literals and iterables of known
length are initialized without over-allocation, by comparing them with
allocation of lists initialized from an unknown size where over-allocation is
expected.
  • Loading branch information
@chadnetzer
chadnetzer committed Mar 22, 2021
commit 7c20c6cc15873cbbc7f94c06727ce1f85c27b855
46 changes: 40 additions & 6 deletions Lib/test/test_list.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -198,12 +198,46 @@ def test_preallocation(self):

@cpython_only
def test_overallocation(self):
iterable = [1,2]
self.assertEqual(sys.getsizeof(iterable), sys.getsizeof(list(iterable)))

# bpo-43574: Don't overallocate for list literals
iterable = [1,2,3]
self.assertEqual(sys.getsizeof(iterable), sys.getsizeof(list(iterable)))
# bpo-33234: Don't overallocate when initialized from known lengths
# bpo-38373: Allows list over-allocation to be zero for some lengths
# bpo-43574: Don't overallocate for list-literals
sizeof = sys.getsizeof

# First handle empty list and empty list-literal cases. Should have no

@gpshead gpshead Apr 11, 2021

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

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

make this set of initial assertions into its own test method.

# overallocation, including init from iterable of unknown length.
self.assertEqual(sizeof([]), sizeof(list()))
self.assertEqual(sizeof([]), sizeof(list(tuple())))
self.assertEqual(sizeof([]), sizeof(list(x for x in [])))

# Must use actual list-literals to test the overallocation behavior of
# compiled list-literals as well as those initialized from them.
test_literals = [
[1],
[1,2],
[1,2,3], # Literals of length > 2 are special-cased in compile
[1,2,3,4],
[1,2,3,4,5,6,7],
[1,2,3,4,5,6,7,8], # bpo-38373: Length 8 init won't over-alloc
[1,2,3,4,5,6,7,8,9],
]

overalloc_amts = []
for literal in test_literals:

@gpshead gpshead Apr 11, 2021

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

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

no action required: meta: this is where I really wish we had an absltest.paramtereize or pytest.mark.parameterize available in the stdlib. it'd run all of these as unique tests with appropriate names instead of a loop that prevents others from running upon first failure.

@sweeneyde sweeneyde Apr 11, 2021

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

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

I think unittest.subTest() displays parameters on the failing subtests and keeps running through each even on failure.

# Ensure that both list literals, and lists made from an iterable
# of known size use the same amount of allocation.
self.assertEqual(sizeof(literal), sizeof(list(literal)))
self.assertEqual(sizeof(literal), sizeof(list(tuple(literal))))

# By contrast, confirm that non-empty lists initialized from an
# iterable where the length is unknown at the time of
# initialization, can be overallocated.
iterated_list = list(x for x in literal)
overalloc_amts.append(sizeof(iterated_list) - sizeof(literal))
self.assertGreaterEqual(sizeof(iterated_list), sizeof(literal))

# bpo-38373: initialized or grown lists are not always over-allocated.
# Confirm that over-allocation occurs at least some of the time.
self.assertEqual(True, any(x>0 for x in overalloc_amts))

@gpshead gpshead Apr 11, 2021

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

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

add msg=repr(overalloc_amts) to aid debugging if this fails.


def test_count_index_remove_crashes(self):
# bpo-38610: The count(), index(), and remove() methods were not
Expand Down