GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — GH-98831: Implement basic cache effects by gvanrossum · Pull Request #99313 · python/cpython

Conversation

@gvanrossum

@gvanrossum gvanrossum commented Nov 10, 2022 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Member

I apologize for the mess that generate_cases.py has become. I promise I will clean it up in the next PR.

This PR is a big step forwards though -- it supports cache effects and implements those for the BINARY_OP family (with one exception -- the "hemi-super-instruction" BINARY_OP_INPLACE_ADD_UNICODE). Check the generated code for the effects.

PS. Merge conflicts for Python/bytecodes.c are quite painful, it seems there are several cooks in this kitchen. :-)

  • Issue: Generate the interpreter #98831

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions
gvanrossum added 2 commits November 9, 2022 18:38
@gvanrossum
Support simple cache effects
9f15c4b
Had to refactor the parser a bit for this.
@gvanrossum
More BINARY_OP instructions
6189043
@bedevere-bot bedevere-bot mentioned this pull request Nov 10, 2022
Generate the interpreter #98831
Closed
@bedevere-bot bedevere-bot added the awaiting core review label Nov 10, 2022
@gvanrossum gvanrossum added the skip news label Nov 10, 2022
gvanrossum and others added 20 commits November 10, 2022 07:27
@gvanrossum
Merge remote-tracking branch 'origin/main' into cache-effects
f5e1aed
@gvanrossum
Tweak dummy definitions in bytecodes.c after merge
a8d608d
@vstinner @gvanrossum
pythongh-99300: Use Py_NewRef() in Objects/ directory (python#99332)
4ee85e7
Replace Py_INCREF() and Py_XINCREF() with Py_NewRef() and
Py_XNewRef() in C files of the Objects/ directory.
@vstinner @gvanrossum
pythongh-99300: Use Py_NewRef() in Objects/dictobject.c (python#99333)
873da31
Replace Py_INCREF() and Py_XINCREF() with Py_NewRef() and
Py_XNewRef() in Objects/dictobject.c.
@ericsnowcurrently @gvanrossum
pythongh-90110: Update the C-analyzer Tool (pythongh-99307)
e0ab5b8
@csuriano23 @kumaraditya303 @gvanrossum
pythongh-99277: remove older version of get_write_buffer_limits (py…
882fdec
…thon#99280)

Co-authored-by: Kumar Aditya <[email protected]>
@vfazio @gvanrossum
pythongh-99204: Calculate base_executable by alternate names in POSIX…
8226fb9
… venvs (pythonGH-99206)

Check to see if `base_executable` exists. If it does not, attempt
to use known alternative names of the python binary to find an
executable in the path specified by `home`.

If no alternative is found, previous behavior is preserved.

Signed-off-by: Vincent Fazio <[email protected]>

Signed-off-by: Vincent Fazio <[email protected]>
@brandtbucher @gvanrossum
pythonGH-99298: Don't perform jumps before error handling (pythonGH-9…
1aa0124
…9299)
@gvanrossum @brandtbucher
pythonGH-98831: Remove all remaining DISPATCH() calls from bytecodes.c (
d094e42
python#99271)

Also mark those opcodes that have no stack effect as such.

Co-authored-by: Brandt Bucher <[email protected]>
@gvanrossum
Remaining BINARY_OP family members
d3d907a
@gvanrossum
Uniformly skip 'unused' effects
0339a67
@gvanrossum
Remove superfluous asserts; fix one 'is not'
f3e7dd6
@gvanrossum
Make BINARY_OP result unused
e3ff6ac
@gvanrossum
Fix parser for family()
3db443a
@gvanrossum
Check family consistency
c58a85a
@gvanrossum
Add first family (binary_op)
756a41b
@gvanrossum
Add assert() to double-check cache struct size
48400ac
@gvanrossum
Merge commit '00ee6d506e' into cache-effects
433243a
@gvanrossum
Merge commit '694cdb24a6' into cache-effects
3d51484
@gvanrossum
Merge remote-tracking branch 'origin/main' into cache-effects
4d42a0a
@gvanrossum
gvanrossum marked this pull request as ready for review November 11, 2022 01:20
@gvanrossum
gvanrossum requested review from brandtbucher and markshannon November 11, 2022 02:34
@gvanrossum

gvanrossum commented Nov 11, 2022

Copy link
Copy Markdown
Member Author

PS. I didn't implement a family that actually uses the cache (the 'counter' doesn't count, it's special since it is written, which our DSL doesn't support). But I figured I'd stop here -- keeping these PRs open for a long time is hard work due to merge conflicts.

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@brandtbucher brandtbucher mentioned this pull request Nov 11, 2022
GH-98686: Get rid of BINARY_OP_GENERIC and COMPARE_OP_GENERIC #99399
Merged
@gvanrossum gvanrossum mentioned this pull request Nov 12, 2022
GH-98831: Refactor generate_cases.py #99408
Closed
@gvanrossum

gvanrossum commented Nov 13, 2022 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Member Author

PS. I didn't implement a family that actually uses the cache (the 'counter' doesn't count, it's special since it is written to, which our DSL doesn't support). But I figured I'd stop here -- keeping these PRs open for a long time is hard work due to merge conflicts.

Working on the refactor I now know for sure there are some bugs in that part. (EDIT: Fixed in GH-99408 but not here.)

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

markshannon
markshannon requested changes Nov 15, 2022
View reviewed changes

@markshannon markshannon left a comment

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

Maybe leave checking of families to another PR, and just implement stack effects in this PR?

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions
Comment thread Python/bytecodes.c Resolved

Uh oh!

There was an error while loading. Please reload this page.

Comment thread Python/bytecodes.c Resolved

Uh oh!

There was an error while loading. Please reload this page.

Comment thread Python/bytecodes.c Resolved

Uh oh!

There was an error while loading. Please reload this page.

Comment thread Tools/cases_generator/generate_cases.py Resolved

Uh oh!

There was an error while loading. Please reload this page.

@bedevere-bot bedevere-bot added awaiting changes and removed awaiting core review labels Nov 15, 2022
@bedevere-bot

bedevere-bot commented Nov 15, 2022

Copy link
Copy Markdown

When you're done making the requested changes, leave the comment: I have made the requested changes; please review again.

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@gvanrossum

gvanrossum commented Nov 15, 2022

Copy link
Copy Markdown
Member Author

I have made the requested changes; please review again

(Well, I've answered everything and would like to merge this as-is so Brandt can continue on GH-99399.)

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@bedevere-bot bedevere-bot added awaiting change review and removed awaiting changes labels Nov 15, 2022
@bedevere-bot

bedevere-bot commented Nov 15, 2022

Copy link
Copy Markdown

Thanks for making the requested changes!

@markshannon: please review the changes made to this pull request.

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@bedevere-bot
bedevere-bot requested a review from markshannon November 15, 2022 15:59
brandtbucher
brandtbucher approved these changes Nov 16, 2022
View reviewed changes

@brandtbucher brandtbucher left a comment

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

Looks good, thanks!

I've sprinked a bunch of random notes and questions throughout. Feel free to fix now, later, or never. :)

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions
Comment thread Tools/cases_generator/parser.py
def outputs(self):
return self.header.outputs
def outputs(self) -> list[StackEffect]:
# This is always true

@brandtbucher brandtbucher Nov 16, 2022

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

What's always true?

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

@gvanrossum gvanrossum Nov 16, 2022

Copy link
Copy Markdown
Member Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

isinstance(x, StackEffect). It's gone in the next refactor.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions
Comment thread Tools/cases_generator/generate_cases.py
for ceffect in cache:
if ceffect.name != "unused":
bits = ceffect.size * 16
f.write(f"{indent} PyObject *{ceffect.name} = read{bits}(next_instr + {cache_offset});\n")

@brandtbucher brandtbucher Nov 16, 2022

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

Not that it matters yet, but these are almost always fixed-width integer types, not objects (though we'll eventually want handling for objects too):

Suggested change
f.write(f"{indent} PyObject *{ceffect.name} = read{bits}(next_instr + {cache_offset});\n")
f.write(f"{indent} uint{bits}_t {ceffect.name} = read{bits}(next_instr + {cache_offset});\n")

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions
Comment thread Python/bytecodes.c
};


inst(BINARY_OP_MULTIPLY_INT, (left, right, unused/1 -- prod)) {

@brandtbucher brandtbucher Nov 16, 2022

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

Just my preference, but I sort of prefer a name like _ to a name like unused for our syntax here. I guess it just feels more "special", and doesn't distract:

Suggested change
inst(BINARY_OP_MULTIPLY_INT, (left, right, unused/1 -- prod)) {
inst(BINARY_OP_MULTIPLY_INT, (left, right, _/1 -- prod)) {

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions
Comment thread Python/bytecodes.c
}

inst(BINARY_OP_MULTIPLY_INT, (left, right -- prod)) {
family(binary_op, INLINE_CACHE_ENTRIES_BINARY_OP) = {

@brandtbucher brandtbucher Nov 16, 2022

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

Honestly, I don't think we really need the INLINE_CACHE_ENTRIES_WHATEVER stuff (or the asserts it produces) in this file anymore (they were originally added to simplify the JUMPBY(...) moves, but those are going to be generated now).

I feel like it sort of just complicates parsing and code generation for no real benefit... plus, we actually already have asserts to this effect in specialize.c where we ended up re-using these constants in some places.

Suggested change
family(binary_op, INLINE_CACHE_ENTRIES_BINARY_OP) = {
family(binary_op) = {

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions
Comment thread Python/bytecodes.c
Comment on lines 80 to +81
static PyObject *value, *value1, *value2, *left, *right, *res, *sum, *prod, *sub;
static PyObject *container, *start, *stop, *v;
static PyObject *container, *start, *stop, *v, *lhs, *rhs;

@brandtbucher brandtbucher Nov 16, 2022

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

:(

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions
Comment thread Tools/cases_generator/generate_cases.py
instr, predictions, indent, f,
cache_size=find_cache_size(instr, families)
)
effects_table[instr.name] = len(instr.inputs), len(instr.outputs), cache_offset

@brandtbucher brandtbucher Nov 16, 2022

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

Hm. This is a bit weird because it treats caches and stack items the same, which doesn't make much sense. It seems to me we'd want something that captures just stack effect and cache size:

Suggested change
effects_table[instr.name] = len(instr.inputs), len(instr.outputs), cache_offset
stack_pre = sum(isinstance(item, StackEffect) for item in instr.inputs)
stack_post = sum(isinstance(item, StackEffect) for item in instr.inputs)
effects_table[instr.name] = stack_post - stack_pre, cache_offset

(This will probably get more complicated as stack effects start getting more complicated...)

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions
Comment thread Tools/cases_generator/parser.py
Comment on lines +150 to +151
raise self.make_syntax_error(
f"Input {name!r} at pos {i} repeated in output at different pos {j}")

@brandtbucher brandtbucher Nov 16, 2022 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

Why is this bad? Seems useful for things like copies and swaps (unless the intention is to have the author assign the output to a new name anyways)?

Maybe it complicates refcounting somehow? Either way, might be worth a comment.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

@gvanrossum gvanrossum Nov 16, 2022

Copy link
Copy Markdown
Member Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

Good question. I thought this was in Mark's DSL spec but I can't find it; I probably just misread something. Intuitively, this rules out cases like

inst(FOO, (left, right -- right)) {
    DECREF(left);
}

which requires shifting right down by one unit, and that seems a bit unexpected (could be caused by a typo?). But you're right, it doesn't cause any complications in the code generator, we'll just generate code like

{
    PyObject *left = PEEK(2), *right = PEEK(1);
    DECREF(left);
    STACK_SHRINK(1);
    POKE(1, right);
}

I'll get rid of this check in the next refactor (it's in the wrong place anyway).

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions
Comment thread Tools/cases_generator/parser.py
break

def stack_effect(self) -> tuple[list[str], list[str]]:
def stack_effect(self) -> tuple[list[Effect], list[Effect]]:

@brandtbucher brandtbucher Nov 16, 2022

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

I didn't look too closely at anything below this line (not a parsing expert). I'm sure it works fine, though. :)

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

gvanrossum reacted with thumbs up emoji
All reactions
  • 👍 1 reaction
Comment thread Tools/cases_generator/parser.py
Comment on lines +256 to +260
while self.expect(lx.COMMA):
if tkn := self.expect(lx.IDENTIFIER):
members.append(tkn.text)
else:
break

@brandtbucher brandtbucher Nov 16, 2022

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

I find this control flow easier to follow:

Suggested change
while self.expect(lx.COMMA):
if tkn := self.expect(lx.IDENTIFIER):
members.append(tkn.text)
else:
break
while self.expect(lx.COMMA) and (tkn := self.expect(lx.IDENTIFIER)):
members.append(tkn.text)

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

@gvanrossum gvanrossum Nov 16, 2022

Copy link
Copy Markdown
Member Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

I'm not sure I agree. Your rewrite is more compact but makes it easy to overlook that this code accepts a trailing comma. The longer form makes you pause and notice that.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions
Comment thread Tools/cases_generator/parser.py
Comment on lines 181 to +183
if (tkn := self.expect(lx.IDENTIFIER)):
if self.expect(lx.LBRACKET):
if arg := self.expect(lx.IDENTIFIER):
if self.expect(lx.RBRACKET):
return f"{tkn.text}[{arg.text}]"
if self.expect(lx.TIMES):
if num := self.expect(lx.NUMBER):
if self.expect(lx.RBRACKET):
return f"{tkn.text}[{arg.text}*{num.text}]"
raise self.make_syntax_error("Expected argument in brackets", tkn)

return tkn.text
if self.expect(lx.CONDOP):
while self.expect(lx.CONDOP):
pass
return "??"
return None
if self.expect(lx.DIVIDE):
if num := self.expect(lx.NUMBER):

@brandtbucher brandtbucher Nov 16, 2022

Copy link
Copy Markdown
Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

I noticed that this file has pretty aggressive if nesting. Out of curiousity, any reason why you prefer not to combine many ifs into one test? Maybe it fits your mental model of the parser better?

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

@gvanrossum gvanrossum Nov 16, 2022

Copy link
Copy Markdown
Member Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

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

The latter, mostly. It makes it easier to add an else clause later. Also, I like to test only one condition per line. The parser does need a bit of cleanup, but it's clean enough for now.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions
@bedevere-bot bedevere-bot added awaiting merge and removed awaiting change review labels Nov 16, 2022
@gvanrossum
gvanrossum merged commit e37744f into python:main Nov 16, 2022
@bedevere-bot bedevere-bot removed the awaiting merge label Nov 16, 2022
@gvanrossum
gvanrossum deleted the cache-effects branch December 8, 2022 22:42
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@brandtbucher brandtbucher brandtbucher approved these changes
@markshannon markshannon Awaiting requested review from markshannon markshannon is a code owner

Uh oh!

There was an error while loading. Please reload this page.

Assignees

No one assigned

Labels

skip news

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

Uh oh!

There was an error while loading. Please reload this page.

8 participants

@gvanrossum @bedevere-bot @markshannon @brandtbucher @vstinner @ericsnowcurrently @csuriano23 @vfazio
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.