[BZ,15884] strcoll: improve performance by removing the cache
diff mbox

Message ID 542282C1.2080504@web.de
State New
Headers show

Commit Message

Leonhard Holz Sept. 24, 2014, 8:37 a.m. UTC
Hello everybody,

this is a path that should solve bug 15884. It complains about the 
performance of strcoll(). It was found out that the runtime of strcoll() 
is actually bound to strlen which is needed for calculating the size of 
a cache that was installed to improve the comparison performance.

The idea for this patch was that the cache is only useful in rare cases 
(strings of same length and same first-level-chars) and that it would be 
better to avoid memory allocation at all. To prove this I wrote a 
performance test that is found in benchtests-strcoll.tar.bz2. Also 
modifications in benchtests/Makefile and localedata/Makefile are 
necessary to make it work.

After removing the cache the strcoll method showed the predicted 
behavior (getting slightly faster) in all but the test case for hindi 
word sorting. This was due the hindi text having much more equal words 
than the other ones. For equal strings the performance was worse since 
all comparison levels were run through and from the second level on the 
cache improved the comparison performance of the original version.

Therefore I added a bytewise test via strcmp iff the first level 
comparison found that both strings did match because in this case it is 
very likely that equal strings are compared. This solved the problem 
with the hindi test case and improved the performance of the others.

Another improvement was achieved by inlineing both static subroutines.

The performance measurements on my machine are:

glibc_files.txt                     en_US.UTF-8	-61.67%
lorem_ipsum_vietnamese.txt          vi_VN.UTF-8	-55.29%
lorem_ipsum_latin.txt               en_US.UTF-8	-59.30%
lorem_ipsum_arabic.txt              ar_SA.UTF-8	-48.18%
lorem_ipsum_l33tspeak.txt           en_US.UTF-8	-57.86%
lorem_ipsum_chinese.txt             zh_CN.UTF-8	-17.21%
lorem_ipsum_czech.txt               cs_CZ.UTF-8	-47.28%
lorem_ipsum_old_english.txt         en_GB.UTF-8	-47.08%
lorem_ipsum_danish.txt              da_DK.UTF-8	-56.21%
lorem_ipsum_polish.txt              pl_PL.UTF-8	-54.80%
lorem_ipsum_french.txt              fr_FR.UTF-8	-45.35%
lorem_ipsum_portugese.txt           pt_PT.UTF-8	-46.27%
lorem_ipsum_greek.txt               el_GR.UTF-8	-40.77%
lorem_ipsum_russian.txt             ru_RU.UTF-8	-49.30%
lorem_ipsum_hebrew.txt              iw_IL.UTF-8	-50.76%
lorem_ipsum_spain.txt               es_ES.UTF-8	-50.51%
lorem_ipsum_hindi.txt               hi_IN.UTF-8	+00.90%
lorem_ipsum_swedish.txt             sv_SE.UTF-8	-56.53%
lorem_ipsum_hungarian.txt           hu_HU.UTF-8	-34.95%
lorem_ipsum_turkish.txt             tr_TR.UTF-8	-50.20%
lorem_ipsum_icelandic.txt           is_IS.UTF-8	-54.63%
lorem_ipsum_italian.txt             it_IT.UTF-8	-46.44%
lorem_ipsum_yugoslavian.txt         sr_RS.UTF-8	-54.81%
lorem_ipsum_japanese.txt            ja_JP.UTF-8	+25.56%

Best,
Leonhard

diff --git a/localedata/Makefile b/localedata/Makefile
index b6235f2..7a197a9 100644
--- a/localedata/Makefile
+++ b/localedata/Makefile
@@ -106,7 +106,10 @@ LOCALES := de_DE.ISO-8859-1 de_DE.UTF-8 en_US.ANSI_X3.4-1968 \
 	   hr_HR.ISO-8859-2 sv_SE.ISO-8859-1 ja_JP.SJIS fr_FR.ISO-8859-1 \
 	   nb_NO.ISO-8859-1 nn_NO.ISO-8859-1 tr_TR.UTF-8 cs_CZ.UTF-8 \
 	   zh_TW.EUC-TW fa_IR.UTF-8 fr_FR.UTF-8 ja_JP.UTF-8 si_LK.UTF-8 \
-	   tr_TR.ISO-8859-9 en_GB.UTF-8
+	   tr_TR.ISO-8859-9 en_GB.UTF-8 vi_VN.UTF-8 ar_SA.UTF-8 zh_CN.UTF-8 \
+       da_DK.UTF-8 pl_PL.UTF-8 pt_PT.UTF-8 el_GR.UTF-8 ru_RU.UTF-8 \
+       iw_IL.UTF-8 es_ES.UTF-8 hi_IN.UTF-8 sv_SE.UTF-8 hu_HU.UTF-8 \
+       is_IS.UTF-8 it_IT.UTF-8 sr_RS.UTF-8
 LOCALE_SRCS := $(shell echo "$(LOCALES)"|sed 's/\([^ .]*\)[^ ]*/\1/g')
 CHARMAPS := $(shell echo "$(LOCALES)" | \
 		    sed -e 's/[^ .]*[.]\([^ ]*\)/\1/g' -e s/SJIS/SHIFT_JIS/g)
diff --git a/string/strcoll_l.c b/string/strcoll_l.c
index d4f42a3..e1377cc 100644
--- a/string/strcoll_l.c
+++ b/string/strcoll_l.c
@@ -22,19 +22,18 @@
 #include <locale.h>
 #include <stddef.h>
 #include <stdint.h>
-#include <stdlib.h>
 #include <string.h>
 #include <sys/param.h>
 
 #ifndef STRING_TYPE
-# define STRING_TYPE char
-# define USTRING_TYPE unsigned char
-# define STRCOLL __strcoll_l
-# define STRCMP strcmp
-# define STRLEN strlen
-# define WEIGHT_H "../locale/weight.h"
-# define SUFFIX	MB
-# define L(arg) arg
+#define STRING_TYPE char
+#define USTRING_TYPE unsigned char
+#define STRCOLL __strcoll_l
+#define STRCMP strcmp
+#define STRLEN strlen
+#define WEIGHT_H "../locale/weight.h"
+#define SUFFIX	MB
+#define L(arg) arg
 #endif
 
 #define CONCAT(a,b) CONCAT1(a,b)
@@ -55,8 +54,6 @@ typedef struct
   size_t backw;			/* Current Backward sequence index.  */
   size_t backw_stop;		/* Index where the backward sequences stop.  */
   const USTRING_TYPE *us;	/* The string.  */
-  int32_t *idxarr;		/* Array to cache weight indices.  */
-  unsigned char *rulearr;	/* Array to cache rules.  */
   unsigned char rule;		/* Saved rule for the first sequence.  */
   int32_t idx;			/* Index to weight of the current sequence.  */
   int32_t save_idx;		/* Save looked up index of a forward
@@ -65,182 +62,12 @@ typedef struct
   const USTRING_TYPE *back_us;	/* Beginning of the backward sequence.  */
 } coll_seq;
 
-/* Get next sequence.  The weight indices are cached, so we don't need to
-   traverse the string.  */
-static void
-get_next_seq_cached (coll_seq *seq, int nrules, int pass,
-		     const unsigned char *rulesets,
-		     const USTRING_TYPE *weights)
-{
-  size_t val = seq->val = 0;
-  int len = seq->len;
-  size_t backw_stop = seq->backw_stop;
-  size_t backw = seq->backw;
-  size_t idxcnt = seq->idxcnt;
-  size_t idxmax = seq->idxmax;
-  size_t idxnow = seq->idxnow;
-  unsigned char *rulearr = seq->rulearr;
-  int32_t *idxarr = seq->idxarr;
-
-  while (len == 0)
-    {
-      ++val;
-      if (backw_stop != ~0ul)
-	{
-	  /* There is something pushed.  */
-	  if (backw == backw_stop)
-	    {
-	      /* The last pushed character was handled.  Continue
-		 with forward characters.  */
-	      if (idxcnt < idxmax)
-		{
-		  idxnow = idxcnt;
-		  backw_stop = ~0ul;
-		}
-	      else
-		{
-		  /* Nothing any more.  The backward sequence
-		     ended with the last sequence in the string.  */
-		  idxnow = ~0ul;
-		  break;
-		}
-	    }
-	  else
-	    idxnow = --backw;
-	}
-      else
-	{
-	  backw_stop = idxcnt;
-
-	  while (idxcnt < idxmax)
-	    {
-	      if ((rulesets[rulearr[idxcnt] * nrules + pass]
-		   & sort_backward) == 0)
-		/* No more backward characters to push.  */
-		break;
-	      ++idxcnt;
-	    }
-
-	  if (backw_stop == idxcnt)
-	    {
-	      /* No sequence at all or just one.  */
-	      if (idxcnt == idxmax)
-		/* Note that LEN is still zero.  */
-		break;
-
-	      backw_stop = ~0ul;
-	      idxnow = idxcnt++;
-	    }
-	  else
-	    /* We pushed backward sequences.  */
-	    idxnow = backw = idxcnt - 1;
-	}
-      len = weights[idxarr[idxnow]++];
-    }
-
-  /* Update the structure.  */
-  seq->val = val;
-  seq->len = len;
-  seq->backw_stop = backw_stop;
-  seq->backw = backw;
-  seq->idxcnt = idxcnt;
-  seq->idxnow = idxnow;
-}
-
-/* Get next sequence.  Traverse the string as required.  */
-static void
-get_next_seq (coll_seq *seq, int nrules, const unsigned char *rulesets,
-	      const USTRING_TYPE *weights, const int32_t *table,
-	      const USTRING_TYPE *extra, const int32_t *indirect)
-{
-  size_t val = seq->val = 0;
-  int len = seq->len;
-  size_t backw_stop = seq->backw_stop;
-  size_t backw = seq->backw;
-  size_t idxcnt = seq->idxcnt;
-  size_t idxmax = seq->idxmax;
-  size_t idxnow = seq->idxnow;
-  unsigned char *rulearr = seq->rulearr;
-  int32_t *idxarr = seq->idxarr;
-  const USTRING_TYPE *us = seq->us;
-
-  while (len == 0)
-    {
-      ++val;
-      if (backw_stop != ~0ul)
-	{
-	  /* There is something pushed.  */
-	  if (backw == backw_stop)
-	    {
-	      /* The last pushed character was handled.  Continue
-		 with forward characters.  */
-	      if (idxcnt < idxmax)
-		{
-		  idxnow = idxcnt;
-		  backw_stop = ~0ul;
-		}
-	      else
-		/* Nothing any more.  The backward sequence ended with
-		   the last sequence in the string.  Note that LEN
-		   is still zero.  */
-		break;
-	    }
-	  else
-	    idxnow = --backw;
-	}
-      else
-	{
-	  backw_stop = idxmax;
-
-	  while (*us != L('\0'))
-	    {
-	      int32_t tmp = findidx (table, indirect, extra, &us, -1);
-	      rulearr[idxmax] = tmp >> 24;
-	      idxarr[idxmax] = tmp & 0xffffff;
-	      idxcnt = idxmax++;
-
-	      if ((rulesets[rulearr[idxcnt] * nrules]
-		   & sort_backward) == 0)
-		/* No more backward characters to push.  */
-		break;
-	      ++idxcnt;
-	    }
-
-	  if (backw_stop >= idxcnt)
-	    {
-	      /* No sequence at all or just one.  */
-	      if (idxcnt == idxmax || backw_stop > idxcnt)
-		/* Note that LEN is still zero.  */
-		break;
-
-	      backw_stop = ~0ul;
-	      idxnow = idxcnt;
-	    }
-	  else
-	    /* We pushed backward sequences.  */
-	    idxnow = backw = idxcnt - 1;
-	}
-      len = weights[idxarr[idxnow]++];
-    }
-
-  /* Update the structure.  */
-  seq->val = val;
-  seq->len = len;
-  seq->backw_stop = backw_stop;
-  seq->backw = backw;
-  seq->idxcnt = idxcnt;
-  seq->idxmax = idxmax;
-  seq->idxnow = idxnow;
-  seq->us = us;
-}
-
 /* Get next sequence.  Traverse the string as required.  This function does not
    set or use any index or rule cache.  */
-static void
-get_next_seq_nocache (coll_seq *seq, int nrules, const unsigned char *rulesets,
-		      const USTRING_TYPE *weights, const int32_t *table,
-		      const USTRING_TYPE *extra, const int32_t *indirect,
-		      int pass)
+static __inline__ void
+get_next_seq (coll_seq * seq, int nrules, const unsigned char *rulesets,
+	      const USTRING_TYPE * weights, const int32_t * table,
+	      const USTRING_TYPE * extra, const int32_t * indirect, int pass)
 {
   size_t val = seq->val = 0;
   int len = seq->len;
@@ -260,7 +87,7 @@ get_next_seq_nocache (coll_seq *seq, int nrules, const unsigned char *rulesets,
 	  if (backw == backw_stop)
 	    {
 	      /* The last pushed character was handled.  Continue
-		 with forward characters.  */
+	         with forward characters.  */
 	      if (idxcnt < idxmax)
 		{
 		  idx = seq->save_idx;
@@ -273,12 +100,12 @@ get_next_seq_nocache (coll_seq *seq, int nrules, const unsigned char *rulesets,
 		     still zero.  */
 		  idx = 0;
 		  break;
-	        }
+		}
 	    }
 	  else
 	    {
 	      /* XXX Traverse BACKW sequences from the beginning of
-		 BACKW_STOP to get the next sequence.  Is ther a quicker way
+	         BACKW_STOP to get the next sequence.  Is ther a quicker way
 	         to do this?  */
 	      size_t i = backw_stop;
 	      us = seq->back_us;
@@ -297,7 +124,7 @@ get_next_seq_nocache (coll_seq *seq, int nrules, const unsigned char *rulesets,
 	  backw_stop = idxmax;
 	  int32_t prev_idx = idx;
 
-	  while (*us != L('\0'))
+	  while (*us != L ('\0'))
 	    {
 	      int32_t tmp = findidx (table, indirect, extra, &us, -1);
 	      unsigned char rule = tmp >> 24;
@@ -307,10 +134,9 @@ get_next_seq_nocache (coll_seq *seq, int nrules, const unsigned char *rulesets,
 
 	      /* Save the rule for the first sequence.  */
 	      if (__glibc_unlikely (idxcnt == 0))
-	        seq->rule = rule;
+		seq->rule = rule;
 
-	      if ((rulesets[rule * nrules + pass]
-		   & sort_backward) == 0)
+	      if ((rulesets[rule * nrules + pass] & sort_backward) == 0)
 		/* No more backward characters to push.  */
 		break;
 	      ++idxcnt;
@@ -322,15 +148,14 @@ get_next_seq_nocache (coll_seq *seq, int nrules, const unsigned char *rulesets,
 	      if (idxcnt == idxmax || backw_stop > idxcnt)
 		/* Note that len is still zero.  */
 		break;
-
 	      backw_stop = ~0ul;
 	    }
 	  else
 	    {
 	      /* We pushed backward sequences.  If the stream ended with the
-		 backward sequence, then we process the last sequence we
-		 found.  Otherwise we process the sequence before the last
-		 one since the last one was a forward sequence.  */
+	         backward sequence, then we process the last sequence we
+	         found.  Otherwise we process the sequence before the last
+	         one since the last one was a forward sequence.  */
 	      seq->back_us = seq->us;
 	      seq->us = us;
 	      backw = idxcnt;
@@ -368,9 +193,9 @@ get_next_seq_nocache (coll_seq *seq, int nrules, const unsigned char *rulesets,
 
 /* Compare two sequences.  This version does not use the index and rules
    cache.  */
-static int
-do_compare_nocache (coll_seq *seq1, coll_seq *seq2, int position,
-		    const USTRING_TYPE *weights)
+static __inline__ int
+do_compare (coll_seq * seq1, coll_seq * seq2, int position,
+	    const USTRING_TYPE * weights)
 {
   int seq1len = seq1->len;
   int seq2len = seq2->len;
@@ -417,61 +242,12 @@ out:
   return result;
 }
 
-/* Compare two sequences using the index cache.  */
-static int
-do_compare (coll_seq *seq1, coll_seq *seq2, int position,
-	    const USTRING_TYPE *weights)
-{
-  int seq1len = seq1->len;
-  int seq2len = seq2->len;
-  size_t val1 = seq1->val;
-  size_t val2 = seq2->val;
-  int32_t *idx1arr = seq1->idxarr;
-  int32_t *idx2arr = seq2->idxarr;
-  int idx1now = seq1->idxnow;
-  int idx2now = seq2->idxnow;
-  int result = 0;
-
-  /* Test for position if necessary.  */
-  if (position && val1 != val2)
-    {
-      result = val1 > val2 ? 1 : -1;
-      goto out;
-    }
-
-  /* Compare the two sequences.  */
-  do
-    {
-      if (weights[idx1arr[idx1now]] != weights[idx2arr[idx2now]])
-	{
-	  /* The sequences differ.  */
-	  result = weights[idx1arr[idx1now]] - weights[idx2arr[idx2now]];
-	  goto out;
-	}
-
-      /* Increment the offsets.  */
-      ++idx1arr[idx1now];
-      ++idx2arr[idx2now];
-
-      --seq1len;
-      --seq2len;
-    }
-  while (seq1len > 0 && seq2len > 0);
-
-  if (position && seq1len != seq2len)
-    result = seq1len - seq2len;
-
-out:
-  seq1->len = seq1len;
-  seq2->len = seq2len;
-  return result;
-}
-
 int
-STRCOLL (const STRING_TYPE *s1, const STRING_TYPE *s2, __locale_t l)
+STRCOLL (const STRING_TYPE * s1, const STRING_TYPE * s2, __locale_t l)
 {
   struct __locale_data *current = l->__locales[LC_COLLATE];
-  uint_fast32_t nrules = current->values[_NL_ITEM_INDEX (_NL_COLLATE_NRULES)].word;
+  uint_fast32_t nrules =
+    current->values[_NL_ITEM_INDEX (_NL_COLLATE_NRULES)].word;
   /* We don't assign the following values right away since it might be
      unnecessary in case there are no rules.  */
   const unsigned char *rulesets;
@@ -483,79 +259,36 @@ STRCOLL (const STRING_TYPE *s1, const STRING_TYPE *s2, __locale_t l)
   if (nrules == 0)
     return STRCMP (s1, s2);
 
+  /* Catch empty strings.  */
+  if (__glibc_unlikely (*s1 == '\0') || __glibc_unlikely (*s2 == '\0'))
+    return (*s1 != '\0') - (*s2 != '\0');
+
   rulesets = (const unsigned char *)
     current->values[_NL_ITEM_INDEX (_NL_COLLATE_RULESETS)].string;
   table = (const int32_t *)
-    current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_TABLE,SUFFIX))].string;
-  weights = (const USTRING_TYPE *)
-    current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_WEIGHT,SUFFIX))].string;
-  extra = (const USTRING_TYPE *)
-    current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_EXTRA,SUFFIX))].string;
-  indirect = (const int32_t *)
-    current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_INDIRECT,SUFFIX))].string;
+    current->values[_NL_ITEM_INDEX (CONCAT (_NL_COLLATE_TABLE, SUFFIX))].
+    string;
+  weights =
+    (const USTRING_TYPE *) current->
+    values[_NL_ITEM_INDEX (CONCAT (_NL_COLLATE_WEIGHT, SUFFIX))].string;
+  extra =
+    (const USTRING_TYPE *) current->
+    values[_NL_ITEM_INDEX (CONCAT (_NL_COLLATE_EXTRA, SUFFIX))].string;
+  indirect =
+    (const int32_t *) current->
+    values[_NL_ITEM_INDEX (CONCAT (_NL_COLLATE_INDIRECT, SUFFIX))].string;
 
   assert (((uintptr_t) table) % __alignof__ (table[0]) == 0);
   assert (((uintptr_t) weights) % __alignof__ (weights[0]) == 0);
   assert (((uintptr_t) extra) % __alignof__ (extra[0]) == 0);
   assert (((uintptr_t) indirect) % __alignof__ (indirect[0]) == 0);
 
-  /* We need this a few times.  */
-  size_t s1len = STRLEN (s1);
-  size_t s2len = STRLEN (s2);
-
-  /* Catch empty strings.  */
-  if (__glibc_unlikely (s1len == 0) || __glibc_unlikely (s2len == 0))
-    return (s1len != 0) - (s2len != 0);
-
-  /* Perform the first pass over the string and while doing this find
-     and store the weights for each character.  Since we want this to
-     be as fast as possible we are using `alloca' to store the temporary
-     values.  But since there is no limit on the length of the string
-     we have to use `malloc' if the string is too long.  We should be
-     very conservative here.
-
-     Please note that the localedef programs makes sure that `position'
-     is not used at the first level.  */
+  int result = 0, rule = 0;
 
   coll_seq seq1, seq2;
-  bool use_malloc = false;
-  int result = 0;
-
   memset (&seq1, 0, sizeof (seq1));
   seq2 = seq1;
 
-  size_t size_max = SIZE_MAX / (sizeof (int32_t) + 1);
-
-  if (MIN (s1len, s2len) > size_max
-      || MAX (s1len, s2len) > size_max - MIN (s1len, s2len))
-    {
-      /* If the strings are long enough to cause overflow in the size request,
-         then skip the allocation and proceed with the non-cached routines.  */
-    }
-  else if (! __libc_use_alloca ((s1len + s2len) * (sizeof (int32_t) + 1)))
-    {
-      seq1.idxarr = (int32_t *) malloc ((s1len + s2len) * (sizeof (int32_t) + 1));
-
-      /* If we failed to allocate memory, we leave everything as NULL so that
-	 we use the nocache version of traversal and comparison functions.  */
-      if (seq1.idxarr != NULL)
-	{
-	  seq2.idxarr = &seq1.idxarr[s1len];
-	  seq1.rulearr = (unsigned char *) &seq2.idxarr[s2len];
-	  seq2.rulearr = &seq1.rulearr[s1len];
-	  use_malloc = true;
-	}
-    }
-  else
-    {
-      seq1.idxarr = (int32_t *) alloca (s1len * sizeof (int32_t));
-      seq2.idxarr = (int32_t *) alloca (s2len * sizeof (int32_t));
-      seq1.rulearr = (unsigned char *) alloca (s1len);
-      seq2.rulearr = (unsigned char *) alloca (s2len);
-    }
-
-  int rule = 0;
-
   /* Cache values in the first pass and if needed, use them in subsequent
      passes.  */
   for (int pass = 0; pass < nrules; ++pass)
@@ -570,73 +303,54 @@ STRCOLL (const STRING_TYPE *s1, const STRING_TYPE *s2, __locale_t l)
       seq2.backw = ~0ul;
 
       /* We need the elements of the strings as unsigned values since they
-	 are used as indices.  */
+         are used as indices.  */
       seq1.us = (const USTRING_TYPE *) s1;
       seq2.us = (const USTRING_TYPE *) s2;
 
       /* We assume that if a rule has defined `position' in one section
-	 this is true for all of them.  */
+         this is true for all of them.  */
+      /* Please note that the localedef programs makes sure that `position'
+         is not used at the first level.  */
+
       int position = rulesets[rule * nrules + pass] & sort_position;
 
       while (1)
 	{
-	  if (__glibc_unlikely (seq1.idxarr == NULL))
-	    {
-	      get_next_seq_nocache (&seq1, nrules, rulesets, weights, table,
-				    extra, indirect, pass);
-	      get_next_seq_nocache (&seq2, nrules, rulesets, weights, table,
-				    extra, indirect, pass);
-	    }
-	  else if (pass == 0)
-	    {
-	      get_next_seq (&seq1, nrules, rulesets, weights, table, extra,
-			    indirect);
-	      get_next_seq (&seq2, nrules, rulesets, weights, table, extra,
-			    indirect);
-	    }
-	  else
-	    {
-	      get_next_seq_cached (&seq1, nrules, pass, rulesets, weights);
-	      get_next_seq_cached (&seq2, nrules, pass, rulesets, weights);
-	    }
-
+	  get_next_seq (&seq1, nrules, rulesets, weights, table,
+			extra, indirect, pass);
+	  get_next_seq (&seq2, nrules, rulesets, weights, table,
+			extra, indirect, pass);
 	  /* See whether any or both strings are empty.  */
 	  if (seq1.len == 0 || seq2.len == 0)
 	    {
 	      if (seq1.len == seq2.len)
-		/* Both ended.  So far so good, both strings are equal
-		   at this level.  */
-		break;
+		{
+		  /* Both ended.  So far so good, both strings are equal
+		     at this level. */
+		  if (pass == 0 && STRCMP (s1, s2) == 0)
+		    /* Shortcut to avoid looping through all levels
+		       for totally equal strings. */
+		    return result;
+		  else
+		    break;
+		}
 
 	      /* This means one string is shorter than the other.  Find out
-		 which one and return an appropriate value.  */
-	      result = seq1.len == 0 ? -1 : 1;
-	      goto free_and_return;
+	         which one and return an appropriate value.  */
+	      return seq1.len == 0 ? -1 : 1;
 	    }
 
-	  if (__glibc_unlikely (seq1.idxarr == NULL))
-	    result = do_compare_nocache (&seq1, &seq2, position, weights);
-	  else
-	    result = do_compare (&seq1, &seq2, position, weights);
+	  result = do_compare (&seq1, &seq2, position, weights);
 	  if (result != 0)
-	    goto free_and_return;
+	    return result;
 	}
-
-      if (__glibc_likely (seq1.rulearr != NULL))
-	rule = seq1.rulearr[0];
-      else
-	rule = seq1.rule;
+      rule = seq1.rule;
     }
 
-  /* Free the memory if needed.  */
- free_and_return:
-  if (use_malloc)
-    free (seq1.idxarr);
-
   return result;
 }
-libc_hidden_def (STRCOLL)
 
+libc_hidden_def (STRCOLL)
 #ifndef WIDE_CHAR_VERSION
-weak_alias (__strcoll_l, strcoll_l)
+  weak_alias (__strcoll_l, strcoll_l)
 #endif

Comments

Siddhesh Poyarekar Sept. 24, 2014, 10:02 a.m. UTC | #1
On Wed, Sep 24, 2014 at 10:37:21AM +0200, Leonhard Holz wrote:
> Hello everybody,
> 
> this is a path that should solve bug 15884. It complains about the
> performance of strcoll(). It was found out that the runtime of strcoll() is
> actually bound to strlen which is needed for calculating the size of a cache
> that was installed to improve the comparison performance.
> 
> The idea for this patch was that the cache is only useful in rare cases
> (strings of same length and same first-level-chars) and that it would be
> better to avoid memory allocation at all. To prove this I wrote a
> performance test that is found in benchtests-strcoll.tar.bz2. Also
> modifications in benchtests/Makefile and localedata/Makefile are necessary
> to make it work.
> 
> After removing the cache the strcoll method showed the predicted behavior
> (getting slightly faster) in all but the test case for hindi word sorting.
> This was due the hindi text having much more equal words than the other
> ones. For equal strings the performance was worse since all comparison
> levels were run through and from the second level on the cache improved the
> comparison performance of the original version.
> 
> Therefore I added a bytewise test via strcmp iff the first level comparison
> found that both strings did match because in this case it is very likely
> that equal strings are compared. This solved the problem with the hindi test
> case and improved the performance of the others.

Thanks for working on this and also writing a benchmark for it.  The
general approach seems sound to me (I haven't done a deep review yet),
but there are quite a few nits that will need to be worked out, most
of them covered in the contributor checklist[1].

- There are a lot of unrelated whitespace and formatting changes in
  the patch.  Most of them seem to have been made using the GNU indent
  program, which is mostly accurate, but not completely.  Please
  review and fix them up.

- The change needs a changelog which mentions all your changes,
  including all the new files.

- Please include bench-strcoll.c in the patch as well.  It's OK if you
  post the input files in the tarball but the source needs to be
  reviewed.

- bench-strcoll.c has some code formatting issues, especially
  unnecessary braces around single line for/if blocks.

> Another improvement was achieved by inlineing both static subroutines.

- Please post the inlining change separately with separate numbers for
  it.  In general we stay away from inlining functions and just let
  the compiler do its job.  However if there is a case where such
  inlining is especially useful, it needs to be accompanied with
  numbers.  So a separate patch with separate numbers for the change
  would be helpful.

- Finally, I don't know if you have signed a copyright assignment with
  the FSF for your changes.  Carlos seems to have mentioned that in
  your previous email thread, but I don't know if you've followed
  through on it since I am not an FSF maintainer.  Maybe one of the
  FSF maintainers can confirm that.

Siddhesh

[1] https://sourceware.org/glibc/wiki/Contribution%20checklist
Siddhesh Poyarekar Sept. 25, 2014, 4:43 a.m. UTC | #2
[Please keep the conversation on list since this information would be
useful in general for those searching the archives]

On Wed, Sep 24, 2014 at 09:39:29PM +0200, Leonhard Holz wrote:
> thanks for your feedback. You are right, I did an "intend" on the sources.
> Though I read https://sourceware.org/glibc/wiki/Style_and_Conventions, I am
> not sure in which details the glibc formating rules differ from the
> GNU/ident standard. Can you give me a hint?

It's not just about incorrect formatting, but also about separating
formatting and whitespace changes from the actual change you're trying
to make so that the code change is minimal.

I'll point out specific problems in the patch and I hope you'll be
able to use that information to improve bench-strcoll.c too.


On Wed, Sep 24, 2014 at 10:37:21AM +0200, Leonhard Holz wrote:
> diff --git a/localedata/Makefile b/localedata/Makefile
> index b6235f2..7a197a9 100644
> --- a/localedata/Makefile
> +++ b/localedata/Makefile
> @@ -106,7 +106,10 @@ LOCALES := de_DE.ISO-8859-1 de_DE.UTF-8 en_US.ANSI_X3.4-1968 \
>  	   hr_HR.ISO-8859-2 sv_SE.ISO-8859-1 ja_JP.SJIS fr_FR.ISO-8859-1 \
>  	   nb_NO.ISO-8859-1 nn_NO.ISO-8859-1 tr_TR.UTF-8 cs_CZ.UTF-8 \
>  	   zh_TW.EUC-TW fa_IR.UTF-8 fr_FR.UTF-8 ja_JP.UTF-8 si_LK.UTF-8 \
> -	   tr_TR.ISO-8859-9 en_GB.UTF-8
> +	   tr_TR.ISO-8859-9 en_GB.UTF-8 vi_VN.UTF-8 ar_SA.UTF-8 zh_CN.UTF-8 \
> +       da_DK.UTF-8 pl_PL.UTF-8 pt_PT.UTF-8 el_GR.UTF-8 ru_RU.UTF-8 \
> +       iw_IL.UTF-8 es_ES.UTF-8 hi_IN.UTF-8 sv_SE.UTF-8 hu_HU.UTF-8 \
> +       is_IS.UTF-8 it_IT.UTF-8 sr_RS.UTF-8

These are not aligned correctly, as you can see.

>  LOCALE_SRCS := $(shell echo "$(LOCALES)"|sed 's/\([^ .]*\)[^ ]*/\1/g')
>  CHARMAPS := $(shell echo "$(LOCALES)" | \
>  		    sed -e 's/[^ .]*[.]\([^ ]*\)/\1/g' -e s/SJIS/SHIFT_JIS/g)

> diff --git a/string/strcoll_l.c b/string/strcoll_l.c
> index d4f42a3..e1377cc 100644
> --- a/string/strcoll_l.c
> +++ b/string/strcoll_l.c
> @@ -22,19 +22,18 @@
>  #include <locale.h>
>  #include <stddef.h>
>  #include <stdint.h>
> -#include <stdlib.h>
>  #include <string.h>
>  #include <sys/param.h>
>  
>  #ifndef STRING_TYPE
> -# define STRING_TYPE char
> -# define USTRING_TYPE unsigned char
> -# define STRCOLL __strcoll_l
> -# define STRCMP strcmp
> -# define STRLEN strlen
> -# define WEIGHT_H "../locale/weight.h"
> -# define SUFFIX	MB
> -# define L(arg) arg
> +#define STRING_TYPE char
> +#define USTRING_TYPE unsigned char
> +#define STRCOLL __strcoll_l
> +#define STRCMP strcmp
> +#define STRLEN strlen
> +#define WEIGHT_H "../locale/weight.h"
> +#define SUFFIX	MB
> +#define L(arg) arg

indent made this change, which is unnecessary and in fact wrong
according to the GNU standards.  We want the one space indentation.

>  #endif
>  
>  #define CONCAT(a,b) CONCAT1(a,b)
> @@ -55,8 +54,6 @@ typedef struct
>    size_t backw;			/* Current Backward sequence index.  */
>    size_t backw_stop;		/* Index where the backward sequences stop.  */
>    const USTRING_TYPE *us;	/* The string.  */
> -  int32_t *idxarr;		/* Array to cache weight indices.  */
> -  unsigned char *rulearr;	/* Array to cache rules.  */
>    unsigned char rule;		/* Saved rule for the first sequence.  */
>    int32_t idx;			/* Index to weight of the current sequence.  */
>    int32_t save_idx;		/* Save looked up index of a forward
> @@ -65,182 +62,12 @@ typedef struct
>    const USTRING_TYPE *back_us;	/* Beginning of the backward sequence.  */
>  } coll_seq;
>  
> -/* Get next sequence.  The weight indices are cached, so we don't need to
> -   traverse the string.  */
> -static void
> -get_next_seq_cached (coll_seq *seq, int nrules, int pass,
> -		     const unsigned char *rulesets,
> -		     const USTRING_TYPE *weights)
> -{
> -  size_t val = seq->val = 0;
> -  int len = seq->len;
> -  size_t backw_stop = seq->backw_stop;
> -  size_t backw = seq->backw;
> -  size_t idxcnt = seq->idxcnt;
> -  size_t idxmax = seq->idxmax;
> -  size_t idxnow = seq->idxnow;
> -  unsigned char *rulearr = seq->rulearr;
> -  int32_t *idxarr = seq->idxarr;
> -
> -  while (len == 0)
> -    {
> -      ++val;
> -      if (backw_stop != ~0ul)
> -	{
> -	  /* There is something pushed.  */
> -	  if (backw == backw_stop)
> -	    {
> -	      /* The last pushed character was handled.  Continue
> -		 with forward characters.  */
> -	      if (idxcnt < idxmax)
> -		{
> -		  idxnow = idxcnt;
> -		  backw_stop = ~0ul;
> -		}
> -	      else
> -		{
> -		  /* Nothing any more.  The backward sequence
> -		     ended with the last sequence in the string.  */
> -		  idxnow = ~0ul;
> -		  break;
> -		}
> -	    }
> -	  else
> -	    idxnow = --backw;
> -	}
> -      else
> -	{
> -	  backw_stop = idxcnt;
> -
> -	  while (idxcnt < idxmax)
> -	    {
> -	      if ((rulesets[rulearr[idxcnt] * nrules + pass]
> -		   & sort_backward) == 0)
> -		/* No more backward characters to push.  */
> -		break;
> -	      ++idxcnt;
> -	    }
> -
> -	  if (backw_stop == idxcnt)
> -	    {
> -	      /* No sequence at all or just one.  */
> -	      if (idxcnt == idxmax)
> -		/* Note that LEN is still zero.  */
> -		break;
> -
> -	      backw_stop = ~0ul;
> -	      idxnow = idxcnt++;
> -	    }
> -	  else
> -	    /* We pushed backward sequences.  */
> -	    idxnow = backw = idxcnt - 1;
> -	}
> -      len = weights[idxarr[idxnow]++];
> -    }
> -
> -  /* Update the structure.  */
> -  seq->val = val;
> -  seq->len = len;
> -  seq->backw_stop = backw_stop;
> -  seq->backw = backw;
> -  seq->idxcnt = idxcnt;
> -  seq->idxnow = idxnow;
> -}
> -
> -/* Get next sequence.  Traverse the string as required.  */
> -static void
> -get_next_seq (coll_seq *seq, int nrules, const unsigned char *rulesets,
> -	      const USTRING_TYPE *weights, const int32_t *table,
> -	      const USTRING_TYPE *extra, const int32_t *indirect)
> -{
> -  size_t val = seq->val = 0;
> -  int len = seq->len;
> -  size_t backw_stop = seq->backw_stop;
> -  size_t backw = seq->backw;
> -  size_t idxcnt = seq->idxcnt;
> -  size_t idxmax = seq->idxmax;
> -  size_t idxnow = seq->idxnow;
> -  unsigned char *rulearr = seq->rulearr;
> -  int32_t *idxarr = seq->idxarr;
> -  const USTRING_TYPE *us = seq->us;
> -
> -  while (len == 0)
> -    {
> -      ++val;
> -      if (backw_stop != ~0ul)
> -	{
> -	  /* There is something pushed.  */
> -	  if (backw == backw_stop)
> -	    {
> -	      /* The last pushed character was handled.  Continue
> -		 with forward characters.  */
> -	      if (idxcnt < idxmax)
> -		{
> -		  idxnow = idxcnt;
> -		  backw_stop = ~0ul;
> -		}
> -	      else
> -		/* Nothing any more.  The backward sequence ended with
> -		   the last sequence in the string.  Note that LEN
> -		   is still zero.  */
> -		break;
> -	    }
> -	  else
> -	    idxnow = --backw;
> -	}
> -      else
> -	{
> -	  backw_stop = idxmax;
> -
> -	  while (*us != L('\0'))
> -	    {
> -	      int32_t tmp = findidx (table, indirect, extra, &us, -1);
> -	      rulearr[idxmax] = tmp >> 24;
> -	      idxarr[idxmax] = tmp & 0xffffff;
> -	      idxcnt = idxmax++;
> -
> -	      if ((rulesets[rulearr[idxcnt] * nrules]
> -		   & sort_backward) == 0)
> -		/* No more backward characters to push.  */
> -		break;
> -	      ++idxcnt;
> -	    }
> -
> -	  if (backw_stop >= idxcnt)
> -	    {
> -	      /* No sequence at all or just one.  */
> -	      if (idxcnt == idxmax || backw_stop > idxcnt)
> -		/* Note that LEN is still zero.  */
> -		break;
> -
> -	      backw_stop = ~0ul;
> -	      idxnow = idxcnt;
> -	    }
> -	  else
> -	    /* We pushed backward sequences.  */
> -	    idxnow = backw = idxcnt - 1;
> -	}
> -      len = weights[idxarr[idxnow]++];
> -    }
> -
> -  /* Update the structure.  */
> -  seq->val = val;
> -  seq->len = len;
> -  seq->backw_stop = backw_stop;
> -  seq->backw = backw;
> -  seq->idxcnt = idxcnt;
> -  seq->idxmax = idxmax;
> -  seq->idxnow = idxnow;
> -  seq->us = us;
> -}
> -
>  /* Get next sequence.  Traverse the string as required.  This function does not
>     set or use any index or rule cache.  */
> -static void
> -get_next_seq_nocache (coll_seq *seq, int nrules, const unsigned char *rulesets,
> -		      const USTRING_TYPE *weights, const int32_t *table,
> -		      const USTRING_TYPE *extra, const int32_t *indirect,
> -		      int pass)
> +static __inline__ void

This should go as a separate change with benchmark numbers to support
it.  Also, use __always_inline (a macro in glibc) instead of the
__inline__.

> +get_next_seq (coll_seq * seq, int nrules, const unsigned char *rulesets,
> +	      const USTRING_TYPE * weights, const int32_t * table,
> +	      const USTRING_TYPE * extra, const int32_t * indirect, int pass)
>  {
>    size_t val = seq->val = 0;
>    int len = seq->len;
> @@ -260,7 +87,7 @@ get_next_seq_nocache (coll_seq *seq, int nrules, const unsigned char *rulesets,
>  	  if (backw == backw_stop)
>  	    {
>  	      /* The last pushed character was handled.  Continue
> -		 with forward characters.  */
> +	         with forward characters.  */

Incorrect whitespace change.

>  	      if (idxcnt < idxmax)
>  		{
>  		  idx = seq->save_idx;
> @@ -273,12 +100,12 @@ get_next_seq_nocache (coll_seq *seq, int nrules, const unsigned char *rulesets,
>  		     still zero.  */
>  		  idx = 0;
>  		  break;
> -	        }
> +		}

Incorrect whitespace change.

>  	    }
>  	  else
>  	    {
>  	      /* XXX Traverse BACKW sequences from the beginning of
> -		 BACKW_STOP to get the next sequence.  Is ther a quicker way
> +	         BACKW_STOP to get the next sequence.  Is ther a quicker way

Incorrect whitespace change.

>  	         to do this?  */
>  	      size_t i = backw_stop;
>  	      us = seq->back_us;
> @@ -297,7 +124,7 @@ get_next_seq_nocache (coll_seq *seq, int nrules, const unsigned char *rulesets,
>  	  backw_stop = idxmax;
>  	  int32_t prev_idx = idx;
>  
> -	  while (*us != L('\0'))
> +	  while (*us != L ('\0'))

Incorrect whitespace change.

>  	    {
>  	      int32_t tmp = findidx (table, indirect, extra, &us, -1);
>  	      unsigned char rule = tmp >> 24;
> @@ -307,10 +134,9 @@ get_next_seq_nocache (coll_seq *seq, int nrules, const unsigned char *rulesets,
>  
>  	      /* Save the rule for the first sequence.  */
>  	      if (__glibc_unlikely (idxcnt == 0))
> -	        seq->rule = rule;
> +		seq->rule = rule;
>  

Incorrect whitespace change.

> -	      if ((rulesets[rule * nrules + pass]
> -		   & sort_backward) == 0)
> +	      if ((rulesets[rule * nrules + pass] & sort_backward) == 0)

This is correct, but should go as a separate change.

>  		/* No more backward characters to push.  */
>  		break;
>  	      ++idxcnt;
> @@ -322,15 +148,14 @@ get_next_seq_nocache (coll_seq *seq, int nrules, const unsigned char *rulesets,
>  	      if (idxcnt == idxmax || backw_stop > idxcnt)
>  		/* Note that len is still zero.  */
>  		break;
> -

Incorrect whitespace change.

>  	      backw_stop = ~0ul;
>  	    }
>  	  else
>  	    {
>  	      /* We pushed backward sequences.  If the stream ended with the
> -		 backward sequence, then we process the last sequence we
> -		 found.  Otherwise we process the sequence before the last
> -		 one since the last one was a forward sequence.  */
> +	         backward sequence, then we process the last sequence we
> +	         found.  Otherwise we process the sequence before the last
> +	         one since the last one was a forward sequence.  */

Incorrect whitespace change.

>  	      seq->back_us = seq->us;
>  	      seq->us = us;
>  	      backw = idxcnt;
> @@ -368,9 +193,9 @@ get_next_seq_nocache (coll_seq *seq, int nrules, const unsigned char *rulesets,
>  
>  /* Compare two sequences.  This version does not use the index and rules
>     cache.  */
> -static int
> -do_compare_nocache (coll_seq *seq1, coll_seq *seq2, int position,
> -		    const USTRING_TYPE *weights)
> +static __inline__ int

The earlier comment about __inline__ applies here too.

> +do_compare (coll_seq * seq1, coll_seq * seq2, int position,
> +	    const USTRING_TYPE * weights)
>  {
>    int seq1len = seq1->len;
>    int seq2len = seq2->len;
> @@ -417,61 +242,12 @@ out:
>    return result;
>  }
>  
> -/* Compare two sequences using the index cache.  */
> -static int
> -do_compare (coll_seq *seq1, coll_seq *seq2, int position,
> -	    const USTRING_TYPE *weights)
> -{
> -  int seq1len = seq1->len;
> -  int seq2len = seq2->len;
> -  size_t val1 = seq1->val;
> -  size_t val2 = seq2->val;
> -  int32_t *idx1arr = seq1->idxarr;
> -  int32_t *idx2arr = seq2->idxarr;
> -  int idx1now = seq1->idxnow;
> -  int idx2now = seq2->idxnow;
> -  int result = 0;
> -
> -  /* Test for position if necessary.  */
> -  if (position && val1 != val2)
> -    {
> -      result = val1 > val2 ? 1 : -1;
> -      goto out;
> -    }
> -
> -  /* Compare the two sequences.  */
> -  do
> -    {
> -      if (weights[idx1arr[idx1now]] != weights[idx2arr[idx2now]])
> -	{
> -	  /* The sequences differ.  */
> -	  result = weights[idx1arr[idx1now]] - weights[idx2arr[idx2now]];
> -	  goto out;
> -	}
> -
> -      /* Increment the offsets.  */
> -      ++idx1arr[idx1now];
> -      ++idx2arr[idx2now];
> -
> -      --seq1len;
> -      --seq2len;
> -    }
> -  while (seq1len > 0 && seq2len > 0);
> -
> -  if (position && seq1len != seq2len)
> -    result = seq1len - seq2len;
> -
> -out:
> -  seq1->len = seq1len;
> -  seq2->len = seq2len;
> -  return result;
> -}
> -
>  int
> -STRCOLL (const STRING_TYPE *s1, const STRING_TYPE *s2, __locale_t l)
> +STRCOLL (const STRING_TYPE * s1, const STRING_TYPE * s2, __locale_t l)

Incorrect whitespace change.

>  {
>    struct __locale_data *current = l->__locales[LC_COLLATE];
> -  uint_fast32_t nrules = current->values[_NL_ITEM_INDEX (_NL_COLLATE_NRULES)].word;
> +  uint_fast32_t nrules =
> +    current->values[_NL_ITEM_INDEX (_NL_COLLATE_NRULES)].word;

Correct, but should go as a separate change.

>    /* We don't assign the following values right away since it might be
>       unnecessary in case there are no rules.  */
>    const unsigned char *rulesets;
> @@ -483,79 +259,36 @@ STRCOLL (const STRING_TYPE *s1, const STRING_TYPE *s2, __locale_t l)
>    if (nrules == 0)
>      return STRCMP (s1, s2);
>  
> +  /* Catch empty strings.  */
> +  if (__glibc_unlikely (*s1 == '\0') || __glibc_unlikely (*s2 == '\0'))
> +    return (*s1 != '\0') - (*s2 != '\0');
> +
>    rulesets = (const unsigned char *)
>      current->values[_NL_ITEM_INDEX (_NL_COLLATE_RULESETS)].string;
>    table = (const int32_t *)
> -    current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_TABLE,SUFFIX))].string;
> -  weights = (const USTRING_TYPE *)
> -    current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_WEIGHT,SUFFIX))].string;
> -  extra = (const USTRING_TYPE *)
> -    current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_EXTRA,SUFFIX))].string;
> -  indirect = (const int32_t *)
> -    current->values[_NL_ITEM_INDEX (CONCAT(_NL_COLLATE_INDIRECT,SUFFIX))].string;
> +    current->values[_NL_ITEM_INDEX (CONCAT (_NL_COLLATE_TABLE, SUFFIX))].
> +    string;
> +  weights =
> +    (const USTRING_TYPE *) current->
> +    values[_NL_ITEM_INDEX (CONCAT (_NL_COLLATE_WEIGHT, SUFFIX))].string;
> +  extra =
> +    (const USTRING_TYPE *) current->
> +    values[_NL_ITEM_INDEX (CONCAT (_NL_COLLATE_EXTRA, SUFFIX))].string;
> +  indirect =
> +    (const int32_t *) current->
> +    values[_NL_ITEM_INDEX (CONCAT (_NL_COLLATE_INDIRECT, SUFFIX))].string;

Likewise.

>  
>    assert (((uintptr_t) table) % __alignof__ (table[0]) == 0);
>    assert (((uintptr_t) weights) % __alignof__ (weights[0]) == 0);
>    assert (((uintptr_t) extra) % __alignof__ (extra[0]) == 0);
>    assert (((uintptr_t) indirect) % __alignof__ (indirect[0]) == 0);
>  
> -  /* We need this a few times.  */
> -  size_t s1len = STRLEN (s1);
> -  size_t s2len = STRLEN (s2);
> -
> -  /* Catch empty strings.  */
> -  if (__glibc_unlikely (s1len == 0) || __glibc_unlikely (s2len == 0))
> -    return (s1len != 0) - (s2len != 0);
> -
> -  /* Perform the first pass over the string and while doing this find
> -     and store the weights for each character.  Since we want this to
> -     be as fast as possible we are using `alloca' to store the temporary
> -     values.  But since there is no limit on the length of the string
> -     we have to use `malloc' if the string is too long.  We should be
> -     very conservative here.
> -
> -     Please note that the localedef programs makes sure that `position'
> -     is not used at the first level.  */
> +  int result = 0, rule = 0;
>  
>    coll_seq seq1, seq2;
> -  bool use_malloc = false;
> -  int result = 0;
> -
>    memset (&seq1, 0, sizeof (seq1));
>    seq2 = seq1;
>  
> -  size_t size_max = SIZE_MAX / (sizeof (int32_t) + 1);
> -
> -  if (MIN (s1len, s2len) > size_max
> -      || MAX (s1len, s2len) > size_max - MIN (s1len, s2len))
> -    {
> -      /* If the strings are long enough to cause overflow in the size request,
> -         then skip the allocation and proceed with the non-cached routines.  */
> -    }
> -  else if (! __libc_use_alloca ((s1len + s2len) * (sizeof (int32_t) + 1)))
> -    {
> -      seq1.idxarr = (int32_t *) malloc ((s1len + s2len) * (sizeof (int32_t) + 1));
> -
> -      /* If we failed to allocate memory, we leave everything as NULL so that
> -	 we use the nocache version of traversal and comparison functions.  */
> -      if (seq1.idxarr != NULL)
> -	{
> -	  seq2.idxarr = &seq1.idxarr[s1len];
> -	  seq1.rulearr = (unsigned char *) &seq2.idxarr[s2len];
> -	  seq2.rulearr = &seq1.rulearr[s1len];
> -	  use_malloc = true;
> -	}
> -    }
> -  else
> -    {
> -      seq1.idxarr = (int32_t *) alloca (s1len * sizeof (int32_t));
> -      seq2.idxarr = (int32_t *) alloca (s2len * sizeof (int32_t));
> -      seq1.rulearr = (unsigned char *) alloca (s1len);
> -      seq2.rulearr = (unsigned char *) alloca (s2len);
> -    }
> -
> -  int rule = 0;
> -
>    /* Cache values in the first pass and if needed, use them in subsequent
>       passes.  */
>    for (int pass = 0; pass < nrules; ++pass)
> @@ -570,73 +303,54 @@ STRCOLL (const STRING_TYPE *s1, const STRING_TYPE *s2, __locale_t l)
>        seq2.backw = ~0ul;
>  
>        /* We need the elements of the strings as unsigned values since they
> -	 are used as indices.  */
> +         are used as indices.  */

Incorrect whitespace change.

>        seq1.us = (const USTRING_TYPE *) s1;
>        seq2.us = (const USTRING_TYPE *) s2;
>  
>        /* We assume that if a rule has defined `position' in one section
> -	 this is true for all of them.  */
> +         this is true for all of them.  */

Incorrect whitespace change.

> +      /* Please note that the localedef programs makes sure that `position'
> +         is not used at the first level.  */
> +

This comment block should be merged with the above block.

>        int position = rulesets[rule * nrules + pass] & sort_position;
>  
>        while (1)
>  	{
> -	  if (__glibc_unlikely (seq1.idxarr == NULL))
> -	    {
> -	      get_next_seq_nocache (&seq1, nrules, rulesets, weights, table,
> -				    extra, indirect, pass);
> -	      get_next_seq_nocache (&seq2, nrules, rulesets, weights, table,
> -				    extra, indirect, pass);
> -	    }
> -	  else if (pass == 0)
> -	    {
> -	      get_next_seq (&seq1, nrules, rulesets, weights, table, extra,
> -			    indirect);
> -	      get_next_seq (&seq2, nrules, rulesets, weights, table, extra,
> -			    indirect);
> -	    }
> -	  else
> -	    {
> -	      get_next_seq_cached (&seq1, nrules, pass, rulesets, weights);
> -	      get_next_seq_cached (&seq2, nrules, pass, rulesets, weights);
> -	    }
> -
> +	  get_next_seq (&seq1, nrules, rulesets, weights, table,
> +			extra, indirect, pass);
> +	  get_next_seq (&seq2, nrules, rulesets, weights, table,
> +			extra, indirect, pass);
>  	  /* See whether any or both strings are empty.  */
>  	  if (seq1.len == 0 || seq2.len == 0)
>  	    {
>  	      if (seq1.len == seq2.len)
> -		/* Both ended.  So far so good, both strings are equal
> -		   at this level.  */
> -		break;
> +		{
> +		  /* Both ended.  So far so good, both strings are equal
> +		     at this level. */
> +		  if (pass == 0 && STRCMP (s1, s2) == 0)
> +		    /* Shortcut to avoid looping through all levels
> +		       for totally equal strings. */
> +		    return result;
> +		  else
> +		    break;
> +		}
>  
>  	      /* This means one string is shorter than the other.  Find out
> -		 which one and return an appropriate value.  */
> -	      result = seq1.len == 0 ? -1 : 1;
> -	      goto free_and_return;
> +	         which one and return an appropriate value.  */
> +	      return seq1.len == 0 ? -1 : 1;
>  	    }

The comment line has a incorrect change.

>  
> -	  if (__glibc_unlikely (seq1.idxarr == NULL))
> -	    result = do_compare_nocache (&seq1, &seq2, position, weights);
> -	  else
> -	    result = do_compare (&seq1, &seq2, position, weights);
> +	  result = do_compare (&seq1, &seq2, position, weights);
>  	  if (result != 0)
> -	    goto free_and_return;
> +	    return result;
>  	}
> -
> -      if (__glibc_likely (seq1.rulearr != NULL))
> -	rule = seq1.rulearr[0];
> -      else
> -	rule = seq1.rule;
> +      rule = seq1.rule;
>      }
>  
> -  /* Free the memory if needed.  */
> - free_and_return:
> -  if (use_malloc)
> -    free (seq1.idxarr);
> -
>    return result;
>  }
> -libc_hidden_def (STRCOLL)
>  
> +libc_hidden_def (STRCOLL)

Unnecessary addition of newline.

>  #ifndef WIDE_CHAR_VERSION
> -weak_alias (__strcoll_l, strcoll_l)
> +  weak_alias (__strcoll_l, strcoll_l)
>  #endif

Unnecessary space addition.

I hope this helps.  You still haven't confirmed if you have signed the
copyright assignment.  Without that we cannot accept your patch.

Siddhesh
Carlos O'Donell Sept. 25, 2014, 7:46 p.m. UTC | #3
On 09/24/2014 06:02 AM, Siddhesh Poyarekar wrote:
> - Finally, I don't know if you have signed a copyright assignment with
>   the FSF for your changes.  Carlos seems to have mentioned that in
>   your previous email thread, but I don't know if you've followed
>   through on it since I am not an FSF maintainer.  Maybe one of the
>   FSF maintainers can confirm that.

Leonhard Holz <leonhard.holz@web.de> has a futures assignment on file
for glibc. Dated 2014-09-22.

Leonhard, thank you very much for completing all of the paperwork! :-)

Cheers,
Carlos.

Patch
diff mbox

diff --git a/benchtests/Makefile b/benchtests/Makefile
index fd3036d..e79ceee 100644
--- a/benchtests/Makefile
+++ b/benchtests/Makefile
@@ -34,7 +34,7 @@  string-bench := bcopy bzero memccpy memchr memcmp memcpy memmem memmove \
 		mempcpy memset rawmemchr stpcpy stpncpy strcasecmp strcasestr \
 		strcat strchr strchrnul strcmp strcpy strcspn strlen \
 		strncasecmp strncat strncmp strncpy strnlen strpbrk strrchr \
-		strspn strstr strcpy_chk stpcpy_chk memrchr strsep strtok
+		strspn strstr strcpy_chk stpcpy_chk memrchr strsep strtok strcoll
 string-bench-all := $(string-bench)
 
 stdlib-bench := strtod