This is the mail archive of the mailing list for the libstdc++ project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Change to search_n

Paolo Carlini wrote:

Chris Jefferson wrote:


Hi and thanks for your message.

During the next days I will analyze in detail your proposal but, first, I'd like to ask your whether your work is related to this algorithm which we were already finding very interesting:

My minor fix, and more extensive fix turn out to be.. identical to the things discussed in this article :) I did come up with it independantly (I originally investigated the algorithm because I was using it, looked it up in my STL manual and was shocked to find the complexity being far higher than I expected).

I had thought about the final part of his dicussion (how even in non-random access partners the number of comparisions can be reduced at the cost of moving through iterators more). This would be useful when comparisons are expensive, but not so in general.

However, it could still be useful, using a little bit of lookahead when pointers can be stored in a register I think (ie just pop forward 2 iterator positions, storing all of them in registers, then check the third one to see if it matches. If so, pop back and check the other 2. This shouldn't cost anything and posibily save some comparisons).

One other thing I think could slightly improve efficency would be to alter the random access version of find (which skips along in 4s) to instead of having a trip_count variable, instead reduce the __last iterator by (__last-__first)%4, and then continue as normal. One thing that pops up from there, is >> 2 really still considered faster than /4, and is that a legal thing to do?

Thank you,


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]