Re: [PATCH] SBuf c-string comparisons

On 04/17/2014 04:43 AM, Amos Jeffries wrote:
> On 17/04/2014 7:23 a.m., Alex Rousskov wrote:
>> Any reasonable/popular implementation selected by the developer. This is
>> a one-time check done by the developer, not an automated check done
>> during Squid build. Sorry I was not clear about that.

> So glibc: a do-while loop scanning word-by-word with individual
> byte-by-byte loop (unrolled) over the bytes in each word.

Yeah (if by "word" you mean "4 characters"). The important part here is
that they _are_ trying to optimize the scan using low level tricks such
as partial loop unrolling. That makes the cloning approach more
attractive than if they did not, but I am not sure it makes it
attractive enough. I am still OK with the hand-rolled loops direction,
as your latest patch suggests.

> The cloning mechanism uses strlen() internally. So no benefit, but extra
> malloc+free costs.

AFAICT, cloning should not call strlen(). We are cloning the SBuf object
("this") which has a known length. We are not cloning the c-string. The
only purpose of cloning is null termination of "this" -- SBuf::c_str()
is not a constant method. Terminating "this" is enough to use the
standard strncmp().

> Patch with hand-rolled scanner attached.

> + // 0-length comparison is always true regardless of buffer states
> + if (!n || (!length() && *s=='\0')) {
> + ++stats.compareFast;
> + return 0;
> + }
> +
> + // N-length compare MUST provide a non-NULL C-string pointer
> + assert(s);

The assertion appears too late to save us from dereferencing NULL s in
the if-statement code above. I suggest carefully removing that overly
complicated if-statement (adjusting the rest of the code accordingly).

    assert(!n || s);
    ... adjusted loops go here ...

I do not insist on removing the if-statement, but if you keep it, please
adjust it so that it asserts instead of dereferencing NULL s from broken
callers.

> + size_type byteCount = min(length(), n);

Using npos in min() makes me uncomfortable but should work because
size_type is unsigned. If you keep this code, please add a comment. For
example:

  // n may be npos, but we treat that as a huge positive value

> + while ((rv = *left - *right++) == 0) {

"left" may point beyond allocated memory if length() is zero but *s is not.

> + if (length() < n)
> + return '\0' - *right;

"right" might also point beyond allocated memory by now -- it was
unconditionally incremented in the loops and I do not think the non-zero
byteCount check protects us from reaching this code in some cases.

> + size_type byteCount = min(length(), n);
...
> + while ((rv = *left - *right++) == 0) {
> + if (*left++ == '\0' || --byteCount == 0)
> + break;

byteCount may underflow here (become huge) if it starts as zero because
length() is zero.

> + while ((rv = *left - *right++) == 0) {
> + if (*left++ == '\0' || --byteCount == 0)
> + break;

This loop in conjunction with mind boggling after-loop checks is just
too smart for the human brains IMHO. This level of complexity creates a
constant trickle of bugs. Please consider a more straightforward
approach that is nearly as efficient. Here is a sketch:

{
  assert(!n || s);
  ...
  const char *left = buf();
  leftCount = length();
  const char *right = s; // or just rename s to right?
  // n may be npos, but we treat that as a huge positive value
  while (n) {
    const c1 = leftCount-- ? *left++ : '\0';
    const c2 = *right++;
    if (!c1 || c1 != c2) // covers !c2 as well
        return c1 - c2;
    n--;
  }
  // all n characters were identical (and none was \0)
  return 0;
}

The above requires some polishing (such as adding c1/2 types and a
case-insensitive loop) but, AFAICT, the only added inefficiency here is
the leftCount--? expression. I think it is worth the gain of much easier
to understand code.

However, I cannot insist that you switch to this simpler approach. If
you prefer to keep fixing the more complex code, I will do my best to
find the time to keep reviewing it.

Thank you,

Alex.
Received on Thu Apr 17 2014 - 18:55:08 MDT