From: apeiros <apeiros@...>
Date: 2008-04-24T08:17:53+09:00
Subject: Re: Changing the algorithm of String#*

Am 24.03.2008 um 09:29 schrieb Yukihiro Matsumoto:

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

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