From: apeiros <apeiros@...>
Date: 2008-03-25T01:26:37+09:00
Subject: Re: Changing the algorithm of String#*

Am 24.03.2008 um 10:17 schrieb Martin Duerst:
> At 17:29 08/03/24, Yukihiro Matsumoto wrote:
>> 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.
>
> 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