Self-modifying code (and space/time complexity)

[Radford Neal]

There are interesting cases where on-the-fly generation of code seems
to be essential to get good asymptotic space and/or time complexity.

Consider the following code fragment (version A):

     for (i = 0; i<L; i++)
     { if (c1) p1();
       if (c2) p2();
       ...
       if (cN) pN();
     }

The Boolean variables c1, c2, ... cN are assumed to be loop invariants.
Assuming the pi all take the same constant time and code space, the
time complexity of this code is O(N), and its space complexity is also
O(N). (I'm ignoring the factor of L for number of loop iterations.)

Now consider the following equivalent code, specialized for N=2, but
clearly generalizable to any N (version B):

     if (c1)
     { if (c2) for (i = 0; i<L; i++) { p1(); p2(); }
       else    for (i = 0; i<L; i++) { p1(); }
     }
     else
     { if (c2) for (i = 0; i<L; i++) { p2(); }
       else    /* Nothing */ ;
     }

Code like this will have a time complexity of O(M), where M is the
number of ci that are actually true, and a space complexity of O(2^N).

Let's say that M, the number of true ci, is typically logN. This gives
the following comparison for versions A and B:

     version  space   time

        A     O(N)    O(N)
        B     O(2^N)  O(logN)

Thus you get to choose between time that is exponentially worse than
it might be, or space that is exponentially worse than it might be.

The following lets you get both (version C):

     start generating code;
     if (c1) generate instruction to call p1;
     if (c2) generate instruction to call p2;
     ...
     if (cN) generate instruction to call pN;
     for (i = 0; i<L; i++) execute generated instructions;

This gives you the low time complexity of version B, with the low
space complexity of version A. It's machine dependent, however.

It _is_ possible to get the same form of time complexity without
machine dependent operations, as follows (version D):

     void (*pa)[N+1];
     j = 0;
     if (c1) pa[j++] = p1;
     if (c2) pa[j++] = p2;
     ...
     if (cN) pa[j++] = pN;
     pa[j] = 0;
     for (i = 0; i<L; i++)
     { for (j = 0; pa[j]; j++) (*pa[j])();
     }

This essentially works by generating code in a very specialized
language, and then interpreting that code. This gives the same
form of time complexity as version B, but with a larger constant
factor - perhaps considerably larger if the pi aren't really procedures,
but just short code sequences.

This is the general sort of reason for the bit-blit algorithms that
generate code on the fly, and I've encountered the same sort of 
situation in other contexts (e.g. a "life" program). One could 
imagine a compiler performing the transformation from version A
to the machine-dependent version C, but I've never heard of such.
Even if it did, it is a bit disturbing that a transformation of
such significance for space/time complexity isn't expressed at the 
source level. This would be solved by having the compiler transform
version D to the faster version C, but that's probably even harder
for the compiler-writer to accomplish than the A to C transformation.

    Radford Neal