Re: [PATCH 8/8] wildmatch: advance faster in asterisk + literal patterns

2012-12-27 Thread Junio C Hamano 
Nguyễn Thái Ngọc Duy  pclo...@gmail.com writes:

 compat, '*/*/*' on linux-2.6.git file list 2000 times, before:
 wildmatch 7s 985049us
 fnmatch   2s 735541us or 34.26% faster

 and after:
 wildmatch 4s 492549us
 fnmatch   0s 888263us or 19.77% slower

 Signed-off-by: Nguyễn Thái Ngọc Duy pclo...@gmail.com
 ---
  wildmatch.c | 21 +
  1 file changed, 21 insertions(+)

 diff --git a/wildmatch.c b/wildmatch.c
 index 3794c4d..68b02e4 100644
 --- a/wildmatch.c
 +++ b/wildmatch.c
 @@ -132,6 +132,27 @@ static int dowild(const uchar *p, const uchar *text, 
 unsigned int flags)
   while (1) {
   if (t_ch == '\0')
   break;
 + /*
 +  * Try to advance faster when an asterisk is
 +  * followed by a literal. We know in this case
 +  * that the the string before the literal
 +  * must belong to *.
 +  */
 + if (!is_glob_special(*p)) {

So far, we have looked at *x or **x in the pattern, p points at
'x' (not an asterisk), and we have text to match.  For text to
match this pattern, the earlier part of it that is consumed to match
the asterisk must be followed by x.  special tells us if we are
allowed to treat '/' as matching the asterisk.

 + p_ch = *p;
 + if ((flags  WM_CASEFOLD)  
 ISUPPER(p_ch))
 + p_ch = tolower(p_ch);

That x in the example is picked up here and stored in p_ch.
Let's skip over text and find that x in there.

 + while ((t_ch = *text) != '\0' 
 +(!(flags  WM_PATHNAME) || t_ch 
 != '/')) {

Why do we look at (flags  WM_PATHMAME) and not special here?

 + if ((flags  WM_CASEFOLD)  
 ISUPPER(t_ch))
 + t_ch = tolower(t_ch);
 + if (t_ch == p_ch)
 + break;

Found it.

 + text++;
 + }
 + if (t_ch != p_ch)
 + return WM_NOMATCH;

If we did not find that x, then **x or *x can never match.
OK.  And at this point text points at that x we found, and p
points at x after the asterisk in the pattern.

Looks good so far.  Thanks.

 + }
   if ((matched = dowild(p, text,  flags)) != 
 WM_NOMATCH) {
   if (!special || matched != 
 WM_ABORT_TO_STARSTAR)
   return matched;
--
To unsubscribe from this list: send the line unsubscribe git in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH 8/8] wildmatch: advance faster in asterisk + literal patterns

2012-12-27 Thread Nguyen Thai Ngoc Duy 
On Fri, Dec 28, 2012 at 1:24 PM, Junio C Hamano gits...@pobox.com wrote:
 + while ((t_ch = *text) != '\0' 
 +(!(flags  WM_PATHNAME) || t_ch 
 != '/')) {

 Why do we look at (flags  WM_PATHMAME) and not special here?

Because I was careless. Thanks for spotting it. I'll fix it and add
some more tests about **literal with WM_PATHNAME.
-- 
Duy
--
To unsubscribe from this list: send the line unsubscribe git in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

[PATCH 8/8] wildmatch: advance faster in asterisk + literal patterns

2012-12-21 Thread Nguyễn Thái Ngọc Duy 
compat, '*/*/*' on linux-2.6.git file list 2000 times, before:
wildmatch 7s 985049us
fnmatch   2s 735541us or 34.26% faster

and after:
wildmatch 4s 492549us
fnmatch   0s 888263us or 19.77% slower

Signed-off-by: Nguyễn Thái Ngọc Duy pclo...@gmail.com
---
 wildmatch.c | 21 +
 1 file changed, 21 insertions(+)

diff --git a/wildmatch.c b/wildmatch.c
index 3794c4d..68b02e4 100644
--- a/wildmatch.c
+++ b/wildmatch.c
@@ -132,6 +132,27 @@ static int dowild(const uchar *p, const uchar *text, 
unsigned int flags)
while (1) {
if (t_ch == '\0')
break;
+   /*
+* Try to advance faster when an asterisk is
+* followed by a literal. We know in this case
+* that the the string before the literal
+* must belong to *.
+*/
+   if (!is_glob_special(*p)) {
+   p_ch = *p;
+   if ((flags  WM_CASEFOLD)  
ISUPPER(p_ch))
+   p_ch = tolower(p_ch);
+   while ((t_ch = *text) != '\0' 
+  (!(flags  WM_PATHNAME) || t_ch 
!= '/')) {
+   if ((flags  WM_CASEFOLD)  
ISUPPER(t_ch))
+   t_ch = tolower(t_ch);
+   if (t_ch == p_ch)
+   break;
+   text++;
+   }
+   if (t_ch != p_ch)
+   return WM_NOMATCH;
+   }
if ((matched = dowild(p, text,  flags)) != 
WM_NOMATCH) {
if (!special || matched != 
WM_ABORT_TO_STARSTAR)
return matched;
-- 
1.8.0.rc2.23.g1fb49df

--
To unsubscribe from this list: send the line unsubscribe git in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html