Discussion about the parser performances.

[denis-migdal]

Hi,

Currently the parser is Brython's biggest bottleneck.
Indeed, the py2ast process is responsible of ~74% of the total execution time.

I took a quick glance at it, and noticed several things:

1. $.Parser does an inefficient copy of tokens (1,671 tokens for my tests, 150k+ on bigger files).
   Do we really need to perform such a copy ? If so, maybe using .filter() or :

   const tokens = new Array(_tokens.length); // preallocate
   let offset   = 0;
   // add a token:
   tokens[offset++] =  _tokens[i];
   // ....
   tokens.length = offset;

   would be more efficient ?
2. I noticed a tokens.splice(), if it is called several times, it can be quite trouble some... do we really need it ?
   One way would be to mark the token, e.g. token.TO_REMOVE = true and then remove then all at once, when we are done.
3. A token as a lot of fields (9) with some that seems redundant:
   • 4x position : the start position may be deductible from the previous token ?
   • line : why do we need to store it as when we have the lineno property ?
   • type/num_type : do we really need to store type ? I have the feeling we can deduce it from num_type ?
   • string/bytes : I didn't noticed a case where they have a different value.
4. Lot of :

   var EXTRA = {};
   EXTRA.lineno = token.lineno;
   EXTRA.?          = token.?;

   I think it would help JS engine to do :

   const EXTRA = {
       lineno: token.lineno,
       ?          : token.?
   }

I didn't take a deeper look, but ofc if it is possible to store the tokens into a pre-allocated Float64Array, it could also help a lot (this can be a pre-allocated buffer we can copy then reuse when parsing several scripts).

Cordially,

[denis-migdal]

2. I noticed a `tokens.splice()`, if it is called several times, it can be quite trouble some... do we really need it ?

If this operation is made too often, using a linked list could also be possible (we can also store a linked list into an array).

[PierreQuentel]

If this operation is made too often, using a linked list could also be possible (we can also store a linked list into an array).

It only happens if the current token is ENDMARKER and parser mode is 'single', that is, in the interactive interpreter. So very rarely and on a small tokens list.

[PierreQuentel]

$.Parser does an inefficient copy of tokens (1,671 tokens for my tests, 150k+ on bigger files)

Where do you find a copy of tokens ?

[PierreQuentel]

I replaced the occurrences of

var EXTRA = {}
EXTRA.lineno = p.tokens[_mark].lineno
EXTRA.col_offset = p.tokens[_mark].col_offset

var EXTRA = {
    lineno: p.tokens[_mark].lineno,
    col_offset: p.tokens[_mark].col_offset
}

It made no difference in performance.

[denis-migdal]

$.Parser does an inefficient copy of tokens (1,671 tokens for my tests, 150k+ on bigger files)

Where do you find a copy of tokens ?

In $.Parser function:

this._tokens=$B.tokenizer(src,filename,mode,this)
this.pos=0
this.tok={}
this.mark=0
this.fill=0
this.level=0
this.size=1
this.starting_lineno=0;
this.starting_col_offset=0;
this.tokens=[]
this.src=src
this.filename=filename
this.mode=mode
this.memo={}
this.arena={a_objects:[]}
if(filename){p.filename=filename}}
Parser.prototype.read_token=function(){while(true){var next=this._tokens[this.pos++]
if(next){var value=next
if(! value.parser_ignored){
if(value.$error_token){$B.raise_error_known_location(...value)}else if(value.$error_token_known_token){$B.raise_error_known_token(...value)}
this.tokens[this.tokens.length]=value
return value}}else{throw Error('tokenizer exhausted')}}}})(__BRYTHON__)
;

tokenizer puts tokens in this._tokens, and Parser.prototype.read_token copy one token of this._tokens at the end of this.tokens.

Note: I believe you can now use ES6 class syntax, the code should be easier to read ?

[denis-migdal]

It made no difference in performance.

Maybe the browser already optimized it (and there are likely some costly operations in the code).

But this is hard to predict as it depends on the browser, how many times the function is called, how it is called, what other things the function is doing, etc.

Well at least this is easier to read, and won't be de-optimized if one day the code change.

For now I'll continue to experiment with SBrython. Once done (in a few years ?), I may try to take a deeper look on Brython code for a rewrite.

[denis-migdal]

@PierreQuentel TL:DR; using sticky regexes may lead to a 13% speed increase in the tokenizer (ofc it depends on whether we perform other expensive operations).

I think I'll try to experiment on the parser.
I took a deeper look at it and did some benchmark for token parsing:
https://jsperf.app/fezuru/2

Observations:

• doing it manually with charCodeAt() is the fastest. Using codePointAt() is 1.4x slower.
• [recommended method] using sticky regex with lastIndex is x1.48 slower (almost the same as codePointAt()).
• [current brython method] using regex.exec() is 1.68x slower (/!\ recreating a regex each time is 1.05x slower).
• using str[i] is 3.16x slower.

Sticky regexes seems recommended by the JS documentation:

The y flag almost always requires setting lastIndex. It always matches strictly at lastIndex and does not attempt any later positions. This is usually useful for writing parsers, when you want to match tokens only at the current position.

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/RegExp/lastIndex

Recommendations:

1. For simple tests, do not use a regex, use charCodeAt() instead.
2. For more complex tests, declare a sticky regex outside of the function (avoid recreating a regex each time + avoid string slicing).
3. When testing several conditions, merge the regexes instead of doing cond1 || cond2, etc (verify if we gain from it or not) (?)
4. Remove the .toLowerCase() == '...' used for only one char.
5. Replace the .match() with .exec() or .test() (should be faster).

I'm using micro-benchmark, so in reality things could change:

• (2) will require less object allocations, and may generate a (x1.13) speed increase.
• (1) may or may not make a difference (depends on how many time this is really called).
• (3) dunno if it is better or worse... would need to be tested.
• (4&5) may not make a big difference.

[denis-migdal]

Some benchmark if we want to slice the string (compared to doing it by hand) :

• Using slice and str.search is 1.05x slower.
• Using a regex to extract the full word at once is ~2.8x slower.
• Using a regex to match characters by characters is x1.41 to x1.56 slower (double negation is faster).

https://jsperf.app/tetumi/3

I'd have to implement and test it, to see if we have the same result in real-life.
I think the result is sound :

• using /\w+/ is costly for regexes due to the way they try to find it.
• executing the regex once, instead of one per characters is more optimized.
• I guess the .slice(1 ...) that is done twice is somehow optimized.