Re: I'm a total push-over..

Linus Torvalds [off-list ref] writes:

Basically, I dislike having two copies of the same data. If something can 
be computed from something else, then only the original data should exist, 
and the other thing should be recomputed.

Yes, I agree with that in principle. Storing computable values
makes sense only when it is expensive to recompute.  We did not
have cache-tree for quite a long time until you noticed that it
was rather expensive and wasteful to recompute tree objects from
unchanged parts of the index every time.

It's the same argument; when the hashing performance starts to
become noticeable, we can think about storing and reusing it,
not before.

I did consider doing the indexing only on demand, and we can certainly 
simply just "turn it off" when we know it's never going to get used (ie 
"git ls-files"). So in that sense, it's easy to get rid of the overhead, 
but it didn't really seem like the conceptual complexity (even if it's 
just a couple of lines) is really worth it. It's not like git ls-files is 
really performance-critical anyway.

Yes, ls-files is cheap.  So is lstat(2) on Linux.  It only
matters when you do it many many times.

In any case, the change does not look too bad.  The best time
(real) of running git-ls-files in the kernel repository on my
box is 0.010s vs 0.011s (10% improvement, heh!, which is the
same as the master version) and empty commit is both 0.082s (no
change).

-- >8 --
[PATCH] lazy index hashing

This delays the hashing of index names until it becomes necessary for
the first time.

Signed-off-by: Junio C Hamano <redacted>
---
 cache.h      |    1 +
 read-cache.c |   26 +++++++++++++++++++++++---
 2 files changed, 24 insertions(+), 3 deletions(-)

diff --git a/cache.h b/cache.h
index 409738c..e4aeff0 100644
--- a/cache.h
+++ b/cache.h

@@ -191,6 +191,7 @@ struct index_state {
 	struct cache_tree *cache_tree;
 	time_t timestamp;
 	void *alloc;
+	unsigned name_hash_initialized : 1;
 	struct hash_table name_hash;
 };
 

diff --git a/read-cache.c b/read-cache.c
index 9477c0b..e45f4b3 100644
--- a/read-cache.c
+++ b/read-cache.c

@@ -34,12 +34,11 @@ static unsigned int hash_name(const char *name, int namelen)
 	return hash;
 }
 
-static void set_index_entry(struct index_state *istate, int nr, struct cache_entry *ce)
+static void hash_index_entry(struct index_state *istate, struct cache_entry *ce)
 {
 	void **pos;
 	unsigned int hash = hash_name(ce->name, ce_namelen(ce));
 
-	istate->cache[nr] = ce;
 	pos = insert_hash(hash, ce, &istate->name_hash);
 	if (pos) {
 		ce->next = *pos;

@@ -47,6 +46,24 @@ static void set_index_entry(struct index_state *istate, int nr, struct cache_ent
 	}
 }
 
+static void lazy_init_name_hash(struct index_state *istate)
+{
+	int nr;
+
+	if (istate->name_hash_initialized)
+		return;
+	for (nr = 0; nr < istate->cache_nr; nr++)
+		hash_index_entry(istate, istate->cache[nr]);
+	istate->name_hash_initialized = 1;
+}
+
+static void set_index_entry(struct index_state *istate, int nr, struct cache_entry *ce)
+{
+	istate->cache[nr] = ce;
+	if (istate->name_hash_initialized)
+		hash_index_entry(istate, ce);
+}
+
 /*
  * We don't actually *remove* it, we can just mark it invalid so that
  * we won't find it in lookups.

@@ -75,7 +92,10 @@ static void replace_index_entry(struct index_state *istate, int nr, struct cache
 int index_name_exists(struct index_state *istate, const char *name, int namelen)
 {
 	unsigned int hash = hash_name(name, namelen);
-	struct cache_entry *ce = lookup_hash(hash, &istate->name_hash);
+	struct cache_entry *ce;
+
+	lazy_init_name_hash(istate);
+	ce = lookup_hash(hash, &istate->name_hash);
 
 	while (ce) {
 		if (!(ce->ce_flags & CE_UNHASHED)) {

-- 
1.5.4.rc4.14.g6fc74

Hi,

On Tue, 22 Jan 2008, Junio C Hamano wrote:

Linus Torvalds [off-list ref] writes:

quoted

Basically, I dislike having two copies of the same data. If something 
can be computed from something else, then only the original data 
should exist, and the other thing should be recomputed.

Yes, I agree with that in principle. Storing computable values makes 
sense only when it is expensive to recompute.  We did not have 
cache-tree for quite a long time until you noticed that it was rather 
expensive and wasteful to recompute tree objects from unchanged parts of 
the index every time.

It's the same argument; when the hashing performance starts to become 
noticeable, we can think about storing and reusing it, not before.

I fully expect it to be noticable with that UTF-8 "normalisation".  But 
then, the infrastructure is there, and whoever has an itch to scratch...

Ciao,
Dscho

On Wed, 23 Jan 2008, Johannes Schindelin wrote:

I fully expect it to be noticable with that UTF-8 "normalisation".  But 
then, the infrastructure is there, and whoever has an itch to scratch...

Actually, it's going to be totally invisible even with UTF-8 
normalization, because we're going to do it sanely.

And by "sanely" I mean just having the code test the high bit, and using 
US-ASCII as-is (possibly with that " & ~0x20 " thing to ignore case in 
it).

End result: practically all projects will never notice anything at all for 
99.9% of all files. One extra well-predicted branch, and a few more hash 
collissions for cases where you have both "Makefile" and "makefile" etc.

Doing names with *lots* of UTF-8 characters will be rather slower. It's 
still not horrible to do if you do it the smart way, though. In fact, it's 
pretty simple, just a few table lookups (one to find the NFD form, one to 
do the upcasing).

And yes, for hashing, it makes sense to turn things into NFD because it's 
generally simpler, but the point is that you really don't actually modify 
the name itself at all, you just hash things (or compare things) character 
by expanded character.

IOW, only a total *moron* does Unicode name comparisons with

	strcmp(convert_to_nfd(a), convert_to_nfd(b));

which is essentially what Apple does. It's quite possible to do

	utf8_nfd_strcmp(a,b)

and (a) do it tons and tons faster and (b) never have to modify the 
strings themselves. Same goes (even more) for hashing.

			Linus

Hi,

On Wed, 23 Jan 2008, Linus Torvalds wrote:

On Wed, 23 Jan 2008, Johannes Schindelin wrote:

quoted

I fully expect it to be noticable with that UTF-8 "normalisation".  
But then, the infrastructure is there, and whoever has an itch to 
scratch...

Actually, it's going to be totally invisible even with UTF-8 
normalization, because we're going to do it sanely.

And by "sanely" I mean just having the code test the high bit, and using 
US-ASCII as-is (possibly with that " & ~0x20 " thing to ignore case in 
it).

End result: practically all projects will never notice anything at all for 
99.9% of all files. One extra well-predicted branch, and a few more hash 
collissions for cases where you have both "Makefile" and "makefile" etc.

Well, that's the point, to avoid having both "Makefile" and "makefile" in 
your repository when you are on case-challenged filesystems, right?

Doing names with *lots* of UTF-8 characters will be rather slower. It's 
still not horrible to do if you do it the smart way, though. In fact, 
it's pretty simple, just a few table lookups (one to find the NFD form, 
one to do the upcasing).

And yes, for hashing, it makes sense to turn things into NFD because 
it's generally simpler, but the point is that you really don't actually 
modify the name itself at all, you just hash things (or compare things) 
character by expanded character.

IOW, only a total *moron* does Unicode name comparisons with

	strcmp(convert_to_nfd(a), convert_to_nfd(b));

which is essentially what Apple does.

Heh, indeed that is what I would have done as an initial step (out of 
laziness).

It's quite possible to do

	utf8_nfd_strcmp(a,b)

and (a) do it tons and tons faster and (b) never have to modify the 
strings themselves. Same goes (even more) for hashing.

Okay.  Point taken.

But I really hope that you are not proposing to use the case-ignoring 
hash when we are _not_ on a case-challenged filesystem...

Ciao,
Dscho

On Wed, 23 Jan 2008, Johannes Schindelin wrote:

quoted

End result: practically all projects will never notice anything at all for 
99.9% of all files. One extra well-predicted branch, and a few more hash 
collissions for cases where you have both "Makefile" and "makefile" etc.

Well, that's the point, to avoid having both "Makefile" and "makefile" in 
your repository when you are on case-challenged filesystems, right?

Right. But what I'm saying is that this is *really* cheap to test for for 
US-ASCII-only characters, and if only 0.1% of all filenames have unicode 
in them, the fact that they are much mroe expensive isn't even going to be 
noticeable. Except for some very odd-ball environments.

quoted

It's quite possible to do

	utf8_nfd_strcmp(a,b)

and (a) do it tons and tons faster and (b) never have to modify the 
strings themselves. Same goes (even more) for hashing.

Okay.  Point taken.

Note that one reason the above is tons faster is that even with complex 
unicode, the *common* case is going to be that the names match with a 
binary compare.

But I really hope that you are not proposing to use the case-ignoring 
hash when we are _not_ on a case-challenged filesystem...

I actually suspect that we could, and nobody will notice. The hash would 
cause a few more collissions, but not so you'd know.

And the thing is, people who work with other people who are on 
case-challenged systems would still want to have the case-insenstive 
compare too - although it should just warn, not actually "work".

			Linus

On Wed, 23 Jan 2008, Linus Torvalds wrote:

quoted

But I really hope that you are not proposing to use the case-ignoring 
hash when we are _not_ on a case-challenged filesystem...

I actually suspect that we could, and nobody will notice. The hash would 
cause a few more collissions, but not so you'd know.

To clarify: the thing I want to point out that the decision to *hash* the 
filenames in a case-insensitive hash, is very different from the decision 
to then *compare* the filenames when traversing the hash with a 
case-insensitive compare.

And this difference is actually very important. Hashing things together 
that are "equivalent" according to any random rule is what makes it 
possible to then *check* for equivalence cheaply (because you only need to 
make the potentially expensive check with the subset of cases where it 
might trigger), but it in no way forces you to actually recode or mangle 
or compare things equivalently.

In fact, I'd argue that this is what HFS+ did wrong in the first place: 
they had stupid/incompetent people who didn't understand about this, so 
they normalized the string *before* the hashing rather than as part of the 
hash itself, and thus actually corrupt the string itself.

So what you can do (and I'd argue that we do) is to have a hash that can 
handle almost arbitrary input, but then never corrupt the filename, and 
always compare exactly by default.

Then, depending on a config option, we can decide to change the compare so 
that equivalent (according to whatever rule) filenames either cause a 
warning (people on sane filesystems, but working with people who aren't), 
or are silently considered the same file (people on insane filesystems).

			Linus

Linus Torvalds wrote:
[snip]

So what you can do (and I'd argue that we do) is to have a hash that can 
handle almost arbitrary input, but then never corrupt the filename, and 
always compare exactly by default.

In general, there may be a large number of comparison function options
that git will eventually support, and they will likely not all form a
single chain of increasing "strictness".

Given that the hash values aren't even being stored on disk (and if they
were, a simple approach of also storing an identifier for the hash
function to know whether they stored values are still valid could be
used), having a chain of increasingly "strict" comparison functions and
using a hash function that corresponds to the least strict one is useful
for exactly one reason: giving (possibly several different levels of)
non-fatal warnings for various types of duplicates.

But since multiple hash functions will be needed anyway to support
different notions of case-insensitivity, if the warning is not enabled,
there is no reason to use a case-insensitive hash function with a
byte-exact comparison.

-- 
Jeremy Maitin-Shepard

Hi,

On Fri, 25 Jan 2008, Jeremy Maitin-Shepard wrote:

But since multiple hash functions will be needed anyway to support 
different notions of case-insensitivity, if the warning is not enabled, 
there is no reason to use a case-insensitive hash function with a 
byte-exact comparison.

No, only multiple compare functions will be needed.  The hash function can 
be built in such a manner that it guarantees that file names being equal 
with _any_ of the compare functions fall into the same bucket.

The upside of such a hash function: less code to maintain.

Hth,
Dscho