3 ms·

Substring searching in sub-linear time

52 points by FooBarWidget 16y ago

js2 16y ago
See also http://news.ycombinator.com/item?id=1626305 http://news.ycombinator.com/item?id=1626305 and http://news.ycombinator.com/item?id=466845 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.
zdw 16y ago
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-and-treachery/ 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.
amccollum 16y ago
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 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/fastsearch.h?revision=77470&view=markup http://svn.python.org/view/python/trunk/Objects/stringlib/fa...
- burke 16y ago
  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-2789 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 https://github.com/ruby/ruby/blob/ruby_1_9_2/regint.h#L281
rmah 16y ago
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.
- FooBarWidget 16y ago
  But still no JIT and no threads that don't take 20 seconds to spawn on a moderately sized app. :(
  - jerf 16y ago
    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.
twp 16y ago
(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".
- onan_barbarian 16y ago
  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.
  - twp 16y ago
    Thanks!

52 points by FooBarWidget 16y ago

js2 16y ago

See also http://news.ycombinator.com/item?id=1626305 http://news.ycombinator.com/item?id=1626305 and http://news.ycombinator.com/item?id=466845 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.

zdw 16y ago

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-and-treachery/ 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.

amccollum 16y ago

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 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/fastsearch.h?revision=77470&view=markup http://svn.python.org/view/python/trunk/Objects/stringlib/fa...

burke 16y ago
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-2789 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 https://github.com/ruby/ruby/blob/ruby_1_9_2/regint.h#L281

rmah 16y ago

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.

FooBarWidget 16y ago
But still no JIT and no threads that don't take 20 seconds to spawn on a moderately sized app. :(
- jerf 16y ago
  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.

twp 16y ago

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

onan_barbarian 16y ago
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.
- twp 16y ago
  Thanks!