Thread

1. strncmp->memcmp when we know the shorter length

   Noah Misch <noah@leadboat.com> — 2010-12-20T18:10:42Z

   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
   

2. Re: strncmp->memcmp when we know the shorter length

   Robert Haas <robertmhaas@gmail.com> — 2010-12-21T23:24:25Z

   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
   
   

3. Re: strncmp->memcmp when we know the shorter length

   Gurjeet Singh <singh.gurjeet@gmail.com> — 2010-12-22T01:29:46Z

   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
   

4. Re: strncmp->memcmp when we know the shorter length

   Robert Haas <robertmhaas@gmail.com> — 2010-12-22T02:01:23Z

   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
   
   

5. Re: strncmp->memcmp when we know the shorter length

   Gurjeet Singh <singh.gurjeet@gmail.com> — 2010-12-22T02:30:14Z

   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
   

6. Re: strncmp->memcmp when we know the shorter length

   Robert Haas <robertmhaas@gmail.com> — 2010-12-22T03:15:41Z

   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
   
   

7. Re: strncmp->memcmp when we know the shorter length

   Tom Lane <tgl@sss.pgh.pa.us> — 2010-12-22T03:24:47Z

   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
   
   

8. Re: strncmp->memcmp when we know the shorter length

   Robert Haas <robertmhaas@gmail.com> — 2010-12-22T03:48:07Z

   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
   
   

9. Re: strncmp->memcmp when we know the shorter length

   Tom Lane <tgl@sss.pgh.pa.us> — 2010-12-22T04:17:45Z

   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
   
   

10. Re: strncmp->memcmp when we know the shorter length

    Noah Misch <noah@leadboat.com> — 2010-12-22T18:19:51Z

    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