I tested string searching algorithms a few years ago[0][1], and 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. But most of us aren't searching Moby Dick, but rather a HTTP header, some user input, or a paragraph of a document. Even long-winded users won't write Moby Dick into your <textarea>. Most languages and libraries use brute force for this reason - initializing and using Boyer-Moore may be slower than brute-forcing the text. Sometimes "practically nothing" is just a brute-force search.
But Boyer-Moore is the perfect choice for Grep! The likely inputs on Unix are all huge: log files, entire directory trees, output pipes from loud programs, etc. The cost of initializing a small skip table is overwhelmed by the cost of I/O and the potential volume of text. It's not surprising that they've gone to some lengths to optimize the core inner loops and the I/O in that context.
> 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.
Or rather, compared to a server log file that hasn't been properly rotated. I wrote a program a while back to incrementally parse a daily log file which was never rotated. It got say that it would take twenty minutes for for the program to just skip the lines that had been parsed previously. When those who had the power to do so started rotating the file, things speed up tremendously.
Sparing that, why not use fseek() and do a binary search to get to where you wanted to go? Even better, save the prior offset somewhere and jump there immediately on T+1?
That, I should have done. I thought to save the number of lines previously read so that I could skip them; I don't know why it didn't occur to me to just save the whole damn offset.
I used this trick the other day -- compute byte range partitions on a large file and use fseek when processing each. Is there a standard unix program that can output an arbitrary byte range from a seekable input? At first blush dd(1) looked like the ticket, but block-oriented operation means extra invocations to deal with a byte range that's not necessarily block-aligned.
I thought this sort of thing was common knowledge? Searching and sorting a certain number of items under a threshold is fastest through brute force. The problem is figuring out what that threshold might be and then have the sorting and searching programs make use of it.
I remember this topic being discussed back in undergrad.
>> initializing and using Boyer-Moore may be slower than brute-forcing the text. Sometimes "practically nothing" is just a brute-force search.
> and you are basing this claim on…?
Think of it as an up-front cost that you expend before doing any actual work. So BM is slower in some cases, and faster in others. In most short cases the cost of setting up outweighs the advantages of the more complex algorithm and then you're better off to brute-force it.
The Moby-Dick example, however is not such a case.
Just like it takes longer to prepare an offset press to make a single copy of a page compared to just slapping it in to the photo-copier. But if you need a million copies, you can't beat (rotary) offset.
edit: I've re-constructed the original comment this replied to because I'm not happy about the recent trend in comment deletions (see below), that's the fourth time in a few days that I come across this. To the author of the parent of this comment (you know who you are), why did you delete your comment after receiving 3 serious replies?
Because he was probably downmodded (appropriately) for his comment, and considered it an embarrassment.
I'm not fond of such deletions, but I think it's good for people to be able to retract their statements when they realize they don't reflect well on themselves.
Perhaps a better solution would be to allow the original comment to be "retracted" such that the author information is removed but the comment remains, so people can still understand the thread of the conversation.
Retracting just the owner means you basically allow anonymous posting (except the mods still know who wrote it, and anyone who read it before the username got wiped). That opens up a whole new can of worms.
The fact that computers use instructions in our universe?
Seriously, if you don't understand what he's basing his claim on, it's because you don't understand the Boyer-Moore algorithm. If you know how Boyer-Moore works, the reason is obvious. Instead of snarkily replying, why don't you take the same amount of time to read the wikipedia article on Boyer-Moore and see why brute force may be faster in some cases.
(Since you've already shown yourself to be lazy, however, I'll explain it: Boyer-Moore constructs two alphabet-sized integer arrays based on the "needle" you're looking for; if your haystack is smaller than twice your alphabet size, and it frequently is, then Boyer-Moore is practically guaranteed to take more time than brute force.)
Searching for "b" in "ab". Just two comparisons, compared to allocating, zeroing, and initializing a lookup table, and then doing a brute force search anyways. There's a fuzzy point where one becomes better than the other. Implementations written to be fast may brute-force length=1 strings, and implementations written for simplicity may not.
Comments
I tested string searching algorithms a few years ago[0][1], and 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. But most of us aren't searching Moby Dick, but rather a HTTP header, some user input, or a paragraph of a document. Even long-winded users won't write Moby Dick into your <textarea>. Most languages and libraries use brute force for this reason - initializing and using Boyer-Moore may be slower than brute-forcing the text. Sometimes "practically nothing" is just a brute-force search.
But Boyer-Moore is the perfect choice for Grep! The likely inputs on Unix are all huge: log files, entire directory trees, output pipes from loud programs, etc. The cost of initializing a small skip table is overwhelmed by the cost of I/O and the potential volume of text. It's not surprising that they've gone to some lengths to optimize the core inner loops and the I/O in that context.
[0] http://www.jakevoytko.com/blog/2007/12/11/fun-with-string-se... I've declared bankruptcy on broken TeX and code examples... WordPress mangles them every few updates.
[1] http://www.lysium.de/blog/index.php?/archives/201-Fun-With-S... A few improvements to the code in my post
> 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.
Moby Dick is very short compared to a normal server logfile.
Or rather, compared to a server log file that hasn't been properly rotated. I wrote a program a while back to incrementally parse a daily log file which was never rotated. It got say that it would take twenty minutes for for the program to just skip the lines that had been parsed previously. When those who had the power to do so started rotating the file, things speed up tremendously.
Why didn't you split it?
Sparing that, why not use fseek() and do a binary search to get to where you wanted to go? Even better, save the prior offset somewhere and jump there immediately on T+1?
That, I should have done. I thought to save the number of lines previously read so that I could skip them; I don't know why it didn't occur to me to just save the whole damn offset.
I used this trick the other day -- compute byte range partitions on a large file and use fseek when processing each. Is there a standard unix program that can output an arbitrary byte range from a seekable input? At first blush dd(1) looked like the ticket, but block-oriented operation means extra invocations to deal with a byte range that's not necessarily block-aligned.
tail -c offset [input] | head -c length
will do the job.
You can set dd's "bs" parameter to 1, then seek, skip & count are all in terms of bytes.
I couldn't, I didn't have control over the file.
I thought this sort of thing was common knowledge? Searching and sorting a certain number of items under a threshold is fastest through brute force. The problem is figuring out what that threshold might be and then have the sorting and searching programs make use of it.
I remember this topic being discussed back in undergrad.
[deleted]
> --somebody-- wrote:
>> initializing and using Boyer-Moore may be slower than brute-forcing the text. Sometimes "practically nothing" is just a brute-force search.
> and you are basing this claim on…?
Think of it as an up-front cost that you expend before doing any actual work. So BM is slower in some cases, and faster in others. In most short cases the cost of setting up outweighs the advantages of the more complex algorithm and then you're better off to brute-force it.
The Moby-Dick example, however is not such a case.
Just like it takes longer to prepare an offset press to make a single copy of a page compared to just slapping it in to the photo-copier. But if you need a million copies, you can't beat (rotary) offset.
edit: I've re-constructed the original comment this replied to because I'm not happy about the recent trend in comment deletions (see below), that's the fourth time in a few days that I come across this. To the author of the parent of this comment (you know who you are), why did you delete your comment after receiving 3 serious replies?
Because he was probably downmodded (appropriately) for his comment, and considered it an embarrassment.
I'm not fond of such deletions, but I think it's good for people to be able to retract their statements when they realize they don't reflect well on themselves.
Perhaps a better solution would be to allow the original comment to be "retracted" such that the author information is removed but the comment remains, so people can still understand the thread of the conversation.
Retracting just the owner means you basically allow anonymous posting (except the mods still know who wrote it, and anyone who read it before the username got wiped). That opens up a whole new can of worms.
People can create an account with just a username and password; we're already effectively allowing anonymous posting.
Still, creating a throwaway account does present a certain barrier. In any case, this has been discussed to death previously.
The fact that computers use instructions in our universe?
Seriously, if you don't understand what he's basing his claim on, it's because you don't understand the Boyer-Moore algorithm. If you know how Boyer-Moore works, the reason is obvious. Instead of snarkily replying, why don't you take the same amount of time to read the wikipedia article on Boyer-Moore and see why brute force may be faster in some cases.
(Since you've already shown yourself to be lazy, however, I'll explain it: Boyer-Moore constructs two alphabet-sized integer arrays based on the "needle" you're looking for; if your haystack is smaller than twice your alphabet size, and it frequently is, then Boyer-Moore is practically guaranteed to take more time than brute force.)
Searching for "b" in "ab". Just two comparisons, compared to allocating, zeroing, and initializing a lookup table, and then doing a brute force search anyways. There's a fuzzy point where one becomes better than the other. Implementations written to be fast may brute-force length=1 strings, and implementations written for simplicity may not.