Forum: Ruby-core [Feature #905] Add String.new(fixnum) to preallocate large buffer

Feature #905: Add String.new(fixnum) to preallocate large buffer
http://redmine.ruby-lang.org/issues/show/905

Author: Charles Nutter
Status: Open, Priority: Normal

Because Strings are used in ruby as arbitrary byte buffers, and because 
the cost of growing a String increases as it gets larger (especially 
when it starts small), String.new should support a form that takes a 
fixnum and ensures the backing store will have at least that much room. 
This is analogous to Array.new(fixnum) which does the same thing.

The simple implementation of this would just add a Fixnum check to the 
String.new method, and the result would be an empty string with that 
size buffer. This would allow heavy string-appending algorithms and 
libraries (like ERb) to avoid doing so many memory copies while they 
run.

Issue #905 has been updated by Brian Ford.


In Rubinius, we have found it useful to have String.pattern(size, value) 
where value can be a fixnum or a string. The string created will be size 
characters where value is repeated. For example:

String.pattern(5, ?a)    # => "aaaaa"
String.pattern(5, " ")   # => "    "
String.pattern(5, "110") # => "11011"

Something like "ab" * 5 then becomes String.pattern("ab".size * 5, 
"ab").
----------------------------------------
http://redmine.ruby-lang.org/issues/show/905

Hi

In message "Re: [ruby-core:20668] [Feature #905] Add String.new(fixnum) 
to preallocate large buffer"
    on Fri, 19 Dec 2008 08:46:13 +0900, Charles Nutter 
<redmine@ruby-lang.org> writes:

|Because Strings are used in ruby as arbitrary byte buffers, and because the cost of growing a String increases as it gets larger (especially when it starts small), String.new should support a form that takes a fixnum and ensures the backing store will have at least that much room. This is analogous to Array.new(fixnum) which does the same thing.

I like the idea.

But I'd prefer adding a new class methodfor the purpose,
say. String#buffer(n), to adding new role to an argument by type,
or there may be a better name.

              matz.

On Dec 18, 2008, at 6:23 PM, Yukihiro Matsumoto wrote:

> But I'd prefer adding a new class methodfor the purpose,
> say. String#buffer(n), to adding new role to an argument by type,
> or there may be a better name.

Maybe

   str = String.capacity(n)

or

   str = String.sized(n)

(presumably n is in bytes, not characters)

Yukihiro Matsumoto wrote:
> I like the idea.
> 
> But I'd prefer adding a new class methodfor the purpose,
> say. String#buffer(n), to adding new role to an argument by type,
> or there may be a better name.

I thought String.new(1000) would be a nice equivalent to
Array.new(1000), since they both do essentially the same thing. But I'm
not opposed to a separate method. I would vote for something active and
descriptive like "allocate", but that's obviously not available.
"buffer" isn't bad.

I like "new" best. And of course Array.new changes behavior depending on
argument types too.

      Array.new(size=0, obj=nil)
      Array.new(array)
      Array.new(size) {|index| block }

What's good for the goose...

Brian Ford wrote:
> Issue #905 has been updated by Brian Ford.
> 
> 
> In Rubinius, we have found it useful to have String.pattern(size, value) where value can be a fixnum or a string. The string created will be size characters where value is repeated. For example:
> 
> String.pattern(5, ?a)    # => "aaaaa"
> String.pattern(5, " ")   # => "    "
> String.pattern(5, "110") # => "11011"
> 
> Something like "ab" * 5 then becomes String.pattern("ab".size * 5, "ab").

Yeah, seems like a reasonably good idea. The string formats seem a
little weird to me though...not what I'd expect. The analog with an
array would be to accept another array as the fill value, which seems
equally weird.

Dave Thomas wrote:
> (presumably n is in bytes, not characters)

Yes, I'm thinking bytes myself. Presumably you either want just a byte
buffer or you know how many bytes you need to allocate for the character
encoding you intend.

At 09:08 08/12/19, Brian Ford wrote:

>Something like "ab" * 5 then becomes String.pattern("ab".size * 5, "ab").

I'm at a total loss to see why
   String.pattern("ab".size * 5, "ab")
should be in any way better than
   "ab" * 5
but maybe that's just me. Can somebody explain?

Regards,    Martin.



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

2008/12/19 Martin Duerst <duerst@it.aoyama.ac.jp>:
> At 09:08 08/12/19, Brian Ford wrote:
>
>>Something like "ab" * 5 then becomes String.pattern("ab".size * 5, "ab").
>
> I'm at a total loss to see why
>   String.pattern("ab".size * 5, "ab")
> should be in any way better than
>   "ab" * 5
> but maybe that's just me. Can somebody explain?

It's probably not.  But if you want "ab" repeated 5 times, then "ab" *
5 is probably the ideal solution.

Fixing the length in bytes is a new and different feature, i.e. your
pattern is cut off.  With String.pattern("bo",3) you would get "bob"
or maybe "bo" but in a buffer of length 3 bytes.

We could also name it "resize" with this semantics:

String.resize(100, "foo") -> "foo" and buffer has 100 bytes
String.resize(100) -> "" and buffer has 100 bytes

Or maybe just "size".  IMHO the idea was that you do not need to have
a String beforehand so all solution which are instance methods receive
a String as argument are probably suboptimal because they will
typically be invoked like show above, i.e. with a String constructor
which needs one object allocation (including GC bookkeeping overhead)
and a bit of memory.

A typical use case would be this:

File.open "foo" do |io|
  buffer = String.size(1024)
  while io.read(1024, buffer)
    # or even io.read(buffer.capacity, buffer)
    $defout.write(buffer)
  end
end

Kind regards

robert

On Dec 18, 2008, at 8:04 PM, Charles Oliver Nutter wrote:

> Yukihiro Matsumoto wrote:
>> I like the idea.
>> But I'd prefer adding a new class methodfor the purpose,
>> say. String#buffer(n), to adding new role to an argument by type,
>> or there may be a better name.
>
> I thought String.new(1000) would be a nice equivalent to  
> Array.new(1000), since they both do essentially the same thing.

There is a slight difference.  Array.new(1000) creates an array with a
thousand elements. The proposed String.new(1000) would create a string
with zero characters, but the ability to grow to 1000 characters (umm,
bytes) without internal reallocation.

I think this difference is enough to warrant different names.

Jim Weirich wrote:
> There is a slight difference.  Array.new(1000) creates an array with a 
> thousand elements. The proposed String.new(1000) would create a string 
> with zero characters, but the ability to grow to 1000 characters (umm, 
> bytes) without internal reallocation.
> 
> I think this difference is enough to warrant different names.

Yes, that's a good point; and the resulting array would << to the 1001st
element.

I suppose then coming up with a common name that works for both would be
a good idea. I'm back to liking "buffer" in both cases.

String.buffer(1000) produces an empty string that can grow to 1000 bytes
without needing to resize/copy.

Array.buffer(1000) produces an empty array that can grow to 1000
elements without needing to resize/copy.

Whatever is decided, I think it's going to be something people want
(need) on 1.8, so I'll probably submit a backport request as well (and
perhaps write up a simple extension people can use until then).

On Dec 19, 2008, at 9:33 AM, Charles Oliver Nutter wrote:

> I suppose then coming up with a common name that works for both  
> would be a good idea. I'm back to liking "buffer" in both cases.
>
> String.buffer(1000) produces an empty string that can grow to 1000  
> bytes without needing to resize/copy.
>
> Array.buffer(1000) produces an empty array that can grow to 1000  
> elements without needing to resize/copy.

I think the reason I dislike this is that you're creating methods that
are polymorphic on the types of their arguments, and yet we generally
don't do that in Ruby-level code. So by creating these methods, you're
giving them a different flavor from methods that would be written in
straight Ruby.

How about something more Ruby-like:

   s = String.new(initial_capacity: 1000)

   t = String.new(buffer, initial_capacity: 2*buffer.length)

Dave

Dave Thomas wrote:
> I think the reason I dislike this is that you're creating methods that 
> are polymorphic on the types of their arguments, and yet we generally 
> don't do that in Ruby-level code. So by creating these methods, you're 
> giving them a different flavor from methods that would be written in 
> straight Ruby.

Neither of those methods are polymorphic on anything. They're both new
methods that accept a Fixnum.

On Dec 19, 2008, at 12:48 PM, Charles Oliver Nutter wrote:

> Neither of those methods are polymorphic on anything. They're both  
> new methods that accept a Fixnum.

.new is

String.buffer is not a meaningful name for a constructor, in my
opinion, whereas String.new has a pedigree. By adding a initial_size:
n optional argument, you exactly express the meaning—you're asking for
an initial allocation when String.new executes. Similarly,

Array.new([1,2,3], initial_size: 100)

lets you both initialize and allocation a new array.


Right now, we have File.open("fred", "w"), rather than
File.open_write("fred"). It seems like a good idea, particularly for
an interface that's likely to grow over time (I can forsee

   String.new(initial_size: 1000, fill_with: " ", encoding: binary,
etc: ...)

Cheers


Dave

Dave Thomas wrote:
> 
> On Dec 19, 2008, at 12:48 PM, Charles Oliver Nutter wrote:
> 
>> Neither of those methods are polymorphic on anything. They're both new 
>> methods that accept a Fixnum.
> 
> .new is

And already has multiple forms in Array, so there's precedent. Also,
adding multiple forms with different named arguments doesn't reduce the
complexity of that single method any.

> String.buffer is not a meaningful name for a constructor, in my opinion, 
> whereas String.new has a pedigree. By adding a initial_size: n optional 
> argument, you exactly express the meaning—you're asking for an initial 
> allocation when String.new executes. Similarly,
> 
> Array.new([1,2,3], initial_size: 100)

But Array.new(initial_size: 100).size would == 0. That's confusing...I
think buffer better expresses that it's the backing store being sized
than the outward expression of the String or Array itself, which is what
initial_size means.

I would also expect that the cost of allocating and populating an
arguments hash for this would negate some of the gain from adding the
new form. Array.buffer(100) adds almost no overhead on top of the
physical creation of the backing store and object to wrap it, where
Array.buffer(initial_size: 100) creates both a new Array and a new Hash.
An implementation detail, sure, but we I think we just need something
simple here. Perhaps buffer just doesn't express it clearly enough?

> Right now, we have File.open("fred", "w"), rather than 
> File.open_write("fred"). It seems like a good idea, particularly for an 
> interface that's likely to grow over time (I can forsee
> 
>   String.new(initial_size: 1000, fill_with: " ", encoding: binary, etc: 
> ...)

It seems to me this is making the semantics of String.new much more
complicated, rather than simpler and more uniform. And at least encoding
is already available outside of "new", so this is little more than a
shortcut. But there's absolutely no way at present to allocate a string
with a guaranteed backing store size, and that's the sole intention of
this RFE.

On Dec 19, 2008, at 4:28 PM, Charles Oliver Nutter wrote:

> store being sized than the outward expression of the String or Array  
> itself, which is what initial_size means.
>
> I would also expect that the cost of allocating and populating an  
> arguments hash for this would negate some of the gain from adding  
> the new form. Array.buffer(100) adds almost no overhead on top of  
> the physical creation of the backing store and object to wrap it,  
> where Array.buffer(initial_size: 100) creates both a new Array and a  
> new Hash. An implementation detail, sure, but we I think we just  
> need something simple here. Perhaps buffer just doesn't express it  
> clearly enough?

I don't think the cost of a hash is going to be significant--if it is,
then I'd hope that implementors find a way of optimizing these styles
of keyword hashes, because they're used more and more
(*cough*Rails*cough*).

I agree initial_size: is misleading. Perhaps String.new(preallocate: n)


Dave

Dave Thomas wrote:
> I don't think the cost of a hash is going to be significant--if it is, 
> then I'd hope that implementors find a way of optimizing these styles of 
> keyword hashes, because they're used more and more (*cough*Rails*cough*).

Hard to do, since it has to be a hash on the callee side. Constructing
the hash could perhaps be delayed, in case the callee was a C function,
but it still has to be something. In comparison, new(1000) is almost 
free.

> Hard to do, since it has to be a hash on the callee side. Constructing the
> hash could perhaps be delayed, in case the callee was a C function, but it
> still has to be something. In comparison, new(1000) is almost free.

I suppose a clever implementation could optimize that out.
-=R

On Dec 19, 2008, at 5:28 PM, Charles Oliver Nutter wrote:
> I would also expect that the cost of allocating and populating an  
> arguments hash for this would negate some of the gain from adding  
> the new form. Array.buffer(100) adds almost no overhead on top of  
> the physical creation of the backing store and object to wrap it,  
> where Array.buffer(initial_size: 100) creates both a new Array and a  
> new Hash. An implementation detail, sure, but we I think we just  
> need something simple here. Perhaps buffer just doesn't express it  
> clearly enough?


How about:

String.reserve(100)
Array.reserve(100)

String.reserve(100, other_string)
Array.reserve(100, start_size, default_object)
Array.reserve(100, other_array)
Array.reserve(100, start_size) { # default block }

On Dec 19, 12:02 am, Martin Duerst <due...@it.aoyama.ac.jp> wrote:
> At 09:08 08/12/19, Brian Ford wrote:
>
> >Something like "ab" * 5 then becomes String.pattern("ab".size * 5, "ab").
>
> I'm at a total loss to see why
>    String.pattern("ab".size * 5, "ab")
> should be in any way better than
>    "ab" * 5
> but maybe that's just me. Can somebody explain?

It's not better. It's not intended that you see it. Behind the scenes
it has been useful for us to have this method. This is one example of
its usage. The string is allocated in one step and filled in one loop.

There are other places it has been useful. The most useful aspect is
requesting a particular size. The initial contents is a lesser, but
still useful aspect.

The mileage for other implementations may vary.

Cheers,
Brian

Gary Wright wrote:
> How about:
> 
> String.reserve(100)
> Array.reserve(100)

"reserve" is pretty good. I'll abstain from commenting on any other
forms since I really just want the single-param fixnum version myself.

Roger Pack wrote:
>> Hard to do, since it has to be a hash on the callee side. Constructing the
>> hash could perhaps be delayed, in case the callee was a C function, but it
>> still has to be something. In comparison, new(1000) is almost free.
>>     
>
> I suppose a clever implementation could optimize that out.
> -=R
>
>   
HEH.  So using this logic we have never had a clever implementation of
Ruby.  Should I laugh or cry? :)

Actually, since the syntax of a hash on the end of a method it is at
least possible we could modify the grammar to do something special on
the front-end (call-side).  Then call a special signature on the backend
for this hash-called method signature.   For regular Ruby-defined
methods with hash on the end we construct the hash and pass it as an
ordinary argument.  For our internally implemented methods (Java) we
could pass as a special signature.  The C impl maybe could do something
similiar.  Just trying to be clever.  I think this would be almost
impossible on a Ruby implemented method.  It would require dynamic
profiling at best.

-Tom

Charles Oliver Nutter wrote:
> Gary Wright wrote:
>> How about:
>>
>> String.reserve(100)
>> Array.reserve(100)
> 
> "reserve" is pretty good. I'll abstain from commenting on any other 
> forms since I really just want the single-param fixnum version myself.

Did anyone suggest String.capacity(100) yet? The sense would be obvious
to ruby extension writers.

I guess the relative silence on this issue means there's not much more
to discuss. Here's a summary up to now:

- Everyone seems to agree it's a good idea to add, so we should add it.
And I would like to see it backported to 1.8.6/7.

- Everyone likes the flat fixnum form except Dave Thomas, who would like
it to be a keyword argument. But that would not support backporting and
no core methods currently accept keyword arguments, plus it would create
a throw-away hash in all current implementations.

- Several names have been suggested: overload 'new', buffer,
preallocate, capacity, sized, reserve. I prefer 'buffer' and 'reserve',
with a strong lean toward 'buffer' because it mimics a well-known idiom
in the Java world: "String.buffer(1000)" == "new StringBuffer(1000)".

- Other forms have been suggested that accept a fill fixnum or fill
string; however I believe we should skip these cases for now since we're
not actually creating a string of a certain size (and content), we're
creating an empty string with a backing store of a certain size. The
expectation is that the contents of that backing store are unimportant
(perhaps \000s), and so fill params are meaningless.

So for me, the solution is String.buffer(1000). I rest my case, your 
honor.

On Dec 22, 2008, at 10:37 AM, Charles Oliver Nutter wrote:

> no core methods currently accept keyword arguments, plus it would  
> create a throw-away hash in all current implementations.

File.open...

Issue #905 has been updated by Yusuke Endoh.

Status changed from Open to Feedback

Hi,

> This would allow heavy string-appending algorithms and libraries (like ERb) to avoid doing so many memory copies while they run.

Is it really a bottleneck?  Please make an experiment and show us
the result.

We can continue API discussion after we confirm the feature really
makes sense.

--
Yusuke Endoh <mame@tsg.ne.jp>
----------------------------------------
http://redmine.ruby-lang.org/issues/show/905

Issue #905 has been updated by caleb clausen.


Do we really need a benchmark to confirm that copying large strings is 
expensive? Pre-sized buffers are a well-known performance win on other 
systems, so why not for ruby as well?

I would like to try to create a benchmark to prove this would help, but 
it may be some time before I can get to it.
----------------------------------------
http://redmine.ruby-lang.org/issues/show/905

On Thu, Mar 4, 2010 at 07:11, caleb clausen <redmine@ruby-lang.org> 
wrote:
> Issue #905 has been updated by caleb clausen.

> Do we really need a benchmark to confirm that copying large strings is expensive? Pre-sized buffers are a well-known performance win on other systems, so why not for ruby as well?

Doesn’t this unnecessarily expose implementation details about String?
 Preallocation doesn’t make as much sense if Strings were implemented
using, for example, Ropes [1].

[1] http://en.wikipedia.org/wiki/Rope_(computer_science)

Hi,

2010/3/4 caleb clausen <redmine@ruby-lang.org>:
> Pre-sized buffers are a well-known performance win on other systems, so why not for ruby as well?

Indeed, it will bring speed up to Ruby, but if the speed up is
negligibly-small, it is not only actually useless but also bad
for code maintenance.

If we confirm the performance up is significant and a patch is
present, we'll be strongly encouraged to discuss the feature
actively and to import the patch.


I have forgotten another matter.  I also wonder how many case
we can expect a precise length that ERB will generate.
If we cannot in many cases, the feature may be still useless.

Well, it may be good only if the feature can be used in Rails...

Doesn't Ruby allocate already using a "double memory if you run out"
rule? That makes string concatenation (amortized) linear, even if the
string must be moved in the memory.

I doubt that there are real-world use cases that would be much faster
with preallocation. As Yusuke said, ERb is more of a counter-example.

Even with this API extension, we wouldn't have control over the
generation of the string buffer in many use cases, as in Array#join,
String#% or in literals using #{}. Its use would be limited to 
String#<<.

[murphy]

On Fri, 5 Mar 2010, Kornelius Kalnbach wrote:

> Doesn't Ruby allocate already using a "double memory if you run out"
> rule? That makes string concatenation (amortized) linear, even if the
> string must be moved in the memory.

Yes (last time I looked), but while this sort of thing is
being looked at I'd like to remind people of the cunning code inside
Lua for handling large string concatenations:

http://www.lua.org/pil/11.6.html

It seems relevant in terms of moving data about.

        HTH
        Hugh

Hi,

2010/3/5 Kornelius Kalnbach <murphy@rubychan.de>:
> Doesn't Ruby allocate already using a "double memory if you run out"
> rule? That makes string concatenation (amortized) linear, even if the
> string must be moved in the memory.

Yes, it does.  This is why I think experiment is needed.

Because the suggested feature can be used to omit first some
expansions, it will actually reduce time.  But I guess if the
reduced time is not so much.


> Even with this API extension, we wouldn't have control over the
> generation of the string buffer in many use cases, as in Array#join,
> String#% or in literals using #{}. Its use would be limited to String#<<.

Absolutely.  The feature is hard to use.
Even if we pre-allocated a string, calling some method on the
string may shrink it.

I think we should call the feature just "optimization hint"
rather than API.  It is better to think the hint may be even
ignored.

Hi,

2010/3/5 Hugh Sasse <hgs@dmu.ac.uk>:
> Yes (last time I looked), but while this sort of thing is
> being looked at I'd like to remind people of the cunning code inside
> Lua for handling large string concatenations:
>
> http://www.lua.org/pil/11.6.html


At first glance, the document explains the difference of destructive
and non-destructive concatenations, like String#+ and #<<.

It is absolutely different topic from pre-allocation.

On Fri, 5 Mar 2010, Yusuke ENDOH wrote:

> At first glance, the document explains the difference of destructive
> and non-destructive concatenations, like String#+ and #<<.
> 
> It is absolutely different topic from pre-allocation.

It is related: the algorithm constructs large strings from smaller
ones in an elegant way using a "tower of Hanoi", and if the top
string concatenation gets bigger than the one below it, only then
are they joined together.  Result is less copying and merging.
Admittedly, it is less applicable with mutable strings, but while
only the top of the tower is modified, there'd be less churn in
memory.

        Hugh

> Doesn't Ruby allocate already using a "double memory if you run out"
> rule? That makes string concatenation (amortized) linear, even if the
> string must be moved in the memory.

It doesn't when you're reading IO.  Causing some serious slowdowns in 
doze.

http://redmine.ruby-lang.org/issues/show/2742
http://redmine.ruby-lang.org/issues/show/2741

So the idea is sound.  I almost surprised it isn't there already.

A better name might be set_size or set_buffer

-rp

Issue #905 has been updated by caleb clausen.


If String#<< is really O(1), there would seem to be little reason to 
change anything. I still want to investigate this myself when I get a 
chance.

I do like the tower of hanoi algorithm hugh pointed out. But it seems 
like a big change from where ruby's String class is now.
----------------------------------------
http://redmine.ruby-lang.org/issues/show/905

On 04.03.10 21:08, caleb clausen wrote:
> If String#<< is really O(1), there would seem to be little reason to
> change anything. I still want to investigate this myself when I get a
> chance.
O(n), where n is the size of the appended string.

But I think it's always worth to look into speedups even if we can't
expect to change the complexity class. The O-factor may not interesting
to theorists, but it matters greatly to programmers. JRuby, for example,
concats strings almost twice as fast in this benchmark:

require 'benchmark'

N = 10_000_000
Benchmark.bm 20 do |results|
  results.report 'loop' do
    N.times { }
  end
  results.report "'' <<" do
    s = ''
    N.times { s << '.' << 'word' }
  end
end

ruby19 string_buffer.rb
                          user     system      total        real
loop                  1.240000   0.010000   1.250000 (  1.255154)
'' <<                 5.820000   0.060000   5.880000 (  5.889959)

jruby string_buffer.rb
                          user     system      total        real
loop                  0.584000   0.000000   0.584000 (  0.488000)
'' <<                 2.900000   0.000000   2.900000 (  2.900000)

So, there is room for optimization somewhere.

[murphy]

Issue #905 has been updated by Kurt  Stephens.


+1

Preallocation of String would be immensely useful in large ERB 
templates.

So much so, I was looking to patching into rb_str_resize(str, len) with 
a method, to get around related performance issues.  Ruby Strings 
already support the difference between the string length and the 
allocated buffer size -- we need to expose it and ensure that Strings do 
not automatically "shrink" the internal String buffers.  There should 
probably be a method to explicitly shrink the internal buffer, if 
needed.

From what I can tell string growth is roughly O(log2 N) because of the 
power-of-2 buffer resizing.   For large buffers making this O(1) for 
large strings helps performance and reduces malloc() memory 
fragmentation.



----------------------------------------
http://redmine.ruby-lang.org/issues/show/905

On 05.03.10 01:13, Kurt Stephens wrote:
> Preallocation of String would be immensely useful in large ERB
> templates.
How big would the buffer size have to be for this template?

  <p><%= link_to @record.name, @record %></p>

> So much so, I was looking to patching into rb_str_resize(str, len)
> with a method, to get around related performance issues.  Ruby
> Strings already support the difference between the string length and
> the allocated buffer size -- we need to expose it and ensure that
> Strings do not automatically "shrink" the internal String buffers.
> There should probably be a method to explicitly shrink the internal
> buffer, if needed.
This sounds like C to me.

> From what I can tell string growth is roughly O(log2 N) because of
> the power-of-2 buffer resizing.
You probably mean O(N * log2 N). But even in the worst case (smallest
possible steps, string data must be relocated for each buffer
extension), it's still just O(N) where N is the length of the final
string. Example:

s = ''
s << '1' # allocate 1 byte, relocate 0 bytes, write 1 byte
s << '2' # allocate 2 bytes, relocate 1 byte, write 1 byte
s << '3' # allocate 4 bytes, relocate 2 bytes, write 1 byte
s << '4' # write 1 byte (buffer is long enough)
s << '5' # allocate 8 bytes, relocate 4 bytes, write 1 byte
...

So it's exactly n bytes for the writes, and O(n) bytes must be relocated
in total (about 2*n since sum[i=0..k] 2^i < 2^(k+1)). Allocation itself
is O(1) for each step.

But I don't say it can't be further optimized in the real world.

> For large buffers making this O(1)
> for large strings helps performance and reduces malloc() memory
> fragmentation.
Ropes have been mentioned, they provide constant time concatenation, but
have slower iteration and indexing. They also use more memory.

Is Array#join optimized for the case where all entries are strings? As 
in:

  if array.all? { |obj| obj.is_a? String }
    buffer_size = array.map { |str| str.size }.sum
  else
    buffer_size = whatever
  end
  result = allocate(buffer_size)
  array.each { |str| result << str }

We could have rope-like performance for concatenation then by using
Arrays, and #join them in linear time to get the final result. Wouldn't
change the complexity, but is probably faster.

[murphy]

Hi,

2010/3/5 Hugh Sasse <hgs@dmu.ac.uk>:
>> At first glance, the document explains the difference of destructive
>> and non-destructive concatenations, like String#+ and #<<.
>>
>> It is absolutely different topic from pre-allocation.
>
> It is related: the algorithm constructs large strings from smaller
> ones in an elegant way using a "tower of Hanoi", and if the top
> string concatenation gets bigger than the one below it, only then
> are they joined together.  Result is less copying and merging.


Ah, sorry.  I had to read all more carefully.

The algorithm itself is interesting, but I understand it is
just workaround to implement efficient string buffer by using
*immutable* strings (because Lua String seems always immutable).

But Ruby String is mutable.  Is it also more efficient with
*mutable* string than current direct concatenation?  I wonder
if the algorithm needs more memcpy than the current.

Hi,

2010/3/5 Kornelius Kalnbach <murphy@rubychan.de>:
>> Preallocation of String would be immensely useful in large ERB
>> templates.
> How big would the buffer size have to be for this template?
>
>  <p><%= link_to @record.name, @record %></p>

Yes, it is generally difficult to determine the size.

We may be able to estimate it by using domain knowledge in some cases.
(e.g., certain page size is empirically known as about 10KB, etc.)
But if the expectation is disappointed, it will cause wasteful memory
allocation or no speed up.


>> So much so, I was looking to patching into rb_str_resize(str, len)
>> with a method, to get around related performance issues.  Ruby
>> Strings already support the difference between the string length and
>> the allocated buffer size -- we need to expose it and ensure that
>> Strings do not automatically "shrink" the internal String buffers.
>> There should probably be a method to explicitly shrink the internal
>> buffer, if needed.
> This sounds like C to me.

Agreed.  It is too easy to waste memory.


> But I don't say it can't be further optimized in the real world.

Agreed.  So, we need a benchmark to discuss this.


>> For large buffers making this O(1)
>> for large strings helps performance and reduces malloc() memory
>> fragmentation.
> Ropes have been mentioned, they provide constant time concatenation, but
> have slower iteration and indexing. They also use more memory.
>
> Is Array#join optimized for the case where all entries are strings?

I think Array#join already does so.


Thank you very much for saying almost all I want to say :-)

On Fri, 5 Mar 2010, Yusuke ENDOH wrote:

> > string concatenation gets bigger than the one below it, only then
> *mutable* string than current direct concatenation?  I wonder
> if the algorithm needs more memcpy than the current.

Possibly.  I've not gone into this in much depth.  I thought it
might be helpful to raise it in case this would give significant
help to garbage collection.  I'm thinking that as the strings get
longer they fill up space in the heap so need to be moved to the
newly allocated space.  Dealing with only the top of the "tower of
Hanoi" would be handling smaller chunks.  I think this would need to
be tested, but could be worth exploring.  Lua is rather quick, and
the article talks about a big speed increase.

On the other hand, it is difficult to decide when to invoke this
algorithm.  It is probably too heavy for just joining two strings,
but for reading in lots of chunks and appending them, it could be a
big help.  I don't know how to detect that distinction in user code.
It might be too much work.

        Hugh

On 3/5/10, Yusuke ENDOH <mame@tsg.ne.jp> wrote:
> allocation or no speed up.
Generally, a given template should expand to about the same size every
time. You can't easily tell ahead of time how big a template will get,
but it's almost never the case that a template is expanded once and
then never again. So, maybe remember what the average expanded size
is, add say a 10% fudge factor, and use that as the initial buffer
size for subsequent expansions. You're not guaranteed that the
expansion will never get bigger than the alloc'd size, but hopefully
that will be rare. It should be a speedup in the average case, and no
slower than the status quo if the guessed size is too small.

The current algorithm wastes up to 49.9% of the allocated string
buffer. On average it might be 25%. This strategy would reduce average
memory wastage to under 10%.

A reasonable _initial_ guess for the expanded size of a template
that's never been expanded before would be the size of the unexpanded
template.

On Fri, Mar 5, 2010 at 17:25, Caleb Clausen <vikkous@gmail.com> wrote:
> On 3/5/10, Yusuke ENDOH <mame@tsg.ne.jp> wrote:
>> 2010/3/5 Kornelius Kalnbach <murphy@rubychan.de>:

>>> How big would the buffer size have to be for this template?
>>>
>>>  <p><%= link_to @record.name, @record %></p>

>> Yes, it is generally difficult to determine the size.
>>
>> We may be able to estimate it by using domain knowledge in some cases.
>> (e.g., certain page size is empirically known as about 10KB, etc.)
>> But if the expectation is disappointed, it will cause wasteful memory
>> allocation or no speed up.

> Generally, a given template should expand to about the same size every
> time.

I’m getting the feeling thath the only real use case that we’ve got
for this so far is ERb.  Wouldn’t it make more sense to change the way
ERb (and similar “string concatenators”) creates its result?

On 05.03.10 18:25, Nikolai Weibull wrote:
> I’m getting the feeling thath the only real use case that we’ve got
> for this so far is ERb.  Wouldn’t it make more sense to change the way
> ERb (and similar “string concatenators”) creates its result?
How about an optimized StringBuffer class in stdlib that's optimized for
this kind of stuff? But only if we really find a way to speed it up.

[murphy]

On 3/5/10, Nikolai Weibull <now@bitwi.se> wrote:
> I’m getting the feeling thath the only real use case that we’ve got
> for this so far is ERb.  Wouldn’t it make more sense to change the way
> ERb (and similar “string concatenators”) creates its result?

So, maybe erb can be modified to collect its result in an array which
is #join'd just before returning instead of a string which is
catenated to as you go along. In other words, instead of something
like this:

  def expand_template
     result=''
     fragments.each{|frag|
       .... #evaluate frag if appropriate
       result<<frag
     }
     return result
  end

it should do this:

  def expand_template
     result=[]
     fragments.each{|frag|
       .... #evaluate frag if appropriate
       result<<frag
     }
     return result.join
  end

This is a good suggestion, Nikolai. Array#join appears to have the
appropriate optimization already; in other words, it preallocates a
buffer (with rb_str_buf_new) that will be large enough for the total
length of all the fragments. However, I still don't see why this
facility which is available internally inside the interpreter cannot
be made available in rubyland as well. Why shouldn't there be a way to
call rb_str_buf_new directly from ruby code?

Note: I've never looked at erb source code; I'm just speculating about
what it might actually consist of.

Nikolai Weibull wrote:
> On Fri, Mar 5, 2010 at 17:25, Caleb Clausen <vikkous@gmail.com> wrote:
>> On 3/5/10, Yusuke ENDOH <mame@tsg.ne.jp> wrote:
>>> 2010/3/5 Kornelius Kalnbach <murphy@rubychan.de>:
> 
>>>> How big would the buffer size have to be for this template?
>>>>
>>>>  <p><%= link_to @record.name, @record %></p>

I can guarantee the lower bound of output size of this example is 7.  :p

ERB template rendering is one of my greatest performance issues right 
now.

I routinely have have ERB templates that are over 80K, comprised mostly
of large static chunks with a small number of dynamic chunks.

For large templates with small substitutions, the cost of reallocation
during concatenation is the biggest cost, thus preallocating a String
buffer to lower bound of the result size of 80k is a big time and memory
saver.

And I am looking at other template engines (e.g. Erubis).

This is a general problem with String concatenation -- ERB is only one
of the cases -- consider XML generation.  To top it off, String
concatentation is slower in MRI > 1.8.6.  String objects provides no
opportunities to give hints about big they will end up.

Low-level problems deserve low-level solutions.

KAS

Yusuke ENDOH wrote:
> Hi,
> 
> 2010/3/5 Kornelius Kalnbach <murphy@rubychan.de>:

> Agreed.  So, we need a benchmark to discuss this.
> 
I can supply a benchmark.

KAS

On 06.03.10 01:31, Kurt Stephens wrote:
> ERB template rendering is one of my greatest performance issues right now.
Have you really identified String concatenation as the primary issue?
There's so much more going on when building a template (especially in
Rails).

Somehow, my feeling is that the actual concatenation of a small string
takes even less time than the calling overhead of String#<< (accessing
self, method lookup, checking arguments, returning the recipient, ...)
We could be talking about, say, 2% of the time your template needs to
compile.

By the way, fact check: ERb really uses String#<<, right?
[murphy]

Issue #905 has been updated by Kornelius Kalnbach.

File string_buffer.diff added

Here's a patch that doesn't work. I don't know what I'm doing wrong 
here: RESIZE_CAPA seemed just right.

Any hints?
----------------------------------------
http://redmine.ruby-lang.org/issues/show/905

Hi,

2010/3/6 Kornelius Kalnbach <redmine@ruby-lang.org>:
> Here's a patch that doesn't work. I don't know what I'm doing wrong here: RESIZE_CAPA seemed just right.

Thank you for your writing a patch!
It seems to work on my environment.  What made you think it does
not work?


I confirmed it by the following program:

  opt = false
  s = ""
  t = "x" * 1_000_000
  s.buffer(100_000_000) if opt
  100.times { s << t }
  p s.size

The above program takes 0.205 sec. when opt is false, and takes
0.195 sec. when opt is true.


But this is artificial example with very big string (1 GB).
The following more realistic case (with 100 KB):

  opt = false
  1000.times do
    s = ""
    s.buffer(opt ? 100_001 : 100)
    x = "x" * 1000
    100.times { s << x }
  end

takes 0.115 sec. when opt is false, 0.130 sec. when opt is true.
I don't know why it becomes slower, but the story seems not to be
so simple.


Anyway, the overhead of concatenation seems not so big.  I doubt
if it is the bottleneck.

On 06.03.10 21:44, Yusuke ENDOH wrote:
> 2010/3/6 Kornelius Kalnbach <redmine@ruby-lang.org>:
>> Here's a patch that doesn't work. I don't know what I'm doing wrong here: RESIZE_CAPA seemed just right.
> Thank you for your writing a patch!
> It seems to work on my environment.  What made you think it does
> not work?
The fact that the memory taken by the Ruby process didn't change in top.
I requested a 200MB buffer, and the process was still at 2.8MB.

> Anyway, the overhead of concatenation seems not so big.  I doubt
> if it is the bottleneck.
That's my conclusion, too. But the JRuby team seems to have seen some
10% speedup:

  http://gist.github.com/323431 - without and with preset buffer

Maybe the question is, is it worth it?

[murphy]

Hi,

2010/3/7 Kornelius Kalnbach <murphy@rubychan.de>:
> On 06.03.10 21:44, Yusuke ENDOH wrote:
>> 2010/3/6 Kornelius Kalnbach <redmine@ruby-lang.org>:
>>> Here's a patch that doesn't work. I don't know what I'm doing wrong here: RESIZE_CAPA seemed just right.
>> Thank you for your writing a patch!
>> It seems to work on my environment.  What made you think it does
>> not work?
> The fact that the memory taken by the Ruby process didn't change in top.
> I requested a 200MB buffer, and the process was still at 2.8MB.

Hmm, I guess you saw physical memory size allocated.
On many platform, physical memory is not allocated until
writing into the page actually occurs.

If you use Linux, see virtual memory size (VSZ column of
ps command), instead of %MEM.  It would reflect your huge
allocation.

The performance may be improved by using madvise, but I
don't think it should be supported by ruby core.

Issue #905 has been updated by Motohiro KOSAKI.


Hi

At least, Linux madvise doesn't improve the performance in such case. 
current cruby + linux(glibc) realloc implementation makes very optimal 
behavior.
a big size string makes a big size realloc() and a big size realloc() is 
using mremap(2) internally. Then, realloc() doesn't makes string copy at 
all.

IOW, the main benefit of string.buffer() is to reduce realloc() cost. 
but it is already zero. so I don't think it is worth method. sadly 
almost developers never use such no improve method, I expect.

Instead, I would propose improve JRuby's internal string representation 
and string concat implementation.

Thanks.
----------------------------------------
http://redmine.ruby-lang.org/issues/show/905

Issue #905 has been updated by _ wanabe.


Hi,

>  opt = false
>  1000.times do
>    s = ""
>    s.buffer(opt ? 100_001 : 100)
>    x = "x" * 1000
>    100.times { s << x }
>  end
>
> takes 0.115 sec. when opt is false, 0.130 sec. when opt is true.

I tried too.
Interestingly, it gets faster on my environment.

$ cat test.rb
require 'benchmark'
opt = ARGV[0]
list = Array.new(10) do
  Benchmark.realtime do
    1000.times do
      s = ""
      s.buffer(opt ? 100_001 : 100)
      x = "x" * 1000
      100.times { s << x }
    end
  end
end
list.sort!
p list.first, list.last

$ ./ruby -v -Ilib test.rb opt
ruby 1.9.2dev (2010-03-07 trunk 26843) [i386-mingw32]
0.1780099868774414
0.18601107597351074

$ ./ruby -v -Ilib test.rb
ruby 1.9.2dev (2010-03-07 trunk 26843) [i386-mingw32]
0.21401190757751465
0.22301316261291504

But, I guess, the patch may not work as expected in some cases.
Some methods (String#succ!, sub!, []=, and so on) can let CAPA shrink.
----------------------------------------
http://redmine.ruby-lang.org/issues/show/905

Hi,

2010/3/5 Kornelius Kalnbach <murphy@rubychan.de>:
>  results.report "'' <<" do
> jruby string_buffer.rb
>                          user     system      total        real
> loop                  0.584000   0.000000   0.584000 (  0.488000)
> '' <<                 2.900000   0.000000   2.900000 (  2.900000)


I wonder why such a simple loop is slower than jruby...?

I retested.

  ruby19
                            user     system      total        real
  loop                  2.100000   0.000000   2.100000 (  2.095623)
  '' <<                11.720000   0.040000  11.760000 ( 11.768111)

  jruby
                            user     system      total        real
  loop                  2.263000   0.000000   2.263000 (  2.228000)
  '' <<                10.193000   0.000000  10.193000 ( 10.193000)

Ko1 told me that GC makes the second benchmark slower than JRuby.
In MRI, a string literal is duplicated whenever evaluated.
I moved the literals out of the loop:

  results.report "'' <<" do
    s = ''
    s1, s2 = '.', 'word'
    N.times { s << s1 << s2 }
  end

  ruby19
                            user     system      total        real
  '' <<                 6.810000   0.040000   6.850000 (  6.851979)

  jruby
                            user     system      total        real
  '' <<                 7.159000   0.000000   7.159000 (  7.126000)

Indeed, there is room for optimization in MRI, but in this case,
it is not in string concatenation, I guess.

Issue #905 has been updated by Motohiro KOSAKI.


>    end
>$ ./ruby -v -Ilib test.rb
>ruby 1.9.2dev (2010-03-07 trunk 26843) [i386-mingw32]
>0.21401190757751465
>0.22301316261291504

Ah, yes. "x" * 1000 is not so big string. then, its realloc() doesn't 
use mremap.
It mean string concat(i.e. "<<" operator) cause string copy on each 
time. but is
this real issue? Does small string copy makes big peformance issue? 
when? So, I
think we need good realistic benchmark.

Thanks.
----------------------------------------
http://redmine.ruby-lang.org/issues/show/905

On 07.03.10 06:57, Yusuke ENDOH wrote:
> Hmm, I guess you saw physical memory size allocated.
> On many platform, physical memory is not allocated until
> writing into the page actually occurs.
I didn't know that. Thanks!
[murphy]

On Sun, Mar 7, 2010 at 4:58 AM, Yusuke ENDOH <mame@tsg.ne.jp> wrote:
> Ko1 told me that GC makes the second benchmark slower than JRuby.
> In MRI, a string literal is duplicated whenever evaluated.
> I moved the literals out of the loop:

JRuby behaves the same, since literal strings are still separate
objects and mutable.

>  jruby
>                            user     system      total        real
>  '' <<                 7.159000   0.000000   7.159000 (  7.126000)
>
> Indeed, there is room for optimization in MRI, but in this case,
> it is not in string concatenation, I guess.

My numbers came out somewhat differently. Make sure you're running
with the JVM's "server" mode if you run on Hotspot (Sun/OpenJDK):

~/projects/jruby âž” jruby --server string_bench.rb
                          user     system      total        real
loop                  0.572000   0.000000   0.572000 (  0.523000)
'' <<                 1.470000   0.000000   1.470000 (  1.470000)

~/projects/jruby âž” ruby1.9 string_bench.rb
                          user     system      total        real
loop                  0.810000   0.000000   0.810000 (  0.838414)
'' <<                 2.670000   0.040000   2.710000 (  2.733041)

Here's numbers with a prototypical String.buffer implementation:

~/projects/jruby âž” jruby --server string_bench.rb
                          user     system      total        real
loop                  0.655000   0.000000   0.655000 (  0.606000)
'' <<                 1.390000   0.000000   1.390000 (  1.390000)
                          user     system      total        real
loop                  0.321000   0.000000   0.321000 (  0.321000)
'' <<                 1.241000   0.000000   1.241000 (  1.241000)
                          user     system      total        real
loop                  0.314000   0.000000   0.314000 (  0.314000)
'' <<                 1.229000   0.000000   1.229000 (  1.229000)

Of course, this 10-15% improvement could simply be because the JVM
does not provide a "realloc" for its arrays (for various reasons, some
of them presumably because it moves objects around in memory a lot).
In order to grow a string, we have to allocate a new array and copy
its contents. Under those circumstances, String.buffer makes a lot of
sense, since the copying can get expensive at large sizes.

I don't know enough about MRI internals to implement an equivalent
String.buffer, but here's the patch to JRuby:

diff --git a/src/org/jruby/RubyString.java 
b/src/org/jruby/RubyString.java
index 71e6b63..e618ec8 100644
--- a/src/org/jruby/RubyString.java
+++ b/src/org/jruby/RubyString.java
@@ -451,6 +451,11 @@ public class RubyString extends RubyObject
implements EncodingCapable {
     public static RubyString newStringLight(Ruby runtime, int size) {
         return new RubyString(runtime, runtime.getString(), new
ByteList(size), false);
     }
+
+    @JRubyMethod(meta = true)
+    public static IRubyObject buffer(ThreadContext context,
IRubyObject self, IRubyObject size) {
+        return newStringLight(context.getRuntime(),
(int)size.convertToInteger().getLongValue());
+    }

     public static RubyString newString(Ruby runtime, CharSequence str) 
{
         return new RubyString(runtime, runtime.getString(), str);

Hi,

2010/3/8 Charles Oliver Nutter <headius@headius.com>:
>> Indeed, there is room for optimization in MRI, but in this case,
>> it is not in string concatenation, I guess.
>
> My numbers came out somewhat differently. Make sure you're running
> with the JVM's "server" mode if you run on Hotspot (Sun/OpenJDK):

Ah, I didn't specify the option:

                            user     system      total        real
  loop                  1.471000   0.000000   1.471000 (  1.248000)
  '' <<                 5.906000   0.000000   5.906000 (  5.906000)

JRuby is great :-)


> Here's numbers with a prototypical String.buffer implementation:
>
*snip*
>
> Of course, this 10-15% improvement could simply be because the JVM
> does not provide a "realloc" for its arrays (for various reasons, some
> of them presumably because it moves objects around in memory a lot).
> In order to grow a string, we have to allocate a new array and copy
> its contents. Under those circumstances, String.buffer makes a lot of
> sense, since the copying can get expensive at large sizes.


Ok, we finally grasped the situation.  To sum up:

- This feature is meaningless with MRI, at least, on Linux.
- But it serves as a workaround for slow string concatenation of JRuby
  that cannot be optimized due to JVM.
- Does MRI provide the feature just for script compatibility?

I cannot make the judgment.  Please wait for matz.