What is the word for nonblocking coroutine stream stuff?

Posted 17 May 2000 at 18:33 UTC by raph Share This

While hacking on libart, I came across what I think is an interesting gap in the terminology of the field. I'm converting the art_svp_render_aa loop so that it can do one scan line at a time rather than the whole thing in one go. But what should the new routine be called?

Clearly, there should be some commonly accepted name for the technique. It's certainly a common programming technique to break out individual iterations of the loop, and putting the state that had been local variables into a "context" data structure. However, I could not come up with a name, even after asking my friends on #gnome. Thus, I put out the challenge to the Advogato community.

There are a lot of concepts that come close. It's not that far from the Iterator pattern in the Design Patterns context, but that's usually used to traverse a container class. In this case, it's not a data structure, but scanlines of an image to be computed. In this way, I suppose, it's not too dissimilar from a function that returns a list of scanlines in a lazy functional programming language, but here we're doing it explicitly in C, not leaving it for the language to take care of.

If you run more than one of these at the same time (which I expect to happen when you ask for more than one vector-path mask when rendering an image), then it's coroutines. However, I'm not really doing any fancy manipulation of the control flow.

In the GUI context, the function itself is called a "work function" or an "idle function", in the latter case because it's scheduled with g_idle_add (at least in Gtk+).

The technique is also widely used to build nonblocking, asynchronous networking code, of which Squid is probably the most notable example. Also in this context, "inverted thread of control" is used to describe the overall architecture. You also see the technique used in streams.

I'm generally very fond of the technique, having used it often in my career. It's a nice, lightweight way to decrease the latency of processing. It also saves memory for buffering the intermediate results. In this way, it competes against threads, but is in some ways nicer - you avoid the buffering and synchronization issues. Unless you're trying to exploit SMP, can be a good way to create the illusion of threads without actually threading.

So, this seems to be a general concept in computer science, cutting across a number of different specializations. Nonetheless, I don't know of a commonly accepted term for it. Possibly there is one that I'm just missing, in which case please let me know. Here's your chance to help name a function in libart!


names, posted 17 May 2000 at 19:39 UTC by imp » (Master)

More gui toolkits than gtk have this concept. In the OI toolkit that I was involved with years ago we had both an idle callback (which is called the next time the system is otherwise idle) as well as a timeout callback (which was called no sooner than N microseconds in the future).
You are basically combining the concept of an idle callback with that of an iterator. Each iteration of loop is one callback. It is very similar to having a sched_yield() function in each interation, only the location of where stuff is done has moved.
Personally, I'd be inclined to call it a work routine and be done with it. I'd call it RenderOneLine or DoSomeWork (or render_one_line or do_some_work if you aren't into the RansomNoteStyleOfFunctionNames).

some possibilities, posted 17 May 2000 at 19:55 UTC by graydon » (Master)

normal names which aren't quite right: thunk, strategy, policy, template method, callback, cursor, self-updating closure (see STG), hook, continuation, promise.

if you want something suggestive of the action (entering the subroutine for a bit, then yanking back out briefly) and would like to avoid sexual connotations, perhaps "boomerang" or "harpoon" might be good.

though personally, being the animal rights kinda person I am, I'd name it a "hiccup".

"iteration"?, posted 17 May 2000 at 20:58 UTC by mjs » (Master)

The gtk function for doing one iteration of the main loop is called "gtk_main_iteration", that is similar to "iterator" but perhaps more clear in this kind of context.

Perhaps just "asynchronous", posted 17 May 2000 at 21:26 UTC by apenwarr » (Master)

We had the same problem with terminology when writing the wvdial and tunnel vision libraries - for lack of another word, we called it "going asynchronous."

If you know anything about digital logic system design, there are three main types of circuits: combinational, synchronous sequential, and asynchronous sequential (also known as "fundamental mode").

Synchronous sequential logic circuits do something whenever the clock cycles; asynchronous circuits don't use a clock, but they change immediately in response to a stimulus input, and stop changing once they've finished responding to the stimulus (which usually happens very quickly).

In terms of software, you can imagine that threads start and stop under the control of a clock -- synchronous -- but our callback functions wait for a stimulus (an event happened, or we get an "everyone is idle" message) do something about the stimulus, and then stop when it seems reasonable -- asynchronous.

So amaze your friends: call it an asynchronous sequential callback. Ooh, ah.

Incidentally, when systems like this get relatively large it becomes more and more painful to do this sort of callback stuff properly. Although I call it a "sequential" callback, the code looks anything but sequential -- what used to be a function written in order, from top to bottom, is not a bunch of code fragments in a giant nested "if" or "case" statement. The right way to do this sort of thing is co-operative multitasking, where you call something like schedule() when you want to give up your time slice, and schedule() appears to return when your function gets called again. This is safe from race conditions and avoids the need for semaphores, unlike threads, but is still easy to abuse -- see most Windows 3.x applications for examples of how to screw up co-operative multitasking for everyone.

The next release of Tunnel Vision (and probably wvdial2) are going to use a simple co-operative multitasking system I wrote called WvTask -- yes, it's actually possible to write a portable implementation of this in plain C/C++, using setjmp() and longjmp().

Have fun.

What about "incremental"?, posted 17 May 2000 at 22:16 UTC by andreas » (Master)

There's a similiar pattern widely used in garbage collection techniques, where instead of pausing the program to wait for the garbage collection to finish, a little bit of the garbage collection is executed each time memory is allocated. This is widely known as "incremental garbage collection", and it is considered valuable since it increases user experience: no more sudden stops of program execution.

So you could name your routine "incremental scanline rendering".

Don't just sit there...DO SOMETHING!, posted 17 May 2000 at 22:44 UTC by jlbec » (Master)

The name of the routine doesn't necessarily have to reflect the technique.

That said, why isn't it an iteration? Yes, there is no fancy underlying data structure, but the point of an iterator is that you get the content you want without having to discover the inner workings. The NextLine() doesn't return anything, sure, but it still does a one-iteration traversal of the data, producing a result. Note that g_list_foreach() doesn't allow for returns, but I would still contend that it iterates over the list. Maybe a "strict" definition of iterator is being applied, but all of these cases satisfy my idea of it.

I kind of like the "asynchronous sequential callback" term. I don't know if that really falls into a technique name properly, but it is a good description of what is happening.

But when it comes down to the function name, I would choose render_one_line(). It describes exactly what is expected from the routine.

Single loop control systems..., posted 17 May 2000 at 22:48 UTC by argent » (Master)

I'm not entirely sure which mechanism you're referring to, but in the realtime control industry the single loop control system, where some main loop spends a little time running bits of several jobs to, if not completion, at least a stopping point where they can save state.

You also have "soft interrupts" running more critical stuff in between the tasks in the main loop. These are more like the "event loop" model that Macs use.

Relay Race, posted 18 May 2000 at 00:10 UTC by bernhard » (Master)

I hope I understand correctly what's going on. What your code does seems similar to a relay race in that the state is passed on from one run of the function to the next. So perhaps relay would be a godd name for this technique and your routine could be called art_svp_render_relay.

This is a generator., posted 18 May 2000 at 01:06 UTC by ping » (Master)

If i understand your description correctly, what you're talking about is a generator: it's a thing that has some state, and you call it several times in sequence, and each time you call it, it generates some more stuff. Your "lazy list" description exactly fits the word "generator".

Some references to this terminology: in Python, in C++, in Scheme.

For a routine that doesn't produce anything but just does work, the usual term i've seen is "idletask" or "workproc".

Generator, automata, quantum blocks..., posted 18 May 2000 at 06:02 UTC by mojotoad » (Journeyer)

I was all ready to cast my hide to the semaphore dogs and suggest "quantum callback"...

However, I really liked the point of the "generator" suggestion. It's an asynchronous state-based generator...which should be familiar to anyone who has studied cellular automata.

So you could condense the concept a bit and call it "celluar callback".

And then, of course, the natural name should be apparent:

bad_driver

Mojotoad (ducking, HHOS)

Visitor, or just plain Hook, posted 18 May 2000 at 06:15 UTC by Talin » (Journeyer)

Actually, I think that the design pattern visitor comes closer to what you are describing. Even though it's not a container, I think the word still applies.

The other possibility is to simply call it scanline hook. I generally use the term "hook" to refer to any callback in a framework, even virtual functions which are meant to be overloaded but don't otherwise do useful work in the base class.

More off-the-cuff suggestions..., posted 18 May 2000 at 06:43 UTC by mojotoad » (Journeyer)

Vistitor sounds interesting...

A few more: ratchet, tiller, evolver (?)...

I like ratchet. It has the taste of a state-based update...the others have a bit of an analog flavor to them.

Mojotoad

call it "iteration", posted 18 May 2000 at 08:16 UTC by cmm » (Journeyer)

...and move on, unblocked and happy.

Don't get too narrow with definitions, posted 18 May 2000 at 13:44 UTC by Rasputin » (Journeyer)

An iterator is simply a function or process that repetitively repeats an action for each instance of some "thing" until it is out of "things" to work on. It doesn't matter if these "things" are containers, structures or scan lines or whatever.

That seems to be a good definition for what you're doing.

generator!, posted 18 May 2000 at 15:59 UTC by effbot » (Master)

or "incremental renderer", if you prefer.

but as someone pointed out, render_one_line is probably a better name. I'd probably make it into a render_lines(n) instead; you can always get some extra speed out of it if you don't have to update the state struct for each line...

And the winner is..., posted 18 May 2000 at 16:42 UTC by raph » (Master)

art_svp_render_aa_iter

Thanks to everyone for the suggestions and discussion.

use in nonblocking IO in rproxy, posted 23 May 2000 at 02:21 UTC by mbp » (Master)

I was just working on a very similar thing in the rproxy library.

Because this is going to go into programs with different IO strategies (threads, nonblocking, blocking) we can make no assumptions on how we'll be called. So, on each call to hs_encode_iter we read in whatever data is available and process it.

The hs_encode_iter function devolves to three internal coroutines, which perform the three encoding functions: generating a whole-file checksum, generating per-block checksums for future matching, and searching for matches with the old file. Each of these has to process independently through the input stream.

What about step., posted 31 May 2000 at 23:04 UTC by notzed » (Master)

I'd just call it a step, but then, being an engineer, I'd rather just get the work done rather whan work out what to call the work function!

Or even "line", since it processes a whole line at a time, right?

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!

X
Share this page