Particles of coroutines

Following the very same idea of the previous post, I've implemented the same stuff for x86. No worry about details — I am not a x86 fan and lover — except that there are few tests I've not done in the m68k version (namely the latter assumed the compressed stream is not corrupted). But it's just noise, not worth considering.

Intel x86 assembly instructions suck, but I admit I don't know it very well and likely I haven't used some cool feature and I don't know any cool feature which, once I'll know it, will make my mind change. Rants end.

Since x86 has not too many registers, and since I've used C library (compiled with nasm, linked with gcc/ld) and x86 calling conventions apply, and since I wanted to avoid special purpose registers (ECX, ESI, EDI…) as “global” variable storage, there are extra push and pop to keep values between calls to library functions, while each coroutine assumes also that the register it's interested in, are not trashed.

The register EBP can be used for “shared” (or global) storage; in fact, I've used it to store the pointer to the token buffer, and the “continuation” address.

The yield/resume feature is done with this code (kept into a macro):

    mov ebx,[ebp]
    mov dword [ebp],$+9
    jmp ebx

First the next address is put into EBX, then it's replaced by the address of the instruction following the jump, then the jump to the address in EBX is performed.

That's all. Readers interested in the whole code can find it at this gist, but I doubt it's worth it. It'd be far more interesting to study an implementation that could be used for really, as the result of compiling high level language code.

Different calling conventions can make it easier, but then you need extra code to call external functions — sticking to common C calling convention on a system is the key to access a lot of code without the need for any kind of glue — almost. Rants end, again; guess when they began.

This may work fine for two coroutines. Let's reason about a third coroutine. Does it work? No. If you need to create another cooperation, e.g. between the parser which extracts tokens (a “lexical scanner” indeed) and a grammar parser (i.e. a parser), you'll be fucked up.

E.g. our parser at some point, instead of got_token, need to give control to another routine, namely the one which understands the grammar. Thus, for each coroutine pair we need a “slot” similar to the one in [ebp]. A theoretical JCONT macro would be more complex, and take into account at least the coroutine we want to give control to. E.g.

 parse:
     JCONT   parse,getc
     test    eax,eax
     ...
 .wend:
     mov     eax,TWORD
     ; the grammar_parser'd like to have ptr to buffer too
     ; ... but this could be a global, as it is
     JCONT   parse,grammar_parser
     ...

If there's a hashmap for each coroutine, then we need to initialize it first, and the somewhere likely we could need a reset too. The macro could look, in pseudocode, something like

    get_slot_of    %2
    mov            ebx,[ebp]
    mov            dword [ebp],$+9
    store_slot_for %1
    jmp            ebx

Just an idea, at a very late hour.

Syntax and efficiency in C

Time for a brand new post.

In my last job interview I was asked to write a function to copy a string. Thinking not about compactness, I wrote on the fly the following code

void strcpy(const char *s, char *d)
{
  while( *s != '\0' ) {
    *d = *s; s++; d++;
  }
  *d = '\0';
}

That of course works, but it is longer than the need (and by the way, it is not compliant with what standard says about real strcpy, but this is not interesting since making a standard-compliant function was not the point of the question).

As noticed by the person making the interview, such a copy can be written in one line. When I've finished the interview and went back with the mind to what I've said and what I could have said, I realized that I could have defended my on-the-fly implementation: it is clearer (isn't it?), it has the same efficiency of the "compact" version, being this one possible just because of the great flexibility of the C syntax... which is, however, a boomerang if abused.

Second thought. The "long" code is clearer. Maybe (usually, not using C compactness ability makes code clearer; but likely in this particular case the one-line version is even clearer). But, my doubt is now: is it really the same with respect to efficiency?

Let us first see how to "convert" the long version to the short one. First, post-increments can be done "in place".

 *d++ = *s++;

Then, assignment can be put into the while:

  while( (*d++ = *s++) != '\0' ) ;

And here's the trap. We don't need the final "terminator-missing fix". Apparently, the short version looks also more efficient. But if we unroll the loops, we have the same amount of assignments, of course. Moreover, the short version assign the terminator reading it from the source; this gives two memory access (one for reading from s, one for writing into d).

On the other hand, the long version, does not need the extra reading access to memory and can be optimized on many processor with a single instruction writing a byte constant (read at the instruction fetch time).

So, it seems that is is the opposite: long version is (slightly) more efficient!

Of course modern compilers' optimization can cancel this apparent advantage. But let's look what gcc does with the basic "implicit" optimization level.

The "short version" (S) x86 code (with added comments):

mstrcpy:
 pushl %ebp            # prolog
 movl %esp, %ebp
.L2:
 movl 8(%ebp), %eax    # get s in eax   M
 movzbl (%eax), %edx   # *s in edx (dl) M
 movl 12(%ebp), %eax   # get d in eax   M
 movb %dl, (%eax)      # *d = *s (dl)   M
 movl 12(%ebp), %eax   #                M
 movzbl (%eax), %eax   # take char*d in eax M
 testb %al, %al        # I
 setne %al             # is not 0? in the same al  I
 addl $1, 12(%ebp)     # these are the post    M
 addl $1, 8(%ebp)      # increments of d and s M
 testb %al, %al        # check al   I
 jne .L2               # loop if not 0 ('\0')  JT
 popl %ebp             # epilog
 ret

The "long version" (L) x86 code (with added comments)

mstrcpy2:
 pushl %ebp              # prolog
 movl %esp, %ebp
 jmp .L5                 # uncond. jump
.L6:
 movl 8(%ebp), %eax      # get s in eax    M
 movzbl (%eax), %edx     # *s in edx (dl)  M
 movl 12(%ebp), %eax     # get d in eax    M
 movb %dl, (%eax)        # *d = *s         M
 addl $1, 12(%ebp)       # d++             M
 addl $1, 8(%ebp)        # s++             M
.L5:
 movl 8(%ebp), %eax      # get s           M
 movzbl (%eax), %eax     # *s in eax (al)  M
 testb %al, %al          # I
 jne .L6                 # exec body if not 0 JT
 movl 12(%ebp), %eax     # get d      M
 movb $0, (%eax)         # *d = '\0'  M
 popl %ebp               # epilog
 ret

The M marks instructions that do memory access; let's count only the in-loop instructions first. S has 8 memory access instrs in loops; L has 8 memory access instrs in loop but S has 3 "register" instrs in loop, while L has none. So for S we have 8+3 in loop, for L only 8.

In S, when the '\0' is reached, the whole 8+3 instruction are performed; then the jump is not taken (JT stands for Jump Taken most of the times). In L, when the '\0' is found, (2+2)+1 instructions are executed (2 M after the .L5 label, and 2 M after the conditional jump). In fact S performs all the "actions" of the C code (post-increments inclusive) in the while; but L does only the test on *s and the final termination of d. (This means also that if we access s and d in the S version, they point one char beyond '\0', while in the L version we do not increment them, since we exit the loop, so s and d will point to the '\0').

On modern processors it is hard to say which is really more efficient. Likely, the difference in performance is negligible. Moreover, optimizations done by the compilers may level down the difference, if any.

It is however worth noting that L version does not produce a so longer code (considering also loop unrolling), and it could be even more efficient than S version!