Re: [boost] Proposal: Monotonic Containers - Comparison with boost::pool and boost::fast_pool

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