This is the mail archive of the libstdc++@gcc.gnu.org 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


Hi :)
Hi Chris, hi list,

<snip>

Its mainly the expressions like (__last - __first >
__count) that are producing these warnings. These
expression will fail to work as expected in case
__first > __last.

I think we just have to careful with these tests :)

<snip>
According to my tests, my new implementation seems to
perform better than the old one in most cases (though
there are circumstances when it performs slightly
worse) and is testing less elements in all cases.
Particularly, when the probability of meeting a
matching element is high, it performs great. In the
example I have mentioned in a previous mail (test D of
my article) your implementation is testing 16% of the
overtaken elements, my old implementation is testing
14% of the overtaken elements and my newest one only
10.7% of the overtaken elements. I have to admit that
when the element comparison itself is very fast, then
my new implementation is not always faster in all
compilers, but in case that the comparison is
non-trivial then it really takes off. :)

I'm of the opinion that a slight decrease in performance in some cases is acceptable as long as many other cases increase dramatically :)


The main problem I had with my previous version was that i wasn't getting much improvement for when the integer parameter was 2..


Bellow I include a draft of this new implementation
and I waiting for your comments.

//---------------------------------------------------

template <class _RandomAccessIter, class _Integer,
class _Tp> inline
Only a tiny thing, I think this is perhaps a little large to inline :)
_RandomAccessIter search_n(_RandomAccessIter __first,
_RandomAccessIter __last,
                      _Integer __count, const _Tp&
__val)
{
	if (__count <= 0)
		return __first;
	if (__count == 1)
		return std::find(__first, __last, __val);

	typedef
std::iterator_traits<_RandomAccessIter>::difference_type
iter_diff;

	iter_diff __tailSize = __last - __first;
	iter_diff __pattSize = __count;

	if (__tailSize >= __pattSize)
	{
		_RandomAccessIter __backTrack;

		iter_diff __remainder, __prevRemainder;
		iter_diff __skipOffset = __pattSize - 1;
		
		_RandomAccessIter __lookAhead = __first +
__skipOffset;

		for ( ; ; __lookAhead += __pattSize ) // the main
loop...
		{
			//__lookAhead here is always pointing to the last
element of next possible match.
			assert( __tailSize >= __pattSize );
			__tailSize -= __pattSize;

			for ( ; ; ) // the skip loop...
			{
				if (*__lookAhead == __val)
					break;
				if (__tailSize < __pattSize)
					return __last;
				
				__lookAhead += __pattSize;
				__tailSize -= __pattSize;
			}
			
			assert( __tailSize == (__last - __lookAhead) - 1 );
			__remainder = __skipOffset;
			
			for ( __backTrack = __lookAhead - 1; *__backTrack
== __val; --__backTrack )
			{
				if (--__remainder == 0)
					return (__lookAhead - __skipOffset); //Success
			}

			for ( ; ; )
			{
				if (__remainder > __tailSize)
					return __last; //failure

				__lookAhead += __remainder;
				__tailSize -= __remainder;

				if (*__lookAhead == __val)
				{
					__prevRemainder = __remainder;
					__backTrack = __lookAhead;

I know quite a lot of people don't like do { ... } while loops, although in this case it looks like the sensible option.
					do
					{
						if (--__remainder == 0)
							return (__lookAhead - __skipOffset); //Success

					} while ( *--__backTrack == __val);
					
					//adjust remainder for next comparison
					__remainder += __skipOffset - __prevRemainder;
				}
				else
					break;
			}

			//__lookAhead here is always pointing to the
element of the last mismatch.
			if (__tailSize < __pattSize)
				return __last;
		}
	}
	
	return __last; //failure
}

Generally it looks good to me, I don't really have much else to say :) My only very slight worry is that as these algorithms are fiddled with they get ever larger :)


Chris


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