Þ   briarpig  » archive  » events

introduction ¶

     See 11 November 2007 for short intro to material on events on this page, providing just a little motivatin context. (See also aelig and tech/callstacks for newer async event material related to this archive page.)

purpose ¶

     Lately (in 2007) I've been working on async event systems both in day job work and home programming language designs. I often have conversations with folks who have no idea I've been here before. So this answers page the following questions:

• Do you know Matt Welsh's work on SEDA?
• Like event driven programming languages?
• Considered event vs thread issues before?

warning ¶

     Perhaps none of this is worth reading. Once you already know how you want to process events, all this must be disorganized distraction. But if you're looking for more random stimulous, this couldn't hurt.

     (This blog entry shows the same old image cited in other places about Mithril events.)

async ¶

     The image below is a reduced version of an old Mithril figure. The original figure appears on the Mithril event model page. Showing transport transparency is a main intent of the image. Local and remote messages are sent in the same basic ways. This allows local simulation of complex distributed systems.

     Note the format of events is not represented in this diagram. The format doesn't really matter, and could easily be XML. (But I expect both internal binary formats and remote XML.) Translation to and from XML is another leg in the transport. As long as conversions are invertible, anyone can play here.

thread curse ¶

     ... Yes, higher level synchronization of fiber activity is also needed. In Mithril this will be handled mainly with async event passing. Fiber context switches will be wired into async event handling. Actual event delivery can be effected atomically by primitives. This shows how cooperative threading can make simpler kernels.

     The first reference Biscuit implementation will be unthreaded. So none of this discussion is very relevant to Biscuit designs. Except a single-threaded Biscuit will also use atomic primitives. The later reworking into Mithril stackless style is for the fibers. What Biscuit does will remain, but how it happens will change.

     (The following material dates from 1998 or 1999 in newsgroup netscape.public.mozilla.netlib, but I can no longer find any sign of it in Google's newsgroup database, which means Google's newsgroup database is 1) corrupt, or 2) censored. This copy comes from an archived treedragon snapshot.)

protocol handlers ¶

     [I wrote the material below at the end of October, obviously, and I want to repost it here in case it helps give ideas related to the pluggable protocol handlers being designed, or related to Brendan Eich's wish for generic thread switchers for MIME-type converters. Sorry I'm being lazy and not updating this content to address those issues precisely; but I want to later if time permits.]

     topic: send/receive event queues to promote threading in data flows.

     (Sorry for this spam to client eng, but now is a good time for such a spam on any topic affecting general architecture plans for future products, when one wants to find out who has answers or suggestions. I bcc'd clienteng to reduce echo spam, so please email me directly if you have anything to say about this material. If you have no real interest in threading, synchronization mechanisms, or improving the architecture of future inter-component communication, then please don't even bother reading this message.)

     First I will explain what this is all about, and then I'll give more specific details about intended product applications. The current status of this inquiry is blue sky assessment that will very rapidly devolve to practical short term plans to do the most expedient thing. Some folks might send only a link to a local web page accompanied by only a word or two of comment; but other folks might want to have a conversation or a meeting (or two, no more please :-) for discussion.

     But more is going to be needed than an injuction to "use class X in NSPR because this already exists", because that is insufficient since to date we are already not using such pre-existing mechanisms.

threading and data flow ¶

     Our current browser+mail/news product is not very thread safe, though we wish it were, and has some pretty complex control mechanisms to effect async data flow patterns in Netlib which must be used in the context of some amount of real threading that is awkward to control.

     We also plan to separate the browser and mail/news portions more while maintaining cooperation and integration between these parts. It would be nice to make the architecture suck less, while rationalizing data flows between the parts, while staging other potential improvements in future threading architecture by loosening unnecessary overt coupling.

     Trying to make the product thread safe in a single go would be a silly goal to attempt. But it is much more feasible to consider using styles of coding that are thread neutral, in the sense that they could be made thread safe in the future without change, while having an appearance of better organization in the short term that makes interfaces rational.

     So I am looking into the possibility of using event queues with basic send/receive semantics (look in an undergraduate operating systems text under synchronization primitives near semaphores and monitors) in order to exchange messages between objects without sharing memory structures (other than the potentially thread safe event queue) for data flows.

     Because one avoids sharing access to memory among threads, one only has to guard against race conditions at the points where threads exchange messages with each other through event queues, so a fairly simple queue structure guarded by a monitor or some other synchronization primitive is all one needs to make basic thread safe data flow channels. (The abstract interface can hide any complex and/or platform specific things that might be required in order to make things work between processes.)

runtime agnostic ¶

     These notions might remind folks of one or another feature provided by specific microkernels and/or runtimes implemented here or elsewhere. I don't really care how the implementation is effected, as long as the interface for event queues is available in a platform neutal way that can be applied with only an understanding of event queues. No one should need to go study a specific system to use these interfaces.

incremental staging ¶

     Using event queues for data flows does not commit to using threads in any particular engineering schedule, while adding such usage makes the future use of threads more feasible, so any amount of event queue usage can be declared victory as soon as one runs out of development time. This is the only prudent scenario in which to consider such changes.

basic semantics and usage patterns ¶

     An event queue is like mailbox with a specific owner that is permitted to pull events from the queue. But anyone can send events to a queue, which does conventional store-and-forward memory management for all events received and stored in the queue. Most semantics of mailboxes also apply to event queues. To broadcast notification to many parties interested in an event, one can send it to an event queue that resends to "mailing list" of interested event queues.

     Event queues should be identified with an abstract id that acts like an integer of 32 bits or 64 bits (or more), because a simple memory address is not abstract enough. Senders only need to know where to send an event, addressed to an event queue with an appropriate id, by knowing the interface to some context that intends to deliver events.

     At minium, an event needs to be a blob of untyped data that presumably encodes the message content in some way. Some metainformation outside the blob is nice but not required to make binding of handlers more convenient. The content should not contain address pointers, or else one has simply cloaked the previous thread-safety issues in a different guise. If the sender needs a response, then they should put the id for a "return address" event queue in the event itself or it's metainfo.

control flow in same-thread event queue usage ¶

     Control flow for event queues works very well when queue owners are in different threads, because an owner can block until an event appears. But when the sender and receiver of an event are running in the same thread, how does the 'receiver' ever get prompted to look for events? For same-thread scenarios, some kind of postmaster manager is required to see who has received events, and to poke receivers in a timely fashion. The coding of a postmaster is a lot like other kinds of time slicing mechanisms, of course. But this particular brand of slicing is mostly transparent to the event queue users who see behavior that looks more like rational send/receive data flows. The interfaces of such a system that uses a postmaster should be replaceable with one that is more thread-based; we can incrementally decide how many threads to use later, and keep the postmaster for all same-thread queue users.

     Note that I don't consider this kind of thing hard engineering, because more than ten years ago I wrote my first simulation system based on sending messages with time delays to event queues, using a centralized dispatcher to wake up threads receiving events at the soonest moment in logical time in which an event could arrive. (Of course the result had a re-invention of Lamport style clock synchronization algoritms.)

specific product applications ¶

     I'm going to look at data flows in mail/news to see whether they can be rationalized using event queues, and to see whether such interfaces will simplify communication with other components, including both the browser and third party applications. No commitment to go in such a direction is implied by this, but the idea seems promising.

     If such event queue interfaces would also make raptor and browser communications more rational, then that's cool and it's up to folks in those areas to consider such application. It would be fun and perhaps very useful to have a discussion with folks about this kind of thing. But the intention is to get results and avoid wasting time dreaming.

     [name], peon loose cannon with a dash of subordinate flavoring; Values have meaning only against the context of a set of relationships.

     (The following was written on 12jun2002, and quoted the 27oct1998 material just above, in the preceding section. The substance of my complaint was every Netscape engineer I met discussed related topics only in terms of "thread architecture" and which threads sent messages to which other threads -- without ever considering thread agnostic event queues.)

event queues ¶

     The [preceding] is from google groups: last-name+threads+netscape. I wrote it in 1998 at Netscape, about topics I considered obvious. I first worked on such related queueing concepts ten years earlier [in 1988]. It was ignored. (Netscape folks were less bright than I'd thought.) I've added some highlighting to emphasize more interesting parts.

     You might ask me where this suggestion of mine failed to get traction. The number one design factor in Mozilla then was to accomodate RDF. The Gecko engine was done -- everything else was to to be RDF-ized. So no one gave a shit about architecture issues related to performance. All our non-RDF square pegs had to be shoved into RDF round holes.

     I was invited to meetings to hear folks praise Windows event pumps. During which youngsters prattled about perferred socket usage and i/o. My idea was as weird as NASA proposing manned missions to Mars. So I merely resolved to add such features to my own future software. The basic value in my suggestion can be boiled down to the following.

     Strictly speaking, very little software needs to know about any threads. Our code need only pay attention to event queues. Threads are optional. It means threads and event queues can be decoupled from each other. Lack of such coupling enables flexible options in architecture choice. As a result, a system is simpler and has fewer maintenance demands.

ship event ¶

     A ship is a quantum one-way message in Mithril. The arrival of a ship consitutes an event notification for the receiver, containing a message from the sender, along with some metainfo explaining the message nature, plus a return address for a reply if one is needed. (Many return addresses might be present, factored by reply purpose.) Message content is optional, since metainfo alone might convey enough information. A single one-way ship is an async event. But a pair of ships makes a synchronous message exchange, if a second replies to a first. For example, remote procedure calls under Mithril are implemented using a pair of ships in such a send/reply pattern. Any fiber in any city can send a ship, but we might constrain receivers from a dock to those showing access rights.

dock address ¶

      A ship arrives only at a dock inside Mithril. A dock is basically an event queue which is uniquely named inside a city. Inside a Mithril world, each dock is uniquely identified by a pair <C,D> where C is city name token integer, and D is a dock name token integer. Each world has a hash table of cities keyed by C, and each city has a hash table of docks keyed by D. (Or maybe each world has a dock table keyed by <C,D>.) So World event dispatching is basically one or two hash table lookups to find a destination dock for a ship. Interworld shipping uses a triple <W,C,D> so the host can map world name token integer W to whatever that means to a host. Token integers optimize metainfo form and use.

fiber blocking ¶

     If a fiber needs another ship from a dock before more progress can be made, a fiber can choose to block until one arrives, modulo timeout control according to fiber specification. We might also let a fiber block on many docks in a city at once. (Note one cannot receive ships from a dock in another city unless they are really forwarded to one's own city.) The combination of message shipping and fiber blocking is how Mithril plans to support concurrency in Mithril apps. So this means the Mithril event system is tightly coupled with fiber scheduling for time cycles. When a fiber is blocked waiting for a ship, it only gets more time when a ship arrives or a timeout occurs. All inter-fiber sync primitives (for things like mutex) are implemented as if ship sending and receiving is involved, though this might only be simulated.

     The following figure illustrates Mithril local and remote event dispatching. Mithril encodes each event as a ship, with metainfo headers as ship papers, and message body as ship cargo. Even though a city can hold many docks and fibers, for simplicity we show only one each per city below. So we use figure names A, B, and C to refer to city, dock, or fiber as convenient.

event figure ¶

     The figure shows three ships sent, with two local events between A and B in a send/reply handshake, and a single remote one-way event from B to C. Suppose A goes first by sending a ship to dock B. After fiber B receives the ship from dock B, it replies to the return address on the ship by sending another ship to dock A. Fiber A might be blocked waiting for a reply, so the ship arriving in dock A will cause the scheduler to wake fiber A to receive the ship event. The same thing would have happened if fibers A and B where in the same city, instead of different cities. Although the sea object makes a pretense of delivering ships, in local cases ships arrive at docks near instantly.

     The remote case in sending a ship from B to C is more complex, and shows a typical path involved during interprocess event delivery, which might also cross a gulf between hosts on separate machines, perhaps using a TCP or UDP connection. Note Ag doesn't care about the transport, which is handled the process environment hosting the Mithril world. The main idea is that the sea holds outbound ships which the host process later sends to a destination process. The host must consult the Ag world for string versions of any values that need remote marshalling. The receiving process reverses the whole business, handing inbound events to the world to encode as sea buffered ships until the VM gets more cycles (by spinning the world on its axis, naturally).

vm context ¶

     A virtual machine in each world is shown for sake of context, because any fiber receiving a ship must be running on a virtual machine. So the presence of a VM is necessary, and directly involved when a scheduler wakes a blocked fiber, but we don't show this level of detail.

      I've been struggling over ship event memory management issues. Why the conflict? I want them to come and go very fast, but avoid copying. So ship is not a node class to avoid refcounting overhead. But it should possible to alias rather than copy any ship papers and cargo. Otherwise there would be copying overhead to extract data from ship events. I think I now have a design with sufficiently lazy reference techniques. Ship subclasses link and yarn, and have yarn member. The link handles ownership by exactly one collection (e.g. dock). The first yarn contains a variable (possibly empty) ship cargo blob. The yarn member holds an open-ended set of variable paper headers. Both yarns might transfer ownership to refcounted rope node instances. Ship would need to ref any such ropes that assume yarn ownership. But ship receivers could look into papers and cargo without aliasing. Refcounting overhead only happens when long term aliasing is needed.

     (In my 2000 designs for Mithril, I used the term "dock" as a synonym for micro-port, to mean an event queue receiving messages for a microthread or lightweight process.)

dock events ¶

     I don't really need a special ear subclass to send ship events to docks. Instead, crier can collect event queue IDs as well as ear's. Then a crier will iterate over both, sending events and calling methods. So listeners can pick their poison and get either callbacks or events. Asynchronous events seem much preferrable to synchronous C++ methods.

     (The mention of async events here was in the middle of a larger discussion, so I quoted a little more of the surrounding context.)

generational gc ¶

     Then we need to consider the city design effect on GGC. In fact, cities were partly motivated to simulate GGC value. Each Mithril city amounts to a closed universe generation. A city is a place where objects live and reference others. Any objects in other cities cannot be referenced directly.

gc isolation ¶

     So each city instance can be garbage collected in isolation. This effectively gives us incremental garbage collection. The latency for any given gc is only the cost of one city. Also, app design can segregate cities by object age profile. A city churning objects cannot force more gc in other cities.

event passing ¶

     Objects in different cities interop by async event passing. Connections are indirect only through docking addresses. A city is a bit like a process with it's own address space. And a dock is a bit like a port for socket communications. But many cities gather under one Mithril world process.

gc granularity ¶

     The city design also captures another advantage of GGC. This is reducing gc size granularity to save wasted space. Typically one wastes as much space as vacated during a gc. When all memory is collected together, this wastes half. With many generations or cities, less memory is wasted.

     (This is from a longer email discussion with Andrew Shebanow. The last paragraph mentions events, and parts before look interesting enough to include.)

     ... In order to make it very easy for C++ to call Lisp that calls C++ etc ad infinitum, one has to represent the thread execution state as a form of continuation that can be represented and manipulated equally well in both C++ and Lisp. Basically this requires a runtime model that would be nearly incomprehensible to a C++ coder, or at best merely distasteful since it would seem very bad style.

     And it requires that you think really twisty in order to initially dream up, so it took me a long time to formulate the intent, which eventually became the runtime design for my (still vaporware) Mithril implementation that's pending in my queue. (Actually I'm creeping up on it incrementally with Biscuit.)

     But the result is a runtime representation of continuations that is very cool, in the sense you can mix and match methods written in any kind of style at all, from native code in C++ or some other language (Lisp or Smalltalk), to virtual machines and abstract syntax tree interpreters in various flavors.

     Basically it's a radical just-in-time architecture, where code lazily (if ever) changes from one representation to another. It let's you write and test (say) a new virtual machine and test it with code running an entirely different virtual machine. And you can similarly experiment directly with native code generation.

     (Thus my maniacal laughter as I dry-wash my hands repeatedly. What, you can't hear me? Turn up the sound volume on your machine.)

     Other parts of the Mithril runtime design are intended to further maximize the good effects of non-interference when pursued. Here we start with non-interference of compilation and interpretation, and non-interference of source language. Then we add more module and namespace control, so different compilers and interpreters can be used at the same time. And then we add separate "cities" (disjoint gc address spaces), so stable code in one city can debug new systems code in another. I can have a debugger running in the same process as the city being debugged, as long as it runs in another city. (Or I can put it on another machine entirely since I'll have async events.)

     (This comes from a conversation with Wes Felter in October 2001 about BeOS, threads, and events.)

immutable ¶

     Absence of sharing is a good approach to efficient threading. This creates more easily controlled firewalls between actions. Even better, it makes it feasible to distribute code participants. A shared state model discriminates against remote task agents. This might encourage coders to give poor distribution support.

     If the state is huge, then sending it around is not very efficient. In that case, it's good to find new ways to send much less data. That goal might even encourage a less apparent clever design. Low transmission and low sharing means fewer dependencies. It seems need to know also applies in code design contexts.

(Wes Felter adds a few more comments in later email:) Another thought: I've seen a lot of people criticizing BeOS (often citing Ousterhout's "threads are hard"), but the empirical fact is that even naive BeOS apps tend to be more responsive than almost all Mac or X11 apps. I don't know if the difference is in the threading, but obviously BeOS is doing something right and the others are doing something wrong.

event passing ¶

     If BeOS has fine-grained event passing models, that might be it. This is what I want to use in Mithril for most communication. I'll deliver async events to very lightweight message queues. This uncouples complex logic, and can be extremely efficient. The same technique works even when you use only one thread.

context switches ¶

     Sending messages need not imply context switches. That's key. Context switching is just overhead, and more is usually worse. Message queues can be made thread agnostic (i.e. independent). Different threads might or might not occur at queue boundaries. This let's you design data flow without designing to the threads.

transparency ¶

     Maybe folks avoid queue styles to reduce memory management. Memory can be tedious unless a system provides direct support. Mithril will provide almost completely transparent event usage. So sending and receiving messages will have little code cost. And it will be cheap when it happens outside the GC footprint.

inter-city events ¶

     Keep in mind I haven't done any of this. Mithril's still vaporware. Differences between theory and reality are smaller for me than you. I'm spoiled by having my technical expectations often be correct. I recently mentioned Mithril cities, and Peter Drayton commented. I didn't recognize AppDomain parallels. (First I've heard of that.)

     I never read about Microsoft technologies. I have my own work. I haven't noticed their old designs being particularly clever before. So there's not much reason to go looking for that. I'm practical. Also, I'm totally indifferent toward demands to recognize genius. That's not a rare commodity. It's not unusually rich at Microsoft.

     Okay, so what's a Mithril city? It's a scope organizational device. It's a spatial metaphor that intends to recall normal human cities. A city is where stuff happens, and scopes many business activities. There's a bigger spatial metaphor called a world, containing cities. The distinction is largely a separation of physical and logical roles.

     Physically, the world is where all storage is managed and shared. So a city physically gets resources from the world for its own use. But logically, each city sees it can only affect space inside itself. Other cities, and agents therein, can only be reached by event mail. One city can only affect another explicitly by messaging interfaces.

     Behind the scenes, the world handles delivery of inter-city events. The sub-part of the world that handles shipping is called the sea. Where are events in transit? They're in a ship at sea. It's an image. However, typically events arrive instantly with no context switch. Of course, events often can't be received without a context switch.

     Unless you send messages to yourself, which is allowed of course. Before I go on, note none of this has anything to do with language. All this design applies to the system that would run Mithril code. Every language must have a model for expressing global resources. This world and city model interacts with a Mithril module system.

atomic events ¶

     Here's an aside about avoiding redundant costs of thread locking. Mithril tries to save cycles by avoiding old unnecessary features. This was the original motivation for the topic of process sandboxes. Mithril will use it's own internal homebrew cooperative threading. It's pre-emptive for code running inside, but at nice boundaries.

     Primitive operations, like event delivery, are atomic without locks. Mithril has big critical sections for these which are still utterly safe. Thus horrendous costs of low level threading are mostly avoided. And locking bugs can't happen in contexts where they don't exist. Of course high level code still needs synchronization primitives.

     But they'll be based on event passing, which is atomic and speedy. I always liked send and receive mechanisms more than semaphores. Any of the standard mechanisms can be used to model the others. For "real" system threads, I plan to use multiple world instances. This described at length in this discussion with Luther Huffman.

networking ¶

     I know some about networking, but not nearly enough about hardware. I follow and use the TCP/IP details at the high end of network stacks. But physical layer matters and configuration arcana still mystify me. Reading about high level ethernet history is not nearly sufficient intro. I tend to assume there's no overall rationale for hardware layer design.

     I have a hard time remembering fine detail without theory as context. Writing server code only requires grasping the software side of stacks. (Of course, that's the whole idea behind layers. Abstraction is good.) But it strikes me as strange that home networking seems so hard to do. Or maybe it's just my laziness in not reading widely about the art yet.

     I'd rather make software even higher level than delve into hardware. I don't even want to bother with socket level details for event coding. It seems that should be implementation detail for my high level APIs. But maybe the semantics are so quirky they bleed through the layers. Nah, it should still be abstracted. Async APIs are a good way to cope.

picoservers ¶

     It would also be fun to work on some web microservers in fine detail. In the future I'd like to be able to crank out ever smaller picoservers. You can always make 'em bigger by piling on more crap and features. But it would be useful to identify the minimal skeletons for additions. This would lower barriers to entry for any new tiny server you want.

     Perhaps I can take existing picoservers and make them perform better. I have specific requirements for memory usage and zero copy effects. My idea of "minimal overhead" is typically less than most folks' idea. I also want to provide a standard pico async event passing framework. That way folks can write servers as message passing, not connections.

     When I write libraries in the future, I'd also like a tiny server protocol. For example, you could choose embedded IronDoc or server IronDoc. So it would be trivial to write a tiny address book server, for example. I'd like server-izing my code libraries to be a matter of turning a crank. And I'd like to do it without swallowing a huge morass of W3C junk.

event queuing ¶

     I'll try to write a tiny blitz response to Jeff Darcy about event queuing. So much for spending only a chintzy fifteen minutes. It deserves much more.

Jeff Darcy: (01Jul2002) [name] has written some more about multithreading vs. event queuing. Unfortunately, about 70% of what he writes is really about how "microthreads" work in an interpreted virtual machine. That's a fine topic but one I consider orthogonal to that of which programming model to use for network applications, so I'll just comment on the other 30%.

     Yes, I was trying to say my take on event queues was strongly influenced by my intention to inextricably entwine event queues and microthreading in Mithril, so that talking about event queues could not make sense without the associated microthreading. I won't have a lot to say about event queues grafted on to hostile systems. I want them to be first class in a language.

     In short, my focus is not network applications. Instead, I'm interested in a language approach which happens to be equally good at network applications as other kinds of applications. Maybe this is a naive idea, given how non-expert I am at networks. But I have some faith in the idea of using language as a simplification device via abstraction. This is a Paul Graham type of notion.

     But I want to talk about event queue techniques in network applications anyway, without dwelling too much on my vaporware. I just thought it would help prevent future disconnects if I outlined by unusual motivating context clearly at least one time first. Folks will invariably make statements about how events "must" be handled which will not be true in a runtime friendlier to them.

Darcy: 1. Too many back-to-back queue/dequeue operations. Many queue-based systems use an interface where a request is always put on the recipient's queue, then the recipient's dispatch routine is called...and 99% of the time the very first thing it does is take that same request right back off the queue.

     I'll come back to this optimization topic later. I need a few paragraphs to make enough interesting points.

Darcy: 2 Complex queuing. Too many event-queuing systems have interfaces that just sort of grow without bound. First they turn a simple queue into a multi-level priority queue.

     I hope not to make my queue interfaces too hairy. For example, I had not planned to give events priority. (In my piece that discussed microthreads too much, I planned to have thread priority, but maybe only two distinct levels. An event receiver can get all events present at one time, and sort out event priority themselves, maybe with standard tools.)

     I prefer the least complex arrangements I can get when it will be necessary to mentally construct proofs of correctness when using event-based behavior. Everything that makes an API soft and fuzzy merely interferes with hard logic about boundaries.

Darcy: I hope my comments can be accepted in the intended spirit of comparing notes and thinking things through collaboratively to arrive at an optimal design. I also hope others will be encouraged to jump in and share their own experience with these sorts of systems.

     Hey folks, please take Jeff Darcy up on this fine sentiment, and help us discuss the interesting parts of such design issues. (I see a lot more discussion on this has been appearing lately. Just yesterday I noticed this piece at Lambda the Ultimate about Declarative Event-Oriented Programming. Note I haven't downloaded the paper -- both Word and postscript are awkward for me.)

threading vs messages ¶

     I return to Jeff Darcy's piece on Multithreading vs. Message Passing. I don't have a specific plan. Maybe I'll just work backwards (links 404).

Jeff Darcy: First, I'd like to point out that many problems - e.g. race conditions, deadlock/livelock, are held in common between the two approaches, even though they might occur in superficially different ways. Other problems are clearly tradeoffs with no "right" answer.

     Problems tend to come back since sweeping them under different rugs won't make them go away. So I'd expect the problems in both threading and message passing to stay but appear differently as the factoring rearranges the issues.

     With high level messaging (using events or whatever we want to call them) as the main synchronization mechanism, we can get a couple nice effects. Done outside a fragile kernel space, it should be easier to get excellent logging that shows the wait-for graph clearly under deadlock, and otherwise merely reports an excellent view of traffic. The other nice effect is one of simpler reasoning.

     For some reason, I imagine a mental view of events passing through queues gives an image that's easier to manipulate when reasoning about emergent outcomes, since one can see results as the effect of event locations and the pattern used by microthreads to dequeue them. The more implicit behavior of traditional pthreads and synchronization mechanisms is harder to put under the light of scrutiny.

Darcy: For example, many multithreaded systems exhibit poor performance due to excessive context switching, and message-passing advocates point out that their systems don't have that problem.

     I think of threading performance problems as having several different parts to the total effect. One cause of excessive context switching is simple mutual exclusion to ensure atomic changes over nearly all shared state changes, from single pointers to complex collections. Event passing can get large atomic critical sections without explicit locking that might cause context switches.

     But that only happens in the context of the vaporware I plan, where primitives execute atomically without any need for an explicit lock. The presence of this mutual exclusion result does not provide extra opportunity to tempt a scheduler to swap contexts. No synchronization mechanism is needed in such virtual machine primitives. So no events need to be send to lock the state changed.

     Reference counting in particular will have less overhead. Of course, changes at higher levels that bridge multiple primitives in the higher level language will need to use explicit locking mechanisms. And these might provoke context switches. So message passing systems do indeed have a context switching cost, even though they are the smaller ones of microthread swaps.

     But even more than context switching cost, I worry about the scaling problem with heavyweight threads. When one ties a thread to each operation like a user request, one reaches a spot beyond which the practical limit on thread count throttles the ability to handle more requests -- at least to keep them moving in incremental progress. In this case, threads are anti-multiplexing.

Darcy: * The excessive context switches are an implementation artifact, avoidable while retaining a multithreaded paradigm (I've done it on more than one occasion). They're not an inherent problem with multithreading.

     The approach I prefer is sharing less space between threads less frequently, so the mutex locking for coordination happens a couple of orders of magnitude less frequently. Typically this amounts to bulk allocation of shared resources that subsequently get suballocated by a single thread that has total control.

     But even though this ameliorates the performance impact of lock contention by threads when the thread limit has not yet been reached, it still doesn't fix the problem that one can't always easily increase the number of threads in use by a factor of ten without a severe penalty.

Darcy: * Message passing systems are only immune to the context-switch problem if they run everything in a single thread, which is to say that they've traded away multiprocessor scalability for simplicity and single-thread performance. Message passing systems that use multiple threads - yes, even staged systems like SEDA - are just as prone to excessive context switches as any multithreaded program ever was.

     But a hybrid system can handle the majority of small granularity work in one thread, while still using numerous threads overall at a large granularity. This applies the traditional 80/20 school of reasoning to reduce the most frequently occuring costs while retaining full generality. As long as multiple threads are used, the benefits of multiprocessor scalability are retained.

Darcy: In short, I consider that particular form of advocacy, most often engaged in by the message-passing folks, intellectually dishonest. If a problem is not inherently worse, or less readily solvable, in one system than the other, then it is of no value in differentiating between them.

     I'd tend to put myself more on the message passing side of the fence. But I focus on downplaying thread usage as much as possible, as opposed to actually removing thread usage, since actually removing threads has a drastic diminishing-returns cost. It usually doesn't pay to eliminate one pure source of improved efficiency. Anyway, both systems should do what they do best.

Darcy: Lastly, my current thoughts. I'm dealing with these very issues in my current project, and the result has been (surprise!) a hybrid between the two approaches.

     Hybrids are often a good idea. I imagine event passing folks have exaggerated their position only because the threading centric camp has long ruled the common consensus of how things should be done. Let me exaggerate the threading position: "Just use more threads! Threads are gnarly. Anything else is unnecessary complexity."

     Unnecessary is a relative term, like most of them. In the space/time/complexity tradeoffs that engineers must make, sometimes a modest amount of complexity with drastically reduce either space or time without increasing the other. Hybridization is a form of complexity, but not a nasty one, since it's typically easily explained as the melding of two techniques.

Darcy: I guess the lesson here is: don't be an extremist. A hybrid approach can solve the worst problems associated with either "pure" approach, but allowing either one to become dogma can be deadly to your real-world effectiveness as a programmer.

     Hey, you stole my line. I see event passing as the underdog in this particular context, because threads are basically well represented already in the current industry practice. Heck, we even have (almost) portable standard interfaces in pthreads. Events and message passing have a weaker degree of development, so they get short shrift. Extremism often favors the incumbent technology.

     I haven't heard much rhetoric from event passing supporters myself. So I'm not sure what they are saying. But I'd guess they don't represent the thread perspective because it's well represented.

hypercard ¶

     Dave Winer talked about Hypercard and the web a year ago. He said the web is a descendent of Hypercard. That sounds fairly close. I'd like to see a descendent of Hypercard permit easy end-user scripting of the web, where a user can hope to learn enough without weeks or months of studying a language.

     Ah, I was just going to cite an email from Bill Seitz on this, but it mostly consisted of those two links above. So let's see, what should I add to this? Okay, I have a particular type of end-user scripting I'd like to see happen. I want to see servers as agent plugins.

     That is, a user should be able to write a script for some agent that handles interesting events or messages, where the agent runs on some machine somewhere -- maybe on a box sitting under the desk at home. Then when roaming around, the user can query the agent with another simple script. A remote agent here is basically a server.

     Hypercard made it possible for users to build useful apps with little code training. But Hypercard stacks tended to be isolated and standalone. I'd like to see something similar which allows a non-developer user roll their own internet apps without this requiring rocket science or network wizardry. The building blocks need not be complex.

event systems ¶

     Note this email has an interesting part snipped out at Kevin's request. I can't name Doctor X, but I'll say hi in case he reads this. (Hi Doctor X!)

Kevin Altis (24Nov2002): Could you elaborate more on the event system requirements you discuss at: newNov02.htm#24nov02-pythoncard-limitations I don't really understand what you're getting at. Neither wxPython or PythonCard prevent you from creating your own events. Also, it is important to be clear about whether you're talking about events in normal user driven system event types of things like mouse clicks and menu selections or "events" from things that might happen in other threads, but that you want to interact with the GUI in some way.

     I could be more clear. (And if I'd actually written a spec about this as I planned, it would be even more clear.) I'll make up a new word to distinguish what I mean from "event". Let's call a new type of message by the name "ynote" (pronounced "why note"). The leading "y" is just a prefix for a ygg namespace.

     A ynote is a notification which can be serialized as an RFC822 message, but is typically in some more efficient binary form in memory. This pure forward-looking hot air, and not a description of exsting code. If you like, consider a ynote to be a one-way async RPC message, and roughly similar to a SOAP message.

     With ynote messages, you can write async message passing systems which encode events as ynote instances (either the efficient in-memory kind, or the text-based RFC822 serialized kind). As it happens, both HTTP requests and responses are ynote instances.

     A system can use ynote internally to represent events instead of native system events. A main event loop would therefore turn every system event received into a ynote instance and stuff this into a thread-safe ynote queue which is the input hopper to the real event-processing system, which is actually a ynote processing system.

     (Actually, to avoid excessive thread context switching, it's best to have one thread process a ynote as long as possible after conversion from a system event, but the above is the abstract model, where we get clear of native events as fast as possible and move on.)

     Earlier when I discussed events, I meant in the absract sense, which could be manifested concretely as ynote instances. The approach I describe is useful because the engine does not need to distinguish between data flow from system events and data flow from external network messaging, because in both cases the data format and handling is the same. The engine is a server, even when in single user mode.

     Look at it this way. Suppose you receive an HTTP request on port 80. You can feed it into the main event loop based on ynote instances the same way you feed system mousedown events into the same ynote hopper.

     By creating my own events, I don't mean creating my own system format events. I mean creating my own total replacement for the event handling system. So I need to drive my widgets with input based on ynote instances. A GUI toolkit based on system events alone is not very useful.

Altis: Anyway, just wanted to see what you were thinking and then I can elaborate or clarify further. Part of the reason for the PythonCard event dispatch system is to sit on top of normal wxPython events and thus have a way of synthesizing events pretty easily not generated by the system and handling listener/observer stuff without doing any extra work. The Message Watcher is a listener of the dispatcher as just one example.

     (Now I'm mostly responding to Doctor X.) The original Hypercard was closely integrated with the Mac runtime, so Hypercard could treat Mac system events as subject to change when desired, the same way I would feel free to change ynote instances. So Hypercard was not exactly limited by the Mac event format, since any limitation could be fixed in a system rev hypothetically.

     (I might not be right, though. Folks thought OpenDoc was integrated with the MacOS runtime, but it was not. We actually ran OpenDoc exactly the same way any developer would do it, without any special hooks in the system. This is one of the reasons performance would have increased after some integration. Perhaps Hypercard also had no special influence on the MacOS.)

     The ycard spec I was planning to write, which would mimic Hypercard, would describe a way of dispatching ynote instances to GUI objects, or to any other object prepared to receive such messages. It would subvert my runtime model if my widgets had to be driven by system events.

     Because ynotes would be defined specifically to ease intermachine communication about "events" over networks, it would be especially easy to write distributed network apps using a ycard infrastructure.

     In short, I don't want the event handling part of my system to be platform specific, and I don't want platform specific widget interfaces either. But that's just me, and just talking about my planned ycard spec. I don't have any strong opinions about how Chandler does it. That's not my professional bailiwick.

matt welsh ¶

     Wes Felter sent email in response to yesterday's picoserver piece. He cited my "standard pico async event passing framework" phrase. Then Wes asked, "Did I bug you about Matt Welsh's SEDA yet?" I didn't remember, so I performed a search to found several things. For example, Duncan Wilcox mentioned it on Wes's site last April.

Duncan Wilcox: Matt Welsh's SEDA is pretty impressive, though. I have only run through the papers very quickly, but it would seem that in addition to using an event driven architecture the stages of event processing are also decoupled. This is a different approach compared to flash, and the latency is measured and seems reasonable. It could also solve the problem of scaling to multiple CPUs, that a straightforward single process event driven implementation (like thttpd) can't do.

     My own Mithril work aims to end up with single threaded systems. However, I plan to take advantage of multiple processors anyway. I think using multiple instances of single-threaded systems is good. They can be serviced and fed by queues that interact with threads. I talked about this a couple years ago in email with Luther Huffman.

I once told Luther Huffman: I usually respond I'm not thinking about that; but that's only close to true. In fact, I think the only way to exploit many processors is by using async event passing, with as much overhead stripped as possible.

     However, this architecture requires a reasonable async model. Most language coding systems presume a synchronous call model. So async is only natural in a language that defines async support. The interface to the outside world depends on non-blocking i/o. Matt Welsh says the following in his April description of NBIO:

Matt Welsh: I am using NBIO as the basis for my thesis research on the staged event-driven architecture (or SEDA). While NBIO provides a low-level nonblocking I/O library for Java, SEDA is a complete architecture and runtime system for building well-conditioned Internet services. In particular, our Java-based Web server, using NBIO, outperforms both Apache and Flash, which are written in C. More information can be found at the SEDA web pages.

     I haven't looked into any of Welsh's stuff. I've no interest in Java. But I might be interested in this low level non-blocking i/o code. I'd like to position anything I do against some well known factor. I guess non-blocking i/o is standard for fast web servers lately. I'm interested in the part that routes requests into async events.

(Matt Welsh writes last March:) SEDA is an acronym for staged event-driven architecture, and decomposes a complex, event-driven application into a set of stages connected by queues. This design avoids the high overhead associated with thread-based concurrency models, and decouples event and thread scheduling from application logic. By performing admission control on each event queue, the service can be well-conditioned to load, preventing resources from being overcommitted when demand exceeds service capacity. SEDA employs dynamic control to automatically tune runtime parameters (such as the scheduling parameters of each stage), as well as to manage load, for example, by performing adaptive load shedding. Decomposing services into a set of stages also enables modularity and code reuse, as well as the development of debugging tools for complex event-driven applications.

     As source code SEDA is of no use to me in Java, except for reading. It sounds like it might be too high level for me to get practical benefit. If so, then I might pick up useful conventions in the low level NBIO. Frankly I don't expect to read this. But I might get to it eventually. However, I greatly appreciate the validation of my own preferences.

     (A lot of extra headings between paragraphs have been added, to summarize on the fly.)

vaporware ¶

     Advance warning: Mithril is vaporware. It's an unfinished language. It's best to consider Mithril a design currently, with some work done. My main reason for describing it now is to clarify async event features. Since these are uncommon in languages, a design seems more relevant. (Mere design is more forgiveable in the absence of concrete options.)

mithril terminology ¶

     All the following definitions of terminology apply to Mithril's design. (I say this now so I needn't add "Mithril" to every sentence below.) The term fiber means microthread: lighter weight than system threads. Get it? A thread is composed of fibers. A fiber is a very small thread. A fiber is a semantic feature. It doesn't appear in syntax or grammar.

runtime underneath ¶

     In this sense, neither fibers nor events are part of the basic language. Instead they are part of runtime operations, but not a separate library. They'll behave a bit like a library, but they need to be very primitive. Mithril's syntax, grammar, and execution will be very like Smalltalk's. Operating with events, fibers, and docks work like any other objects.

scheduling ¶

     But using them always implicitly drives the fiber scheduler's behavior. None of these things need to exist until Mithril has fiber scheduling. A dock means something similar to port, or channel, or mailbox. I chose the term dock to imply much higher granularity than port. A dock is something in which discrete messages arrive, like a ship.

city metaphor ¶

     The metaphor fits the model of event ships arriving in a Mithril city. This is roughly depicted in the image below. A city is a state locus. A city is roughly a carefully closed subset of a process address space. Garbage collection happens in city granularity. This implies something. Objects in a city cannot refer to objects outside a city. A city is closed.

gc roots ¶

     All the garbage collection roots in a city are inside the city. This matters. It's why a city can be garbage collected without regard for other cities. Code within a city acts just like ordinary code in any language today. If you write one-city apps, they'll be rather like simple Smalltalk apps. Message sending inside an city is synchronous just like function calls.

fiber scope ¶

     You only need one fiber in a city to do such plain vanilla programming. Every fiber lives in exactly one city. A city is each fiber's state horizon. Every fiber can reference objects by pointer in at most one city, for gc. Each city hosts some F fibers and some D docks. Docks receive events. Any fiber can block by synchronously reading an event from a dock.

non-blocking ¶

     Or a fiber can check for events without blocking. I'll have much variety. I think fibers should have many options in the way events are handled. If a dock is zero-buffered, it will behavior just like a Limbo channel. In this case, a sending fiber will block until a receiver gets an event. But it's important to note this is an optional usage choice for any fiber.

thread agnostic ¶

     Generally speaking, every city is single-threaded to avoid all lock usage. Locks need only be used at event queues at city boundaries for threads. Threads can be assigned to handle various cities to use multiple CPUs. (Or cities in a world might be single threaded with a world per thread.) The important idea is that event queueing discipline is thread agnostic.

messaging ¶

     An event is a message, much like a server request or an email message. Each event has metainformation headers and a body to contain content. Header metainfo indicates many things, like where a response should go. In fact, email message formats are a great thing to imagine for events. In this sense, a dock is very similar to a mailbox, with store and forward.

bounded resources ¶

     Yes, there's a problem with using unbounded space for events in docks. This is why dock usage must specify what the resource constraints are. Different policies for dock event capacity and handling can be enforced. So it needn't be a unbounded space usage problem unless you really want. Conditions like dock overflow can be handled by sending notifications.

timeouts as events ¶

     And the notifications will themselves be events send to other docks. Basically you do complex state machines with fibers, events, and docks. Events are asynchronous messages. You can reply to get a rendezvous. Or you can use zero-buffered docks to get rendezvous. Sure, why not. You can't block forever on a dock because timeouts deliver events.

simulation engine ¶

     The Mithril event/dock system is basically a general simulation engine. If you were modeling some hardware, an event would be like a signal. My design comes from discrete simulation stuff I did back in college. You can build up any kind of complex high level semantics you want. But you aren't screwed by bad high level choices someone else made.

sync or async ¶

     You can write your libraries using normal synchronous style coding. But you can also write them using async event dock interfaces instead. This is what you want to do for servers and for distributed computing. But you needn't go to that level of complexity unless you really want. And you could use wrappers for sockets in totally conventional code.

data driven option ¶

     But Mithril will give you an option of writing async data driven code. It might be complex, but you can react in exactly the way you want. All errors caused by absence of events received can be handled well. A user interface need never freeze while waiting for a stupid timeout. And you can write event based staged servers like Matt Welsh likes.

async servers ¶

     The other day I pointed my boss at the Matt Welsh's SEDA system. Then we talked for a while about what I intended with async events. This doesn't figure into any job plans, but we often discuss pure tech. That way we get our expectations in sync about what's really possible. He noticed Mithril's design sounded like hardware discrete simulation.

     That's when I told him it was based on college work to do just that. I'm going somewhere with this. I'm still leading up to the good part. The key concept you should attend here is a basic idea of simulation. I asked my boss, "What's the difference between real and simulation?" In this case, real referred to any async systems talking to one another.

     "None at all, of course," he replied, knowing that's what I'd intended. If all you know is based on message evidence, messages are reality. This came up in the context of my describing staged distributed apps. Mithril aims to simulate distribution within a local context using cities. In one process, fibers in two cities can communicate via events alone.

     When you have this debugged, you can separate the cities more widely. First you move them into different processes, then different machines. My boss said it was hard to simulate realistic latency in the local case. I said, no it's not. You can merely put a noisy intermediary in between. You can programmatically induce latency, or even lose events outright.

     The nice thing about event-oriented apps is that routing is so explicit. You can write routing intermediaries that explicitly fudge mappings. Obviously time latency is a main mapping that needs careful fudging. You can just test what an async system will do in a good simulation. The next section is an expansion of what I told him only very briefly.

multiplexing ¶

     Much of my work does code and data multiplexing of various kinds. I told my boss that a coupling of granularity is what chokes systems. When your system requires one-to-one relationships, this will clot. I use the word clot in the same sense as a blood clot inside a vein. A bottleneck chokes with a clot if an element cannot be multiplexed.

     For example, conventional servers associate one thread per request. When neither can be multiplexed, this represents a system bottleneck. The design of Mithril really aims to multiplex many such bottlenecks. For example, modules multiplex global namespace of other languages. Fibers multiplex threads, cities multiplex processes, etc. It goes on.

     Async events can multiplex a traditional synchronous subroutine call. Each sync method call expects one (and exactly one) function response. But it's a problem whenever zero or more than one response are better. Async systems are hard to break on first principles. They expect little. When sending doesn't expect a response, lack of response is no problem.

     If you react only to messages received, expectations can stay very low. If you infer a message is received when it appears, this is very likely so. In contrast, synchronous systems expect things that haven't happened. When an error occurs, this can stymie and fubar a synchronous system. Async systems are more complex because they must handle all the cases.

     But that's exactly why they can be much more robust than sync systems. When you write an async system with a stupid expectation, it's explicit. You can always rewrite dumb assumptions to act on positive evidence. Somehow I veered too far from my multiplexing topic, so I'll return. IronDoc is mainly about multiplexing the contents of files and memory.

     You have a problem when your system puts each little thing in one file. When you have a zillion little things, you'll lose big on open latency. So the one-thing-one-file coupling causes a clot in system granularity. The data channel plugs up as soon as time to access a file gets too big. Conventional systems have granularity problems in both code and data.

obvious is as obvious does ¶

     Two days ago Wes Felter sent an email in response to my event piece. I had used the word "obvious" in that context, about async event use. I guess it wouldn't hurt to spell out more clearly what's so obvious. Otherwise it might sound like I'm belittling Matt Welsh's research. Hey, I'm just some guy. What I discuss here is either useful or not.

Wes Felter: The implementation is Java-specific, but the SEDA papers are pretty general and IMO interesting. Before SEDA, I don't think anyone had figured out how to easily compose event-driven servers from components. Maybe this is already obvious to you, though.

     http://www.cs.berkeley.edu/~mdw/papers/seda-sosp01.pdf

     No, it wasn't already obvious to me how to easily compose event-driven servers. The words "easily" and "compose" both individually imply a great deal of work, of the sort that's seldom obvious without living and breathing the problem space for a while. And the words "figured out" imply a highly satisfactory level of quality which is even harder yet.

     However, that servers would be most efficient if designed as highly granular data flow engines with async events as the comm backbone was already obvious. Using threads heavily in a granularity that closes follows the granularity of requests obviously uses resources in a heavy handed way that could be better used to get actual work done.

     This doesn't mean I'm smart enough to figure out how to easily compose servers using that kind of architecture. That's something that requires actual performance of the feat to form an opinion. However, it would certainly be fun to try. And it figures into my medium range interests as applications of Mithril and IronDoc. (Which are both vaporware, for new readers.)

     Servers are so clearly stimulus and response systems that pay quite a bit less attention to the vagaries of user interface interaction, in comparison to typical desktop app design and implementation. This makes it easier to view them as pure data flow functional computing problems. This is a problem I already spent time thinking about years ago.

     On other occasions I described by job at C*ATS in Palo Alto, after leaving Taligent in 1993 and before joining the OpenDoc team in 1995. (I didn't join OpenDoc instead in 1993 because Apple had a savage hiring freeze at the crucial moment of truth.) Previously I said my work was adding polymorphic dispatching to a graphical programming language.

     That's true, but I never really emphasized before that the language was a lazy functional language, which intended to settle financial accounts in large distributed systems, and would rely upon parallel computation whenever possible based on knowledge of immutable data patterns. And only the computations needed to satisfy demanded outputs would execute.

     (This part of the problem reminds me a bit of Raph Levien's recent change notification piece for display updating. Strictly speaking, a display view need only recompute what is demanded for current display in visible areas. This resembles the lazy output computation problem we had at C*ATS. But our problem had the benefit of being generally more static in nature.)

     Anyway, the basic idea (... wait for it...) is that everything is a graph ... again! (It's always a graph in a every problem. Why do you suppose that is? :-) In this case, the interesting part of the graph is the dependency graph between what is demanded and the inputs that feed into the computations that generate the outputs. Dependencies drive computation.

     (And this part of the problem reminds me of Raph Levien's interest in writing a new kind of make build system named rebar. Obviously building generated object code from statically defined source code inputs is a lazy evaluation problem based on component dependencies. (How much do you want to bet some idiot patented that idea?))

     Similarly, you can view a server's typical behavior as executing a dependency graph to generate a response that satisfies the demand of a client request, given a model of server component dependencies that are involved in building a suitable output response. This is even more so in the context of caching (AKA memoization).

     Maybe I'm abnormal for viewing a lot of computation primarily as data flows, which get serviced by code that performs the necessary transformations and bit movement. I'm aware many folks focus instead on code that "does stuff" -- which is sort of idiotic when the patterns involved in what "gets done" never get examined in detail. (It's data flows.)

     I'm not an app writer. I'm not obsessed with apps that "do stuff" and look pretty for admiring audiences. I'm a runtime hacker, and I obsess about data flows -- exactly when bits changes, and how, and why, and what a programmer does in order to control this. I'm pissed off that queueing and async events are not already network norms.

     For example, when I talked to Raph Levien on the phone yesterday, he discussed some existing networking metaphors, like leases. I told him as far as I was concerned, as long as I was denied access to async events directly, every networking API was broken. I only want high level APIs when I also have a low level async back door.

     So basically, most server design stuff I heard sounds overtly stupid when it seems behavior centric (around code in threads) instead of being content flow centric (around data funneled through queues). I think Matt Welsh is to be congratulated for seeing things the more natural and intelligible way. But I don't see why I should pretend it's not obvious.

     Maybe my saying it's obvious is my way of intimidating folks who would otherwise be unable to judge for themselves, and might otherwise say it must be wrong because it's not the Apache way. Sometimes I have indirect and obtuse approaches to picking fights with incumbents. It sets the stage for a more amusing exchange with folks who say, "Nuh uh!"

asynchrony ¶

     I know I'm spending too much time talking about async event systems. But Raph Levien had more good remarks in his weblog on async APIs. Below I've quoted just three of the several paragraphs. There are more. I hope Raph didn't take my "app writer" remarks yesterday personally. I didn't have anyone in mind at all when I disclaimed my own style bias.

Raph Levien: Every time you do something over the network, it's asynchronous whether you like it or not. Yet, event-driven programs seem a lot more complex than their simple, synchronous cousins. David would like to recapture that simplicity in asynchronous programs. A lot of other people have tried things in this direction, without very happy results so far. I feel that CORBA is a cautionary tale in this regard. It pretends that method calls are really local, when in reality they're decomposed into two asynchronous events, and of course all kinds of things can happen in the meantime.

     CORBA made the mistake of trying to make object location transparent, so local and remote objects could not be easily distinguished. This is a terrible idea because location matters. I've spend a fair amount of time trashing transparency in general in the past. The following is a sample of something I wrote five years ago on orthogonal persistence.

I wrote on distobj: My opinion is that complete and utter transparency of some features is a flaw that fails under analysis using first principles. Extreme transparency prevents handling and control, hence practical failure. A feature must manifest concretely enough to permit theorems about invariants to be applicable, or otherwise little reasoning is possible.

     I'm not sure exactly how I plan to recapture simplicity in async systems. I find message sending simple in general, but other folks might disagree. For example, I find it easy to reason about the meaning of email when it arrives in a certain order that reflects the sequence of antecedents. I want to reason about event sending logic the same way.

     Of course async event sending is low level, and one ought to use some higher level combinations of the low level primitive effects. But the process of debugging ought to directly reveal the low level parts on demand. I want high level uses of events to be libraries using simple primitives. But code will be robust if it plans what happens when no reply is seen.

Raph Levien: I haven't seen any of the details of Mithril yet, but I'm fairly skeptical that it will make asynchronous programming accessible to less-skilled programmers. On the other hand, I am perfectly willing to believe that it will be a good tool for expressing asynchrony concisely, and thus useful for people who know what they're doing.

     I haven't said a lot about events in Mithril besides the model page and the associated dialog. But I also discuss Mithril events in this exchange with Wes Felter concerning BXXP, which has since been renamed to BEEP. I didn't have accessibility to less skilled programmers in mind when I was designing. But I wasn't trying to exclude them either.

     I suspect if less skilled coders are told to treat events like email messages that won't necessarily see any reply, they might start to get the hang of how things get organized when writing async systems. Then coders might correctly design systems to react only to what is known for sure from the last event received. But we'd need norms to avoid code bloat.

Raph Levien: I mentioned that the CSP way might be easier to reason about. There's another issue that came to mind after our call: the queue required for the fully asynchronous case requires unbounded resources in the general case. Obviously, in tiny embedded systems, this can be a real problem. On desktops, it's less clear. But if a system is operating under very high load, you probably want to worry about whether the queues will keep growing. Of course you can always implement flow control on top of async messages, but that's not really the point. On CSP, the default is not to grow unboundedly.

     As I mentioned here recently, I plan to have dock buffer sizing for events explicitly managed as part of event usage. Total transparency of policies is wrong. However, default policies that go in patterns is a good way to avoid manually setting every dial and meter. I worry about the unbounded resource usage in the general case. I'd disallow it by default.

     In our phone conversation I mentioned something I'd like to repeat for other folks. (I mentioned it to my boss last week too.) This was that I'd like to provide async event protocol APIs for libraries that I write. Instead of using the option of embedding a library, you could instead interact with a library as a server, using async events to communicate.

     Raph objected that this sort of async event API would not normally map onto a typical code library that is organized as synchronous method calls. That's when I told him the idea was to have the library itself also be async event driven internally as well. So the async event protocol would actually map directly to the native representation.

     For example, an async event version of IronDoc would be much better at fostering useful app progress when waiting for database disk i/o to happen. But that would probably require a rewrite after the next rewrite to integrate with Mithril using normal synchronous styles. One of the reasons I wanted to rewrite IronDoc in Mithril was to use continuations.

     Using continuations and trampolined execution, I could suspend a fiber asynchronously waiting for disk i/o, and run other code instead, without the agonizing overhead of lacing IronDoc infrastructure with threading assumptions. I'd use async events at the very least for handling my disk i/o and fiber scheduling, if not the IronDoc API itself at first.

async runtimes ¶

     Raph Levien's gonna lap me with his two new asynchrony diary posts. The last has an amusing echo of Joel Spolsky's new complements piece. I quote that part below, regarding Sun's Java motivation and hardware. I wish I had time to write about Joel's useful microeconomics piece now. Instead I'll comment briefly on Mithril threads and garbage collection.

Raph Levien: Matt chose Java for his implementation. On the surface, this is a strange choice. For one, until quite recently, Java didn't even have a nonblocking I/O library. Matt had to implement his own, using JNI. The path of least resistance is to use a thread per connection, which has scaling problems as the number of connections grows large. Of course, it's possible to mitigate these scaling problems by throwing more hardware at the problem. Now why would Sun do a thing like that?

     Elsewhere Raph notes lock contention, memory, and garbage collection. Mithril will not need any heap mutexes to allocate memory internally. In fact, memory allocation is a place I expect to see good performance. A Mithril city allocates boxes (i.e. cons cells) from large chapter blocks. Cities are single threaded so no mutex is needed in heap box allocation.

     In fact, box allocation can approach pointer bumping as average cost. Overhead for fragmentation and node size stats is much less than C++. Except when gc happens, Mithril box allocation is atomic and unlocked. Also, gc scoped within a city approximates generational gc performance. There are fast, simple ways to do these things without complex research.

shared nothing ¶

     I was hoping to respond to both Patrick Logan and to Jon Udell today. But I only have time to start this cursory setup for more discussion later. Jon Udell cites the same section about shared nothing message passing. Udell says, "I might have entitled it 'Multithreading Considered Harmful'." This is strongly related to async events and my Mithril messaging plans.

Patrick Logan: The guys who invented shared-memory multi-threading in the late 60s, early 70s discovered these problems early on. Which is why they went on to develop higher-level, shared-nothing mechanisms in the mid/late 70s. Why Java and subsequently dotNET adopted this troublesome 1960s technology at the core of their architecture is curious if the intent is an efficient but widely applicable language for developing concurrent Internet applications. It's like managing your own memory allocation, only worse.

     This is another case where I concur with Patrick Logan's perspective. Async event passing is a form of "shared nothing" messaging style. When you receive an event, the data belongs to you and isn't shared. In my Mithril memory design, cities will use single threaded gc space. This is another "shared nothing" design to keep any threads far apart.

complexity ¶

     These links to Raph Levien are the same diary entry as the next ones. I was going to address this question entirely in my next blog section. But it would be a shame to pass completely on open ended questions. They're such good starting places. We can come back to it repeatedly. An answer anticipating the next section is it depends on dependencies.

Raph Levien: Is it possible to use a much simpler technique to accomplish nearly the same results, nearly as well?

     Which results do we want to accomplish nearly as well? If the goal is to implement async event systems, then yes, this can be done in most systems without the cost being too painful. This is partly because async events are so much better that it's worth it no matter how horrible the host system is in typical cases. But it can be a major problem when the host runtime is already quite complex.

     I was looking forward to doing async events in Mithril where they'd be a trivial problem when the microthread scheduling algorithm considers them primitive. In that context I can also arrange large numbers of compound savings by leveraging common avoidances of inefficiency. For example, centralized tokenizing of metainfo symbols would improve both time and space behavior in low complexity.

     However, what if you meant accomplishing what a Mithril city does instead? There isn't a simpler technique for getting similar results at all, let alone nearly as well, as far as I can see. Generally the semantics of space allocation in a system must be primitive or it's a no go if one wishes to compete with "native" memory efficiency. Among other things, I really intend to see very small gc latencies.

     Regarding the problem of implementing async event systems -- I don't find this intrinsically interesting. I wouldn't invest a substantial amount of time doing what amounts to make-work trying to subvert stupid runtimes like the one in Java. I only consider async events a useful feature to have on the way to somewhere else, if I can have them for less than a man-month of labor. And I will in Mithril.

event passing context ¶

     This is where I start a response to Jeff Darcy's cool material (links now 404). However, first this will only be about my Mithril vaporware design. Come back another day if you only want my direct feedback on Darcy. What's my reason for discussing a vaporware design first? That's easy. I find analysis only useful in the presence of a question -- about design.

     A comparison of events vs threads seems irrelevant without a problem. Some folks focus on the problem of optimizing a server's performance. For example, one might ask what makes a web server perform best. That's not my question. I've a more general language-based question. And the basic question inspires a lot of other related subgoal questions.

     I'll start by asking many of these questions below. You might hate this. But questions are often more important than the answers they generate. That's because questions often remain useful if circumstances change. You can come back and get new answers for any new context you find. Whereas the old polished answers can become irrelevant as time passes.

     Ultimately I want to say when events and threads are used in Mithril. (In the vaporware design. I know you'll forget this is all vaporware.) Because if you don't know this, you might make random assumptions. For example, in my focus on events, you'll think threads are missing. I normally give shorter shrift to the parts mostly solved (e.g. threads).

     The general motivation is to remove dependencies in runtime graphs. (The first is about questions; the second: on tech food chain graphs.) In particular, depending on threads causes several types of problems. The big portability showstopper is: What if a platform has no threads? (Single platform folks blow off this question, but it makes me wince.)

     Here's weaker version of the question: What about interface coupling? How can you arrange code interfaces so threads are more orthogonal? The other more common questions folks ask are about performance. Can thread usage be assigned with less waste of available resources? Can threads multiplex effectively when otherwise too heavyweight?

thread independence ¶

     The big problem I want to solve is independence from native threads. So I can use them when available, or drop them in a New York minute. I don't want the way threads work to be any significant choke point. Most importantly, this makes it easier to port any high level language. I'd like presence of (m)any threads to be optional without code change.

     The last point has two critical practical effects, and I want both of them. First, I can tune a threading approach to fit analysis of code execution. But I can't do this if changing my mind will alter the code architecture. Second, I want the same code to work (at need) using only one thread. I might need to run in an embedded mode when threads are impossible.

     To folks who write multi-threaded servers, my concerns are pointless. The idea of total independence seems ridiculous. Threads are assumed. And the idea of tuning after analysis might seem a second order yawn. But it's huge to be able to go around and ignore a thread showstopper. One can continue development in other areas, without getting hung up.

tcp bashing context ¶

     Luke Gorrie replies to Jeff Darcy by writing a new TCP bashing essay. I didn't plan to write about this tonight, so this one citation is gratuitous. Actually, Luke's not bashing TCP -- he's saying others are bashing TCP. (Bashing is rote geek behavior, like sneezing is when you have allergies.) (It's no big deal. Pointing out bashing is more assessing targets are easy.)

Luke Gorrie: First off, there's not much against TCP as a reliable stream protocol for the internet. For people doing stream-based internet programs, TCP's doing a good job for them and they have no need to be "annoyed" with it or to invent their own hopefully-extra-efficient protocols based on UDP. The article doesn't suggest this, but I think it's a fairly common notion (y'know, for when it needs to be really efficient...)

     I'd been thinking a majority of my future event-based communication will not be stream-based. So a protocol engineered to work well for streams is not a particularly good match. Not if there's cost I pay for which I don't get a corresponding benefit. If an app has a high volume of little messages, with rare larger streams, then infrastructure oriented toward datagrams might be better.

     I envision apps sending each other short async messages, like people firing status emails at each other, where they stay happy as long as everything goes well. But at any sign of a problem, they can get a TCP connection to sync up, like two people talking on the phone when the email barrage is not sufficient. Time delayed communication is basically more efficient when it's sufficient.

serialized events ¶

     I've written several times about event passing as good coding style. And the original Mithril design put event dispatch as a central idea. The event format was always planned as at least two main encodings. An internal/local encoding would leverage efficient binary symbols. But an external/global encoding would use generic header formats.

     In particular, I always envisioned events as just like mail messages. For example, the colored text shown above comes from this old page. Lately I've been thinking more about events in the context of ycard. I want to show users exactly what happens when my Hypercard runs. So in principle I'll support event logging to trace messaging activity.

     One form of end user debugging can trawl through recorded events. Playback is also a typical thing one wants to do with recorded events. (But this is fraught with complexity, as I learned once at Taligent.) (At Taligent I tried to design safe low level event playback. It's hard.) Anyway, so picture a stream of serialized events in plain text format.

     This is a kind of input to data driven programming. It's like a script. But it's declarative rather than imperative, assuming events are data. If events contained executable scripts, that would be more like code. Instead, declarative data events can only execute in playback context. And the results depend entirely on how one wants to interpret them.

     Tonight's train of thought started with an idea of testing IronDoc. I've been vacillating back and forth between IronDoc and Mithril. I started working on the Biscuit prototype for good IronDoc testing. But it occurs to me I didn't really need much in the way of code. I could have tested IronDoc blob btrees with event-filled scripts.

     Data-only scripts could be filled with events denoting blob changes. The code interpreting such an event stream behaves likes a server. Each event in the stream resembles a request sent to a web server. An event resembles an HTTP request, but with different headers. (I parse HTTP requests in my day job, so I find this view natural.)

     The first Lisp interpreter I wrote was for testing a database this way. I sent the database I was writing events in the form of s-expressions. But I could have just as easily used line-based headers for this work. Now I'm thinking about using line-based events in header formats. Previously I had only thought about events in a transport context.

     Tonight I was thinking about a stream of arriving events as a driver. Partly it's because I'd been seeing ycard as discrete event simulation. But now I feel like I've stumbled onto a useful primitive perspective. However, all the parts are things I already knew before, so it's weird. I can't put my finger on what's now different about my viewpoint.

     Okay, let's return to a specific usage scenario that I was imagining. Interactive testing is my goal. (I really want interactive everything.) I like script-based testing mainly because I can do it interactively. Then I can capture the heart of a good session to use as a unit test. Tonight I imagined typing in event headers while testing some code.

     This is of couse similar to the way folks interactively test protocols. Every GUI application is basically similar to a server in this fashion. A main event loop is a server waiting for event requests from a user. In much the same way, a Hypercard engine is a server for UI events. Maybe the new idea tonight was just a plan to interpret test events.

     But this view further simplifies a ycard plan I already liked a lot. A main idea of my Hypercard design was to make scripting central. Everything you could do in the UI could also be done from a script. In fact, a UI would simply call the same code that any script would. (This was the idea of Mithril UI in general, also planned in ycard.)

     But I'd been thinking with a more code focus in scripts, however. Now I'm just seeing the scripts with a more data driven event focus. Of course there's some kind of mapping between the two at runtime. I prefer the dataflow perspective, however, since it has lower entropy. Code coupling tends to be inherently more fragile than data coupling.

     Anyway, now I see how to go about testing IronDoc and Mithril. And it dovetails with the way I planned to use ycard to drive them. It's now easier to grasp how Mithril does incremental compilation. Source code compilation is simpler as event-based than file-based. And that solves a puzzle I was having with build system manifests.

     It makes it easier to design an integrated development environment. With event-based inputs, one can drive event-based error reports. This makes it easier to think about queueing up compilation status. I want to end up with ycard being used as it's own coding system. Debugging and editing stacks would be cool to do by ycard stacks.

     Incidentally, this train of thought doesn't have any good ending. I merely drove you around through the center of the connections. On the fringes it connects to everything, so the web just gets bigger. However, tonight's train of thought leads to a specific coding plan. I'll make a utility class that focuses on processing streams of events.

     Then I can use this as an interactive driver for event-based unit tests. I can test both IronDoc and Mithril using it with lower dependencies. Neither IronDoc nor Mithril need depend on the other for unit tests. This was one of the cool parts -- removing an annoying dependency. I won't bother presenting my MIME multipart style encoding ideas.

     There's another good side effect of using event streams to unit test. The same event mechanisms also represent the protocol for a server. That means no difficult redesign is required to use ycard as a server. For that matter, the path to use IronDoc as a server is also smoothed. See, I was planning to use Mithril as my server writing language.

     (This entry dates from my October 2002 codenames for related projects — ynote was the name of my approach to async event message passing, in which I planned to use a pseudo RFC822 format when serializing events for remote dispatch.)

ynote ¶

     ynote is an event messaging scheme using simplified RFC822 (etc) formats to encode events. The other y

     Operating system events will be encoded as notes and passed to ycard so it can dispatch in a platform neutral manner. Notes can also be send from scripts, so neither scripting nor the UI has a dominant position over the other with regard to best native support.

     The term note means functionally the same thing as message, but ynote is a spec for a standard encoding of messages that can be used to implement several existing types of internet services. For example, HTTP web server requests and responses will be compatible with the note format, so ynote could be used to implement one part of servers.

     The first (and possibly only) ynote deliverable will be a spec which covers text formatting encodings, and object interfaces for accessing parsed representations of the text format.

     The ynote image looks like a postcard to illustrate the way note messages are like one-way mail messages, and includes a musical note to help illustrate that content itself can be notes, including the kind which is code when executed by yharp.

     (I wrote the following not long after starting at OSAF in 2002, thus the comment on Python. This material is only tangentially related to events and message passing, but it emphasizes more of the language aspect.)

handlers ¶

     Some programming languages are more suited to writing a Hypercard clone than others. When I'm not spending most of my time coming up to speed on the Chandler project, I'll write more of my planned ycard spec for a future Hypercard clone. My planned yharp scripting language for ycard ought to be a suitable language.

     When I write the yharp spec, it might be a redesign of my (vaporware) Mithril language, which is a variant of Smalltalk, in

     Hypercard allows code handlers to be defined on individual objects, but since Mithril is based on Smalltalk, it too uses a class based object system for defining the way code is defined and invoked. Generally speaking, the Smalltalk way puts methods in classes, and does not allow individual objects to have methods.

     So if I used Mithril to represent Hypercard style objects, I'd have to do one of two awkward things in order to apply Mithril unchanged. Either I'd need a ycard code dispatchging system different from Mithril's, or I'd need to make each object have it's own unique class when unique handler methods are added.

     The idea of generating a new class for most objects is a crummy idea. It would be better to add the ability to invoke methods on objects that don't belong to all instances of the object's class. (Incidentally, it seems Python already allows this, so it would be a good language to use as yharp.)

     In the general case (primitive builtin types are handled differently), each Smalltalk object instance has a pointer to its class. You can think of a class as a hash table of methods, among other things. This is not enough support for per-object methods.

     Each object instance could also have a pointer to an optional hash table of methods of specific to the one object instance alone. The slot for a pointer to a table for individual object methods would be a waste of space if every object had this slot and few objects actually had per-object methods. So perhaps a special subclass of the Object root class could add this member, and then all subclasses supporting per-object methods and slots derive from this new root class.

     I gather that Python object instances resemble a hash table of state slots and method slots already, so that Python objects need not have the same members even when instances of the same type. (Python object members are not declared, so they seem to be created on demand when first mentioned, typically in __init__ methods.)

hypercard ¶

     When I describe my principal interest in Hypercard, I tell folks about two main goals, where one is a user interface goal and the other is a backend engine goal.

     The harder of the two to describe is the backend goal, which is to achieve the message dispatching hierarchy among Hypercard stacks, cards, and widgets inside cards as implemented in the original version of Hypercard. This is what I consider the backbone of Hypercard's architecture. If you avoid it, it's not Hypercard.

     The easier of the two to describe is the frontend goal, which is to expose all app activity to users as inspectable scripts. It should be possible to "open" every visible user interface element and see scripts defining the behavior of widgets. By changing the scripts, a user could alter an application's behavior.

     Of course, users need not edit scripts, but they could. Presumably only a small percentage of technical users would do so, and other folks would merely use their innovations based on scripting. Apps modifiable by users through scripts are more useful because a cottage industry for customization and innovation can easily exist.

     For example, suppose you see a menu item named "Reload" under the "View" menu. What does that mean? I'd like a Hypercard clone to allow that menu item to be opened so you can see a script that runs when the menu item is selected. This script would be what the menu item actually means, and you could change it.

     The scripts might invoke methods which themselves need explanation. An app could support user examination of documentation for the methods. And in a development environment release of an app, the code defining the methods could easily be found and examined.

     Although the Chandler architecture does not aim to have the backend message dispatching character of Hypercard, it's possible to make parts of Chandler inspectable as scripts in the manner I desire, and this would be cool. Andy Hertzfeld's ideas about agents handling user activity might further this possibility.

     (As I get better at Python and more familiar with wxWindows used by Chandler, I'll probably get more interested in a version of a future ycard clone of Hypercard using Python and wxWindows, and maybe parts of Chandler. The focus of ycard would be the Hypercard style message dispatching architecture.)