Subject: Re: [boost] Proposal: Monotonic Containers - Comparison with boost::pool and boost::fast_pool
From: Christian Schladetsch (christian.schladetsch_at_[hidden])
Date: 2009-06-18 21:31:14
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