Substring searching in sub-linear time | Hacker News Reader

Substring searching in sub-linear time

blog.phusion.nl

52 pointsFooBarWidget10 comments

Actually, Python does use a Boyer-Moore-Horspool variant internally for substring matching (I'm not sure about Ruby, though). See:

http://effbot.org/zone/stringlib.htm

Here's a link to the file in the Python SVN repo:

http://svn.python.org/view/python/trunk/Objects/stringlib/fa...

Ruby 1.8.7 does too. Not sure about Oniguruma in 1.9

https://github.com/ruby/ruby/blob/ruby_1_8_7/regex.c#L2751-2...

EDIT: Looks like 1.9 does too:

https://github.com/ruby/ruby/blob/ruby_1_9_2/regint.h#L281

Luckily, perl will optimize some constant regular expressions to use Boyer-Moore.

For example, if you do:

  $str =~ /foobarbaz/;

perl sees what you want and uses Boyer-Moore instead of a normal regex state machine.

This, and many other optimizations, is what 20 years of language development gets you.

But still no JIT and no threads that don't take 20 seconds to spawn on a moderately sized app. :(

Actually, in all seriousness, deeply ingrained problems is also what 20 years of development gets you. That's why it's still important to have new up and coming languages getting created. Unfortunately there is no language so perfect it can escape this fate, and I wouldn't say Perl's problems stand out particularly on that front. It's a rare language that is even around to be criticized 20 years later, they all have their issues.

Using an algorithm with a better average case and very bad worst case instead of an agorithm that always executes in linear time is pretty common - for example, in grep:

http://ridiculousfish.com/blog/archives/2006/05/30/old-age-a...

Makes sense, as long as you and the people using the code know the tradeoffs involved.

(I posted this comment on the blog as well)

The poor performance of Turbo Boyer-Moore might be due to cache locality issues. If you jump from checking the end of the needle to the start of the needle, then there's a good chance that you'll cause a cache miss - which has the same cost as several hundred instructions. A modern Turbo Boyer-Moore would probably work backwards within the same cache line before jumping to the start of the needle. A couple of carefully chosen cache-preload instructions could make Turbo Boyer-Moore. For a good overview of cache effects, google "gallery of processor cache effects".

This is a plausible and knowledgeable-sounding argument; its only flaw is that it not true.

The only relevant 'several hundred instructions' cache miss on a Core 2 Duo is a L2 miss ("Last Level Cache" miss). The hardware pre-fetcher will pick up accesses to the data stream after the first 1-2 misses. No amount of minor local jumping around in Turbo-BM is going to affect this.

Thanks!

See also http://news.ycombinator.com/item?id=1626305 and http://news.ycombinator.com/item?id=466845 and I was about to link to the rediculous fish post, but I see zdw beat me to it.

Reply on news.ycombinator.com