Our proposal for a MATDS

Tue Mar 4 00:54:00 GMT 2003

Hi all!

As mentioned erlier on this list (http://gcc.gnu.org/ml/libstdc++/2003-02/msg00098.html) we (that's me and Ola RÃ¶nnerup) have been working on a allocator suitable for MT applications for quite some time now. The initial version was written mid last year and has been running in production enviorment since then with good results. Now we have taken that code and rewritten it to a patch against stl_alloc.h and solved the issues that we've come across and added some new ideas (mostly related to how thread_id's are assigned to support both thread pool and producer/consumer models, the way memory allocated by one thread and then deallocated by another is handled and minimizing heap growth over time by dynamically limiting the freelists).

While looking at the patch, bear in mind that this is our first attempt to write a patch against libstdc++ and there are most likely both formatting, naming and other things wrong but the patch works with our CVS version of GCC (g++ (GCC) 3.4 20030202 (experimental)) with and without threadsupport (posix) enabled.

First we would like to give you some results from various performance tests using the simple testapplications attached (which are the same as in the post mentioned above but with __mt_alloc added).

NOTES:
- All "single" tests are compiled with -static -O2
- All "mt" tests are compiled with -static -pthread -O2
- All tests are done on otherwise unloaded systems twice to filter out any real flukes - another rather interesting "mt" test is done further down. 
- All tests are done on Linux systems with kernel 2.4.18 and libc 2.2.5

alloc_perf_comp_single.cc, no threads, single 1GHz CPU machine:
Target run-time: 10s
Calibrating test_ints... DONE! Will do 5500000 iterations.
__pool_alloc... DONE! Time 9.910733
__malloc_alloc... DONE! Time 15.141536
__mt_alloc... DONE! Time 12.615181
Relative performance to __pool_alloc:
__malloc_alloc 65.453947 %
__mt_alloc 78.561956 %

alloc_perf_comp_single.cc, no threads, dual 1GHz CPU machine:
Target run-time: 10s
Calibrating test_ints... DONE! Will do 5600000 iterations.
__pool_alloc... DONE! Time 10.092421
__malloc_alloc... DONE! Time 15.412243
__mt_alloc... DONE! Time 12.789449
Relative performance to __pool_alloc:
__malloc_alloc 65.483142 %
__mt_alloc 78.912086 %

alloc_perf_comp_single.cc, posix threads, single 1GHz CPU machine:
Target run-time: 10s
Calibrating test_ints... DONE! Will do 5400000 iterations.
__pool_alloc... DONE! Time 9.888981
__malloc_alloc... DONE! Time 14.917552
__mt_alloc... DONE! Time 14.302427
Relative performance to __pool_alloc:
__malloc_alloc 66.290910 %
__mt_alloc 69.141978 %

alloc_perf_comp_single.cc, posix threads, dual 1GHz CPU machine:
Target run-time: 10s
Calibrating test_ints... DONE! Will do 5500000 iterations.
__pool_alloc... DONE! Time 10.065420
__malloc_alloc... DONE! Time 15.163035
__mt_alloc... DONE! Time 14.692080
Relative performance to __pool_alloc:
__malloc_alloc 66.381302 %
__mt_alloc 68.509156 %

alloc_perf_comt_mt.cc, posix threads, single 1GHz CPU machine:
Target run-time: 10s
Calibrating test_ints... DONE! Will do 2700000 iterations.
__pool_alloc... DONE! Time 116.988530
__malloc_alloc... DONE! Time 97.573828
__mt_alloc... DONE! Time 77.698650
Relative performance to __pool_alloc:
__malloc_alloc 119.897448 %
__mt_alloc 150.567005 %

alloc_perf_comt_mt.cc, posix threads, dual 1GHz CPU machine:
Target run-time: 10s
Calibrating test_ints... DONE! Will do 2700000 iterations.
__pool_alloc... DONE! Time 86.109538
__malloc_alloc... DONE! Time 98.029429
__mt_alloc... DONE! Time 77.588871
Relative performance to __pool_alloc:
__malloc_alloc 87.840497 %
__mt_alloc 110.981816 %

The conclusion so far is that in non threaded applications this allocator is slower than the default, but then again it's not aimed at this either and it still beats __malloc_alloc (There's probably quite a lot that can be optimized in single mode - this has not been our focus, just getting it to compile).

As expected it's faster than __pool_alloc in mt applications and the more threads the better it performs =) However we could not figure out what we did to accomplish the numbers (from the same testcases/machines) that we initially posted and that we have seen in real world applications that we have used this allocator in. It turns out that an unloaded system and/or this specific way of testing does not tell the whole story (but then again, what does ;-).

While running the tests one can observe the excessive context switching that comes from the global lock in __pool_alloc (alloc_perf_comt_mt.cc, posix threads, dual 1GHz CPU machine, vmstat 5):
   procs                      memory    swap          io     system         cpu
 r  b  w   swpd   free   buff  cache  si  so    bi    bo   in    cs  us  sy  id
 8  0  0      0  10280   3128 425984   0   0     0     0  101 18100  92   8   0
 8  0  0      0  10280   3128 425984   0   0     0     0  101 17606  92   8   0
 8  0  0      0  10280   3128 425984   0   0     0     0  101 23502  90  10   0

The applications that we have been working on has primarily been network services. Simulating some "real world" network traffic is not easy but to demonstrate the effect we have run various applications at the same time as running the mt tests and found that the more the system is loaded/doing the better both __malloc_alloc and __mt_alloc perform. Here's a sample from my workstation (alloc_perf_comt_mt.cc, posix threads, single 1GHz CPU machine) with xmms in the background playing a 128kbit stream:
Target run-time: 10s
Calibrating test_ints... DONE! Will do 2500000 iterations.
__pool_alloc... DONE! Time 143.066890
__malloc_alloc... DONE! Time 93.877978
__mt_alloc... DONE! Time 74.594824
Relative performance to __pool_alloc:
__malloc_alloc 152.396646 %
__mt_alloc 191.791980 %

In "real world applications" the use of per-bin-mutexes also reduces contention quite radically and the fixed size - even though it does consume more memory - virtually eliminates fragmentation.

There are a few things in the patch that needs to be discussed and solved if it's even going to be subject for inclusion in libstdc++ in one form or another:
- There is no __gthread_mutex_init () call in gthr.h. Right now we do a pthread_mutex_init () call to get it working...
- There's a minor issue/ugly workaround related to the supposed parser related bug (see c++/9779 for more details)
- We don't check malloc () calls for errors - it's not clear to us what the libstdc++ "rules" are when it comes to internal error handling and how this is to be reported back to the application.

As I wrote erlier most of our ideas are in this implementation, but future development would include a similar approach to customizing the allocator as described by Phil (see http://gcc.gnu.org/ml/libstdc++/2003-02/msg00319.html) using template arguments etc.

Ciao!

/Stefan & Ola

-- 
Experience is what you get when you were expecting something else.

-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: alloc_perf_comp_single.cc
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20030304/17e8ccfa/attachment.cc>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: alloc_perf_comp_mt.cc
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20030304/17e8ccfa/attachment-0001.cc>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: mtalloc.diff
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20030304/17e8ccfa/attachment.ksh>