How CPython parser works, and how to make it work better
Skrobov, Artyom
How CPython parser works, and how to make it work better The part of CPython core that parses the Python source code is some very old and convoluted code: the time has proven its reliability, but few CPython hackers understand (or care) how it works, or even what exactly it does. There is, however, a good reason to care: for short-running scripts, the performance of CPython may easily be dominated by that of parsing the source code. The talk will describe the two parsers that are involved, it will explain how these two parsers build two different kinds of syntax trees, and then show how the structure of one of the trees can be amended to reduce its memory footprint threefold, with only minor changes necessary in its consumers. It will also suggest other, more invasive improvements, which can yield even better savings. The talk will assume fluency in C and a basic acquaintance with CPython core internals, and will give the attendees an introduction into hacking the parser, guiding their way through to the very tangible end result of reducing Python overall memory consumption by up to 30%, measured at standard micro-benchmarks
 So, hello. This is about some work that I did with my previous employer. When I left them, they asked me to remove the slides and not mention their name. So I'm here with no business affiliation. Unlike most talks in this conference, this is not about writing stuff with Python. This is about Python himself. And most specifically about the C Python, which is the reference implementation. And even more specifically about the parser, which is part of this implementation. So what is the Python parser? When I put Python parser into Google, this is the picture that came up. But actually, parser is the first stage of the interpreter, which converts the source code into parse tree, which the compiler then compiles into white code. And the white code is what the interpreter actually runs. Now what is Python parser like? Same as any mature programming language, it has a formal grammar, which looks something like this. If this link should open. Has a formally defined production, three start symbols for three different kinds of inputs. Every line defines a new non-terminal symbol, and the notation here is a bit more complicated than the BNF notation that grammar is usually written in. Something more like regular expressions. So we have something like plus modifiers and somewhere star modifiers for repetitions, as well as parentheses for grouping. And the other ingredient is the header file with the definition of all tokens. Python has 57 types of tokens, number 0 to 56. And the numbers above 256 are reserved for non-terminals, which are the ones that are defined in the grammar. Then we have a parser generator that based on the formal grammar and the token definition produces a file which looks like this. Basically it's just a definition of static data. It doesn't have any code in it. All it does is it defines the one DFA for every non-terminal that the grammar defines. So every DFA is defined as an array of states. Every state is defined as an array of arcs. And every arc has a label and destination state. Oh, sorry. I thought my screen is deplicated, but it's not really. Sorry. Did the previous files got missing again? Did you see the previous files that I was trying to show? Okay. Then I'll have to scroll back. This is what the grammar looks like with the productions and the right-hand sides that looks like regular expressions. And that's what the header file looks like with the token definitions. I don't know how to make it deplicated again. Let me try. Right. Now at least I see myself what I'm showing. So to go back, each state is defined as an array of arcs going out of this state. And each arc is defined as an... Now, each DFA is defined as an array of states. Each state is defined as an array of arcs going out of it. The first item is the arc label, which is more or less the same as the symbol number. And the second item is the destination state. And in fact, we have a special table which converts symbol IDs into arc labels because label number one corresponds to all keywords and all identifiers. So we also have to match which specific keyword it corresponds to so that each one of those get a different arc label number, even though they're all sharing the same symbol ID. And near the very end of this file, we have the definition of DFA's themselves. And for each DFA, we also have the start set, which shows which tokens the specific non-terminal can start with. And this is all sophisticated enough. So I prepared a short demonstration of how this works for a very simple Python program which looks like this. We parse it as a single input. So that's the production that we are parsing it according to. And our parse tree starts with the just root node of single input. And the DFA which parses single input is the DFA number zero, which looks like this. And in the initial state, which is state number zero, we have three arcs going out of it. So the first arc with label number two corresponds to new line. Next arc to simple statement, third arc to compound statement. And we are looking at the if token in the inputs. And according to the start sets, we know that simple statement cannot begin with if. If is not a new line, but compound statement can begin with if. So we transition along the last arc, add the compound statement node to the parse tree. And before we actually transition to state number two, we switch to the new DFA which parses compound statements. For compound statement, we have nine options. So in the initial state, we have nine arcs going out of it. Only the first arc, which is for if statement, can start with the if token. So we add if statement node to the parse tree, transition along this arc and so on. Now we switch to the DFA which parses if statement. It's sophisticated enough that it didn't fit on this slide. Because you see that its definition is also sophisticated having the parenthesis and repetitions and optional parts. In the initial state, we have only one arc, which with label 97 corresponds to the if token. Because it's a terminal symbol, we just add it to the parse tree, consume it from the input, switch to the next state, and stay in the same DFA. The next state once again has only one arc going out of it, but this one is for test. Non-terminal, the start set for test says that it can indeed begin with the number, such as 42. So we add the test node, switch to the DFA which parses test and so on. It goes for an awful long time before we actually get back into the same DFA. And now we are in state number two. Has one arc which consumes the colon token from the input, transitions to the next state. Once again, we have only one arc corresponding to suite. The start set confirms that suite can begin from print token. So we add a suite node to the parse tree, switch to DFA for suite. Once again, it takes an awful long time before we get here. And the interesting bit is now we have three arcs going out of the state number four. Arc with label 98 corresponding to the terminal L if, 99 to the terminal Ls, and the next token in the input is the new line. So it's neither of these. And the arc label zero means that it's a final state. So if we didn't match anything, which are just done with this DFA and go back to the previous one. So we go back to compound statement. We are ending up in state that only has zero arc, which means no matter what the next token in the input is, we are done. And going back to the previous one. Go back to the root DFA that we started from. There is only one arc with label number two, which is for new line. So we consume the new line from the input. Add a node to the parse tree. And the transition to state number one, which is final. So we are at end of input. We're in the final state of the root DFA, which means that the parsing succeeded. We are done. So what has just happened? We had a program which was 27 bytes long tokenized into seven tokens. And this is the parse tree which we produced for it. 64 nodes takes the 100 times as much memory as the source code itself. And it's not so much a tree as a bamboo stalk because it almost doesn't branch. We see that we have a huge, like, series of a dozen nodes with a single child each. All these because Python has a rather primitive parser which has to define grammar like this. It works. To actually see this instead of repeating all steps that I have shown just earlier. Yeah, that's more important. Because the parse tree can take 100 times as much memory as the source code. If I have a moderately big Python source file of, say, 30 megabytes, then the parser would not even be able to load it into memory because the syntax tree for it would be too big. So that was my motivation for this work. I had a 30 megabytes Python file and I couldn't possibly run it through Python. To show these CSTs, there is a standard module called parser. It can show you the CSTs realized into the structure of nested lists. Every list has two elements. The first one is the symbol ID. So it's 0 to 56 for terminals and something above 256 for non-terminals. And the second item is the token string for terminals, also a sub tree. Even in a nested list for non-terminals. The documentation for parser module actually says that people shouldn't use it because there is a better module called AST, which is a second kind of syntax tree that Python uses. This example shows what the AST looks like for the same example Python code. It's much more compact, it's almost human readable and the point is unlike CST which reflects how the program is represented in the source code, the AST reflects what the program actually intends to do. So it's actually the AST that the compiler runs on to generate the byte code. So the second kind of syntax tree actually also has a formal grammar, which is what this formal grammar looks like, a different format. Now we have each kind of AST node defining what its children should be, how many and what are their types. And the funny bit is that there is no parser generator which takes this file as input. This file is just formal documentation, but the parser is handwritten. Hope it opens. So this handwritten parser is actually 5200 lines long. It's a bit of very old and dusty code which dates from 2005 to 2007. Nobody touches it. Nobody remembers how it works. But the general attitude is if it ain't broke, don't fix it. It has been working for 10 years. Time has proven that it does work. Okay. And once again, the AST for our sample code is the very simple structure of nine nodes which I'm showing here. So this is what this second parser actually looks like. The example is a function that parses expert type of nodes. And what it does is it has a loop organized with the label and I go to from the middle of the function, something that the extra would not approve of. And what it actually does is that for each node which only has one child, it knows that there is nothing interesting for this node, so nothing to do. We just skip to the next node. So we see that two thirds of the nodes in the CST have one child. We don't do anything with them. We just skip to the next node. What I thought was why do we have all these useless nodes occupying the memory? If we can eliminate them at the time when we generate the CST, then at the same time we are saving two thirds of the memory. And also the second parser becomes simpler because it doesn't have to be concerned with skipping all these useless nodes. This is what an example of compressed CST looks like. It's actually small enough so it fits on one slide without scrolling. And at the same time we have this modified function which no longer has the awkward loop. Actually, it doesn't have any loops at all. What it does is that in each branch of the switch it can assert that the node has more than one child, meaning we can do something meaningful with this node and not just skip it. Now this shows the serialized CSTs before and after my fix. You can see that the CST has become so small that it almost becomes human readable. The catch here is that the only purpose of CST is to be parsed by the second parser into the AST and then it's discarded from the memory. We never use it again. So if we have a long running script such as web service, for example, that loads in a split second and then runs for hours and days, then it really doesn't matter how much memory the CST takes because it's only there for the first split second. On the other hand, if we have a system utility which runs for a split second and finishes immediately, then the performance of this utility would be dominated by the performance of the parser. That was my case. My script was just looking up a value in the 30 megabytes literal dictionary. Indeed with my fix to the Python parser, memory consumption of my script reduced by a factor of three. I was curious how my patch would affect other standard benchmarks. These are the results. One of them has shown improvement by a third. A few of them have shown around a dozen percent improvement. Nothing has got worse. But actually this benchmark package which I was using was replicated in October last year on the grounds that the results it was showing were inconsistent and meaningless for some purposes. I'm not a performance analysis person, so I don't know what it did and what it did wrong. But it had been superseded with the performance package and these are the results. Basically something got a little bit better, something got a little bit worse, but the big picture is that nothing changed. My intuition is that by performance intentionally runs a few warm-up loops before starting the timer and this way intentionally avoids the time in the loading and parsing of the source code. I didn't actually look inside by performance. It's big and sophisticated enough. But nevertheless even these results confirmed that my patch has no unintended side effects, it doesn't break anything and at the same time it enables use case which may not be relevant to most Python programmers, but at least if I bumped into it, maybe other people would bump into it as well. So then my desire was to share this patch with the community, get it included into Python, how somebody does this is it opens a bug in the bug tracker because that's where all the discussions happen, where all the reviews happen and there you also have a mailing list where you're allowed to send things once a month if your bug is not getting enough attention. So I opened two issues in the bug tracker and one of them, the second one of them, actually got accepted and committed. It took me three months waiting for a review and what it does was the second handwritten parser knows that the input that it parses always comes from the first parser. So it's guaranteed to conform with the first formal grammar. So it doesn't have to validate that it conforms to it. It knows for sure that for example for if statement node, the first child is always if tokened and the second child is always test. But parser module can take an arbitrary realized CST as input and run it through this second parser. And then if it doesn't conform to the formal grammar, the Python binary would just crash on invalid memory access. So they had to implement the validation for CST themselves. How they implemented this was like this. I'm showing just validation for three different types of nodes, but it was all more or less the same. They are checking that the number of the children in the node is correct, that the types of the children are correct, and then recursively descending into each child node and the call invalidation function for the child node. When I was looking at this code, which had to be updated with every change to the grammar too much, the updated grammar, I thought maybe we can auto-generate it from the grammar. We can write some DFA's which would traverse the CST to see if it's valid. And then what occurred to me is that we already have this DFA's, the DFA's which parser runs. We can just run them on the CST instead of the token stream of the input. So this way I could eliminate 2400 lines of handwritten code with just 70 lines of code for running the DFA's which we already have in Python parser and which are guaranteed to stay in sync with the parser because they are what the parser runs. But after three months in review, my other patch was rejected by Wido van Rossem himself saying that's because it's so big and sophisticated and nobody has volunteered to review it over three months. I shouldn't hold my breath for anybody to jump up and review it. If nobody cares as much as I do about running 30 megabytes Python scripts through the interpreter, then tough luck for me. Basically, this is the motivation while I'm here. Maybe you can enter this BPO 26415 back ticket, take a weekend to review it. And from that it's okay. Yet it committed. Yeah. Basically, I have explained what my patch does. But that's not all. If the only purpose of the CST is to get parsed by the second parser and discarded, why do we have to store it in the memory at all? Maybe we can generate one CST note at a time, handle it in the CST parser and discard it immediately. That way instead of improving its memory consumption by a factor of three, we're improving it infinitely. To take zero memory. What the current parser actually does is it has two entry points, one for string objects and one for file objects. It passes this input to parse token function which runs a loop inside it, extracting one token at a time from the input, passing this extracted token to my parser at token function. This token kind of consumer function maintains its state in a parser state structure which most importantly has the stack of the DFA's keeping track of the current state for each DFA and the pointer to the CST root note. So it's a new CST note to this tree. The parse token is done at the end of input, it returns the CST root to the caller and the caller passes it to the second function called by ST from note object which is essentially the second parser. It reverses this tree and for each subtree of the CST, it generates the corresponding subtree of the CST. The important bit here is that the whole of CST is available by the time second parser runs so it can analyze notes out of order, it can analyze one node repeatedly and so on. My suggestion is to replace the by ST from node object with a different function, something like by ST from tokenizer which would more or less do the same but for getting each CST note it would call this next node function which would pick the parser state, all the parameters for the tokenizer which would just pass on to the tokenizer and generate one note in the output which means only node type and node string but no children and as well return in unvalue indicating the position of the new node relatively to the previous node. So whether it's the first child of a parent node and next sibling of a child node or whether the previous node was the last child and we're going back to the parent. The difficult question here is what are we going to do with the parser module because we no longer have the CST's memory, there is nothing that it could serialize into the structure of nested lists and I'm not sure anybody is actually using the parser module even especially so that it's documented as deprecated. All source cores are used because it's much easier to use but with some effort we can make the parser itself call next node recursively to serialize the CST to serialize it into these nested lists and then to discard the whole thing just for compatibility with existing consumers if there are some. And there are some difficulties here, the minor difficulty is that the parse token no longer have a loop running inside it, we have to change it to a generator function and extract a loop out of it into the parser state structure but the main difficulty is that we have to rewrite all the 5200 lines of the 100 in parser. This is the example of rewriting one function in this way, this is for parser for slice nodes, slice is when you have square brackets and one or two or three numbers separated by columns inside them and you see that the old parser does all kinds of interesting things about the rewritten parser can only check each node once and it has to go on these nodes in order which actually simplifies the code. The question is it would obviously take some time to rewrite the 5200 lines this way, maybe several weekends, maybe many weekends and do we want to do this and if for example I take several weekends to do this, will there be somebody who wants to review the patch including the rewriting of 5200 lines of code? That's actually all I have and when I put Python questions into Google, this is the image that came up so Python is actually queued. Thank you very much. What was the limit that you hit to run out of memory or was there some internal structure that was a static size and it over followed? Yes, I was doing it on my laptop which only has two gigabytes of memory. So if you bought more memory or had more swap then it wouldn't have been a problem and in the future when computers are even larger than they are, it's not going to be a problem for hardly anybody. If you want to run Python on your phone then it will always be a problem. We already know Python doesn't run on phones. Rather than rewrite all the conversion from the concrete parse tree to the abstract syntax tree, is it not possible to some equivalent to a grammar definition for that and generate the code because it does look awfully repetitive for that code? I agree that it does look repetitive and I think that the, I can actually show this, like most grammars for YAC for example include the bits of code with each production that the parser generator inserts into the parser. Maybe something similar can be done to this SDL file to help to generate in the parser. But this would change the syntax of this file which is something formal and somebody outside of the parser, Python tree, may rely on this exact structure. So yes, while keeping the same input structure of the grammar, it's not possible. If we give ourselves the availability to rewrite the grammar then it would be possible but we may be breaking somebody else's code. Hi, I for one think this is awesome and if the entire problem is having a co-maintainer, I think you could become one. You clearly qualified. Thank you. For what it's worth, the C Python tree moved to Git for five months ago. So all of your HG links are now five months out of date. Sorry, can you repeat? This web page is at hg.python.org. Python is now hosted on GitHub and has been for five months. So we're now looking at five month old source code. My slide deck is actually older than five months because this work has been going on since a year ago but I'm sorry about using outdated links. They still work. Any other questions? Okay. So thanks again for a very interesting talk.
 So, hello.  This is about some work that I did with my previous employer.  When I left them, they asked me to remove the slides and not mention their name.  So I'm here with no business affiliation.  Unlike most talks in this conference, this is not about writing stuff with Python.  This is about Python himself.  And most specifically about the C Python, which is the reference implementation.  And even more specifically about the parser, which is part of this implementation.  So what is the Python parser?  When I put Python parser into Google, this is the picture that came up.  But actually, parser is the first stage of the interpreter, which converts the source  code into parse tree, which the compiler then compiles into white code.  And the white code is what the interpreter actually runs.  Now what is Python parser like?  Same as any mature programming language, it has a formal grammar, which looks something  like this.  If this link should open.  Has a formally defined production, three start symbols for three different kinds of  inputs.  Every line defines a new non-terminal symbol, and the notation here is a bit more complicated  than the BNF notation that grammar is usually written in.  Something more like regular expressions.  So we have something like plus modifiers and somewhere star modifiers for repetitions,  as well as parentheses for grouping.  And the other ingredient is the header file with the definition of all tokens.  Python has 57 types of tokens, number 0 to 56.  And the numbers above 256 are reserved for non-terminals, which are the ones that are  defined in the grammar.  Then we have a parser generator that based on the formal grammar and the token definition  produces a file which looks like this.  Basically it's just a definition of static data.  It doesn't have any code in it.  All it does is it defines the one DFA for every non-terminal that the grammar defines.  So every DFA is defined as an array of states.  Every state is defined as an array of arcs.  And every arc has a label and destination state.  Oh, sorry.  I thought my screen is deplicated, but it's not really.  Sorry.  Did the previous files got missing again?  Did you see the previous files that I was trying to show?  Okay.  Then I'll have to scroll back.  This is what the grammar looks like with the productions and the right-hand sides that  looks like regular expressions.  And that's what the header file looks like with the token definitions.  I don't know how to make it deplicated again.  Let me try.  Right.  Now at least I see myself what I'm showing.  So to go back, each state is defined as an array of arcs going out of this state.  And each arc is defined as an...  Now, each DFA is defined as an array of states.  Each state is defined as an array of arcs going out of it.  The first item is the arc label, which is more or less the same as the symbol number.  And the second item is the destination state.  And in fact, we have a special table which converts symbol IDs into arc labels because  label number one corresponds to all keywords and all identifiers.  So we also have to match which specific keyword it corresponds to so that each one of those  get a different arc label number, even though they're all sharing the same symbol ID.  And near the very end of this file, we have the definition of DFA's themselves.  And for each DFA, we also have the start set, which shows which tokens the specific non-terminal  can start with.  And this is all sophisticated enough.  So I prepared a short demonstration of how this works for a very simple Python program  which looks like this.  We parse it as a single input.  So that's the production that we are parsing it according to.  And our parse tree starts with the just root node of single input.  And the DFA which parses single input is the DFA number zero, which looks like this.  And in the initial state, which is state number zero, we have three arcs going out of it.  So the first arc with label number two corresponds to new line.  Next arc to simple statement, third arc to compound statement.  And we are looking at the if token in the inputs.  And according to the start sets, we know that simple statement cannot begin with if.  If is not a new line, but compound statement can begin with if.  So we transition along the last arc, add the compound statement node to the parse tree.  And before we actually transition to state number two, we switch to the new DFA which  parses compound statements.  For compound statement, we have nine options.  So in the initial state, we have nine arcs going out of it.  Only the first arc, which is for if statement, can start with the if token.  So we add if statement node to the parse tree, transition along this arc and so on.  Now we switch to the DFA which parses if statement.  It's sophisticated enough that it didn't fit on this slide.  Because you see that its definition is also sophisticated having the parenthesis and repetitions  and optional parts.  In the initial state, we have only one arc, which with label 97 corresponds to the if token.  Because it's a terminal symbol, we just add it to the parse tree, consume it from the input,  switch to the next state, and stay in the same DFA.  The next state once again has only one arc going out of it, but this one is for test.  Non-terminal, the start set for test says that it can indeed begin with the number,  such as 42.  So we add the test node, switch to the DFA which parses test and so on.  It goes for an awful long time before we actually get back into the same DFA.  And now we are in state number two.  Has one arc which consumes the colon token from the input, transitions to the next state.  Once again, we have only one arc corresponding to suite.  The start set confirms that suite can begin from print token.  So we add a suite node to the parse tree, switch to DFA for suite.  Once again, it takes an awful long time before we get here.  And the interesting bit is now we have three arcs going out of the state number four.  Arc with label 98 corresponding to the terminal L if, 99 to the terminal Ls, and the next  token in the input is the new line.  So it's neither of these.  And the arc label zero means that it's a final state.  So if we didn't match anything, which are just done with this DFA and go back to the  previous one.  So we go back to compound statement.  We are ending up in state that only has zero arc, which means no matter what the next token  in the input is, we are done.  And going back to the previous one.  Go back to the root DFA that we started from.  There is only one arc with label number two, which is for new line.  So we consume the new line from the input.  Add a node to the parse tree.  And the transition to state number one, which is final.  So we are at end of input.  We're in the final state of the root DFA, which means that the parsing succeeded.  We are done.  So what has just happened?  We had a program which was 27 bytes long tokenized into seven tokens.  And this is the parse tree which we produced for it.  64 nodes takes the 100 times as much memory as the source code itself.  And it's not so much a tree as a bamboo stalk because it almost doesn't branch.  We see that we have a huge, like, series of a dozen nodes with a single child each.  All these because Python has a rather primitive parser which has to define grammar like this.  It works.  To actually see this instead of repeating all steps that I have shown just earlier.  Yeah, that's more important.  Because the parse tree can take 100 times as much memory as the source code.  If I have a moderately big Python source file of, say, 30 megabytes, then the parser would  not even be able to load it into memory because the syntax tree for it would be too big.  So that was my motivation for this work.  I had a 30 megabytes Python file and I couldn't possibly run it through Python.  To show these CSTs, there is a standard module called parser.  It can show you the CSTs realized into the structure of nested lists.  Every list has two elements.  The first one is the symbol ID.  So it's 0 to 56 for terminals and something above 256 for non-terminals.  And the second item is the token string for terminals, also a sub tree.  Even in a nested list for non-terminals.  The documentation for parser module actually says that people shouldn't use it because  there is a better module called AST, which is a second kind of syntax tree that Python  uses.  This example shows what the AST looks like for the same example Python code.  It's much more compact, it's almost human readable and the point is unlike CST which  reflects how the program is represented in the source code, the AST reflects what the  program actually intends to do.  So it's actually the AST that the compiler runs on to generate the byte code.  So the second kind of syntax tree actually also has a formal grammar, which is what this  formal grammar looks like, a different format.  Now we have each kind of AST node defining what its children should be, how many and  what are their types.  And the funny bit is that there is no parser generator which takes this file as input.  This file is just formal documentation, but the parser is handwritten.  Hope it opens.  So this handwritten parser is actually 5200 lines long.  It's a bit of very old and dusty code which dates from 2005 to 2007.  Nobody touches it.  Nobody remembers how it works.  But the general attitude is if it ain't broke, don't fix it.  It has been working for 10 years.  Time has proven that it does work.  Okay.  And once again, the AST for our sample code is the very simple structure of nine nodes  which I'm showing here.  So this is what this second parser actually looks like.  The example is a function that parses expert type of nodes.  And what it does is it has a loop organized with the label and I go to from the middle  of the function, something that the extra would not approve of.  And what it actually does is that for each node which only has one child, it knows that  there is nothing interesting for this node, so nothing to do.  We just skip to the next node.  So we see that two thirds of the nodes in the CST have one child.  We don't do anything with them.  We just skip to the next node.  What I thought was why do we have all these useless nodes occupying the memory?  If we can eliminate them at the time when we generate the CST, then at the same time  we are saving two thirds of the memory.  And also the second parser becomes simpler because it doesn't have to be concerned with  skipping all these useless nodes.  This is what an example of compressed CST looks like.  It's actually small enough so it fits on one slide without scrolling.  And at the same time we have this modified function which no longer has the awkward loop.  Actually, it doesn't have any loops at all.  What it does is that in each branch of the switch it can assert that the node has more  than one child, meaning we can do something meaningful with this node and not just skip  it.  Now this shows the serialized CSTs before and after my fix.  You can see that the CST has become so small that it almost becomes human readable.  The catch here is that the only purpose of CST is to be parsed by the second parser into  the AST and then it's discarded from the memory.  We never use it again.  So if we have a long running script such as web service, for example, that loads in a  split second and then runs for hours and days, then it really doesn't matter how much memory  the CST takes because it's only there for the first split second.  On the other hand, if we have a system utility which runs for a split second and finishes  immediately, then the performance of this utility would be dominated by the performance  of the parser.  That was my case.  My script was just looking up a value in the 30 megabytes literal dictionary.  Indeed with my fix to the Python parser, memory consumption of my script reduced by a factor  of three.  I was curious how my patch would affect other standard benchmarks.  These are the results.  One of them has shown improvement by a third.  A few of them have shown around a dozen percent improvement.  Nothing has got worse.  But actually this benchmark package which I was using was replicated in October last year  on the grounds that the results it was showing were inconsistent and meaningless for some  purposes.  I'm not a performance analysis person, so I don't know what it did and what it did wrong.  But it had been superseded with the performance package and these are the results.  Basically something got a little bit better, something got a little bit worse, but the  big picture is that nothing changed.  My intuition is that by performance intentionally runs a few warm-up loops before starting the  timer and this way intentionally avoids the time in the loading and parsing of the source  code.  I didn't actually look inside by performance.  It's big and sophisticated enough.  But nevertheless even these results confirmed that my patch has no unintended side effects,  it doesn't break anything and at the same time it enables use case which may not be  relevant to most Python programmers, but at least if I bumped into it, maybe other people  would bump into it as well.  So then my desire was to share this patch with the community, get it included into Python,  how somebody does this is it opens a bug in the bug tracker because that's where all the  discussions happen, where all the reviews happen and there you also have a mailing list  where you're allowed to send things once a month if your bug is not getting enough attention.  So I opened two issues in the bug tracker and one of them, the second one of them, actually  got accepted and committed.  It took me three months waiting for a review and what it does was the second handwritten  parser knows that the input that it parses always comes from the first parser.  So it's guaranteed to conform with the first formal grammar.  So it doesn't have to validate that it conforms to it.  It knows for sure that for example for if statement node, the first child is always  if tokened and the second child is always test.  But parser module can take an arbitrary realized CST as input and run it through this second  parser.  And then if it doesn't conform to the formal grammar, the Python binary would just crash  on invalid memory access.  So they had to implement the validation for CST themselves.  How they implemented this was like this.  I'm showing just validation for three different types of nodes, but it was all more or less  the same.  They are checking that the number of the children in the node is correct, that the types of  the children are correct, and then recursively descending into each child node and the call  invalidation function for the child node.  When I was looking at this code, which had to be updated with every change to the grammar  too much, the updated grammar, I thought maybe we can auto-generate it from the grammar.  We can write some DFA's which would traverse the CST to see if it's valid.  And then what occurred to me is that we already have this DFA's, the DFA's which parser runs.  We can just run them on the CST instead of the token stream of the input.  So this way I could eliminate 2400 lines of handwritten code with just 70 lines of code  for running the DFA's which we already have in Python parser and which are guaranteed  to stay in sync with the parser because they are what the parser runs.  But after three months in review, my other patch was rejected by Wido van Rossem himself  saying that's because it's so big and sophisticated and nobody has volunteered to review it over  three months.  I shouldn't hold my breath for anybody to jump up and review it.  If nobody cares as much as I do about running 30 megabytes Python scripts through the interpreter,  then tough luck for me.  Basically, this is the motivation while I'm here.  Maybe you can enter this BPO 26415 back ticket, take a weekend to review it.  And from that it's okay.  Yet it committed.  Yeah.  Basically, I have explained what my patch does.  But that's not all.  If the only purpose of the CST is to get parsed by the second parser and discarded, why do  we have to store it in the memory at all?  Maybe we can generate one CST note at a time, handle it in the CST parser and discard it  immediately.  That way instead of improving its memory consumption by a factor of three, we're improving it infinitely.  To take zero memory.  What the current parser actually does is it has two entry points, one for string objects  and one for file objects.  It passes this input to parse token function which runs a loop inside it, extracting one  token at a time from the input, passing this extracted token to my parser at token function.  This token kind of consumer function maintains its state in a parser state structure which  most importantly has the stack of the DFA's keeping track of the current state for each  DFA and the pointer to the CST root note.  So it's a new CST note to this tree.  The parse token is done at the end of input, it returns the CST root to the caller and  the caller passes it to the second function called by ST from note object which is essentially  the second parser.  It reverses this tree and for each subtree of the CST, it generates the corresponding  subtree of the CST.  The important bit here is that the whole of CST is available by the time second parser  runs so it can analyze notes out of order, it can analyze one node repeatedly and so  on.  My suggestion is to replace the by ST from node object with a different function, something  like by ST from tokenizer which would more or less do the same but for getting each CST  note it would call this next node function which would pick the parser state, all the  parameters for the tokenizer which would just pass on to the tokenizer and generate one  note in the output which means only node type and node string but no children and as well  return in unvalue indicating the position of the new node relatively to the previous  node.  So whether it's the first child of a parent node and next sibling of a child node or whether  the previous node was the last child and we're going back to the parent.  The difficult question here is what are we going to do with the parser module because  we no longer have the CST's memory, there is nothing that it could serialize into the  structure of nested lists and I'm not sure anybody is actually using the parser module  even especially so that it's documented as deprecated.  All source cores are used because it's much easier to use but with some effort we can  make the parser itself call next node recursively to serialize the CST to serialize it into  these nested lists and then to discard the whole thing just for compatibility with existing  consumers if there are some.  And there are some difficulties here, the minor difficulty is that the parse token no  longer have a loop running inside it, we have to change it to a generator function and extract  a loop out of it into the parser state structure but the main difficulty is that we have to  rewrite all the 5200 lines of the 100 in parser.  This is the example of rewriting one function in this way, this is for parser for slice  nodes, slice is when you have square brackets and one or two or three numbers separated  by columns inside them and you see that the old parser does all kinds of interesting things  about the rewritten parser can only check each node once and it has to go on these nodes  in order which actually simplifies the code.  The question is it would obviously take some time to rewrite the 5200 lines this way, maybe  several weekends, maybe many weekends and do we want to do this and if for example I  take several weekends to do this, will there be somebody who wants to review the patch  including the rewriting of 5200 lines of code?  That's actually all I have and when I put Python questions into Google, this is the  image that came up so Python is actually queued.  Thank you very much.  What was the limit that you hit to run out of memory or was there some internal structure  that was a static size and it over followed?  Yes, I was doing it on my laptop which only has two gigabytes of memory.  So if you bought more memory or had more swap then it wouldn't have been a problem and in  the future when computers are even larger than they are, it's not going to be a problem  for hardly anybody.  If you want to run Python on your phone then it will always be a problem.  We already know Python doesn't run on phones.  Rather than rewrite all the conversion from the concrete parse tree to the abstract syntax  tree, is it not possible to some equivalent to a grammar definition for that and generate  the code because it does look awfully repetitive for that code?  I agree that it does look repetitive and I think that the, I can actually show this,  like most grammars for YAC for example include the bits of code with each production that  the parser generator inserts into the parser.  Maybe something similar can be done to this SDL file to help to generate in the parser.  But this would change the syntax of this file which is something formal and somebody outside  of the parser, Python tree, may rely on this exact structure.  So yes, while keeping the same input structure of the grammar, it's not possible.  If we give ourselves the availability to rewrite the grammar then it would be possible but  we may be breaking somebody else's code.  Hi, I for one think this is awesome and if the entire problem is having a co-maintainer,  I think you could become one.  You clearly qualified.  Thank you.  For what it's worth, the C Python tree moved to Git for five months ago.  So all of your HG links are now five months out of date.  Sorry, can you repeat?  This web page is at hg.python.org.  Python is now hosted on GitHub and has been for five months.  So we're now looking at five month old source code.  My slide deck is actually older than five months because this work has been going on  since a year ago but I'm sorry about using outdated links.  They still work.  Any other questions?  Okay.  So thanks again for a very interesting talk.
A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_0_4811.png A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_4812_5339.png A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_5340_5447.png A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_5448_6899.png A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_6900_7763.png A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_7764_14471.png A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_14472_14519.png A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_14520_14579.png A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_14580_14723.png A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_14724_14783.png A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_14784_14867.png A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_14868_15383.png A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_15384_19643.png A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_19644_20663.png A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_20664_21515.png A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_21516_21575.png A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_21576_21635.png A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_21636_21683.png A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_21684_21743.png A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_21744_21791.png A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_21792_21851.png A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_21852_21911.png A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_21912_21971.png A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_21972_22031.png A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_22032_22091.png A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_22092_22139.png A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_22140_22199.png A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_22200_22259.png A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_22260_22331.png A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_22332_22403.png A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_22404_22463.png A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_22464_26015.png A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_26016_32183.png A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_32184_33947.png A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_33948_34019.png A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_34020_46715.png A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_46716_46871.png A__Skrobov_-_How_CPython_parser_works__and_how_to_make_it_work_better_qq6eHivQOjI_46872_47171.png
So, hello. This is about some work that I did with my previous employer. When I left them, they asked me to remove the slides and not mention their name. So I'm here with no business affiliation. Unlike most talks in this conference, this is not about writing stuff with Python. This is about Python himself. And most specifically about the C Python, which is the reference implementation. And even more specifically about the parser, which is part of this implementation. So what is the Python parser? When I put Python parser into Google, this is the picture that came up. But actually, parser is the first stage of the interpreter, which converts the source code into parse tree, which the compiler then compiles into white code. And the white code is what the interpreter actually runs. Now what is Python parser like? Same as any mature programming language, it has a formal grammar, which looks something like this. If this link should open. Has a formally defined production, three start symbols for three different kinds of inputs. Every line defines a new non-terminal symbol, and the notation here is a bit more complicated than the BNF notation that grammar is usually written in. Something more like regular expressions. So we have something like plus modifiers and somewhere star modifiers for repetitions, as well as parentheses for grouping. And the other ingredient is the header file with the definition of all tokens. Python has 57 types of tokens, number 0 to 56. And the numbers above 256 are reserved for non-terminals, which are the ones that are defined in the grammar. Then we have a parser generator that based on the formal grammar and the token definition produces a file which looks like this. Basically it's just a definition of static data. It doesn't have any code in it. All it does is it defines the one DFA for every non-terminal that the grammar defines. So every DFA is defined as an array of states. Every state is defined as an array of arcs. And every arc has a label and destination state. Oh, sorry. I thought my screen is deplicated, but it's not really. Sorry. Did the previous files got missing again? Did you see the previous files that I was trying to show? Okay. Then I'll have to scroll back. This is what the grammar looks like with the productions and the right-hand sides that looks like regular expressions. And that's what the header file looks like with the token definitions. I don't know how to make it deplicated again. Let me try. Right. Now at least I see myself what I'm showing. So to go back, each state is defined as an array of arcs going out of this state. And each arc is defined as an... Now, each DFA is defined as an array of states. Each state is defined as an array of arcs going out of it. The first item is the arc label, which is more or less the same as the symbol number. And the second item is the destination state. And in fact, we have a special table which converts symbol IDs into arc labels because label number one corresponds to all keywords and all identifiers. So we also have to match which specific keyword it corresponds to so that each one of those get a different arc label number, even though they're all sharing the same symbol ID. And near the very end of this file, we have the definition of DFA's themselves. And for each DFA, we also have the start set, which shows which tokens the specific non-terminal can start with. And this is all sophisticated enough. So I prepared a short demonstration of how this works for a very simple Python program which looks like this. We parse it as a single input. So that's the production that we are parsing it according to. And our parse tree starts with the just root node of single input. And the DFA which parses single input is the DFA number zero, which looks like this. And in the initial state, which is state number zero, we have three arcs going out of it. So the first arc with label number two corresponds to new line. Next arc to simple statement, third arc to compound statement. And we are looking at the if token in the inputs. And according to the start sets, we know that simple statement cannot begin with if. If is not a new line, but compound statement can begin with if. So we transition along the last arc, add the compound statement node to the parse tree. And before we actually transition to state number two, we switch to the new DFA which parses compound statements. For compound statement, we have nine options. So in the initial state, we have nine arcs going out of it. Only the first arc, which is for if statement, can start with the if token. So we add if statement node to the parse tree, transition along this arc and so on. Now we switch to the DFA which parses if statement. It's sophisticated enough that it didn't fit on this slide. Because you see that its definition is also sophisticated having the parenthesis and repetitions and optional parts. In the initial state, we have only one arc, which with label 97 corresponds to the if token. Because it's a terminal symbol, we just add it to the parse tree, consume it from the input, switch to the next state, and stay in the same DFA. The next state once again has only one arc going out of it, but this one is for test. Non-terminal, the start set for test says that it can indeed begin with the number, such as 42. So we add the test node, switch to the DFA which parses test and so on. It goes for an awful long time before we actually get back into the same DFA. And now we are in state number two. Has one arc which consumes the colon token from the input, transitions to the next state. Once again, we have only one arc corresponding to suite. The start set confirms that suite can begin from print token. So we add a suite node to the parse tree, switch to DFA for suite. Once again, it takes an awful long time before we get here. And the interesting bit is now we have three arcs going out of the state number four. Arc with label 98 corresponding to the terminal L if, 99 to the terminal Ls, and the next token in the input is the new line. So it's neither of these. And the arc label zero means that it's a final state. So if we didn't match anything, which are just done with this DFA and go back to the previous one. So we go back to compound statement. We are ending up in state that only has zero arc, which means no matter what the next token in the input is, we are done. And going back to the previous one. Go back to the root DFA that we started from. There is only one arc with label number two, which is for new line. So we consume the new line from the input. Add a node to the parse tree. And the transition to state number one, which is final. So we are at end of input. We're in the final state of the root DFA, which means that the parsing succeeded. We are done. So what has just happened? We had a program which was 27 bytes long tokenized into seven tokens. And this is the parse tree which we produced for it. 64 nodes takes the 100 times as much memory as the source code itself. And it's not so much a tree as a bamboo stalk because it almost doesn't branch. We see that we have a huge, like, series of a dozen nodes with a single child each. All these because Python has a rather primitive parser which has to define grammar like this. It works. To actually see this instead of repeating all steps that I have shown just earlier. Yeah, that's more important. Because the parse tree can take 100 times as much memory as the source code. If I have a moderately big Python source file of, say, 30 megabytes, then the parser would not even be able to load it into memory because the syntax tree for it would be too big. So that was my motivation for this work. I had a 30 megabytes Python file and I couldn't possibly run it through Python. To show these CSTs, there is a standard module called parser. It can show you the CSTs realized into the structure of nested lists. Every list has two elements. The first one is the symbol ID. So it's 0 to 56 for terminals and something above 256 for non-terminals. And the second item is the token string for terminals, also a sub tree. Even in a nested list for non-terminals. The documentation for parser module actually says that people shouldn't use it because there is a better module called AST, which is a second kind of syntax tree that Python uses. This example shows what the AST looks like for the same example Python code. It's much more compact, it's almost human readable and the point is unlike CST which reflects how the program is represented in the source code, the AST reflects what the program actually intends to do. So it's actually the AST that the compiler runs on to generate the byte code. So the second kind of syntax tree actually also has a formal grammar, which is what this formal grammar looks like, a different format. Now we have each kind of AST node defining what its children should be, how many and what are their types. And the funny bit is that there is no parser generator which takes this file as input. This file is just formal documentation, but the parser is handwritten. Hope it opens. So this handwritten parser is actually 5200 lines long. It's a bit of very old and dusty code which dates from 2005 to 2007. Nobody touches it. Nobody remembers how it works. But the general attitude is if it ain't broke, don't fix it. It has been working for 10 years. Time has proven that it does work. Okay. And once again, the AST for our sample code is the very simple structure of nine nodes which I'm showing here. So this is what this second parser actually looks like. The example is a function that parses expert type of nodes. And what it does is it has a loop organized with the label and I go to from the middle of the function, something that the extra would not approve of. And what it actually does is that for each node which only has one child, it knows that there is nothing interesting for this node, so nothing to do. We just skip to the next node. So we see that two thirds of the nodes in the CST have one child. We don't do anything with them. We just skip to the next node. What I thought was why do we have all these useless nodes occupying the memory? If we can eliminate them at the time when we generate the CST, then at the same time we are saving two thirds of the memory. And also the second parser becomes simpler because it doesn't have to be concerned with skipping all these useless nodes. This is what an example of compressed CST looks like. It's actually small enough so it fits on one slide without scrolling. And at the same time we have this modified function which no longer has the awkward loop. Actually, it doesn't have any loops at all. What it does is that in each branch of the switch it can assert that the node has more than one child, meaning we can do something meaningful with this node and not just skip it. Now this shows the serialized CSTs before and after my fix. You can see that the CST has become so small that it almost becomes human readable. The catch here is that the only purpose of CST is to be parsed by the second parser into the AST and then it's discarded from the memory. We never use it again. So if we have a long running script such as web service, for example, that loads in a split second and then runs for hours and days, then it really doesn't matter how much memory the CST takes because it's only there for the first split second. On the other hand, if we have a system utility which runs for a split second and finishes immediately, then the performance of this utility would be dominated by the performance of the parser. That was my case. My script was just looking up a value in the 30 megabytes literal dictionary. Indeed with my fix to the Python parser, memory consumption of my script reduced by a factor of three. I was curious how my patch would affect other standard benchmarks. These are the results. One of them has shown improvement by a third. A few of them have shown around a dozen percent improvement. Nothing has got worse. But actually this benchmark package which I was using was replicated in October last year on the grounds that the results it was showing were inconsistent and meaningless for some purposes. I'm not a performance analysis person, so I don't know what it did and what it did wrong. But it had been superseded with the performance package and these are the results. Basically something got a little bit better, something got a little bit worse, but the big picture is that nothing changed. My intuition is that by performance intentionally runs a few warm-up loops before starting the timer and this way intentionally avoids the time in the loading and parsing of the source code. I didn't actually look inside by performance. It's big and sophisticated enough. But nevertheless even these results confirmed that my patch has no unintended side effects, it doesn't break anything and at the same time it enables use case which may not be relevant to most Python programmers, but at least if I bumped into it, maybe other people would bump into it as well. So then my desire was to share this patch with the community, get it included into Python, how somebody does this is it opens a bug in the bug tracker because that's where all the discussions happen, where all the reviews happen and there you also have a mailing list where you're allowed to send things once a month if your bug is not getting enough attention. So I opened two issues in the bug tracker and one of them, the second one of them, actually got accepted and committed. It took me three months waiting for a review and what it does was the second handwritten parser knows that the input that it parses always comes from the first parser. So it's guaranteed to conform with the first formal grammar. So it doesn't have to validate that it conforms to it. It knows for sure that for example for if statement node, the first child is always if tokened and the second child is always test. But parser module can take an arbitrary realized CST as input and run it through this second parser. And then if it doesn't conform to the formal grammar, the Python binary would just crash on invalid memory access. So they had to implement the validation for CST themselves. How they implemented this was like this. I'm showing just validation for three different types of nodes, but it was all more or less the same. They are checking that the number of the children in the node is correct, that the types of the children are correct, and then recursively descending into each child node and the call invalidation function for the child node. When I was looking at this code, which had to be updated with every change to the grammar too much, the updated grammar, I thought maybe we can auto-generate it from the grammar. We can write some DFA's which would traverse the CST to see if it's valid. And then what occurred to me is that we already have this DFA's, the DFA's which parser runs. We can just run them on the CST instead of the token stream of the input. So this way I could eliminate 2400 lines of handwritten code with just 70 lines of code for running the DFA's which we already have in Python parser and which are guaranteed to stay in sync with the parser because they are what the parser runs. But after three months in review, my other patch was rejected by Wido van Rossem himself saying that's because it's so big and sophisticated and nobody has volunteered to review it over three months. I shouldn't hold my breath for anybody to jump up and review it. If nobody cares as much as I do about running 30 megabytes Python scripts through the interpreter, then tough luck for me. Basically, this is the motivation while I'm here. Maybe you can enter this BPO 26415 back ticket, take a weekend to review it. And from that it's okay. Yet it committed. Yeah. Basically, I have explained what my patch does. But that's not all. If the only purpose of the CST is to get parsed by the second parser and discarded, why do we have to store it in the memory at all? Maybe we can generate one CST note at a time, handle it in the CST parser and discard it immediately. That way instead of improving its memory consumption by a factor of three, we're improving it infinitely. To take zero memory. What the current parser actually does is it has two entry points, one for string objects and one for file objects. It passes this input to parse token function which runs a loop inside it, extracting one token at a time from the input, passing this extracted token to my parser at token function. This token kind of consumer function maintains its state in a parser state structure which most importantly has the stack of the DFA's keeping track of the current state for each DFA and the pointer to the CST root note. So it's a new CST note to this tree. The parse token is done at the end of input, it returns the CST root to the caller and the caller passes it to the second function called by ST from note object which is essentially the second parser. It reverses this tree and for each subtree of the CST, it generates the corresponding subtree of the CST. The important bit here is that the whole of CST is available by the time second parser runs so it can analyze notes out of order, it can analyze one node repeatedly and so on. My suggestion is to replace the by ST from node object with a different function, something like by ST from tokenizer which would more or less do the same but for getting each CST note it would call this next node function which would pick the parser state, all the parameters for the tokenizer which would just pass on to the tokenizer and generate one note in the output which means only node type and node string but no children and as well return in unvalue indicating the position of the new node relatively to the previous node. So whether it's the first child of a parent node and next sibling of a child node or whether the previous node was the last child and we're going back to the parent. The difficult question here is what are we going to do with the parser module because we no longer have the CST's memory, there is nothing that it could serialize into the structure of nested lists and I'm not sure anybody is actually using the parser module even especially so that it's documented as deprecated. All source cores are used because it's much easier to use but with some effort we can make the parser itself call next node recursively to serialize the CST to serialize it into these nested lists and then to discard the whole thing just for compatibility with existing consumers if there are some. And there are some difficulties here, the minor difficulty is that the parse token no longer have a loop running inside it, we have to change it to a generator function and extract a loop out of it into the parser state structure but the main difficulty is that we have to rewrite all the 5200 lines of the 100 in parser. This is the example of rewriting one function in this way, this is for parser for slice nodes, slice is when you have square brackets and one or two or three numbers separated by columns inside them and you see that the old parser does all kinds of interesting things about the rewritten parser can only check each node once and it has to go on these nodes in order which actually simplifies the code. The question is it would obviously take some time to rewrite the 5200 lines this way, maybe several weekends, maybe many weekends and do we want to do this and if for example I take several weekends to do this, will there be somebody who wants to review the patch including the rewriting of 5200 lines of code? That's actually all I have and when I put Python questions into Google, this is the image that came up so Python is actually queued. Thank you very much. What was the limit that you hit to run out of memory or was there some internal structure that was a static size and it over followed? Yes, I was doing it on my laptop which only has two gigabytes of memory. So if you bought more memory or had more swap then it wouldn't have been a problem and in the future when computers are even larger than they are, it's not going to be a problem for hardly anybody. If you want to run Python on your phone then it will always be a problem. We already know Python doesn't run on phones. Rather than rewrite all the conversion from the concrete parse tree to the abstract syntax tree, is it not possible to some equivalent to a grammar definition for that and generate the code because it does look awfully repetitive for that code? I agree that it does look repetitive and I think that the, I can actually show this, like most grammars for YAC for example include the bits of code with each production that the parser generator inserts into the parser. Maybe something similar can be done to this SDL file to help to generate in the parser. But this would change the syntax of this file which is something formal and somebody outside of the parser, Python tree, may rely on this exact structure. So yes, while keeping the same input structure of the grammar, it's not possible. If we give ourselves the availability to rewrite the grammar then it would be possible but we may be breaking somebody else's code. Hi, I for one think this is awesome and if the entire problem is having a co-maintainer, I think you could become one. You clearly qualified. Thank you. For what it's worth, the C Python tree moved to Git for five months ago. So all of your HG links are now five months out of date. Sorry, can you repeat? This web page is at hg.python.org. Python is now hosted on GitHub and has been for five months. So we're now looking at five month old source code. My slide deck is actually older than five months because this work has been going on since a year ago but I'm sorry about using outdated links. They still work. Any other questions? Okay. So thanks again for a very interesting talk.
specifically about the C Python, which is the specifically about the parser, which is part of different kinds of inputs. Every line defines a know how to make it deplicated again. Let me try. that we started from. There is only one arc with memory because the syntax tree for it would be It can show you the CSTs realized into the very old and dusty code which dates from 2005 to years. Time has proven that it does work. Okay. the very simple structure of nine nodes which I'm that parses expert type of nodes. And what it saving two thirds of the memory. And also the finishes immediately, then the performance of this utility would be dominated by the to the Python parser, memory consumption of my curious how my patch would affect other standard in the loading and parsing of the source code. I even these results confirmed that my patch has no but it was all more or less the same. They are about running 30 megabytes Python scripts through way instead of improving its memory consumption tree. The parse token is done at the end of question is it would obviously take some time to interesting talk.