Re: Compression and dictionaries

From: Shawn Pearce <spearce@spearce.org>
Date: Aug 16, 2006, 06:55 UTC
Message-ID: <20060816065515.GB18778@spearce.org>
In-Reply-To: <Pine.LNX.4.63.0608160832320.28360@wbgn013.biozentrum.uni-wuerzburg.de>

Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:

Show 11 quoted lines

> Hi,
> 
> On Wed, 16 Aug 2006, Jon Smirl wrote:
> 
> > On 8/16/06, John Rigby <jcrigby@gmail.com> wrote:
> > > Sorry if this is off topic, but could the dictionary be used to make
> > > git-grep alot faster?
> > 
> > It would be almost instant.
> 
> But only if you are not using a regular expression, but a single word.

Yes and no. If the inverted index contains terms broken by some known pattern (e.g. break on word-type boundaries) and the regex in question has constant sections (it should, otherwise it might as well just be '.') then you can reduce your search space to a fraction of the overall data by looking at the inverted index to select likely terms, select the related revisions containing those possible terms, then run the regex only on those revisions.

Sure you would be possibly pulling out a number of false positives but if the constant sequence(s) in the regex reduce your search space to below 1/2 of the overall data that's probably a lot less I/O and CPU required to complete the query, even if you have to read the entire dictionary and apply each term in the dictionary to the regex to look for those possible matches.

-- 
Shawn.