[boost] [Intrusive] More compile time parameters

From: Rei Thiessen (reittsm_at_[hidden])
Date: 2007-08-09 02:56:53

Hello,

(my version of the library is intrusive.2007-03-04.zip. Is there a more
recent version?)

I have three suggestions:

1) The containers uses a modulo operation to map the hash value range into
the bucket index domain. When using a bucket size that is an order of 2, the
excess cost of the div instruction is unneeded. This was a critical issue
for me.

There can be a new templated type parameter for specifying a functor that
takes the hash output value and the bucket size as inputs and outputs the
bucket index.  The default type of this template parameter can simply be
std::modulus.

2) Each container stores the bucket size. This is too an unneeded excess in
certain circumstances. If the containers had a (optional) templated constant
parameter that determined its bucket size, then the container memory
footprint can be reduced at the expense of bloating the code segments with
multiple instantiations. This memory saving is crucial when deploying
numerous small hash container objects.

This new templated constant parameter has interface ramifications. We would
require two specializations of the container class: the run-time bucket size
specialization is what we have today; for the compile-time bucket size
container, the constructors would not have "size_type buckets_len"
parameters.

3) Now, if we add another templated type parameter for specifying a functor
that takes the object 'this' pointer as input and outputs the memory address
of the bucket array, then we can reduce the memory cost of each container to
zero.

Combining 2) and 3), we can develop a single concept:  As an example...

struct default_bucket_info
{
   /* appropriate constructors... */
   bucket_ptr  buckets_;
   size_type   buckets_len_;
   template<class T> bucket_ptr buckets( T* container ) const { return
buckets_; }
   size_type buckets_len() const { return buckets_len_; }
}

Realizing 2):

template< unsigned n >
struct bucket_info_size_n
{
   /* appropriate constructors... */
   bucket_ptr  buckets_;
   template<class T> bucket_ptr buckets( T* container ) const { return
buckets_; }
   size_type buckets_len() const { return 1<<n; }
}

Realizing 2) and 3):

template< unsigned n >
struct bucket_info_in_place_size_n
{
   template<class T> bucket_ptr buckets( T* container ) const { return
(bucket_ptr)container; }
   size_type buckets_len() const { return 1<<n; }
}

Applying these concepts, I think we can reach a balance between having a
concrete container class and having a collection of free container algorithm
functions.  (If only C++ would adopt C99's VLAs, 3) can be far more
elegant...)

Are there any drawbacks to extending the unordered associative container
classes with these concepts?
(I will be modifying my copy of the library with these changes for my
personal needs)

RT