strncmp->memcmp when we know the shorter length

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 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? Look at the
warning above the StrNCpy(), for example.

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

singh.gurjeet@{ 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.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 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@gmail.com> wrote:

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 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.gurjeet@{ 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@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 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@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