Wc2: Investigates optimizing 'wc', the Unix word count program

Post by throwaway55533 » Thu, Jun 20, 2024, 5:33 PM UTC

GrantMoyer wrote: post #55

throwaway55533 wrote: post #53

From reading the article, how is this more efficient? Doesn't any word counting algorithm have to iterate through all the characters and count spaces? What makes this better than the standard algorithm of wc = 0 prev = null for ch in charStream: if !isSpace(ch) and isSpace(prev): wc += 1 prev = ch

Basically, it's just a lookup table for isSpace, rather than whatever logic is in the original function (which probably has conditional branches). There's a little bit of a complication in the fact that a state machine can implicitly share parts of the computation for utf-8 encoded codepoints with shared prefixes, so instead of a 2^32-element lookup table, you only need 4 2^8-element lookup tables (and instead of 1 s…

Post by kardos » Thu, Jun 20, 2024, 5:51 PM UTC

Vvector wrote: post #57

James_K wrote: post #36

Earlier quoted context omitted.

You can figure it out by just looking at the table and output. It prints the number of lines, then words, then characters. Since the lines count is counts[1], you can conclude that when a newline is encountered, the machine will transition to state 1, hence why the newline is the only 2 entry in the character table and all 2 entries in the state machine point to state 1. From the character table, we can see that char…

I've read recently (here on HN) that branch predictors are right 99% if the time. Is that inaccurate?

Post by btown » Thu, Jun 20, 2024, 5:58 PM UTC

Post by mananaysiempre » Thu, Jun 20, 2024, 6:04 PM UTC

mananaysiempre wrote: post #64

thequux wrote: post #7

Earlier quoted context omitted.

A hand-written SIMD wc is likely to be even faster than a state machine, but at the cost of orders of magnitude more work. The huge advantage of state machines are that they are a relatively generic approach that provides massive speedups nearly every time. A SIMD wc algorithm is a significant effort that can't be generalized, and is only likely to provide a 4x speedup or so: rarely worth it except in cases where the…

An ASCII SIMD wc would likely be much more than 4× faster. The 320 MB/s is speed TFA quotes is good for a byte-at-a-time solution, but pitiful as far as the capabilities of modern machines are concerned. A decent SSD is an order of magnitude faster than that. Around 1 GB/s (i.e. ~100 cycles/fetch) is table stakes for a task of this complexity. (TFA almost nerd-sniped me into writing a SIMD implementation already, and…

  #if 0 /* shell polyglot */
  exec ${CC:-cc} $CPPFLAGS -g -O2 -march=x86-64-v3 $CFLAGS -o "${0%.c}" "$0" || exit $?
  #endif
  /* SPDX-License-Identifier: CC0-1.0 */
  
  #include 
  #include 
  #include 
  #include 
  
  int main(int argc, char **argv) {
      const char *const progname = argc ? argv[0] : "";
      unsigned long long bytes = 0, words = 0, lines = 0;
      uint32_t prev = -1;
      for (;;) {
          static __m256i buf[1024 * 1024];
          ssize_t k, n = 0;
          do {
              k = read(STDIN_FILENO, (char *)buf + n, sizeof buf - n);
          } while (k > 0 && (n += k) > 31);
              prev = mask;
          }
      }
      words += !(prev >> 31);
      printf("%llu %llu %llu\n", lines, words / 2, bytes);
      return 0;
  }

Post by PaulHoule » Thu, Jun 20, 2024, 6:09 PM UTC

rhelz wrote: post #62

moody__ wrote: post #32

The "asynchronous state machine" name here is a bit strange, when searching for this term used elsewhere I couldn't find any formal definition what it is. Reading further in the README it looks like the author implies that it really just means a DFA? Not entirely sure. I'd also like to add the Plan 9 implementation[0], which also uses the properties of utf8 as part of its state machine and anecdotally has been quite…

"Asynchronous" isn't part of the name of some really cool state machine :-) Its just an adjective and means the same as when you put it in front of any other noun. A synchronous state machine is one where the incoming stream of events is always "in sync" with the state transitions, in the following sense: 1. When an event happens, the state machine can transition to the next state and perform any necessary actions be…