Re: [PATCH 00/32] Split index mode for very large indexes
On Mon, Apr 28, 2014 at 02:18:44PM -0700, Shawn Pearce wrote:
The read penalty is not addressed here, so I still pay 14MB hashing
cost. But that's an easy problem. We could cache the validated index
in a daemon. Whenever git needs to load an index, it pokes the daemon.
The daemon verifies that the on-disk index still has the same
signature, then sends the in-mem index to git. When git updates the
index, it pokes the daemon again to update in-mem index. Next time git
reads the index, it does not have to pay I/O cost any more (actually
it does but the cost is hidden away when you do not have to read it
yet).
If we are going this far, maybe it is worthwhile building a mmap()
region the daemon exports to the git client that holds the in memory
format of the index. Clients would mmap this PROT_READ, MAP_PRIVATE
and can then quickly access the base file information without doing
further validation, or copying the large(ish) data over a pipe.
The below patch implements such a daemon to cache the index. It takes
91ms and 377ms to load a 25MB index with and without the daemon. I use
share memory instead of pipe, but the format is still on disk not
in memory for simplicity. I think we're good even without in memory
format.
The daemon should work on Windows after shm_open and unix socket are
replaced with the equivalents. Then we could cache name-hash in it
too.
With all improvements on (index v4, split index, preload index,
untracked cache, read-cache daemon), git status goes from 1.8s to
0.6s on webkit.git (the CPU is clocked at 800 MHz so this is close to
poor machine case).
Time to convince Junio it's good and push bit by bit to master :)
-- 8 --
diff --git a/.gitignore b/.gitignore
index 70992a4..07e0cb6 100644
--- a/.gitignore
+++ b/.gitignore
@@ -110,6 +110,7 @@
/git-pull
/git-push
/git-quiltimport
+/git-read-cache--daemon
/git-read-tree
/git-rebase
/git-rebase--am
diff --git a/Makefile b/Makefile
index 028749b..98d22de 100644
--- a/Makefile
+++ b/Makefile
@@ -1502,6 +1502,12 @@ ifdef HAVE_DEV_TTY
BASIC_CFLAGS += -DHAVE_DEV_TTY
endif
+ifdef HAVE_SHM
+ BASIC_CFLAGS += -DHAVE_SHM
+ EXTLIBS += -lrt
+ PROGRAM_OBJS += read-cache--daemon.o
+endif
+
ifdef DIR_HAS_BSD_GROUP_SEMANTICS
COMPAT_CFLAGS += -DDIR_HAS_BSD_GROUP_SEMANTICS
endif
diff --git a/cache.h b/cache.h
index 99854c7..5251bda 100644
--- a/cache.h
+++ b/cache.h
@@ -290,10 +290,14 @@ struct index_state {
struct split_index *split_index;
struct cache_time timestamp;
unsigned name_hash_initialized : 1,
+keep_mmap : 1,
+poke_daemon : 1,
initialized : 1;
struct hashmap name_hash;
struct hashmap dir_hash;
unsigned char sha1[20];
+ void *mmap;
+ size_t mmap_size;
};
extern struct index_state the_index;
diff --git a/config.mak.uname b/config.mak.uname
index 23a8803..b6a37e5 100644
--- a/config.mak.uname
+++ b/config.mak.uname
@@ -33,6 +33,7 @@ ifeq ($(uname_S),Linux)
HAVE_PATHS_H = YesPlease
LIBC_CONTAINS_LIBINTL = YesPlease
HAVE_DEV_TTY = YesPlease
+ HAVE_SHM = YesPlease
endif
ifeq ($(uname_S),GNU/kFreeBSD)
NO_STRLCPY = YesPlease
diff --git a/git-compat-util.h b/git-compat-util.h
index f6d3a46..b2116ab 100644
--- a/git-compat-util.h
+++ b/git-compat-util.h
@@ -723,4 +723,12 @@ struct tm *git_gmtime_r(const time_t *, struct tm *);
#define gmtime_r git_gmtime_r
#endif
+#ifndef HAVE_SHM
+static inline int shm_open(const char *path, int flags, int mode)
+{
+ errno = ENOSYS;
+ return -1;
+}
+#endif
+
#endif
diff --git a/read-cache--daemon.c b/read-cache--daemon.c
new file mode 100644
index 000..32a5aa7
--- /dev/null
+++ b/read-cache--daemon.c
@@ -0,0 +1,168 @@
+#include cache.h
+#include sigchain.h
+#include unix-socket.h
+#include split-index.h
+#include pkt-line.h
+
+static char *socket_path;
+static struct strbuf shm_index = STRBUF_INIT;
+static struct strbuf shm_sharedindex = STRBUF_INIT;
+
+static void cleanup_socket(void)
+{
+ if (socket_path)
+ unlink(socket_path);
+ if (shm_index.len)
+ shm_unlink(shm_index.buf);
+ if (shm_sharedindex.len)
+ shm_unlink(shm_sharedindex.buf);
+}
+
+static void cleanup_socket_on_signal(int sig)
+{
+ cleanup_socket();
+ sigchain_pop(sig);
+ raise(sig);
+}
+
+static void share_index(struct index_state *istate, struct strbuf *shm_path)
+{
+ struct strbuf sb = STRBUF_INIT;
+ void *map;
+ int fd;
+
+ strbuf_addf(sb, /git-index-%s, sha1_to_hex(istate-sha1));
+ if (shm_path-len strcmp(sb.buf, shm_path-buf)) {
+ shm_unlink(shm_path-buf);
+ strbuf_reset(shm_path);
+ }
+ fd = shm_open(sb.buf, O_RDWR | O_CREAT | O_TRUNC, 0700);
+ if (fd 0)
+ return;
+ /*
+* We lock the shm in preparation by set its size larger
+
Re: [PATCH 00/32] Split index mode for very large indexes
Duy Nguyen pclo...@gmail.com writes: On Mon, Apr 28, 2014 at 02:18:44PM -0700, Shawn Pearce wrote: The read penalty is not addressed here, so I still pay 14MB hashing cost. But that's an easy problem. We could cache the validated index in a daemon. Whenever git needs to load an index, it pokes the daemon. The daemon verifies that the on-disk index still has the same signature, then sends the in-mem index to git. When git updates the index, it pokes the daemon again to update in-mem index. Next time git reads the index, it does not have to pay I/O cost any more (actually it does but the cost is hidden away when you do not have to read it yet). If we are going this far, maybe it is worthwhile building a mmap() region the daemon exports to the git client that holds the in memory format of the index. Clients would mmap this PROT_READ, MAP_PRIVATE and can then quickly access the base file information without doing further validation, or copying the large(ish) data over a pipe. The below patch implements such a daemon to cache the index. It takes 91ms and 377ms to load a 25MB index with and without the daemon. I use share memory instead of pipe, but the format is still on disk not in memory for simplicity. I think we're good even without in memory format. Interesting ;-). -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 00/32] Split index mode for very large indexes
On 2014-04-28 06:55, Nguyễn Thái Ngọc Duy wrote: From the user point of view, this reduces the writable size of index down to the number of updated files. For example my webkit index v4 is 14MB. With a fresh split, I only have to update an index of 200KB. Every file I touch will add about 80 bytes to that. As long as I don't touch every single tracked file in my worktree, I should not pay penalty for writing 14MB index file on every operation. I played around with these changes a bit and have some questions: * These changes should only affect performance when the index is updated, right? In other words, if I do git status; git status the second git status shouldn't update the index and therefore shouldn't have a noticeable performance improvement relative to Git without these patches. Right? * Do you have any before/after benchmark results you can share? * Are there any benchmark scripts I can use to test it out in my own repositories? * Is there a debug utility I can use to examine the contents of the index and sharedindex.* files in a more human-readable way? I'm asking because in my (very basic) tests I noticed that with the following command: git status; time git status the second git status had an unexpected ~20% performance improvement in my repo relative to a build without your patches. The second git status in the following command also had about a ~20% performance improvement: git status; touch file-in-index; time git status So it seems like the patches did improve performance somewhat, but in ways I wasn't expecting. (I'm not entirely certain my benchmark method is sound.) Thanks, Richard -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 00/32] Split index mode for very large indexes
On Wed, Apr 30, 2014 at 04:48:05PM -0400, Richard Hansen wrote:
I played around with these changes a bit and have some questions:
* These changes should only affect performance when the index is
updated, right? In other words, if I do git status; git status
the second git status shouldn't update the index and therefore
shouldn't have a noticeable performance improvement relative to Git
without these patches. Right?
Yes, provided that other factors in git status give stable numbers
too.
* Do you have any before/after benchmark results you can share?
I did not pay much attention to benchmarking because the index size is
pretty much the deciding factor to write performance (of course too
much computation could add up to that..). But here it is with the 14MB
webkit index, about 182k files. The lines of interest are the first
one (read_cache) and forth (update_index_if_able).
With normal index
pclouds@lanh ~/d/webkit $ time ~/w/git/git status /dev/null
278.382ms gitmodules_config:199 if (read_cache() 0) die(index file
0.004ms cmd_status:1294 read_cache_preload(s.pathspec);
489.275ms cmd_status:1295 refresh_index(the_index, REFRESH_QUIE
6.191ms cmd_status:1299 update_index_if_able(the_index, inde
12.321ms wt_status_collect:616 wt_status_collect_changes_worktree(s)
12.733ms wt_status_collect:621 wt_status_collect_changes_index(s)
98.043ms lazy_init_name_hash:136 { int nr; if (istate-name_hash_initia
915.331ms wt_status_collect:622 wt_status_collect_untracked(s)
real0m1.727s
user0m0.809s
sys 0m0.915s
pclouds@lanh ~/d/webkit $ touch wscript
pclouds@lanh ~/d/webkit $ time ~/w/git/git status /dev/null
276.307ms gitmodules_config:199 if (read_cache() 0) die(index file
0.004ms cmd_status:1294 read_cache_preload(s.pathspec);
504.034ms cmd_status:1295 refresh_index(the_index, REFRESH_QUIE
356.122ms cmd_status:1299 update_index_if_able(the_index, inde
11.870ms wt_status_collect:616 wt_status_collect_changes_worktree(s)
10.077ms wt_status_collect:621 wt_status_collect_changes_index(s)
96.205ms lazy_init_name_hash:136 { int nr; if (istate-name_hash_initia
899.425ms wt_status_collect:622 wt_status_collect_untracked(s)
real0m2.071s
user0m1.115s
sys 0m0.953s
pclouds@lanh ~/d/webkit $ time ~/w/git/git status /dev/null
279.424ms gitmodules_config:199 if (read_cache() 0) die(index file
0.004ms cmd_status:1294 read_cache_preload(s.pathspec);
484.303ms cmd_status:1295 refresh_index(the_index, REFRESH_QUIE
5.288ms cmd_status:1299 update_index_if_able(the_index, inde
13.927ms wt_status_collect:616 wt_status_collect_changes_worktree(s)
12.507ms wt_status_collect:621 wt_status_collect_changes_index(s)
98.220ms lazy_init_name_hash:136 { int nr; if (istate-name_hash_initia
920.985ms wt_status_collect:622 wt_status_collect_untracked(s)
real0m1.731s
user0m0.830s
sys 0m0.897s
And with split index:
pclouds@lanh ~/d/webkit $ time ~/w/git/git update-index --split-index
real0m0.660s
user0m0.601s
sys 0m0.058s
pclouds@lanh ~/d/webkit $ time ~/w/git/git status /dev/null
281.211ms gitmodules_config:199 if (read_cache() 0) die(index file
0.003ms cmd_status:1294 read_cache_preload(s.pathspec);
479.629ms cmd_status:1295 refresh_index(the_index, REFRESH_QUIE
5.489ms cmd_status:1299 update_index_if_able(the_index, inde
12.611ms wt_status_collect:616 wt_status_collect_changes_worktree(s)
11.235ms wt_status_collect:621 wt_status_collect_changes_index(s)
96.086ms lazy_init_name_hash:136 { int nr; if (istate-name_hash_initia
894.489ms wt_status_collect:622 wt_status_collect_untracked(s)
real0m1.697s
user0m0.813s
sys 0m0.881s
pclouds@lanh ~/d/webkit $ touch wscript
pclouds@lanh ~/d/webkit $ time ~/w/git/git status /dev/null
291.411ms gitmodules_config:199 if (read_cache() 0) die(index file
0.003ms cmd_status:1294 read_cache_preload(s.pathspec);
475.144ms cmd_status:1295 refresh_index(the_index, REFRESH_QUIE
24.348ms cmd_status:1299 update_index_if_able(the_index, inde
12.440ms wt_status_collect:616 wt_status_collect_changes_worktree(s)
10.400ms wt_status_collect:621 wt_status_collect_changes_index(s)
97.147ms lazy_init_name_hash:136 { int nr; if (istate-name_hash_initia
907.240ms wt_status_collect:622 wt_status_collect_untracked(s)
real0m1.734s
user0m0.842s
sys 0m0.888s
pclouds@lanh ~/d/webkit $ time ~/w/git/git status /dev/null
281.119ms gitmodules_config:199 if (read_cache() 0) die(index file
0.004ms cmd_status:1294 read_cache_preload(s.pathspec);
479.702ms cmd_status:1295 refresh_index(the_index, REFRESH_QUIE
5.061ms cmd_status:1299 update_index_if_able(the_index, inde
12.220ms wt_status_collect:616 wt_status_collect_changes_worktree(s)
11.408ms wt_status_collect:621 wt_status_collect_changes_index(s)
95.374ms lazy_init_name_hash:136 { int nr; if
[PATCH 00/32] Split index mode for very large indexes
I hinted about it earlier [1]. It now passes the test suite and with a design that I'm happy with (thanks to Junio for a suggestion about the rename problem). From the user point of view, this reduces the writable size of index down to the number of updated files. For example my webkit index v4 is 14MB. With a fresh split, I only have to update an index of 200KB. Every file I touch will add about 80 bytes to that. As long as I don't touch every single tracked file in my worktree, I should not pay penalty for writing 14MB index file on every operation. The read penalty is not addressed here, so I still pay 14MB hashing cost. But that's an easy problem. We could cache the validated index in a daemon. Whenever git needs to load an index, it pokes the daemon. The daemon verifies that the on-disk index still has the same signature, then sends the in-mem index to git. When git updates the index, it pokes the daemon again to update in-mem index. Next time git reads the index, it does not have to pay I/O cost any more (actually it does but the cost is hidden away when you do not have to read it yet). The forth patch is not really necessary. I started out with a different approach that needed that abstraction. But I think it's still a nice thing to keep. The real meat starts from 0017 to 0025. In essence, the new index is more like a journal, where the real index is put away unchanged. Doing this in other implementations should be easy (at least the reading part) and with small code change. The whole index format is retained. All you need is to read a new extension that contains two ewah-bitmaps and apply the changes to create the final index. This is a preparation step for my untracked file cache. With writing (and later on reading) index becoming cheap, I can start to put more things in there. [1] http://thread.gmane.org/gmane.comp.version-control.git/246471/focus=247031 Nguyễn Thái Ngọc Duy (32): ewah: fix constness of ewah_read_mmap ewah: delete unused ewah_read_mmap_native declaration sequencer: do not update/refresh index if the lock cannot be held read-cache: new API write_locked_index instead of write_index/write_cache read-cache: relocate and unexport commit_locked_index() read-cache: store in-memory flags in the first 12 bits of ce_flags read-cache: be strict about changed in remove_marked_cache_entries() read-cache: be specific what part of the index has changed update-index: be specific what part of the index has changed resolve-undo: be specific what part of the index has changed unpack-trees: be specific what part of the index has changed cache-tree: mark istate-cache_changed on cache tree invalidation cache-tree: mark istate-cache_changed on cache tree update cache-tree: mark istate-cache_changed on prime_cache_tree() entry.c: update cache_changed if refresh_cache is set in checkout_entry() read-cache: save index SHA-1 after reading read-cache: split-index mode read-cache: mark new entries for split index read-cache: save deleted entries in split index read-cache: mark updated entries for split index split-index: the writing part split-index: the reading part split-index: do not invalidate cache-tree at read time split-index: strip pathname of on-disk replaced entries update-index: new options to enable/disable split index mode update-index --split-index: do not split if $GIT_DIR is read only rev-parse: add --shared-index-path to get shared index path read-tree: force split-index mode off on --index-output read-tree: note about dropping split-index mode or index version read-cache: force split index mode with GIT_TEST_SPLIT_INDEX t2104: make sure split index mode is off for the version test t1700: new tests for split-index mode -- 1.9.1.346.ga2b5940 -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 00/32] Split index mode for very large indexes
On Mon, Apr 28, 2014 at 3:55 AM, Nguyễn Thái Ngọc Duy pclo...@gmail.com wrote: I hinted about it earlier [1]. It now passes the test suite and with a design that I'm happy with (thanks to Junio for a suggestion about the rename problem). From the user point of view, this reduces the writable size of index down to the number of updated files. For example my webkit index v4 is 14MB. With a fresh split, I only have to update an index of 200KB. Every file I touch will add about 80 bytes to that. As long as I don't touch every single tracked file in my worktree, I should not pay penalty for writing 14MB index file on every operation. This is a very welcome type of improvement. I am however concerned about the complexity of the format employed. Why do we need two EWAH bitmaps in the new index? Why isn't this just a pair of sorted files that are merge-joined at read, with records in $GIT_DIR/index taking priority over same-named records in $GIT_DIR/sharedindex.$SHA1? Deletes could be marked with a bit or an all zero metadata record. The read penalty is not addressed here, so I still pay 14MB hashing cost. But that's an easy problem. We could cache the validated index in a daemon. Whenever git needs to load an index, it pokes the daemon. The daemon verifies that the on-disk index still has the same signature, then sends the in-mem index to git. When git updates the index, it pokes the daemon again to update in-mem index. Next time git reads the index, it does not have to pay I/O cost any more (actually it does but the cost is hidden away when you do not have to read it yet). If we are going this far, maybe it is worthwhile building a mmap() region the daemon exports to the git client that holds the in memory format of the index. Clients would mmap this PROT_READ, MAP_PRIVATE and can then quickly access the base file information without doing further validation, or copying the large(ish) data over a pipe. Junio had some other great ideas for improving the index on really large trees. Maybe I should let him comment since they are really his ideas. Something about not even checking out most files, storing most subtrees as just a tree entry in the index. E.g. if you are a bad developer and never touch the t/ subdirectory then that is stored as just t and the SHA-1 of the t tree, rather than the recursively exploded list of the test directory. -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 00/32] Split index mode for very large indexes
Nguyễn Thái Ngọc Duy pclo...@gmail.com writes: The read penalty is not addressed here, so I still pay 14MB hashing cost. Hmm, yeah, the cost for verify_hdr() would still matter, and presumably you would be hashing the additional 200kB to validate the smaller changes since the base file to give users the same level of protection against corruption. Doing this in other implementations should be easy (at least the reading part) and with small code change. The whole index format is retained. All you need is to read a new extension that contains two ewah-bitmaps and apply the changes to create the final index. Why bitmaps, though? Naïvely I would have expected you to read from two sorted streams and have the transaction log override the base. Intrigued to find it out... -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 00/32] Split index mode for very large indexes
On Tue, Apr 29, 2014 at 4:18 AM, Shawn Pearce spea...@spearce.org wrote: On Mon, Apr 28, 2014 at 3:55 AM, Nguyễn Thái Ngọc Duy pclo...@gmail.com wrote: I hinted about it earlier [1]. It now passes the test suite and with a design that I'm happy with (thanks to Junio for a suggestion about the rename problem). From the user point of view, this reduces the writable size of index down to the number of updated files. For example my webkit index v4 is 14MB. With a fresh split, I only have to update an index of 200KB. Every file I touch will add about 80 bytes to that. As long as I don't touch every single tracked file in my worktree, I should not pay penalty for writing 14MB index file on every operation. This is a very welcome type of improvement. I am however concerned about the complexity of the format employed. Why do we need two EWAH bitmaps in the new index? Why isn't this just a pair of sorted files that are merge-joined at read, with records in $GIT_DIR/index taking priority over same-named records in $GIT_DIR/sharedindex.$SHA1? Deletes could be marked with a bit or an all zero metadata record. With the bitmaps, I know the exact position to replace or delete an entry. Merge sort works, but I would need to walk through all entries in both indexes to compare entry name and stage, a bit costly in my opinion. And if you look at the format description in patch 0017, I store the replaced entries without their names to save a bit more space. EWAH is just an implementation detail. A straightforward bitmap should work fine (25kb for 200k entries seem reasonable). -- Duy -- To unsubscribe from this list: send the line unsubscribe git in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
