[Top][All Lists]
[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
- faster fnmatch,
Ondrej Bilka <=