From: Kornelius Kalnbach <murphy@...>
Date: 2010-03-05T11:58:25+09:00
Subject: [ruby-core:28493] Re: [Feature #905] Add String.new(fixnum) to preallocate large buffer

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]