Posts Tagged binary

Cache implementation reloaded (II)

Last week I talked about many changes in the cache implementation. Well, yesterday I made more changes.

My proposal on Summer of Code was based on using an embedded database. But I changed the algorithm that builds the graph and the queries against the database also changed. These queries now are very simple so I’ve decided to remove the database dependency and use binary files instead. Now I’m using two files to store the log messages:

LogMessages file

This file stores all log messages in a binary format. I use RandomAccessFile to read and write in it. RandomAccessFile lets me move to a certain byte position with its seek() method. Also it lets me know in which position I am, thanks to the getFilePointer() method.

Revisions file

This file indexes the previous file. It stores the offsets of each log message in the logMessages file. This is, from byte 0 to 7 it saves the offset of the first log message; from byte 8 to 15 it saves the offset of the second log message; and so on. That is, for the Nth revision the offset is stored at position (N-1)*8.

If I need to read the log message of a certain revision this is more or less what happens:

revisions.seek((revision-1)*8);
long offset = revisions.readLong();
logMessages.seek(offset);
logMessage = readNext();

Very simple, very fast 🙂

With this file it’s also very simple to know which is the latest revision number stored:

long latestRevision = revisions.length() / 8;

Now it takes about 3 seconds in my computer to build a graph from a repository with 4,000 revisions. The later implementation took 8 seconds. Also the database size is lesser and no initialization is required (the embedded database took about 10 seconds to initializate).

My plan now is to improve the graph output (maybe using Zest) and try to include merge information.

Leave a Comment