Re: [Boost-users] [Fusion] Views of Associative Sequences

Subject: Re: [Boost-users] [Fusion] Views of Associative Sequences
From: Christopher Schmidt (mr.chr.schmidt_at_[hidden])
Date: 2009-10-16 09:37:54

Joel de Guzman schrieb:
> Nate Knight wrote:
>> Joel de Guzman <joel <at> boost-consulting.com> writes:
>>
>>> And in case you are wondering, Christopher Schmidt's wonderful
>>> c++0x port will be the future of fusion.
>>>
>>> Regards,
>>
>> Cool.  The port looks really nice.  After looking through the code, 
>> I've got a
>> couple of questions.  The most direct one regards the implementation 
>> of at_key
>> for set and map.  The implementation seems to have changed 
>> considerably from the
>> 1.40 version.  If I'm reading things correctly at_key is now 
>> implemented using a
>> new find_key algorithm whereas the 1.40 version used some function 
>> overloading
>> mechanism.  Is there any run-time performance difference between the two
>> approaches?  It looks as if find_key is a constant time algorithm.  Am 
>> I correct
>> in my understanding?
> 
> I'd guess it would be the same. I'm not so sure about compile rime
> performance though. I'll let Christopher provide details. At any
> rate, I'd urge Christopher to add more benchmarks. I started one
> a long time ago, but it needs to be beefed up, especially with the
> upcoming 0x port.
> 
> Regards,

My implementation introduces associative iterators. An associative 
forward sequence shall provide an iterator that allows direct mapping 
from the iterator (type) to the underlying element (type), key type and 
the actual value (type) associated with the key.
I split fusion::find up in fusion::find_key and a new fusion::find. My 
fusion::find does not care about the associative-ness of the sequence. 
It searches for a plain element type. That is it returns the first 
iterator for which is_same<fusion::result_of::value_of<mpl::_1>, Elem> 
evaluates to true, or an end-iterator. fusion::find_key returns the 
first iterator for which is_same<fusion::result_of::key_of<mpl::_1>, 
Key> evaluates to true, or an end-iterator.

The compile-time evaluation of a 
fusion::(result_of::)find_key-invocation should scale linear to the 
number of elements of the sequence being searched on. The 
fusion::find_key implementation uses fusion::detail::static_seq_find_if, 
which is 4-unrolled optimized.
This should be slightly faster compared to the unoptimized 
implementation of fusion::map<...>/set<...>::(meta_)find_impl(_const), 
which are plain recursive metafunctions/n-overloaded functions.
The runtime performance of my port should be better if the compiler 
supports rvalue references. If not, there should not be a difference in 
any case at all. For fusion::find, the run-time performance is of course 
constant.
The "old" implementation uses a distinct intrusive (meta-)function, 
analogue to find, to implement at_key. I implemented fusion::at_key 
based on fusion::find_key.

For more information on my port, have a look at the posts over at the 
development mailing list.

http://article.gmane.org/gmane.comp.lib.boost.devel/194322

-Christopher