8000 bpo-43574: Dont overallocate list literals by chadnetzer · Pull Request #24954 · python/cpython · GitHub
[go: up one dir, main page]
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
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
Update test_overallocation of empty list append()
  • Loading branch information
@chadnetzer
chadnetzer committed Apr 4, 2021
commit 4336cc6060188b1af9976dd785696b53b865031e
12 changes: 11 additions & 1 deletion Lib/test/test_list.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -224,7 +224,8 @@ def test_overallocation(self):
overalloc_amts = []
for literal in test_literals:
Copy link
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.

Copy link
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.
# of known size use the same amount of allocation. It will be
# verified later that no over-allocation occurs for list literals.
Copy link
Member

Choose a reason for hiding this comment

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

This comment says "verified later", but I see no specific test of no-over-allocation of list literals. There is SizeofTest in test_sys.py but it only tests two literal lengths.
I would imagine this kind of test:

prev_literal = None
for literal in [[] + test_literals]:
    if prev_literal is not None
        # Allocation of literal N uses one more pointer than allocation of literal N-1
        self.assertEqual(sizeof(literal), sizeof(prev_literal) + struct.calcsize('P'))
    prev_literal = literal

Copy link
Author

Choose a reason for hiding this comment

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

Yes, I should have said "verified below", ie. in same test, after the loop. It's an implicit test, though, since with the current over-allocation strategy, the list capacity can sometimes equal list length, so it's not universally true that each list-literal will have less memory allocated than a normal list of equivalent length. So it only can test that at least sometimes the list-literals are created with less capacity then a grown list of equivalent length.

I was avoiding a direct test of memory usage, like you propose, just to keep things general. But I can certainly add such a direct test, which (afaict) is really the only way to test that all the list-literals are being created without over-allocation.

Copy link
Author

Choose a reason for hiding this comment

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

@pitrou I ran with your idea, and added a direct test of the memory allocated for a list-literal, which also let me remove the confusing wording about verifying "later", since that's no longer the case. Thanks for the suggestion.

self.assertEqual(sizeof(literal), sizeof(list(literal)))
self.assertEqual(sizeof(literal), sizeof(list(tuple(literal))))

Expand All @@ -239,6 +240,15 @@ def test_overallocation(self):
# Confirm that over-allocation occurs at least some of the time.
self.assertEqual(True, any(x>0 for x in overalloc_amts))
Copy link
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.


# Empty lists should overallocate on initial append/insert (unlike
Copy link
Member

Choose a reason for hiding this comment

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

Turn this bit into an additional test method.

# list-literals)
l1 = []
l1.append(1)
self.assertGreater(sizeof(l1), sizeof([1]))
l2 = []
l2.insert(0, 1)
self.assertGreater(sizeof(l2), sizeof([1]))

def test_count_index_remove_crashes(self):
# bpo-38610: The count(), index(), and remove() methods were not
# holding strong references to list elements while calling
Expand Down
0