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(at)leadboat(dot)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 6:24 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:

> On Mon, Dec 20, 2010 at 1:10 PM, Noah Misch <noah(at)leadboat(dot)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? Look at the
warning above the StrNCpy(), for example.

Regards,
--
gurjeet.singh
@ EnterpriseDB - The Enterprise Postgres Company
http://www.EnterpriseDB.com

singh(dot)gurjeet(at){ gmail | yahoo }.com
Twitter/Skype: singh_gurjeet

Mail sent from my BlackLaptop device

On Tue, Dec 21, 2010 at 8:29 PM, Gurjeet Singh <singh(dot)gurjeet(at)gmail(dot)com> wrote:
> On Tue, Dec 21, 2010 at 6:24 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
>>
>> On Mon, Dec 20, 2010 at 1:10 PM, Noah Misch <noah(at)leadboat(dot)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 with StrNCpy(..., 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 9:01 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:

> On Tue, Dec 21, 2010 at 8:29 PM, Gurjeet Singh <singh(dot)gurjeet(at)gmail(dot)com>
> wrote:
> > On Tue, Dec 21, 2010 at 6:24 PM, Robert Haas <robertmhaas(at)gmail(dot)com>
> wrote:
> >>
> >> On Mon, Dec 20, 2010 at 1:10 PM, Noah Misch <noah(at)leadboat(dot)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 with StrNCpy(..., 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.
>
>
I missed the part where Noah said "... where we have the length of the *
_shorter_* string". I agree we are safe here.

Regards,
--
gurjeet.singh
@ EnterpriseDB - The Enterprise Postgres Company
http://www.EnterpriseDB.com

singh(dot)gurjeet(at){ gmail | yahoo }.com
Twitter/Skype: singh_gurjeet

Mail sent from my BlackLaptop device

On Tue, Dec 21, 2010 at 6:24 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> On Mon, Dec 20, 2010 at 1:10 PM, Noah Misch <noah(at)leadboat(dot)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 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.

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

Robert Haas <robertmhaas(at)gmail(dot)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(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Robert Haas <robertmhaas(at)gmail(dot)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(at)gmail(dot)com> writes:
> On Tue, Dec 21, 2010 at 10:24 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)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