The target audience, Unix graybeards programming shell scripts using commands like wc, is extremely hard to convince to use new tools. If you don't integrate these optimizations into, say, the GNU Core Utils wc program, the impact will be nil.
Wc2: Investigates optimizing 'wc', the Unix word count program
131–140 of 157 posts
Re: Wc2: Investigates optimizing 'wc', the Unix word count program
#132Earlier quoted context omitted.
I've read recently (here on HN) that branch predictors are right 99% if the time. Is that inaccurate?
That's an over-generalization. Only branches that capture exceptional events, e.g. error checks, show 99% hit rate. Branches that are part of an algorithm are driven by the data you feed to them. For example in a classical binary search, the prediction is right only 50% of the time.
But there's an overall loop which branches backward to the same spot, regardless whether the iteration went left or right. At least that's predictable.
If we have an instruction that will conditionally load one of two pointers from memory, the left or right traversal can be made branch-free.
The only reason we need to switch between two code paths in the binary tree descent is that we have two different pieces of code for loading the left or right pointer to the different offsets used in the load instruction.
If we use a two element array for left and right, the indices [0] and [1] select between them. We make the comparison condition calculate a 0 or 1 result and use it as an index.
Re: Wc2: Investigates optimizing 'wc', the Unix word count program
#133Earlier quoted context omitted.
// 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 su…
Why would the author of this repository make "wc2 - asynchronous state machine parsing" his header of his README if indeed wc2 was not by his own definition an "asynchronous state machine"? I ask you to consider what is more likely: that your blanket definition of asynchronous is incorrect as applied here or the author is just fucking with us by adding random words as the description of his project.
You'll have to ask him.
Re: Wc2: Investigates optimizing 'wc', the Unix word count program
#134I wrote a clean C++ version of `wc` for fun, and successfully beat the system version by 10-20% iirc. My goal was to make the code much more readable than the GNU/C version, which is a big spaghetti loop, while maintaining the same semantics (ie. return the same counts). Blog posts: https://bytepawn.com/tag/wc.html Code: https://github.com/mtrencseni/wcpp/
A "word" counter in C++ (not really, but kind of)
std::cout (std::cin), std::istream_iterator()) And I guess you could get "character" count using istreambuf_iterator.
Don't do this :-) (Though I've used it in a pinch)
Re: Wc2: Investigates optimizing 'wc', the Unix word count program
#135I wrote a clean C++ version of `wc` for fun, and successfully beat the system version by 10-20% iirc. My goal was to make the code much more readable than the GNU/C version, which is a big spaghetti loop, while maintaining the same semantics (ie. return the same counts). Blog posts: https://bytepawn.com/tag/wc.html Code: https://github.com/mtrencseni/wcpp/
A "word" counter in C++ (not really, but kind of) std::cout (std::cin), std::istream_iterator ()) And I guess you could get "character" count using istreambuf_iterator. Don't do this :-) (Though I've used it in a pinch)
Also, sorry for the typos... the character version is istreambuf_iterator also... whoops!
Re: Wc2: Investigates optimizing 'wc', the Unix word count program
#136Earlier quoted context omitted.
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
According to the authors it's also faster on files full of 'x' or ' ', so there must be more than just better unicode support.
Even something as simple as wc calling a libc function for parsing utf-8, that doesn't get inlined, would destroy its performance relative to anything optimized.
Personally, I'd expect SIMD to win over all of these. wc sounds like kind of challenge that's very easy to partition and process in chunks, though UTF-8 might ruin that.
Re: Wc2: Investigates optimizing 'wc', the Unix word count program
#137Earlier quoted context omitted.
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 precl…
Last time I implemented this myself I just computed the epsilon closure at each step.
Re: Wc2: Investigates optimizing 'wc', the Unix word count program
#138> 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…
Writing text and writing code are two distinct abilities. It is very rare the professional that possesses both.
[deleted]
Re: Wc2: Investigates optimizing 'wc', the Unix word count program
#139> 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…
Writing text and writing code are two distinct abilities. It is very rare the professional that possesses both.
That used to not be the case. Has something changed?
Re: Wc2: Investigates optimizing 'wc', the Unix word count program
#140Earlier quoted context omitted.
> 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.
That isn't relevant in the ASCII example, and the UTF-8 one uses a 256×256 table.
Half of all bytes are illegal ASCII though.