How does Snap!’s scheduler work? With extensive explanation by @jens

Are (all) primitive blocks executed atomically?

E.g. Wait (interval) or (condition) script pic (3),
whose implementation, for all I (as a user) know, might as well be something like:

Programming tools SANDBOX script pic (24)

... could malfunction if two parallel threads are trying to change it, and a context switch happens somehere between fetching the variable's original value and setting the new value (if you're reading Advanced Topics I probably don't have to explain).

I would be highly surprised if Wait (interval) or (condition) script pic (3) were non-atomical in its execution,
but perhaps some other primitives (working on very long lists) may take so much time that they may be interrupted half way?

EDIT
I already found the answer to my question in topic 11127, post 3:

I ran a test of how often context switching between threads is done. More specifically I launched a “WARPed” counter script, and had it run against a very processor-intensive single higher-order block. From what I had previously understood, I assumed that both scripts would get half a second of processor time alternately. However in practice the WARPed counter script was interrupted early; the parent script was highly favored over the launched script:

I wondered whether this was due to the fact that the parent script was in the middle of executing a single block, and Snap! would try to execute that single block as “atomically” as reasonably feasible. So I ran a second test with the processor-intensive single block being launched, and the counter script being part of the parent script. Now the boot was on the other foot, the counter script got most of the processor time. I ran a third test, with a counter script launched as a parallel thread, and a second counter script within the parent script. In all cases, execution of the parent script was highly favored over parallel threads.

Test scripts can be found here:
https://snap.berkeley.edu/snap/snap.html#present:Username=qw23&ProjectName=Context%20switch%20test

Question
Is what I described the result of a deliberate policy by the development team?

What makes you think we don't know what we're doing?

Would that be necessary for having a policy? :slight_smile:

Sigh.

Snap's scheduler and primitives are designed such that a wide range of projects with anything from a single sprite with a single stack of blocks to a bunch of sprites and a bunch of parallel scripts will run at roughly the same speed across a wide range of different devices running different operating systems and different web browsers. We made it so that kids on their public-school issued Chromebooks can collaborate with rich kids sporting shiny new Macs, with their nerd classmates on recycled Linux machines and their geek friends on gaming PCs with overclocked CPUs. We're achieving this by slowing Snap's scheduler down so much that it's basically sitting idle for most of the time. The idle time inside each clock cycle is designed to be so long that it serves as a buffer that projects can grow into without slowing down noticeably. Because we love teaching about emergence and music we've also added a "turbo" mode so we can fast forward the drawing of fractals and allocate a higher timing resolution to polyphony. And because we also love teaching recursion we've further added a "warp" block so we can run a loop as a single block without screen refresh.

"Warp" only makes sense if the loop it is wrapped around completes well within the time of a clock tick, otherwise instead of speeding things up it actually slows things down and renders the IDE less responsive to user interactions. This happens if you warp large parts of a script, e.g. very long loops that do a lot, or if you warp parts of several scripts that run in parallel, so the time it takes for one tick to run extends into the scheduler's "idle buffer". At some point, when what should normally be over in 15 ms takes longer than half a second we break up long warped sections and long recursive reporter evaluations by filling in emergency yields, so users get a chance to press the red stop button to get themselves out of infinite recursion because they forgot a base case.

At every display cycle ("frame") our scheduler does a round robin running one atom per process after another. Every process gets to run a step, we're not ever skipping one. But in the case of warp (or if you're maxing out the scheduler in some other way) we'll run as many steps as we can for half a second and then we'll yield every following process at the earliest possible moment. Since we're not skipping any processes it may actually take longer than half a second for the emergency yield to take effect. Also, because this is, after all, an emergency mechanism, protected code sections are then no longer guaranteed to be atomic.

Here's an example of a maxed-out scheduler:

Overwhelmed Processes

Pressing the green flag button starts three processes, one for each script. At every display cycle the scheduler does a round robin telling each thread to run one atomic step. After each round the thread manager removes the terminated processes before letting the scheduler call the following round.

First frame:
The first process begins counting up to a Million, which takes a little over a second on my laptop. After half a second the scheduler interrupts the first process and runs the second one. Since the frame already went on for over 500 ms the second thread only runs a few steps before being emergency interrupted itself. The scheduler now turns to the third process and it, too, only runs a few steps before being cut short. If you look closely you'll see that the second and third processes count up the exact same numbers in this frame.

Second frame:
Same thing. The first process still doesn't reach the Million in less than 500 ms and again is emergency-interrupted. Again the second and third threads only run a minimal set of instructions each, because the overall time allocated to the frame has already been maxed out by the time it's their turn. If you look closely you'll see that this time the number of instructions the second and third threads are able to run before being cut short are slightly differing. This is because the scheduler doesn't query the system clock at every single instruction, which would cost too much CPU time itself, but only after about every 100 blocks.

Third Frame:
The first process reaches the Million and runs the "stop all" block. The scheduler still completes its current round robin for every thread. The second process doesn't make it up to a Million in time and is cut short. But because the first process didn't take longer than 500 ms the second thread had way more time and was able to perform more instructions than during the first 2 frames before being interrupted. Again, because the scheduler is at this time in emergency mode the third process only gets to run a minimal set of instructions before being cut short.

After the third frame the thread manager sweeps the terminated process off its "turntable" which leaves none to be stepped at the next frame.

Dunno what you mean with "policy", but this part of the evaluator is actually somewhat well documented...

Thx, @jens, for your clear, extensive, and interesting explanation of Snap!’s scheduler. If you don’t mind I will change the name of the topic accordingly, so others interested in the subject may find it more easily.

From your expose I derive that the parent script being “favored” in terms of processor time isn’t so much a deliberate policy as it is a consequence of the particular way the scheduling mechanism was constructed, only occurring when the scheduler is being “maxed out”. So much for my original interpretation :wink: (jumping to conclusions).

I was surprised to read about the “egalitarian” philosophy behind the scheduler, enabling “average” kids with a modest (school) laptop to keep up with their affluent / nerdy / geeky peers. I can see it making sense, though.

ps:does not work if someone's project is too warpy and blocky
e.g the school computers cannot run rocket simulator 2

yes, that's the point of my explanation: Use warp sparingly and wisely around individual, finite loops.

agree

Though having experimented with Snap! for like 9 months now, even I wasn’t fully informed of the seemingly subtle difference between “warp” and “turbo mode”.

Considering …

  • many (non-HOF) operations in Snap! are slow when performed in “standard” mode, notably where substantial amounts of data, or e.g. recursive functions, are involved;
  • “warp” and “turbo mode” are powerful tools to upgrade performance, and therefore attractive to be used (incl. overused, misused);
  • powerful tools, when misused, may cause “collateral damage” (parallel scripts being slowed down significantly)

… wouldn't it be advisable to devote a section in (the back of) the manual to the scheduler, performance considerations and some rules-of-thumb regarding the use of these blocks?