Re: Q about ctype.narrow

[Martin Sebor <sebor at roguewave dot com>]

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