Sub-optimal usage of string.reserve in decoder

[GoogleCodeExporter]

I have identified a bottleneck in the streaming decoder implementation, more 
precisely where decoded_target->reserve() is called unconditionally in 
VCDiffDeltaFileWindow::ReadHeader.

When string.reserve is called, the standard C++ library typically 
over-allocates space in its internal buffer - when a string is expanded 
incrementally (through string.append for example) one would like to avoid 
reallocating a larger C-string and memcpy:ing the contents for each operation. 
A typical approach is to double the internal buffer size each time it 
overflows. This algorithm also applies to string.reserve, at least in recent 
GNU libstdc++.

Starting with the GNU Standard C++ Library v3, string.reserve honors shrink 
requests, which means that a smaller internal string will be reallocated if 
string.reserve is called with an argument smaller than the string's current 
capacity. This means that the cleverly over-allocated string will be shrunk 
again at the next call to VCDiffDeltaFileWindow::ReadHeader. Then, at the next 
call, it will be expanded and over-allocated, and then shrunk again and so on. 
This proves to be expensive when the number of chunks is relatively large.

In my benchmark program (attached), performance is increased by more than a 
factor 10 simply by avoiding the call to string.reserve if it already had the 
sufficient space:

---
marty@java:~$ time ./test 

real    0m38.713s
user    0m17.581s
sys 0m21.133s
marty@java:~$ time 
LD_PRELOAD=/home/marty/open-vcdiff-read-only/.libs/libvcddec.so ./test 

real    0m2.531s
user    0m1.872s
sys 0m0.656s

---

I have also attached my proposed patch.

Original issue reported on code.google.com by martyro...@gmail.com on 29 Jul 2010 at 4:10

Attachments:

• test.cc
• string_alloc_optimization.patch

[GoogleCodeExporter]

See also http://gcc.gnu.org/bugzilla/show_bug.cgi?id=20706

Original comment by martyro...@gmail.com on 29 Jul 2010 at 4:31

[GoogleCodeExporter]

Thanks very much for your contribution, Marty, and for your interest in 
open-vcdiff.

Even though it's a small patch (with a big effect), would you mind filling out 
a Contributor License Agreement, as described in the project wiki?
http://code.google.com/p/open-vcdiff/wiki/OpenVcdiffDevGuide
Thanks!

Saludos,

lincoln

Original comment by openvcd...@gmail.com on 29 Jul 2010 at 4:41

• Changed state: Started
• Added labels: Performance

[GoogleCodeExporter]

Sure. I just realized I used the wrong account to post the patch - I will 
resubmit it from my other account once the CLA for it has been processed.

Original comment by martyro...@gmail.com on 29 Jul 2010 at 5:24

[GoogleCodeExporter]

Err, why not post the patch right away. Here it is again.

Original comment by marty22...@gmail.com on 29 Jul 2010 at 5:32

Attachments:

• string_alloc_optimization.patch

[GoogleCodeExporter]

Fixed in open-vcdiff version 0.8.

Original comment by openvcd...@gmail.com on 4 Aug 2010 at 6:46

• Changed state: Fixed