◐ Shell
reader mode source ↗
Skip to content

GH-98363: Presize the list for batched()#98419

Merged
rhettinger merged 6 commits into
python:mainfrom
rhettinger:better_batched
Oct 20, 2022
Merged

GH-98363: Presize the list for batched()#98419
rhettinger merged 6 commits into
python:mainfrom
rhettinger:better_batched

Conversation

@rhettinger

@rhettinger rhettinger commented Oct 18, 2022 •
edited by bedevere-bot
Loading

Copy link
Copy Markdown
Contributor

Presizing the result lists saves space from list over-allocation and is faster than the PyList_Append() approach.

This is a short PR but it took a while to figure out that PyList_GetSlice() would make short work of the problem. Ideally, we need something like _PyTuple_Resize() to resize the list inplace using a realloc() and updating the allocated field.

@rhettinger rhettinger added performance Performance or resource usage skip news labels Oct 18, 2022
@rhettinger rhettinger requested a review from sweeneyde October 18, 2022 23:09
@rhettinger rhettinger added the 🔨 test-with-buildbots Test PR w/ buildbots; report in status section label Oct 19, 2022
@bedevere-bot

bedevere-bot commented Oct 19, 2022

Copy link
Copy Markdown

🤖 New build scheduled with the buildbot fleet by @rhettinger for commit fd5b508 🤖

If you want to schedule another build, you need to add the ":hammer: test-with-buildbots" label again.

@bedevere-bot bedevere-bot removed the 🔨 test-with-buildbots Test PR w/ buildbots; report in status section label Oct 19, 2022
sweeneyde
sweeneyde approved these changes Oct 20, 2022
View reviewed changes

@sweeneyde sweeneyde left a comment

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.

Hide comment

Regardless of the decision about Py_CLEAR, I think this is a good improvement.

Out of curiosity, before this PR, I measured consume(batched(repeat(None, 1_000_000), 100)) to have a bimodal distribution of timings, with about half of runs at 41ms and half at 8ms (cache effects?). After this PR, I measured about 3ms consistently. This was on Windows, without PGO.

@rhettinger rhettinger merged commit c1e02d4 into python:main Oct 20, 2022
@rhettinger

rhettinger commented Oct 20, 2022 •
edited
Loading

Copy link
Copy Markdown
Contributor Author

Thanks for the interesting line of thought. I like having this match the pure python equivalent. Also, I don't think that it would ever matter. Code like enumerate() and zip() has been deployed for 20 years with no ill effects. More-itertools has iterators than also succumb to your "strange iterator" and no one seems have had an issue.

The likely reason that you're getting a bimodal timing distribution is that PyList_Append() calls realloc() which uncontrollably runs in either of two modes, fast for an inplace resize when the memory can be extended inplace, and slow for a resize that has to move all the data because there isn't room for an inplace resize. The new code doesn't have that issue because PyList_New() makes a single call to malloc() which never moves data. The new code also has better memory utilization because it never returns an overallocated list.

carljm added a commit to carljm/cpython that referenced this pull request Oct 20, 2022
@carljm
Merge branch 'main' into typewatch …
8bba5da 
* main: (40 commits)
  pythongh-98461: Fix source location in comprehensions bytecode (pythonGH-98464)
  pythongh-98421: Clean Up PyObject_Print (pythonGH-98422)
  pythongh-98360: multiprocessing now spawns children on Windows with correct argv[0] in virtual environments (pythonGH-98462)
  CODEOWNERS: Become a typing code owner (python#98480)
  [doc] Improve logging cookbook example. (pythonGH-98481)
  Add more tkinter.Canvas tests (pythonGH-98475)
  pythongh-95023: Added os.setns and os.unshare functions (python#95046)
  pythonGH-98363: Presize the list for batched() (pythonGH-98419)
  pythongh-98374: Suppress ImportError for invalid query for help() command. (pythongh-98450)
  typing tests: `_overload_dummy` raises `NotImplementedError`, not `RuntimeError` (python#98351)
  pythongh-98354: Add unicode check for 'name' attribute in _imp_create_builtin (pythonGH-98412)
  pythongh-98257: Make _PyEval_SetTrace() reentrant (python#98258)
  pythongh-98414: py.exe launcher does not use defaults for -V:company/ option (pythonGH-98460)
  pythongh-98417: Store int_max_str_digits on the Interpreter State (pythonGH-98418)
  Doc: Remove title text from internal links (python#98409)
  [doc] Refresh the venv introduction documentation, and correct the statement about VIRTUAL_ENV (pythonGH-98350)
  Docs: Bump sphinx-lint and fix unbalanced inline literal markup (python#98441)
  pythongh-92886: Replace assertion statements in `handlers.BaseHandler` to support running with optimizations (`-O`) (pythonGH-93231)
  pythongh-92886: Fix tests that fail when running with optimizations (`-O`) in `_test_multiprocessing.py` (pythonGH-93233)
  pythongh-92886: Fix tests that fail when running with optimizations (`-O`) in `test_py_compile.py` (pythonGH-93235)
  ...
@rhettinger rhettinger deleted the better_batched branch October 20, 2022 21:38
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@sweeneyde sweeneyde sweeneyde approved these changes

Assignees

No one assigned

Labels

performance Performance or resource usage skip news

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

3 participants

@rhettinger @bedevere-bot @sweeneyde