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 3:02

>>33
If you're reading byte-by-byte or if the maximum chunk size is too small to dispatch to another thread without overhead killing you. The latter is probably true on many systems, but if you can avoid copying Steele's algorithm is still faster.

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