* [Patch] [BZ 15884] strcoll: improve performance by removing the cache
@ 2014-09-24 8:37 Leonhard Holz
2014-09-24 10:02 ` Siddhesh Poyarekar
0 siblings, 1 reply; 13+ messages in thread
From: Leonhard Holz @ 2014-09-24 8:37 UTC (permalink / raw)
To: libc-alpha
[-- Attachment #1: Type: text/plain, Size: 2859 bytes --]
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
[-- Attachment #2: benchtests_Makefile.diff --]
[-- Type: text/plain, Size: 612 bytes --]
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
[-- Attachment #3: benchtests-strcoll.tar.bz2 --]
[-- Type: application/octet-stream, Size: 114882 bytes --]
[-- Attachment #4: localedata_Makefile.diff --]
[-- Type: text/plain, Size: 893 bytes --]
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)
[-- Attachment #5: string_strcoll_l.c.diff --]
[-- Type: text/plain, Size: 17607 bytes --]
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
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [Patch] [BZ 15884] strcoll: improve performance by removing the cache
2014-09-24 8:37 [Patch] [BZ 15884] strcoll: improve performance by removing the cache Leonhard Holz
@ 2014-09-24 10:02 ` Siddhesh Poyarekar
[not found] ` <54231DF1.1050305@web.de>
` (2 more replies)
0 siblings, 3 replies; 13+ messages in thread
From: Siddhesh Poyarekar @ 2014-09-24 10:02 UTC (permalink / raw)
To: Leonhard Holz; +Cc: libc-alpha
[-- Attachment #1: Type: text/plain, Size: 3209 bytes --]
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
[-- Attachment #2: Type: application/pgp-signature, Size: 473 bytes --]
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [Patch] [BZ 15884] strcoll: improve performance by removing the cache
[not found] ` <54231DF1.1050305@web.de>
@ 2014-09-25 4:43 ` Siddhesh Poyarekar
0 siblings, 0 replies; 13+ messages in thread
From: Siddhesh Poyarekar @ 2014-09-25 4:43 UTC (permalink / raw)
To: Leonhard Holz; +Cc: libc-alpha
[-- Attachment #1: Type: text/plain, Size: 22303 bytes --]
[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
[-- Attachment #2: Type: application/pgp-signature, Size: 473 bytes --]
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [Patch] [BZ 15884] strcoll: improve performance by removing the cache
2014-09-24 10:02 ` Siddhesh Poyarekar
[not found] ` <54231DF1.1050305@web.de>
@ 2014-09-25 19:46 ` Carlos O'Donell
2014-09-29 10:30 ` Leonhard Holz
2 siblings, 0 replies; 13+ messages in thread
From: Carlos O'Donell @ 2014-09-25 19:46 UTC (permalink / raw)
To: Siddhesh Poyarekar, Leonhard Holz; +Cc: libc-alpha
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.
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [Patch] [BZ 15884] strcoll: improve performance by removing the cache
2014-09-24 10:02 ` Siddhesh Poyarekar
[not found] ` <54231DF1.1050305@web.de>
2014-09-25 19:46 ` Carlos O'Donell
@ 2014-09-29 10:30 ` Leonhard Holz
2014-10-05 10:16 ` [Ping] " Leonhard Holz
2014-10-07 15:26 ` Siddhesh Poyarekar
2 siblings, 2 replies; 13+ messages in thread
From: Leonhard Holz @ 2014-09-29 10:30 UTC (permalink / raw)
To: libc-alpha
[-- Attachment #1: Type: text/plain, Size: 6801 bytes --]
Ok, according to Siddhesh remarks I splitted the patch in two, this
which removes the cache and a following one that introduces inline-ing.
Formating should now be better and I tried to minimize the changed lines.
2014-09-29 Leonhard Holz <leonhard.holz@web.de>
[BZ #15884]
* string/strcoll_l.c: Remove weight and rules cache.
* benchtests/bench-strcoll.c: Benchmark for strcoll().
* benchtests/Makefile: Likewise.
* benchtests/strcoll-inputs/glibc_files.txt: Benchmark data.
* benchtests/strcoll-inputs/lorem_ipsum_vietnamese.txt
* benchtests/strcoll-inputs/lorem_ipsum_latin.txt
* benchtests/strcoll-inputs/lorem_ipsum_arabic.txt
* benchtests/strcoll-inputs/lorem_ipsum_l33tspeak.txt
* benchtests/strcoll-inputs/lorem_ipsum_chinese.txt
* benchtests/strcoll-inputs/lorem_ipsum_czech.txt
* benchtests/strcoll-inputs/lorem_ipsum_old_english.txt
* benchtests/strcoll-inputs/lorem_ipsum_danish.txt
* benchtests/strcoll-inputs/lorem_ipsum_polish.txt
* benchtests/strcoll-inputs/lorem_ipsum_french.txt
* benchtests/strcoll-inputs/lorem_ipsum_portugese.txt
* benchtests/strcoll-inputs/lorem_ipsum_greek.txt
* benchtests/strcoll-inputs/lorem_ipsum_russian.txt
* benchtests/strcoll-inputs/lorem_ipsum_hebrew.txt
* benchtests/strcoll-inputs/lorem_ipsum_spain.txt
* benchtests/strcoll-inputs/lorem_ipsum_hindi.txt
* benchtests/strcoll-inputs/lorem_ipsum_swedish.txt
* benchtests/strcoll-inputs/lorem_ipsum_hungarian.txt
* benchtests/strcoll-inputs/lorem_ipsum_turkish.txt
* benchtests/strcoll-inputs/lorem_ipsum_icelandic.txt
* benchtests/strcoll-inputs/lorem_ipsum_italian.txt
* benchtests/strcoll-inputs/lorem_ipsum_yugoslavian.txt
* benchtests/strcoll-inputs/lorem_ipsum_japanese.txt
* localedata/Makefile: Generate locales needed for benchtests.
The numbers are:
glibc_files.txt en_US.UTF-8 -46.72%
lorem_ipsum_vietnamese.txt vi_VN.UTF-8 -36.60%
lorem_ipsum_latin.txt en_US.UTF-8 -45.83%
lorem_ipsum_arabic.txt ar_SA.UTF-8 -34.11%
lorem_ipsum_l33tspeak.txt en_US.UTF-8 -46.28%
lorem_ipsum_chinese.txt zh_CN.UTF-8 +30.95%
lorem_ipsum_czech.txt cs_CZ.UTF-8 -36.17%
lorem_ipsum_old_english.txt en_GB.UTF-8 -35.22%
lorem_ipsum_danish.txt da_DK.UTF-8 -39.22%
lorem_ipsum_polish.txt pl_PL.UTF-8 -42.62%
lorem_ipsum_french.txt fr_FR.UTF-8 -31.09%
lorem_ipsum_portugese.txt pt_PT.UTF-8 -30.27%
lorem_ipsum_greek.txt el_GR.UTF-8 -32.07%
lorem_ipsum_russian.txt ru_RU.UTF-8 -36.00%
lorem_ipsum_hebrew.txt iw_IL.UTF-8 -41.44%
lorem_ipsum_spain.txt es_ES.UTF-8 -35.64%
lorem_ipsum_hindi.txt hi_IN.UTF-8 -00.17%
lorem_ipsum_swedish.txt sv_SE.UTF-8 -38.85%
lorem_ipsum_hungarian.txt hu_HU.UTF-8 -21.82%
lorem_ipsum_turkish.txt tr_TR.UTF-8 -38.08%
lorem_ipsum_icelandic.txt is_IS.UTF-8 -43.40%
lorem_ipsum_italian.txt it_IT.UTF-8 -30.52%
lorem_ipsum_yugoslavian.txt sr_RS.UTF-8 -36.41%
lorem_ipsum_japanese.txt ja_JP.UTF-8 +18.00%
Chinese and japanese are a bit special as AFAIK in these languages every
character is a word and the benchmark is probably comparing sentences.
Also theses language complete much faster in absolute numbers, about 1e6
vs. 3e6 (new) / 5e6 (old) for alphabetic languages.
Best,
Leonhard
Am 24.09.2014 12:02, schrieb Siddhesh Poyarekar:
> 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
>
[-- Attachment #2: bench-strcoll.c --]
[-- Type: text/plain, Size: 6310 bytes --]
/* Measure strcoll implementation.
Copyright (C) 2014 Free Software Foundation, Inc.
This file is part of the GNU C Library.
The GNU C Library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.
The GNU C Library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public
License along with the GNU C Library; if not, see
<http://www.gnu.org/licenses/>. */
#define TEST_MAIN
#define TEST_NAME "strcoll"
#include <stdio.h>
#include <stdlib.h>
#include <locale.h>
#include "bench-timing.h"
// many thanks to http://generator.lorem-ipsum.info/
const char *li_files[] = {
"strcoll-inputs/lorem_ipsum_vietnamese.txt",
"strcoll-inputs/lorem_ipsum_latin.txt",
"strcoll-inputs/lorem_ipsum_arabic.txt",
"strcoll-inputs/lorem_ipsum_l33tspeak.txt",
"strcoll-inputs/lorem_ipsum_chinese.txt",
"strcoll-inputs/lorem_ipsum_czech.txt",
"strcoll-inputs/lorem_ipsum_old_english.txt",
"strcoll-inputs/lorem_ipsum_danish.txt",
"strcoll-inputs/lorem_ipsum_polish.txt",
"strcoll-inputs/lorem_ipsum_french.txt",
"strcoll-inputs/lorem_ipsum_portugese.txt",
"strcoll-inputs/lorem_ipsum_greek.txt",
"strcoll-inputs/lorem_ipsum_russian.txt",
"strcoll-inputs/lorem_ipsum_hebrew.txt",
"strcoll-inputs/lorem_ipsum_spain.txt",
"strcoll-inputs/lorem_ipsum_hindi.txt",
"strcoll-inputs/lorem_ipsum_swedish.txt",
"strcoll-inputs/lorem_ipsum_hungarian.txt",
"strcoll-inputs/lorem_ipsum_turkish.txt",
"strcoll-inputs/lorem_ipsum_icelandic.txt",
"strcoll-inputs/lorem_ipsum_italian.txt",
"strcoll-inputs/lorem_ipsum_yugoslavian.txt",
"strcoll-inputs/lorem_ipsum_japanese.txt"
};
const char *li_locales[] = {
"vi_VN.UTF-8",
"en_US.UTF-8",
"ar_SA.UTF-8",
"en_US.UTF-8",
"zh_CN.UTF-8",
"cs_CZ.UTF-8",
"en_GB.UTF-8",
"da_DK.UTF-8",
"pl_PL.UTF-8",
"fr_FR.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",
"tr_TR.UTF-8",
"is_IS.UTF-8",
"it_IT.UTF-8",
"sr_RS.UTF-8",
"ja_JP.UTF-8"
};
const char *filenames_file = "strcoll-inputs/glibc_files.txt";
#define LI_DELIMITER " \n\r\t.,?!"
#define FILENAMES_DELIMITER "\n\r"
char *
read_file (const char *filename)
{
char *buffer = NULL;
FILE *f = fopen (filename, "rb");
if (f)
{
fseek (f, 0, SEEK_END);
size_t length = ftell (f);
fseek (f, 0, SEEK_SET);
buffer = malloc (length + 1);
if (buffer)
{
fread (buffer, 1, length, f);
*(buffer + length) = '\0';
}
fclose (f);
}
return buffer;
}
size_t
count_words (const char *text, const char *delim)
{
size_t wordcount = 0;
char *tmp = strdup (text);
char *token = strtok (tmp, delim);
while (token != NULL)
{
if (*token != '\0')
wordcount++;
token = strtok (NULL, delim);
}
free (tmp);
return wordcount;
}
typedef struct
{
char *str;
size_t strlen;
size_t size;
char **words;
} word_list;
word_list
tokenize_string (const char *str, const char *delim)
{
word_list list;
list.strlen = strlen (str);
list.size = count_words (str, delim);
list.words = malloc (list.size * sizeof (char *));
size_t n = 0;
list.str = strdup (str);
char *word = strtok (list.str, delim);
while (word != NULL && n < list.size)
{
if (*word != '\0')
list.words[n++] = word;
word = strtok (NULL, delim);
}
return list;
}
word_list
copy_word_list (const word_list list)
{
size_t i;
word_list copy;
copy.strlen = list.strlen;
copy.str = malloc (list.strlen + 1);
memcpy (copy.str, list.str, list.strlen + 1);
copy.size = list.size;
copy.words = malloc (list.size * sizeof (char *));
for (i = 0; i < list.size; i++)
copy.words[i] = list.words[i] - list.str + copy.str;
return copy;
}
int
compare_words (const void *a, const void *b)
{
const char *s1 = *(char **) a;
const char *s2 = *(char **) b;
return strcoll (s1, s2);
}
word_list
sort_word_list (const word_list list)
{
word_list sorted = copy_word_list (list);
qsort (sorted.words, sorted.size, sizeof (char *), compare_words);
return sorted;
}
void
print_word_list (word_list list)
{
size_t i;
for (i = 0; i < list.size; i++)
printf ("%s\n", list.words[i]);
}
void
free_word_list (word_list list)
{
free (list.words);
free (list.str);
}
#undef INNER_LOOP_ITERS
#define INNER_LOOP_ITERS 16
void
test_file (const char *filename, const char *delim, const char *locale)
{
setlocale (LC_ALL, locale);
timing_t start, stop, cur;
size_t i, iters = INNER_LOOP_ITERS;
printf ("%-50s %-10s", filename, setlocale (LC_ALL, NULL));
char *text = read_file (filename);
word_list list = tokenize_string (text, delim);
word_list *tests = malloc (INNER_LOOP_ITERS * sizeof (word_list));
for (i = 0; i < INNER_LOOP_ITERS; i++)
tests[i] = copy_word_list (list);
TIMING_NOW (start);
for (i = 0; i < INNER_LOOP_ITERS; i++)
qsort (tests[i].words, tests[i].size, sizeof (char *), compare_words);
TIMING_NOW (stop);
setlocale (LC_ALL, "en_US.UTF-8");
TIMING_DIFF (cur, start, stop);
TIMING_PRINT_MEAN ((double) cur, (double) iters);
putchar ('\n');
for (i = 0; i < INNER_LOOP_ITERS; i++)
free_word_list (tests[i]);
free (tests);
free_word_list (list);
free (text);
}
int
do_bench (void)
{
if (setlocale (LC_ALL, "en_US.UTF-8") == NULL)
{
printf ("Failed to set default locale.");
return 1;
}
timing_t res __attribute__ ((unused));
TIMING_INIT (res);
test_file (filenames_file, FILENAMES_DELIMITER, "en_US.UTF-8");
size_t i;
for (i = 0; i < (sizeof (li_files) / sizeof (li_files[0])); i++)
test_file (li_files[i], LI_DELIMITER, li_locales[i]);
return 0;
}
#define TEST_FUNCTION do_bench ()
/* On slower platforms this test needs more than the default 2 seconds. */
#define TIMEOUT 10
#include "../test-skeleton.c"
[-- Attachment #3: benchtests_Makefile.diff --]
[-- Type: text/plain, Size: 612 bytes --]
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
[-- Attachment #4: localedata_Makefile.diff --]
[-- Type: text/plain, Size: 884 bytes --]
diff --git a/localedata/Makefile b/localedata/Makefile
index b6235f2..cb24974 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)
[-- Attachment #5: strcoll-inputs.tar.bz2 --]
[-- Type: application/octet-stream, Size: 112406 bytes --]
[-- Attachment #6: string_strcoll_l.c.diff --]
[-- Type: text/plain, Size: 12533 bytes --]
diff --git a/string/strcoll_l.c b/string/strcoll_l.c
index d4f42a3..dbda23c 100644
--- a/string/strcoll_l.c
+++ b/string/strcoll_l.c
@@ -22,7 +22,6 @@
#include <locale.h>
#include <stddef.h>
#include <stdint.h>
-#include <stdlib.h>
#include <string.h>
#include <sys/param.h>
@@ -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,179 +62,9 @@ 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)
@@ -366,10 +193,9 @@ get_next_seq_nocache (coll_seq *seq, int nrules, const unsigned char *rulesets,
seq->idx = idx;
}
-/* Compare two sequences. This version does not use the index and rules
- cache. */
+/* Compare two sequences. */
static int
-do_compare_nocache (coll_seq *seq1, coll_seq *seq2, int position,
+do_compare (coll_seq *seq1, coll_seq *seq2, int position,
const USTRING_TYPE *weights)
{
int seq1len = seq1->len;
@@ -417,56 +243,6 @@ 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)
{
@@ -483,6 +259,10 @@ 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 *)
@@ -499,65 +279,12 @@ STRCOLL (const STRING_TYPE *s1, const STRING_TYPE *s2, __locale_t l)
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)
{
seq1.idxcnt = 0;
@@ -575,64 +302,44 @@ STRCOLL (const STRING_TYPE *s1, const STRING_TYPE *s2, __locale_t l)
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,
+ get_next_seq (&seq1, nrules, rulesets, weights, table,
extra, indirect, pass);
- get_next_seq_nocache (&seq2, nrules, rulesets, weights, table,
+ get_next_seq (&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);
- }
-
/* 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. 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;
+ 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)
^ permalink raw reply [flat|nested] 13+ messages in thread
* [Ping] [Patch] [BZ 15884] strcoll: improve performance by removing the cache
2014-09-29 10:30 ` Leonhard Holz
@ 2014-10-05 10:16 ` Leonhard Holz
2014-10-07 15:26 ` Siddhesh Poyarekar
1 sibling, 0 replies; 13+ messages in thread
From: Leonhard Holz @ 2014-10-05 10:16 UTC (permalink / raw)
To: libc-alpha
Hi! Please review this patch:
https://sourceware.org/ml/libc-alpha/2014-09/msg00643.html
Best,
Leonhard
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [Patch] [BZ 15884] strcoll: improve performance by removing the cache
2014-09-29 10:30 ` Leonhard Holz
2014-10-05 10:16 ` [Ping] " Leonhard Holz
@ 2014-10-07 15:26 ` Siddhesh Poyarekar
2014-10-08 8:32 ` Leonhard Holz
1 sibling, 1 reply; 13+ messages in thread
From: Siddhesh Poyarekar @ 2014-10-07 15:26 UTC (permalink / raw)
To: Leonhard Holz; +Cc: libc-alpha
[-- Attachment #1: Type: text/plain, Size: 28781 bytes --]
On Mon, Sep 29, 2014 at 12:30:18PM +0200, Leonhard Holz wrote:
> Ok, according to Siddhesh remarks I splitted the patch in two, this which
> removes the cache and a following one that introduces inline-ing. Formating
> should now be better and I tried to minimize the changed lines.
Thanks, this version is better in terms of formatting. More detailed
review below.
>
> 2014-09-29 Leonhard Holz <leonhard.holz@web.de>
>
> [BZ #15884]
> * string/strcoll_l.c: Remove weight and rules cache.
> * benchtests/bench-strcoll.c: Benchmark for strcoll().
> * benchtests/Makefile: Likewise.
> * benchtests/strcoll-inputs/glibc_files.txt: Benchmark data.
> * benchtests/strcoll-inputs/lorem_ipsum_vietnamese.txt
> * benchtests/strcoll-inputs/lorem_ipsum_latin.txt
> * benchtests/strcoll-inputs/lorem_ipsum_arabic.txt
> * benchtests/strcoll-inputs/lorem_ipsum_l33tspeak.txt
> * benchtests/strcoll-inputs/lorem_ipsum_chinese.txt
> * benchtests/strcoll-inputs/lorem_ipsum_czech.txt
> * benchtests/strcoll-inputs/lorem_ipsum_old_english.txt
> * benchtests/strcoll-inputs/lorem_ipsum_danish.txt
> * benchtests/strcoll-inputs/lorem_ipsum_polish.txt
> * benchtests/strcoll-inputs/lorem_ipsum_french.txt
> * benchtests/strcoll-inputs/lorem_ipsum_portugese.txt
> * benchtests/strcoll-inputs/lorem_ipsum_greek.txt
> * benchtests/strcoll-inputs/lorem_ipsum_russian.txt
> * benchtests/strcoll-inputs/lorem_ipsum_hebrew.txt
> * benchtests/strcoll-inputs/lorem_ipsum_spain.txt
> * benchtests/strcoll-inputs/lorem_ipsum_hindi.txt
> * benchtests/strcoll-inputs/lorem_ipsum_swedish.txt
> * benchtests/strcoll-inputs/lorem_ipsum_hungarian.txt
> * benchtests/strcoll-inputs/lorem_ipsum_turkish.txt
> * benchtests/strcoll-inputs/lorem_ipsum_icelandic.txt
> * benchtests/strcoll-inputs/lorem_ipsum_italian.txt
> * benchtests/strcoll-inputs/lorem_ipsum_yugoslavian.txt
> * benchtests/strcoll-inputs/lorem_ipsum_japanese.txt
> * localedata/Makefile: Generate locales needed for benchtests.
The ChangeLog is wrong. You need to mention the function name where
you've made the change and for the new files, it is sufficient to just
say "New file".
* string/strcoll_l.c (STRCOLL): Remove weight and rules cache.
* benchtests/bench-strcoll.c: New benchmark.
* benchtests/Makefile (bench-string): Use it.
* benchtests/strcoll-inputs/lorem_ipsum_vietnamese.txt: New file.
... followed by 'Likewise' for the rest of the benchmark data
files.
>
> The numbers are:
>
> glibc_files.txt en_US.UTF-8 -46.72%
> lorem_ipsum_vietnamese.txt vi_VN.UTF-8 -36.60%
> lorem_ipsum_latin.txt en_US.UTF-8 -45.83%
> lorem_ipsum_arabic.txt ar_SA.UTF-8 -34.11%
> lorem_ipsum_l33tspeak.txt en_US.UTF-8 -46.28%
> lorem_ipsum_chinese.txt zh_CN.UTF-8 +30.95%
> lorem_ipsum_czech.txt cs_CZ.UTF-8 -36.17%
> lorem_ipsum_old_english.txt en_GB.UTF-8 -35.22%
> lorem_ipsum_danish.txt da_DK.UTF-8 -39.22%
> lorem_ipsum_polish.txt pl_PL.UTF-8 -42.62%
> lorem_ipsum_french.txt fr_FR.UTF-8 -31.09%
> lorem_ipsum_portugese.txt pt_PT.UTF-8 -30.27%
> lorem_ipsum_greek.txt el_GR.UTF-8 -32.07%
> lorem_ipsum_russian.txt ru_RU.UTF-8 -36.00%
> lorem_ipsum_hebrew.txt iw_IL.UTF-8 -41.44%
> lorem_ipsum_spain.txt es_ES.UTF-8 -35.64%
> lorem_ipsum_hindi.txt hi_IN.UTF-8 -00.17%
> lorem_ipsum_swedish.txt sv_SE.UTF-8 -38.85%
> lorem_ipsum_hungarian.txt hu_HU.UTF-8 -21.82%
> lorem_ipsum_turkish.txt tr_TR.UTF-8 -38.08%
> lorem_ipsum_icelandic.txt is_IS.UTF-8 -43.40%
> lorem_ipsum_italian.txt it_IT.UTF-8 -30.52%
> lorem_ipsum_yugoslavian.txt sr_RS.UTF-8 -36.41%
> lorem_ipsum_japanese.txt ja_JP.UTF-8 +18.00%
>
> Chinese and japanese are a bit special as AFAIK in these languages every
> character is a word and the benchmark is probably comparing sentences. Also
> theses language complete much faster in absolute numbers, about 1e6 vs. 3e6
> (new) / 5e6 (old) for alphabetic languages.
Please include at least one verbatim output from the test run for this
test.
> /* Measure strcoll implementation.
> Copyright (C) 2014 Free Software Foundation, Inc.
> This file is part of the GNU C Library.
>
> The GNU C Library is free software; you can redistribute it and/or
> modify it under the terms of the GNU Lesser General Public
> License as published by the Free Software Foundation; either
> version 2.1 of the License, or (at your option) any later version.
>
> The GNU C Library is distributed in the hope that it will be useful,
> but WITHOUT ANY WARRANTY; without even the implied warranty of
> MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
> Lesser General Public License for more details.
>
> You should have received a copy of the GNU Lesser General Public
> License along with the GNU C Library; if not, see
> <http://www.gnu.org/licenses/>. */
>
> #define TEST_MAIN
> #define TEST_NAME "strcoll"
>
> #include <stdio.h>
> #include <stdlib.h>
> #include <locale.h>
> #include "bench-timing.h"
>
> // many thanks to http://generator.lorem-ipsum.info/
Use /* ... */ for comments.
> const char *li_files[] = {
> "strcoll-inputs/lorem_ipsum_vietnamese.txt",
> "strcoll-inputs/lorem_ipsum_latin.txt",
> "strcoll-inputs/lorem_ipsum_arabic.txt",
> "strcoll-inputs/lorem_ipsum_l33tspeak.txt",
> "strcoll-inputs/lorem_ipsum_chinese.txt",
> "strcoll-inputs/lorem_ipsum_czech.txt",
> "strcoll-inputs/lorem_ipsum_old_english.txt",
> "strcoll-inputs/lorem_ipsum_danish.txt",
> "strcoll-inputs/lorem_ipsum_polish.txt",
> "strcoll-inputs/lorem_ipsum_french.txt",
> "strcoll-inputs/lorem_ipsum_portugese.txt",
> "strcoll-inputs/lorem_ipsum_greek.txt",
> "strcoll-inputs/lorem_ipsum_russian.txt",
> "strcoll-inputs/lorem_ipsum_hebrew.txt",
> "strcoll-inputs/lorem_ipsum_spain.txt",
> "strcoll-inputs/lorem_ipsum_hindi.txt",
> "strcoll-inputs/lorem_ipsum_swedish.txt",
> "strcoll-inputs/lorem_ipsum_hungarian.txt",
> "strcoll-inputs/lorem_ipsum_turkish.txt",
> "strcoll-inputs/lorem_ipsum_icelandic.txt",
> "strcoll-inputs/lorem_ipsum_italian.txt",
> "strcoll-inputs/lorem_ipsum_yugoslavian.txt",
> "strcoll-inputs/lorem_ipsum_japanese.txt"
> };
>
> const char *li_locales[] = {
> "vi_VN.UTF-8",
> "en_US.UTF-8",
> "ar_SA.UTF-8",
> "en_US.UTF-8",
> "zh_CN.UTF-8",
> "cs_CZ.UTF-8",
> "en_GB.UTF-8",
> "da_DK.UTF-8",
> "pl_PL.UTF-8",
> "fr_FR.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",
> "tr_TR.UTF-8",
> "is_IS.UTF-8",
> "it_IT.UTF-8",
> "sr_RS.UTF-8",
> "ja_JP.UTF-8"
> };
It would be better if this was just one array. You could achieve this
by naming your tests as lorem_ipsum_is_IS, lorem_ipsum_ja_JP, etc. and
then just have an array of locales:
const char *locales[] = {
"vi_VN",
"en_US",
"ar_SA",
...
};
and then add the UTF-8 suffix to the locale name and file name
prefixes and suffixes in the program below.
>
> const char *filenames_file = "strcoll-inputs/glibc_files.txt";
This looks like just a listing of the input files, so just generate
this file automatically as a temporary file (see add_temp_file
function in test-skeleton.c and sample usages in the test sources).
>
> #define LI_DELIMITER " \n\r\t.,?!"
> #define FILENAMES_DELIMITER "\n\r"
Why \r ?
>
> char *
> read_file (const char *filename)
> {
> char *buffer = NULL;
> FILE *f = fopen (filename, "rb");
>
> if (f)
> {
> fseek (f, 0, SEEK_END);
> size_t length = ftell (f);
> fseek (f, 0, SEEK_SET);
> buffer = malloc (length + 1);
> if (buffer)
> {
> fread (buffer, 1, length, f);
> *(buffer + length) = '\0';
> }
> fclose (f);
> }
>
> return buffer;
> }
Use 'open' to open the file, 'fstat' to get the size to allocate your
buffer and then 'read' to read in the file into your buffer.
>
> size_t
> count_words (const char *text, const char *delim)
> {
> size_t wordcount = 0;
> char *tmp = strdup (text);
>
> char *token = strtok (tmp, delim);
> while (token != NULL)
> {
> if (*token != '\0')
> wordcount++;
> token = strtok (NULL, delim);
> }
>
> free (tmp);
> return wordcount;
> }
>
> typedef struct
> {
> char *str;
> size_t strlen;
> size_t size;
> char **words;
> } word_list;
>
> word_list
Pass and return pointers instead of the whole struct.
> tokenize_string (const char *str, const char *delim)
> {
> word_list list;
> list.strlen = strlen (str);
> list.size = count_words (str, delim);
> list.words = malloc (list.size * sizeof (char *));
>
> size_t n = 0;
> list.str = strdup (str);
> char *word = strtok (list.str, delim);
> while (word != NULL && n < list.size)
> {
> if (*word != '\0')
> list.words[n++] = word;
> word = strtok (NULL, delim);
> }
>
> return list;
> }
>
> word_list
Likewise.
> copy_word_list (const word_list list)
Likewise.
> {
> size_t i;
> word_list copy;
>
> copy.strlen = list.strlen;
> copy.str = malloc (list.strlen + 1);
> memcpy (copy.str, list.str, list.strlen + 1);
>
> copy.size = list.size;
> copy.words = malloc (list.size * sizeof (char *));
>
> for (i = 0; i < list.size; i++)
> copy.words[i] = list.words[i] - list.str + copy.str;
>
> return copy;
> }
>
> int
> compare_words (const void *a, const void *b)
> {
> const char *s1 = *(char **) a;
> const char *s2 = *(char **) b;
> return strcoll (s1, s2);
> }
>
> word_list
> sort_word_list (const word_list list)
Pass pointers, not entire structures.
> {
> word_list sorted = copy_word_list (list);
> qsort (sorted.words, sorted.size, sizeof (char *), compare_words);
> return sorted;
> }
>
> void
> print_word_list (word_list list)
Likewise.
> {
> size_t i;
>
> for (i = 0; i < list.size; i++)
> printf ("%s\n", list.words[i]);
> }
>
> void
> free_word_list (word_list list)
> {
> free (list.words);
> free (list.str);
> }
>
> #undef INNER_LOOP_ITERS
> #define INNER_LOOP_ITERS 16
>
> void
> test_file (const char *filename, const char *delim, const char *locale)
> {
> setlocale (LC_ALL, locale);
Test return value of setlocale.
> timing_t start, stop, cur;
> size_t i, iters = INNER_LOOP_ITERS;
>
> printf ("%-50s %-10s", filename, setlocale (LC_ALL, NULL));
>
It is sufficient to print the locale value passed to this function
here once you ensure that the setlocale return value is successful.
> char *text = read_file (filename);
> word_list list = tokenize_string (text, delim);
>
> word_list *tests = malloc (INNER_LOOP_ITERS * sizeof (word_list));
> for (i = 0; i < INNER_LOOP_ITERS; i++)
> tests[i] = copy_word_list (list);
This will obviously have to be adjusted (and hence made cleaner) once
copy_word_list and all other functions above pass pointers to
word_list.
>
> TIMING_NOW (start);
> for (i = 0; i < INNER_LOOP_ITERS; i++)
> qsort (tests[i].words, tests[i].size, sizeof (char *), compare_words);
> TIMING_NOW (stop);
>
> setlocale (LC_ALL, "en_US.UTF-8");
>
> TIMING_DIFF (cur, start, stop);
> TIMING_PRINT_MEAN ((double) cur, (double) iters);
> putchar ('\n');
>
> for (i = 0; i < INNER_LOOP_ITERS; i++)
> free_word_list (tests[i]);
> free (tests);
>
> free_word_list (list);
> free (text);
> }
I'd like the printed output to be in JSON format, but we can do the
first cut in plain text if you're willing to add an extra improvement
later to make the output in JSON.
>
>
> int
> do_bench (void)
> {
> if (setlocale (LC_ALL, "en_US.UTF-8") == NULL)
> {
> printf ("Failed to set default locale.");
> return 1;
> }
Why do you need this?
>
> timing_t res __attribute__ ((unused));
> TIMING_INIT (res);
>
> test_file (filenames_file, FILENAMES_DELIMITER, "en_US.UTF-8");
>
> size_t i;
> for (i = 0; i < (sizeof (li_files) / sizeof (li_files[0])); i++)
> test_file (li_files[i], LI_DELIMITER, li_locales[i]);
>
> return 0;
> }
>
> #define TEST_FUNCTION do_bench ()
>
> /* On slower platforms this test needs more than the default 2 seconds. */
> #define TIMEOUT 10
>
> #include "../test-skeleton.c"
> 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
> diff --git a/localedata/Makefile b/localedata/Makefile
> index b6235f2..cb24974 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..dbda23c 100644
> --- a/string/strcoll_l.c
> +++ b/string/strcoll_l.c
> @@ -22,7 +22,6 @@
> #include <locale.h>
> #include <stddef.h>
> #include <stdint.h>
> -#include <stdlib.h>
> #include <string.h>
> #include <sys/param.h>
>
> @@ -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,179 +62,9 @@ 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)
> @@ -366,10 +193,9 @@ get_next_seq_nocache (coll_seq *seq, int nrules, const unsigned char *rulesets,
> seq->idx = idx;
> }
>
> -/* Compare two sequences. This version does not use the index and rules
> - cache. */
> +/* Compare two sequences. */
> static int
> -do_compare_nocache (coll_seq *seq1, coll_seq *seq2, int position,
> +do_compare (coll_seq *seq1, coll_seq *seq2, int position,
> const USTRING_TYPE *weights)
> {
> int seq1len = seq1->len;
> @@ -417,56 +243,6 @@ 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)
> {
> @@ -483,6 +259,10 @@ 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 *)
> @@ -499,65 +279,12 @@ STRCOLL (const STRING_TYPE *s1, const STRING_TYPE *s2, __locale_t l)
> 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)
> {
> seq1.idxcnt = 0;
> @@ -575,64 +302,44 @@ STRCOLL (const STRING_TYPE *s1, const STRING_TYPE *s2, __locale_t l)
> 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,
> + get_next_seq (&seq1, nrules, rulesets, weights, table,
> extra, indirect, pass);
> - get_next_seq_nocache (&seq2, nrules, rulesets, weights, table,
> + get_next_seq (&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);
> - }
> -
> /* 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. Both strings are equal at this level. */
> + if (pass == 0 && STRCMP(s1, s2) == 0)
Space between STRCMP and (.
> + /* Shortcut to avoid looping through all levels
> + for totally equal strings. */
Two spaces after period. I'd suggest merging this comment with the
above comment to make a single one, something like:
Both strings ended and are equal at this level. Do a byte-level
comparison to ensure that we don't waste time going through
multiple passes for totally equal strings before proceeding to
subsequent passes.
> + 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;
> + 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)
Thanks,
Siddhesh
[-- Attachment #2: Type: application/pgp-signature, Size: 473 bytes --]
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [Patch] [BZ 15884] strcoll: improve performance by removing the cache
2014-10-07 15:26 ` Siddhesh Poyarekar
@ 2014-10-08 8:32 ` Leonhard Holz
2014-10-08 9:09 ` Siddhesh Poyarekar
0 siblings, 1 reply; 13+ messages in thread
From: Leonhard Holz @ 2014-10-08 8:32 UTC (permalink / raw)
To: libc-alpha
Dear Siddhesh,
before I start changing the patch some notes / questions:
>
>>
>> #define LI_DELIMITER " \n\r\t.,?!"
>> #define FILENAMES_DELIMITER "\n\r"
>
> Why \r ?
>
Defensive programming... the input files are all generated and might be
regenerated by some else in the future.
>> typedef struct
>> {
>> char *str;
>> size_t strlen;
>> size_t size;
>> char **words;
>> } word_list;
>>
>> word_list
>
> Pass and return pointers instead of the whole struct.
Is this really an issue? It's only four times the size of a pointer, the
benchmark is not affected by it and the malloc's will not make the
code nicer.
>> void
>> test_file (const char *filename, const char *delim, const char *locale)
>> {
>> setlocale (LC_ALL, locale);
>
> Test return value of setlocale.
>
>> timing_t start, stop, cur;
>> size_t i, iters = INNER_LOOP_ITERS;
>>
>> printf ("%-50s %-10s", filename, setlocale (LC_ALL, NULL));
>>
>
> It is sufficient to print the locale value passed to this function
> here once you ensure that the setlocale return value is successful.
>
The idea is to set a fallback locale at the beginning which is used if
one of the benchmarked locales are not available. This is why the used
locale is also printed in the results. So you want it to skip the run if
the needed locale is not available?
>> char *text = read_file (filename);
>> word_list list = tokenize_string (text, delim);
>>
>> word_list *tests = malloc (INNER_LOOP_ITERS * sizeof (word_list));
>> for (i = 0; i < INNER_LOOP_ITERS; i++)
>> tests[i] = copy_word_list (list);
>
> This will obviously have to be adjusted (and hence made cleaner) once
> copy_word_list and all other functions above pass pointers to
> word_list.
Maybe I'll see when I change it but maybe you can give me a hint what
you mean with "cleaner".
>
>>
>> TIMING_NOW (start);
>> for (i = 0; i < INNER_LOOP_ITERS; i++)
>> qsort (tests[i].words, tests[i].size, sizeof (char *), compare_words);
>> TIMING_NOW (stop);
>>
>> setlocale (LC_ALL, "en_US.UTF-8");
>>
>> TIMING_DIFF (cur, start, stop);
>> TIMING_PRINT_MEAN ((double) cur, (double) iters);
>> putchar ('\n');
>>
>> for (i = 0; i < INNER_LOOP_ITERS; i++)
>> free_word_list (tests[i]);
>> free (tests);
>>
>> free_word_list (list);
>> free (text);
>> }
>
> I'd like the printed output to be in JSON format, but we can do the
> first cut in plain text if you're willing to add an extra improvement
> later to make the output in JSON.
>
Is there some code that can be reused for output in JSON format?
>>
>>
>> int
>> do_bench (void)
>> {
>> if (setlocale (LC_ALL, "en_US.UTF-8") == NULL)
>> {
>> printf ("Failed to set default locale.");
>> return 1;
>> }
>
> Why do you need this?
See above.
Thank you for your time,
Leonhard
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [Patch] [BZ 15884] strcoll: improve performance by removing the cache
2014-10-08 8:32 ` Leonhard Holz
@ 2014-10-08 9:09 ` Siddhesh Poyarekar
2014-10-13 12:20 ` Leonhard Holz
0 siblings, 1 reply; 13+ messages in thread
From: Siddhesh Poyarekar @ 2014-10-08 9:09 UTC (permalink / raw)
To: Leonhard Holz; +Cc: libc-alpha
[-- Attachment #1: Type: text/plain, Size: 2599 bytes --]
On Wed, Oct 08, 2014 at 10:32:40AM +0200, Leonhard Holz wrote:
> Defensive programming... the input files are all generated and might be
> regenerated by some else in the future.
Fair enough.
> Is this really an issue? It's only four times the size of a pointer, the
> benchmark is not affected by it and the malloc's will not make the
> code nicer.
It does make the code better in addition to the fact that it is more
familiar coding style; I've elaborated on the 'how' below. In general
the number of copies of the struct in all those functions is just
wasteful. It may not affect the benchmark, but that's no reason to
keep it sloppy.
> The idea is to set a fallback locale at the beginning which is used if one
> of the benchmarked locales are not available. This is why the used locale is
> also printed in the results. So you want it to skip the run if the needed
> locale is not available?
The test should fail with an error, because the locale should always
be available in this test - we're generating them. In fact, I think
we might need to wire things up so that locales are generated during
`make bench`. I don't think that's happening currently because
they're currently generated as part of `make check`.
> >> char *text = read_file (filename);
> >> word_list list = tokenize_string (text, delim);
> >>
> >> word_list *tests = malloc (INNER_LOOP_ITERS * sizeof (word_list));
> >> for (i = 0; i < INNER_LOOP_ITERS; i++)
> >> tests[i] = copy_word_list (list);
> >
> >This will obviously have to be adjusted (and hence made cleaner) once
> >copy_word_list and all other functions above pass pointers to
> >word_list.
>
> Maybe I'll see when I change it but maybe you can give me a hint what you
> mean with "cleaner".
Your word_list API (for the lack of a better term) becomes cleaner:
1. tokenize_string should allocate and returns a word_list. You can
rename it to new_word_list to make it more consistent
2. copy_word_list allocates (and copies) and returns a word_list
3. free_word_list frees the word_list
Everything else just uses the reference and can hence modify the list
in place. sort_word_list for example would no longer need to create a
copy of the passed in object. Oh, and it looks like sort_word_list is
unused, so you can just remove it.
> Is there some code that can be reused for output in JSON format?
See bench-skeleton.c for an example. Or maybe the malloc benchmark
patch that Will Newton posted recently[1].
Siddhesh
[1] http://patchwork.sourceware.org/patch/3092/
[-- Attachment #2: Type: application/pgp-signature, Size: 473 bytes --]
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [Patch] [BZ 15884] strcoll: improve performance by removing the cache
2014-10-08 9:09 ` Siddhesh Poyarekar
@ 2014-10-13 12:20 ` Leonhard Holz
2014-10-14 8:43 ` Siddhesh Poyarekar
0 siblings, 1 reply; 13+ messages in thread
From: Leonhard Holz @ 2014-10-13 12:20 UTC (permalink / raw)
To: Siddhesh Poyarekar; +Cc: libc-alpha
[-- Attachment #1: Type: text/plain, Size: 2777 bytes --]
Hi Siddhesh,
please have a look at the attached JSON output of the strcoll benchmark.
Best,
Leonhard
Am 08.10.2014 11:09, schrieb Siddhesh Poyarekar:
> On Wed, Oct 08, 2014 at 10:32:40AM +0200, Leonhard Holz wrote:
>> Defensive programming... the input files are all generated and might be
>> regenerated by some else in the future.
>
> Fair enough.
>
>> Is this really an issue? It's only four times the size of a pointer, the
>> benchmark is not affected by it and the malloc's will not make the
>> code nicer.
>
> It does make the code better in addition to the fact that it is more
> familiar coding style; I've elaborated on the 'how' below. In general
> the number of copies of the struct in all those functions is just
> wasteful. It may not affect the benchmark, but that's no reason to
> keep it sloppy.
>
>> The idea is to set a fallback locale at the beginning which is used if one
>> of the benchmarked locales are not available. This is why the used locale is
>> also printed in the results. So you want it to skip the run if the needed
>> locale is not available?
>
> The test should fail with an error, because the locale should always
> be available in this test - we're generating them. In fact, I think
> we might need to wire things up so that locales are generated during
> `make bench`. I don't think that's happening currently because
> they're currently generated as part of `make check`.
>
>>>> char *text = read_file (filename);
>>>> word_list list = tokenize_string (text, delim);
>>>>
>>>> word_list *tests = malloc (INNER_LOOP_ITERS * sizeof (word_list));
>>>> for (i = 0; i < INNER_LOOP_ITERS; i++)
>>>> tests[i] = copy_word_list (list);
>>>
>>> This will obviously have to be adjusted (and hence made cleaner) once
>>> copy_word_list and all other functions above pass pointers to
>>> word_list.
>>
>> Maybe I'll see when I change it but maybe you can give me a hint what you
>> mean with "cleaner".
>
> Your word_list API (for the lack of a better term) becomes cleaner:
>
> 1. tokenize_string should allocate and returns a word_list. You can
> rename it to new_word_list to make it more consistent
> 2. copy_word_list allocates (and copies) and returns a word_list
> 3. free_word_list frees the word_list
>
> Everything else just uses the reference and can hence modify the list
> in place. sort_word_list for example would no longer need to create a
> copy of the passed in object. Oh, and it looks like sort_word_list is
> unused, so you can just remove it.
>
>> Is there some code that can be reused for output in JSON format?
>
> See bench-skeleton.c for an example. Or maybe the malloc benchmark
> patch that Will Newton posted recently[1].
>
> Siddhesh
>
> [1] http://patchwork.sourceware.org/patch/3092/
>
[-- Attachment #2: bench-strcoll.out --]
[-- Type: text/plain, Size: 4236 bytes --]
"strcoll": {
"file list": {
"directory": "..",
"file_count": 39086,
"locale": "en_US.UTF-8",
"duration": 4.72532e+09,
"iterations": 16,
"mean": 2.95333e+08
},
"word list": {
"file": "strcoll-inputs/lorem_ipsum_vi_VN",
"locale": "vi_VN.UTF-8",
"duration": 4,86973e+07,
"iterations": 16,
"mean": 3,04358e+06
},
"word list": {
"file": "strcoll-inputs/lorem_ipsum_en_US",
"locale": "en_US.UTF-8",
"duration": 4.39686e+07,
"iterations": 16,
"mean": 2.74804e+06
},
"word list": {
"file": "strcoll-inputs/lorem_ipsum_ar_SA",
"locale": "ar_SA.UTF-8",
"duration": 5.45405e+07,
"iterations": 16,
"mean": 3.40878e+06
},
"word list": {
"file": "strcoll-inputs/lorem_ipsum_en_US",
"locale": "en_US.UTF-8",
"duration": 4.63733e+07,
"iterations": 16,
"mean": 2.89833e+06
},
"word list": {
"file": "strcoll-inputs/lorem_ipsum_zh_CN",
"locale": "zh_CN.UTF-8",
"duration": 2.09213e+07,
"iterations": 16,
"mean": 1.30758e+06
},
"word list": {
"file": "strcoll-inputs/lorem_ipsum_cs_CZ",
"locale": "cs_CZ.UTF-8",
"duration": 5,6144e+07,
"iterations": 16,
"mean": 3,509e+06
},
"word list": {
"file": "strcoll-inputs/lorem_ipsum_en_GB",
"locale": "en_GB.UTF-8",
"duration": 5.56252e+07,
"iterations": 16,
"mean": 3.47658e+06
},
"word list": {
"file": "strcoll-inputs/lorem_ipsum_da_DK",
"locale": "da_DK.UTF-8",
"duration": 4,97187e+07,
"iterations": 16,
"mean": 3,10742e+06
},
"word list": {
"file": "strcoll-inputs/lorem_ipsum_pl_PL",
"locale": "pl_PL.UTF-8",
"duration": 4,46531e+07,
"iterations": 16,
"mean": 2,79082e+06
},
"word list": {
"file": "strcoll-inputs/lorem_ipsum_fr_FR",
"locale": "fr_FR.UTF-8",
"duration": 5,47468e+07,
"iterations": 16,
"mean": 3,42168e+06
},
"word list": {
"file": "strcoll-inputs/lorem_ipsum_pt_PT",
"locale": "pt_PT.UTF-8",
"duration": 5,45736e+07,
"iterations": 16,
"mean": 3,41085e+06
},
"word list": {
"file": "strcoll-inputs/lorem_ipsum_el_GR",
"locale": "el_GR.UTF-8",
"duration": 7,71665e+07,
"iterations": 16,
"mean": 4,8229e+06
},
"word list": {
"file": "strcoll-inputs/lorem_ipsum_ru_RU",
"locale": "ru_RU.UTF-8",
"duration": 5,48712e+07,
"iterations": 16,
"mean": 3,42945e+06
},
"word list": {
"file": "strcoll-inputs/lorem_ipsum_iw_IL",
"locale": "iw_IL.UTF-8",
"duration": 5.38097e+07,
"iterations": 16,
"mean": 3.3631e+06
},
"word list": {
"file": "strcoll-inputs/lorem_ipsum_es_ES",
"locale": "es_ES.UTF-8",
"duration": 5,28691e+07,
"iterations": 16,
"mean": 3,30432e+06
},
"word list": {
"file": "strcoll-inputs/lorem_ipsum_hi_IN",
"locale": "hi_IN.UTF-8",
"duration": 3.64249e+09,
"iterations": 16,
"mean": 2.27656e+08
},
"word list": {
"file": "strcoll-inputs/lorem_ipsum_sv_SE",
"locale": "sv_SE.UTF-8",
"duration": 4,69127e+07,
"iterations": 16,
"mean": 2,93204e+06
},
"word list": {
"file": "strcoll-inputs/lorem_ipsum_hu_HU",
"locale": "hu_HU.UTF-8",
"duration": 7,46276e+07,
"iterations": 16,
"mean": 4,66422e+06
},
"word list": {
"file": "strcoll-inputs/lorem_ipsum_tr_TR",
"locale": "tr_TR.UTF-8",
"duration": 4,89509e+07,
"iterations": 16,
"mean": 3,05943e+06
},
"word list": {
"file": "strcoll-inputs/lorem_ipsum_is_IS",
"locale": "is_IS.UTF-8",
"duration": 4,36657e+07,
"iterations": 16,
"mean": 2,72911e+06
},
"word list": {
"file": "strcoll-inputs/lorem_ipsum_it_IT",
"locale": "it_IT.UTF-8",
"duration": 5,59324e+07,
"iterations": 16,
"mean": 3,49578e+06
},
"word list": {
"file": "strcoll-inputs/lorem_ipsum_sr_RS",
"locale": "sr_RS.UTF-8",
"duration": 5,25292e+07,
"iterations": 16,
"mean": 3,28307e+06
},
"word list": {
"file": "strcoll-inputs/lorem_ipsum_ja_JP",
"locale": "ja_JP.UTF-8",
"duration": 1.96942e+07,
"iterations": 16,
"mean": 1.23089e+06
}
}
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [Patch] [BZ 15884] strcoll: improve performance by removing the cache
2014-10-13 12:20 ` Leonhard Holz
@ 2014-10-14 8:43 ` Siddhesh Poyarekar
2014-10-14 8:48 ` Leonhard Holz
0 siblings, 1 reply; 13+ messages in thread
From: Siddhesh Poyarekar @ 2014-10-14 8:43 UTC (permalink / raw)
To: Leonhard Holz; +Cc: libc-alpha
[-- Attachment #1: Type: text/plain, Size: 1363 bytes --]
On Mon, Oct 13, 2014 at 02:19:48PM +0200, Leonhard Holz wrote:
> please have a look at the attached JSON output of the strcoll benchmark.
Thanks.
> "strcoll": {
> "file list": {
> "directory": "..",
> "file_count": 39086,
> "locale": "en_US.UTF-8",
> "duration": 4.72532e+09,
> "iterations": 16,
> "mean": 2.95333e+08
> },
The "directory" and "file_count" directives are not necessary. Also,
rename the "file list" key to "" (an empty string) to indicate that
this is the default case, i.e. plain text, which is how the default
benchtest output looks like.
> "word list": {
> "file": "strcoll-inputs/lorem_ipsum_vi_VN",
> "locale": "vi_VN.UTF-8",
> "duration": 4,86973e+07,
> "iterations": 16,
> "mean": 3,04358e+06
> },
Likewise, the "file" directive is not necessary since it is derived
from the locale name. Instead of "word list", make the locale name as
the key so that you can get rid of the "locale" key.
With the above two changes, your "word list" and "file list" will end
up looking the same barring the extra 'locale' key in "plaintext":
"vi_VN.UTF-8": {
"duration": 4,86973e+07,
"iterations": 16,
"mean": 3,04358e+06
},
"": {
"locale": "en_US.UTF-8",
"duration": 4.72532e+09,
"iterations": 16,
"mean": 2.95333e+08
},
Siddhesh
[-- Attachment #2: Type: application/pgp-signature, Size: 473 bytes --]
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [Patch] [BZ 15884] strcoll: improve performance by removing the cache
2014-10-14 8:43 ` Siddhesh Poyarekar
@ 2014-10-14 8:48 ` Leonhard Holz
2014-10-14 8:53 ` Siddhesh Poyarekar
0 siblings, 1 reply; 13+ messages in thread
From: Leonhard Holz @ 2014-10-14 8:48 UTC (permalink / raw)
To: Siddhesh Poyarekar; +Cc: libc-alpha
Ok, I'll do so. After sending this I noticed that there is a problem in
json_attr_double. It's output is depended on the current locale - see
the "mean" field below. What to do about it?
Am 14.10.2014 10:43, schrieb Siddhesh Poyarekar:
> On Mon, Oct 13, 2014 at 02:19:48PM +0200, Leonhard Holz wrote:
>> please have a look at the attached JSON output of the strcoll benchmark.
>
> Thanks.
>
>> "strcoll": {
>> "file list": {
>> "directory": "..",
>> "file_count": 39086,
>> "locale": "en_US.UTF-8",
>> "duration": 4.72532e+09,
>> "iterations": 16,
>> "mean": 2.95333e+08
>> },
>
> The "directory" and "file_count" directives are not necessary. Also,
> rename the "file list" key to "" (an empty string) to indicate that
> this is the default case, i.e. plain text, which is how the default
> benchtest output looks like.
>
>> "word list": {
>> "file": "strcoll-inputs/lorem_ipsum_vi_VN",
>> "locale": "vi_VN.UTF-8",
>> "duration": 4,86973e+07,
>> "iterations": 16,
>> "mean": 3,04358e+06
>> },
>
> Likewise, the "file" directive is not necessary since it is derived
> from the locale name. Instead of "word list", make the locale name as
> the key so that you can get rid of the "locale" key.
>
> With the above two changes, your "word list" and "file list" will end
> up looking the same barring the extra 'locale' key in "plaintext":
>
> "vi_VN.UTF-8": {
> "duration": 4,86973e+07,
> "iterations": 16,
> "mean": 3,04358e+06
> },
>
> "": {
> "locale": "en_US.UTF-8",
> "duration": 4.72532e+09,
> "iterations": 16,
> "mean": 2.95333e+08
> },
>
> Siddhesh
>
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [Patch] [BZ 15884] strcoll: improve performance by removing the cache
2014-10-14 8:48 ` Leonhard Holz
@ 2014-10-14 8:53 ` Siddhesh Poyarekar
0 siblings, 0 replies; 13+ messages in thread
From: Siddhesh Poyarekar @ 2014-10-14 8:53 UTC (permalink / raw)
To: Leonhard Holz; +Cc: libc-alpha
[-- Attachment #1: Type: text/plain, Size: 346 bytes --]
On Tue, Oct 14, 2014 at 10:48:26AM +0200, Leonhard Holz wrote:
> Ok, I'll do so. After sending this I noticed that there is a problem in
> json_attr_double. It's output is depended on the current locale - see the
> "mean" field below. What to do about it?
Revert to en_US when calling the json functions, i.e. when printing
any output.
Siddhesh
[-- Attachment #2: Type: application/pgp-signature, Size: 473 bytes --]
^ permalink raw reply [flat|nested] 13+ messages in thread
end of thread, other threads:[~2014-10-14 8:53 UTC | newest]
Thread overview: 13+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2014-09-24 8:37 [Patch] [BZ 15884] strcoll: improve performance by removing the cache Leonhard Holz
2014-09-24 10:02 ` Siddhesh Poyarekar
[not found] ` <54231DF1.1050305@web.de>
2014-09-25 4:43 ` Siddhesh Poyarekar
2014-09-25 19:46 ` Carlos O'Donell
2014-09-29 10:30 ` Leonhard Holz
2014-10-05 10:16 ` [Ping] " Leonhard Holz
2014-10-07 15:26 ` Siddhesh Poyarekar
2014-10-08 8:32 ` Leonhard Holz
2014-10-08 9:09 ` Siddhesh Poyarekar
2014-10-13 12:20 ` Leonhard Holz
2014-10-14 8:43 ` Siddhesh Poyarekar
2014-10-14 8:48 ` Leonhard Holz
2014-10-14 8:53 ` Siddhesh Poyarekar
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).