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-19 01:58:46

Updated tests (more of them, better formatting of results) for
https://svn.boost.org/svn/boost/sandbox/monotonic/libs/monotonic/test/compare_memory_pool.cppis
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_at_[hidden]> 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
>
>