diff mbox

[v2] Improve fnmatch performance.

Message ID 20150512235339.GA27716@domone
State New
Headers show

Commit Message

Ondřej Bílka May 12, 2015, 11:53 p.m. UTC 
Hi, this is revised improvement of fnmatch. It improves queries of
locate command around three times for UTF locale on x64 by finding start
of pattern with fast strstr.

It uses fast locale type check as introduced in strdiff.

How to synchronize this with gnulib? Only implementation specific detail
is utf8 detection.

There are several possible improvements. Main idea is reject strings as
fast as possible. If string is matched then likely you will do some
expensive operation with it.

This for simplicity just tries to find starting quarted of strstr.
it doesn't apply on patterns that start with special character.
Natural extension would be parse pattern, find quartet sequence that
must occur and do same strstr test. Second would be use whole characters
in casefold strstr with nonascii UTF.

Passes test, OK to commit this?

	* posix/fnmatch.c (fnmatch): Improve performance.

Comments

Paul Eggert May 13, 2015, 4:48 p.m. UTC | #1 
Ondřej Bílka wrote:
> How to synchronize this with gnulib? Only implementation specific detail
> is utf8 detection.

It could be something like this:

  #if _LIBC
   struct __locale_data *current = _NL_CURRENT_LOCALE->__locales[LC_COLLATE];
   uint_fast32_t encoding =
     current->values[_NL_ITEM_INDEX (_NL_COLLATE_ENCODING_TYPE)].word;
   bool is_utf8 = encoding == !__cet_other;
  #else
   bool is_utf8 = STRCASEEQ (locale_charset (),
                             "UTF-8", 'U','T','F','-','8',0,0,0,0)
  #endif

We should package this sort of thing up and make it easier to use, but that 
could be another day.
diff mbox

Patch

diff --git a/posix/fnmatch.c b/posix/fnmatch.c
index a707847..7152055 100644
--- a/posix/fnmatch.c
+++ b/posix/fnmatch.c
@@ -333,7 +333,48 @@  fnmatch (pattern, string, flags)
      int flags;
 {
 # if HANDLE_MULTIBYTE
-  if (__builtin_expect (MB_CUR_MAX, 1) != 1)
+
+  struct __locale_data *current = _NL_CURRENT_LOCALE->__locales[LC_COLLATE];
+  uint_fast32_t encoding =
+    current->values[_NL_ITEM_INDEX (_NL_COLLATE_ENCODING_TYPE)].word;
+
+  /* ASCII with \+/.*?[{(@! excluded.  */
+  static unsigned char normal[256] = {
+ 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
+ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+ 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 
+ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0,
+ 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
+ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1,
+ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
+ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
+ };
+
+  if (encoding == !__cet_other)
+    {
+      char start[16];
+      char *string2;
+      size_t i;
+      for (i = 0; i < 4 && normal[(unsigned char) pattern[i]]; i++)
+        start[i] = pattern[i];
+      start[i] = 0;
+      if (flags & FNM_CASEFOLD)
+        string2 = strcasestr (string, start);
+      else  
+        string2 = strstr (string, start);
+      if (!string2)
+        return FNM_NOMATCH;
+    }
+
+  if (MB_CUR_MAX != 1)
     {
       mbstate_t ps;
       size_t n;