17 devlogs
59h 28m 22s
Compile Scratch projects to WebAssembly. Started before flavortown, but I’m aiming to ship a stable version by the end of it.
Turns out that the previous changes actually made an extra 2 tests pass that i hadn’t noticed - because 2 tests also regressed. I’ve fixed these (and hopefully preemptively fixed some future bugs), although i’m not entirely sure why the changes I made fixed the bugs. The main thing was changing how loop unrolling works to eagerly clone the loop body - which is what the big refactor was trying to avoid. but somehow that made things worked (the bug was essentially that during loop unrolling, variables were created that were read from but never initialised).
But that means we now have 45 tests passing which is nice (and now up to 400 commits! [do bear in mind the first commit was some time in 2023 i think])
0
Log in to leave a comment
The recent work to revamp how steps are stored internally is now complete, which means that loops containing blocks that yield now work correctly! I’ve added two tests for this to catch any regressions in the future. I feel like the code is now even less readable than it was - there is more indirection than there was previously I think - but it should be easy to make it nicer in the future. But the basis is there!
Today’s image: 2 extra tests passing (but both ones that i added)
0
Log in to leave a comment
I’ve been working on a large refactor, which should help resolve some fundamental problems with the IR.
Currently, all steps are stored as Rcs. When a step is used in multiple places in the IR, it is deeply cloned (i.e. the underlying Step is cloned and assigned a new ID, rather than just cloning the Rc). This causes problems where a step needs mutating, but it’s been cloned: some versions lag behind and are never updated. For instance, when we encounter a loop in which the last block yields, or doesn’t continue the opcode stack linearly (think: non-warped proc calls, broadcast and wait), the loop isnt properly constructed and we end up terminating after only one iteration.
To fix this, I’m trying to give steps types that reflect their use. Non-inlined steps (those that are started at the top-level by the scheduler) are stored as RefCells in a central map, and referenced elsewhere by a StepIndex (a wrapper around usize). Inlined steps - e.g. if/else statement bodies - are stored everywhere as Rc<RefCell>s and not stored centrally. When inlined steps are used in multiple places, they are cloned lazily, i.e. only when they need context-aware mutation.
I have done most of this and am now left with another small problem, to do with newly introduced polymorphisms over the two kinds of steps. In such contexts, when I want to reason about all steps - e.g. in the SSA pass, where each step is associated with a graph - it’s not clear how steps should be stored. To sort this out I’ll probably create some sort of Step trait implemented for the relevant types, backed by the current Step struct, with some sort of dynamic dispatch for hashing. Or, I might change some algorithms to avoid needing such a collection of steps - I have yet to decide. Regardless, now seemed like a good place to make a commit before I make yet more big changes.
Today’s image is the latest commit summary (I’ve nothing else to give as it doesn’t compile yet)
1
Log in to leave a comment
Comments
i wrote this devlog a week ago but tried to submit it during the hackatime outage and promptly forgot about it. it was also very very difficult to get it below 2000 characters
I’ve now implemented control_wait, which was very similar to event_broadcastandwait and should have been simpler, but I managed to really confused myself with when threads should terminate and when they shouldn’t… but I managed to get my brain working eventually. Similarly to broadcast and waiting, this spawns a thread in the same thread stack as the current thread (I told you I needed to come up with better words for the different types of thread), with the struct argument having a single float argument, which is the value of the timer after which the thread should resume. This value is then compared to the timer value in subsequent steps.
Today’s image: 2 more tests passing (and more failing, but that’s ok I think)
0
Log in to leave a comment
Taking a brief detour from broadcast-related stuff, I slightly altered the project loading system so that it can now load projects that weren’t uploaded from the online editor - turns out that for these, https://projects.scratch.mit.edu/[id]/ (with a trailing slash) returns 404, but without the trailing slash it’s all good (but returns the zip instead of just the project.json. but that’s fine).
I’ve also implemented the timer blocks in a fairly rudimentary manner - I think they drift a bit more than they should, but that’s something I’m happy to deal with at a later date.
I have also now reached 20,000 lines of code (but only 900 lines of comments! shocking)
Today’s image: another test is passing (which is nice because it means I don’t need to be creative about what image to use)
0
Log in to leave a comment
I have now implemented the broadcast and wait block, which was actually quite fun to implement. It works like so:
-
the relevant threads are spawned, and their thread indices added to a GC array
-
the step that comes after the broadcast and wait is inserted in the relevant place
-
a new thread is spawned in the same stack, which polls the aforementioned array of indices to check which threads have terminated, and if they have all terminated, yields to the next step
which all works quite nicely. Alas this doesn’t cause any new tests to pass because they all either need other blocks to be implemented, or rely on execution ordering which hyperquark doesn’t respect yet. So for today’s image, you can get my lines of code report from cloc - we’re rapidly approaching 20k which is astonishing. (as a reminder, much of those 20k lines of code were written before flavortown)
0
Log in to leave a comment
I’m getting better at writing devlogs after fewer hours of work! In preparation for implementing the broadcast and wait block, I split the WASM for spawning a new thread in the same stack into its own function, in much the same manner as spawning a brand new thread was split previously. (I think I need to come up with some better terminology, because I’m using thread both to mean a stack of blocks headed by a hat block, and a structure keeping track of a currently running block).
I also changed some rustfmt settings (joyous!) to make some things a bit nicer - now imports are grouped nicely depending on whether they’re from the crate, std, or external. That’s been bugging me for ages so I’m glad I did that.
No more tests are passing so the image this time is of a totally unrelated script that I discovered turbowarp intentionally breaks compared to scratch. Fun! (see: https://github.com/HyperQuark/hyperquark/issues/46)
0
Log in to leave a comment
the broadcast block has now been implemented; broadcast and wait shouldn’t be too difficult following these changes.
The most time-consuming and thought-provoking change here was that I wanted to move the thread spawning logic into its own static function so it could be used in multiple places. I already had code in place to supply static functions (but only when used), but this required the instructions to be able to be generated inside of a const block. Alas, the thread spawning function needed type indices that aren’t available at compile time, so I had to rejig this such that the functions are generated at the module generation time instead, which was a bit fiddly but some closures did the trick.
Attached image: the usual (one more test passes! yay! [but i think it might pass due to a bug, because execution order isn’t fully scratch-compatible yet])
0
Log in to leave a comment
Since my last devlog I’ve tidied up some small bugs around loop unrolling and const folding, and have also addressed some very long-standing TODOs in operator_equals; now, strings are compared to numbers correctly, so that “1”==“1.0” is true (yippee). Also, ln can actually return NaN now.
Next up: broadcasts?
Today’s image: 1 more test passing.
0
Log in to leave a comment
I have no idea how I managed to accrue nearly 22 hours of undevlogged time - I think hackatime must be having a bit of a silly moment (or the time that’s displayed when I write the devlog is just wrong).
I have been working on some new optimisations which should counteract a big ol’ performance regression that I had to introduce recently to maintain scratch compatibility. Now, the first few iterations of each loop are unrolled (in the hope that the types of any variables stabilise to a single basic type after a few iterations), and I’ve implemented a little bit of const folding to help wasm-opt out, as it can’t optimise string operations.
I have no suitable images today as the only thing this changes is performance, which is tricky to take a picture of, so have a picture of a llama.
_(19692833269).jpg)
0
Log in to leave a comment
More bugs fixed, primarily surrounding procedures; in particular, non-warped procedures are now called with return_call_ref to avoid annoying fallthroughs, global variables are backed up before non-warped procedure calls, and procedure return variables are now boxed where necessary (this might be necessary because of control_stop). 36 tests passing!
0
Log in to leave a comment
Woops! I forgot to devlog when I last committed so I’ve now got 2 things to devlog about, and quite a lot of time!
The more interesting thing is that non-warped procedures (custom blocks without “run without screen refresh” enabled) are now supported; this required large changes to the scheduler which I expected to have a very large performance impact, but it seems to be ok for now. Will keep an eye on it.
I also redid the JS that actually runs the project, both to make it cleaner (it basically hasn’t changed since I first wrote it awfully 3 years ago), and to be able to reuse the same project runner in the integration tests. This all works nicely, and we now have 33% of tests passing which I think is very exciting!
0
Log in to leave a comment
Ok so 5h48m is a long time to go without a devlog but I was working very hard to fix many annoying bugs! I have now implemented data_insertatlist, data_removeitemoflist and data_listcontents. The latter was mighty annoying, because its behaviour differs depending on if all of its elements are single-character strings, which is annoying to test for and also means that strings can no longer be proactively converted to floats - this has put const-folding higher up in my list of priorities!
New milestones reached: 17,000 lines of code (!) and 23 integration tests passing (and also, wow look at all those unit tests!) (see images)
2
Log in to leave a comment
Comments
not all of the images uploaded :( but there are 385 unit tests (which all pass)
wow, congratulations on passing so many unit tests
A bunch of other msicellaneous bugs fixed, but the most interesting thing is not a bug fix but a rework of how lists are initialised. Originally, i was using the array.new_fixed instruction, which requires you to list every member of the list in order to instantiate it. This is nice because it is useable in extended const contexts, so you can get away with immutable lists being actually immutable. However, I then realised that I was initialising lists with a maximum length of 2000, rather than 200,000 (which is what it should be), and I didn’t really want to generate 200,000 instructions for lists that are going to be mostly empty. Instead, I’m now initialising the lists with the required amount of elements, in some sort of sensible default state (i.e. 0 or “”), and then in the WASM start function, using the array.init_data or array.init_elem (for strings) functions, which svaes quite a lot of space in the generated WASM. Yay! 21 tests pass now :)
0
Log in to leave a comment
The promised fixes of IR type system bugs have arrived:
Some list blocks take more arguments than the equivalent(ish) variable blocks, which was causing confusion in the SSA optimisation - these are now ignored and things work as expected.
When new SSA variables were created, they were created with a dummy initial value of false. This was artificially inflating their type to include Boolean, which was causing problems; new SSA variables are now created with an empty type, as expected.
We now have 20 tests passing - I wasn’t sure what to put as the attachment so I’ll just give you an image of the test summary again. You’re welcome :)
0
Log in to leave a comment
Ok so apparently time is counted since the 15th of December, not from when you sign up to flavortown - so I’ve got 17 hours to devlog for. Sorry ‘bout that. I have so much to say that it ends up going over the character limit, so I’ll have to be quite concise.
So, a summary of what I’ve been working on in the last 5 days:
- variable type analysis has been rewritten to be less buggy and more maintainable - the main difference is that, rather than each step being responsible for writing any variable changes to the outer scope at the end, the outer step is responsible for this (this is inspired by the idea of ‘phi nodes’ in tradition SSA optimisations, which I’ve only recently become aware of). This makes life a lot easier, as steps don’t need to keep track of multiple different states - they just focus on themselves, and when an inner step (in a loop or if/else block, for example) needs optimised, it can compare the state of the inner step to its own state, and react accordingly.
- I’ve taken some of turbowarp’s (another scratch mod, that compiles scratch projects to javascript)’s integration tests so I can do more automated tracking of feature parity with upstream. At the time of writing, ~18% of eligible tests pass, which isn’t bad.
- This highlighted a lot of project loading issues which are now fixed, including that sb2 files (from projects created using Scratch 2) couldn’t be loaded as they were never converted to sb3s. There are still a couple more bits and bobs which need ironing out, but they seem to be mostly quite obscure things (like having a null variable ID…. why does scratch allow that?!)
- A lot of housekeeping to do with dependencies and CI
- Variables are now generated with their initial values intact
- Most list operations are now supported, using wasm GC arrays for now.
- And some other small fixes.
Wow, that’s quite a lot!
Next up are some bug-fixes in the IR type system, and then more list stuff.
1
Log in to leave a comment
Comments
The devlog times seem to have been updated which is nice because it means I no longer have a suspicious 17 hours of time at the beginning, but on the other hand, i don’t get 17 free hours at the beginning tear🥲
The current thing I’m working on in hyperquark is lists. The changes are looking quite chunky at the moment.
0
Log in to leave a comment