Q about ctype.narrow

[Martin Sebor]

Jerry Quinn wrote:

...
> I think optimizing the array version will be harder.  The catch of
> course is the need to test whether we have a cached value - again
> defeating some of the speed advantage of the loop.  So the candidate
> function looks like:
> 
> char* ctype<char>::narrow(char* lo, char* hi, char default, char* dest)
> {
>   for (; lo != hi; ++dest,++lo) {
>     *dest = table[*lo] ? table[*lo] : do_narrow(*lo, default);
>   }
>   return hi;
> }
> 
> This assumes we prefill the table rather than fill on demand.  Now
> compare to the current version of array do_narrow():
> 
> char* ctype<char>::do_narrow(char* lo, char* hi, char default, char* dest)
> {
>   memcpy(dest, lo, hi-lo);
>   return hi;
> }
> 
> So the question is whether a virtual call followed by call to memcpy
> is faster or slower than the first loop doing a test every iteration.
> I'm not considering the case where do_narrow gets called in the first
> function, since that would only happen in a derived class.
> 
> I'll have to benchmark it...

I suspect this will be a No Contest :) (I.e., the virtual call will
be a lot faster than the loop with the conditional in the general
case).

But I think there is quite a bit of room for improvement. In the
common case, the cache will be fully populated (i.e., no unfilled
slots) with consecutive values from 0 through UCHAR_MAX, so the
loop can be replaced with a memcpy:

inline char*
ctype<char>::narrow(char* lo, char* hi, char dfault, char* dest)
{
   if (cache_consecutive)
       memcpy (dest, lo, hi - lo);
   else
       __narrow (lo, hi, dfault, dest);
   return hi;
}

/* out-of-line */ char*
ctype<char>::__narrow(char* lo, char* hi, char dfault, char* dest)
{
   if (cache_empty) {
        const char s[] = { 0, ..., UCHAR_MAX };
        do_narrow (s, s + sizeof s, 0, cache);
        cache_consecutive = !memchr (cache + 1, 0, sizeof cache - 1);
        cache_empty = false;
   }

   if (cache_consecutive)
       memcpy (dest, lo, hi - lo);
   else {
       for (; lo != hi; ++lo, ++dest)
           *dest = table [*lo] ? table [*lo] : dfault;
   }

   return hi;
}

Martin