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

From: Rei Thiessen (reittsm_at_[hidden])
Date: 2007-08-09 07:48:07

"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.

> 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 modulo option parameter can perhaps be folded into an expanded concept 
of a hash function class.

>
> 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.

> BTW: Zero-sized objects do not exist in C++ (EBCO allows empty
> subobjects to be mapped to the same address and thus take up no extra
> space - a concrete object, however, takes up at least one byte, so
> pointer comparison can be used for checking object identity).
>

The goal is to use placement operator new to construct the container object 
directly on top of the bucket array, relying on the object having no 
members. Although then it seems silly to do such a convoluted thing just for 
the sake of using thiscalls and perhaps the library could just expose "hash 
table algorithms" as free functions.

>
> Why are you assuming that a constant bucket size should always be a
> power of two?
>

They were just examples ;)

Regards,
RT