Hacker News Reader

> 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'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.

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

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?

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.

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 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.