Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

github.com

Post reply on HN
Print view View original

41–50 of 157 posts

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

#41

Post by SoftTalker »

YesThatTom2 wrote: post #6

I love state machines and every time I use one my workers think I invented it because they’ve never seen them before. The data for state machine in this article might be best prepared by generating it from a program. That generator program doesn’t need to care (too much) about performance since it is run during the build process. I like the idea of doing a lot of work now to save time in the future.

I agree, and I raised an eyebrow at the "The algorithm is known as an "asynchronous state-machine parser". It's a technique for parsing that you don't learn in college."

I certainly learned about state machines in college. Not sure we ever studied this particular algorithm but the concept was definitely covered.

And I also agree that when you are dealing with a known, finite set of values, pre-computing lookup or index tables for techniques like this can be a big win.

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

#42

Post by loeg »

veltas wrote: post #27
mananaysiempre wrote: post #18

> This is analogous to NFA and DFA regular-expressions. If you use the NFA approach, you need to buffer the entire chunk of data, so that the regex can backtrack. Using the DFA approach, input can be provided as a stream Sorry, no, this is completely wrong. There are other reasons NFAs or DFAs might be preferable, and there are other performance considerations as far as backtracking is concerned, but NFA implementati…

How do you implement a non-backtracking NFA other than converting it to a DFA?

As GP said, you can keep a bag of current states.

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

#43

Post by GrantMoyer »

> The algorithm is known as an "asynchronous state-machine parser". It's a technique for parsing that you don't learn in college.

The mapping from regular and context free languages to state machines and their table-based implementations was covered in depth in the Compilers course I took. A table based state machine is literally the textbook algorithm for parsing these classes of languages, and implementing them has been almost entirely automated by tools like Flex and Bison since the 80s.

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

#44

Post by arp242 »

roywiggins wrote: post #30
aftbit wrote: post #23

Earlier quoted context omitted.

Why? Because it's wrong? If it were correct, wouldn't it be useful?

This is a bit like presenting someone with a raw egg on a plate and saying "ah, but if I had cooked it, might it not be a tasty omelet?" Correctness is the hard part!

More like a covered plate you're expected to eat without looking. "This may be an amazing omelet and you will have a great meal, or you may eat a raw egg, get salmonella, and be sick for a week. It's probably an omelet, but I'm not sure, so you'll probably be fine. Enjoy!"

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

#45

Post by Joker_vD »

thequux wrote: post #7
im3w1l wrote: post #3

I'm surprised there is no mention of simd. Like I'm sure this is "fast enough" but if you want to make a really fast wc for fun wouldn't that be a natural direction?

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…

SIMD-based reimplementations of wc already exist, e.g. this [0] one, and it's rather straightforward.

[0] https://github.com/expr-fi/fastlwc

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

#46

Post by canucker2016 »

markstos wrote: post #5

Was this ever submitted an update to the `wc` shipped on systems?

I doubt it - from the project's readme page:

"...Now the real wc works with a lot more character-sets, and we don't do that. But by implementing UTF-8, we've shown that it's possible, and that the speed for any character-set is the same."

Looking at the command line options for wc2.c and comparing to the FSF wc man page, it looks like there are some missing/unsupported options in wc2.c as well.

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

#47

Post by mananaysiempre »

veltas wrote: post #27
mananaysiempre wrote: post #18

> This is analogous to NFA and DFA regular-expressions. If you use the NFA approach, you need to buffer the entire chunk of data, so that the regex can backtrack. Using the DFA approach, input can be provided as a stream Sorry, no, this is completely wrong. There are other reasons NFAs or DFAs might be preferable, and there are other performance considerations as far as backtracking is concerned, but NFA implementati…

How do you implement a non-backtracking NFA other than converting it to a DFA?

Assuming each state transition consumes a character (“epsilon-free NFA”), just follow the definition. Before each step, you have a list of NFA states you might be in, initially containing only the start state. During each step, go through each state on that list and enter any acceptable successors into a new one. Deduplicate and repeat.

This is (potentially super)linear in the number of states, but that doesn’t preclude it from being linear in the input length. In particular, even though it’s essentially a bad lazy implementation of standard NFA-to-DFA conversion, you’re avoiding the exponential state blowup you get in the eager version. (I say it’s a bad lazy implementation because a proper one would memoize; that, however, would bring the worst-case blowup back.) I think that, in addition to the fact that people do actually do this kind of thing in production implementations, qualifies it as a separate approach.

If your NFA does have epsilon-transitions—like, say, the NFAs obtained from the textbook Thompson regexp-to-NFA construction—you can either use a different (Glushkov) regexp-to-NFA construction[1], eliminate those transitions as a separate pass[2], or adjust the algorithm above to eliminate duplicate NFA states on the fly[3].

[1]: https://en.wikipedia.org/wiki/Glushkov%27s_construction_algo...

[2]: https://news.ycombinator.com/item?id=19272990

[3]: https://swtch.com/~rsc/regexp/regexp2.html

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

#48

Post by laurent_du »

roelschroeven wrote: post #34
bruce343434 wrote: post #19

What about this is "asynchronous"?

I don't get that either. It feels like they compare the asynchronous-ness of their algorithm to Nginx being asynchronous ("asynchronous web-servers like Nginx use a state-machine parser. They parse the bytes as they arrive, and discard them."), but I don't see how that relates. The way web-servers handle requests (multiple threads vs multiple processes vs asynchronous event-driven in one thread) is completely orthogo…

My understanding was that scalability came from the removal of memory buffers.

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

#49

Post by anon1040 »

canucker2016 wrote: post #46
markstos wrote: post #5

Was this ever submitted an update to the `wc` shipped on systems?

I doubt it - from the project's readme page: "...Now the real wc works with a lot more character-sets, and we don't do that. But by implementing UTF-8, we've shown that it's possible, and that the speed for any character-set is the same." Looking at the command line options for wc2.c and comparing to the FSF wc man page, it looks like there are some missing/unsupported options in wc2.c as well.

> ...the real wc works with a lot more character-sets...

This should read: the real wc works with a lot more character _encodings_

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

#50

Post by sebastianmestre »

jmholla wrote: post #8

> No, you aren't suppose to be able to see how the word-count works by looking at this code. The complexity happens elsewhere, setting up the state-machine. This is like most of the reason I opened this article. I wish they'd spend more time talking about this. In fact, most of the README covers details that are important, but, irrelevant to their algorithmic improvements. Maybe they expect you to open up the code, b…

Yeah, Sean Barrett has a good writeup about them and optimizing them for branch-prediction, etc

It's framed in the context of programming-language tokenization, but the principles are the same.

https://nothings.org/computer/lexing.html

Post reply on HN