Forum: Ruby-core What does rb_memsearch do?

4995c7ce9523ce00dea01362cb976196?d=identicon&s=25 Kornelius Kalnbach (Guest)
on 2006-11-11 07:38
(Received via mailing list)
Hello!

I've been wondering what the function rb_memsearch does. It is
defined in
re.c (line 101). It is only used for rb_str_index, and I can't figure
out
what it does.

Is it an exotic string search algorithm? Whatever it does, it's very
slow,
slower then the naive memcmp implementation from memcmp.c.

Benchmark attached.
[murphy]

require 'benchmark'

N = 100_000
sub = 'That is a foo.'
s = 'That is a bar. ' * 10 + sub

Benchmark.bm 20 do |bm|
   bm.report 'String#index' do
     N.times do
       s.index sub
     end
   end

   sub.reverse!
   s.reverse!
   bm.report 'String#rindex' do
     N.times do
       s.rindex sub
     end
   end
end
# >>                           user     system      total        real
# >> String#index          0.170000   0.000000   0.170000
(  0.163899)  # OK
# >> String#rindex         0.710000   0.000000   0.710000
(  0.704800)  # why?
0ec4920185b657a03edf01fff96b4e9b?d=identicon&s=25 Yukihiro Matsumoto (Guest)
on 2006-11-11 08:06
(Received via mailing list)
Hi,

In message "Re: What does rb_memsearch do?"
    on Sat, 11 Nov 2006 15:36:47 +0900, Kornelius Kalnbach
<murphy@rubychan.de> writes:
|
|Hello!
|
|I've been wondering what the function rb_memsearch does. It is
|defined in
|re.c (line 101). It is only used for rb_str_index, and I can't figure
|out
|what it does.
|
|Is it an exotic string search algorithm? Whatever it does, it's very
|slow,
|slower then the naive memcmp implementation from memcmp.c.

It is multibyte aware string search using Karp Rabin algorithm.

							matz.
This topic is locked and can not be replied to.