[Intrusive] More compile time parameters
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
Hi, just some comments, having discussed some related material just yesterday (note I'm *not* an author of the library). Rei Thiessen wrote:
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.
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.
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.
Please, no more type template parameters! Add another type member to the traits of that container and keep the primary interface simple, instead.
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.
1) and 2) can nicely be combined (see below).
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.
Well, not necessarily: template< size_t BucketSize > class constant_bucket_size { public: constant_bucket_size() { } size_t get_bucket_size() const { return BucketSize; } size_t modulate(size_t value) { // metaprogram that decides whether to use & or % } }; class dynamic_bucket_size { size_t val_bucket_size; public: /* implicitly converting */ dynamic_bucket_size(size_t bucket_size) { } size_t get_bucket_size() const { return this->val_bucket_size; } size_t modulate(size_t value) { return value % thos->val_bucket_size; } }; template // ... class container // ... { public: typedef typename Traits::bucket_size bucket_size; container(... , bucket_size const& bs = bucket_size() ); void set_bucket_size(bucket_size const& bs); }; 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.
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.
That's pretty much "non-intrusive Intrusive", again, which we have been discussing yesterday ;-). So 3) can probably be generalized further and applied to all containers (see yesterday's posts). 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).
Combining 2) and 3), we can develop a single concept: As an example...
<code> Why are you assuming that a constant bucket size should always be a power of two? Regards, Tobias
"Tobias Schwinger" <tschwinger@isonews2.com> wrote in message news:f9elpo$86r$1@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
Rei Thiessen wrote:
"Tobias Schwinger" <tschwinger@isonews2.com> wrote in message news:f9elpo$86r$1@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
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@isonews2.com> wrote in message news:f9fo2i$1ul$1@sea.gmane.org...
Rei Thiessen wrote:
"Tobias Schwinger" <tschwinger@isonews2.com> wrote in message news:f9elpo$86r$1@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
In both of the implementations of mapped_file_source and mapped_file_sink, the devices are not seekable (whereas basic_array_source and basic_array_sink are). I am wondering whether there is a rationale for this, or whether it was simply an oversight in development. Since mapped_files are still contiguous piece of memory I see no reason why they should not be seekable. On a side note, should a direct_tag not imply ssekable_device_tag i.e., struct direct_tag : seekable_device_tag {};
Schalk Cronje wrote:
In both of the implementations of mapped_file_source and mapped_file_sink, the devices are not seekable (whereas basic_array_source and basic_array_sink are).
I am wondering whether there is a rationale for this, or whether it was simply an oversight in development. Since mapped_files are still contiguous piece of memory I see no reason why they should not be seekable.
No. Because the DirectDevice doesn't have a stream position. The DirectDevice is not strictly a Device. If you use the class direct_adapter, you can get a Seekable. See also: #include <boost/iostreams/detail/adapter/direct_adapter.hpp> Regards, Takeshi Mouri
participants (4)
-
Rei Thiessen -
Schalk_Cronje＠McAfee.com -
Takeshi Mouri -
Tobias Schwinger