[PATCH] Memory Pool + Bucket Allocator

[Jorma Rebane]

This patch adds a custom high performance memory pool implementation to 0 A.D. In addition an STL-compatible custom allocator (bucket_allocator<T>) is included.

Adding memory pools will greatly improve the overall performance of 0 A.D. In order to make this convenient a wrapper header "ps_stl.h" is also included that wraps the STL containers with the custom bucket allocator.

The bucket allocator uses Thread-Local-Storage to create a collection of memory-pools. It is called a bucket allocator because all allocations are divided into sized 'buckets':

Buckets [0..24]		4 8 12 16 20 24 
Buckets [25..64]	32 40 48 56 64 
Buckets [65..128]	80 96 112 128 
Buckets [129..256]	160 192 224 256 
Buckets [257..1024]	384 512 640 768 896 1024

Names of the wrapped stl containers in ps_stl.h:

ps::string
ps::stringstream
ps::wstring
ps::wstringstream
ps::vector<T>
ps::list<T>
ps::map<Key, T>
ps::set<T>
ps::unordered_map<Key, T>
ps::unordered_set<T>

These are the performance comparisons from the patch test suite:

    >> RELEASE Debugger Attached
    std_alloc fragmented:     2614ms
    std_alloc growshrink:     8156ms
    std_alloc temporaries:    86ms
    tls_bucket fragmented:    7ms
    tls_bucket growshrink:    4ms
    tls_bucket temporaries:   3ms
    stress_test std::stl:     628ms
    stress_test ps::stl:      48ms
     
    >> RELEASE No debugger
    std_alloc fragmented:     15ms
    std_alloc growshrink:     13ms
    std_alloc temporaries:    9ms
    tls_bucket fragmented:    5ms
    tls_bucket growshrink:    4ms
    tls_bucket temporaries:   4ms
    stress_test std::stl:     76ms
    stress_test ps::stl:      41ms

After adding this patch, the 0 A.D. source can be changed iteratively to include the new ps_stl.h wrapped containers without having to change the whole codebase.

[historic_bruno]

A few quick thoughts:

• Would it be possible to use namespaces, like ps::vector instead of psvector?
• Since the perf tests are relatively time consuming, we should disable them by default and allow enabling them with a command line option (see test_Pathfinder.h​ for an example)

[Jorma Rebane]

Replying to historic_bruno:

A few quick thoughts:

• Would it be possible to use namespaces, like ps::vector instead of psvector?
• Since the perf tests are relatively time consuming, we should disable them by default and allow enabling them with a command line option (see test_Pathfinder.h​ for an example)

• The initial goal was indeed to use ps:: namespace, but in order to differentiate between std::vector and psvector, I opted for the non-namespace names. This is just to make the transition easier. Once all of it is in the game, we can do a global search & replace.
• Right. The perf tests should indeed be disabled by default.

[Josh]

Compiles and tests fine using default GCC from Ubuntu 13.04 64 bit, test results ​here.

[Jorma Rebane]

Pretty much final. Fixed basic_string wrapper, support for std::string with ps::to_string and ps::string_ref.

[historic_bruno]

Closing these tickets as no further active development is expected. See Philip's megapatch-split git branch for an attempt at splitting megapatch into it's separate parts: ​http://git.wildfiregames.com/gitweb/?p=0ad.git;a=shortlog;h=refs/heads/projects/philip/megapatch-split