bug-coreutils
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

faster fnmatch


From: Ondrej Bilka
Subject: faster fnmatch
Date: Thu, 16 Apr 2009 21:09:44 +0200
User-agent: Mutt/1.5.18 (2008-05-17)

Hello. I am writing partial fnmatch to speed up locate et al. 
Idea is save state state to match common prefix only once.

fnmatch source is too complex so I wrote simplified version.
My code is 2-4 times faster than fnmatch.

Here is list what provided speedup and can be applied to original source

FOLD causes worst performance slowdown. 
>From what I tried is best convert in buffer to uppercase when needed.

Other optimalizations are based on preprocessing pattern

1. For each * we compute minimal size of rest and we have smaller for cycles.
2. We can replace *? by ?*
3. If * is followed by letter we check it at for cycle of *
4. If pattern contains four consecutive letters we compare them as int

I also tried optimalizations which didnt worked. 
use mask to match four letters and ?
strlen trick to find first letter after * faster.
Boyer-moore skiping didnt work either.

-- 

50% of the manual is in .pdf readme files




reply via email to

[Prev in Thread] Current Thread [Next in Thread]