Cool, the golden ratio strikes again.
I have to wonder, though, whether this has a measurable impact
(a) on modern architectures where memory is organized in pages
or (b) in typical programs where one probably has more than
one dynamic data structure growing at a time anyway.
I don't really know. Nominally, with any of the "classical"
allocation algorithms, if you have one vector which just grows
and grows, it eventually migrates to the end of the free space
arena (because it becomes bigger than any of the holes), and
this factor could possibly affect just how large you could make
it grow. Except, of course, that you'll likely bring the
machine to its knees through paging before that. And that there
are enough additional factors involved that it's not certain
that the rule really changes anything.
Just out of curiousity, during my lunch hour, I wrote a simple
allocator and tested the principles. Using some simple
multipliers, I get the following output:
For 1.10: max size = 389582583 (39.0%)
For 1.20: max size = 389586745 (39.0%)
For 1.30: max size = 513088587 (51.3%)
For 1.40: max size = 477760691 (47.8%)
For 1.50: max size = 419279977 (41.9%)
For 1.60: max size = 432051256 (43.2%)
For 1.70: max size = 360273482 (36.0%)
For 1.80: max size = 307547665 (30.8%)
For 1.90: max size = 328691801 (32.9%)
For 2.00: max size = 268435456 (26.8%)
Change just about any of the parmeters, however, and you get
something different: using an initial size of 500 (rather than
128) results in:
For 1.10: max size = 374691238 (37.5%)
For 1.20: max size = 519586870 (52.0%)
For 1.30: max size = 420105341 (42.0%)
For 1.40: max size = 488743519 (48.9%)
For 1.50: max size = 323374783 (32.3%)
For 1.60: max size = 259493561 (25.9%)
For 1.70: max size = 288397093 (28.8%)
For 1.80: max size = 371637543 (37.2%)
For 1.90: max size = 357024500 (35.7%)
For 2.00: max size = 262144000 (26.2%)
Change the size of the arena from 1000000000 to 500000000, and
you get:
For 1.10: max size = 219909214 (44.0%)
For 1.20: max size = 225455293 (45.1%)
For 1.30: max size = 233540550 (46.7%)
For 1.40: max size = 174111040 (34.8%)
For 1.50: max size = 279519985 (55.9%)
For 1.60: max size = 168770022 (33.8%)
For 1.70: max size = 124662105 (24.9%)
For 1.80: max size = 170859814 (34.2%)
For 1.90: max size = 172995685 (34.6%)
For 2.00: max size = 134217728 (26.8%)
For the moment, I'm not sure what one can really conclude
.
Anyhow, for those interested, here's the code. It uses my
library, but only a few simple things from it, which can easily
be replaced. Also, it's entirely possible that I've got an
error somewhere in it (it was written very quickly), which could
explain the randomness of the results as well.
-------------- fill.cc ----------------
#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <new>
#include "gb/FFmt.hh"
#include "gb/CommandLine.hh"
#include "gb/NumericOption.hh"
Gabi::BoundNumericOption
arenaSize( 'a', 1000000000 ) ;
Gabi::BoundNumericOption
startSize( 's', 128 ) ;
Gabi::BoundNumericOption
intervalCount( 'i', 10 ) ;
class Pool
{
public:
explicit Pool( size_t size = arenaSize ) ;
~Pool() ;
void* allocate( size_t n ) ;
void free( void* p ) ;
private:
struct BlockHeader
{
BlockHeader* next ;
bool isFree ;
} ;
void* base ;
BlockHeader* first ;
inline void* add( void* p, size_t n )
{
return static_cast< char* >( p ) + n ;
}
inline size_t diff( void* p1, void* p2 )
{
return static_cast said:
}
} ;
void
testPool(
double ratio )
{
Pool p ;
size_t s = startSize ;
void* v = p.allocate( s ) ;
while ( v != NULL ) {
size_t s2 = (size_t)( ratio * s ) ;
void* v2 = p.allocate( s2 ) ;
p.free( v ) ;
v = v2 ;
if ( v != NULL ) {
s = s2 ;
}
}
std::cout << "For " << Gabi::FFmt( 4, 2 ) << ratio
<< ": max size = " << std::setw( 9 ) << s
<< " (" << Gabi::FFmt( 4, 1 ) << 100.0 * s / arenaSize
<< "%)"
<< std::endl ;
}
int
main( int argc, char** argv )
{
Gabi::CommandLine::instance().parse( argc, argv ) ;
for ( int i = 1 ; i <= intervalCount ; ++ i ) {
testPool( 1.0 + i / static_cast< double
( intervalCount.value() ) ) ;
}
return 0 ;
}
Pool:
ool(
size_t size )
{
base = std::malloc( size ) ;
if ( base == NULL ) {
throw std::bad_alloc() ;
}
first = static_cast< BlockHeader* >( base ) ;
BlockHeader* last
= static_cast< BlockHeader* >(
add( first, size - sizeof( BlockHeader ) ) ) ;
first->next = last ;
first->isFree = true ;
last->next = NULL ;
last->isFree = false ;
}
Pool::~Pool()
{
std::free( base ) ;
}
void*
Pool::allocate(
size_t n )
{
n += sizeof( BlockHeader ) ;
n = (n + 7) & (static_cast< size_t >( -1 ) << 3) ;
BlockHeader* result = NULL ;
BlockHeader* b = first ;
while ( result == NULL && b != NULL ) {
if ( b->isFree ) {
while ( b->next->isFree ) {
b->next = b->next->next ;
}
if ( diff( b, b->next ) > n ) {
result = b ;
}
}
b = b->next ;
}
if ( result != NULL ) {
if ( diff( result, result->next ) > n +
sizeof( BlockHeader ) ) {
BlockHeader* newNext
= static_cast< BlockHeader* >( add( result,
n ) ) ;
newNext->next = result->next ;
newNext->isFree = true ;
result->next = newNext ;
}
result->isFree = false ;
++ result ;
}
return result ;
}
void
Pool::free(
void* p )
{
if ( p != NULL ) {
BlockHeader* b = static_cast< BlockHeader* >( p ) - 1 ;
b->isFree = true ;
}
}
---------------- ------- ----------------
