Turbocharge Awk Scripts – Translate into C (Sudoku Revisted)

Photo Courtesy: Kol Tregaskes

In the first article of this series we saw how awk could be put to work (or play) for more than just processing text. The simple script demonstrated the use of associative arrays, recursion and how we could use more arrays (more than required to represent the data) to speed up the processing. There were some teaser ideas left at the end if you were looking for something faster.

When would you need something faster? One reader pointed out that solving the puzzles is easy. What if you were designing a system to generate puzzles? One of the tools you would need is a program which ensures that there is only one solution to a puzzle. (Another reader, Milos, suggested slight modifications to find all solutions.) Or, what if we wanted to increase the size of the puzzles to 16×16 or 25×25?

Translating the script to a fast compiled language might help and in this article we’ll examine one of the major benefits of awk with the ease of translating to C when necessary.

First Cut Translation

In our first stab at translating the program we will show snippets of the code side by side to demonstrate the minor differences required. We’ll examine the three main functions which get hit the most; inuse(), mark() and the recursive search() function. The code is so close that a copy of the awk program to start editing for the conversion to C was used.

First, to get some of the definitions out of the way. We’ll also use the region pre-compile since we’re after more speed. The first difference needing to be dealt with is that the awk array indexes were one relative and by default C array indexes are zero relative. For our purposes and to keep things simple, we’ll continue to use the one relative indexes and allocate arrays with additional elements.

#define SUBORDER 3
#define ORDER    (SUBORDER * SUBORDER)
#define MARK     1
#define UNMARK   0

int  count = 0;
unsigned int  regmap[ORDER+1] [ORDER+1];
unsigned int  master[ORDER+1] [ORDER+1];

unsigned int  C[ORDER+1][ORDER+1];
unsigned int  R[ORDER+1][ORDER+1];
unsigned int  Q[ORDER+1][ORDER+1];

#define fregmap(r,c) (regmap[r][c])

/* precompile region map for faster lookup
*/
int initregmap()
{
   int i,j;

   for (i = 0; i < ORDER ; i++)
     for (j = 0; j < ORDER ; j++)
       regmap[i+1][j+1]  =   i/SUBORDER*SUBORDER + j/SUBORDER +1 ;
}

The Awk to C Comparison

Now to delve into the three main functions to see the similarities and slight differences. The original awk versions of the functions are left as comments. Here are some of the differences:

• C requires function, parameter and variable type declarations
• awk does not require semicolon statement separators if there is only one statement per line
• awk “fakes” multi-dimensional arrays by using associative arrays and separating the indexes with the SUBSEP character represented with a comma
• in awk, local variable declarations are simply thrown in with the parameters for the function, usually with extra spaces to separate them for readability
• comment delimiters are different
• functions are declared differently
• C uses zero relative indexes for arrays

Nevertheless, you can see a direct one-to-one correspondence and translating from awk to C is almost trivial in this example.

inline int inuse(r,c,try)                        // function inuse(r,c,try) {
int r,c,try;                                     //
{                                                //
  int q = fregmap(r,c);                          //   q = fregmap(r,c)
                                                 //
  return (R[r][try] || C[c][try] || Q[q][try]);  //   return (C[c,try] || R[r,try] || Q[q,try])
}                                                // }
	

inline void mark(r,c,try, flag)                  // function mark(r,c,try, flag,          q) {
int       r,c,try, flag;                         //
{                                                //
  int q        = fregmap(r,c);                   //   q = fregmap(r,c)
                                                 //
  Q[q][try]    = flag;                           //   Q[q,try]    = flag
  R[r][try]    = flag;                           //   R[r,try]    = flag
  C[c][try]    = flag;                           //   C[c,try]    = flag
  master[r][c] = flag ? try : 0 ;                //   master[r,c] = flag ? try : 0
}                                                // }




int search(r,c)                                  // function search(r,c,   q,i,a,try) {
int        r,c;                                  //
{                                                //
  int q,i,a,try;                                 //
  count++ ;                                      //   count++
                                                 //
  while (master[r][c]) {                         //   while (master[r,c]) {
    if (++c >  ORDER) {                          //     if (++c >  ORDER) {
      c = 1 ;                                    //       c = 1
      if (++r >  ORDER) {                        //       if (++r >  ORDER) {
        /* then we're done filling */            //         # then we're done filling!
        return 1 ;                               //         return 1
      }                                          //       }
    }                                            //     }
  }                                              //   }
                                                 //
  for (try=1; try <= ORDER; try++) {             //   for (try=1; try <= ORDER; try++) {
    if (! inuse(r,c,try)) {                      //     if (! inuse(r,c,try)) {
      mark(r,c,try, MARK) ;                      //       mark(r,c,try, 1)
      if (search(r,c)) return 1 ;                //       if (search(r,c)) return 1
   /* else zero returned -- unwind, unmark */    //     # else zero returned -- unwind
      mark(r,c,try, UNMARK) ;                    //       mark(r,c,try, 0)  # unmark
    }                                            //     }
  }                                              //   }
                                                 //
  return 0;                                      //   return 0
}                                                // }

Bitmaps

One of the keys to speed alluded to in the previous article was using bitmaps for the R, C and Q arrays. Since each of these arrays is only used to test for element membership or not, it is strictly a binary function that could be represented by a single bit instead of an int. This enabled us to test whether an entry was valid or not (one of the hardest hit functions) in very few machine cycles relative to other lookup methods.

Here are a few code snippets to show how it resembles our original awk prototype. The obligatory declarations have changed slightly from the original C version above; we've lost a dimension for the C, R and Q arrays and we'll be using the ints as bit arrays.

-----------------------------------------------------------------------------
#define SUBORDER 3
#define ORDER    (SUBORDER * SUBORDER)
unsigned int  regmap[ORDER+1] [ORDER+1];
unsigned int  master[ORDER+1] [ORDER+1];

unsigned int  C[ORDER+1];
unsigned int  R[ORDER+1];
unsigned int  Q[ORDER+1];

-----------------------------------------------------------------------------

The mark() and inuse() functions are called many times and this is where we need the fast direct lookups. The mark() function is a tad more complex than the awk and original C versions because of the bit-fiddling we need to do. However, the inuse() function is very simple.

-----------------------------------------------------------------------------
void mark(r,c,try, flag)
int       r,c,try, flag;
{
  unsigned bitmap = (1 << try) ;
  int      q      = fregmap(r,c);

  if (flag) {
    Q[q]        |= bitmap ;
    R[r]        |= bitmap ;
    C[c]        |= bitmap ;
  }
  else {
    Q[q]        &= ~bitmap ;
    R[r]        &= ~bitmap ;
    C[c]        &= ~bitmap ;
  }
  master[r][c] = flag ? try : 0 ;
}

int inuse(r,c,try)
int r,c,try;
{
  int q = fregmap(r,c);
  unsigned bitmap = 1 << try;

  return ((R[r] | C[c] | Q[q]) & bitmap) ;
}

-----------------------------------------------------------------------------

The search() function remains virtually unchanged from the awk version and is identical to our original C version above.. We've used information hiding to conceal the fact that the other functions use bitmaps for lookup.

Bottom Line

The timing results are interesting. Both C versions are for a thousand iterations, as a single iteration was too small to measure reliably. On our system we get the following results on average for a sample file:

1. Original awk script – real: 10.9s, user: 10.2s
2. First C version – 1000 iterations, real: 21.2s, user: 19.7s
3. Second C version with bitmaps – 1000 iterations, real: 16.4s, user: 15.1s

The original awk version ( solve.awk ) is about 500x slower than the first C version and maybe 675x slower than the bitmap version (using the user times).

The awk script was certainly fast enough for most purposes and this will often be the case in real-world scripts. When there is a requirement for more speed, awk may still be used as an effective prototyping tool. The similarity to C in some ways makes it fairly straightforward to translate to this language when the need arises which is another big plus for awk over the alternatives. You can't always assume that it will be this much better in C however. This was a fairly CPU intensive contrived example. Text processing, where awk really shines, is another matter.

When used carefully, awk can sometimes surprise us with its speed. For example, the “established wisdom” is that if you can do something with grep or sed, that it will be faster than awk. Not necessarily true. A log parsing sed script was recently replaced with a version written in awk which was about 40 times faster and far more flexible. This makes a great difference when parsing tens or hundreds of gigabytes worth of log files. If there is interest, it will be included in a future article.