> Brute Force was surprisingly performant, enough that picking a string searching algorithm becomes an engineering tradeoff. It found a sentence fragment at the end of Moby Dick within 8ms, 7 times slower than Boyer-Moore.
I think that line of thinking is actually symptomatic of producing the kind of software that eats up our present day powerhouses and makes them dog slow.
> "Even long-winded users won't write Moby Dick into your <textarea>"
Which has most cases already much longer than those where the setup costs of BM are larger than the gain if the match is found on average halfway in to the text.
Typically you hit that point when the 'haystack' is about 2,000 characters and the 'needle' is longer than about 4 to 5, longer 'needles' or longer 'haystacks' would increase the advantage.
So the HTTP header one is probably one situation where you'd be quicker using brute force but in those other two instances it is very well possible that BM is already faster.
This assumes that you are going to the trouble of initializing your skip table once and re-using it. Now you have state to maintain beyond the life of the function call, or else your performance is slower than brute-force. That, in addition to probably needing to write the function in the first place, means you've got all sorts of bugs to find and fix.
And anyway, what are you doing searching HTTP headers in anything more than a one-off script? More likely, you are parsing the whole header and sticking it in a hash table. So, not only aren't you searching, but even if you were, that's not the hard part. And even that is dwarfed by the application that's going to service the HTTP request. (Unless you are Google, in which case you don't need my advice.)
Searching HTTP headers is not your bottleneck. Use your language's built in string search. Premature optimization makes code slower.
I really haven't seen this problem, like, ever. All coder's are vastly more likely to preoptimise the hell out of everything, and we end up with the opposite problem - thousands of hours of wasted programmer time won't even reach 1 saved hour of user time. Bear in mind as well that the actual speed of execution isn't always the main cause of perceived slowness - if something runs 10 times as slowly, but runs in the background and never causes the user to wait, it's actually running infinitely faster, from the users perspective.
A much better solution is to write things in the easiest way for coders to change - that way, when something is found to be the actual cause of slowness, anyone can easily go in and optimise it or move it to a background thread. Optimising EVERYTHING in the hopes of obtaining speed is a fool's errand - due to the 90/10 rule, 90% of the code you optimise will never be the bottleneck.
I'm not arguing for anything, I'm stating a fact. Users choose more but slower features or in web app terms business people choose more but slower features and throw more hardware at it.
I'd prefer it your way too. One other thing, we're assuming good programmers and that's not something I'd bet on at most places.
Comments
> Brute Force was surprisingly performant, enough that picking a string searching algorithm becomes an engineering tradeoff. It found a sentence fragment at the end of Moby Dick within 8ms, 7 times slower than Boyer-Moore.
I think that line of thinking is actually symptomatic of producing the kind of software that eats up our present day powerhouses and makes them dog slow.
His next line was "But most of us aren't searching Moby Dick, but rather a HTTP header, some user input, or a paragraph of a document."
A HTTP header is several orders of magnitude shorter than Moby Dick.
Followed by:
> "Even long-winded users won't write Moby Dick into your <textarea>"
Which has most cases already much longer than those where the setup costs of BM are larger than the gain if the match is found on average halfway in to the text.
Typically you hit that point when the 'haystack' is about 2,000 characters and the 'needle' is longer than about 4 to 5, longer 'needles' or longer 'haystacks' would increase the advantage.
So the HTTP header one is probably one situation where you'd be quicker using brute force but in those other two instances it is very well possible that BM is already faster.
The chances of analyzing just one HTTP header in an application are almost nil. Use a boyer-moore skip table.
This assumes that you are going to the trouble of initializing your skip table once and re-using it. Now you have state to maintain beyond the life of the function call, or else your performance is slower than brute-force. That, in addition to probably needing to write the function in the first place, means you've got all sorts of bugs to find and fix.
And anyway, what are you doing searching HTTP headers in anything more than a one-off script? More likely, you are parsing the whole header and sticking it in a hash table. So, not only aren't you searching, but even if you were, that's not the hard part. And even that is dwarfed by the application that's going to service the HTTP request. (Unless you are Google, in which case you don't need my advice.)
Searching HTTP headers is not your bottleneck. Use your language's built in string search. Premature optimization makes code slower.
it's a trade off against programmer time. For the most part users have preferred more but slower features rather than fewer but faster features.
I happen to agree with your preference, but most people don't seem to.
The error in this argument is that often 1 hour of programmer time saved can easily translate into thousands of hours of wasted user time.
I really haven't seen this problem, like, ever. All coder's are vastly more likely to preoptimise the hell out of everything, and we end up with the opposite problem - thousands of hours of wasted programmer time won't even reach 1 saved hour of user time. Bear in mind as well that the actual speed of execution isn't always the main cause of perceived slowness - if something runs 10 times as slowly, but runs in the background and never causes the user to wait, it's actually running infinitely faster, from the users perspective.
A much better solution is to write things in the easiest way for coders to change - that way, when something is found to be the actual cause of slowness, anyone can easily go in and optimise it or move it to a background thread. Optimising EVERYTHING in the hopes of obtaining speed is a fool's errand - due to the 90/10 rule, 90% of the code you optimise will never be the bottleneck.
-- Ayjay on Fedang/coding
I'm not arguing for anything, I'm stating a fact. Users choose more but slower features or in web app terms business people choose more but slower features and throw more hardware at it.
I'd prefer it your way too. One other thing, we're assuming good programmers and that's not something I'd bet on at most places.