[Boost-users] Pool ordered_malloc and O(n)

Subject: [Boost-users] Pool ordered_malloc and O(n)
From: Georg Sauthoff (g_sauthoff_at_[hidden])
Date: 2009-02-17 15:33:56

Hi,

the boost pool documentation states ordererd_malloc(n) and boost::free(chunk,
n) both take O(n). I tested it with a workload of a lot of n=1 and n=2
small allocations.

Basically if I just use boost::malloc(2*base_size) even if i just need
boost::malloc(base_size) the runtime is 1 min. With
ordered_malloc(_)/boost::free(_,_) the runtime explodes (>> 30 minutes)
(I terminated the program).  Profiling it, one can see, that
ordered_malloc dominates the runtime (83 % after a few minutes).

Is this a known issue? Is the runtime of ordered_malloc in O(n), i.e. in
O(c\cdot n), but the constant factor c is very huge?

Best regards
Georg Sauthoff