Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

GH-109369: Add machinery for deoptimizing tier2 executors, both individually and globally.#110384

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.

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

Already on GitHub?Sign in to your account

Merged
markshannon merged 11 commits intopython:mainfromfaster-cpython:tier2-deopt-part-2
Oct 23, 2023

Conversation

@markshannon
Copy link
Member

This PR just provides the machinery; we still need to add support for exiting executors when theirvalid flag is falsified.

The implementation uses abloom filter.
The advantage of a bloom filter is that it requires no coupling between the executors and the objects they depend on, plus it is simpler to implement and uses less memory than a precise mapping.

I've chosen k = 6 and m = 256.
This should give a low enough false positive rate for most cases. We want to keep the false positive rate very low, as spurious de-optimizations could be expensive.

@markshannon
Copy link
MemberAuthor

Skipping news, as this an implementation detail

@gvanrossum
Copy link
Member

gvanrossum commentedOct 18, 2023•
edited
Loading

Okay, let me summarize what's here so we know I understand. Then I will start a code review.

  1. I've heard of Bloom filters and I understand their properties qualitatively (but I couldn't reproduce the math to evaluate which parameters we need).
  2. When a code object's bytecode is modified to add instrumentation, we need to invalidate the executors that could be affected.
  3. Because we can trace through functions, the list of executors in the code object is not enough to find all (potentially) affected executors. (Also because in theory an executor could be replaced by another while it's still running.)
  4. Wecould solve this problem using a data structure where each code object has an list of references to executors.
  5. (In fact, code objects can already have an array of references to executors, when they contain ENTER_EXECUTOR instructions. Though reusing this feels wrong.)
  6. Because executors may live shorter than the code objects they depend on, we'd have to manipulate the list when an executor is finalized, which means there would have to be a list of links from the executor back to its dependent code objects.
  7. A collection of weak references (presumably a weak set) from code objects to executors would do nicely. (We'd have to enable weak refs to executors, but that's straightforward.)
  8. However, that's a fairly heavy-weight data structure.
  9. Instead, we use a Bloom filter, which only occupies a fixed amount of space per executor (32 bytes, for our chosen size of 256 bits), and no space per code object. Presumably there are more code objects than executors, because only hot code gets an executor. (Are we collecting data on this?)
  10. The results are only probabilistic, but at worst we invalidate a few executors too many, so correctness is preserved.
  11. Now, OTOH, we have to have a data structure that lets us walk all executors. The current PR uses a doubly-linked list (so deleting an executor is quick), with a list head in the interpreter data structure (code objects and executors can't cross interpreters). There's a comment suggesting we could use something better performing (a kind of tree?) in the future. The nice thing about the doubly-linked list is that each executor is its own list node, so the cost is just two pointers per executor.

All in all I think this is a fine plan.

Copy link
Member

@gvanrossumgvanrossum left a comment

Choose a reason for hiding this comment

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

This is cool, a rare excursion to classic data structures! I'm not sure, but I worry about a bug in the linked list code when unlinking the head node promotes another node to being the head; see comment inunlink_executor().

@markshannonmarkshannon merged commit52e902c intopython:mainOct 23, 2023
@brandtbucher
Copy link
Member

brandtbucher commentedOct 24, 2023•
edited
Loading

It looks like this PR introduced refleaks and assertion failures when runningtest_embed with tier two enabled:

======================================================================FAIL: test_forced_io_encoding (test.test_embed.EmbeddingTests.test_forced_io_encoding)----------------------------------------------------------------------Traceback (most recent call last):  File "/home/brandtbucher/cpython/Lib/test/test_embed.py", line 219, in test_forced_io_encoding    out, err = self.run_embedded_interpreter("test_forced_io_encoding", env=env)               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^  File "/home/brandtbucher/cpython/Lib/test/test_embed.py", line 113, in run_embedded_interpreter    self.assertEqual(p.returncode, returncode,AssertionError: -6 != 0 : bad returncode -6, stderr is "_testembed: Objects/dictobject.c:938: unicodekeys_lookup_unicode: Assertion `PyUnicode_CheckExact(ep->me_key)' failed.\n"======================================================================FAIL: test_run_main_loop (test.test_embed.EmbeddingTests.test_run_main_loop)----------------------------------------------------------------------Traceback (most recent call last):  File "/home/brandtbucher/cpython/Lib/test/test_embed.py", line 326, in test_run_main_loop    out, err = self.run_embedded_interpreter("test_run_main_loop")               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^  File "/home/brandtbucher/cpython/Lib/test/test_embed.py", line 113, in run_embedded_interpreter    self.assertEqual(p.returncode, returncode,AssertionError: -6 != 0 : bad returncode -6, stderr is "_testembed: Objects/dictobject.c:938: unicodekeys_lookup_unicode: Assertion `PyUnicode_CheckExact(ep->me_key)' failed.\n"======================================================================FAIL: test_init_is_python_build_with_home (test.test_embed.InitConfigTests.test_init_is_python_build_with_home)----------------------------------------------------------------------Traceback (most recent call last):  File "/home/brandtbucher/cpython/Lib/test/test_embed.py", line 1375, in test_init_is_python_build_with_home    self.check_all_configs("test_init_is_python_build", config,  File "/home/brandtbucher/cpython/Lib/test/test_embed.py", line 794, in check_all_configs    out, err = self.run_embedded_interpreter(testname,               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^  File "/home/brandtbucher/cpython/Lib/test/test_embed.py", line 113, in run_embedded_interpreter    self.assertEqual(p.returncode, returncode,AssertionError: -6 != 0 : bad returncode -6, stderr is "_testembed: Objects/dictobject.c:938: unicodekeys_lookup_unicode: Assertion `PyUnicode_CheckExact(ep->me_key)' failed.\n"======================================================================FAIL: test_no_memleak (test.test_embed.MiscTests.test_no_memleak) (frozen_modules='off', stmt='pass')----------------------------------------------------------------------Traceback (most recent call last):  File "/home/brandtbucher/cpython/Lib/test/test_embed.py", line 1820, in test_no_memleak    self.assertEqual(refs, 0, out)AssertionError: 11 != 0 : [11 refs, 11 blocks]======================================================================FAIL: test_no_memleak (test.test_embed.MiscTests.test_no_memleak) (frozen_modules='on', stmt='pass')----------------------------------------------------------------------Traceback (most recent call last):  File "/home/brandtbucher/cpython/Lib/test/test_embed.py", line 1820, in test_no_memleak    self.assertEqual(refs, 0, out)AssertionError: 11 != 0 : [11 refs, 11 blocks]======================================================================FAIL: test_no_memleak (test.test_embed.MiscTests.test_no_memleak) (frozen_modules='off', stmt='import __hello__')----------------------------------------------------------------------Traceback (most recent call last):  File "/home/brandtbucher/cpython/Lib/test/test_embed.py", line 1820, in test_no_memleak    self.assertEqual(refs, 0, out)AssertionError: 11 != 0 : [11 refs, 11 blocks]======================================================================FAIL: test_no_memleak (test.test_embed.MiscTests.test_no_memleak) (frozen_modules='on', stmt='import __hello__')----------------------------------------------------------------------Traceback (most recent call last):  File "/home/brandtbucher/cpython/Lib/test/test_embed.py", line 1820, in test_no_memleak    self.assertEqual(refs, 0, out)AssertionError: 11 != 0 : [11 refs, 11 blocks]----------------------------------------------------------------------

I'm looking into it more now, but is there anything obvious to either of you that may be causing this?

@gvanrossum
Copy link
Member

Possibly the refleaks might be cured by increasing the warmup count (changing the-R parameter and the expected output correspondingly). This has happened a few times before.

No idea about the assertion failure.

void
_Py_Executor_DependsOn(_PyExecutorObject*executor,void*obj)
{
assert(executor->vm_data.valid= true);
Copy link
Member

Choose a reason for hiding this comment

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

Not the issue, but something I noticed while combing over this:

Suggested change
assert(executor->vm_data.valid= true);
assert(executor->vm_data.valid== true);

@gvanrossum
Copy link
Member

See#111339 for the test_embed crashes etc.

aisk pushed a commit to aisk/cpython that referenced this pull requestFeb 11, 2024
@markshannonmarkshannon deleted the tier2-deopt-part-2 branchAugust 6, 2024 10:17
Glyphack pushed a commit to Glyphack/cpython that referenced this pull requestSep 2, 2024
Sign up for freeto join this conversation on GitHub. Already have an account?Sign in to comment

Reviewers

@gvanrossumgvanrossumgvanrossum left review comments

@brandtbucherbrandtbucherbrandtbucher left review comments

Assignees

No one assigned

Labels

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

3 participants

@markshannon@gvanrossum@brandtbucher
[8]ページ先頭
©2009-2025 Movatter.jp