Lambda the Ultimate

This is a reply to the opening question in Keean Schupke's Variables post yesterday. I don't expect to discuss this further, unless I see something surprising. Correcting misapprehension is not one of my compulsions, and neither is teaching how to do things that seem obvious to me, beyond friendly summary in sketch form. Infinite patience is more of a workplace habit.

Could you explain how you handle variables across async calls that return to the event loop, so that I can benchmark this against the setjmp method?

Variables are in stack frames, same as always when locals live in stack frames. The only difference is whether frames are in a contiguous stack array or in a discontiguous stack linked list. When a thread suspends by blocking, variables stay where they are on the stack. When a fiber suspends by parking, variables also stay where they are on the stack. You are proposing to copy parts of a stack array, and want to benchmark this against zero-copy stack lists, because you have a hypothesis that copying might be faster.

That answer appears earlier in the other discussion, but there's a lot to read so I'll boil it down. As prerequisite, one should read about stacks, call discipline, and activation frames in plain vanilla old-school implementations of programming languages that use frames, so backtraces are found easily by following frame pointer (fp) list linkages. Old treatises on programming 68K in assembler give fine frame discipline explanations that are easy to read.

Suppose you look at some C code whose stack is contiguous in the address space, with frames going up to main() and beyond, laid end-to-end in contiguous memory, typically linked in a list via frame pointers (which is where a debugger gets a backtrace when you ask). If you rewrite such code to use CPS (continuation passing style), one way to do this instead is via heap-based cactus stacks (aka spaghetti stacks) where each frame is separately allocated, so the stack is a linked list of frames instead of a contiguous array. Some folks make the mistake of assuming this means all calls change this way, but calls near the bottom of a call tree can remain as they were before, using a conventional contiguous C stack that unwinds to the list version upon return to trampoline. (This is not return to an event loop; find out what is meant by trampoline -- it's not complex compared to anything abstract, but I do find writing style of functional language folks using trampolines almost impossible to follow when implementation is not described imperatively in terms of which memory locations change.)

One way to implement fibers is via setjmp/longjmp after copying part of the stack to and from a location on the heap. Another way is by switching which frame list is now the "top of stack" without doing anything at all to the contiguous C stack. Schupke proposes to benchmark which is faster, because I claimed the bottleneck was memory bandwidth, where touching more cache lines is slower. A good benchmark can probably be constructed, if realistic stack populations are represented, with a range of optimistic and pessimistic sizes likely bracketing what actually happens. You would need to implement the heap frame approach efficiently, using frames pooled in standard sizes that are always cache-line aligned (and preferrably powers of two in size, aligned to addresses that are a multiple of that size). There's not much good in having a frame smaller than, say, a 64 byte cache line. Obviously cache lines vary to larger sizes.

A valid benchmark must also cause a realistic cache-line pressure via memory load corresponding to an actual application where you want to use far more fibers than you can afford to have threads. Your benchmark should model live traffic from active connections in a server with many thousands of connections, where only some are currently active, but each is moving a lot of data through memory and therefore completely flushing the cache almost continuously. Assume it's gigabit plus transfer rates.

Say a stack is typically about sixteen to thirty frames deep in some application, like a network stack that is perhaps implementing IPsec or deduplication. You can just go sample a population of stack frames in some application, or make some assumptions about distribution in frame count and size. In server side network code, it's common to see a lot of temporary buffers on the stack for staging messages, logging control flow, analyzing IPv6 addresses, and consulting a lot of policy description. (When debugging I log a backtrace everywhere something significant happens; very deep stacks are common.) Small and shallow stacks in this context are rare to the point of non-existence.

Depth (in frame count) in a fiber stack would depend on where fibers are introduced: toward the top of a network stack or at the top of some nested feature like IPsec and dedup. Closer to the leaf end of the call stack is less than half, but that end has larger frames because temp bufs show up more as the mix moves from policy to mechanism and binary formats get staged for concrete processing. Total number of fibers depends on how many things occur concurrently per connection activity: not very many for IPsec, but a lot for dedup with high granularity fragments, like every 2K on average. At one end you need a handful of fibers per connection; at the other you need dozens of fibers per connection.

For a benchmark with any relation to reality in server loads causing high memory pressure, where cache lines turn over continuously, you need at least thousands of fibers whose size average somewhere between 2K and 16K, where 4K to 8K is plausible. This is exclusive of actual i/o buffer space, which is bigger, and isn't relevant to a benchmark, beyond causing cache line pressure much greater than caused by fibers.

Awakening a fiber makes it's stack active. Normally this will be all or nearly all cache line misses if a lot of i/o happened while a fiber was parked. For stack frame lists, this means the topmost frame has at least one cache line miss. For contiguous stack frame arrays, this means every frame you copy before calling longjmp is a cache line miss. I would expect the setjmp method to come in at more than an order of magnitude worse. About 50 times as many cache line misses would not be surprising, but seat-of-pants guesses are often not very good. Maybe you can copy large swathes of memory using instructions with no effect on cache lines at the destination, but when awakening a fiber we still expect the heap-based source stack to be out-of-cache when read.

Edit: Regarding trampoline efficiency, it's okay with me that async calls dispatch up to several times slower when they might park a fiber. (Extra cache line misses are worse than extra function calls.) Highest priority is efficiency at or near leaves of a call tree, which are far more numerous than inner nodes. Tight loops and local graphs of calls with bounded non-parking behavior don't get rewritten to dispatch via trampoline; instead they stay the same and operate as efficiently as an optimizing C compiler makes them using normal C stack that unwinds upon return to trampoline. Local areas of in-the-small code is normal C; only wide areas of in-the-large code needs CPS rewrite around points where context switches can occur. It's a hybrid tactic of old and new stack style. Not every sort of trampoline requires special privilege, or costs more than any other kind of branch; the only extra cost in my model is branching more times and making more implicit calls.

The main user class I think about is a developer, usually one who will see C source, before and after rewrite for fibers. Call this user Jim: a C dev who is working with multithreaded effect. Another class of dev may compile another language to C without caring about C any more than assembler; say this is Ann (my sister) who writes in Scheme, a sidekick of Ivy (who focuses on C++). Last is end user Tom (one of my three brothers) who doesn't code much, unless it's writing tiny HyperCard scripts. Tom understands no C whatsoever; Ann can scrape by in C; Jim lives and breathes complex concurrent server side C.

My main audience is Jim, until I write a Scheme or prototype a HyperCard; and only then I'd write docs for Ann and Tom. Jim will be able to see everything reified after rewrite. I only use term fiber here at LtU because it's a standard term. In my docs I would only use fiber to explain a job, in more abstract terms.

Replying to Keean Schupke's Thorn is fine:

It was more the part about abstraction, that is if as a user I can see the difference between a Thorn fibre (job) and a generic fibre, there is something wrong.

I can see that for Tom driving the GUI of an end user app. Ann needs to know both words. Jim has to debug job infrastructure when trying to prove it isn't jobs that are broken when some other bug occurs.

Therefore I only expect to see the word 'job' or Thorn fibre when discussing how Thorn implements fibres internally. I prefer Thorn fibre to job, but I understand that's just my personal preference. When discussing the user view of Thorn I think we should be talking about fibres and LWPs,

Term job has a long tradition in computing. I first heard it when submitting Fortran punched card decks in the 70's, before I learned Pascal in college, where we still used punched cards. (No, I learned Dartmouth Basic first in 1975 on a paper terminal. C I learned by 83.) To schedule a run you needed to add job control cards to a deck. Systems understood a job control language. The concept of job is essentially one run of a program. This also applies to how job is used to described job control in unix shells. And when you think about it, an executing fiber is one run of a control flow, and that's what a Thorn job is. The idea that code might run as a control flow in the future is fiber: a blueprint for execution. But when actually running, it's a job. Sounds clear to me anyway. Having more than one way to say it also affords definitions that are not quite so painfully circular.

because it doesn't matter to me (a Thorn user) how they are implemented, and my intuitions about fibres from other fibre systems should apply without modification.

That's pretty reasonable. The ways in which you might need to know how they are implemented would involve situations where you directly parked or unparked a job yourself, because of privileged information you had, not represented some other way by existing interfaces.

In other words we are really discussing generic fibres and LWPs and that the platform is Thorn is irrelevant unless discussing the internals of Thorn.

Sounds good to me. Acronym LWP has two problems. First is a three-syllable letter within. Second is ambiguity if you pronounce it loop, which is said often when discussing code, so that doesn't work. It's a good name in print though.

but sometimes an outside perspective can be useful, or shine light on things in a different and unexpected way.

Yes, this is one reason I like talking to people: I want to be surprised. I'm especially interested in new spin on old ideas too, if outright surprise can't be had.

I agree on your thoughts about languages in general, although I am not a fan of Lisp. I like the 'idea' of Lisp, and writing a Lisp interpreter is fun, but I don't actually like programming in Lisp. I prefer my functional languages pure, and I find object mutation and looping constructs easier to read. I quite like programming in Ada, apart from its generics (which are module-like rather than C++'s type-class like templates) and its treatment of pointers. I find myself agreeing with a lot of things you write, and I think our philosophy of programming is similar in a lot of ways.

With any language, I have the most trouble with abstraction system of a person showing me sample code. In my favorite languages, people can write the weirdest looking things, just because of the way they think. (Often from being cargo cult copy-and-paste, when a dev doesn't know what it means, exactly.) If you haven't implemented a Lisp or used one much, I'd expect weirdness of Lisp to often be from the person who wrote the code. For example, if a Haskell programmer wrote Lisp in favorite idioms, I'd have no idea what it does. Because Lisp is low in syntax, you're likely to get a naked view of the abstraction model.

I would like to discuss this too. I think Erlang handles this in a very elegant way.

A lot of my current approach to fiber design started out from aiming to make C more like Erlang in some way. I'm not sure exactly when I started that. Maybe ten years ago, plus or minus a little. I haven't used it though. I'm more interested in the story about things work, rather than playing with them, unless I need to get something done.

Shared memory (and locks) are problematic, and parallel (concurrent?) processes communicating by message passing seems a better model to me, however I am concerned that it may be less efficient than the thread model. However there is a large semantic overlap. If we consider the 'lock' on an area of shared memory to be a token that only one thread can possess at a time, you could see that this could be an access handle, that you pass from thread to thread in a message.

People famously make a lot of mistakes with shared-mem concurrency, I suspect partly because not enough diagnostics are included. I was once unable to get folks to add identity of who held a semaphore, so we could diagnose deadlocks clearly. Usually the advice is: stop making mistakes! I think we should pay a tax in both space and time to reveal concurrency bugs often, even if sometimes there are false negatives (when you fail to report its wrong). Just catching a good percentage of them in a run will weed them out.

I'm pretty interested in ensuring resources are released, especially when it comes to locks. Holding locks anonymously is not okay. I generally don't like shared multiple writers; I prefer one writer, who takes and executes requests to make changes on behalf of other parties, when a shared state model is really necessary. A central server is often effective when you can trust just one writer. Blame is distributed and dilluted when multiple writers could have done something wrong.

[I think it only becomes really complex when database semantics are present, and you can't lose data. I actually don't want to talk about that. :-) It's just as involved as programming language discussions. Certain things must be done carefully with layers of backup, and can't be done with glib one-layer locking schemes. But we need to provide tools following clear and precise rules for folks wielding them to do hard things. I think mainly people want a guarantee locks cannot be leaked, because they can handle redundancy in guaranteeing copies for transactions themselves.]

This is the kind of concurrency/parallelism model I am thinking of. Of course this only models a simple mutex, there are other possibilities to consider like a shared read lock, and exclusive write lock.. This seems to generalise the single lock nicely, but has the problem of how to restrict the shared read handle you may have already given to other processes when you want to write to the write handle. Software Transactional memory might be a good option, but I am not sure, I probably have to try it out. If I had to give an answer to the question directly it would be performance, or rather lack of proof than the more structured approaches perform as well as the threaded/shared-memory approach.

For any given layer that makes conflict under concurrency possible, there's a suitable way to synchronize for access control. Inter-process, inter-thread, and inter-fiber concurrency all need mechanisms that accurately follow rules advertised by an interface. It's simpler in user space, so fibers are easy. If you're going to roll your own process and thread mechanisms, you have harder ones to define and implement. I'd prefer using an existing api though. For example, I only plan to code to a posix thread interface, though one abstracted through a vtable of function pointers in an env.

What do you want to hear about a vfs (virtual file system) as it pertains to hosting single-app-daemon-process collections of green processes and green threads?

Do posts about system effects on PL design and runtime have a chilling effect on all other LtU discussion? (Why would a few messages about one subject undermine desire to talk about other things?) Is getting your hands dirty a sign of lower class breeding? Or is it that only math is cool, and anything that smells like operations research is vulgar? This comes from curiosity rather than intent to challenge (a desire to draw out rather than suppress). My best guess is that realistic design plans sound complex, even with a focus on simplicity, and this depresses a person who hopes thinking about exactly one thing will be sufficient. Does undesirable realism intrude more on setting goals, or on safe abstract world views? Of the two I prefer to upset any assumption something can be perfect, which is silly, but easy to believe by avoiding practical evidence.

Right now I'm going over standard tools for portable async i/o, like libevent and libev, and everything has problems, caused by model assumptions about memory management and control flow interface like callback organization. Of the two libevent is worse; libev was designed specifically to address libevent's imposed model effects, but it still presents an event loop design and abstracts memory use no further than allowing plugins to replace malloc, realloc, and free, etc. And standard system types like descriptors are not abstracted (no one will ever need more than an integer to identify a resource). At the very least, I want nearly every native type upgraded to a larger sized struct that adds a namespace and a generation number as a weak capability to catch lifetime and cross-domain mistakes with IDs. A 32-bit file descriptor becomes 64-bit triple (fd, ns, gen) where gen is assigned at fd creation time, and that layer knows the gen associated with each fd, so it can be stringently enforced (no access without the correct gen). There also needs to be a way to clean up and release a resource belonging to a green process that goes away, so things like file descriptors cannot leak in long running apps where processes get killed.

Apparently on Windows one must use iocp (i/o completion ports) to scale anywhere near as well as posix alternatives, but they have the odd character of reporting only accomplished tasks (your read or write was done) instead of saying a non-blocking operation can now safely occur. That is, iocp usage is async but blocking; while async is good, non-blocking is better. This likely means entry points for i/o in an abstract environment interface must be able handle both "i/o can occur" and "i/o is done" (before and after i/o) in a common way, which might be an abstract valve interface for streams or datagrams. The after-io style iocp can be tested using before-io OS api by using a shim, but the reverse is not true, as folks have noted. That might be why libevent feels free to impose a specific buffering interface, which is implied by after-io style associated with iocp. That would force an extra copy for all i/o when the intended destination is immutable refcounted data structure for zero-copy streaming effects. Edit: no, said that wrong. Async means non-blocking, so the problem is that iocp api is early-resource-pinning, with fixed sized capacity. So buffer space pins early, and you can't dynamically change the size when ready without risk of blocking.

A programming language can show an OS-neutral interface for efficient async (and maybe non-blocking) i/o, provided a sufficiently hands-off general api is defined. Maybe most PL i/o designs assume an existing OS interface is wrapped to hide sharp edges, often aiming for a high level when an assumption low level performance won't be needed.

Topic change: queueing need not imply excessive buffering. There's an idea called "credit-based flow control" whose purpose is to effectively limit queue buffering sizes, by contracting ahead of time instead of assuming everything will be fine. Note how often control is overloaded to mean different things. Word order matters too. A control flow like a thread or fiber is a line of control that flows, while flow control is data flow that needs control. In both cases the first noun is primary and the second noun after modifies. Controlling flow with credit is basically a pessimistic strategy for bounded buffers (assume it won't work until reserved space is signalled), compared to blocking when buffers become full, which is a more optimistic strategy (assume it will work and block-or-park when a limit is hit). In both cases, green or OS condition variables can be used; for fibers, both strategies involve parking until a green condition variable signals, but one approach uses more buffer space than another. Complexity comes from using a window with credit systems, to avoid stalling a producer just to get permission to go; latency to clear queues can be smoothed by window size and credit extended.

Meant as a reply to above post: Would a good starting point be a new cross platform async IO wrapper library? Is satisfies the Unix idea of doing one single thing well, and is likely to get to the point of being useful quicker. You can then build your further work on that once the API is stabilised.

When I'm making prototype or throw-away code, I usually regard Windows as irrelevant. It's insufficiently documented, development tools are not installed by default, and most of its I/O stuff is, as you've been noticing, obtuse. It's not worth my time when I'm just trying to get something to work. And it seems like most new stuff requires asynchronous I/O, which is exactly what it's worst at.

That said, I/O and system interaction in general seems to be way harder than it needs to be in virtually all computer systems, and doing it in a semantics-neutral building-block compatible way is especially hard in third-party libraries for those systems. It's hard to even check for anything's existence, for example, unless compiled in the presence of an assumption that everything required to support its existence is already available. In too many cases you have rather harsh options. You can attempt to use it and crash if it's not available, or not attempt to use it and never learn whether it's available. Or, you just can't build the library at all unless everything that would be necessary for it to become available is already in place.

When I'm at the bottom level of a project -- putting things in place that will become the building blocks for other things -- I want as close to neutral semantics as I can get, and most libraries don't provide it. As Rys says, I don't want anything that interferes with prototype structure. Most libraries of these things require jumping through additional hoops to support conveniences that the prototype structure will not be taking advantage of. That would be okay except that they almost universally follow the use-it-or-break problem I outlined above. They either provide no way to opt out of those conveniences which would release me from the requirement to still have them available, or provide no way to opt out of them that doesn't require me to still jump through those hoops and have available all the infrastructure that they'd need.

It's sort of like driving a Jaguar - the car can be a marvel of engineering, but if the airconditioner breaks, you'll wind up vapor locked at the side of the road, because that damn airconditioner, whether you want to aircondition the interior or not, is necessary to the function of its engine cooling system!

HN topic 84% of a single-threaded 1KB write in Redis is spent in the kernel has a number of interesting comments about user space scheduling as performance optimization.