aboutsummaryrefslogtreecommitdiff
path: root/cache.h
diff options
context:
space:
mode:
authorLinus Torvalds <torvalds@linux-foundation.org>2008-01-22 18:41:14 -0800
committerJunio C Hamano <gitster@pobox.com>2008-01-22 21:46:30 -0800
commitcf558704fb68514a820e3666968967c900e0fd29 (patch)
treead48d2aa679b9d6ea5c6db2f05831592cf4f7c1f /cache.h
parent6d91da6d3c170d026f2d7f79bbd7b657a6908cc8 (diff)
downloadgit-cf558704fb68514a820e3666968967c900e0fd29.tar.gz
git-cf558704fb68514a820e3666968967c900e0fd29.tar.xz
Create pathname-based hash-table lookup into index
This creates a hash index of every single file added to the index. Right now that hash index isn't actually used for much: I implemented a "cache_name_exists()" function that uses it to efficiently look up a filename in the index without having to do the O(logn) binary search, but quite frankly, that's not why this patch is interesting. No, the whole and only reason to create the hash of the filenames in the index is that by modifying the hash function, you can fairly easily do things like making it always hash equivalent names into the same bucket. That, in turn, means that suddenly questions like "does this name exist in the index under an _equivalent_ name?" becomes much much cheaper. Guiding principles behind this patch: - it shouldn't be too costly. In fact, my primary goal here was to actually speed up "git commit" with a fully populated kernel tree, by being faster at checking whether a file already existed in the index. I did succeed, but only barely: Best before: [torvalds@woody linux]$ time git commit > /dev/null real 0m0.255s user 0m0.168s sys 0m0.088s Best after: [torvalds@woody linux]$ time ~/git/git commit > /dev/null real 0m0.233s user 0m0.144s sys 0m0.088s so some things are actually faster (~8%). Caveat: that's really the best case. Other things are invariably going to be slightly slower, since we populate that index cache, and quite frankly, few things really use it to look things up. That said, the cost is really quite small. The worst case is probably doing a "git ls-files", which will do very little except puopulate the index, and never actually looks anything up in it, just lists it. Before: [torvalds@woody linux]$ time git ls-files > /dev/null real 0m0.016s user 0m0.016s sys 0m0.000s After: [torvalds@woody linux]$ time ~/git/git ls-files > /dev/null real 0m0.021s user 0m0.012s sys 0m0.008s and while the thing has really gotten relatively much slower, we're still talking about something almost unmeasurable (eg 5ms). And that really should be pretty much the worst case. So we lose 5ms on one "benchmark", but win 22ms on another. Pick your poison - this patch has the advantage that it will _likely_ speed up the cases that are complex and expensive more than it slows down the cases that are already so fast that nobody cares. But if you look at relative speedups/slowdowns, it doesn't look so good. - It should be simple and clean The code may be a bit subtle (the reasons I do hash removal the way I do etc), but it re-uses the existing hash.c files, so it really is fairly small and straightforward apart from a few odd details. Now, this patch on its own doesn't really do much, but I think it's worth looking at, if only because if done correctly, the name hashing really can make an improvement to the whole issue of "do we have a filename that looks like this in the index already". And at least it gets real testing by being used even by default (ie there is a real use-case for it even without any insane filesystems). NOTE NOTE NOTE! The current hash is a joke. I'm ashamed of it, I'm just not ashamed of it enough to really care. I took all the numbers out of my nether regions - I'm sure it's good enough that it works in practice, but the whole point was that you can make a really much fancier hash that hashes characters not directly, but by their upper-case value or something like that, and thus you get a case-insensitive hash, while still keeping the name and the index itself totally case sensitive. Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Diffstat (limited to 'cache.h')
-rw-r--r--cache.h6
1 files changed, 6 insertions, 0 deletions
diff --git a/cache.h b/cache.h
index 3a47cdc9d..409738ca6 100644
--- a/cache.h
+++ b/cache.h
@@ -3,6 +3,7 @@
#include "git-compat-util.h"
#include "strbuf.h"
+#include "hash.h"
#include SHA1_HEADER
#include <zlib.h>
@@ -109,6 +110,7 @@ struct ondisk_cache_entry {
};
struct cache_entry {
+ struct cache_entry *next;
unsigned int ce_ctime;
unsigned int ce_mtime;
unsigned int ce_dev;
@@ -131,6 +133,7 @@ struct cache_entry {
#define CE_UPDATE (0x10000)
#define CE_REMOVE (0x20000)
#define CE_UPTODATE (0x40000)
+#define CE_UNHASHED (0x80000)
static inline unsigned create_ce_flags(size_t len, unsigned stage)
{
@@ -188,6 +191,7 @@ struct index_state {
struct cache_tree *cache_tree;
time_t timestamp;
void *alloc;
+ struct hash_table name_hash;
};
extern struct index_state the_index;
@@ -211,6 +215,7 @@ extern struct index_state the_index;
#define refresh_cache(flags) refresh_index(&the_index, (flags), NULL, NULL)
#define ce_match_stat(ce, st, options) ie_match_stat(&the_index, (ce), (st), (options))
#define ce_modified(ce, st, options) ie_modified(&the_index, (ce), (st), (options))
+#define cache_name_exists(name, namelen) index_name_exists(&the_index, (name), (namelen))
#endif
enum object_type {
@@ -297,6 +302,7 @@ extern int read_index_from(struct index_state *, const char *path);
extern int write_index(struct index_state *, int newfd);
extern int discard_index(struct index_state *);
extern int verify_path(const char *path);
+extern int index_name_exists(struct index_state *istate, const char *name, int namelen);
extern int index_name_pos(struct index_state *, const char *name, int namelen);
#define ADD_CACHE_OK_TO_ADD 1 /* Ok to add */
#define ADD_CACHE_OK_TO_REPLACE 2 /* Ok to replace file/directory */