This is the mail archive of the libc-alpha@sourceware.org mailing list for the glibc project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH] speedup strcoll by using strdiff


This patch uses strdiff to skip over equal prefixes in strcoll. This is implemented for 8-bit character sets and UTF-8.

The benchmark shows the following changes:

file listing	-52.82%
vi_VN.UTF-8	-10.63%
en_US.UTF-8	-12.33%
ar_SA.UTF-8	-23.02%
zh_CN.UTF-8	4.80%
cs_CZ.UTF-8	-8.54%
en_GB.UTF-8	-4.14%
da_DK.UTF-8	-13.84%
pl_PL.UTF-8	-8.77%
fr_FR.UTF-8	-7.12%
pt_PT.UTF-8	-7.80%
el_GR.UTF-8	-21.93%
ru_RU.UTF-8	-14.70%
iw_IL.UTF-8	-34.43%
es_ES.UTF-8	-8.97%
hi_IN.UTF-8	-59.70%
sv_SE.UTF-8	-15.63%
hu_HU.UTF-8	-17.53%
tr_TR.UTF-8	-9.62%
is_IS.UTF-8	-5.57%
it_IT.UTF-8	-7.22%
sr_RS.UTF-8	-20.78%
ja_JP.UTF-8	21.09%

	* string/strcoll_l.c (strsuffix): New function.
	* (get_encoding): Likewise.
	* (STRDIFF): Likewise.
	* (STRCOLL): Use STRDIFF to skip over equal prefix.
	* wcsmbs/wcscoll_l.c: Define STRDIFF.
	* localedata/charmaps-8bit.c: New file.

diff --git a/localedata/charmaps-8bit.c b/localedata/charmaps-8bit.c
index e69de29..339032d 100644
--- a/localedata/charmaps-8bit.c
+++ b/localedata/charmaps-8bit.c
@@ -0,0 +1,205 @@
+"ANSI_X3.4-1968",
+"ARMSCII-8",
+"ASMO_449",
+"BRF",
+"BS_4730",
+"BS_VIEWDATA",
+"CP10007",
+"CP1125",
+"CP1250",
+"CP1251",
+"CP1252",
+"CP1253",
+"CP1254",
+"CP1255",
+"CP1256",
+"CP1257",
+"CP1258",
+"CP737",
+"CP770",
+"CP771",
+"CP772",
+"CP773",
+"CP774",
+"CP775",
+"CP949",
+"CSA_Z243.4-1985-1",
+"CSA_Z243.4-1985-2",
+"CSA_Z243.4-1985-GR",
+"CSN_369103",
+"CWI",
+"DEC-MCS",
+"DIN_66003",
+"DS_2089",
+"EBCDIC-AT-DE",
+"EBCDIC-AT-DE-A",
+"EBCDIC-CA-FR",
+"EBCDIC-DK-NO",
+"EBCDIC-DK-NO-A",
+"EBCDIC-ES",
+"EBCDIC-ES-A",
+"EBCDIC-ES-S",
+"EBCDIC-FI-SE",
+"EBCDIC-FI-SE-A",
+"EBCDIC-FR",
+"EBCDIC-IS-FRISS",
+"EBCDIC-IT",
+"EBCDIC-PT",
+"EBCDIC-UK",
+"EBCDIC-US",
+"ECMA-CYRILLIC",
+"ES",
+"ES2",
+"GEORGIAN-ACADEMY",
+"GEORGIAN-PS",
+"GOST_19768-74",
+"GREEK7",
+"GREEK7-OLD",
+"GREEK-CCITT",
+"HP-GREEK8",
+"HP-ROMAN8",
+"HP-ROMAN9",
+"HP-THAI8",
+"HP-TURKISH8",
+"IBM037",
+"IBM038",
+"IBM1004",
+"IBM1026",
+"IBM1047",
+"IBM1124",
+"IBM1129",
+"IBM1132",
+"IBM1133",
+"IBM1160",
+"IBM1161",
+"IBM1162",
+"IBM1163",
+"IBM1164",
+"IBM256",
+"IBM273",
+"IBM274",
+"IBM275",
+"IBM277",
+"IBM278",
+"IBM280",
+"IBM281",
+"IBM284",
+"IBM285",
+"IBM290",
+"IBM297",
+"IBM420",
+"IBM423",
+"IBM424",
+"IBM437",
+"IBM500",
+"IBM850",
+"IBM851",
+"IBM852",
+"IBM855",
+"IBM856",
+"IBM857",
+"IBM860",
+"IBM861",
+"IBM862",
+"IBM863",
+"IBM864",
+"IBM865",
+"IBM866",
+"IBM866NAV",
+"IBM868",
+"IBM869",
+"IBM870",
+"IBM871",
+"IBM874",
+"IBM875",
+"IBM880",
+"IBM891",
+"IBM903",
+"IBM904",
+"IBM905",
+"IBM918",
+"IBM922",
+"IEC_P27-1",
+"INIS",
+"INIS-8",
+"INIS-CYRILLIC",
+"INVARIANT",
+"ISIRI-3342",
+"ISO_10367-BOX",
+"ISO_11548-1",
+"ISO_2033-1983",
+"ISO_5427",
+"ISO_5427-EXT",
+"ISO_5428",
+"ISO_646.BASIC",
+"ISO_646.IRV",
+"ISO_6937-2-25",
+"ISO-8859-1",
+"ISO-8859-10",
+"ISO-8859-11",
+"ISO-8859-13",
+"ISO-8859-14",
+"ISO-8859-15",
+"ISO-8859-16",
+"ISO_8859-1,GL",
+"ISO-8859-2",
+"ISO-8859-3",
+"ISO-8859-4",
+"ISO-8859-5",
+"ISO-8859-6",
+"ISO-8859-7",
+"ISO-8859-8",
+"ISO-8859-9",
+"ISO-8859-9E",
+"ISO_8859-SUPP",
+"ISO-IR-197",
+"ISO-IR-209",
+"IT",
+"JIS_C6220-1969-JP",
+"JIS_C6220-1969-RO",
+"JIS_C6229-1984-A",
+"JIS_C6229-1984-B",
+"JIS_C6229-1984-B-ADD",
+"JIS_C6229-1984-HAND",
+"JIS_C6229-1984-HAND-ADD",
+"JIS_C6229-1984-KANA",
+"JIS_X0201",
+"JUS_I.B1.002",
+"JUS_I.B1.003-MAC",
+"JUS_I.B1.003-SERB",
+"KOI-8",
+"KOI8-R",
+"KOI8-RU",
+"KOI8-T",
+"KOI8-U",
+"KSC5636",
+"LATIN-GREEK",
+"LATIN-GREEK-1",
+"MAC-CENTRALEUROPE",
+"MAC-CYRILLIC",
+"MACINTOSH",
+"MAC-IS",
+"MAC-SAMI",
+"MAC-UK",
+"MIK",
+"MSZ_7795.3",
+"NATS-DANO",
+"NATS-DANO-ADD",
+"NATS-SEFI",
+"NATS-SEFI-ADD",
+"NC_NC00-10",
+"NEXTSTEP",
+"NF_Z_62-010",
+"NF_Z_62-010_1973",
+"NS_4551-1",
+"NS_4551-2",
+"PT",
+"PT154",
+"PT2",
+"RK1048",
+"SAMI",
+"SAMI-WS2",
+"SEN_850200_B",
+"SEN_850200_C",
+"T.61-7BIT",
+"VISCII"
diff --git a/string/strcoll_l.c b/string/strcoll_l.c
index 658d5b9..2df3361 100644
--- a/string/strcoll_l.c
+++ b/string/strcoll_l.c
@@ -24,11 +24,13 @@
 #include <stdint.h>
 #include <string.h>
 #include <sys/param.h>
+#include <bits/libc-lock.h>

 #ifndef STRING_TYPE
 # define STRING_TYPE char
 # define USTRING_TYPE unsigned char
 # define STRCOLL __strcoll_l
+# define STRDIFF __strdiff
 # define STRCMP strcmp
 # define WEIGHT_H "../locale/weight.h"
 # define SUFFIX	MB
@@ -41,6 +43,96 @@
 #include "../locale/localeinfo.h"
 #include WEIGHT_H

+/* Mapping of locale to encoding type.  */
+typedef struct encoding
+{
+  int type;
+  const char *locale;
+  struct encoding *next;
+} *encoding_t;
+
+#define ENCODING_OTHER 0
+#define ENCODING_8BIT  1
+#define ENCODING_UTF8  2
+
+__libc_lock_define (typedef, lock_t)
+static encoding_t encodings = NULL;
+static const char *const encodings_8bit[] =
+{
+#include "../localedata/charmaps-8bit.c"
+};
+static lock_t encodings_lock = LLL_LOCK_INITIALIZER;
+
+static int
+strsuffix(const char *str, const char *suffix)
+{
+  if (!str || !suffix)
+    return 0;
+  size_t lenstr = strlen (str);
+  size_t lensuffix = strlen (suffix);
+  if (lensuffix >  lenstr)
+    return 0;
+  return strncmp (str + lenstr - lensuffix, suffix, lensuffix) == 0;
+}
+
+static int
+get_encoding (const char *locale)
+{
+  encoding_t encoding = encodings;
+  while (encoding != NULL)
+    {
+      if (encoding->locale == locale)
+	return encoding->type;
+      encoding = encoding->next;
+    }
+
+  /* Add new encoding type.  Lock encoding map and check if another thread
+     has already added the new type while waiting for the lock.  */
+  __libc_lock_lock (encodings_lock);
+
+  encoding = encodings;
+  while (encoding != NULL)
+    {
+      if (encoding->locale == locale)
+	{
+	  __libc_lock_unlock (encodings_lock);
+	  return encoding->type;
+	}
+      encoding = encoding->next;
+    }
+
+  encoding_t new_encoding = malloc (sizeof (encoding_t*));
+  if (strsuffix (locale, "UTF-8"))
+    new_encoding->type = ENCODING_UTF8;
+  else
+    {
+      new_encoding->type = ENCODING_OTHER;
+      for (size_t i = 0; i < sizeof (encodings_8bit) / sizeof (char *); i++)
+	if (strsuffix (locale, encodings_8bit[i]))
+	  {
+	    new_encoding->type = ENCODING_8BIT;
+	    break;
+	  }
+    }
+  new_encoding->locale = locale;
+  new_encoding->next = encodings;
+  encodings = new_encoding;
+
+  __libc_lock_unlock (encodings_lock);
+  return new_encoding->type;
+}
+
+size_t
+STRDIFF (const STRING_TYPE *s, const STRING_TYPE *t)
+{
+  size_t n;
+
+  for (n = 0; *s != '\0' && *s++ == *t++; ++n)
+    continue;
+
+  return n;
+}
+
 /* Track status while looking for sequences in a string.  */
 typedef struct
 {
@@ -242,6 +334,9 @@ out:
   return result;
 }

+#define MASK_UTF8_7BIT  (1 << 7)
+#define MASK_UTF8_START (3 << 6)
+
 int
 STRCOLL (const STRING_TYPE *s1, const STRING_TYPE *s2, __locale_t l)
 {
@@ -255,9 +350,28 @@ STRCOLL (const STRING_TYPE *s1, const STRING_TYPE *s2, __locale_t l)
   const USTRING_TYPE *extra;
   const int32_t *indirect;

+  /* In case there is no locale specific sort order (C locale).  */
   if (nrules == 0)
     return STRCMP (s1, s2);

+  /* Fast forward to the position of the first difference.  Needs to be
+     encoding aware as the byte-by-byte comparison can stop in the midle
+     of a char sequence for non fixed width encodings like UTF-8.  */
+  int encoding = get_encoding (l->__names[LC_CTYPE]);
+  if (encoding != ENCODING_OTHER)
+    {
+      size_t diff = STRDIFF (s1, s2);
+      if (diff > 0)
+	{
+	  if (encoding == ENCODING_UTF8 && (*(s1 + diff) & MASK_UTF8_7BIT) != 0)
+	    do
+	      diff--;
+	    while (diff > 0 && (*(s1 + diff) & MASK_UTF8_START) != MASK_UTF8_START);
+	  s1 += diff;
+	  s2 += diff;
+	}
+    }
+
   /* Catch empty strings.  */
   if (__glibc_unlikely (*s1 == '\0') || __glibc_unlikely (*s2 == '\0'))
     return (*s1 != '\0') - (*s2 != '\0');
@@ -321,7 +435,8 @@ STRCOLL (const STRING_TYPE *s1, const STRING_TYPE *s2, __locale_t l)
 		     byte-level comparison to ensure that we don't waste time
 		     going through multiple passes for totally equal strings
 		     before proceeding to subsequent passes.  */
-		  if (pass == 0 && STRCMP (s1, s2) == 0)
+		  if (pass == 0 && encoding == ENCODING_OTHER &&
+		      STRCMP (s1, s2) == 0)
 		    return result;
 		  else
 		    break;
diff --git a/wcsmbs/wcscoll_l.c b/wcsmbs/wcscoll_l.c
index 106ec93..9f60cee 100644
--- a/wcsmbs/wcscoll_l.c
+++ b/wcsmbs/wcscoll_l.c
@@ -23,6 +23,7 @@
 #define STRING_TYPE wchar_t
 #define USTRING_TYPE wint_t
 #define STRCOLL __wcscoll_l
+#define STRDIFF __wcsdiff
 #define STRCMP wcscmp
 #define WEIGHT_H "../locale/weightwc.h"
 #define SUFFIX	WC


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]