diff options
Diffstat (limited to '2024/10/18/Building-custom-fibers-library-in-FSharp/index.html')
| -rw-r--r-- | 2024/10/18/Building-custom-fibers-library-in-FSharp/index.html | 18 |
1 files changed, 9 insertions, 9 deletions
diff --git a/2024/10/18/Building-custom-fibers-library-in-FSharp/index.html b/2024/10/18/Building-custom-fibers-library-in-FSharp/index.html index ea5071f4..e1a6c2c8 100644 --- a/2024/10/18/Building-custom-fibers-library-in-FSharp/index.html +++ b/2024/10/18/Building-custom-fibers-library-in-FSharp/index.html @@ -203,14 +203,14 @@ <p>What we’re after, are more lightweight structures (less than 1kB), that can live fully in a user space, so that we can have even millions of them cooperating frequently with each other without heavy performance penalties.</p> <p>Before we begin, I think it’s good to discuss different designs. We’ll cover several different topics to be able to make more informed decisions, that we’re up to apply to our own solution.</p> <h3 id="Preemptive-vs-cooperative-scheduler"><a href="#Preemptive-vs-cooperative-scheduler" class="headerlink" title="Preemptive vs cooperative scheduler"></a>Preemptive vs cooperative scheduler</h3><p>Scheduler is a subsystem, which direct responsibility is to assign CPU core processing power to a particular fiber. It’s also responsible for coordinating fibers execution. The two most common categories of schedulers are preemptive and cooperative.</p> -<p>A <strong>preemptive</strong> scheduler is the one, that’s always in control of fiber execution. It’s able to decide on its own, when fiber can be started and stopped. The most obvious example of such is a thread scheduler existing on most operating systems.</p> +<p>A preemptive scheduler is the one, that’s always in control of fiber execution. It’s able to decide on its own, when fiber can be started and stopped. The most obvious example of such is a thread scheduler existing on most operating systems.</p> <p>Preemptive scheduler usually works in one of two ways:</p> <ul> <li>Time based scheduler takes a quant of CPU time and gives it to a given fiber, which ten can execute its logic until it reaches its execution time limit (of course, it can finish earlier). This is how OS thread scheduler, but also how Go goroutine scheduler works.</li> <li>Another variant is step-based scheduler, which splits fiber’s function body into series of (more or less equal) steps. Then each fiber is given a number of steps to execute before preemption occurs. Example of such is Erlang’s BEAM - it simply allows each process to execute up to 2000 “reductions”, where each reduction is basically a function call. <em>And since in Erlang there are no loops, only tail-recursive functions, this approach works well for long-living iterative processes as well.</em></li> </ul> -<p>One of the problems with preemptive schedulers is that they usually need some kind of involvement from the compiler or hosting virtual machine in order to work. For this reason, most of the fiber libraries use <strong>cooperative</strong> schedulers to perform their work.</p> -<p>A <strong>cooperative</strong> scheduler doesn’t have a concept of preemption - once started by the scheduler, a fiber will execute until it doesn’t give back the control willingly. This is often done with dedicated programming constructs, and often is known as yielding, parking or awaiting.</p> +<p>One of the problems with preemptive schedulers is that they usually need some kind of involvement from the compiler or hosting virtual machine in order to work. For this reason, most of the fiber libraries use cooperative schedulers to perform their work.</p> +<p>A cooperative scheduler doesn’t have a concept of preemption - once started by the scheduler, a fiber will execute until it doesn’t give back the control willingly. This is often done with dedicated programming constructs, and often is known as yielding, parking or awaiting.</p> <p>In cooperative variant, a fiber body is usually split into series of discrete steps, between which fiber gives control back to the scheduler.</p> <p>Keep in mind that these two are not mutually exclusive - a preemptive scheduler often provides a way for a fiber to return control back to it when it’s known that fiber won’t be executing any longer eg. because it has been put to sleep for a while.</p> <h3 id="Stackless-vs-stackful"><a href="#Stackless-vs-stackful" class="headerlink" title="Stackless vs. stackful"></a>Stackless vs. stackful</h3><p>A concept, that’s somewhat related to a topic above is the idea of stackless and stackful coroutines.</p> @@ -221,11 +221,11 @@ <li>Finite state machines - this variant is usually faster and can be encoded manually (example of such case is Akka actors), but for a human eye it usually doesn’t really read as a sequential step-by-step program execution, unless it has some support from the compiler itself (see: C# and Rust).</li> <li>Monadic sequencing via bind/flatMap operator, which is very popular in functional languages. While we cover it in more details in the rest of this blog post, for now it’s enough to say that it’s a way to chain callback-based behaviors together in a way, that resembles standard sequential code.</li> </ol> -<p>For sure one of the advantages of stackful coroutines is that they’re <em>mono-colored</em>: you can yield/continue coroutine execution from within any other function, while in the stackless variant splits your world into <em>two-colored</em> functions - synchronous and <strong>async</strong>hronous - where async one can be only called and yielded safely (without blocking underlying OS thread) from within another async function.</p> +<p>For sure one of the advantages of stackful coroutines is that they’re <em>mono-colored</em>: you can yield/continue coroutine execution from within any other function, while in the stackless variant splits your world into <em>two-colored</em> functions - synchronous and asynchronous - where async one can be only called and yielded safely (without blocking underlying OS thread) from within another async function.</p> <h3 id="Eager-vs-lazy-fibers"><a href="#Eager-vs-lazy-fibers" class="headerlink" title="Eager vs lazy fibers"></a>Eager vs lazy fibers</h3><p>We already mentioned two important events in fiber execution life cycle - starting and parking. Here I briefly discuss about different design decisions on when to start a fiber execution.</p> -<p><strong>Eager</strong> execution means, that fiber is started automatically after its creation. An example of such are Scala <code>Future[A]</code> and JavaScript <code>Promise</code>. Since execution process starts right away, we’re willingly resign from a certain degree of control over how or when to execute given fiber. Usually this is solved by wrapping a fiber creation into another function or lambda.</p> -<p><strong>Lazy</strong> execution is much more common and preferred way of work, as it allows us to separate place where we want to define our asynchronous sequence of steps from the place, where the execution details are defined. It’s used in C# TPL as well as pretty much in all functional languages implementations (excluding Scala futures mentioned earlier).</p> -<h3 id="Interruption"><a href="#Interruption" class="headerlink" title="Interruption"></a>Interruption</h3><p>There are also few decisions regarding premature escaping the fiber execution, also known as interruption/cancelation: one of them requires passing special object - a <strong>token</strong> - between method calls and explicit checking for its completion. It is how C# Tasks work. However putting such requirement onto the API user can be cumbersome and error-prone option. Therefore pretty much every other coroutine library either allows to direcly interrupt a fiber or (like in case of F# Async) passes cancelation tokens and check if they were triggered under the hood.</p> +<p>Eager execution means, that fiber is started automatically after its creation. An example of such are Scala <code>Future[A]</code> and JavaScript <code>Promise</code>. Since execution process starts right away, we’re willingly resign from a certain degree of control over how or when to execute given fiber. Usually this is solved by wrapping a fiber creation into another function or lambda.</p> +<p>Lazy execution is much more common and preferred way of work, as it allows us to separate place where we want to define our asynchronous sequence of steps from the place, where the execution details are defined. It’s used in C# TPL as well as pretty much in all functional languages implementations (excluding Scala futures mentioned earlier).</p> +<h3 id="Interruption"><a href="#Interruption" class="headerlink" title="Interruption"></a>Interruption</h3><p>There are also few decisions regarding premature escaping the fiber execution, also known as interruption/cancelation: one of them requires passing special object - a token - between method calls and explicit checking for its completion. It is how C# Tasks work. However putting such requirement onto the API user can be cumbersome and error-prone option. Therefore pretty much every other coroutine library either allows to direcly interrupt a fiber or (like in case of F# Async) passes cancelation tokens and check if they were triggered under the hood.</p> <h2 id="Implementation"><a href="#Implementation" class="headerlink" title="Implementation"></a>Implementation</h2><p>Since we talked a bit about various approaches, let’s get to the meat of this blog post: implementing our own coroutine library in F#. So, what properties will it have?:</p> <ol> <li>We use cooperative scheduling (we don’t want to tweak the compiler) of stackless fibers with support from F# computation expression for nice syntax.</li> @@ -268,7 +268,7 @@ <p>Now, since our cancellation is not explicit, we need to deal with few things:</p> <ol> <li>Whenever parent fiber is cancelled, all child fibers it spawned are also cancelled.</li> -<li>Whenever we cancel a fiber that loose the race, we <strong>don’t want</strong> to accidentally cancel a token of its parent.</li> +<li>Whenever we cancel a fiber that loose the race, we don’t want to accidentally cancel a token of its parent.</li> </ol> <p>This behavior implies at least using two separate tokens, however in practice it will be more pragmatic to make our <code>Cancel</code> token work as a tree hierarchy - this way we can easily keep track of things and support more complex scenarios.</p> <figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">[<Sealed;AllowNullLiteral>]</span></span><br><span class="line"><span class="keyword">type</span> <span class="title class_">Cancel</span>(parent<span class="operator">:</span> Cancel) <span class="operator">=</span></span><br><span class="line"> <span class="keyword">let</span> <span class="keyword">mutable</span> flag<span class="operator">:</span> <span class="type">int</span> <span class="operator">=</span> <span class="number">0</span></span><br><span class="line"> <span class="keyword">let</span> <span class="keyword">mutable</span> children<span class="operator">:</span> Cancel <span class="type">list</span> <span class="operator">=</span> []</span><br><span class="line"> <span class="keyword">new</span>() <span class="operator">=</span> Cancel(<span class="literal">null</span>)</span><br><span class="line"> <span class="comment">/// Check if token was cancelled</span></span><br><span class="line"> <span class="keyword">member</span> __.Cancelled <span class="operator">=</span> flag <span class="operator">=</span> <span class="number">1</span></span><br><span class="line"> <span class="comment">/// Remove child token</span></span><br><span class="line"> <span class="keyword">member</span> <span class="keyword">private</span> __.RemoveChild(child) <span class="operator">=</span> </span><br><span class="line"> <span class="keyword">let</span> <span class="keyword">rec</span> loop child <span class="operator">=</span></span><br><span class="line"> <span class="keyword">let</span> children' <span class="operator">=</span> children</span><br><span class="line"> <span class="keyword">let</span> nval <span class="operator">=</span> children' <span class="operator">|></span> List.filter ((<span class="operator"><></span>) child)</span><br><span class="line"> <span class="keyword">if</span> <span class="built_in">not</span> (obj.ReferenceEquals(children', Interlocked.CompareExchange(<span class="operator">&</span>children, nval, children')))</span><br><span class="line"> <span class="keyword">then</span> loop child</span><br><span class="line"> <span class="keyword">if</span> <span class="built_in">not</span> (List.isEmpty children) <span class="keyword">then</span> loop child</span><br><span class="line"> <span class="comment">/// Create a new child token and return it.</span></span><br><span class="line"> <span class="keyword">member</span> this.AddChild () <span class="operator">=</span></span><br><span class="line"> <span class="keyword">let</span> <span class="keyword">rec</span> loop child <span class="operator">=</span></span><br><span class="line"> <span class="keyword">let</span> children' <span class="operator">=</span> children</span><br><span class="line"> <span class="keyword">if</span> (obj.ReferenceEquals(children', Interlocked.CompareExchange(<span class="operator">&</span>children, child<span class="operator">::</span>children', children')))</span><br><span class="line"> <span class="keyword">then</span> child</span><br><span class="line"> <span class="keyword">else</span> loop child</span><br><span class="line"> loop (Cancel this)</span><br><span class="line"> <span class="comment">/// Cancel a token</span></span><br><span class="line"> <span class="keyword">member</span> this.Cancel() <span class="operator">=</span></span><br><span class="line"> <span class="keyword">if</span> Interlocked.Exchange(<span class="operator">&</span>flag, <span class="number">1</span>) <span class="operator">=</span> <span class="number">0</span> <span class="keyword">then</span></span><br><span class="line"> <span class="keyword">for</span> child <span class="keyword">in</span> Interlocked.Exchange(<span class="operator">&</span>children, []) <span class="keyword">do</span> child.Cancel()</span><br><span class="line"> <span class="keyword">if</span> <span class="built_in">not</span> (isNull parent) <span class="keyword">then</span> parent.RemoveChild(this)</span><br><span class="line"></span><br></pre></td></tr></table></figure> @@ -379,7 +379,7 @@ <figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">let</span> <span class="keyword">rec</span> run () <span class="operator">=</span></span><br><span class="line"> <span class="keyword">match</span> Seq.tryHead timeline <span class="keyword">with</span></span><br><span class="line"> <span class="operator">|</span> <span class="literal">None</span> <span class="operator">-></span> running <span class="operator"><-</span> <span class="literal">false</span></span><br><span class="line"> <span class="operator">|</span> <span class="literal">Some</span> (KeyValue(time, bucket)) <span class="operator">-></span></span><br><span class="line"> timeline <span class="operator"><-</span> Map.remove time timeline</span><br><span class="line"> currentTime <span class="operator"><-</span> time</span><br><span class="line"> <span class="keyword">for</span> fn <span class="keyword">in</span> List.rev bucket <span class="keyword">do</span> </span><br><span class="line"> fn () </span><br><span class="line"> run ()</span><br></pre></td></tr></table></figure> <p>We’ll try to pick the first entry from the timeline - since here we use F# map, which is sorted in ascending order, we know that first entry is the one with the shortest execution timeout. We update our “current” time to match the expected one we calculated earlier, and finally we execute all functions scheduled at that time and repeat the loop all over until we eventually run out of scheduled actions.</p> -<p>Now here’s the trick - we use <code>List.rev</code> to execute functions in the same order in which they were scheduled, because we want our tests to be deterministic and our bugs to be reproducible. However this is not the only strategy - <strong>since we know that functions in the same bucket could as well be executing in parallel, we could shuffle them around in different permutations for early discovery of some data races!</strong> I’ll won’t dive into it, but leave that idea as food for thoughts for you.</p> +<p>Now here’s the trick - we use <code>List.rev</code> to execute functions in the same order in which they were scheduled, because we want our tests to be deterministic and our bugs to be reproducible. However this is not the only strategy - since we know that functions in the same bucket could as well be executing in parallel, we could shuffle them around in different permutations for early discovery of some data races! I’ll won’t dive into it, but leave that idea as food for thoughts for you.</p> <p>One last note about the test scheduler is that isolating it from the actual physical clock means, we cannot trust our time functions (like <code>DateTime.UtcNow</code>) any longer. This shouldn’t really be an issue though - because relying on physical time would potentially make our tests indeterministic, we didn’t want to use it anyway, right?</p> <p>However, we need to be able to obtain current time from the scheduler, so we need to extend its API:</p> <figure class="highlight fsharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">type</span> <span class="title class_">IScheduler</span> <span class="operator">=</span></span><br><span class="line"> <span class="keyword">abstract</span> UtcNow<span class="operator">:</span> <span class="type">unit</span> <span class="operator">-></span> <span class="type">unit</span></span><br><span class="line"> <span class="comment">// ... other methods</span></span><br><span class="line"> </span><br><span class="line"><span class="keyword">type</span> <span class="title class_">TestScheduler</span>() <span class="operator">=</span></span><br><span class="line"> <span class="keyword">let</span> <span class="keyword">mutable</span> currentTime <span class="operator">=</span> DateTime.UtcNow.Ticks</span><br><span class="line"> <span class="comment">// ... rest of the implementation</span></span><br><span class="line"> <span class="keyword">interface</span> IScheduler <span class="keyword">with</span></span><br><span class="line"> <span class="keyword">member</span> __.UtcNow() <span class="operator">=</span> DateTime(currentTime)</span><br><span class="line"> <span class="comment">// ... other methods</span></span><br></pre></td></tr></table></figure> |