Re: SBCL Fibers proposal

#+OPTIONS: toc:nil num:nil

* 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/ ([[https://web.archive.org/web/20260308181851/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.
* 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.  doi:10.1145/1073970.1073974
  - LêEtAl2013 :: Correct and Efficient Work-Stealing for Weak Memory Models. 2013.  doi: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/