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

21–30 of 157 posts

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

#21

Post by roywiggins »

aargh_aargh wrote: post #14

I wanted to take a peek the state diagram (ASCII version). But I was feeling lazy, so apologies for having ChatGPT do the work for me. I wasn't going for correctness and didn't check it. If you're like me, here you go: https://dreampuf.github.io/GraphvizOnline/#digraph%20StateMa... digraph StateMachine { rankdir=LR; size="8,5"; node [shape = circle]; LookingForWord -> InsideWord [label="Non-space"]; LookingForWord ->…

Surely correctness is the most important thing? Anyone can produce an incorrect state diagram.

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

#22

Post by smaudet »

I was a bit surprised by the macos/linux speed differential here:

> The difference in macOS and Linux speed is actually the difference in clang and gcc speed. The LLVM clang compiler is doing better optimizations for x86 processors here.

I know GCC has been getting much, much more aggressive as of late, but there have been some complaints that it is now much, much less safe (checks intended for security getting optimized away, e.g.).

I wonder if you were to go back to 5 years ago, if you'd see the linux code was generally safer than the speedy osx llvm code...

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

#23

Post by aftbit »

bruce343434 wrote: post #15
aargh_aargh wrote: post #14

I wanted to take a peek the state diagram (ASCII version). But I was feeling lazy, so apologies for having ChatGPT do the work for me. I wasn't going for correctness and didn't check it. If you're like me, here you go: https://dreampuf.github.io/GraphvizOnline/#digraph%20StateMa... digraph StateMachine { rankdir=LR; size="8,5"; node [shape = circle]; LookingForWord -> InsideWord [label="Non-space"]; LookingForWord ->…

This is a useless contribution to the discussion, maybe even negative... Why didn't you check it at least before sharing?

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

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

#25

Post by zadokshi »

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…

> why this is better than just iterating over characters?

The explanation it provides regarding Apache vs Ngnix seemed to me to imply that Apache requires memory allocation to read headers into buffers and Ngnix uses a state machine to avoid memory allocation. Memory allocation is slower than most people realise.

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

#27

Post by veltas »

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?

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

#28

Post by kstrauser »

smaudet wrote: post #22

I was a bit surprised by the macos/linux speed differential here: > The difference in macOS and Linux speed is actually the difference in clang and gcc speed. The LLVM clang compiler is doing better optimizations for x86 processors here. I know GCC has been getting much, much more aggressive as of late, but there have been some complaints that it is now much, much less safe (checks intended for security getting optim…

I'd assume the difference between Linux's GNU and macOS's BSD implementations would be much more significant.

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

#29

Post by rep_movsd »

Remember "The Zen of Code Optimization" by Michael Abrash in the 90s?

This word count challenge was the first one he described. The table driven approach was discussed, but was not necessarily the fastest due to the large cache overflowing (on 90s processors) table needed.

I used the same example in a chapter I wrote for a C++ book

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

#30

Post by roywiggins »

aftbit wrote: post #23
bruce343434 wrote: post #15

Earlier quoted context omitted.

This is a useless contribution to the discussion, maybe even negative... Why didn't you check it at least before sharing?

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!
Post reply on HN