Updated tests (more of them, better formatting of results) for https://svn.boost.org/svn/boost/sandbox/monotonic/libs/monotonic/test/compar... here http://tinyurl.com/m83vll for GCC and here http://tinyurl.com/n9g8jv for MSVC. I also added a column for std::allocator/mono. On Fri, Jun 19, 2009 at 1:31 PM, Christian Schladetsch < christian.schladetsch@gmail.com> wrote:

Hello,

I ran the following test http://tinyurl.com/l89llq

This compares std::allocator, boost::fast_pool_allocator, boost::pool_allocator and monotonic::allocator.

The only test in which monotonic allocation fails to perform faster than the other schemes is thrash_pool_sort_list_int against fast_pool. The reason for this is that fast_pool effectively stores a pre-generated array of correctly-aligned chunks, so allocation against this is a pointer increment.

Fast pool can do this, because it stores different pools for different-sized blocks. Rather, the monotonic allocator uses a single buffer for all allocations, so it has to align each time. There is an optimisation I can introduce between a monotonic::allocator<T> and the underlying storage that can improve performance slightly for this case.

The downside for fast_pool is that the user has to keep track of each different-sized chunk that can possiblly be used, and it doesn't differentiate on type. From the documentation:

"Since the size of T is used to determine the type of the underlying Pool, each allocator for different types of the same size will share the same underlying pool. The tag class prevents pools from being shared between pool_allocator and fast_pool_allocator. For example, on a system where sizeof(int) == sizeof(void *), pool_allocator<int> and pool_allocator<void *> will both allocate/deallocate from/to the same pool."

This is problematic for cases where a given allocator is rebound to a different type, as happens for the node-based containers. I am unsure what the best practise is here, or if boost::pool and boost::fast_pool simply leak in this case.

You will also not that fast_pool is very slow for thrash_pool_sort, which sorts different-sized vectors. Here, the same mechanism that made it %10-%20 faster than monotonic using lists makes it many times slower when using vectors.

In the following tables, the first row is the maximum number of elements in the relevant container; all internal columns are in seconds.

Results for MSVC /O2.

thrash_pool count fast_p pool std mono local fp/mono pool/mono 10 0.015 0.019 0.02 0.005 0.005 300% 380% 210 0.035 0.037 0.038 0.01 0.009 350% 370% 410 0.051 0.055 0.04 0.013 0.013 392.3% 423.1% 610 0.069 0.072 0.046 0.017 0.017 405.9% 423.5% 810 0.088 0.093 0.048 0.021 0.022 419% 442.9% 1010 0.105 0.111 0.053 0.026 0.028 403.8% 426.9% 1210 0.125 0.138 0.06 0.031 0.03 403.2% 445.2% 1410 0.142 0.143 0.061 0.034 0.033 417.6% 420.6% 1610 0.164 0.162 0.069 0.038 0.038 431.6% 426.3% 1810 0.179 0.184 0.072 0.043 0.042 416.3% 427.9% thrash_pool_iter count fast_p pool std mono local fp/mono pool/mono 10 0.027 0.032 0.032 0.012 0.011 225% 266.7% 210 0.152 0.146 0.118 0.102 0.101 149% 143.1% 410 0.27 0.263 0.199 0.191 0.189 141.4% 137.7% 610 0.4 0.372 0.286 0.283 0.284 141.3% 131.4% 810 0.509 0.487 0.376 0.372 0.372 136.8% 130.9% 1010 0.64 0.598 0.474 0.474 0.464 135% 126.2% 1210 0.765 0.721 0.579 0.563 0.592 135.9% 128.1% 1410 0.895 0.841 0.632 0.662 0.652 135.2% 127% 1610 0.991 0.923 0.701 0.714 0.759 138.8% 129.3% 1810 1.185 1.096 0.793 0.91 0.842 130.2% 120.4% thrash_pool_sort count fast_p pool std mono local fp/mono pool/mono 10 0.01 0.002 0.002 0.001 0.001 1000% 200% 110 0.091 0.011 0.011 0.008 0.009 1138% 137.5% 210 0.233 0.023 0.02 0.017 0.016 1371% 135.3% 310 0.495 0.034 0.026 0.025 0.025 1980% 136% 410 1.347 0.044 0.036 0.035 0.034 3849% 125.7% 510 1.411 0.058 0.045 0.042 0.042 3360% 138.1% 610 2.928 0.067 0.055 0.052 0.053 5631% 128.8% 710 2.54 0.078 0.064 0.065 0.061 3908% 120% 810 6.175 0.089 0.073 0.07 0.07 8821% 127.1% 910 3.976 0.104 0.081 0.082 0.08 4849% 126.8% thrash_pool_sort_list_int count fast_p pool std mono local fp/mono pool/mono 10 0.006 0.011 0.011 0.003 0.004 200% 366.7% 210 0.057 0.087 0.088 0.06 0.059 95% 145% 410 0.102 0.214 0.169 0.135 0.125 75.56% 158.5% 610 0.156 0.367 0.254 0.199 0.196 78.39% 184.4% 810 0.211 0.588 0.346 0.26 0.261 81.15% 226.2% 1010 0.269 0.837 0.459 0.351 0.35 76.64% 238.5% 1210 0.347 1.16 0.547 0.441 0.431 78.68% 263% 1410 0.406 1.504 0.632 0.54 0.511 75.19% 278.5% 1610 0.481 1.882 0.728 0.583 0.587 82.5% 322.8% 1810 0.559 2.32 0.817 0.671 0.674 83.31% 345.8% thrash_pool_map_list_unaligned count fast_p pool std mono local fp/mono pool/mono 10 0.002 0.003 0.004 0.001 0.001 200% 300% 210 0.033 0.083 0.079 0.029 0.029 113.8% 286.2% 410 0.067 0.214 0.164 0.058 0.061 115.5% 369% 610 0.102 0.404 0.246 0.091 0.092 112.1% 444% 810 0.139 0.646 0.338 0.122 0.126 113.9% 529.5% 1010 0.174 0.936 0.415 0.155 0.16 112.3% 603.9% 1210 0.219 1.271 0.51 0.19 0.197 115.3% 668.9% 1410 0.253 1.675 0.594 0.23 0.237 110% 728.3% 1610 0.297 2.144 0.678 0.273 0.274 108.8% 785.3% 1810 0.339 2.692 0.874 0.402 0.313 84.33% 669.7%

Results for GCC -O2 thrash_pool count fast_p pool std mono local fp/mono pool/mono 10 0 0.01 0 0.01 0 0% 100% 210 0.01 0.01 0.01 0 0 inf% inf% 410 0.01 0 0.01 0.01 0 100% 0% 610 0.01 0.01 0.01 0 0 inf% inf% 810 0.01 0 0.01 0.01 0 100% 0% 1010 0 0.01 0 0 0.01 nan% inf% 1210 0.01 0.01 0.01 0 0 inf% inf% 1410 0.01 0 0.01 0 0.01 inf% nan% 1610 0 0.01 0.01 0 0 nan% inf% 1810 0 0.01 0 0 0.01 nan% inf% thrash_pool_iter count fast_p pool std mono local fp/mono pool/mono 10 0.01 0.01 0 0.01 0 100% 100% 210 0.05 0.06 0.02 0.02 0.02 250% 300% 410 0.12 0.1 0.04 0.03 0.03 400% 333.3% 610 0.16 0.15 0.05 0.05 0.04 320% 300% 810 0.2 0.21 0.06 0.06 0.07 333.3% 350% 1010 0.25 0.25 0.07 0.08 0.08 312.5% 312.5% 1210 0.29 0.31 0.08 0.08 0.09 362.5% 387.5% 1410 0.33 0.35 0.1 0.08 0.1 412.5% 437.5% 1610 0.38 0.37 0.11 0.12 0.12 316.7% 308.3% 1810 0.43 0.45 0.12 0.13 0.13 330.8% 346.2% thrash_pool_sort count fast_p pool std mono local fp/mono pool/mono 10 0.01 0.01 0 0 0 inf% inf% 110 0.06 0.01 0.01 0.01 0.01 600% 100% 210 0.19 0.02 0.02 0.02 0.01 950% 100% 310 0.47 0.02 0.02 0.02 0.02 2350% 100% 410 0.69 0.04 0.04 0.03 0.02 2300% 133.3% 510 1.99 0.05 0.04 0.03 0.04 6633% 166.7% 610 1.65 0.06 0.04 0.04 0.04 4125% 150% 710 4.73 0.07 0.05 0.04 0.05 1.182e+04% 175% 810 2.28 0.07 0.07 0.06 0.06 3800% 116.7% 910 4.29 0.09 0.05 0.08 0.06 5362% 112.5% thrash_pool_sort_list_int count fast_p pool std mono local fp/mono pool/mono 10 0 0.01 0 0 0 nan% inf% 210 0.03 0.05 0.04 0.04 0.03 75% 125% 410 0.07 0.15 0.1 0.08 0.06 87.5% 187.5% 610 0.1 0.26 0.12 0.11 0.12 90.91% 236.4% 810 0.13 0.39 0.19 0.18 0.14 72.22% 216.7% 1010 0.17 0.57 0.24 0.19 0.2 89.47% 300% 1210 0.24 0.74 0.29 0.23 0.24 104.3% 321.7% 1410 0.26 0.98 0.36 0.26 0.28 100% 376.9% 1610 0.27 1.21 0.37 0.3 0.33 90% 403.3% 1810 0.35 1.51 0.43 0.35 0.37 100% 431.4% thrash_pool_map_list_unaligned count fast_p pool std mono local fp/mono pool/mono 10 0 0 0 0 0 nan% nan% 210 0.02 0.05 0.03 0.02 0.02 100% 250% 410 0.02 0.11 0.06 0.04 0.04 50% 275% 610 0.06 0.19 0.11 0.07 0.07 85.71% 271.4% 810 0.06 0.33 0.13 0.09 0.08 66.67% 366.7% 1010 0.09 0.51 0.17 0.11 0.11 81.82% 463.6% 1210 0.12 0.65 0.21 0.13 0.14 92.31% 500% 1410 0.15 0.93 0.25 0.14 0.14 107.1% 664.3% 1610 0.17 1.11 0.27 0.19 0.15 89.47% 584.2% 1810 0.18 1.35 0.33 0.21 0.21 85.71% 642.9%

Regards, Christian