Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

fastest wc program

Name: Anonymous 2013-08-07 20:47

Write the fastest program that counts the number of words and lines in a string.

Here's my solution

#include "stdlib.h"
#include "stdbool.h"
#include "stdio.h"

// macro that increments index, sets variables for the next stage, and
// gotos the label indexed by the current character
#define next(c, lc, iw) cnt = (c); lcnt = (lc); in_word = (iw); idx++; goto *(jmp_arr[(int)str[idx-1]]);

                             
int main(int argc, char** argv)
{
  /* test string */
  char* str = argv[1];
 
 
  /* normally this would be done as a sort of partial evaluation, but i can't for example generate an optimized function at runtime in C */
  void** jmp_arr;
 
  jmp_arr = malloc(sizeof(char)*256);
  int i;
  for (i = 0; i < 256; i++)
    {
      switch ((char)i)
        {
        case '\n':
          jmp_arr[i] = &&newline;
          break;
        case ' ':
          jmp_arr[i] = &&whitespace;
          break;
        default:
          jmp_arr[i] = &&character;
          break;
        }
    }
 
  // null character points to exit label
  jmp_arr[0] = &&terminate;

 
 
  int cnt = 0;
  int lcnt = 1;
  bool in_word = false;
  int idx = 0;
 
 // jump to label for first char
  goto *(jmp_arr[(int)str[0]]);
 
 terminate:
  printf("words: %i, lines: %i\n", cnt, lcnt);
  return 0;
 
 whitespace:
  next(cnt, lcnt, false);
   
 newline:
  next(cnt, lcnt+1, false);
 
 character:
  if (in_word)
    {
      next(cnt, lcnt, true);
    }
  else
    {
      next(cnt+1, lcnt, true);
    }
}

Name: Anonymous 2013-08-08 1:06

>>6
The point is partially evaluating the part of the problem that is statically known.  It's difficult to do this in C, (it would require piecing together machine code by hand, compiling and loading code from another program at runtime, or using C macros)
 so I just did it in the same chunk of code.
And since it works, it quite obviously handles whitespace.

>>7
Yeah, I didn't feel like hacking that in, but the lisp version compiles the jump table into a function.

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List