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

From: Rei Thiessen (reittsm_at_[hidden])
Date: 2007-08-17 05:00:01

> That's pretty much "non-intrusive Intrusive", again, which we have been
> discussing yesterday ;-).

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

I am arguing from the database implementation point-of-view, where it would 
be convenient to define the type of a header-less page as a 
boost::compressed_pair<unordered_set<...>,void*[1024]>; thus I expressed my 
wish for empty-sized containers and non-modulo ops. These intrusive 
containers are so close to perfect that it's painful to have to modify them.

RT

"Tobias Schwinger" <tschwinger_at_[hidden]> wrote in message 
news:f9fo2i$1ul$1_at_sea.gmane.org...
> 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
>
> _______________________________________________
> Unsubscribe & other changes: 
> http://lists.boost.org/mailman/listinfo.cgi/boost
>