Thread: strncmp->memcmp when we know the shorter length

When the caller knows the smaller string length, memcmp and strncmp are
functionally equivalent.  Since memcmp need not watch each byte for a NULL
terminator, it often compares a CPU word at a time for better performance.  The
attached patch changes use of strncmp to memcmp where we have the length of the
shorter string.  I was most interested in the varlena.c instances, but I tried
to find all applicable call sites.  To benchmark it, I used the attached
"bench-texteq.sql".  This patch improved my 5-run average timing of the SELECT
from 65.8s to 56.9s, a 13% improvement.  I can't think of a case where the
change should be pessimal.

Thanks,
nm

On Mon, Dec 20, 2010 at 1:10 PM, Noah Misch <noah@leadboat.com> wrote:
> When the caller knows the smaller string length, memcmp and strncmp are
> functionally equivalent.  Since memcmp need not watch each byte for a NULL
> terminator, it often compares a CPU word at a time for better performance.  The
> attached patch changes use of strncmp to memcmp where we have the length of the
> shorter string.  I was most interested in the varlena.c instances, but I tried
> to find all applicable call sites.  To benchmark it, I used the attached
> "bench-texteq.sql".  This patch improved my 5-run average timing of the SELECT
> from 65.8s to 56.9s, a 13% improvement.  I can't think of a case where the
> change should be pessimal.

This is a good idea.  I will check this over and commit it.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Tue, Dec 21, 2010 at 8:29 PM, Gurjeet Singh <singh.gurjeet@gmail.com> wrote:
> On Tue, Dec 21, 2010 at 6:24 PM, Robert Haas <robertmhaas@gmail.com> wrote:
>>
>> On Mon, Dec 20, 2010 at 1:10 PM, Noah Misch <noah@leadboat.com> wrote:
>> > When the caller knows the smaller string length, memcmp and strncmp are
>> > functionally equivalent.  Since memcmp need not watch each byte for a
>> > NULL
>> > terminator, it often compares a CPU word at a time for better
>> > performance.  The
>> > attached patch changes use of strncmp to memcmp where we have the length
>> > of the
>> > shorter string.  I was most interested in the varlena.c instances, but I
>> > tried
>> > to find all applicable call sites.  To benchmark it, I used the attached
>> > "bench-texteq.sql".  This patch improved my 5-run average timing of the
>> > SELECT
>> > from 65.8s to 56.9s, a 13% improvement.  I can't think of a case where
>> > the
>> > change should be pessimal.
>>
>> This is a good idea.  I will check this over and commit it.
>
> Doesn't this risk accessing bytes beyond the shorter string?

If it's done properly, I don't see how this would be a risk.

> Look at the
> warning above the StrNCpy(), for example.

If you're talking about this comment:
*      BTW: when you need to copy a non-null-terminated string (like a text*      datum) and add a null, do not do it
withStrNCpy(..., len+1).  That*      might seem to work, but it fetches one byte more than there is in the*      text
object.

...then that's not applicable here.  It's perfectly safe to compare to
strings of length n using an n-byte memcmp().  The bytes being
compared are 0 through n - 1; the terminating null is in byte n, or
else it isn't, but memcmp() certainly isn't going to look at it.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Tue, Dec 21, 2010 at 6:24 PM, Robert Haas <robertmhaas@gmail.com> wrote:
> On Mon, Dec 20, 2010 at 1:10 PM, Noah Misch <noah@leadboat.com> wrote:
>> When the caller knows the smaller string length, memcmp and strncmp are
>> functionally equivalent.  Since memcmp need not watch each byte for a NULL
>> terminator, it often compares a CPU word at a time for better performance.  The
>> attached patch changes use of strncmp to memcmp where we have the length of the
>> shorter string.  I was most interested in the varlena.c instances, but I tried
>> to find all applicable call sites.  To benchmark it, I used the attached
>> "bench-texteq.sql".  This patch improved my 5-run average timing of the SELECT
>> from 65.8s to 56.9s, a 13% improvement.  I can't think of a case where the
>> change should be pessimal.
>
> This is a good idea.  I will check this over and commit it.

A little benchmarking reveals that on my system (MacOS X 10.6.5) it
appears that strncmp() is faster for a 4 character string, but
memcmp() is faster for a 5+ character string.  So I think most of
these are pretty clear wins, but I have reverted the changes to
src/backend/tsearch because I'm not entirely confident that lexemes
and affixes will be long enough on average for this to be a win there.Please feel free to resubmit that part with
performanceresults 
showing that it works out to a win.  Some of the ltree changes
produced compiler warnings, so I omitted those also.  Committed the
rest.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Robert Haas <robertmhaas@gmail.com> writes:
> If it's done properly, I don't see how this would be a risk.

I'm fairly uncomfortable about the broad swath and low return of this
patch.  Noah is assuming that none of these places are relying on
strncmp to stop short upon finding a null, and I don't believe that
that's a safe assumption in every single place.  Nor do I believe that
it's worth the effort of trying to prove it safe in most of those
places.

I think this might be a good idea in the varchar.c and varlena.c calls,
but I'd be inclined to leave the rest of the calls alone.
        regards, tom lane

On Tue, Dec 21, 2010 at 10:24 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Robert Haas <robertmhaas@gmail.com> writes:
>> If it's done properly, I don't see how this would be a risk.
>
> I'm fairly uncomfortable about the broad swath and low return of this
> patch.  Noah is assuming that none of these places are relying on
> strncmp to stop short upon finding a null, and I don't believe that
> that's a safe assumption in every single place.  Nor do I believe that
> it's worth the effort of trying to prove it safe in most of those
> places.
>
> I think this might be a good idea in the varchar.c and varlena.c calls,
> but I'd be inclined to leave the rest of the calls alone.

Eh, I already committed somewhat more than that.  I did think about
the concern which you raise.  It seems pretty clear that's not a
danger in readfuncs.c.  In the hstore and ltree cases, at least at
first blush, it appears to me that it would be downright broken for
someone to be counting on a null to terminate the comparison.  The
intent of these bits of code appears to be to do equality comparison a
string stored as a byte count + a byte string, rather than a
null-terminated cstring, so unless I'm misunderstanding something it's
more likely that the use of strncmp() would lead to a bug; the prior
coding doesn't look like it would be correct if NUL bytes were
possible.  The tsearch cases also appear to be safe in this regard,
but since I decided against committing those on other grounds I
haven't looked at them as carefully.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Robert Haas <robertmhaas@gmail.com> writes:
> On Tue, Dec 21, 2010 at 10:24 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> I'm fairly uncomfortable about the broad swath and low return of this
>> patch. �Noah is assuming that none of these places are relying on
>> strncmp to stop short upon finding a null, and I don't believe that
>> that's a safe assumption in every single place. �Nor do I believe that
>> it's worth the effort of trying to prove it safe in most of those
>> places.

> Eh, I already committed somewhat more than that.  I did think about
> the concern which you raise.

Okay ... I was arguing for not bothering to expend that effort, but
since you already did, it's a moot point.
        regards, tom lane

On Tue, Dec 21, 2010 at 10:15:41PM -0500, Robert Haas wrote:
> A little benchmarking reveals that on my system (MacOS X 10.6.5) it
> appears that strncmp() is faster for a 4 character string, but
> memcmp() is faster for a 5+ character string.

Good call; I hadn't considered that possibility.

> So I think most of
> these are pretty clear wins, but I have reverted the changes to
> src/backend/tsearch because I'm not entirely confident that lexemes
> and affixes will be long enough on average for this to be a win there.
>  Please feel free to resubmit that part with performance results
> showing that it works out to a win.  Some of the ltree changes
> produced compiler warnings, so I omitted those also.  Committed the
> rest.

Thanks for the quick review and commit.  I'm not acquainted with the performance
significance of the tsearch and ltree call sites.  Leaving those as-is makes
sense to me.

nm