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

Post by tylerhou » Fri, Jun 21, 2024, 6:02 PM UTC

anamexis wrote: post #86

tylerhou wrote: post #58

Earlier quoted context omitted.

There are fewer branches but there is now a data dependency between loop iterations which makes each iteration slightly slower (maybe 1-2 cycles additional latency per iteration). Because newlines are relatively common and unpredictable a state machine is likely better. But on a long file with no new lines and no spaces the branching one should be slightly faster. (All reasoning from first principles; I have not done…

The README covers the exact case you describe - the `word.txt` benchmark is just a file with 93MB of the char `x`. The state machine is still faster in this case.

Post by trealira » Fri, Jun 21, 2024, 9:08 PM UTC

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

  state = OUT;
  nl = nw = nc = 0;
  while ((c = getchar()) != EOF) {
      ++nc;
      if (c == '\n')
          ++nl;
      if (isspace(c))
          state = OUT;
      else if (state == OUT) {
          state = IN;
          ++nw;
      }
  }

Post by bear8642 » Fri, Jun 21, 2024, 10:25 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…

Post by teo_zero » Sat, Jun 22, 2024, 5:15 AM UTC

samatman wrote: post #73

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…

> But I'm not sure why the table is 4×4. The fourth transition from every state is unreachable since the symbols are all in [0, 2]. I think the fourth transition represents illegal Unicode. From there it stays in the illegal state until it hits legal UTF-8, then goes back to counting.

Post by teo_zero » Sat, Jun 22, 2024, 7:11 AM UTC

ashvardanian wrote: post #117

btown wrote: post #65

State machines are great for complex situations, but when it comes to performance, it's not at all clear to me that they're the most scalable approach with modern systems. The data dependency between a loop iteration for each character might be pipelined really well when executed, and we can assume large enough L1/L2 cache for our lookup tables. But we're still using at least one lookup per character. Projects like h…

In the context of State Machines and Automatas - Intel HyperScan might be a better reference point. But the idea is the same. With a trivial PoC using Python wrappers over SIMD libraries one can get a 3x boost over the native `wc` CLI on a modern CPU, memory-mapping a very average SSD: https://github.com/ashvardanian/StringZilla/tree/main/cli