Q about ctype.narrow

[Jerry Quinn]

Martin Sebor writes:
 > Jerry Quinn wrote:
 > 
 > ...
 > > Now, call narrow(125, 5) followed by narrow(125,10).  Assuming the
 > > table was inited with 0's, table[125] will get 5, the first time
 > > through, and the second time, we'll return 5 instead of 10.
 > 
 > Good point. I hadn't thought of that.
 > 
 > > 
 > > Fixing this starts to get uglier.  I think you need to detect that
 > > default may get returned and not cache the result in that case:
 > > 
 > > char ctype<char>::narrow(char c, char default)
 > > {
 > >   if (table[c]) return table[c];
 > >   char x = do_narrow(c, default);
 > >   if (x != default) table[c] = x;
 > >   return x;
 > > }
 > > 
 > > Maybe this still speeds things up over always doing do_narrow, but the
 > > complexity seems unpleasant.
 > 
 > Is it really that bad? The only thing that needs to be optimized
 > is successful table lookups, everything else can be outlined:

Good point back :-)

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...

Jerry