Re: [boost] [Intrusive] More compile time parameters

From: Tobias Schwinger (tschwinger_at_[hidden])
Date: 2007-08-09 14:57:23

Rei Thiessen wrote:
> "Tobias Schwinger" <tschwinger_at_[hidden]> wrote in message 
> news:f9elpo$86r$1_at_sea.gmane.org...
>> Interesting. Note, that this optimization does not pay off in general:
>> Worse distribution (no avalanche effect because bits are cut off) ==>
>> more probing ==> more data cache misses.
>>
> 
> If the hash function is poor, then modulo with a prime number will certainly 
> help; however, I don't think containers should be responsible for improving 
> the effectiveness of hash functions. If I already have a fine source of hash 
> values, then applying further (expensive!) operations are of diminishing 
> value.

A prime modulus certainly improves the distribution for the 
(bit-twiddling-based) default hash function in Boost (I've tried it). 
Whether or not it pays off in a concrete case depends on so many 
factors, that it's petty pointless to speculate or argue.

>> Please, no more type template parameters! Add another type member to the
>> traits of that container and keep the primary interface simple, instead.
>>
> (If "traits" here refers to value traits) I don't think bucket pointer, 
> bucket size, and the modulo options belong in the value traits, > since they 
> pertain more to the container than to the templated types. I do support 
> adding a "bucket trait" class, and perhaps folding the SizeType parameter 
> into the bucket trait class as well. (I'm not sure whether converting the 
> currently internal implementation types for the buckets into a trait-based 
> system has been discussed already)

The interface is slightly awkward because of too many template 
arguments, already.

It's fine to split up the configuration into different pieces but then 
let's arbitrate the ordering, applying some kind of policy mixing (e.g. 
a mechanism to provide named arguments as provided by Boost.Parameter).

     container<T, offset_ptr_storage<T>, fixed_bucket_size<256> >

being the same as

     container<T, fixed_bucket_size<256>, offset_ptr_storage<T> >

(once could probably get rid of that 'T' argument to 'offset_ptr_storage').

I'd also like to see a 'T' parameter for straightforwardness

     template< class T, class Policy1 = /unspecified/ , ... >
     class container;

so one could just say

     container<T>

given 'T' provides appropriate hooks.

> The modulo option parameter can perhaps be folded into an expanded concept 
> of a hash function class.

Hmm... Maybe it's better to stick with the standard concepts for the 
hash function.

> 
>> If 'dynamic_bucket_size_policy' is configured in the container's traits,
>> the ctor and the 'set_bucket_size' member function accept an integer. If
>> 'constant_bucket_size_policy' is used an attempt to use an integer will
>> yield a compile error. EBCO can be exploited for a zero-overhead
>> implementation.
> 
> That'll work.

One note about my code: There's actually no need to implement special 
optimization for power of too, since the expression 'x % I', where I is 
a non-type, integral template argument equal to a power of two will be 
translated to an AND instruction by every decent compiler (sorry, I was 
in a bit of a hurry when I wrote it).

Regards,
Tobias