{"push_id":2794557476,"size":5,"distinct_size":0,"ref":"refs/heads/nd/unpack-trees-with-cache-tree","head":"43fac1154fe9466d944defc3851a20e961d67df9","before":"7d549be06c44bca37ca641bd49f72f4d2abbd77a","commits":[{"sha":"a192faf79e62e75565bd6e31ff617061cc3c04cb","author":{"name":"Nguyễn Thái Ngọc Duy","email":"024f400cd820cb2ddbe54c7fecfd01e45f30bb96@gmail.com"},"message":"trace.h: support nested performance tracing\n\nPerformance measurements are listed right now as a flat list, which is\nfine when we measure big blocks. But when we start adding more and\nmore measurements, some of them could be just part of a bigger\nmeasurement and a flat list gives a wrong impression that they are\nexecuted at the same level instead of nested.\n\nAdd trace_performance_enter() and trace_performance_leave() to allow\nindent these nested measurements. For now it does not help much\nbecause the only nested thing is (lazy) name hash initialization\n(e.g. called in diff-index from \"git status\"). This will help more\nbecause I'm going to add some more tracing that's actually nested.\n\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\nSigned-off-by: Junio C Hamano <gitster@pobox.com>","distinct":false,"url":"https://api.github.com/repos/gitgitgadget/git/commits/a192faf79e62e75565bd6e31ff617061cc3c04cb"},{"sha":"9afe7c488ae65e2690737323f049edfe3e1439bd","author":{"name":"Nguyễn Thái Ngọc Duy","email":"024f400cd820cb2ddbe54c7fecfd01e45f30bb96@gmail.com"},"message":"unpack-trees: add performance tracing\n\nWe're going to optimize unpack_trees() a bit in the following\npatches. Let's add some tracing to measure how long it takes before\nand after. This is the baseline (\"git checkout -\" on webkit.git, 275k\nfiles on worktree)\n\n    performance: 0.056651714 s:  read cache .git/index\n    performance: 0.183101080 s:  preload index\n    performance: 0.008584433 s:  refresh index\n    performance: 0.633767589 s:   traverse_trees\n    performance: 0.340265448 s:   check_updates\n    performance: 0.381884638 s:   cache_tree_update\n    performance: 1.401562947 s:  unpack_trees\n    performance: 0.338687914 s:  write index, changed mask = 2e\n    performance: 0.411927922 s:    traverse_trees\n    performance: 0.000023335 s:    check_updates\n    performance: 0.423697246 s:   unpack_trees\n    performance: 0.423708360 s:  diff-index\n    performance: 2.559524127 s: git command: git checkout -\n\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\nSigned-off-by: Junio C Hamano <gitster@pobox.com>","distinct":false,"url":"https://api.github.com/repos/gitgitgadget/git/commits/9afe7c488ae65e2690737323f049edfe3e1439bd"},{"sha":"74101edb6079354a1c902cb32b3bd0ec18bcc528","author":{"name":"Nguyễn Thái Ngọc Duy","email":"024f400cd820cb2ddbe54c7fecfd01e45f30bb96@gmail.com"},"message":"unpack-trees: optimize walking same trees with cache-tree\n\nIn order to merge one or many trees with the index, unpack-trees code\nwalks multiple trees in parallel with the index and performs n-way\nmerge. If we find out at start of a directory that all trees are the\nsame (by comparing OID) and cache-tree happens to be available for\nthat directory as well, we could avoid walking the trees because we\nalready know what these trees contain: it's flattened in what's called\n\"the index\".\n\nThe upside is of course a lot less I/O since we can potentially skip\nlots of trees (think subtrees). We also save CPU because we don't have\nto inflate and apply the deltas. The downside is of course more\nfragile code since the logic in some functions are now duplicated\nelsewhere.\n\n\"checkout -\" with this patch on webkit.git (275k files):\n\n    baseline      new\n  --------------------------------------------------------------------\n    0.056651714   0.080394752 s:  read cache .git/index\n    0.183101080   0.216010838 s:  preload index\n    0.008584433   0.008534301 s:  refresh index\n    0.633767589   0.251992198 s:   traverse_trees\n    0.340265448   0.377031383 s:   check_updates\n    0.381884638   0.372768105 s:   cache_tree_update\n    1.401562947   1.045887251 s:  unpack_trees\n    0.338687914   0.314983512 s:  write index, changed mask = 2e\n    0.411927922   0.062572653 s:    traverse_trees\n    0.000023335   0.000022544 s:    check_updates\n    0.423697246   0.073795585 s:   unpack_trees\n    0.423708360   0.073807557 s:  diff-index\n    2.559524127   1.938191592 s: git command: git checkout -\n\nAnother measurement from Ben's running \"git checkout\" with over 500k\ntrees (on the whole series):\n\n    baseline        new\n  ----------------------------------------------------------------------\n    0.535510167     0.556558733     s: read cache .git/index\n    0.3057373       0.3147105       s: initialize name hash\n    0.0184082       0.023558433     s: preload index\n    0.086910967     0.089085967     s: refresh index\n    7.889590767     2.191554433     s: unpack trees\n    0.120760833     0.131941267     s: update worktree after a merge\n    2.2583504       2.572663167     s: repair cache-tree\n    0.8916137       0.959495233     s: write index, changed mask = 28\n    3.405199233     0.2710663       s: unpack trees\n    0.000999667     0.0021554       s: update worktree after a merge\n    3.4063306       0.273318333     s: diff-index\n    16.9524923      9.462943133     s: git command: git.exe checkout\n\nThis command calls unpack_trees() twice, the first time on 2way merge\nand the second 1way merge. In both times, \"unpack trees\" time is\nreduced to one third. Overall time reduction is not that impressive of\ncourse because index operations take a big chunk. And there's that\nrepair cache-tree line.\n\nPS. A note about cache-tree invalidation and the use of it in this\ncode.\n\nWe do invalidate cache-tree in _source_ index when we add new entries\nto the (temporary) \"result\" index. But we also use the cache-tree from\nsource index in this optimization. Does this mean we end up having no\ncache-tree in the source index to activate this optimization?\n\nThe answer is twisted: the order of finding a good cache-tree and\ninvalidating it matters. In this case we check for a good cache-tree\nfirst in all_trees_same_as_cache_tree(), then we start to merge things\nand potentially invalidate that same cache-tree in the process. Since\ncache-tree invalidation happens after the optimization kicks in, we're\nstill good. But we may lose that cache-tree at the very first\ncall_unpack_fn() call in traverse_by_cache_tree().\n\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\nSigned-off-by: Junio C Hamano <gitster@pobox.com>","distinct":false,"url":"https://api.github.com/repos/gitgitgadget/git/commits/74101edb6079354a1c902cb32b3bd0ec18bcc528"},{"sha":"9261c5920eede294e151c17609217193a8c73f2c","author":{"name":"Nguyễn Thái Ngọc Duy","email":"024f400cd820cb2ddbe54c7fecfd01e45f30bb96@gmail.com"},"message":"unpack-trees: reduce malloc in cache-tree walk\n\nThis is a micro optimization that probably only shines on repos with\ndeep directory structure. Instead of allocating and freeing a new\ncache_entry in every iteration, we reuse the last one and only update\nthe parts that are new each iteration.\n\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\nSigned-off-by: Junio C Hamano <gitster@pobox.com>","distinct":false,"url":"https://api.github.com/repos/gitgitgadget/git/commits/9261c5920eede294e151c17609217193a8c73f2c"},{"sha":"43fac1154fe9466d944defc3851a20e961d67df9","author":{"name":"Nguyễn Thái Ngọc Duy","email":"024f400cd820cb2ddbe54c7fecfd01e45f30bb96@gmail.com"},"message":"unpack-trees: reuse (still valid) cache-tree from src_index\n\nWe do n-way merge by walking the source index and n trees at the same\ntime and add merge results to a new temporary index called o->result.\nThe merge result for any given path could be either\n\n- keep_entry(): same old index entry in o->src_index is reused\n- merged_entry(): either a new entry is added, or an existing one updated\n- deleted_entry(): one entry from o->src_index is removed\n\nFor some reason [1] we keep making sure that the source index's\ncache-tree is still valid if used by o->result: for all those\nmerged/deleted entries, we invalidate the same path in o->src_index,\nso only cache-trees covering the \"keep_entry\" parts remain good.\n\nBecause of this, the cache-tree from o->src_index can be perfectly\nreused in o->result. And in fact we already rely on this logic to\nreuse untracked cache in edf3b90553 (unpack-trees: preserve index\nextensions - 2017-05-08). Move the cache-tree to o->result before\ndoing cache_tree_update() to reduce hashing cost.\n\nSince cache_tree_update() has risen up as one of the most expensive\nparts in unpack_trees() after the last few patches. This does help\nreduce unpack_trees() time significantly (on webkit.git):\n\n    before       after\n  --------------------------------------------------------------------\n    0.080394752  0.051258167 s:  read cache .git/index\n    0.216010838  0.212106298 s:  preload index\n    0.008534301  0.280521764 s:  refresh index\n    0.251992198  0.218160442 s:   traverse_trees\n    0.377031383  0.374948191 s:   check_updates\n    0.372768105  0.037040114 s:   cache_tree_update\n    1.045887251  0.672031609 s:  unpack_trees\n    0.314983512  0.317456290 s:  write index, changed mask = 2e\n    0.062572653  0.038382654 s:    traverse_trees\n    0.000022544  0.000042731 s:    check_updates\n    0.073795585  0.050930053 s:   unpack_trees\n    0.073807557  0.051099735 s:  diff-index\n    1.938191592  1.614241153 s: git command: git checkout -\n\n[1] I'm pretty sure the reason is an oversight in 34110cd4e3 (Make\n    'unpack_trees()' have a separate source and destination index -\n    2008-03-06). That patch aims to _not_ update the source index at\n    all. The invalidation should have been done on o->result in that\n    patch. But then there was no cache-tree on o->result even then so\n    it's pointless to do so.\n\nSigned-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>\nSigned-off-by: Junio C Hamano <gitster@pobox.com>","distinct":false,"url":"https://api.github.com/repos/gitgitgadget/git/commits/43fac1154fe9466d944defc3851a20e961d67df9"}]}
{"actor":{"display_login":"dscho"}}