Skip to contentSkip to conversation

read-cache.c: index format v5 -- 30% smaller/faster than v4

PATCH In review Nguyễn Thái Ngọc Duy 4 participants 5 messages Feb 13, 2019 – Feb 15, 2019

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 read-cache.c: index format v5 -- 30% smaller/faster than v4

Index file size more or less translates to write time because we hash the entire file every time we update the index. And we update the index quite often (automatically index refresh is done everywhere). This means smaller index files are faster, especially true for very large worktrees.

Index v4 attempts to reduce file size by "prefix compressing" paths. This reduces file size from 17% (git.git) to 41% (webkit.git, deep hierarchy).

Index v5 takes the same idea to the next level. Instead of compressing just paths, based on the previous entry, we "compress" a lot more fields.

Take a look at stat data, st_dev, st_uid, st_gid and st_mode are the same most of the time. ctime should often be the same (or differs just slightly). And sometimes mtime is the same as well. st_ino is also always zero on Windows. We're storing a lot of duplicate values.

Index v5 handles this

- by adding a "same mask" per entry. If st_dev is the same as previous entry, for instance, we set "st_dev is the same" flag and will not store it at all, saving 31 bits per entry.

- even when we store it, "varint" encoding is used. We should rarely need to write out 4 bytes

- for ctime and mtime, even if we have to store it, we store the offset instead of absolute numbers. This often leads to smaller numbers, which also means fewer bytes to encode.

As a result of this, v5 reduces file size from 30% (git.git) to 36% (webkit.git) compared to v4. Comparing to v2, webkit.git index file size is reduced by 63%! A 8.4MB index file is _almost_ acceptable.

Of course we trade off storage with cpu. We now need to spend more cycles writing or even reading (but still plenty fast compared to zlib). For reading, I'm counting on multi thread to hide away all this even if it becomes significant.

For writing, I believe the extra cycles spent in writing is still nothing compared to hashing code and this should still result in faster index update (numbers needed). On webkit.git, updating one entry on v5 is 30% faster than v4.

---
I forgot why I started on this again. Something from the mailing list... Anyway this looks exciting!

 cache.h      |   2 +-
 read-cache.c | 245 ++++++++++++++++++++++++++++++++++++++++++++++++---
 2 files changed, 234 insertions(+), 13 deletions(-)
cache.h +1 -1
index 27fe635f62..fb5175fbb2 100644
@@ -140,7 +140,7 @@ struct cache_header {
 };
 
 #define INDEX_FORMAT_LB 2
-#define INDEX_FORMAT_UB 4
+#define INDEX_FORMAT_UB 5
 
 /*
  * The "cache_time" is just the low 32 bits of the
read-cache.c +233 -12

323 lines not on this page · raw message

Signature · 1 line
2.21.0.rc0.328.g0e39304f8d
#1 lore raw

read-cache.c static struct cache_entry *create_from_disk(struct mem_pool *ce_mem_pool, · line 1753

Quoted 6 lines · Nguyễn Thái Ngọc Duy
read-cache.c +1 -1
@@ -1749,16 +1750,16 @@ static struct cache_entry *create_from_disk(struct mem_pool *ce_mem_pool,
 	 * number of bytes to be stripped from the end of the previous name,
 	 * and the bytes to append to the result, to come up with its name.
 	 */
-	int expand_name_field = version == 4;
+	int expand_name_field = version >= 4;

The code can be lazy like this, insteasd of being more descriptive to say "version 4 or 5", because we won't accept version 6 or later anyway. Which is OK, I guess.

read-cache.c static struct cache_entry *create_from_disk(struct mem_pool *ce_mem_pool, · line 1765

Quoted 9 lines
read-cache.c +2 -2
 	if (flags & CE_EXTENDED) {
-		struct ondisk_cache_entry_extended *ondisk2;
+		const struct ondisk_cache_entry_extended *ondisk2 = mmap;
 		int extended_flags;
-		ondisk2 = (struct ondisk_cache_entry_extended *)ondisk;
+
 		extended_flags = get_be16(&ondisk2->flags2) << 16;
 		/* We do not yet understand any bit out of CE_EXTENDED_FLAGS */
 		if (extended_flags & ~CE_EXTENDED_FLAGS)

This part may be a good clean-up regardless.

Quoted 5 lines
read-cache.c +1 -0
@@ -1820,6 +1821,113 @@ static struct cache_entry *create_from_disk(struct mem_pool *ce_mem_pool,
 	return ce;
 }
 
+enum same_value_bit {

read-cache.c static struct cache_entry *create_from_disk(struct mem_pool *ce_mem_pool, · line 1834

Quoted 10 lines
read-cache.c +10 -0
+	DELTA_FORMAT = 1 << 0,
+	SAME_CTIME   = 1 << 1, /* only covers sec, not nsec */
+	SAME_MTIME   = 1 << 2, /* only covers sec, not nsec */
+	SAME_DEV     = 1 << 3,
+	SAME_INO     = 1 << 4,
+	SAME_MODE    = 1 << 5,
+	SAME_UID     = 1 << 6,
+	SAME_GID     = 1 << 7,
+	SAME_FLAGS   = 1 << 7
+};

Hmph, really?

read-cache.c static struct cache_entry *create_from_disk(struct mem_pool *ce_mem_pool, · line 1840

Quoted 5 lines
read-cache.c +5 -0
+static struct cache_entry no_previous_ce;
+
+static uintmax_t decode_varoffset(const unsigned char **bufp, uintmax_t prev)
+{
+	uintmax_t val = decode_varint(bufp);

You'd need to make sure (1) !val, which indicates an overflow of the varint, and (2) bufp after decoding haven't over-read the mmapped index file. We may want to improve decode_varint() API so that we can detect truncated data (i.e. (2)) more reliably without first reading too much. Loose error checking like these would make good targets for fuzz tests, I suspect.

Review static struct cache_entry *create_from_disk(struct mem_pool *ce_mem_pool, · line 1841

Quoted 2 lines
(quoted diff) +2 -0
+	return val & 1 ? prev - (val >> 1) : prev + (val >> 1);
+}

So, the LSB is used for sign, and the magnitude is shifted by one? OK.

read-cache.c static struct cache_entry *create_from_disk(struct mem_pool *ce_mem_pool, · line 1855

Quoted 11 lines
read-cache.c +11 -0
+static uintmax_t decode_varoffset_same(const unsigned char **bufp, uintmax_t prev,
+				       int same_flag)
+{
+	return same_flag ? prev : decode_varoffset(bufp, prev);
+}
+
+static uintmax_t decode_varint_same(const unsigned char **bufp, uintmax_t prev,
+				    int same_flag)
+{
+	return same_flag ? prev : decode_varint(bufp);
+}

Likewise about two error conditions.

Quoted 9 lines
read-cache.c +0 -2
@@ -1967,12 +2075,18 @@ static unsigned long load_cache_entry_block(struct index_state *istate,
 	unsigned long src_offset = start_offset;
 
 	for (i = offset; i < offset + nr; i++) {
-		struct ondisk_cache_entry *disk_ce;
 		struct cache_entry *ce;
 		unsigned long consumed;
 
-		disk_ce = (struct ondisk_cache_entry *)(mmap + src_offset);

read-cache.c static unsigned long load_cache_entry_block(struct index_state *istate, · line 2089

Quoted 10 lines
read-cache.c +9 -1
-		ce = create_from_disk(ce_mem_pool, istate->version, disk_ce, &consumed, previous_ce);
+		if (istate->version <= 4)
+			ce = create_from_disk(ce_mem_pool, istate->version,
+					      mmap + src_offset, &consumed,
+					      previous_ce);
+		else
+			ce = create_from_disk_v5(ce_mem_pool,
+						 mmap + src_offset,
+						 &consumed,
+						 previous_ce);

This goes directly against the spirit of "create_from_disk()" internal API, doesn't it? It takes istate->version because it is an implementation detail of that function how bytes at &mmap[src_offset] are consumed, possibly using previous_ce information.

IOW, I think the version dependent switch should go inside that function and not in this loop.

read-cache.c static void copy_cache_entry_to_ondisk(struct ondisk_cache_entry *ondisk, · line 2670

Quoted 3 lines
read-cache.c +3 -0
+static int ce_write_varint(git_hash_ctx *c, int fd, uintmax_t value)
+{
+	unsigned char varint[16];

We may want to do something about these "16".

Quoted 3 lines
read-cache.c +3 -0
+static int ce_write_varoffset(git_hash_ctx *c, int fd, uintmax_t next, uintmax_t prev)
+{
+	unsigned char varint[16];
#2 lore raw
In reply to Nguyễn Thái Ngọc Duy
Quoted 14 lines · Nguyễn Thái Ngọc Duy

Index file size more or less translates to write time because we hash the entire file every time we update the index. And we update the index quite often (automatically index refresh is done everywhere). This means smaller index files are faster, especially true for very large worktrees.

Index v4 attempts to reduce file size by "prefix compressing" paths. This reduces file size from 17% (git.git) to 41% (webkit.git, deep hierarchy).

Index v5 takes the same idea to the next level. Instead of compressing just paths, based on the previous entry, we "compress" a lot more fields.

Quoted 6 lines

Take a look at stat data, st_dev, st_uid, st_gid and st_mode are the same most of the time. ctime should often be the same (or differs just slightly). And sometimes mtime is the same as well. st_ino is also always zero on Windows. We're storing a lot of duplicate values.

Index v5 handles this

This looks really promising.

Quoted 10 lines

- by adding a "same mask" per entry. If st_dev is the same as previous entry, for instance, we set "st_dev is the same" flag and will not store it at all, saving 31 bits per entry.

- even when we store it, "varint" encoding is used. We should rarely need to write out 4 bytes

- for ctime and mtime, even if we have to store it, we store the offset instead of absolute numbers. This often leads to smaller numbers, which also means fewer bytes to encode.

Sounds good. I wonder if you've thought about/considered a couple of optimizations on top of this, or if they're possible. Both share the same theme:

* Instead of adding a "same as last mask" adding "same as Nth mask". Something similar exists in the Sereal format (which also has other techniques you use, e.g. varint
https://github.com/Sereal/Sereal/blob/master/sereal_spec.pod#the-copy-tag)

So instead of:

      <mask1><same><mask2><same><mask1><same> etc.

You'd have:

      <mask1 (mark1)><same><mask2 (mark2)><same><insert: mark1><same> etc.

I.e. when you have data that flip-flops a lot you can save space by saying "it's the same as existing earlier value at offset N". Maybe it doesn't make sense for this data, I don't know...

* For ctime/mtime presumably for dir paths, are these paths tolerant to or already out of glob() order? Then perhaps they can be pre-sorted so the compression or ctime/mtime offset compression is more effective.

Quoted 8 lines

As a result of this, v5 reduces file size from 30% (git.git) to 36% (webkit.git) compared to v4. Comparing to v2, webkit.git index file size is reduced by 63%! A 8.4MB index file is _almost_ acceptable.

Of course we trade off storage with cpu. We now need to spend more cycles writing or even reading (but still plenty fast compared to zlib). For reading, I'm counting on multi thread to hide away all this even if it becomes significant.

This would be a bigger change, but have we/you ever done a POC experiment to see how much of this time is eaten up by zlib that wouldn't be eaten up with some of the newer "fast but good enough" compression algorithms, e.g. Snappy and Zstandard?

author
#3 lore raw
Quoted 8 lines · Ævar Arnfjörð Bjarmason
Quoted 6 lines

Take a look at stat data, st_dev, st_uid, st_gid and st_mode are the same most of the time. ctime should often be the same (or differs just slightly). And sometimes mtime is the same as well. st_ino is also always zero on Windows. We're storing a lot of duplicate values.

Index v5 handles this

This looks really promising.

I was going to reply to Junio. But it turns out I underestimated "varint" encoding overhead and it increases read time too much. I might get back and try some optimization when I'm bored, but until then this is yet another failed experiment.

Quoted 9 lines
Quoted 8 lines

As a result of this, v5 reduces file size from 30% (git.git) to 36% (webkit.git) compared to v4. Comparing to v2, webkit.git index file size is reduced by 63%! A 8.4MB index file is _almost_ acceptable.

Of course we trade off storage with cpu. We now need to spend more cycles writing or even reading (but still plenty fast compared to zlib). For reading, I'm counting on multi thread to hide away all this even if it becomes significant.

Quoted 4 lines

This would be a bigger change, but have we/you ever done a POC experiment to see how much of this time is eaten up by zlib that wouldn't be eaten up with some of the newer "fast but good enough" compression algorithms, e.g. Snappy and Zstandard?

I'm quite sure I tried zlib at some point, the only lasting impression I have is "not good enough". Other algorithms might improve a bit, perhaps on the uncompress/read side, but I find it unlikely we could reasonably compress like a hundred megabytes in a few dozen milliseconds (a quick google says Snappy compresses 250MB/s, so about 400ms per 100MB, too long). Splitting the files and compressing in parallel might help. But I will probably focus on "sparse index" approach before going that direction.

Signature · 1 line
Duy
#4 lore raw
Quoted 7 lines · Duy Nguyen
Quoted 5 lines · Ævar Arnfjörð Bjarmason
Quoted 5 lines

Take a look at stat data, st_dev, st_uid, st_gid and st_mode are the same most of the time. ctime should often be the same (or differs just slightly). And sometimes mtime is the same as well. st_ino is also always zero on Windows. We're storing a lot of duplicate values.

Quoted 13 lines
Quoted 3 lines
Quoted 1 line

Index v5 handles this

This looks really promising.

I was going to reply to Junio. But it turns out I underestimated "varint" encoding overhead and it increases read time too much. I might get back and try some optimization when I'm bored, but until then this is yet another failed experiment.

Quoted 4 lines
Quoted 4 lines

As a result of this, v5 reduces file size from 30% (git.git) to 36% (webkit.git) compared to v4. Comparing to v2, webkit.git index file size is reduced by 63%! A 8.4MB index file is _almost_ acceptable.

Just for kicks, I tried this out on a couple of repos I have handy.

files version index size %savings
200k 2 25,033,758 0.00%

	3	25,033,758	0.00%
	4	15,269,923	39.00%
	5	9,759,844	61.01%

3m 2 446,123,848 0.00%

	3	446,123,848	0.00%
	4	249,631,640	44.04%
	5	82,147,981	81.59%

The 81% savings is very impressive. I didn't measure performance but not writing out an extra 167MB to disk has to help.

I'm definitely also interested in your 'sparse index' format ideas as in our 3M repos, there are typically only a few thousand that don't have the skip-worktree bit set. I'm not sure if that is the same 'sparse' you had in mind but it would sure be nice!

I've also contemplated multi-threading the index write code path. My thought was in the primary thread to allocate a buffer and when it is full have a background thread compute the SHA and write it to disk while the primary thread fills the next buffer.

I'm not sure how much it will buy us as I don't know the relative cost of computing the SHA/writing to disk vs filling the buffer. I've suspected the filling the buffer thread would end up blocked on the background thread most of the time which is why I haven't tried it yet.

Quoted 19 lines
Quoted 9 lines
Quoted 4 lines

Of course we trade off storage with cpu. We now need to spend more cycles writing or even reading (but still plenty fast compared to zlib). For reading, I'm counting on multi thread to hide away all this even if it becomes significant.

This would be a bigger change, but have we/you ever done a POC experiment to see how much of this time is eaten up by zlib that wouldn't be eaten up with some of the newer "fast but good enough" compression algorithms, e.g. Snappy and Zstandard?

I'm quite sure I tried zlib at some point, the only lasting impression I have is "not good enough". Other algorithms might improve a bit, perhaps on the uncompress/read side, but I find it unlikely we could reasonably compress like a hundred megabytes in a few dozen milliseconds (a quick google says Snappy compresses 250MB/s, so about 400ms per 100MB, too long). Splitting the files and compressing in parallel might help. But I will probably focus on "sparse index" approach before going that direction.