Ruby Forum Ruby-core > Changing the algorithm of String#*

Hi there

I recently played around and found String#* to be rather slow,
wondering why I dug in the source and found it copied only linearly.
That can be reduced to a logarithmic copying, so I rewrote the code to
use an algorithm of logarithmic complexity. Please note that my C-fu
is rather weak, so please peer-review to code.
I hope you deem it worthy to be used in ruby :)
Zenspider btw. pointed out, that the same could be used with Array#*.

The rewritten rb_str_times routine in string.c:

VALUE
rb_str_times(str, times)
   VALUE str;
   VALUE times;
{
   VALUE str2;
   long copy_bytes, ltimes, tmp_len, target_len, rest;

   ltimes = NUM2LONG(times);
   if (ltimes < 0) {
     rb_raise(rb_eArgError, "negative argument");
   }
   if (ltimes && LONG_MAX/ltimes <  RSTRING_LEN(str)) {
     rb_raise(rb_eArgError, "argument too big");
   }

   tmp_len    = (long)pow(2,floor(log2((double)ltimes))) *
RSTRING_LEN(str);
   target_len = RSTRING_LEN(str) * ltimes;
   rest       = target_len - tmp_len;
   str2       = rb_str_new5(str,0, target_len);
   memcpy(RSTRING_PTR(str2), RSTRING_PTR(str), RSTRING_LEN(str));

   for (copy_bytes = RSTRING_LEN(str); copy_bytes < tmp_len;
copy_bytes *= 2) {
     memcpy(RSTRING_PTR(str2)+copy_bytes, RSTRING_PTR(str2),
copy_bytes);
   }
   memcpy(RSTRING_PTR(str2)+copy_bytes, RSTRING_PTR(str2), rest);
   RSTRING_PTR(str2)[RSTRING_LEN(str2)] = '\0';

   OBJ_INFECT(str2, str);

   return str2;
}


Regards
Stefan Rusterholz

Hi,

In message "Re: Changing the algorithm of String#*"
    on Sun, 23 Mar 2008 05:44:06 +0900, apeiros <apeiros@gmx.net> 
writes:

|I recently played around and found String#* to be rather slow,  
|wondering why I dug in the source and found it copied only linearly.  
|That can be reduced to a logarithmic copying, so I rewrote the code to  
|use an algorithm of logarithmic complexity. Please note that my C-fu  
|is rather weak, so please peer-review to code.
|I hope you deem it worthy to be used in ruby :)
|Zenspider btw. pointed out, that the same could be used with Array#*.
|
|The rewritten rb_str_times routine in string.c:

Does this make any meaningful difference?  memcpy(), which is O(n)
seems significant.

              matz.

At 17:29 08/03/24, Yukihiro Matsumoto wrote:
>|I hope you deem it worthy to be used in ruby :)
>|Zenspider btw. pointed out, that the same could be used with Array#*.
>|
>|The rewritten rb_str_times routine in string.c:
>
>Does this make any meaningful difference?  memcpy(), which is O(n)
>seems significant.

If the original string is reasonably long, this is true. But it may
not be true for very short strings (e.g. 1 byte). Stephan, can you give
some actual execution times?

Regards,    Martin.



#-#-#  Martin J. Du"rst, Assoc. Professor, Aoyama Gakuin University
#-#-#  http://www.sw.it.aoyama.ac.jp       mailto:duerst@it.aoyama.ac.jp

In article <E1JdhWd-0004oI-T1@x61.netlab.jp>,
  Yukihiro Matsumoto <matz@ruby-lang.org> writes:

> Does this make any meaningful difference?  memcpy(), which is O(n)
> seems significant.

I implemented (and committed) similar idea for 1.9 a month ago. 
(r15514)

My implementation doesn't use floating point operation, though.

% time ruby -ve '"a" * 100000000'
ruby 1.9.0 (2008-03-24 revision 15830) [i686-linux]
-e:1: warning: useless use of * in void context
ruby -ve '"a" * 100000000'  0.12s user 0.10s system 93% cpu 0.231 total

% time ruby-1.8 -ve '"a" * 100000000'
ruby 1.8.6 (2008-03-11 patchlevel 5000) [i686-linux]
-e:1: warning: useless use of * in void context
ruby-1.8 -ve '"a" * 100000000'  3.68s user 0.08s system 97% cpu 3.843 
total

Am 24.03.2008 um 10:17 schrieb Martin Duerst:
>> code to
>
> If the original string is reasonably long, this is true. But it may
> not be true for very short strings (e.g. 1 byte). Stephan, can you  
> give
> some actual execution times?
>
> Regards,    Martin.

Unfortunately I have to go 2 weeks to military in a few minutes. But
in my tests it was around 5-10x faster than without my patch (for 1
byte Strings that is).
For small N it might become less, but I'm interested in Tanakas patch
without float operations. I'll take a look at it when I'm back :)

Regards
Stefan

Am 24.03.2008 um 09:29 schrieb Yukihiro Matsumoto:

> |use an algorithm of logarithmic complexity. Please note that my C-fu
> |is rather weak, so please peer-review to code.
> |I hope you deem it worthy to be used in ruby :)
> |Zenspider btw. pointed out, that the same could be used with Array#*.
> |
> |The rewritten rb_str_times routine in string.c:
>
> Does this make any meaningful difference?  memcpy(), which is O(n)
> seems significant.
>
>               matz.

Here are the numbers of a bench I did, 1000 iterations each:
                               user     system      total        real
|   gain
----------------------------------------------------------------------
+--------
String#*  1Byte*10        0.000000   0.000000   0.000000 (  0.002699) |
String#** 1Byte*10        0.000000   0.000000   0.000000 (  0.002798)
|   -3.5%
----------------------------------------------------------------------
+--------
String#*  1Byte*1000      0.040000   0.010000   0.050000 (  0.036235) |
String#** 1Byte*1000      0.000000   0.000000   0.000000 (  0.006490)
| +458.3%
----------------------------------------------------------------------
+--------
String#*  1Byte*100_000   3.100000   0.340000   3.440000 (  3.438175) |
String#** 1Byte*100_000   0.110000   0.350000   0.460000 (  0.472152)
| +628.2%
----------------------------------------------------------------------
+--------
String#*  1KB*10          0.010000   0.020000   0.030000 (  0.044639) |
String#** 1KB*10          0.020000   0.010000   0.030000 (  0.014168)
| +215.1%
----------------------------------------------------------------------
+--------
String#*  1KB*1000        1.000000   3.250000   4.250000 (  4.312175) |
String#** 1KB*1000        1.240000   3.200000   4.440000 (  4.483295)
|   -3.8%

The benchcode:
require 'benchmark'
require 'stringtimes2'

OneByte     = " ".freeze
OneKiloByte = (" "*1000).freeze
A = 1000

Benchmark.bm(32) { |x|
  x.report("String#*  1Byte*10") {
    A.times { OneByte * 10 }
  }
  x.report("String#** 1Byte*10") {
    A.times { OneByte ** 10 }
  }

  x.report("String#*  1Byte*1000") {
    A.times { OneByte * 1000 }
  }
  x.report("String#** 1Byte*1000") {
    A.times { OneByte ** 1000 }
  }

  x.report("String#*  1Byte*100_000") {
    A.times { OneByte * 100_000 }
  }
  x.report("String#** 1Byte*100_000") {
    A.times { OneByte ** 100_000 }
  }

  x.report("String#*  1KB*10") {
    A.times { OneKiloByte * 10 }
  }
  x.report("String#** 1KB*10") {
    A.times { OneKiloByte ** 10 }
  }

  x.report("String#*  1KB*1000") {
    A.times { OneKiloByte * 1000 }
  }
  x.report("String#** 1KB*1000") {
    A.times { OneKiloByte ** 1000 }
  }
}

I hope that helps. I wonder how those numbers compare to Tanakas code
without floating point operations.

Regards
Stefan