[Performances] Use DOP principles for the AST generation ?

[denis-migdal]

Hi,

I recently learned about the DOP (Data Oriented Programming) principles.

I wonder if it could help to speed up the Py2JS process by changing how the AST is stored.

In the previous Brython version (not up-to-date), I have the following performances :

• Py2Ast : 36ms
• AST2js : 18ms
• browser js parsing : 4.4ms
• execution : 4.8ms

Py2JS is therefore ~5/6 of the total execution time.

DOP seems to promise quite good speed up. Zig parser was rewritten using it, with a significant speed gain:
https://www.youtube.com/watch?v=IroPQ150F6c

The main principle is to :

• reduce object creations ;
• reduce the amount of RAM -> L2 cache updates.
• reduce the amount of copy / if / etc.

We could transform the ASTNode tree into a struct of arrays, greatly reducing object creations, and possibly access time.

For example, some of the AST node properties, e.g. lineno, could be stored in a :

const lineno = new Float64Array(); // we could pre-allocate such array depending on the script length (e.g. script.length / 3).

// get the lineno of the ASTNode with the id my_astnode_id.
lineno[my_astnode_id]

Children could also be stored in arrays :

const firstChildren = new Float64Array(); // we could pre-allocate such array depending on the script length (e.g. script.length / 3).
const nextBrother = new Float64Array(); 

// get the first children of the ASTNode with the id my_astnode_id.
let childID = firstChildren[my_astnode_id]
// get the next children :
let child     = nextBrother[childID]  // if childID === -1 => no more children.

toJS function could be fetched from a NODE_TYPE_ID :

const nodes_type = new Float64Array();

// get the toJS for my id my_astnode_id.
toJS[ nodes_type[my_astnode_id] ]( ... );

I don't really have time to work on it (still haven't finished SBrython), maybe I'll try it in a few years ;).

EDIT: maybe I could try on my SBrython ASTConv to see if I have some changes in performances with it.
Could be quicker to test if this is a promising solution. Won't be able to work on it for maybe a year, but that's something that I could try once I'll have some more free time.

Cordially,

[denis-migdal]

I had time to though about it, and I think I can test it in less than one day.
And I think I'm too impatient to wait too much to test it...

So, we store data in typed arrays in order to reduce allocations, GC work, and CPU cache misses.
A good thing is that for multiple scripts parsing, we can reuse such arrays, so we can have an initial big allocation.
The typed array type we'll call it T and its initial size MAX_TOKEN would need to be found by testing different values.

Such data could also be easily transferred/stored/shared between workers. Maybe we could find some benefit for that.
Normalizing such structs could also help separating the pycode2jscode steps, and may help people contributing on small parts ?

So we would have 4 structs :

const T = Float64Array;
const MAX_TOKENS = 1024*1024; // ~1 million tokens max will consume ~= 100Mo of memory.

const TOKENS = new T(4*MAX_TOKENS);
const TOKEN_TYPE                     = 0; // a number identifying the token type
const TOKEN_CHILDREN_BEG  = 1; // the TOKEN_ID of the first child OR VALUE_ID OR VALUE of the token (depends on TOKEN_TYPE).
const TOKEN_CHILDREN_END  = 2; // the TOKEN_ID + 1 of the last child OR 0
const TOKEN_RESULT_TYPE      = 3; // a number identifying the type of the token result (for SBrython).

// TOKENS[4*TOKEN_ID+TOKEN_TYPE] // getting the token type from a token ID.

const VALUES = new Array();
// VALUES[VALUE_ID]; // get the arbitrary value VALUE_ID.
// small values (e.g. bool, numbers, etc) can be stored inside TOKEN_CHILDREN_BEG.
// strings could be stored using TOKEN_CHILDREN_BEG and TOKEN_CHILDREN_END.

const toJS = new Array();
// toJS[TOKEN_TYPE](TOKEN_ID) // transform the token into JS code.

const PY_CODE =  new T(4*MAX_TOKENS); // + also for JS_CODE (for SBrython)  
const CODE_LINE = 0;
const CODE_COL  = 1;
const CODE_BEG  = 0;
const CODE_END  = 2;
const CODE_BEG_LINE = CODE_BEG + CODE_LINE;
const CODE_BEG_COL  = CODE_BEG + CODE_COL;
const CODE_END_LINE = CODE_END + CODE_LINE;
const CODE_END_COL  = CODE_END + CODE_COL;

// PY_CODE[4*TOKEN_ID + CODE_BEG_LINE] // get the token starting line.

In SBrython, I only convert Brython's AST to then convert it in JS. So my test will focus on it.
I am not yet familiar enough with tokenize and tokens2AST.

If I had to guess, tokenize would fill the PY_CODE array (?). And tokens2AST the other arrays (?).
Could both step be merged (?)... and... should they ?

I also think standard python verification should be performed in optional steps we could add/remove.
This would enable to:

• plug more steps (e.g. type verification) ;
• remove checks (e.g. for a production version) ;
• replace a step by a more naïve one.

[denis-migdal]

The order in which the tokens are stored and visited also matters.

I initially though of storing them like that :

T1
|--- T1_1
|        |--- T1_1A
|        |--- T1_1B
|--- T1_2

[T1,  T1_1, T1_2,  T1_1A, T1_1B]

The number of children is easy to fetch, but the token and its children are far from each other in memory.
Also, we likely visit the tokens with a depth-first algorithm.

Maybe storing them like that could help :

[T1,  T1_1, T1_1A, T1_1B, T1_2]

• We'd then only need 3 numbers for each tokens: TOKEN_TYPE, TOKEN_CHILDREN_END, TOKEN_RESULT_TYPE (so less memory used).
• Should be more appropriate for a depth-first.

The drawbacks is that we can't easily know the number of children.

The token algorithm being something like :

let CUR_TOKEN_ID = 0;

const CH_END = TOKENS[3*CUR_TOKEN_ID + TOKEN_CHILDREN_END];
while(CUR_TOKEN_ID != CH_END) {
        // consume children...
}

Maybe there would be a better graph visit algorithm, but I do not see which one.
Breadth-first search doesn't seem appropriate for this usage.

One issue with current visit is the fact that this is recursive. But I do not see how we could manage our own stack in such context.

[denis-migdal]

I wonder if I could reduce [TOKEN_TYPE, TOKEN_CHILDREN_END_OR_VALUE, TOKEN_RESULT_TYPE] further.

TOKEN_CHILDREN_END is only necessary when we do not know the number of children.
We could make it in such a way that all the tokens that have a TOKEN_RESULT_TYPE know their exact number of children.

Therefore having something like: [TOKEN_TYPE, TOKEN_RESULT_TYPE_OR_END_CHILDREN].
Saving 1/3 of memory.

But I'll have an issue to store the TOKEN_VALUE...
I can either :
A. store it on TOKEN_RESULT_TYPE_OR_END_CHILDREN, but this may make type verification more complex (requiring to check the TOKEN_TYPE). Maybe the token consumption could somehow return the TOKEN_RESULT_TYPE or store it in a kind of global """register""" ?
B. store it on a special token, but this would waste 6 to 10 numbers (2 for a token + 4 to 8 for the py codes).
C. store all values into a sparse array, using TOKEN_ID as a key ?
D. create new token types on the fly for values ??? Or could be pre-allocated, and use a non-sparse VALUES array ?

Knowing that :

• Some values like True and False could be their own token type. Maybe also some values like 0, 1, -1, 2 ?
• str could use PY_CODE to slice the code source, and be truly parsed during ast2js process ? Could be made for other types too... but wouldn't a VALUES sparse structure be more efficient ?
• big types either need to be truly parsed during ast2js process, or be stored in VALUES.

I think (C) should be the best solution.

But... if I assume all literal values are properly parsed/prepared during ast2js, I'd already have a VALUES structure : the list of the tokens from the tokenizer... Then, maybe (A) could be a possible solution...

I think I'll first try the [TOKEN_TYPE, TOKEN_VALUE, TOKEN_CHILD_END, TOKEN_RESULT_TYPE] and then try to see if I really need some cols.

[denis-migdal]

I decided to take some holidays this week, so I'll try to test this DOP on (S)Brython ^^.
The goal is to use DOP principles to rewrite the AST tree and see if it is promising for Brython.

I'll post few updates this week (2-3 ?) to show my progress.
I'll post the final results on the Google Group.

First of all, I updated my brython version to the latest:

**Executed in: 70.840ms** => **Executed in: 66.400ms** 
    **Runtime: 11.780ms**  => **Runtime: 10.840ms**
        **genFct:  5.920ms**  =>     **genFct:  5.200ms**
        **exeFct:  5.860ms**   =>    **exeFct:  5.640ms**
    **Py2JS  : 64.920ms*       => **Py2JS  : 61.200ms**

As we can see the last version of Brython is faster than the previous.

However, SBrython is still faster (as I don't perform a LOT of checks.):

Tested         : 194/1866 (1672 excluded) [28]
Code size      : x 0.91/+ 9.71% (x 5.69/-82.44%)
Executed in    : 53.620ms (x 1.60/-37.35%)
    Runtime    :  3.820ms (x 3.75/-73.30%)
        genFct :  3.300ms (x 1.87/-46.60%)
        exeFct :  0.520ms (x11.88/-91.59%)
    Py2JS      : 50.320ms (x 1.58/-36.62%)
        Py2AST : 43.220ms
        ASTConv:  4.060ms
        AST2JS :  3.040ms (x11.90/-91.60%)

As you can see, the parsing time is wayyy too slow compared to the execution time.
The goal would be to have a Py2JS negligible compared to genFct.

If DOP is promising, we should see faster ASTConv and AST2JS computations, and we will try to see how much.
As well as less memory consumption.

Py2AST currently uses Brython's tokenizer and tokens2AST, so its execution time should remain the same.
As you can see this is very slow. If the new AST tree is promising, this should also speed up tokens2AST.

For the tokenizer, I do not know the process enough to speak.
I think the best candidates would be:

• the regexes performances ;
• building the pycode structure for tokens' begin/end lines/cols ;
• not building an array of strings, but letting tokens2AST doing it when really needed ?
• ^ maybe having a kind of tokenizer.nextToken() that tokens2AST could consume ?

However, I do not plan to modify the tokenizer yet, maybe for a student project ;)

But first we should wait to the the results to know whether DOP is promising or not ;).

EDIT: my results should be slightly biases as the codes I use are very small : 8 to 104 tokens.

[denis-migdal]

Okay, first update.

I replaced my JS code / Py code positions with my new DOP structure, but didn't see a significant speed increase yet (maybe very very slightly worse, but hard to say as it is very small times).
Though I noticed a significant speed increase by branching my laptop to the sector xD.

My hypothesis:

• in not production mode, the constant indexes I use aren't replaced (?) ;
• JS code / Py code positions were properties of my ASTNode class (that I still use), so I long as I do not remove this class, I may not see significant changes.
• I still have lot of bad structures in my code.
• I may be doing costlier operations.
• the code I use may be too small to the the benefit of DOP.
• TypedArray aren't correctly optimized on FF (I perform way better on Chromium, too bad I didn't test it on it beforehand).

So let's continue ^^.

[denis-migdal]

It seems that WASM is nowadays faster than JS. It may also enable to perform better memory/allocations management.
So rewriting the code in C/C++/Rust to execute as WASM in the browser may lead to x1.5+ speed increase (up to x11).

https://developer.mozilla.org/en-US/docs/WebAssembly/Guides/C_to_Wasm

That's something I may be tempted to test ^^
I don't think I'll have the time this weekend though xD.

[denis-migdal]

Funny stuff, astconv and ast2js are slower BUT py2ast (that I didn't touch) seems faster.
Overall this seems 3ms faster ( -6% py2js time ).

I think we start to see the DOP benefit : the GC has less work, so executions made after are faster.

I think the real difference will be when I'll replace my ASTNode class, i.e. one less class instantiation and array construction (the node children) for each nodes.

In SBrython, some ast node types are quite simple, but some others quite complex. My type checking system and some other parts may constitute a big part of the execution time.

[denis-migdal]

Hum, that's strange.

I moved the ast node's value into a sparse array.
It should be slower and it is (+1ms for astconv), but overall seems ~5ms faster...
I really wasn't expecting it.

I noticed that I used value a lot to store some information... I could really optimize that.

I think my operators and function arguments system can be rewritten.
My type system as well.

I also wonder if I could somehow avoid recursion in ast2js and astconv... but this seems quite hard.

Now, I only need to transform the ast node result_type into a number, and then I'll finally be able to replace the ASTNode class by an array...

[denis-migdal]

In my AST nodes, replaced a reference to the result type to an index to an array of result type.
In C++ I could easily use pointers, but in JS can't put pointers into typed arrays (and can't convert double to pointers too).

In my operators, I made it so it reused conversion/return functions.

    Py2JS      : 42.360ms (x 1.40/-28.71%)
        Py2AST : 35.000ms
        ASTConv:  4.520ms
        AST2JS :  2.840ms (x 8.60/-88.37%)

This is funny to see that ASTConv execute time increase, but Py2AST decreases xD.

Still can't remove my ASTNode structure as I attached it some conversions and operator priority information...
I'm really eager to see the result then.

[denis-migdal]

Currently, I write the position of each ASTNode in the generated JS code with its start/end line/col.
This requires me to generate the JS code "in order": I generate JS code, I update the cursor (line/col), and so on.

The issue for the operator priority, is that I need the ASTNode to know the priority of its parent.
I could add the parent index into the ASTNode or use a parse array, but meh.

It could be great if I could generate the ASTNode child first, look at its priority, then add parenthesis if needed.
But I can't do so if I generate JS code "in order".

A solution is to change how I compute the position of each ASTNode. Instead of writing a position with 2 pairs (line ; column), I can simply write its length, and its offset from its parent. Then at the end, I can go though the generated code to get the position of all line breaks (more reliable than trying to tracking new lines as they come).

This enables to generate the JS code "out of order" therefore solving my issue.

In C++, I could use very nice structures to remove the recursions and to create a tree of strings.
In JS, strings concatenations should be implemented in a nice way. This should also remove lots of temporary arrays I had when generating my JS code.

So I'll have to see the perfs with this new generation methods (for position seems already slightly faster). I did a commit just in case it's worse.

I hope I can finally remove my ASTNode structure soon xD.

EDIT: Well, it was a fail.
Generating the JS out of order is a pain to write, however I do not want to impact readability too much.
I also want to keep the JS positions of my ast nodes, in order to be able to print the codes and AST tree in the Editor.

I could have a system with an array of one string to simulate a pointer, a from this try to improve... but I just though that the solution I though I'll use isn't that great. Indeed, if the child shows its priority, it either have to be an information in its node (at this point better having the father giving its priority to the children) or a global variable. However, if I use a global variable and it isn't consumed by the father (e.g. the father was another kind of node), it'll cause issues.

Therefore, I reverted to my previous commit, and will use another value to store the operator priority as I do not want to spend too much time on it. I want to remove this ASTNode structure by the end of the week so that I can see the result before going back to work ;).

[denis-migdal]

Okay, by properly adding the operator priority information, I killed all the performances I previously won, and went back to the original performances.

EDIT: and without doing anything I'm back to my good performances... WTF.

Indeed, as there is now an additional number initialized to 0 for each ASTNode, there is more work.
But now I can start transforming my ASTNode tree into a typed array \o/

I think I will have to rework the operator system, could do something better.
Lot of little parts I could rewrite.

Also, I found a nice video on JS GC, this explain the results I observe.
Using less the GC can increase the current code execution time, but decrease future execution time as the GC has then less work.

https://www.youtube.com/watch?v=OG_AZnPokGw

[denis-migdal]

So I got the results...

It is generally at 39-42ms, with so pics at 50ms.

    Py2JS      : 41.040ms (x 1.46/-31.33%)
        Py2AST : 34.140ms
        ASTConv:  3.960ms
        AST2JS :  2.940ms (x 8.71/-88.52%)

I won ~10ms (-20% total py2js time), but only on the Py2AST part that I didn't touched...
I think I'll check my time computation just in case xD.

It seems using indexes and typed arrays has a cost which is compensated by less GC work/cache misses.
Though, before removing ASTNode, ASTConv was at ~4.5ms.

But I also have a list of optimizations I can do that would be, this time, costless.