Turbocharge Awk Scripts – Translate into C (Sudoku Revisted)

by Bill Duncan, VE3IED on February 10, 2010

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.


Linux Sysadmin Course Linux provides several powerful administrative tools and utilities which will help you to manage your systems effectively. If you don’t know what these tools are and how to use them, you could be spending lot of time trying to perform even the basic administrative tasks. The focus of this course is to help you understand system administration tools, which will help you to become an effective Linux system administrator.
Get the Linux Sysadmin Course Now!

If you enjoyed this article, you might also like..

  1. 50 Linux Sysadmin Tutorials
  2. 50 Most Frequently Used Linux Commands (With Examples)
  3. Top 25 Best Linux Performance Monitoring and Debugging Tools
  4. Mommy, I found it! – 15 Practical Linux Find Command Examples
  5. Linux 101 Hacks 2nd Edition eBook Linux 101 Hacks Book

Bash 101 Hacks Book Sed and Awk 101 Hacks Book Nagios Core 3 Book Vim 101 Hacks Book

{ 3 comments… read them below or add one }

1 Rick Stanley February 10, 2010 at 11:46 am

Why did you post the full awk code but not the full C code that you used to run the test?

I also notice that you are still using the old K&R coding standards. It surprises me to still see:

void mark(r,c,try, flag)
int r,c,try, flag;
{

}

instead of:

void mark(int r, int c, int try, int flag)
{

}

2 bill duncan February 10, 2010 at 3:44 pm

The other bits of the C program were not very interesting and the one I wrote wasn’t very elegant.. ;-)

The only bits left out are the I/O routines and main(). You can easily set up the parsing for the tokens using strtok() or something similar. If anyone writes a parser for this and wants to submit it here..

As for the K&R coding style; it’s been a while since I did much coding in C, so I often fall back to that when I’ve been away from it. I meant to change it before publishing, but I got sidetracked and it got missed..

Thanks!

3 clarf February 10, 2010 at 9:48 pm

“If there is interest, it will be included in a future article.”

Sure, I usually include awk in many scripts instead of calls to tr, sed, tail and other commands. It´ll be very interesting to see how to make awk programs faster and how to implement awk in an elegant way replacing complex shell commands.

Do you know some important tips to share?

Thank you for the attention pleased,
clarf

Leave a Comment

Previous post:

Next post: