What is the word for nonblocking coroutine stream stuff?
Posted 17 May 2000 at 18:33 UTC by raph
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
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
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 »
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).
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 »
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.
We had the same problem with terminology when writing the wvdial and
tunnel vision libraries - for lack of another word, we called it "going
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
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.
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().
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".
The name of the routine doesn't necessarily have to reflect the
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
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 »
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.
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:
For a routine that doesn't produce anything but just does
work, the usual term i've seen is "idletask" or "workproc".
I was all ready to cast my hide to the semaphore dogs and suggest
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:
Mojotoad (ducking, HHOS)
Actually, I think that the design pattern visitor comes closer to
you are describing. Even though it's not a container, I think the word
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.
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.
call it "iteration", posted 18 May 2000 at 08:16 UTC by cmm »
...and move on, unblocked and happy.
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"
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 »
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...
Thanks to everyone for the suggestions and discussion.
I was just working on a
very similar thing in the rproxy
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 »
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?