jxndnxu
Re:Wc2: Investigates optimizing 'wc', the Unix word count program
on Thursday June 20, 2024 @03:44PM (#40742509)
How would if have helped? You either design a DFA by hand or use a compiled from a regular language
Re:Wc2: Investigates optimizing 'wc', the Unix word count program
on Thursday June 20, 2024 @03:41PM (#40742477)
You have answered your question yourself: your algorithm looks at each byte twice, not once
It's even more obvious in the UTF case where the classic implementation first looks at 1-4 byte to parse a character and only then checks if it's a space
Re:Wc2: Investigates optimizing 'wc', the Unix word count program
on Thursday June 20, 2024 @03:37PM (#40742436)
My understanding of the article's use of scalable was "fixed overhead more or less regardless of the complexity of the state machine and input" not "fastest implementation available"
Re:Wc2: Investigates optimizing 'wc', the Unix word count program
on Thursday June 20, 2024 @03:33PM (#40742399)
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 a word etc)
Using a dfa has fixed compute per byte