Re: SBCL Fibers proposal
Christophe Rhodes via Sbcl-devel <[email protected]> Fri, 13 Mar 2026 09:12:12 +0000
| Newsgroups | gmane.lisp.steel-bank.devel |
|---|---|
| Message-ID | <[email protected]> |
Christophe Rhodes via Sbcl-devel <[email protected]> writes: > I've now had a chance to read the proposal and write some observations, > which are attached. I hope that this can help provide a basis for > useful conversations. (I took a guess at what mail archive services would do with a text/plain attachment, and guessed wrong. The below is a plain-text export of my review, with all the same content, mostly so that I and others can refer to it directly in future. Apologies for the duplicate content.) Christophe Executive Summary ═════════════════ This is my personal review of SBCL Fibers: Lightweight Cooperative Threads, version dated March 1, 2026, available at <https://atgreen.github.io/repl-yell/posts/sbcl-fibers/> ([Internet Archive link]). Perhaps more than usual it is important to stress that I do not claim to speak for or on behalf of my employer, and all opinions expressed in this review are my own. Although there exists implementation code related to this document, I have not looked at that in forming this review. On balance I believe that this document describes a reasonable design for cooperative user-space threads in SBCL. I have a number of high-level questions about the design that might influence the overall direction and shape of an implementation; some substantive criticisms of aspects of this specific design as expressed in this document; and a list of points of detail of various degrees of importance. I also include a small section reflecting on the process of reading the original document and writing this review. [Internet Archive link] <https://web.archive.org/web/20260308181851/https://atgreen.github.io/repl-yell/posts/sbcl-fibers/> High level questions ════════════════════ Structured Concurrency ────────────────────── My reading of this document is that it does not go as far as a design for an implementation of Structured Concurrency [Sústrik2016, Smith2018]. As far as I can tell there's no notion in this document about parent-child relationships between fibers (section 2.6), nor of cancellation protocols. That's fine! I don't know if Structured Concurrency is a uniformly-desireable user-space programming paradigm. But it might be interesting to think about how the design in this document would have to be extended to support Structured Concurrency efficiently. Can it be done without any changes whatsoever? Or would there need to be substantial changes to the scheduler, or the processes of fiber creation and reaping processes? Could the scheduler design in this document be hookable to extend it, or does that offer too much flexibility for the user to accidentally degrade performance? Again, it's totally fine if the implementation of these is out of scope, or left for a future project – but it would also be interesting to know what the gap is. (And, also, whether there are users out there who have existing workloads that are naturally expressed using Structured Concurrency). Testing, single-threaded implementation ─────────────────────────────────────── Testing the implementation of fibers is almost not mentioned in this document at all. Maybe there's an implicit expectation that there will be some suite of unit tests for the individual components (maybe a strong set of tests for the circular array implementation underlying the Lev-Chase deque, some unit-like testing for the deque itself, some integration tests for the deque along the lines of existing concurrency tests, and so on…) I wonder if we can imagine a way to increase confidence in testing faster: maybe by running the existing quite fierce regression test suite with various modes. One where each `with-test' form runs on its own fiber? One where `sb-thread:make-thread' runs a fiber instead of a thread? Run each test file three times, on three fibers, divided between two carriers? Something else along these lines? Perhaps along the same lines of thinking about unconventional ways of imagining running with fibers: how possible is it to imagine fibers of this design in a single-threaded Lisp, multiplexing everything (including the REPL) through a single scheduler group with a single carrier thread? Pinning, growing (and shrinking) scheduler groups ───────────────────────────────────────────────── One thing I have found useful in some contexts is to be able to grow thread pools – in this context, scheduler groups (unless I've misunderstood). Is this a possible (and desireable) thing to do in this model? In particular, if a fiber pins itself, that can affect the progress of other fibers in that scheduler group. If enough fibers in a group pin themselves, then all other progress can be starved. Supporting growth of a scheduler group (adding cariers) on pin, as maybe an option, might be worth considering? Of course if we grow a group, we might also need to think about shrinking too. On the subject of pinning: the "pin" concept in this document expresses both "must not be moved to another thread" and "must block rather than yield". Are these two intrinsically coupled, or is there a case for a thread-affinity-like "must not be moved to another thread" while still allowing yielding? Performance ─────────── I found myself underwhelmed by the performance measurements presented in section 14. (I don't really know what I expected). Is the ~1.5x improvement in HTTP request handling expected (with reference to fiber-like implementations in other languages, for example)? Is there potential for a more noticeable tail latency (say 99th-percentile) improvement? Section 14 says that fibers provide a "decisive" advantage at high connection counts. Is that actually true? What about the statement about the kernel's scheduler and thousands of running threads (section 14)? From the table in 14.1 it seems to me that the kernel scheduler is coping pretty well with 25,000 threads? Substantive critiques ═════════════════════ Unclarity through inconsistency ─────────────────────────────── The terms "scheduler" and "scheduler group" are used as distinct entities in various places (for example, in the terminology definitions in section 1.3), and conflated elsewhere. For example section 3.1, but in section 2 and probably elsewhere as well. I think this also has led to some lack of clarity in this document about the API, which entities are first-class, which entities are manipulable from "outside", etc. Is there an inconsistency between the handling of a scheduler group's active count? It looks like a scheduler group wants to terminate when its active count is 0 (sections 8.1, 8.5) but how does that square with setting up a scheduler group and submitting fibers to it (2.7.2)? Debugger integration ──────────────────── It seems to me that this design somewhat neglects the interaction between errors in fibers, the usual interactive debugger, signalling (including resignalling) conditions to give outer handlers a chance to handle or decline them; and restart-based protocols. I think it is potentially surprising to users, and it was to me, to find that by design in section 12 signalling a condition of type `error' with the `error' function in a fiber would not cause a debugger to be invoked. This might be a function of different expectations; I can imagine that a workload of tens of thousands of fibers might suffer badly if they all go wrong and the session has tens of thousands of pending debugger sessions. So, it might be that there is a constraint that means that the debugger shouldn't be offered, but why? What are the tradeoffs here? If debugger support within fibers is possible, that would influence the design of guard pages for at least the control stack: replicating the existing support in the runtime for a debugger session when the (first) stack guard page is hit implies a need for a second stack guard page, which when hit sets up execution to unwind the stack completely – along the lines of the guard page described in this document. GC correctness ────────────── Some of the sections of the document are substantially reference to code that (by the terms of this review) are out of scope; particularly the GC integration section. This makes it impossible to assess any kind of correctness in the design. However, at least the assertion in section 7.8 that the GC threads waits for all mutator threads to reach a safepoint is wrong in general; the GC is mostly not safepoint-based. (Section 7.8 is not convincing in general) Context switching performance ───────────────────────────── The context switch microbenchmark suggests that some of the earlier sections' descriptions of fiber context switching as fast needs revising. The emphasis on a a "hand-written assembly routine" (section 1.2) for register saving is perhaps misplaced given everything else that needs to be done (section 3.3, which feels like it might have been better placed under section 4 with the rest of context switching.) Fiber results ───────────── The document is not clear about returning results from fibers. I would expect any API around return values to transparently handle multiple values; meanwhile, condition objects are valid values and must not be punned to indicate errors. I would generally expect unhandled serious conditions to trigger a debugger, or failing that to abort in some way (and for that to cause fiber-join to signal some kind of condition with useful restarts). But that's not very consistent with an API like run-fibers returning a list-of-results. On the other hand, handling multiple values straightforwardly will presumably involve allocation, which might not be desireable. I think this whole area needs more thought, or at least it's not obvious to me what the right thing is. Chase-Lev Deque ─────────────── The Chase-Lev Lock-Free Deque [ChaseLev2005] depends (in the small print) on comparison checks between top and bottom; top only ever increases. If stealing dominates, at some point bottom will overflow. In [ChaseLev2005] the assertion is made that 64-bit quantities for top and bottom give multiple years of runtime even with highly active stealing before overflow can occur (64 years at 4 billion steals per second). This is fine, and remains fine if these fields are implemented in terms of `fixnum' on 64-bit platforms (with 61 or 63 bits on PPC64 or the other 64-platforms). However, the document describes implementing this data structure on 32-bit platforms, and I'm not sure that's straightforward: with the same steal rate assumption, the lifetime before overflow is about half a second, or less if using 30-bit fixnums. (Implementing a 64-bit field is not straightforward because top must be updated atomically, which means we would need double-width compare and swap or equivalent). Also on the Chase-Lev Lock-Free Deque, the implementation in [Lêetal2013] quotes substantial performance improvements on relaxed memory architectures, though note the dangers of transliterating algorithms from one language to another observed in this specific case by [Wingo2022]. Points of detail ════════════════ • Section 1.2, "must see a consistent view of all fiber state". What does this mean? • Section 1.2, "small per-fiber memory footprint". 256KiB is only 32 times smaller than our default 8MiB stack size; that feels like one order of magnitude more space, but is that obviously transformative? • Section 2.1: do we really want an additional guard page on top of the 256KiB stack? Or just to `mprotect()' the last page? • Section 2.1: "analogous to the `:initial-bindings' argument to sb-thread:make-thread". There is no such argument to sb-thread:make-thread. • Section 2.2/2.3/2.4: the `fiber-yield' / `fiber-sleep' / `fiber-park' lambda lists are weirdly inconsistent. I think it would benefit from inversion: thinking of `fiber-park' (or whatever it should be called) as the primitive, and implementing `fiber-yield' and `fiber-sleep' in terms of it. • Section 2.2: "… the fiber becomes immediately runnable again (it is pushed back on the scheduler's deque) …". As described I think this leads to one cpu-bound fiber starving all other fibers on a given carrier/scheduler – should there be some other auxiliary parking spot for yielding fibers which are immediately runnable? • Section 2.4: "The scheduler calls it during maintenance passes…". It's perhaps important to make it explicit that the predicate will be called in the dynamic environment of the scheduler, and not the one of `fiber-park' – so the predicate has indefinite extent and must capture any special bindings it wants to preserve. • Section 2.4: "Internally, `fiber-park' stores the timeout as a deadline… and passes the predicate to `fiber-yield'". As described I think if the fiber is pinned this leaves the scheduler in an inconsistent state, which might matter if something handles the error from `fiber-yield'. • Section 2.6: `fiber-scheduler-group' is not in the table of API functions or described. Why is it accessing the current scheduler rather than (as its name suggests) the current fiber? • Section 2.7.1: is it wise to expose the scheduler `idle-hook' function in a "simple" API? There are surely so many ways to mess that up that I would suggest leaving it out of anything exposed as simple. • Section 2.7.2: is it legal to have a null `initial-fibers' argument to `start-fibers'? Does the scheduler group instantly end (see section 8.1)? • Section 2.7.2: the argument order to `submit-fiber' feels reversed from what is natural to me. • Section 2.7.2: If I didn't understand the results of fibers now, I *really* don't understand how `finish-fibers' is meant to be used. • Section 2.7.2: I don't understand what `fiber-group-done-p' is for. If it returns true, I can't take any action based on that because it might be false an arbitrary small amount of time later. If it returns false, what does that imply? What can I not do if it returns false, submit new fibers? • Section 2.8.5: `sb-ext:wait-for' documents its timeout as waiting "at most approximately <timeout>". If I've understood correctly, the deadline-based scheduler in this document works on an "at least <timeout>" basis. • Section 2.9: "Pinning increments a per-fiber counter". Can pinning be done to fibers from outside? The `fiber' argument to `fiber-pin' / `finer-unpin' / `with-fiber-pinned' suggests that it can. Then the counter needs to be manipulated atomically. • Section 2.9: if pinning can be done from outside a fiber, I don't see how it is possible to use `fiber-can-yield-p' safely. • Section 2.9: it might be more Lispy to simply `signal' a documented condition, rather than the `*pinned-blocking-action*' cases, and allow users to handle that condition as they choose in their fibers. • Section 2.10: "The list is captured under a mutex to provide a consistent snapshot". What else contends for this mutex? Consistent with respect to what? • Section 2.10: if there is `list-all-fibers' should there be `map-all-fibers' and/or `do-all-fibers'? • Section 2.10: should there be a `list-all-fibers' analogue for a scheduler group, as well as or instead of a global collection of fibers? (What is this used for?) • Section 2.10: should there be an introspective function to determine why a fiber is `:suspended' (what it might be waiting for)? • Section 2.10: how can `fiber-alive-p' be safely used, given that its state might change immediately after return? • Section 2.10: is it reasonable to request the equivalent of `backtrace-as-list' for `print-fiber-backtrace'? • Section 2.10: what does `print-fiber-backtrace' do for fibers in `:running' state? • Section 2.10: what does `print-fiber-backtrace' do if the fiber it is backtracing is resumed while the backtracing is occurring? • Section 2.10: is there a need for intercession? (aside from `fiber-pin'). For example is it reasonable to bake in some kind of way to cancel fibers? • Section 2.11: what can I do with the return value of `make-fiber-scheduler'? I think all the other API functions operate either on fibers or on scheduler-groups. • Section 3.1: "A single carrier with a single scheduler is the simplest configuration". In section 1.3 "Terminology" schedulers are defined to have a 1:1 correspondence with carriers. • Section 3.3: Yield: is there a race here between steps 5 and 6, and things like `print-fiber-backtrace', where the state is `:suspended' but not quite all of the state is saved? • Section 3.3: Resume: there is nothing in this set of steps that sets the fiber's state to anything (presumably `:running'?) • Section 4.1: While it might be obvious that the FPU state is shared between fibers in this implementation, that is Lisp-user-visible in a way that segment registers and signal masks aren't, and probably needs its own call-out for things like rounding modes, enabled exceptions and the like. • Section 4.2: why not unconditionally pass and patch the thread register? • Section 4.2: will the `ret' at the end of the sequence mispredict its target essentially 100% of the time? • Section 4.5: I think it's OK to use raw machine words but I also think that a VOP with sap arguments called inline with suitable SAP constructors should also not allocate anything. • Section 4.5 "TLS scratch hash table" a forward reference to section 6.2 would have been nice. • Section 5.1: Some day I will hunt down whoever it was who decided that downward-growing stacks should grow upward on the page, and give them a piece of my mind. • Section 5.2: calling `lose()' from hitting a guard page – as opposed to "just" killing the fiber – is excessive, isn't it? Can we do better? • Section 5.3: "singly-linked free list protected by a mutex": for some fiber workloads, what is the expected contention here? • Section 5.5: I don't see why relocating the stack would invalidate return addresses. (I agree that given imprecise heap references on the stack relocation is not possible). • Section 6.1: "This create a problem" is missing an "s" on "create". • Section 6.2: Pass 1 could perhaps be better done with a bit-vector? If we are avoiding consing, then a pre-allocated bit-vector capable of storing a bit for each of the possible TLS indices will be much smaller than a pre-allocated hash-table capable of doing this. • Section 6.4: `handler-case' is a much higher-level construct than `throw' and `unwind-protect': if catch and unwind save/restore are working, I would not expect anything extra to be done to support any of the condition system (`signal' / `handler-bind' / `restart-bind') can be implemented in pure CL [Pitman1988]. • Section 7.7: `pseudo-atomic' is a further mechanism for inhibiting GC for short sequences of machine instructions. • Section 7.7: having a large `without-interrupts' block stops interactive debugging from SIGINT or related signals, or even stack traces from errors. This might affect the debuggability of the critical parts. (That might be OK) • Section 7.7: is it in fact the case that `without-interrupts' blocks the stop-for-GC signal? I think this might be a misunderstanding. • Section 7.8: can the inconsistent state be observed by anything else? (introspective tools?) • Section 8.2: should the period-64 maintenance cycle be a parameter? Or adaptive in some way? • Section 8.4: after calling `destroy-fiber', what happens to the fiber's result value(s)? How does this interact with returning values? • Section 8.5: the 1ms timeout seems arbitrary here. Is it a parameter? Should there be some kind of backoff? Why is there a need for a timeout at all? • Section 8.6: "64 is a compromise: at 2 million switches/sec". Where does the 2 million switches per second come from? If it's from the measurement in section 14.4, that value is an upper bound (so the quoted ~32 microseconds is a lower bound). What is the value for more typical workloads, and how does that affect the provision of "sub-millisecond responsiveness"? • Section 9.1: `top' is in general written by the owner (via CAS) as well as by thieves. It is also worth making explicit here that `top' is only ever incremented, never decremented. • Section 9.4: I know it's this way in the literature, but just as with stacks and their diagrams I will regret `top' being below `bottom' and how nonsensical that makes the `loop' bounds seem. (I believe they're correct). • Section 9.4: The sentence "The owner publishes the new buffer…" is unclear, but I think the point is that the new buffer is separate from the `top' and `bottom' values, and thieves can in principle steal all the active entries while the buffer growth is occurring because of the atomic incrementing of `top'. (The word "harmlessly" should perhaps be "correctly"?) • Section 9.4: Is there a case for shrinking the circular arrays if they are underpopulated? • Section 9.5: `random' might be too heavyweight for this, at least with the current MT19937-based implementation. Are there alternatives? (last-successfully-stolen-index + self-index mod n, maybe?) • Section 10.5: I didn't understand "with a fast-path check against the scheduler's `ready-fds' hash table on Linux". • Section 10.6: The 100ms and 10ms values for caps here seem arbitrary. Should they be parameterized? Why are they different? • Section 10.7: given that we have a hash table of fds to waiters (section 10.3), why is the single poll O(W)? Would it not be O(FD) instead? • Section 12.1: I'm not convinced that even if we want to not support interactive debugging, this is the best way of writing that. It interferes with handlers resignalling outwards before deciding to handle; it doesn't set up useful restarts; more prosaically it doesn't handle `serious-condition'. (Also, I think it would be kind if it bound a handler that attempted to call `continue' before abandoning entirely). I agree with the design goal in section 12.2 that an unhandled "user-mode" condition in one fiber should not take the whole carrier down without explicit user intervention, but maybe these decisions are better expressed using restarts? • Section 12.4: "the fiber's `gc_info' is widened to cover the full stack". Is there something that ensures that the unused part of the fiber stack is zeroed, or might the GC see old data at that point? • Section 13.7: `interrupt-thread' is fundamentally broken and should not be used. "on carrier threads" is superfluous. • Section 14.2: the table is, well, not very interesting. I think information about how the system behaves with different values for thread control stack size (controllable by the `--control-stack-size' command-line argument to SBCL) would be more illuminating. • Section 14.3: if the GC pause times scale linearly, as is expected, what is the coefficient? (And how does it compare to an equivalent number of threads?) • Section 14.4: please use the same units for both rows in this table. Metareview ══════════ Positives ───────── I was far from an expert in user-mode threading before starting this review. (For the avoidance of doubt: I'm still far from an expert). This process has forced me to read, think and learn, and has probably given me an improved understanding of some of the programming frameworks that I interact with (and have to debug) in the course of my work. Also, to the extent that this is a test-bed for assessing LLM-assisted (at the very least) design, I found the document to be not excessively alienating. I don't know exactly the process in getting it to the form in which I received it, but whatever it was it ended up being of an comparable quality to documents I have read in the past – for the avoidance of doubt, that's a wide range: I've read some truly awful student project reports and conference paper submissions, as well as some glorious scientific work. Annoyances ────────── I have found the process of engaging with this document difficult along three axes, which is two more than the usual. Because of the process that generated it, and the use that it might be put to, I have felt that: 1. Each sentence needs to be read in detail and with suspicion, because there is a reasonable chance that some fraction of the facts asserted within the document will be wrong. 2. Each design decision needs to be read in detail and considered through the lens of a perverse implementor with limited cultural context. 3. Any feedback that I give might end up being shoved into a context-free process for distillation before being considered by any humans. I have experience with (1) from my past life as an educator: this part is not unlike reading student work, or indeed research paper submissions. I have experience with (2) from work in my current position, where critiquing design documents written by people who might not be the same people as will eventually implement the design is relatively rare but not unknown in my experience. Each of (1) and (2) I can work with; both at once is a bit painful, but not unlike working with interns, Summer of Code students, or the like. Unfortunately I also have growing experience with (3); the less said about that the better. All three at once is tiring! I think I'd recommend for us to guide newcomers to avoid triggering all three of these concerns at once. The easiest one to alleviate, I would suggest, is (3), and I would encourage people to open discussions early: commit to frequent, repeated interactions to build trust that those interactions are rewarding to all parties. In the LLM world, (2) is perhaps unavoidable; although best practice [Willison2026] might include thoroughly reviewing code before sending patches or pointing to branches, in practice any LLM-authored patch coming from a design document like this will have to be read in fine detail. Can we alleviate (1)? The superficial polish of LLM-authored prose, with its tendency towards persuasive writing, coupled with the nature to produce content of similar shape to the training set, makes it likely that we will be dealing with plausible falsehoods (or "hallucinations"; see [Broad2026] for a recent example) and the consequences of them (such as [Xkcd978]) for the forseeable future. I acknowledge that there's a continuum of tools to support writing, from spell checkers through automated translation to style assistance, generative systems and beyond; I don't know what the answer is here. (Perhaps once again it boils down to trust and understanding, which can only be built through repeated positive interaction). Addendum ╌╌╌╌╌╌╌╌ After finishing this review, I showed it to a colleague. They pointed out to me that the 8 MB per-thread stack size quoted throughout the document, in section 1 (motivation), 5 (design) and 14 (measurements, if multiplying numbers is a measurement) is not correct. I offer this as yet another datum: despite my being primed to suspect every claim in this document, and aiming to read the document as cautiously as possible, the value quoted looked plausible, was used consistently, and its plausibility allowed that value to just slide by. References ══════════ Broad2026 Why we should care about ChatGPT's accuracy gap. <https://leahbroad.substack.com/p/chatgpts-accuracy-gap-is-dangerous> ChaseLev2005 Dynamic Circular Work-Stealing Deque, 2005. <https://doi.org/10.1145/1073970.1073974> LêEtAl2013 Correct and Efficient Work-Stealing for Weak Memory Models. 2013. <https://doi.org/10.1145/2442516.2442524> Pitman1988 CONDITIONS. <https://www.nhplace.com/kent/CL/Revision-18.lisp> Smith2018 Notes on structured concurrency, or: Go statement considered harmful. <https://vorpus.org/blog/notes-on-structured-concurrency-or-go-statement-considered-harmful/> Sústrik2016 Structured Concurrency. <https://www.250bpm.com/p/structured-concurrency> Willison2026 Agentic Engineering Patterns. <https://simonwillison.net/guides/agentic-engineering-patterns/> Wingo2022 on "Correct and Efficient Work-Stealing for Weak Memory Models". <https://wingolog.org/archives/2022/10/03/on-correct-and-efficient-work-stealing-for-weak-memory-models> Xkcd978 Citogenesis. <https://xkcd.com/978/> _______________________________________________ Sbcl-devel mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/sbcl-devel