From efa15594e17fc20827dba66414fb391e99905394 Mon Sep 17 00:00:00 2001 From: Bruno Haible Date: Wed, 22 Jul 2020 18:35:20 +0200 Subject: [PATCH] Optimize three-valued comparison between integers. (a > b ? 1 : a < b ? -1 : 0) is the same as (a > b) - (a < b). * m4/gnulib-common.m4 (gl_COMMON): Define _GL_CMP. * lib/c-strcasecmp.c (c_strcasecmp): Use _GL_CMP. * lib/c-strncasecmp.c (c_strncasecmp): Likewise. * lib/dfa.c (compare): Likewise. * lib/fts.c (fts_compare_ino): Likewise. * lib/mbmemcasecmp.c (mbmemcasecmp): Likewise. * lib/mbscasecmp.c (mbscasecmp): Likewise. * lib/mbsncasecmp.c (mbsncasecmp): Likewise. * lib/memcasecmp.c (memcasecmp): Likewise. * lib/memcmp2.c (memcmp2): Likewise. * lib/savedir.c (direntry_cmp_inode): Likewise. * lib/strcasecmp.c (strcasecmp): Likewise. * lib/strncasecmp.c (strncasecmp): Likewise. * lib/unistr/u-cmp2.h (FUNC): Likewise. --- ChangeLog | 19 +++++++++++++++++++ lib/c-strcasecmp.c | 2 +- lib/c-strncasecmp.c | 2 +- lib/dfa.c | 2 +- lib/fts.c | 3 +-- lib/mbmemcasecmp.c | 4 ++-- lib/mbscasecmp.c | 2 +- lib/mbsncasecmp.c | 2 +- lib/memcasecmp.c | 3 +-- lib/memcmp2.c | 7 +------ lib/savedir.c | 2 +- lib/strcasecmp.c | 2 +- lib/strncasecmp.c | 2 +- lib/unistr/u-cmp2.h | 7 +------ m4/gnulib-common.m4 | 16 +++++++++++++++- 15 files changed, 48 insertions(+), 27 deletions(-) diff --git a/ChangeLog b/ChangeLog index 08804223d1..3203040d0f 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,22 @@ +2020-07-23 Bruno Haible + + Optimize three-valued comparison between integers. + (a > b ? 1 : a < b ? -1 : 0) is the same as (a > b) - (a < b). + * m4/gnulib-common.m4 (gl_COMMON): Define _GL_CMP. + * lib/c-strcasecmp.c (c_strcasecmp): Use _GL_CMP. + * lib/c-strncasecmp.c (c_strncasecmp): Likewise. + * lib/dfa.c (compare): Likewise. + * lib/fts.c (fts_compare_ino): Likewise. + * lib/mbmemcasecmp.c (mbmemcasecmp): Likewise. + * lib/mbscasecmp.c (mbscasecmp): Likewise. + * lib/mbsncasecmp.c (mbsncasecmp): Likewise. + * lib/memcasecmp.c (memcasecmp): Likewise. + * lib/memcmp2.c (memcmp2): Likewise. + * lib/savedir.c (direntry_cmp_inode): Likewise. + * lib/strcasecmp.c (strcasecmp): Likewise. + * lib/strncasecmp.c (strncasecmp): Likewise. + * lib/unistr/u-cmp2.h (FUNC): Likewise. + 2020-07-23 Bruno Haible lchmod: Use /proc on Cygwin. diff --git a/lib/c-strcasecmp.c b/lib/c-strcasecmp.c index 3ac650f87c..1de04b7066 100644 --- a/lib/c-strcasecmp.c +++ b/lib/c-strcasecmp.c @@ -52,5 +52,5 @@ c_strcasecmp (const char *s1, const char *s2) /* On machines where 'char' and 'int' are types of the same size, the difference of two 'unsigned char' values - including the sign bit - doesn't fit in an 'int'. */ - return (c1 > c2 ? 1 : c1 < c2 ? -1 : 0); + return _GL_CMP (c1, c2); } diff --git a/lib/c-strncasecmp.c b/lib/c-strncasecmp.c index a4e67d1655..1782e54ad1 100644 --- a/lib/c-strncasecmp.c +++ b/lib/c-strncasecmp.c @@ -52,5 +52,5 @@ c_strncasecmp (const char *s1, const char *s2, size_t n) /* On machines where 'char' and 'int' are types of the same size, the difference of two 'unsigned char' values - including the sign bit - doesn't fit in an 'int'. */ - return (c1 > c2 ? 1 : c1 < c2 ? -1 : 0); + return _GL_CMP (c1, c2); } diff --git a/lib/dfa.c b/lib/dfa.c index dee7be8617..1d2d404574 100644 --- a/lib/dfa.c +++ b/lib/dfa.c @@ -2466,7 +2466,7 @@ static int compare (const void *a, const void *b) { position const *p = a, *q = b; - return p->index < q->index ? -1 : p->index > q->index; + return _GL_CMP (p->index, q->index); } static void diff --git a/lib/fts.c b/lib/fts.c index 5e357bee59..a34092ca25 100644 --- a/lib/fts.c +++ b/lib/fts.c @@ -1190,8 +1190,7 @@ fts_children (register FTS *sp, int instr) static int fts_compare_ino (struct _ftsent const **a, struct _ftsent const **b) { - return (a[0]->fts_statp->st_ino < b[0]->fts_statp->st_ino ? -1 - : b[0]->fts_statp->st_ino < a[0]->fts_statp->st_ino ? 1 : 0); + return _GL_CMP (a[0]->fts_statp->st_ino, b[0]->fts_statp->st_ino); } /* Map the dirent.d_type value, DTYPE, to the corresponding stat.st_mode diff --git a/lib/mbmemcasecmp.c b/lib/mbmemcasecmp.c index 57039d2950..d0eea69d4b 100644 --- a/lib/mbmemcasecmp.c +++ b/lib/mbmemcasecmp.c @@ -33,7 +33,7 @@ int mbmemcasecmp (const char *s1, size_t n1, const char *s2, size_t n2) { if (s1 == s2) - return (n1 < n2 ? -1 : n1 > n2 ? 1 : 0); + return _GL_CMP (n1, n2); if (MB_CUR_MAX > 1) { @@ -80,7 +80,7 @@ mbmemcasecmp (const char *s1, size_t n1, const char *s2, size_t n2) /* On machines where 'char' and 'int' are types of the same size, the difference of two 'unsigned char' values - including the sign bit - doesn't fit in an 'int'. */ - return (c1 > c2 ? 1 : c1 < c2 ? -1 : 0); + return _GL_CMP (c1, c2); } ++p1; ++p2; diff --git a/lib/mbscasecmp.c b/lib/mbscasecmp.c index 9a1ea4bb35..976e94a070 100644 --- a/lib/mbscasecmp.c +++ b/lib/mbscasecmp.c @@ -93,6 +93,6 @@ mbscasecmp (const char *s1, const char *s2) /* On machines where 'char' and 'int' are types of the same size, the difference of two 'unsigned char' values - including the sign bit - doesn't fit in an 'int'. */ - return (c1 > c2 ? 1 : c1 < c2 ? -1 : 0); + return _GL_CMP (c1, c2); } } diff --git a/lib/mbsncasecmp.c b/lib/mbsncasecmp.c index a414a6986f..da43d5cb8c 100644 --- a/lib/mbsncasecmp.c +++ b/lib/mbsncasecmp.c @@ -94,6 +94,6 @@ mbsncasecmp (const char *s1, const char *s2, size_t n) /* On machines where 'char' and 'int' are types of the same size, the difference of two 'unsigned char' values - including the sign bit - doesn't fit in an 'int'. */ - return (c1 > c2 ? 1 : c1 < c2 ? -1 : 0); + return _GL_CMP (c1, c2); } } diff --git a/lib/memcasecmp.c b/lib/memcasecmp.c index a44379373c..6720b8cdb8 100644 --- a/lib/memcasecmp.c +++ b/lib/memcasecmp.c @@ -40,8 +40,7 @@ memcasecmp (const void *vs1, const void *vs2, size_t n) unsigned char u2 = s2[i]; int U1 = toupper (u1); int U2 = toupper (u2); - int diff = (UCHAR_MAX <= INT_MAX ? U1 - U2 - : U1 < U2 ? -1 : U2 < U1); + int diff = (UCHAR_MAX <= INT_MAX ? U1 - U2 : _GL_CMP (U1, U2)); if (diff) return diff; } diff --git a/lib/memcmp2.c b/lib/memcmp2.c index c9c3316870..bbfbb0294d 100644 --- a/lib/memcmp2.c +++ b/lib/memcmp2.c @@ -26,11 +26,6 @@ memcmp2 (const char *s1, size_t n1, const char *s2, size_t n2) { int cmp = memcmp (s1, s2, n1 <= n2 ? n1 : n2); if (cmp == 0) - { - if (n1 < n2) - cmp = -1; - else if (n1 > n2) - cmp = 1; - } + cmp = _GL_CMP (n1, n2); return cmp; } diff --git a/lib/savedir.c b/lib/savedir.c index 5d7151ea81..c93b81a0b9 100644 --- a/lib/savedir.c +++ b/lib/savedir.c @@ -65,7 +65,7 @@ direntry_cmp_inode (void const *a, void const *b) direntry_t const *dea = a; direntry_t const *deb = b; - return dea->ino < deb->ino ? -1 : dea->ino > deb->ino; + return _GL_CMP (dea->ino, deb->ino); } #endif diff --git a/lib/strcasecmp.c b/lib/strcasecmp.c index c0b610e5e8..bcb9adb185 100644 --- a/lib/strcasecmp.c +++ b/lib/strcasecmp.c @@ -58,5 +58,5 @@ strcasecmp (const char *s1, const char *s2) /* On machines where 'char' and 'int' are types of the same size, the difference of two 'unsigned char' values - including the sign bit - doesn't fit in an 'int'. */ - return (c1 > c2 ? 1 : c1 < c2 ? -1 : 0); + return _GL_CMP (c1, c2); } diff --git a/lib/strncasecmp.c b/lib/strncasecmp.c index 4c1b5b52c9..396d1caaa2 100644 --- a/lib/strncasecmp.c +++ b/lib/strncasecmp.c @@ -58,5 +58,5 @@ strncasecmp (const char *s1, const char *s2, size_t n) /* On machines where 'char' and 'int' are types of the same size, the difference of two 'unsigned char' values - including the sign bit - doesn't fit in an 'int'. */ - return (c1 > c2 ? 1 : c1 < c2 ? -1 : 0); + return _GL_CMP (c1, c2); } diff --git a/lib/unistr/u-cmp2.h b/lib/unistr/u-cmp2.h index 85a5db80c5..1e0ea72802 100644 --- a/lib/unistr/u-cmp2.h +++ b/lib/unistr/u-cmp2.h @@ -21,12 +21,7 @@ FUNC (const UNIT *s1, size_t n1, const UNIT *s2, size_t n2) int cmp = U_CMP (s1, s2, MIN (n1, n2)); if (cmp == 0) - { - if (n1 < n2) - cmp = -1; - else if (n1 > n2) - cmp = 1; - } + cmp = _GL_CMP (n1, n2); return cmp; } diff --git a/m4/gnulib-common.m4 b/m4/gnulib-common.m4 index f4ba5e3a00..ba4239188d 100644 --- a/m4/gnulib-common.m4 +++ b/m4/gnulib-common.m4 @@ -1,4 +1,4 @@ -# gnulib-common.m4 serial 50 +# gnulib-common.m4 serial 51 dnl Copyright (C) 2007-2020 Free Software Foundation, Inc. dnl This file is free software; the Free Software Foundation dnl gives unlimited permission to copy and/or distribute it, @@ -292,6 +292,20 @@ AC_DEFUN([gl_COMMON_BODY], [ that may clobber errno, it needs to save and restore the value of errno. */ #define _GL_ASYNC_SAFE +]) + AH_VERBATIM([micro_optimizations], +[/* _GL_CMP (n1, n2) performs a three-valued comparison on n1 vs. n2. + It returns + 1 if n1 > n2 + 0 if n1 == n2 + -1 if n1 < n2 + The naïve code (n1 > n2 ? 1 : n1 < n2 ? -1 : 0) produces a conditional + jump with nearly all GCC versions up to GCC 10. + This variant (n1 < n2 ? -1 : n1 > n2) produces a conditional with many + GCC versions up to GCC 9. + The better code (n1 > n2) - (n1 < n2) from Hacker's Delight § 2-9 + avoids conditional jumps in all GCC versions >= 3.4. */ +#define _GL_CMP(n1, n2) ((n1) > (n2)) - ((n1) < (n2)) ]) dnl Hint which direction to take regarding cross-compilation guesses: dnl When a user installs a program on a platform they are not intimately -- 2.39.5