From f13c2a8dff2329c6692a80176262ceaaf8a6f74e Mon Sep 17 00:00:00 2001 From: Leonhard Holz Date: Tue, 12 May 2015 11:37:52 +0200 Subject: [PATCH] Improve strcoll with strdiff. This patch improves strcoll hot case by finding first byte that mismatches. That is in likely case enough to determine comparison result. --- ChangeLog | 11 +++++++++++ locale/C-collate.c | 4 +++- locale/categories.def | 1 + locale/langinfo.h | 1 + locale/localeinfo.h | 8 ++++++++ locale/programs/ld-collate.c | 9 +++++++++ string/strcoll_l.c | 38 +++++++++++++++++++++++++++++++++++++- wcsmbs/wcscoll_l.c | 1 + 8 files changed, 71 insertions(+), 2 deletions(-) diff --git a/ChangeLog b/ChangeLog index c998dd59b8..d78c626b25 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,14 @@ +2015-05-12 Leonhard Holz + + * locale/categories.def: Define _NL_COLLATE_ENCODING_TYPE. + * locale/langinfo.h: Add _NL_COLLATE_ENCODING_TYPE to attribute list. + * locale/localeinfo.h: Add enum collation_encoding_type. + * locale/C-collate.c: Set _NL_COLLATE_ENCODING_TYPE to 8bit. + * programs/ld-collate.c (collate_output): Add encoding type info. + * string/strcoll_l.c (STRDIFF): New function. + * (STRCOLL): Use STRDIFF to skip over equal prefix. + * wcsmbs/wcscoll_l.c: Define STRDIFF. + 2015-05-11 Joseph Myers [BZ #18397] diff --git a/locale/C-collate.c b/locale/C-collate.c index 06dfdfaad5..d7f3c550a5 100644 --- a/locale/C-collate.c +++ b/locale/C-collate.c @@ -144,6 +144,8 @@ const struct __locale_data _nl_C_LC_COLLATE attribute_hidden = /* _NL_COLLATE_COLLSEQWC */ { .string = (const char *) collseqwc }, /* _NL_COLLATE_CODESET */ - { .string = _nl_C_codeset } + { .string = _nl_C_codeset }, + /* _NL_COLLATE_ENCODING_TYPE */ + { .word = __cet_8bit } } }; diff --git a/locale/categories.def b/locale/categories.def index a8dda53007..045489d741 100644 --- a/locale/categories.def +++ b/locale/categories.def @@ -58,6 +58,7 @@ DEFINE_CATEGORY DEFINE_ELEMENT (_NL_COLLATE_COLLSEQMB, "collate-collseqmb", std, wstring) DEFINE_ELEMENT (_NL_COLLATE_COLLSEQWC, "collate-collseqwc", std, wstring) DEFINE_ELEMENT (_NL_COLLATE_CODESET, "collate-codeset", std, string) + DEFINE_ELEMENT (_NL_COLLATE_ENCODING_TYPE, "collate-encoding-type", std, word) ), NO_POSTLOAD) diff --git a/locale/langinfo.h b/locale/langinfo.h index a565d9d120..ffc5c7f471 100644 --- a/locale/langinfo.h +++ b/locale/langinfo.h @@ -255,6 +255,7 @@ enum _NL_COLLATE_COLLSEQMB, _NL_COLLATE_COLLSEQWC, _NL_COLLATE_CODESET, + _NL_COLLATE_ENCODING_TYPE, _NL_NUM_LC_COLLATE, /* LC_CTYPE category: character classification. diff --git a/locale/localeinfo.h b/locale/localeinfo.h index 1d2ee00876..bdab9fe745 100644 --- a/locale/localeinfo.h +++ b/locale/localeinfo.h @@ -110,6 +110,14 @@ enum coll_sort_rule sort_mask }; +/* Collation encoding type. */ +enum collation_encoding_type +{ + __cet_other, + __cet_8bit, + __cet_utf8 +}; + /* We can map the types of the entries into a few categories. */ enum value_type { diff --git a/locale/programs/ld-collate.c b/locale/programs/ld-collate.c index dc0fe30a13..a39a94f2cc 100644 --- a/locale/programs/ld-collate.c +++ b/locale/programs/ld-collate.c @@ -32,6 +32,7 @@ #include "linereader.h" #include "locfile.h" #include "elem-hash.h" +#include "../localeinfo.h" /* Uncomment the following line in the production version. */ /* #define NDEBUG 1 */ @@ -2130,6 +2131,8 @@ collate_output (struct localedef_t *locale, const struct charmap_t *charmap, /* The words have to be handled specially. */ if (idx == _NL_ITEM_INDEX (_NL_COLLATE_SYMB_HASH_SIZEMB)) add_locale_uint32 (&file, 0); + else if (idx == _NL_ITEM_INDEX (_NL_COLLATE_ENCODING_TYPE)) + add_locale_uint32 (&file, __cet_other); else add_locale_empty (&file); } @@ -2493,6 +2496,12 @@ collate_output (struct localedef_t *locale, const struct charmap_t *charmap, add_locale_raw_data (&file, collate->mbseqorder, 256); add_locale_collseq_table (&file, &collate->wcseqorder); add_locale_string (&file, charmap->code_set_name); + if (strcmp (charmap->code_set_name, "UTF-8") == 0) + add_locale_uint32 (&file, __cet_utf8); + else if (charmap->mb_cur_max == 1) + add_locale_uint32 (&file, __cet_8bit); + else + add_locale_uint32 (&file, __cet_other); write_locale_data (output_path, LC_COLLATE, "LC_COLLATE", &file); obstack_free (&weightpool, NULL); diff --git a/string/strcoll_l.c b/string/strcoll_l.c index 658d5b9b90..0fa005f0f9 100644 --- a/string/strcoll_l.c +++ b/string/strcoll_l.c @@ -29,6 +29,7 @@ # define STRING_TYPE char # define USTRING_TYPE unsigned char # define STRCOLL __strcoll_l +# define STRDIFF __strdiff # define STRCMP strcmp # define WEIGHT_H "../locale/weight.h" # define SUFFIX MB @@ -41,6 +42,20 @@ #include "../locale/localeinfo.h" #include WEIGHT_H +#define MASK_UTF8_7BIT (1 << 7) +#define MASK_UTF8_START (3 << 6) + +size_t +STRDIFF (const STRING_TYPE *s, const STRING_TYPE *t) +{ + size_t n; + + for (n = 0; *s != '\0' && *s++ == *t++; ++n) + continue; + + return n; +} + /* Track status while looking for sequences in a string. */ typedef struct { @@ -255,9 +270,29 @@ STRCOLL (const STRING_TYPE *s1, const STRING_TYPE *s2, __locale_t l) const USTRING_TYPE *extra; const int32_t *indirect; + /* In case there is no locale specific sort order (C / POSIX). */ if (nrules == 0) return STRCMP (s1, s2); + /* Fast forward to the position of the first difference. Needs to be + encoding aware as the byte-by-byte comparison can stop in the middle + of a char sequence for multibyte encodings like UTF-8. */ + uint_fast32_t encoding = + current->values[_NL_ITEM_INDEX (_NL_COLLATE_ENCODING_TYPE)].word; + if (encoding != __cet_other) + { + size_t diff = STRDIFF (s1, s2); + if (diff > 0) + { + if (encoding == __cet_utf8 && (*(s1 + diff) & MASK_UTF8_7BIT) != 0) + do + diff--; + while (diff > 0 && (*(s1 + diff) & MASK_UTF8_START) != MASK_UTF8_START); + s1 += diff; + s2 += diff; + } + } + /* Catch empty strings. */ if (__glibc_unlikely (*s1 == '\0') || __glibc_unlikely (*s2 == '\0')) return (*s1 != '\0') - (*s2 != '\0'); @@ -321,7 +356,8 @@ STRCOLL (const STRING_TYPE *s1, const STRING_TYPE *s2, __locale_t l) byte-level comparison to ensure that we don't waste time going through multiple passes for totally equal strings before proceeding to subsequent passes. */ - if (pass == 0 && STRCMP (s1, s2) == 0) + if (pass == 0 && encoding == __cet_other && + STRCMP (s1, s2) == 0) return result; else break; diff --git a/wcsmbs/wcscoll_l.c b/wcsmbs/wcscoll_l.c index 106ec93511..9f60cee9ea 100644 --- a/wcsmbs/wcscoll_l.c +++ b/wcsmbs/wcscoll_l.c @@ -23,6 +23,7 @@ #define STRING_TYPE wchar_t #define USTRING_TYPE wint_t #define STRCOLL __wcscoll_l +#define STRDIFF __wcsdiff #define STRCMP wcscmp #define WEIGHT_H "../locale/weightwc.h" #define SUFFIX WC -- 2.11.4.GIT