Tuning request: List access

[ArnoHue]

Performance-profiling the GoK Chess project at https://turbowarp.org/148769358 via Google dev tools, it shows that a significant amount of time is spent on list items access, mostly listGet() and listReplace(), which in turn invoke listIndex().

I noticed that there is special handling required for string-based index parameters like "first", "last", "random", and expect this to be a main cause. I am no JavaScript expert, but was wondering whether there might be an alternative, e.g. passing the index parameter straight through in JavaScript, and only if the item turns out to be undefined, trigger special handling for string parameters. Or alternatively, detect those string constants during parsing, and generate special JavaScript code to cover the string index cases. This still leaves out dynamically passed strings, but that scenario should be extremely seldom. I suppose a Visitor pattern implementation might not be an option due to weak typing?

[GarboMuffin]

Long-term we want to rewrite the compiler to be able to reason about variable types much more effectively. Short-term I'll try to find some time over the next week or so to look for any low-hanging fruit to help your project

[n-d-v]

Long-term we want to rewrite the compiler to be able to reason about variable types much more effectively. Short-term I'll try to find some time over the next week or so to look for any low-hanging fruit to help your project

You could include an additional feature in the "Turbowarp Blocks" extension where you can make variables that only support numbers, or you could make it so that the compiler checks to see if there is any way that the variable can become a string, and if there is a way it can become a string (like setting a variable to a string using the block or allowing the user to control the variable using the "ask ( ) and wait" block) and if not, then you can make the variable integer-only.

[ArnoHue]

As a followup, esp. with the dawn of 3d engines and neural networks on TurboWarp, is there a chance to speed up operations on numeric list items in access and numeric ops?

E.g. a custom block adding list values to other list values is currently transpiled like this. Besides the sanitizing and backward-comp-code, it also triggers invocation of listReplace() and listIndex().

return function fun63_NNUE_AddAccWght2_16_ (p0,p1) {
listReplace(b0, ((+p0 || 0) + 0), ((+(b0.value[((((+p0 || 0) + 0) || 0) | 0) - 1] ?? "") || 0) + (+(b1.value[((((+p1 || 0) + 0) || 0) | 0) - 1] ?? "") || 0)));
listReplace(b0, ((+p0 || 0) + 1), ((+(b0.value[((((+p0 || 0) + 1) || 0) | 0) - 1] ?? "") || 0) + (+(b1.value[((((+p1 || 0) + 1) || 0) | 0) - 1] ?? "") || 0)));
listReplace(b0, ((+p0 || 0) + 2), ((+(b0.value[((((+p0 || 0) + 2) || 0) | 0) - 1] ?? "") || 0) + (+(b1.value[((((+p1 || 0) + 2) || 0) | 0) - 1] ?? "") || 0)));
listReplace(b0, ((+p0 || 0) + 3), ((+(b0.value[((((+p0 || 0) + 3) || 0) | 0) - 1] ?? "") || 0) + (+(b1.value[((((+p1 || 0) + 3) || 0) | 0) - 1] ?? "") || 0)));
listReplace(b0, ((+p0 || 0) + 4), ((+(b0.value[((((+p0 || 0) + 4) || 0) | 0) - 1] ?? "") || 0) + (+(b1.value[((((+p1 || 0) + 4) || 0) | 0) - 1] ?? "") || 0)));
listReplace(b0, ((+p0 || 0) + 5), ((+(b0.value[((((+p0 || 0) + 5) || 0) | 0) - 1] ?? "") || 0) + (+(b1.value[((((+p1 || 0) + 5) || 0) | 0) - 1] ?? "") || 0)));
listReplace(b0, ((+p0 || 0) + 6), ((+(b0.value[((((+p0 || 0) + 6) || 0) | 0) - 1] ?? "") || 0) + (+(b1.value[((((+p1 || 0) + 6) || 0) | 0) - 1] ?? "") || 0)));
listReplace(b0, ((+p0 || 0) + 7), ((+(b0.value[((((+p0 || 0) + 7) || 0) | 0) - 1] ?? "") || 0) + (+(b1.value[((((+p1 || 0) + 7) || 0) | 0) - 1] ?? "") || 0)));

Given the runtime type of the two custom block parameters could be checked to be numeric, indexes within list bounds, and when ensured lists only containing numeric values, there might be potential optimizations.

An alternative would be an extension implementing a special IntList component w/o bound-checks, type-conversion and backward-compatibility. But it would not be Scratch3-compatible.

Thank you for consideration!

[Hasilo1]

I do not have much too add, but I completely agree that the Lists are slowing down Projects by alot and I would be happy if they were to get a speedup.

[SPARTonScratch]

Author of White Dove https://turbowarp.org/858052938 (another Scratch / Turbowarp chess engine) here! Lists also play a huge role in my chess engine, and a speedup of lists would benefit White Dove a lot too :)

[ArnoHue]

you could make it so that the compiler checks to see if there is any way that the variable can become a string, and if there is a way it can become a string (like setting a variable to a string using the block or allowing the user to control the variable using the "ask ( ) and wait" block) and if not, then you can make the variable integer-only.

Thank you for that suggestion, and this is what I did at the end, namely a TW extension providing blocks for bulk operations (add, sub, relu), for lists with numeric values only. It resulted in a significant speedup.

[GarboMuffin]

would you all be interested in an experimental branch that removes support for random/last entirely so all list accesses can compile very cleanly?

[CubesterYT]

Yeah, let's try it. This could be interesting...

[SPARTonScratch]

would you all be interested in an experimental branch that removes support for random/last entirely so all list accesses can compile very cleanly?

Sounds cool!

[ArnoHue]

would you all be interested in an experimental branch that removes support for random/last entirely so all list accesses can compile very cleanly?

Great! Maybe this could be turned into an advanced setting later? And could bounds-checking be disabled? Means the caller being responsible for valid indexes?

[GarboMuffin]

do your projects seem to run a bit faster here?

https://experiments.turbowarp.org/faster-lists/

a few small changes:

• reading from a list assumes it will only ever see numerical indices
• replacing an item in a list assumes it will only ever see numerical indices
• behavior when dealing with out of bounds indices is very undefined

if the gains are significant that will motivate finding a path for faster lists in the main site

[ArnoHue]

do your projects seem to run a bit faster here?

https://experiments.turbowarp.org/faster-lists/

a few small changes:

• reading from a list assumes it will only ever see numerical indices
• replacing an item in a list assumes it will only ever see numerical indices
• behavior when dealing with out of bounds indices is very undefined

if the gains are significant that will motivate finding a path for faster lists in the main site

Thanks a ton! Initial tests show a moderate speedup. I have to implement a scoped performance test still.

The generated code now looks like this:

b0.value[((((+p0 || 0) + 0) || 0) | 0) - 1] = 
((+(b0.value[((((+p0 || 0) + 0) || 0) | 0) - 1] ?? "") || 0) + 
(+(b1.value[((((+p1 || 0) + 0) || 0) | 0) - 1] ?? "") || 0));

Are the bitwise / logical ops and esp. the ?? operator really still required, given above constraints?