Implement Rabin-Karp algorithm for String#rindex #3876

makenowjust · 2017-01-12T13:25:11Z

Reverse version of this.

Benchmark is here.

My result is:

$ crystal run --release rindex_bench.cr
For long string:
       rindex_old 258.31  (  3.87ms) (± 6.69%) 11.04× slower
rindex_rabin_karp   2.85k ( 350.8µs) (± 6.77%)       fastest
For short string:
       short_rindex_old   1.92M (520.84ns) (± 6.08%)  2.66× slower
short_rindex_rabin_karp   5.11M (195.87ns) (± 8.64%)       fastest

(I recommend you run this benchmark on your environment ;)

drhuffman12 · 2017-01-12T13:40:48Z

Is it faster for short and long strings?

makenowjust · 2017-01-12T13:46:21Z

Old implementation is to scan string from head to end, and short string benchmark has no match but long string benchmark has match in middle of string, so long string benchmark is better score. Generally, the longer string length is, the better score.

asterite · 2017-01-12T14:27:31Z

Rabin-Karp is also faster for shorter strings. The old algorithm was very naive, for every char in the string check if there's a match from there on, so O(n*m), and Rabin-Karp will almost always be faster because of it's rolling hash algorithm.

Note that I knew the old algorithm was slow, it just wasn't a priority to improve it. There are many parts in the std that could use an optimization review.

@makenowjust By the way, there's also String#byte_index that currently has a very slow algorithm but could use Rabin-Karp (and it's easier, because it's byte index, not char index)

makenowjust · 2017-01-12T14:29:51Z

@asterite I have known it. I'll work tomorrow. Good night...

drhuffman12 · 2017-01-12T15:15:09Z

Awesome! Crystal is already quite fast; but I won't complain if it gets even faster! :)

bcardiff

Besides the spec that was mysteriously removed, if you can squash the format tool commit to the parent one we will be fine to merge this as is.

Thanks for the performance addition and sending clear benchmarks with them 👍

bcardiff · 2017-01-12T17:16:51Z

spec/std/string_spec.cr

@@ -653,7 +653,8 @@ describe "String" do

      describe "with offset" do
        assert { "foo baro baz".rindex("o b", 6).should eq(2) }
-        assert { "foo baro baz".rindex("fg").should be_nil }


why this spec was removed?

There is this in "with offset" section, but it has no offset option and it exists already in another line, so I thought it is just copy-and-paste mistaking.

Yeap, you are right.

MaxLap · 2017-01-13T00:53:16Z

I posted a possible improvement to the algorithm in the previous (for index) change #3873. I think it should be reviewed before merging this copy of it.

makenowjust · 2017-01-13T01:37:31Z

@MaxLap Your idea is awesome, but I think we cannot apply it to String#rindex.

makenowjust · 2017-01-13T02:04:29Z

@bcardiff Rebased

MaxLap · 2017-01-13T03:28:17Z

Ah, i see what you mean. A check could still be made to do another step unless the current byte is a valid starting one, but there may be less to gain here. You could still try it if you want.

if (byte & 0x80) == 0 || (byte & 0x40) != 0 is the same as if (byte & 0xC0) != 0x80. But maybe the compiler handles that one itself.

sdogruyol · 2017-01-13T09:20:47Z

Keep up the great work people 🎉 😍

Benchmark is here: https://gist.github.com/MakeNowJust/7a3c08cb6fab3862a305a01dec223ad0

makenowjust · 2017-01-13T09:31:48Z

@MaxLap Thanks. I applied some optimizations.

bcardiff · 2017-01-13T14:41:02Z

Thanks @makenowjust and @MaxLap ! ⚡️ ⚡️

kostya · 2017-01-22T14:23:26Z

little changed behavior after this:

0.20.4
crystal eval 'p "".includes?("")'
false

0.20.5
crystal eval 'p "".includes?("")'
true

not sure what is really correct.

MaxLap · 2017-01-22T20:06:19Z

Really? for me, on 0.20.5, I still get true O_o

kostya · 2017-01-22T20:16:48Z

ops i miss versions, fixed
so, true, i think correct, ok

MaxLap · 2017-01-22T20:54:32Z

True would be the same result as "".include?("") in ruby.

It may be interesting to add this edge case to the specs.

bcardiff added performance topic:stdlib labels Jan 12, 2017

spalladino added the pr:needs-review label Jan 12, 2017

spalladino requested a review from bcardiff January 12, 2017 15:15

bcardiff requested changes Jan 12, 2017

View reviewed changes

bcardiff self-assigned this Jan 12, 2017

makenowjust force-pushed the feature/string/rindex-rabin-karp branch from 52dbfe9 to e460317 Compare January 13, 2017 00:58

makenowjust force-pushed the feature/string/rindex-rabin-karp branch from e460317 to 85a6044 Compare January 13, 2017 02:03

makenowjust force-pushed the feature/string/rindex-rabin-karp branch 2 times, most recently from e61369e to 991c6bd Compare January 13, 2017 09:18

makenowjust added 2 commits January 13, 2017 18:27

Optimize String#index with multi-byte text

553fe51

Implement Rabin-Karp algorithm for String#rindex

dac6c94

Benchmark is here: https://gist.github.com/MakeNowJust/7a3c08cb6fab3862a305a01dec223ad0

makenowjust force-pushed the feature/string/rindex-rabin-karp branch from 991c6bd to dac6c94 Compare January 13, 2017 09:27

bcardiff merged commit 88e5cf2 into crystal-lang:master Jan 13, 2017

bcardiff added this to the Next milestone Jan 13, 2017

makenowjust deleted the feature/string/rindex-rabin-karp branch January 13, 2017 20:55

This was referenced Jun 22, 2017

String: implement Rabin-Karp algorithm for #byte_index #4609

Merged

Implement Rabin-Karp algorithm for String#index #3873

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Implement Rabin-Karp algorithm for String#rindex #3876

Implement Rabin-Karp algorithm for String#rindex #3876

makenowjust commented Jan 12, 2017

drhuffman12 commented Jan 12, 2017

makenowjust commented Jan 12, 2017

asterite commented Jan 12, 2017

makenowjust commented Jan 12, 2017

drhuffman12 commented Jan 12, 2017

bcardiff left a comment

bcardiff Jan 12, 2017

makenowjust Jan 12, 2017 •

edited

bcardiff Jan 13, 2017

MaxLap commented Jan 13, 2017

makenowjust commented Jan 13, 2017

makenowjust commented Jan 13, 2017

MaxLap commented Jan 13, 2017

sdogruyol commented Jan 13, 2017

makenowjust commented Jan 13, 2017

bcardiff commented Jan 13, 2017

kostya commented Jan 22, 2017 •

edited

MaxLap commented Jan 22, 2017

kostya commented Jan 22, 2017 •

edited

MaxLap commented Jan 22, 2017

Implement Rabin-Karp algorithm for String#rindex #3876

Implement Rabin-Karp algorithm for String#rindex #3876

Conversation

makenowjust commented Jan 12, 2017

drhuffman12 commented Jan 12, 2017

makenowjust commented Jan 12, 2017

asterite commented Jan 12, 2017

makenowjust commented Jan 12, 2017

drhuffman12 commented Jan 12, 2017

bcardiff left a comment

Choose a reason for hiding this comment

bcardiff Jan 12, 2017

Choose a reason for hiding this comment

makenowjust Jan 12, 2017 • edited

Choose a reason for hiding this comment

bcardiff Jan 13, 2017

Choose a reason for hiding this comment

MaxLap commented Jan 13, 2017

makenowjust commented Jan 13, 2017

makenowjust commented Jan 13, 2017

MaxLap commented Jan 13, 2017

sdogruyol commented Jan 13, 2017

makenowjust commented Jan 13, 2017

bcardiff commented Jan 13, 2017

kostya commented Jan 22, 2017 • edited

MaxLap commented Jan 22, 2017

kostya commented Jan 22, 2017 • edited

MaxLap commented Jan 22, 2017

makenowjust Jan 12, 2017 •

edited

kostya commented Jan 22, 2017 •

edited

kostya commented Jan 22, 2017 •

edited