[Experiment] Use Data Oriented Programming to speed up brython py code to js code

[Denis Migdal]

Hi,

As I recently learned about DOP, I though this might help speed up Brython js to py code transcription, by reducing:
- allocations ;
- GC work ;
- cache misses.

I'll soon try out a new AST format on SBrython to see if it really is promising.

I'm writing this message to ask you if you had some suggestions, ideas, or insights.


More details here : https://github.com/brython-dev/brython/issues/2545

Cordially,

[Ed]

Hey Denis, thanks for sharing.  By Data Oriented Programming, do you mean this:

https://blog.klipse.tech/dop/2022/06/22/principles-of-dop.html

I find it quite useful.  I tend to program this way even in Python, as I find special-purpose object-based classes too limiting / inflexible.  Thought I was just too lazy to make proper classes.  😝 

That's why I love programming.  Laziness is often a virtue.

As far as brython, afraid I can't be much help.  I slept through programming language courses at uni, somehow scraped together a barely functional parser and promptly forgot the whole thing.  BNF grammar = Better Not For me.

--
You received this message because you are subscribed to the Google Groups "brython" group.
To unsubscribe from this group and stop receiving emails from it, send an email to brython+u...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/brython/af86161f-02bc-44c0-a87a-c4ea3c9fbcf0n%40googlegroups.com.

[Denis Migdal]

The results are in :

Tested : 194/1866 (1672 excluded)
Executed in : 53.620ms -> 43.740ms (-18.5%)
Runtime : 3.820ms -> 2.960ms (-22.5%)
- genFct : 3.300ms -> 2.540ms (-23%)
- exeFct : 0.520ms -> 0.420ms (-24%)
Py2JS : 50.320ms -> 41.200ms (-18%)
- Py2AST : 43.220ms -> 34.360ms (-20.5%)
- ASTConv: 4.060ms -> 3.840ms (-5.4%)
- AST2JS : 3.040ms -> 3.000ms (-1.3%)

Strangely, I mainly improve the parts I didn't touched (I only changed ASTConv and AST2JS).
This may be due to the fact that in JS, the gain of DOP are offset by indexes and typed arrays cost.
I mainly test it on FF, Chromium optimization being too greedy to really benchmark.

However, as the browser as then way less GC work, other parts are speed up.
This video explains the how JS' GC works : https://www.youtube.com/watch?v=OG_AZnPokGw

I "only" changed the way I represent the AST.
There are lot of other parts I can (and plan to) optimize.
My goal is to make ASTConv and AST2JS quick enough that genFct becomes the bottleneck.
But I do not think this is possible.

Also I test it on part of the Brython unit test suite (194 lines in 28 files). I think the DOP benefit will be stronger and stronger the more the files are bigger.
Unfortunately, SBrython lacks too much features to pass (and use) the other tests.

I'd also like to rewrite Py2AST (so the tokenizer and the token2AST parts) in order to see their performances (and to remove ASTConv which convert Brython AST to my own AST format).

[Ed]

Very nice work, Denis.  20% gain is a huge benefit.

The timing numbers make me a bit suspicious - showing so much reduction across the board in parts you never changed.  Could be fewer data objects and less GC runs, as you say.  Or maybe the measurements are off somehow.  Would also like to see timings from chrome to compare.

One thought occurred to me.  This is as much for Pierre as Denis -

I recently stumbled on lark, a parsing toolkit for python.  Lark turns an EBNF grammar spec into a parser that creates an AST.  lark-js will produce the parser in javascript.  They already have python3 grammars.  Claims it's highly optimized for performance.

Which made me think.  Why implement a parser in brython?  Why not reuse an existing parser?  Leverage another project that already focuses on creating parsers.  Let brython benefit from their performance optimizations, and just focus on the unique parts of brython: providing a python-compatible runtime and stdlib.

Saying that, I know it's not so easy.  For one, lark may not be suitable.  They produce an AST in their own format.  Translating their AST into a standard python AST could be more trouble than it's worth.  Second, I had a try running lark-js and couldn't get it to work.  Maybe it's me, but the docs aren't very helpful.  So lark may not be a good choice.

But it sparked the idea.  Parsing is a common problem.  Perhaps it's worth looking into existing parsers that run in js, rather than reinventing the wheel for brython?  Unless parsers are your passion and you really like building your own, I understand that.

Maybe I misunderstood the issues.  Parsers aren't my strong suit.

Best,

--

You received this message because you are subscribed to the Google Groups "brython" group.
To unsubscribe from this group and stop receiving emails from it, send an email to brython+u...@googlegroups.com.

To view this discussion visit https://groups.google.com/d/msgid/brython/3592b10a-1054-4609-9702-81a294d6edacn%40googlegroups.com.

[Denis Migdal]

Hi,

The issue of using an existing library is that when we have a specific need, it is quite hard to properly adapt that.
Genericity also has a cost, and if we have to convert the generated structure, it has also a cost.

We do not use a parser to visualize an AST, but to generate JS code from Python.
Therefore we do not need a generic AST structure, and can tailor make our own with all of the informations we need (e.g. positions in Py code, type informations, operator priorities, etc), putting the children in the order we want/need, etc. We can also insert (and remove) our own checks (e.g. Python parser error message), etc.

In SBrython, I only do the AST2JS part, and use Brython's AST that I convert into my own format.

> Would also like to see timings from chrome to compare.

I didn't measure it initially. But Chrome optimization is too greedy to benchmark. For exemple, when running the tests twice, it will cache the generated JS.
But yeah in Chrome I win more 10ms.

Next WE (or the next) I think I work on my Editor to have better stats.

> The timing numbers make me a bit suspicious - showing so much reduction across the board in parts you never changed.  Could be fewer data objects and less GC runs, as you say.  Or maybe the measurements are off somehow.

I had something like 14,700 AST nodes in total in my tests, for each (a type, an array of children, a toJS function, a result type, a value, py+js position beg/end + col/line so like ~20 objects per AST node, so up to 294,000+ objects to check when the GC needs to (de)allocate.

Now I have 3 types arrays, and only one array of values to check.
And Pierre's Py2AST is performing LOT of allocations, so the GC is likely to be called a lot too.
And the GC is likely to be called at the start of py2ast to liberate the data of the previous test file.


Cordially,

[Denis Migdal]

> The timing numbers make me a bit suspicious - showing so much reduction across the board in parts you never changed.  Could be fewer data objects and less GC runs, as you say.  Or maybe the measurements are off somehow.  Would also like to see timings from chrome to compare.

Before the optimization, when testing tests one by one, I was (for Brython) at 61ms for py2js with an py2ast of ~43ms
By putting all the tests together (for Brython) : 118ms for py2js with ~46.88ms for py2ast.

Sure, putting all the tests together adds functions to the generated file, and the ast2js is measured when computing SBrython results (I'll soon change that).
Still, a 2x difference, seems a lot. py2ast increased a little (+3ms). So either ast2js exploded in Brython due to the function generation, or/and the GC is strongly showing.

On Monday, March 3, 2025 at 10:38:24 AM UTC+1 Edward Elliott wrote:

[Denis Migdal]

I put a simple loop to repeat the test 1000x :

Runtime : 1.334540s = 2.280ms
- genFct : 0.384480s = 0.700ms
- exeFct : 0.950060s = 1.580ms
Py2JS : 17.4549000s = 52.380ms
- Py2AST : 16.216660s = 42.260ms
- ASTConv: 0.701780s = 5.220ms
- AST2JS : 0.536460s = 4.900ms

Results are more stables,  but we see that the browser is performing optimizations.
The issue is that we never know if such optimizations comes from true optimizations (the browser inline frequently called functions), or due to some caching as we repeat the same thing several times.

We can see that the browser is really good at optimizing my DOP code (x10 quicker when doing 1,000 iterations). I guess that as I use indexes/number, it is easier to cache can references. We can see that Py2AST was responsible of ~93% of the cost of py2js, while being 2.6x faster.
But I can't know if such optimization would occurs in real life on real code.

I look at the perfs, ~13% of the time seems to be used by "parsenumber". I never understood why Brython converts integer into JS first, then re-converting them into strings to generate the JS.

FF profiler isn't really helpful.

[Pierre Quentel]

Which made me think.  Why implement a parser in brython?  Why not reuse an existing parser?  Leverage another project that already focuses on creating parsers.  Let brython benefit from their performance optimizations, and just focus on the unique parts of brython: providing a python-compatible runtime and stdlib.

The parser introduced in Brython 3.12.3 is actually no more a Brython-specific version, it's an adaptation to Javascript of the parser included in the CPython code, which could already generate parsers in C and Python. The big advantage of this toolkit is that it supports the "grammar actions" included in the grammar file (details in PEP 617 - New PEG parser for Python) that directly generate the AST. 

I didn't try but from the documentation I doubt very much that lark.js can generate parsers from the Python grammar and make something of "grammar actions".

- Pierre

[Ed]

Thanks Pierre.  I think you're right, lark doesn't handle grammar actions.  I did find a comparison chart, which led to ANTLR4:

From a grammar, ANTLR generates a parser that can build parse trees.  

ANTLR 4 supports 10 target languages (Cpp, CSharp, Dart, Java, JavaScript, PHP, Python3, Swift, TypeScript, Go), and ensuring consistency across these targets is a unique and highly valuable feature.

ANTLR4 does LL(*) parsing and supports grammar actions.  No idea if it's suitable.  Just FYI.

I also came across this article with good advice (for me at least):

Let us start by saying this: if you want the absolute best performance you may want to opt for a custom parser. You will spend ten times as much on maintenance and you will be less productive, but you will get the best performance possible. This is how the official parsers for languages like C# or Java are built. A custom parser makes sense in those cases, but in the vast majority of cases, it does not. You will be much more productive using ANTLR, or another parser generator, than writing a custom parser by hand. 

Given that the first few paragraphs of that PEP made my head hurt, I'll leave parsing to the pros! 😅

Best,

--

You received this message because you are subscribed to the Google Groups "brython" group.
To unsubscribe from this group and stop receiving emails from it, send an email to brython+u...@googlegroups.com.

To view this discussion visit https://groups.google.com/d/msgid/brython/435f0a55-fc70-41ec-91b2-ee188440da2bn%40googlegroups.com.