The Boston Diaries

The ongoing saga of a programmer who doesn't live in Boston, nor does he even like Boston, but yet named his weblog/journal “The Boston Diaries.”

Go figure.

Saturday, October 20, 2007

Some more musings on coroutines, plus a “proof-of-concept”

I spent today playing around with coroutines and how I might go about implementing them. My feeling is that with the upcoming push for multiprocessor systems, using some form of coroutines might make better use of such power, while at the same time being a bit easier to wrap the brain around instead of dealing with actual multithreaded programming.

My “ideal sample program,” which is a pseudo-C like language, looked like:

int main(string argv[])
{
  file input  = file.stdin;
  file output = file.stdout;
  
  switch(argv.items)
  {
    case 3: output = file.open.write(argv[2]);
    case 2: input  = file.open.read(argv[1]);
    default: break;
  }
  
  input => conversion(toupper)
        => strip_html
        => rot(13)
        => conversion(tolower)
        => rot(13)
        => output;
  exit(EXIT_SUCCESS);
}

/********************************************/

coroutine void conversion(char (*conv)(char))
        receive char c;
        send char;
{
  while(receive c)
    send conv(c);
}

/*********************************************/

coroutine void strip_html
        receive char c;
        send char;
{
  char c;
  bool in_tag = false;
  
  while(receive c)
  {
    if (c == '<')
      in_tag = true;
    else if (c == '>')
      in_tag = false;
    else
    {
      if (!in_tag)
        send c;
    }
  }
}

/******************************************/

coroutine void rot(int bias)
        receive char c;
        send char;
{
  while(receive c)
  {
    if (c.isupper)
    {
      c += bias;
      if (c > 'Z') c -= 26;
    }
    else if (c.islower)
    {
      c += bias;
      if (c > 'z') c -= 26;
    }
    
    send c;
  }
}

Why yes, the code in main() is reminiscent of the Unix command line. That's the intent. And on a uniprocessor machine, I suppose the code generated would be such that control would pass from one routine to another via some form of interprocedural goto (but hidden, much like the gotos are hidden in a while loop). And on a multiprocessor (or multicore) machine, you could create cheap threads and pipe the data between each coroutine.

And that's what my first prototype version did. This prototype is about three times longer, and uses pipes to transfer the data among the five threads that were created.

/*----------------------------------------------
; error checking removed to keep this example
; short.  It's already getting a bit silly
; in length, don't you think?
;---------------------------------------------*/

rc = pipe(p1);
rc = pipe(p2);
rc = pipe(p3);
rc = pipe(p4);

/*---------------------------------------------------
; the following is so I can avoid doing single byte
; calls to read() and write(), which will definitely
; destroy any performance gains we might get on a 
; multiprocessor system.  By wrapping these pipes in
; FILE *s, I automagically get buffering.
;
; Also, these structures contain the local data for
; each of the "coroutines" in this program,
; since I can only pass a single pointer to each.
;---------------------------------------------------*/

t1.fpin  = stdin;
t1.fpout = fdopen(p1[1],"w");
t2.fpin  = fdopen(p1[0],"r");
t2.fpout = fdopen(p2[1],"w");
t3.fpin  = fdopen(p2[0],"r");
t3.fpout = fdopen(p3[1],"w");
t4.fpin  = fdopen(p3[0],"r");
t4.fpout = fdopen(p4[1],"w");
t5.fpin  = fdopen(p4[0],"r");
t5.fpout = stdout;

rc = clone(conversion,&m_stack1[1022],FLAGS,&t1);
rc = clone(strip_html,&m_stack2[1022],FLAGS,&t2);
rc = clone(rot,       &m_stack3[1022],FLAGS,&t3);
rc = clone(conversion,&m_stack4[1022],FLAGS,&t4);
rc = clone(rot,       &m_stack5[1022],FLAGS,&t5);

while(1)
{
  child = waitpid(0,&status,0);
  if (child == -1)
  {
    if (errno == ECHILD) break;
    perror("waitpid()");
  }
}

Not only that, but there're plenty of places where things can break, although in my limited testing, things worked with very minimal error checking. I didn't bother to do any testing, this was more or less a “proof-of-concept” type thing.

I then thought of doing a second implemention, this time doing away with the pipes and seeing if I could somehow pass data directly between the “coroutines.” It required a bit of thought, and the solution I cooked up almost works (and I'll get to that in a bit).

The second version looks a bit like the first, only a bit less overhead since I don't have to create all the pipes:

/*-------------------------------------
; two extra threads are required for
; this version.  One to feed the file
; into the chain of coroutines, and one
; to accept the final data for the
; output file.
;--------------------------------------*/

t0.next = (struct parms_common *)&t1;
t1.next = (struct parms_common *)&t2;
t2.next = (struct parms_common *)&t3;
t3.next = (struct parms_common *)&t4;
t4.next = (struct parms_common *)&t5;
t5.next = (struct parms_common *)&t6;
t6.next = (struct parms_common *)&t0;

t0.pid = clone(INTERNA_input,  &m_stack0[1022],FLAGS,&t0);
t1.pid = clone(conversion,     &m_stack1[1022],FLAGS,&t1);
t2.pid = clone(strip_html,     &m_stack2[1022],FLAGS,&t2);
t3.pid = clone(rot,            &m_stack3[1022],FLAGS,&t3);
t4.pid = clone(conversion,     &m_stack4[1022],FLAGS,&t4);
t5.pid = clone(rot,            &m_stack5[1022],FLAGS,&t5);
t6.pid = clone(INTERNAL_output,&m_stack6[1022],FLAGS,&t6);

All the coroutines are linked together, and for the actual implementation, they all pause() (which stops the thread until a signal is received), and upon receiving a signal, process the data given to it (through a fixed location—you'll see in a second) and then signal the “coroutine” next in line before calling pause(). For instance, the conversion “coroutine”:

int conversion(void *arg)
{
  struct parms_conversion *parm = arg;
  int c;

  while(1)
  {
    pause();
    c = parm->c;

    /*--------------------------------------
    ; convert the data, and dump into the
    ; next coroutine's data block, then
    ; signal it that it can process the data.
    ;----------------------------------------*/

    parm->next->c = (*parm->conv)(c);
    kill(parm->next->pid,SIGCONT);

    /*-----------------------------------
    ; if we got an end-of-file marker,
    ; stop this thread.
    ;----------------------------------*/
    if (c == EOF)
      break;
  }
  _exit(EXIT_SUCCESS);
}

And it worked.

Mostly.

I was able to track the problem down to the stip_html() “coroutine”:

int strip_html(void *arg)
{
  struct parms_strip_html *parm = arg;
  int c;
  int in_tag = 0;

  while(1)
  {
    pause();
    c = parm->c;
    if (c == '<') { in_tag = 1; continue; }
    if (c == '>') { in_tag = 0; continue; }
    if (!in_tag)
    {
      parm->next->c = c;
      kill(parm->next->pid,SIGCONT);
    }
    if (c == EOF) break;
  }
  _exit(EXIT_SUCCESS);
}

It doesn't always trigger the next “coroutine” to run, which ultimately causes everything to grind to a halt. While I can hack this to work, it ultimately shows a rather critical failure on this method of implementing coroutines, in that any coroutine that doesn't send all the data it received further down the line will stop the entire chain.

And issues aside, it was about four times the code as the “ideal program.”

If anything, doing this exercise showed me two things. One, it's probably best to use pipes for “coroutines” under Unix. And two, the overhead in using “coroutines” is a bit frightening to do by hand. And it's frightening to think of all the bits that could fail. But is it worth worrying about? In Assembly it's easy to detect if some mathematical operation overflows (in fact, I haven't come across a CPU that doesn't detect overflow), but it's something I don't really concern myself with in C. Heck, in the first “proof-of-concept” I went with using fgetc() and fputc() which simply return EOF when anything bad happens. Sure, it simplifies the code, but it's hard to determine what went wrong when it goes wrong. Which is why I'm concerned: does abstraction scale?

More thoughts (now surfacing after writing all this): are coroutines really all that useful? I can see using them in mod_blog to simplify some code (mainly, formatting of entries) but in general, not much of the code I've written lends itself really to flow by coroutine. Perhaps it's that I don't have that particular tool in my toolchest and I've learned to work around it.

More pondering is required.

Obligatory Picture

[It's the most wonderful time of the year!]

Obligatory Links

Obligatory Miscellaneous

You have my permission to link freely to any entry here. Go ahead, I won't bite. I promise.

The dates are the permanent links to that day's entries (or entry, if there is only one entry). The titles are the permanent links to that entry only. The format for the links are simple: Start with the base link for this site: http://boston.conman.org/, then add the date you are interested in, say 2000/08/01, so that would make the final URL:

http://boston.conman.org/2000/08/01

You can also specify the entire month by leaving off the day portion. You can even select an arbitrary portion of time.

You may also note subtle shading of the links and that's intentional: the “closer” the link is (relative to the page) the “brighter” it appears. It's an experiment in using color shading to denote the distance a link is from here. If you don't notice it, don't worry; it's not all that important.

It is assumed that every brand name, slogan, corporate name, symbol, design element, et cetera mentioned in these pages is a protected and/or trademarked entity, the sole property of its owner(s), and acknowledgement of this status is implied.

Copyright © 1999-2019 by Sean Conner. All Rights Reserved.