git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH/RFC v2 1/2] Strip namelen out of ce_flags into a ce_namelen field

From
Junio C Hamano <gitster@pobox.com>
Date
Jul 9, 2012, 04:59 UTC
Message-ID
<7vy5mtlebz.fsf@alter.siamese.dyndns.org>
In-Reply-To
<1341590850-15653-2-git-send-email-t.gummerer@gmail.com>
Thomas Gummerer <t.gummerer@gmail.com> writes:
Show 5 quoted lines
> Strip the name length from the ce_flags field and move it
> into its own ce_namelen field in struct cache_entry. This
> will both give us a tiny bit of a performance enhancement
> when working with long pathnames and is part of the
> refactoring for the index-v5 file format.
Careful.

I do not mind moving name length out of low bits of ce_flags in principle, but if you claim this helps performance, you need to substanticate it.

FYI, the current layout was designed for performance to take advantage of the fact that most paths are short (among 39k paths in the kernel tree, the longest seems to be 80 bytes long) and using strlen() is rarely needed (the code even skips the first 4k bytes when it has to use strlen()). It of course also shaves a few hundred kilobytes of memory necessary to hold the length separately in cache entries).

> Index-v5 won't store the name length in the on disk index
> file, so storing it in the flags wouldn't make sense for
> index-v5.

I think this split could make sense even without a new on-disk format.

On the other hand, even if the result of this patch were to prove undesirable, it is still possible for the read_index code for v5 format to convert from its ondisk_cache_entry (which does not have length anywhere) to the canonical cache_entry struct (which stores length for common short path names in lower bits of flags field), and write_index code could do the reverse.

Because of the above two points, what index-v5 has or does not have is mostly immaterial when judging this patch, unless such a conversion has very high cost.

> It also enhances readability, by making it more clear what
> is a flag, and where the length is stored and make it clear
> which functions use stages in comparisions and which only
> use the length.

That can be true, but if we were to go this route, the patch should be able to make CE_NAMEMASK totally private to the codepath that reads and writes v2/v3/v4 format and nowhere else. The ce_flags field in "struct cache_entry" that is visible to everybody from cache.h shouldn't need the padding of 12-low bits that is not used (I think CE_STAGESHIFT could even become 0, even though I do not see an immediate need for such a change).

Shouldn't "struct ondisk_cache_entry" in read-cache.c the only place that need to know about this old layout, no?

Show 9 quoted lines
> diff --git a/builtin/apply.c b/builtin/apply.c
> index dda9ea0..10f83fc 100644
> --- a/builtin/apply.c
> +++ b/builtin/apply.c
> @@ -3502,7 +3502,8 @@ static void add_index_file(const char *path, unsigned mode, void *buf, unsigned
>  	ce = xcalloc(1, ce_size);
>  	memcpy(ce->name, path, namelen);
>  	ce->ce_mode = create_ce_mode(mode);
> -	ce->ce_flags = namelen;

I think this should have been create_ce_flags(namelen, 0) originally, so I would prefer the new code to spell it as create_ce_flags(0).

> +	ce->ce_flags = 0;
> +	ce->ce_namelen = namelen;
Show 10 quoted lines
> diff --git a/builtin/blame.c b/builtin/blame.c
> index 24d3dd5..e181368 100644
> --- a/builtin/blame.c
> +++ b/builtin/blame.c
> @@ -2153,7 +2153,8 @@ static struct commit *fake_working_tree_commit(struct diff_options *opt,
>  	ce = xcalloc(1, size);
>  	hashcpy(ce->sha1, origin->blob_sha1);
>  	memcpy(ce->name, path, len);
> -	ce->ce_flags = create_ce_flags(len, 0);
> +	ce->ce_flags = 0;

Likewise. I think it is more in line with your "making it more clear" if you said create_ce_flags(0) here. I won't repeat this for the remainder of the patch where a bare number is stored without using create_ce_flags(stage).

> +#define ce_namelen(ce) ((ce)->ce_namelen)
Good.
Show 5 quoted lines
> @@ -448,6 +440,7 @@ extern int discard_index(struct index_state *);
>  extern int unmerged_index(const struct index_state *);
>  extern int verify_path(const char *path);
>  extern struct cache_entry *index_name_exists(struct index_state *istate, const char *name, int namelen, int igncase);
> +extern int index_name_stage_pos(const struct index_state *, const char *name, int stage, int namelen);

The name string and its length form a pair; keep them next to each other (i.e. swap stage and namelen).

Show 5 quoted lines
> @@ -857,6 +850,7 @@ extern int validate_headref(const char *ref);
>  extern int base_name_compare(const char *name1, int len1, int mode1, const char *name2, int len2, int mode2);
>  extern int df_name_compare(const char *name1, int len1, int mode1, const char *name2, int len2, int mode2);
>  extern int cache_name_compare(const char *name1, int len1, const char *name2, int len2);
> +extern int cache_name_stage_compare(const char *name1, int stage1, int len1, const char *name2, int stage2, int len2);
Likewise.
Show 15 quoted lines
> diff --git a/read-cache.c b/read-cache.c
> index ef355cc..ea75c89 100644
> --- a/read-cache.c
> +++ b/read-cache.c
> @@ -395,10 +395,8 @@ int df_name_compare(const char *name1, int len1, int mode1,
>  	return c1 - c2;
>  }
>  
> -int cache_name_compare(const char *name1, int flags1, const char *name2, int flags2)
> +int cache_name_stage_compare(const char *name1, int stage1, int len1, const char *name2, int stage2, int len2)
>  {
> -	int len1 = flags1 & CE_NAMEMASK;
> -	int len2 = flags2 & CE_NAMEMASK;
>  	int len = len1 < len2 ? len1 : len2;
>  	int cmp;

Isn't this a _BUGFIX_? It appears to me that the original code would only compare the first 4k bytes and ignore the rest, if two cache entries, both with overlong names, are compared. Care to come up with a test case to demonstrate the breakage and a bugfix without the remainder of this patch, to be applied to 'master' and older maintenance releases? Perpahs something along the lines of this:

 read-cache.c | 14 +++++++++-----
 1 file changed, 9 insertions(+), 5 deletions(-)
diff --git a/read-cache.c b/read-cache.c
index 1df6adf..d226e5e 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -397,11 +397,15 @@ int df_name_compare(const char *name1, int len1, int mode1,
 
 int cache_name_compare(const char *name1, int flags1, const char *name2, int flags2)
 {
-	int len1 = flags1 & CE_NAMEMASK;
-	int len2 = flags2 & CE_NAMEMASK;
-	int len = len1 < len2 ? len1 : len2;
-	int cmp;
-
+	int len1, len2, len, cmp;
+
+	len1 = flags1 & CE_NAMEMASK;
+	if (len1 >= CE_NAMEMASK)
+		len1 = strlen(name1)
+	len2 = flags2 & CE_NAMEMASK;
+	if (len2 >= CE_NAMEMASK)
+		len2 = strlen(name2);
+	len = len1 < len2 ? len1 : len2;
 	cmp = memcmp(name1, name2, len);
 	if (cmp)
 		return cmp;

Pros and cons of adding a new ce_namelen field can be discussed
separately and built on top of such a bugfix.

> @@ -1319,7 +1324,8 @@ static struct cache_entry *cache_entry_from_ondisk(struct ondisk_cache_entry *on
>  	ce->ce_uid   = ntoh_l(ondisk->uid);
>  	ce->ce_gid   = ntoh_l(ondisk->gid);
>  	ce->ce_size  = ntoh_l(ondisk->size);
> -	ce->ce_flags = flags;
> +	ce->ce_flags = flags & ~CE_NAMEMASK;
> +	ce->ce_namelen = len;

OK, so this part wants to make (ce->ce_flags & CE_NAMEMASK) MBZ
(must be zero), which is a step in the right direction (provided
that the creation of ce_namelen field is the right thing to do, that
is).

> @@ -1743,7 +1749,7 @@ int write_index(struct index_state *istate, int newfd)
>  {
>  	git_SHA_CTX c;
>  	struct cache_header hdr;
> -	int i, err, removed, extended, hdr_version;
> +	int i, err, removed, extended, hdr_version, len;
>  	struct cache_entry **cache = istate->cache;
>  	int entries = istate->cache_nr;
>  	struct stat st;
> @@ -1759,6 +1765,11 @@ int write_index(struct index_state *istate, int newfd)
>  			extended++;
>  			cache[i]->ce_flags |= CE_EXTENDED;
>  		}
> +		if (cache[i]->ce_namelen >= CE_NAMEMASK)
> +			len = CE_NAMEMASK;
> +		else
> +			len = cache[i]->ce_namelen;
> +		cache[i]->ce_flags |= len;
>  	}

This is extremely dubious.  Didn't the earlier hunk at 1319 declare
that low bits of ce_flags is MBZ?  I would understand it if
something like this is done to ondisk in ce_write_entry(), but I do
not think it is consistent to contaminate the low bits of ce_flags
here while your cache_entry_from_ondisk() clears them.
Previous: Thomas GummererNext: Thomas Gummerer
Message 8 of 18 in “Replace ce_namelen() with a ce_namelen field”
  1. Replace ce_namelen() with a ce_namelen fieldThomas Gummerer, Jul 4, 2012
  2. Thomas RastJul 4, 2012
  3. Nguyen Thai Ngoc DuyJul 4, 2012
  4. Nguyen Thai Ngoc DuyJul 4, 2012
  5. Junio C HamanoJul 4, 2012
  6. Introduction of a ce_namelen fieldThomas Gummerer, Jul 6, 2012
  7. 1/2 Strip namelen out of ce_flags into a ce_namelen fieldThomas Gummerer, Jul 6, 2012
  8. Junio C HamanoJul 9, 2012
  9. 0/3 Introduction of a ce_namelen fieldThomas Gummerer, Jul 11, 2012
  10. 1/3 read-cache.c: Handle long filenames correctlyThomas Gummerer, Jul 11, 2012
  11. Nguyen Thai Ngoc DuyJul 11, 2012
  12. Junio C HamanoJul 11, 2012
  13. 2/3 Strip namelen out of ce_flags into a ce_namelen fieldThomas Gummerer, Jul 11, 2012
  14. 3/3 Replace strlen() with ce_namelen()Thomas Gummerer, Jul 11, 2012
  15. Junio C HamanoJul 11, 2012
  16. Junio C HamanoJul 11, 2012
  17. 2/2 Replace strlen() with ce_namelen()Thomas Gummerer, Jul 6, 2012
  18. Junio C HamanoJul 9, 2012

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.