Wc2: Investigates optimizing 'wc', the Unix word count program • Hacker News Board

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

#91

Post by leni536 » Thu, Jun 20, 2024, 8:41 PM UTC

nitwit005 wrote: post #74

The primary reason their code is faster as they've made incorrect code that assumes you always have a UTF-8 locale. The normal isspace does not assume this: > The real programs spend most of their time in functions like mbrtowc() to parse multi-byte characters and iswspace() to test if they are spaces This will produce bad results in the real world. People have previously posted about bugs related to this on Hacker N…

It would be just as fast if it detected the locale correctly, and used the UTF8 state machine for the UTF8 locale only. Other locales could have their own state machines or just fall back to a generic implementation.

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

#92

Post by trealira » Thu, Jun 20, 2024, 8:42 PM UTC

NunoSempere wrote: post #60

From a previous project: https://nunosempere.com/blog/2023/09/15/wc/ that was looking not at speed, but at simplicity, here is a comparison of different historical versions of wc: --- The [version of wc.c]( https://git.nunosempere.com/personal/wc/src/branch/master/sr... ) in this repository sits at 44 lines. It decides to read from stdin if the number of arguments fed to it is otherwise zero, and uses the standard C…

There's another version from Unix V10: http://tuhs.org/cgi-bin/utree.pl?file=V10/cmd/wc.c

Also, from V8: https://www.tuhs.org/cgi-bin/utree.pl?file=V8/usr/src/cmd/wc...

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

#93

Post by drchickensalad » Thu, Jun 20, 2024, 9:02 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?

If you're like me, you need to stop thinking of it as "99% of call sites" and start thinking of it as "99% of iteration loops". I know it's super obvious on the face of it, but the implications is that most call sites can repeatedly fail but are totally overshadowed by insanely high frequency hot loops that it almost always predicts right (it's skewed, just like avg vs median)

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

#94

Post by GrantMoyer » Thu, Jun 20, 2024, 9:02 PM UTC

throwaway55533 wrote: post #61

GrantMoyer wrote: post #55

Earlier quoted context omitted.

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…

Ah. Is 8 bits really optimal? I don't know how many UTF space characters there are, I thought there were only a few. Why not a 16-bit lookup?

UTF-8 encoded codepoints can have an odd number of bytes, so processing a file 2 bytes at a time would be a little more complicated. Processing the file one codepoint at a time works because you can decode the UTF-8 stream into a stream of 32-bit codepoints before passing the codepoints to the lookup table. I suppose you could also transform from UTF-8 to UTF-16 before passing values to the lookup table.

Processing byte by byte isn't necessarily faster than processing codepoint by codepoint, or any other size. You'd need to measure performance empirically, and it probably depends on caches sizes and other factors. In theory, you could also process bit by bit — then you'd only need 32 2-element lookup tables — but that's unlikely to be efficient, since you'd need to do a lot of bit manipulation.

Edit: Upon inspection, the method I described doesn't appear to be the method used by the featured program. It still basically uses a lookup table for detecting space characters, byte by byte, but the states are not how I described. Instead of the states representing which byte of a UTF-8 encoded codepoint is being processed, and the word count being incremented upon certain transitions — a Mealy machine — the state represent the class of the codepoint last fully processed, and the count is always increased based on the current state (often by zero) — a Moore machine.

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

#95

Post by mywittyname » Thu, Jun 20, 2024, 9:10 PM UTC

GrantMoyer wrote: post #43

> 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…

Compilers was a graduate course at my school.

CS as a field has grown quite a lot over the years, and it seems that colleges are responding by pushing the more theoretical classes into grad school to make room for the more applied classes.

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

#96

Post by JackSlateur » Thu, Jun 20, 2024, 9:24 PM UTC

orf wrote: post #66

JackSlateur wrote: post #56

Reading the code to help me understand how things are I got the wc_lines from coreutils: https://github.com/coreutils/coreutils/blob/master/src/wc.c#... And I thought "damn, I understand nothing about the state-machine stuff, how did they made this faster ?" Truth is: they did not Of course, this is just the "count line" part. Other parts are indeed faster. Coreutils 9.4: 0.67 [jack:/tmp] /usr/bin/time -v wc -l debia…

Any notable difference if you pipe the file in, rather than read from disk? IO caches are a thing as well, don’t use the first measurement.

I've accounted for IO cache, the test is running from an in-memory dataset

After checking a bit more, wc2 is indeed faster than wc in a specific use case: counting characters. That is, transforming a sequence of one or multiple bytes into meaningful character (wc --chars somefile).

In wc, the related code is here: https://github.com/coreutils/coreutils/blob/master/src/wc.c#...

So in the end, wc uses the function while wc2 does not: https://en.cppreference.com/w/c/string/multibyte/mbrtoc32

Now, what I cannot tell : is wc2's code really comparable versus mbrtoc32 ? From a couple of tests, it works against ascii and utf8 dataset, but is that all ? Or are there edgecases cleverly handled by mbrtoc32 (with a performance cost) ?

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

#97

Post by kllrnohj » Thu, Jun 20, 2024, 9:56 PM UTC

jxndnxu wrote: post #81

loeg wrote: post #39

Earlier quoted context omitted.

Why is this better for wc, though? wc is not doing memory allocation in the hot loop.

Because classic wc is not iterating over every byte once, but multiple times. It's especially obvious in the Unicode case where it first takes 1-4 bytes to get a Unicode character and then checks this character with another function to see if it's whitespace But even with with naive ASCII approach, if you don't hand roll a state machine you are checking multiple conditions on each byte (is it a space and am I leaving…

Those 1-4 bytes are sitting in a register the entire time and thus basically free to read as often as you want, though.

An actual sampled profile showing the two approaches would be interesting. Naively it seems like it's just because it has faster UTF8 handling and nothing to do with being a state machine exactly

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

#98

Post by rhelz » Thu, Jun 20, 2024, 10:03 PM UTC

PaulHoule wrote: post #69

rhelz wrote: post #62

Earlier quoted context omitted.

"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…

As I see it, state machines are particularly good for expressing logic in asynchronous systems. For instance in the late 1980s I wrote assembly language XMODEM implementations for the 6809 and the 80286 and since that kind of code is interrupt drive it is efficient to make a state machine that processes one character at a time. Today when you use async/await the compiler converts your code, loops and all, into a stat…

// 6809

The good old days :-)

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

#99

Post by FroshKiller » Thu, Jun 20, 2024, 10:10 PM UTC

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'm a little surprised to hear this. Writing a state machine to simulate an alarm clock used to be an introductory project for first-year computer science undergraduates.

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

#100

Post by rhelz » Thu, Jun 20, 2024, 10:16 PM UTC

moody__ wrote: post #72

rhelz wrote: post #62

Earlier quoted context omitted.

"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…

I was not treating "asynchronous state machine" as a noun, even if taken as a generic adjective it doesn't make sense in this context. What "other things" is this wc2.c doing while the state machine is churning? There is no multi threading or multi processing going on here. So I find it hard to believe that this use of "asynchronous" is inside of what I would generally see it used as. As such I thought perhaps it ref…

// What "other things" is this wc2.c doing...

AFAICT, wc2.c isn't written to be an asynchronous state machine. It doesn't ever seem to transfer the control to any other place.

// So I find it hard to believe that this use of "asynchronous" is inside of what I would generally see it used as

Yeah, you are legitimately confused. The post talks about asynchronous state machines, but w2c.c isn't an example of that. I'm sure this gave you a severe case of WTF?!??

// thought perhaps it referred to a specific methodology for designing the code

It does---that's exactly what it is, a programming methodolog, or perhaps better put, a design pattern. But w2c.c isn't an example of code written using that methodology. Again, you are legitimately confused here, because the post talks about something and w2c.c isn't that.

Do you know python? If you google for "asynchronous programming in python" you'll get all kinds of blog posts and youtube videos which explain the technique.