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-98831: Simple input-output stack effects#99120

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
gvanrossum merged 22 commits intopython:mainfromgvanrossum:stack-effect
Nov 8, 2022

Conversation

gvanrossum
Copy link
Member

@gvanrossumgvanrossum commentedNov 5, 2022
edited
Loading

No arrays; no conditionals; no types; no cache effects.

No arrays; no conditionals; no types; no cache effects.
// stack effect: (__0--)
inst(BINARY_OP_MULTIPLY_INT) {
instr(BINARY_OP_MULTIPLY_INT, (left, right--prod)) {
// TODO: Don't pop from the stack before DEOPF_IF() calls.
Copy link
Member

Choose a reason for hiding this comment

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

Could you generate peeks at the beginning of the instruction and pops at the end just before the pushes?

Copy link
MemberAuthor

Choose a reason for hiding this comment

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

Yeah, that's why this is still a draft PR. :-)

@gvanrossum
Copy link
MemberAuthor

@brandtbucher@markshannon: In bytecodes.c I now get red wiggles on every use of a variable defined through a stack effect (since thePyObject *value; (etc.) is not in the instruction body any more). It's particularly annoying when it occurs in a macro likePy_DECREF(value) -- the wiggle shows onPy_DECREF. Any suggestions?

@gvanrossum
Copy link
MemberAuthor

@markshannon I have some questions about howERROR_IF() should work. Your spec says "If anERROR_IF occurs, all values will be removed from the stack." It's easy enough to add aSTACK_SHRINK() call (see latest code in generated_cases.c.h), but I'm not sure about whose responsibility it should be toDECREF() those variables.In practice, in the dozen or so instructions I've converted so far, whenERROR_IF() is called the code has already calledDECREF(). Example definition:

        instr(UNARY_POSITIVE, (value -- res)) {            res = PyNumber_Positive(value);            Py_DECREF(value);            ERROR_IF(res == NULL, error);        }

This expands to the following:

        TARGET(UNARY_POSITIVE) {            PyObject *value = PEEK(1);            PyObject *res;            res = PyNumber_Positive(value);            Py_DECREF(value);            if (res == NULL) { STACK_SHRINK(1); goto error; }            POKE(1, res);            DISPATCH();        }

Shall we make this part of the spec forERROR_IF(), that you must call it after "consuming" all the inputs?

@brandtbucher
Copy link
Member

brandtbucher commentedNov 5, 2022
edited
Loading

Perhaps we could makeinst a variadic macro that turns a list of stack items into a declaration list? Downside is that you need some marker to separate in/out parameters, and handling braces might get trickier.

On my phone now, but something like:

typedefPyObject*_dummy_stack_item;#defineinst_begin(NAME, ...)          \    case (NAME): {                     \        _dummy_stack_item __VA_ARGS__;#defineinst_end }inst_begin(BINARY_OP,lhs,rhs,_,res)// Implementation goes here...inst_end

if (TOP() == NULL) {
goto error;
}
ERROR_IF(TOP() == NULL, error);
Copy link
Member

Choose a reason for hiding this comment

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

TOP() —> res

@gvanrossum
Copy link
MemberAuthor

gvanrossum commentedNov 7, 2022
edited
Loading

Some notes after converting a few basic instructions (and failing to convert a few outliers).

  • Converting "raw" instruction definitions (with PUSH()/POP() or custom stack operations) to streamlined DSL with input and output stack effects is a slow manual process that requires careful review (e.g. the mistake that Irit found).
  • So far, every few instructions I converted required changes to the code generator.
  • The code generator needs to be refactored to make future changes easier.
  • I haven't even started to think about how to implement array and conditional stack effects or cache streams.
  • The families are currently not read by the code generator. We can address this once we need them.
  • For some reason I no longer see red wiggly underlines in bytecodes.c. (EDIT: After closing and reopening the file they are back.)
  • There are some instructions that don't seem to fit in the DSL.
    • PUSH_NULL must wait until I've implemented types, since it pushes a NULL.
    • LIST_APPEND and SET_ADD dig up a stack entry that occurs 'oparg' deep.
    • Opcodes like BINARY_SUBSCR_ADAPTIVE are problematic since they have special exits (DISPATCH_SAME_OPARG and GO_TO_INSTRUCTION). We may have to rethink such exits.

At this point I think the way forward is to merge this and then iterate, leaving the hardest cases for last.

@gvanrossumgvanrossum marked this pull request as ready for reviewNovember 7, 2022 08:11
Copy link
Member

@markshannonmarkshannon left a comment

Choose a reason for hiding this comment

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

No need to justify not adding more features; smaller PRs are better. There is no need to convert all the instructions at once.
Let's add features to the code generator as we actually need them.

Have you benchmarked this?
Some of the instructions, particularly theBINARY_OP ones have been quite sensitive to minor code re-orderings.

Wiggly lines can be fixed by adding dummy static definitions to the top of bytecodes.c

JUMPBY(INLINE_CACHE_ENTRIES_BINARY_OP);
}

// stack effect: (__0 -- )
inst(BINARY_OP_INPLACE_ADD_UNICODE) {
// This is a weird one. It's a super-instruction for
Copy link
Member

Choose a reason for hiding this comment

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

Maybe drop the "This is a weird one."
It is unusual, but its there for a good reason, which is to maintain the historical behavior thats += ... in a loop is not quadratic.

predictions = set()
for inst in instrs:
for target in re.findall(r"(?:PREDICT|GO_TO_INSTRUCTION)\((\w+)\)", inst.block.text):
def write_instr(instr: InstDef, predictions: set[str], indent: str, f: TextIO, dedent: int = 0):
Copy link
Member

Choose a reason for hiding this comment

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

Note for future PRs.
We need to factor out the three parts:

  • analysis
  • translation
  • output

# Write the body
ninputs = len(instr.inputs or ())
for line in blocklines:
if m := re.match(r"(\s*)ERROR_IF\(([^,]+), (\w+)\);\s*$", line):
Copy link
Member

Choose a reason for hiding this comment

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

See comment in generated_cases.c.h about introducing code into theif (cond) goto... code.

Py_DECREF(container);
if (res == NULL) { STACK_SHRINK(3); goto error; }
Copy link
Member

Choose a reason for hiding this comment

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

Anything more thanif (cond) goto ... introduces extra jumps around the conditional block and may slow things down.
E.g.

if (res==NULL) {STACK_SHRINK(3);     gotoerror; }

will be lowered to something like:

if (res!=NULL) gotonext;STACK_SHRINK(3);   gotoerror;next:

The C compilermight move theSTACK_SHRINK(3); goto error; out of line, but I think it better to do this in the code generator. Something like:

if (res==NULL) gotopop3_error;...pop3_error:STACK_SHRINK(1);pop2_error:STACK_SHRINK(1);pop_error:STACK_SHRINK(1);error:   ...

@gvanrossum
Copy link
MemberAuthor

I have benchmark results (thanks@brandtbucher!). Bottom line, it's a wash.

We compared three commits:

The second and third both are 1% faster than the baseline. This suggests that there is no measurable effect from just this PR, or from the creation of super-instructions (which was merged into this commit from main, but not included in Mark's PEP 479 changes).
output.txt

I am going ahead with merging this.

@gvanrossumgvanrossum merged commitf1a6546 intopython:mainNov 8, 2022
@gvanrossumgvanrossum deleted the stack-effect branchNovember 8, 2022 16:23
Sign up for freeto join this conversation on GitHub. Already have an account?Sign in to comment
Reviewers

@iritkatrieliritkatrieliritkatriel left review comments

@markshannonmarkshannonmarkshannon left review comments

@brandtbucherbrandtbucherAwaiting requested review from brandtbucher

Assignees
No one assigned
Labels
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

5 participants
@gvanrossum@brandtbucher@iritkatriel@markshannon@bedevere-bot

[8]ページ先頭

©2009-2025 Movatter.jp