[webkit-dev] Optimization of buffer allocation of Vector and StringBuilder

[Xianzhu Wang (王显著)]

Hi,

One aspect of the cost of WTF::Vector and WTF::StringBuilder is about buffer
expansion and shrinking. The affecting factors include the minimum capacity,
policy of expansion and shrinking, etc. I think the optimal configurations
of them are related to not only the application, but also the underlying
memory allocation library. For example, with tcmalloc, allocation of a
17-byte buffer will get a 32-byte buffer, so we can directly allocate a
32-byte buffer when the required size is 17; and we don't need to shrink a
32-byte buffer to 17. I think considering this we could reduce the
unnecessary allocations and copies. I'm doing some experiments, and the data
will be available soon.

malloc_good_size() can get the rounded-up size of a required size, but it
seems not available on all platforms. It's easy to implementation it over
tcmalloc. On platforms that malloc_good_size() is not available, it's
possible to get the mapping with a program and then hardcode the rules in
WebKit, but I'm afraid if the rules could match the actual running
environment. Any ideas?

Thanks,
Xianzhu

=============================
Appendix:

The current characteristics of WTF::Vector and WTF::StringBuilder about
memory allocation are as below:

Vector:
  - minimum capacity: 16 elements
  - inline buffer, copy on release
  - dynamic buffer: expand by (1/4 of the original size + 1) each time: 16,
21, 27, 34, 43, 54, .... these seem not good for allocators
  - shrinkToFit() will shrink to required size

StringBuilder:
  - minimum capacity: 16 UChars
  - expand to 2x size each time
  - shrinkToFit() will shrink if over-allocation > 1/4 of the required size
  - automic strinking in toString(), if over-allocation > 1/4 of the
required size
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.webkit.org/pipermail/webkit-dev/attachments/20111010/41bec070/attachment.html>