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 v3] speedup strcoll by using strdiff


This patch uses strdiff to skip over equal prefixes in strcoll. With this patch
the time for collating a filelist drops to twice the time of byte-comparison. It
is implemented for 8-bit character sets and UTF-8. The new attribute
_NL_COLLATE_ENCODING_TYPE is added to the locale data to state the charset
encoding. I opt for commiting this and do the factoring out of strdiff in a
follow-up patch. The tests show no problems although one needs to remove the old
locale data manually.

				change		current		patched
filelist#C			+1.49%		23,724,500	24,078,400
filelist#en_US.UTF-8		-43.06%		95,092,000	54,150,100
lorem_ipsum#vi_VN.UTF-8		-0.29%		1,995,540	1,989,810
lorem_ipsum#en_US.UTF-8		-15.96%		2,081,250	1,749,150
lorem_ipsum#ar_SA.UTF-8		-24.48%		2,618,660	1,977,630
lorem_ipsum#zh_CN.UTF-8		+15.03%		793,925		913,224
lorem_ipsum#cs_CZ.UTF-8		-10.68%		2,749,650	2,455,860
lorem_ipsum#en_GB.UTF-8		-6.12%		2,451,930	2,301,790
lorem_ipsum#da_DK.UTF-8		-18.40%		2,128,290	1,736,710
lorem_ipsum#pl_PL.UTF-8		-7.76%		2,005,750	1,850,190
lorem_ipsum#fr_FR.UTF-8		-3.95%		2,799,710	2,689,040
lorem_ipsum#pt_PT.UTF-8		-8.94%		2,803,570	2,552,890
lorem_ipsum#el_GR.UTF-8		-26.48%		4,063,660	2,987,760
lorem_ipsum#ru_RU.UTF-8		-14.48%		2,908,900	2,487,730
lorem_ipsum#iw_IL.UTF-8		-36.47%		2,707,980	1,720,460
lorem_ipsum#es_ES.UTF-8		-11.02%		2,539,390	2,259,460
lorem_ipsum#hi_IN.UTF-8		-61.35%		231,126,000	89,330,100
lorem_ipsum#sv_SE.UTF-8		-12.04%		1,971,310	1,733,890
lorem_ipsum#hu_HU.UTF-8		-14.46%		3,708,090	3,172,060
lorem_ipsum#tr_TR.UTF-8		-9.95%		2,409,160	2,169,550
lorem_ipsum#is_IS.UTF-8		-14.22%		2,032,850	1,743,860
lorem_ipsum#it_IT.UTF-8		-10.03%		2,696,880	2,426,500
lorem_ipsum#sr_RS.UTF-8		-11.96%		2,360,780	2,078,510
lorem_ipsum#ja_JP.UTF-8		-3.45%		1,141,530	1,102,100


	* locale/categories.def: Define _NL_COLLATE_ENCODING_TYPE.
	* locale/langinfo.h: Add _NL_COLLATE_ENCODING_TYPE to attribute list.
	* locale/localeinfo.h: Add enum collation_encoding_type.
	* locale/C-collate.c: Set _NL_COLLATE_ENCODING_TYPE to 8bit.
	* programs/ld-collate.c (collate_output): Add encoding type info.
	* string/strcoll_l.c (STRDIFF): New function.
	* (STRCOLL): Use STRDIFF to skip over equal prefix.
	* wcsmbs/wcscoll_l.c: Define STRDIFF.

diff --git a/locale/C-collate.c b/locale/C-collate.c
index 06dfdfa..d7f3c55 100644
--- a/locale/C-collate.c
+++ b/locale/C-collate.c
@@ -144,6 +144,8 @@ const struct __locale_data _nl_C_LC_COLLATE attribute_hidden =
     /* _NL_COLLATE_COLLSEQWC */
     { .string = (const char *) collseqwc },
     /* _NL_COLLATE_CODESET */
-    { .string = _nl_C_codeset }
+    { .string = _nl_C_codeset },
+    /* _NL_COLLATE_ENCODING_TYPE */
+    { .word = __cet_8bit }
   }
 };
diff --git a/locale/categories.def b/locale/categories.def
index a8dda53..45d644e 100644
--- a/locale/categories.def
+++ b/locale/categories.def
@@ -58,6 +58,7 @@ DEFINE_CATEGORY
   DEFINE_ELEMENT (_NL_COLLATE_COLLSEQMB,        "collate-collseqmb",        std,
wstring)
   DEFINE_ELEMENT (_NL_COLLATE_COLLSEQWC,        "collate-collseqwc",        std,
wstring)
   DEFINE_ELEMENT (_NL_COLLATE_CODESET,		"collate-codeset",	    std, string)
+  DEFINE_ELEMENT (_NL_COLLATE_ENCODING_TYPE,	"collate-encoding-type",    std, word)
   ), NO_POSTLOAD)


diff --git a/locale/langinfo.h b/locale/langinfo.h
index a565d9d..ffc5c7f 100644
--- a/locale/langinfo.h
+++ b/locale/langinfo.h
@@ -255,6 +255,7 @@ enum
   _NL_COLLATE_COLLSEQMB,
   _NL_COLLATE_COLLSEQWC,
   _NL_COLLATE_CODESET,
+  _NL_COLLATE_ENCODING_TYPE,
   _NL_NUM_LC_COLLATE,

   /* LC_CTYPE category: character classification.
diff --git a/locale/localeinfo.h b/locale/localeinfo.h
index 1d2ee00..bdab9fe 100644
--- a/locale/localeinfo.h
+++ b/locale/localeinfo.h
@@ -110,6 +110,14 @@ enum coll_sort_rule
   sort_mask
 };

+/* Collation encoding type.  */
+enum collation_encoding_type
+{
+  __cet_other,
+  __cet_8bit,
+  __cet_utf8
+};
+
 /* We can map the types of the entries into a few categories.  */
 enum value_type
 {
diff --git a/locale/programs/ld-collate.c b/locale/programs/ld-collate.c
index dc0fe30..a39a94f 100644
--- a/locale/programs/ld-collate.c
+++ b/locale/programs/ld-collate.c
@@ -32,6 +32,7 @@
 #include "linereader.h"
 #include "locfile.h"
 #include "elem-hash.h"
+#include "../localeinfo.h"

 /* Uncomment the following line in the production version.  */
 /* #define NDEBUG 1 */
@@ -2130,6 +2131,8 @@ collate_output (struct localedef_t *locale, const struct
charmap_t *charmap,
 	  /* The words have to be handled specially.  */
 	  if (idx == _NL_ITEM_INDEX (_NL_COLLATE_SYMB_HASH_SIZEMB))
 	    add_locale_uint32 (&file, 0);
+	  else if (idx == _NL_ITEM_INDEX (_NL_COLLATE_ENCODING_TYPE))
+	    add_locale_uint32 (&file, __cet_other);
 	  else
 	    add_locale_empty (&file);
 	}
@@ -2493,6 +2496,12 @@ collate_output (struct localedef_t *locale, const struct
charmap_t *charmap,
   add_locale_raw_data (&file, collate->mbseqorder, 256);
   add_locale_collseq_table (&file, &collate->wcseqorder);
   add_locale_string (&file, charmap->code_set_name);
+  if (strcmp (charmap->code_set_name, "UTF-8") == 0)
+    add_locale_uint32 (&file, __cet_utf8);
+  else if (charmap->mb_cur_max == 1)
+    add_locale_uint32 (&file, __cet_8bit);
+  else
+    add_locale_uint32 (&file, __cet_other);
   write_locale_data (output_path, LC_COLLATE, "LC_COLLATE", &file);

   obstack_free (&weightpool, NULL);
diff --git a/string/strcoll_l.c b/string/strcoll_l.c
index 658d5b9..0fa005f 100644
--- a/string/strcoll_l.c
+++ b/string/strcoll_l.c
@@ -29,6 +29,7 @@
 # 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 +42,20 @@
 #include "../locale/localeinfo.h"
 #include WEIGHT_H

+#define MASK_UTF8_7BIT  (1 << 7)
+#define MASK_UTF8_START (3 << 6)
+
+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
 {
@@ -255,9 +270,29 @@ 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 / POSIX).  */
   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 middle
+     of a char sequence for multibyte encodings like UTF-8.  */
+  uint_fast32_t encoding =
+    current->values[_NL_ITEM_INDEX (_NL_COLLATE_ENCODING_TYPE)].word;
+  if (encoding != __cet_other)
+    {
+      size_t diff = STRDIFF (s1, s2);
+      if (diff > 0)
+	{
+	  if (encoding == __cet_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 +356,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 == __cet_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]