[2/3] read-cache: read on-disk entries in byte order

Commit Message

Jeff King Sept. 28, 2022, 4:21 a.m. UTC

An index entry starts with stat data and mode, followed by an oid,
followed by flags, followed by the entry name. We parse this out of
order:

  1. we must read the flags to know how long the name is

  2. we must know how long the name is in order to allocate the
     struct cache_entry, since it has a FLEX_ARRAY

  3. we must allocate the cache_entry in order to parse the stat_data
     and oid into it

This makes the parser a little hard to follow, because we have to access
the flags using an offset, rather than walking through it in byte order.

We can break the cyclic dependency by parsing the stat_data, etc, into
temporary variables, then allocating the cache_entry and copying the
parsed values in. This sets us up for simplifying the parsing in the
next commit.

The downside is that we're copying the data an extra time. It's not very
much data, and it's all fixed size, so the compiler should be able to do
a reasonable job of optimizing here. But I didn't time the potential
impact.

Note one subtlety in the patch: besides reordering the flags/name versus
stat data, we adjust the order within the stat data to match the on-disk
order (notably both fields of each cache_time struct are adjacent).

Signed-off-by: Jeff King <[e-mail]>
---
 read-cache.c | 42 +++++++++++++++++++++++++-----------------
 1 file changed, 25 insertions(+), 17 deletions(-)

Comments

Jeff King Sept. 29, 2022, 11:27 a.m. UTC | #1

On Wed, Sep 28, 2022 at 12:21:15AM -0400, Jeff King wrote:

> The downside is that we're copying the data an extra time. It's not very
> much data, and it's all fixed size, so the compiler should be able to do
> a reasonable job of optimizing here. But I didn't time the potential
> impact.

I timed this using "test-tool read-cache". It's kind of an artificial
benchmark, but it does isolate the code we're touching here. The results
are...not good. Here's the time to read the index of linux.git 1000
times, before and after this reordering patch:

  Benchmark 1: ./test-tool.old read-cache 1000
    Time (mean ± σ):      2.870 s ±  0.073 s    [User: 2.555 s, System: 0.315 s]
    Range (min … max):    2.789 s …  3.001 s    10 runs
  
  Benchmark 2: ./test-tool.new read-cache 1000
    Time (mean ± σ):      3.180 s ±  0.080 s    [User: 2.849 s, System: 0.331 s]
    Range (min … max):    3.092 s …  3.297 s    10 runs
  
  Summary
    './test-tool.old read-cache 1000' ran
      1.11 ± 0.04 times faster than './test-tool.new read-cache 1000'

I think that's probably the nail in the coffin for my proposed approach.
To be fair, it's only .3ms extra for a normal program which reads the
index once. That's not that big in absolute numbers. But there are
larger index files in the wild. And the improvement in simplicity and
readability is simply not that great.

-Peff

Junio C Hamano Sept. 29, 2022, 3:47 p.m. UTC | #2

Jeff King <[e-mail]> writes:

> On Wed, Sep 28, 2022 at 12:21:15AM -0400, Jeff King wrote:
>
>> The downside is that we're copying the data an extra time. It's not very
>> much data, and it's all fixed size, so the compiler should be able to do
>> a reasonable job of optimizing here. But I didn't time the potential
>> impact.
> ...
>   Summary
>     './test-tool.old read-cache 1000' ran
>       1.11 ± 0.04 times faster than './test-tool.new read-cache 1000'
>
> I think that's probably the nail in the coffin for my proposed approach.
> To be fair, it's only .3ms extra for a normal program which reads the
> index once. That's not that big in absolute numbers. But there are
> larger index files in the wild. And the improvement in simplicity and
> readability is simply not that great.

Thanks for the due diligence.  This result may be an indication of
how efficient the existing code is, but it is a bit surprising that
one more copy of the stat_data struct makes that much difference.

Patch

diff --git a/read-cache.c b/read-cache.c
index d16eb97906..efb9efa5ee 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -1879,11 +1879,14 @@  static struct cache_entry *create_from_disk(struct mem_pool *ce_mem_pool,
 					    unsigned long *ent_size,
 					    const struct cache_entry *previous_ce)
 {
+	struct stat_data sd;
+	unsigned int mode;
+	struct object_id oid;
 	struct cache_entry *ce;
 	size_t len;
 	const char *name;
 	const unsigned hashsz = the_hash_algo->rawsz;
-	const char *flagsp = ondisk + offsetof(struct ondisk_cache_entry, data) + hashsz;
+	const char *flagsp;
 	unsigned int flags;
 	size_t copy_len = 0;
 	/*
@@ -1895,6 +1898,24 @@  static struct cache_entry *create_from_disk(struct mem_pool *ce_mem_pool,
 	 */
 	int expand_name_field = version == 4;
 
+	sd.sd_ctime.sec = get_be32(ondisk + offsetof(struct ondisk_cache_entry, ctime)
+							+ offsetof(struct cache_time, sec));
+	sd.sd_ctime.nsec = get_be32(ondisk + offsetof(struct ondisk_cache_entry, ctime)
+							 + offsetof(struct cache_time, nsec));
+	sd.sd_mtime.sec = get_be32(ondisk + offsetof(struct ondisk_cache_entry, mtime)
+							+ offsetof(struct cache_time, sec));
+	sd.sd_mtime.nsec = get_be32(ondisk + offsetof(struct ondisk_cache_entry, mtime)
+							 + offsetof(struct cache_time, nsec));
+	sd.sd_dev   = get_be32(ondisk + offsetof(struct ondisk_cache_entry, dev));
+	sd.sd_ino   = get_be32(ondisk + offsetof(struct ondisk_cache_entry, ino));
+	mode        = get_be32(ondisk + offsetof(struct ondisk_cache_entry, mode));
+	sd.sd_uid   = get_be32(ondisk + offsetof(struct ondisk_cache_entry, uid));
+	sd.sd_gid   = get_be32(ondisk + offsetof(struct ondisk_cache_entry, gid));
+	sd.sd_size  = get_be32(ondisk + offsetof(struct ondisk_cache_entry, size));
+
+	oidread(&oid, (const unsigned char *)ondisk + offsetof(struct ondisk_cache_entry, data));
+	flagsp = ondisk + offsetof(struct ondisk_cache_entry, data) + hashsz;
+
 	/* On-disk flags are just 16 bits */
 	flags = get_be16(flagsp);
 	len = flags & CE_NAMEMASK;
@@ -1934,25 +1955,12 @@  static struct cache_entry *create_from_disk(struct mem_pool *ce_mem_pool,
 	}
 
 	ce = mem_pool__ce_alloc(ce_mem_pool, len);
-
-	ce->ce_stat_data.sd_ctime.sec = get_be32(ondisk + offsetof(struct ondisk_cache_entry, ctime)
-							+ offsetof(struct cache_time, sec));
-	ce->ce_stat_data.sd_mtime.sec = get_be32(ondisk + offsetof(struct ondisk_cache_entry, mtime)
-							+ offsetof(struct cache_time, sec));
-	ce->ce_stat_data.sd_ctime.nsec = get_be32(ondisk + offsetof(struct ondisk_cache_entry, ctime)
-							 + offsetof(struct cache_time, nsec));
-	ce->ce_stat_data.sd_mtime.nsec = get_be32(ondisk + offsetof(struct ondisk_cache_entry, mtime)
-							 + offsetof(struct cache_time, nsec));
-	ce->ce_stat_data.sd_dev   = get_be32(ondisk + offsetof(struct ondisk_cache_entry, dev));
-	ce->ce_stat_data.sd_ino   = get_be32(ondisk + offsetof(struct ondisk_cache_entry, ino));
-	ce->ce_mode  = get_be32(ondisk + offsetof(struct ondisk_cache_entry, mode));
-	ce->ce_stat_data.sd_uid   = get_be32(ondisk + offsetof(struct ondisk_cache_entry, uid));
-	ce->ce_stat_data.sd_gid   = get_be32(ondisk + offsetof(struct ondisk_cache_entry, gid));
-	ce->ce_stat_data.sd_size  = get_be32(ondisk + offsetof(struct ondisk_cache_entry, size));
+	ce->ce_stat_data = sd;
+	ce->ce_mode = mode;
 	ce->ce_flags = flags & ~CE_NAMEMASK;
 	ce->ce_namelen = len;
 	ce->index = 0;
-	oidread(&ce->oid, (const unsigned char *)ondisk + offsetof(struct ondisk_cache_entry, data));
+	oidcpy(&ce->oid, &oid);
 
 	if (expand_name_field) {
 		if (copy_len)