Re: GSoC - Designing a faster index format

From: Nguyen Thai Ngoc Duy <pclouds@gmail.com>
Date: Mar 27, 2012, 06:31 UTC
Message-ID: <CACsJy8BZVFKZvd1=jz8PoCvTKjX6LorRidJgTxsjFUGfBUai+w@mail.gmail.com>
In-Reply-To: <CAJo=hJsPgUZi2qMc5aDUn0+o5=9n7pBS+yWBASfqtov8WuFBRA@mail.gmail.com>

On Mon, Mar 26, 2012 at 11:08 PM, Shawn Pearce <spearce@spearce.org> wrote:

Show 11 quoted lines

>> [1] http://www.sqlite.org/fileformat2.html
>
> Or use LevelDb[2]. Its BSD license. Uses an immutable file format, but
> writes updates to new smaller files and eventually collapses
> everything back together into a bigger file. This can be a
> dramatically simpler approach than dealing with your own free block
> system inside of a single file. Its only real downside is needing to
> periodically pay a penalty to rewrite the whole index. But this
> rewrite is going to be faster than the time it takes to rewrite the
> pack files for the same repository, which git gc or git repack
> handles. So I don't think its actually a problem for the index.

Cool. I had an experiment with it. A database is created where are keys `git ls-files` on linux-2.6. A few things after the experiment:

 - we need to link to libstdc++.so. I still hope to avoid any new
runtime dependencies
 - I use gettimeofday to time some operations. On linux-2.6,
read_cache() costs 27ms. leveldb_open() alone takes 90ms. Iterating
over all keys takes ~200ms.

Performance wise it does not look very good but maybe I'm just not doing it right.

> [2] http://code.google.com/p/leveldb/

-- 
Duy