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

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

#111

Post by [deleted] » Fri, Jun 21, 2024, 3:20 AM UTC

tialaramex wrote: post #51

munchler wrote: post #38

Earlier quoted context omitted.

> Just remember, if you're ever debugging something and some values in a Class/Object/Group of them are set and others are unset the state machine avoids that issue. Better yet, switch to a language that supports discriminated unions to avoid invalid state without having to write a low-level state machine. Each case in the union represents one of the valid states of the type. This is one of the many benefits of funct…

This comes down to "Make Invalid States Unrepresentable" Notably Go's choice here is instead "Make Representable States Valid". So for example in Go it's not possible for a type not to have a default value - every type must have a value you get by default, you could name this unwanted default value FUCK_OFF or DO_NOT_USE if you like, but in a larger system (where Go is supposed to thrive) you can be certain you'll fi…

[deleted]

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

#112

Post by aftbit » Fri, Jun 21, 2024, 3:22 AM UTC

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!

Right, but are its labels of the state actually incorrect? I don't know well enough how to check.

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

#113

Post by kelnos » Fri, Jun 21, 2024, 3:23 AM UTC

ekidd wrote: post #79

tialaramex wrote: post #51

Earlier quoted context omitted.

This comes down to "Make Invalid States Unrepresentable" Notably Go's choice here is instead "Make Representable States Valid". So for example in Go it's not possible for a type not to have a default value - every type must have a value you get by default, you could name this unwanted default value FUCK_OFF or DO_NOT_USE if you like, but in a larger system (where Go is supposed to thrive) you can be certain you'll fi…

> This is one of the few things the C++ type system almost gets right. You really can say for your C++ type no, it doesn't have a default. Rust does even better here, I think, for fairly subtle reasons: - Exceptions are replaced by Result, with explicitly-marked return points. They're far less magic. ("panic!" is still magic, but it's allowed to be a call to "abort", so you only use it when the world is burning.) - "…

> Default initialization only works if you implement "Default".

And -- and I think this is important -- even then, you have to explicitly assign the default value[0]. You won't just somehow magically get a default value.

[0] E.g.:

    let foo: SomeType = Default::default();

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

#114

Post by stkdump » Fri, Jun 21, 2024, 3:38 AM UTC

leni536 wrote: post #91

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.

I'm wondering if you could easily build the state machine quickly at startup time. Unless it is a multi byte encoding it should be trivial.

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

#115

Post by stkdump » Fri, Jun 21, 2024, 3:47 AM UTC

bruce343434 wrote: post #19

What about this is "asynchronous"?

I guess since state is fully encoded inside a single state variable and of course the output counts, it would be trivially simple to switch between multiple input streams and incrementally count words in each of them as new data arrives.

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

#116

Post by stkdump » Fri, Jun 21, 2024, 3:52 AM UTC

Dylan16807 wrote: post #109

fragmede wrote: post #106

In the bringing a tank to a knife fight kind of way, could this be optimized to run on a GPU? Load the contents then do an "and" across the whole contents in parallel, and then sum the whitespaces?

These benchmarks are on 92 million byte files so we're into the range where bringing a tank is fair (and worth the startup cost).

I doubt that you can make it faster on the GPU than on CPU when utilizing SIMD, reason being that you are actually doing something close to trivial upon looking at each byte in sequence. So you transfer it from CPU memory to GPU memory in order to do almost nothing with it.

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

#117

Post by ashvardanian » Fri, Jun 21, 2024, 3:56 AM UTC

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

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

#118

Post by zzo38computer » Fri, Jun 21, 2024, 4:10 AM UTC

scottlamb wrote: post #88

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…

Are we looking at the same thread? Folks there seem to be complaining the old interfaces are anything from outdated to confusing to simply wrong, and I agree. I think it's totally reasonable for a program designed in 2024 to say it only supports ASCII and UTF-8 encodings. Whether/how it should support the full spectrum of Unicode definitions of characters/graphemes/... is more interesting. For a lot of backend code (…

> I think it's totally reasonable for a program designed in 2024 to say it only supports ASCII and UTF-8 encodings.

I think that it should depends on the program; that might be reasonable for some programs but in a lot of cases I think that it won't be reasonable. (Your explanation includes some of the examples, although not all of them.)

Sometimes, it is most helpful to support only ASCII (although non-ASCII bytes might still be supported, even without needing special processing to handle them; in some cases this may effectively allow other ASCII-compatible encodings as well such as EUC-JP).

Sometimes, a program should not need to deal with character encoding at all.

Sometimes, it makes sense to deal with whatever character encodings are used in the file formats the program is designed to handle.

Sometimes, it makes sense to support multiple character encodings, with or without conversion (depending on what is being done with them).

Even if a program does only support ASCII and UTF-8 encodings, then depending on what it does with them, mentioning ASCII might be unnecessary since UTF-8 is a superset of ASCII anyways.

But unfortunately many programs use UTF-8 (or other encodings, but mostly UTF-8) where it is inappropriate to do so, which can result in many problems including inefficiency.

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

#119

Post by Dylan16807 » Fri, Jun 21, 2024, 4:31 AM UTC

stkdump wrote: post #116

Dylan16807 wrote: post #109

Earlier quoted context omitted.

These benchmarks are on 92 million byte files so we're into the range where bringing a tank is fair (and worth the startup cost).

I doubt that you can make it faster on the GPU than on CPU when utilizing SIMD, reason being that you are actually doing something close to trivial upon looking at each byte in sequence. So you transfer it from CPU memory to GPU memory in order to do almost nothing with it.

It's only at a limit like that if you don't parallelize. And sure you could use more cores, but you can go a lot faster on 20% of a GPU than on 20% of your CPU cores.

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

#120

Post by _lvbh » Fri, Jun 21, 2024, 4:57 AM UTC

joe_the_user wrote: post #102

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…

Hmm, A project with all code working with special magic reminds me of another project that some attention a while back (XZ lib - supposed improvements with packages containing clever system back doors). Edit: The code is likely harmless but the more opaqueness is in a system, the easier it is for malevolent opaqueness to hide.

That is not what they mean by “magic”. The “magic” in xz is the complexity in the build system. Here, the “magic” are seemingly arbitrary numbers that improve performance. The reason they’re magic is because we don’t know why they were chosen. The code itself is obvious and not magic.