{"thread":{"id":"34621","subject":"[PATCH] git exproll: steps to tackle gc aggression","startedAt":"2013-08-06T02:38:47Z","lastAt":"2013-08-10T10:16:00Z","messageCount":33,"participants":["Ramkumar Ramachandra","Duy Nguyen","Junio C Hamano","Martin Fick","Martin Langhoff","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"224636","messageId":"1375756727-1275-1-git-send-email-artagnon@gmail.com","threadId":"34621","inReplyTo":null,"subject":"[PATCH] git exproll: steps to tackle gc aggression","fromName":"Ramkumar Ramachandra","fromEmail":"artagnon@gmail.com","sentAt":"2013-08-06T02:38:47Z","receivedAt":"2013-08-06T02:38:47Z","isPatch":true,"sender":{"key":"r@artagnon.com","avatar":"https://avatars.githubusercontent.com/u/37226?v=4"},"body":"This is the rough explanation I wrote down after reading it:\n\nSo, the problem is that my .git/objects/pack is polluted with little\npacks everytime I fetch (or push, if you're the server), and this is\nproblematic from the perspective of a overtly (naively) aggressive gc\nthat hammers out all fragmentation. So, on the first run, the little\npackfiles I have are all \"consolidated\" into big packfiles; you also\nwrite .keep files to say that \"don't gc these big packs we just\ngenerated\". In subsequent runs, the little packfiles from the fetch are\nabsorbed into a pack that is immune to gc. You're also using a size\nheuristic, to consolidate similarly sized packfiles. You also have a\n--ratio to tweak the ratio of sizes.\n\nFrom: Martin Fick\nSee: https://gerrit-review.googlesource.com/#/c/35215/\nThread: http://thread.gmane.org/gmane.comp.version-control.git/231555\n(Martin's emails are missing from the archive)\n---\n Not a candidate for inclusion, given how difficult it is to convince\n our conservative maintainer to add anything new to the tree.\n\n I'm posting this in the interest of visibility: I've checked it into\n my repo and started using it. I encourage everyone else to do the\n same, so we can learn from it and discuss how to improve gc.\n\n contrib/exproll/git-exproll.sh | 566 +++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 566 insertions(+)\n create mode 100755 contrib/exproll/git-exproll.sh\n\ndiff --git a/contrib/exproll/git-exproll.sh b/contrib/exproll/git-exproll.sh\nnew file mode 100755\nindex 0000000..9526d9f\n--- /dev/null\n+++ b/contrib/exproll/git-exproll.sh\n@@ -0,0 +1,566 @@\n+#!/bin/bash\n+# Copyright (c) 2012, Code Aurora Forum. All rights reserved.\n+#\n+# Redistribution and use in source and binary forms, with or without\n+# modification, are permitted provided that the following conditions are\n+# met:\n+# # Redistributions of source code must retain the above copyright\n+# notice, this list of conditions and the following disclaimer.\n+# # Redistributions in binary form must reproduce the above\n+# copyright notice, this list of conditions and the following\n+# disclaimer in the documentation and/or other materials provided\n+# with the distribution.\n+# # Neither the name of Code Aurora Forum, Inc. nor the names of its\n+# contributors may be used to endorse or promote products derived\n+# from this software without specific prior written permission.\n+#\n+# THIS SOFTWARE IS PROVIDED \"AS IS\" AND ANY EXPRESS OR IMPLIED\n+# WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF\n+# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT\n+# ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS\n+# BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR\n+# CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF\n+# SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR\n+# BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,\n+# WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE\n+# OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN\n+# IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\n+\n+usage() { # error_message\n+\n+ cat <<-EOF\n+\t\tusage: $(basename $0) [-unvt] [--noref] [--nolosse] [-r|--ratio number]\n+\t\t [git gc option...] git.repo\n+\n+\t\t-u|-h usage/help\n+\t\t-v verbose\n+\t\t-n dry-run don't actually repack anything\n+\t\t-t touch treat repo as if it had been touched\n+\t\t--noref avoid extra ref packing timestamp checking\n+\t\t--noloose do not run just because there are loose object dirs\n+\t\t (repacking may still run if they are referenced)\n+\t\t-r ratio packfile ratio to aim for (default 10)\n+\n+\t\tgit gc option will be passed as args to git gc\n+\n+\t\tgit.repo to run gc against\n+\n+\t\tGarbage collect using a pseudo logarithmic packfile maintenance\n+\t\tapproach. This approach attempts to minimize packfile churn\n+\t\tby keeping several generations of varying sized packfiles around\n+\t\tand only consolidating packfiles (or loose objects) which are\n+\t\teither new packfiles, or packfiles close to the same size as\n+\t\tanother packfile.\n+\n+\t\tAn estimate is used to predict when rollups (one consolidation\n+\t\twould cause another consolidation) would occur so that this\n+\t\trollup can be done all at once via a single repack. This reduces\n+\t\tboth the runtime and the pack file churn in rollup cases.\n+\n+\t\tApproach: plan each consolidation by creating a table like this:\n+\n+\t\tId Keep Size Sha1(or consolidation list) Actions(repack down up note)\n+\t\t1 - 11356 9052edfb7392646cd4e5f362b953675985f01f96 y - - New\n+\t\t2 - 429088 010904d5c11cd26a79fda91b01ab454d1001b402 y - - New\n+\t\tc1 - 440444 [1,2] - - -\n+\n+\t\tId: numbers preceded by a c are estimated \"c pack\" files\n+\t\tKeep: - none, k private keep, o our keep\n+\t\tSize: in disk blocks (default du output)\n+\t\tSha1: of packfile, or consolidation list of packfile ids\n+\t\tActions\n+\t\trepack: - n no, y yes\n+\t\tdown: - noop, ^ consolidate with a file above\n+\t\tup: - noop, v consolidate with a file below\n+\t\tnote: Human description of script decisions:\n+\t\t New (file is a new packfile)\n+\t\t Consolidate with:\n+\t\t (too far from:)\n+\n+\t\tOn the first pass, always consolidate any new packfiles along\n+\t\twith loose objects and along with any packfiles which are within\n+\t\tthe ratio size of their predecessors (note, the list is ordered\n+\t\tby increasing size). After each consolidation, insert a fake\n+\t\tconsolidation, or \"c pack\", to naively represent the size and\n+\t\tordered positioning of the anticipated new consolidated pack.\n+\t\tEvery time a new pack is planned, rescan the list in case the\n+\t\tnew \"c pack\" would cause more consolidation...\n+\n+\t\tOnce the packfiles which need consolidation are determined, the\n+\t\tpackfiles which will not be consolidated are marked with a .keep\n+\t\tfile, and those which will be consolidated will have their .keep\n+\t\tremoved if they have one. Thus, the packfiles with a .keep will\n+\t\tnot get repacked.\n+\n+\t\tPackfile consolidation is determined by the --ratio parameter\n+\t\t(default is 10). This ratio is somewhat of a tradeoff. The\n+\t\tsmaller the number, the more packfiles will be kept on average;\n+\t\tthis increases disk utilization somewhat. However, a larger\n+\t\tratio causes greater churn and may increase disk utilization due\n+\t\tto deleted packfiles not being reclaimed since they may still be\n+\t\tkept open by long running applications such as Gerrit. Sane\n+\t\tratio values are probably between 2 and 10. Since most\n+\t\tconsolidations actually end up smaller than the estimated\n+\t\tconsolidated packfile size (due to compression), the true ratio\n+\t\tachieved will likely be 1 to 2 greater than the target ratio.\n+\t\tThe smaller the target ratio, the greater this discrepancy.\n+\n+\t\tFinally, attempt to skip garbage collection entirely on untouched\n+\t\trepos. In order to determine if a repo has been touched, use the\n+\t\ttimestamp on the script's keep files, if any relevant file/dir\n+\t\tis newer than a keep marker file, assume that the repo has been\n+\t\ttouched and gc needs to run. Also assume gc needs to run whenever\n+\t\tthere are loose object dirs since they may contain untouched\n+\t\tunreferenced loose objects which need to be pruned (once they\n+\t\texpire).\n+\n+\t\tIn order to allow the keep files to be an effective timestamp\n+\t\tmarker to detect relevant changes in a repo since the last run,\n+\t\tall relevant files and directories which may be modified during a\n+\t\tgc run (even during a noop gc run), must have their timestamps\n+\t\treset to the same time as the keep files or gc will always run\n+\t\teven on untouched repos. The relevant files/dirs are all those\n+\t\tfiles and directories which garbage collection, object packing,\n+\t\tref packing and pruning might change during noop actions.\n+EOF\n+\n+ [ -n \"$1\" ] && info \"ERROR $1\"\n+\n+ exit\n+}\n+\n+debug() { [ -n \"$SW_V\" ] && info \"$1\" ; }\n+info() { echo \"$1\" >&2 ; }\n+\n+array_copy() { #v2 # array_src array_dst\n+ local src=$1 dst=$2\n+ local s i=0\n+ eval s=\\${#$src[@]}\n+ while [ $i -lt $s ] ; do\n+ eval $dst[$i]=\\\"\\${$src[$i]}\\\"\n+ i=$(($i + 1))\n+ done\n+}\n+\n+array_equals() { #v2 # array_name [vals...]\n+ local a=$1 ; shift\n+ local s=0 t=() val\n+ array_copy \"$a\" t\n+ for s in \"${!t[@]}\" ; do s=$((s+1)) ; done\n+ [ \"$s\" -ne \"$#\" ] && return 1\n+ for val in \"${t[@]}\" ; do\n+ [ \"$val\" = \"$1\" ] || return 2\n+ shift\n+ done\n+ return 0\n+}\n+\n+packs_sizes() { # git.repo > \"size pack\"...\n+ du -s \"$1\"/objects/pack/pack-$SHA1.pack | sort -n 2> /dev/null\n+}\n+\n+is_ourkeep() { grep -q \"$KEEP\" \"$1\" 2> /dev/null ; } # keep\n+has_ourkeep() { is_ourkeep \"$(keep_for \"$1\")\" ; } # pack\n+has_keep() { [ -f \"$(keep_for \"$1\")\" ] ; } # pack\n+is_repo() { [ -d \"$1/objects\" ] && [ -d \"$1/refs/heads\" ] ; } # git.repo\n+\n+keep() { # pack # returns true if we added our keep\n+ keep=$(keep_for \"$1\")\n+ [ -f \"$keep\" ] && return 1\n+ echo \"$KEEP\" > \"$keep\"\n+ return 0\n+}\n+\n+keep_for() { # packfile > keepfile\n+ local keep=$(echo \"$1\" | sed -es'/\\.pack$/.keep/')\n+ [ \"${keep/.keep}\" = \"$keep\" ] && return 1\n+ echo \"$keep\"\n+}\n+\n+idx_for() { # packfile > idxfile\n+ local idx=$(echo \"$1\" | sed -es'/\\.pack$/.idx/')\n+ [ \"${idx/.idx}\" = \"$idx\" ] && return 1\n+ echo \"$idx\"\n+}\n+\n+# pack_or_keep_file > sha\n+sha_for() { echo \"$1\" | sed -es'|\\(.*/\\)*pack-\\([^.]*\\)\\..*$|\\2|' ; }\n+\n+private_keeps() { # git.repo -> sets pkeeps\n+ local repo=$1 ary=$2\n+ local keep keeps=(\"$repo\"/objects/pack/pack-$SHA1.keep)\n+ pkeeps=()\n+ for keep in \"${keeps[@]}\" ; do\n+ is_ourkeep \"$keep\" || pkeeps=(\"${pkeeps[@]}\" \"$keep\")\n+ done\n+}\n+\n+is_tooclose() { [ \"$(($1 * $RATIO))\" -gt \"$2\" ] ; } # smaller larger\n+\n+unique() { # [args...] > unique_words\n+ local lines=$(while [ $# -gt 0 ] ; do echo \"$1\" ; shift ; done)\n+ lines=$(echo \"$lines\" | sort -u)\n+ echo $lines # as words\n+}\n+\n+outfs() { # fs [args...] > argfs...\n+ local fs=$1 ; shift\n+ [ $# -gt 0 ] && echo -n \"$1\" ; shift\n+ while [ $# -gt 0 ] ; do echo -n \"$fs$1\" ; shift ; done\n+}\n+\n+sort_list() { # < list > formatted_list\n+ # n has_keep size sha repack down up note\n+ awk '{ note=$8; for(i=8;i treat as touched\" ; return 0 ; }\n+\n+ if [ -z \"$SW_LOOSE\" ] ; then\n+ # If there are loose objects, they may need to be pruned,\n+ # run even if nothing has really been touched.\n+ loose=$(find \"$repo/objects\" -type d \\\n+ -wholename \"$repo/objects/[0-9][0-9]\"\n+ -print -quit 2>/dev/null)\n+ [ -n \"$loose\" ] && { info \"There are loose object directories\" ; return 0 ; }\n+ fi\n+\n+ # If we don't have a keep, the current packfiles may not have been\n+ # compressed with the current gc policy (gc may never have been run),\n+ # so run at least once to repack everything. Also, we need a marker\n+ # file for timestamp tracking (a dir needs to detect changes within\n+ # it, so it cannot be a marker) and our keeps are something we control,\n+ # use them.\n+ for keep in \"$repo\"/objects/pack/pack-$SHA1.keep ; do\n+ is_ourkeep \"$keep\" && { ours=$keep ; break ; }\n+ done\n+ [ -z \"$ours\" ] && { info 'We have no keep (we have never run?): run' ; return 0 ; }\n+\n+ debug \"Our timestamp keep: $ours\"\n+ # The wholename stuff seems to get touched by a noop git gc\n+ newer=$(find \"$repo/objects\" \"$repo/refs\" \"$repo/packed-refs\" \\\n+ '!' -wholename \"$repo/objects/info\" \\\n+ '!' -wholename \"$repo/objects/info/*\" \\\n+ -newer \"$ours\" \\\n+ -print -quit 2>/dev/null)\n+ [ -z \"$newer\" ] && return 1\n+\n+ info \"Touched since last run: $newer\"\n+ return 0\n+}\n+\n+touch_refs() { # git.repo start_date refs\n+ local repo=$1 start_date=$2 refs=$3\n+ (\n+ debug \"Setting start date($start_date) on unpacked refs:\"\n+ debug \"$refs\"\n+ cd \"$repo/refs\" || return\n+ # safe to assume no newlines in a ref name\n+ echo \"$refs\" | xargs -d '\\n' -n 1 touch -c -d \"$start_date\"\n+ )\n+}\n+\n+set_start_date() { # git.repo start_date refs refdirs packedrefs [packs]\n+ local repo=$1 start_date=$2 refs=$3 refdirs=$4 packedrefs=$5 ; shift 5\n+ local pack keep idx repacked\n+\n+ # This stuff is touched during object packs\n+ while [ $# -gt 0 ] ; do\n+ pack=$1 ; shift\n+ keep=\"$(keep_for \"$pack\")\"\n+ idx=\"$(idx_for \"$pack\")\"\n+ touch -c -d \"$start_date\" \"$pack\" \"$keep\" \"$idx\"\n+ debug \"Setting start date on: $pack $keep $idx\"\n+ done\n+ # This will prevent us from detecting any deletes in the pack dir\n+ # since gc ran, except for private keeps which we are checking\n+ # manually. But there really shouldn't be any other relevant deletes\n+ # in this dir which should cause us to rerun next time, deleting a\n+ # pack or index file by anything but gc would be bad!\n+ debug \"Setting start date on pack dir: $start_date\"\n+ touch -c -d \"$start_date\" \"$repo/objects/pack\"\n+\n+\n+ if [ -z \"$SW_REFS\" ] ; then\n+ repacked=$(find \"$repo/packed-refs\" -newer \"$repo/objects/pack\"\n+ -print -quit 2>/dev/null)\n+ if [ -n \"$repacked\" ] ; then\n+ # The ref dirs and packed-ref files seem to get touched even on\n+ # a noop refpacking\n+ debug \"Setting start date on packed-refs\"\n+ touch -c -d \"$start_date\" \"$repo/packed-refs\"\n+ touch_refs \"$repo\" \"$start_date\" \"$refdirs\"\n+\n+ # A ref repack does not imply a ref change, but since it is\n+ # hard to tell, simply assume so\n+ if [ \"$refs\" != \"$(cd \"$repo/refs\" ; find -depth)\" ] || \\\n+ [ \"$packedrefs\" != \"$(<\"$repo/packed-refs\")\" ] ; then\n+ # We retouch if needed (instead of simply checking then\n+ # touching) to avoid a race between the check and the set.\n+ debug \" but refs actually got packed, so retouch packed-refs\"\n+ touch -c \"$repo/packed-refs\"\n+ fi\n+ fi\n+ fi\n+}\n+\n+note_consolidate() { # note entry > note (no duplicated consolidated entries)\n+ local note=$1 entry=$2\n+ local entries=() ifs=$IFS\n+ if echo \"$note\" | grep -q 'Consolidate with:[0-9,c]' ; then\n+ IFS=,\n+ entries=( $(echo \"$note\" | sed -es'/^.*Consolidate with:\\([0-9,c]*\\).*$/\\1/') )\n+ note=( $(echo \"$note\" | sed -es'/Consolidate with:[0-9,c]*//') )\n+ IFS=$ifs\n+ fi\n+ entries=( $(unique \"${entries[@]}\" \"$entry\") )\n+ echo \"$note Consolidate with:$(outfs , \"${entries[@]}\")\"\n+}\n+\n+note_toofar() { # note entry > note (no duplicated \"too far\" entries)\n+ local note=$1 entry=$2\n+ local entries=() ifs=$IFS\n+ if echo \"$note\" | grep -q '(too far from:[0-9,c]*)' ; then\n+ IFS=,\n+ entries=( $(echo \"$note\" | sed -es'/^.*(too far from:\\([0-9,c]*\\)).*$/\\1/') )\n+ note=( $(echo \"$note\" | sed -es'/(too far from:[0-9,c]*)//') )\n+ IFS=$ifs\n+ fi\n+ entries=( $(unique \"${entries[@]}\" \"$entry\") )\n+ echo \"$note (too far from:$(outfs , \"${entries[@]}\"))\"\n+}\n+\n+last_entry() { # isRepack pline repackline > last_rows_entry\n+ local size_hit=$1 pline=$2 repackline=$3\n+ if [ -n \"$pline\" ] ; then\n+ if [ -n \"$size_hit\" ] ; then\n+ echo \"$repack_line\"\n+ else\n+ echo \"$pline\"\n+ fi\n+ fi\n+}\n+\n+init_list() { # git.repo > shortlist\n+ local repo=$1\n+ local file\n+ local n has_keep size sha repack\n+\n+ packs_sizes \"$1\" | {\n+ while read size file ; do\n+ n=$((n+1))\n+ repack=n\n+ has_keep=-\n+ if has_keep \"$file\" ; then\n+ has_keep=k\n+ has_ourkeep \"$file\" && has_keep=o\n+ fi\n+ sha=$(sha_for \"$file\")\n+ echo \"$n $has_keep $size $sha $repack\"\n+ done\n+ } | sort_list\n+}\n+\n+consolidate_list() { # run < list > list\n+ local run=$1\n+ local sum=0 psize=0 sum_size=0 size_hit pn clist pline repackline\n+ local n has_keep size sha repack down up note\n+\n+ {\n+ while read n has_keep size sha repack down up note; do\n+ [ -z \"$up\" ] && up='-'\n+ [ -z \"$down\" ] && down=\"-\"\n+\n+ if [ \"$has_keep\" = \"k\" ] ; then\n+ echo \"$n $has_keep $size $sha $repack - - Private\"\n+ continue\n+ fi\n+\n+ if [ \"$repack\" = \"n\" ] ; then\n+ if is_tooclose $psize $size ; then\n+ size_hit=y\n+ repack=y\n+ sum=$(($sum + $sum_size + $size))\n+ sum_size=0 # Prevents double summing this entry\n+ clist=($(unique \"${clist[@]}\" $pn $n))\n+ down=\"^\"\n+ [ \"$has_keep\" = \"-\" ] && note=\"$note New +\"\n+ note=$(note_consolidate \"$note\" \"$pn\")\n+ elif [ \"$has_keep\" = \"-\" ] ; then\n+ repack=y\n+ sum=$(($sum + $size))\n+ sum_size=0 # Prevents double summing this entry\n+ clist=($(unique \"${clist[@]}\" $n))\n+ note=\"$note New\"\n+ elif [ $psize -ne 0 ] ; then\n+ sum_size=$size\n+ down=\"!\"\n+ note=$(note_toofar \"$note\" \"$pn\")\n+ else\n+ sum_size=$size\n+ fi\n+ else\n+ sum_size=$size\n+ fi\n+\n+ # By preventing \"c files\" (consolidated) from being marked\n+ # \"repack\" they won't get keeps\n+ repack2=y\n+ [ \"${n/c}\" != \"$n\" ] && { repack=- ; repack2=- ; }\n+\n+ last_entry \"$size_hit\" \"$pline\" \"$repack_line\"\n+ # Delay the printout until we know whether we are\n+ # being consolidated with the entry following us\n+ # (we won't know until the next iteration).\n+ # size_hit is used to determine which of the lines\n+ # below will actually get printed above on the next\n+ # iteration.\n+ pline=\"$n $has_keep $size $sha $repack $down $up $note\"\n+ repack_line=\"$n $has_keep $size $sha $repack2 $down v $note\"\n+\n+ pn=$n ; psize=$size # previous entry data\n+ size_hit='' # will not be consolidated up\n+\n+ done\n+ last_entry \"$size_hit\" \"$pline\" \"$repack_line\"\n+\n+ [ $sum -gt 0 ] && echo \"c$run - $sum [$(outfs , \"${clist[@]}\")] - - -\"\n+\n+ } | sort_list\n+}\n+\n+process_list() { # git.repo > list\n+ local list=$(init_list \"$1\") plist run=0\n+\n+ while true ; do\n+ plist=$list\n+ run=$((run +1))\n+ list=$(echo \"$list\" | consolidate_list \"$run\")\n+ if [ \"$plist\" != \"$list\" ] ; then\n+ debug \"------------------------------------------------------------------------------------\"\n+ debug \"$HEADER\"\n+ debug \"$list\"\n+ else\n+ break\n+ fi\n+ done\n+ debug \"------------------------------------------------------------------------------------\"\n+ echo \"$list\"\n+}\n+\n+repack_list() { # git.repo < list\n+ local repo=$1\n+ local start_date newpacks=0 pkeeps keeps=1 refs refdirs rtn\n+ local packedrefs=$(<\"$repo/packed-refs\")\n+\n+ # so they don't appear touched after a noop refpacking\n+ if [ -z \"$SW_REFS\" ] ; then\n+ refs=$(cd \"$repo/refs\" ; find -depth)\n+ refdirs=$(cd \"$repo/refs\" ; find -type d -depth)\n+ debug \"Before refs:\"\n+ debug \"$refs\"\n+ fi\n+\n+ # Find a private keep snapshot which has not changed from\n+ # before our start_date so private keep deletions during gc\n+ # can be detected\n+ while ! array_equals pkeeps \"${keeps[@]}\" ; do\n+ debug \"Getting a private keep snapshot\"\n+ private_keeps \"$repo\"\n+ keeps=(\"${pkeeps[@]}\")\n+ debug \"before keeps: ${keeps[*]}\"\n+ start_date=$(date)\n+ private_keeps \"$repo\"\n+ debug \"after keeps: ${pkeeps[*]}\"\n+ done\n+\n+ while read n has_keep size sha repack down up note; do\n+ if [ \"$repack\" = \"y\" ] ; then\n+ keep=\"$repo/objects/pack/pack-$sha.keep\"\n+ info \"Repacking $repo/objects/pack/pack-$sha.pack\"\n+ [ -f \"$keep\" ] && rm -f \"$keep\"\n+ fi\n+ done\n+\n+ ( cd \"$repo\" && git gc \"${GC_OPTS[@]}\" ) ; rtn=$?\n+\n+ # Mark any files withoug a .keep with our .keep\n+ packs=(\"$repo\"/objects/pack/pack-$SHA1.pack)\n+ for pack in \"${packs[@]}\" ; do\n+ if keep \"$pack\" ; then\n+ info \"New pack: $pack\"\n+ newpacks=$((newpacks+1))\n+ fi\n+ done\n+\n+ # Record start_time. If there is more than 1 new packfile, we\n+ # don't want to risk touching it with an older date since that\n+ # would prevent consolidation on the next run. If the private\n+ # keeps have changed, then we should run next time no matter what.\n+ if [ $newpacks -le 1 ] || ! array_equals pkeeps \"${keeps[@]}\" ; then\n+ set_start_date \"$repo\" \"$start_date\" \"$refs\" \"$refdirs\" \"$packedrefs\" \"${packs[@]}\"\n+ fi\n+\n+ return $rtn # we really only care about the gc error code\n+}\n+\n+git_gc() { # git.repo\n+ local list=$(process_list \"$1\")\n+ if [ -z \"$SW_V\" ] ; then\n+ info \"Running $PROG on $1. git gc options: ${GC_OPTS[@]}\"\n+ echo \"$HEADER\" >&2\n+ echo \"$list\" >&2 ;\n+ fi\n+ echo \"$list\" | repack_list \"$1\"\n+}\n+\n+\n+PROG=$(basename \"$0\")\n+HEADER=\"Id Keep Size Sha1(or consolidation list) Actions(repack down up note)\"\n+KEEP=git-exproll\n+HEX='[0-9a-f]'\n+HEX10=$HEX$HEX$HEX$HEX$HEX$HEX$HEX$HEX$HEX$HEX\n+SHA1=$HEX10$HEX10$HEX10$HEX10\n+\n+RATIO=10\n+SW_N='' ; SW_V='' ; SW_T='' ; SW_REFS='' ; SW_LOOSE='' ; GC_OPTS=()\n+while [ $# -gt 0 ] ; do\n+ case \"$1\" in\n+ -u|-h) usage ;;\n+ -n) SW_N=\"$1\" ;;\n+ -v) SW_V=\"$1\" ;;\n+\n+ -t) SW_T=\"$1\" ;;\n+ --norefs) SW_REFS=\"$1\" ;;\n+ --noloose) SW_LOOSE=\"$1\" ;;\n+\n+ -r|--ratio) shift ; RATIO=\"$1\" ;;\n+\n+ *) [ $# -le 1 ] && break\n+ GC_OPTS=( \"${GC_OPTS[@]}\" \"$1\" )\n+ ;;\n+ esac\n+ shift\n+done\n+\n+\n+REPO=\"$1\"\n+if ! is_repo \"$REPO\" ; then\n+ REPO=$REPO/.git\n+ is_repo \"$REPO\" || usage \"($1) is not likely a git repo\"\n+fi\n+\n+\n+if [ -z \"$SW_N\" ] ; then\n+ is_touched \"$REPO\" || { info \"Repo untouched since last run\" ; exit ; }\n+ git_gc \"$REPO\"\n+else\n+ is_touched \"$REPO\" || info \"Repo untouched since last run, analyze anyway.\"\n+ process_list \"$REPO\" >&2\n+fi\n-- \n1.8.4.rc1.4.gd6cbf2f\n"},{"id":"224661","messageId":"CACsJy8CGWJ07Uk8EBjfejdyshKB1NKk=_7VUoeyZWZgJFqCSkg@mail.gmail.com","threadId":"34621","inReplyTo":"1375756727-1275-1-git-send-email-artagnon@gmail.com","subject":"Re: [PATCH] git exproll: steps to tackle gc aggression","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-08-06T12:24:50Z","receivedAt":"2013-08-06T12:24:50Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Aug 6, 2013 at 9:38 AM, Ramkumar Ramachandra wrote:\n> + Garbage collect using a pseudo logarithmic packfile maintenance\n> + approach. This approach attempts to minimize packfile churn\n> + by keeping several generations of varying sized packfiles around\n> + and only consolidating packfiles (or loose objects) which are\n> + either new packfiles, or packfiles close to the same size as\n> + another packfile.\n\nI wonder if a simpler approach may be nearly efficient as this one:\nkeep the largest pack out, repack the rest at fetch/push time so there\nare at most 2 packs at a time. Or we we could do the repack at 'gc\n--auto' time, but with lower pack threshold (about 10 or so). When the\nsecond pack is as big as, say half the size of the first, merge them\ninto one at \"gc --auto\" time. This can be easily implemented in\ngit-repack.sh.\n-- \nDuy\n"},{"id":"224692","messageId":"7v61vihg6k.fsf@alter.siamese.dyndns.org","threadId":"34621","inReplyTo":"CACsJy8CGWJ07Uk8EBjfejdyshKB1NKk=_7VUoeyZWZgJFqCSkg@mail.gmail.com","subject":"Re: [PATCH] git exproll: steps to tackle gc aggression","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-08-06T17:39:31Z","receivedAt":"2013-08-06T17:39:31Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Duy Nguyen writes:\n\n> On Tue, Aug 6, 2013 at 9:38 AM, Ramkumar Ramachandra wrote:\n>> + Garbage collect using a pseudo logarithmic packfile maintenance\n>> + approach. This approach attempts to minimize packfile churn\n>> + by keeping several generations of varying sized packfiles around\n>> + and only consolidating packfiles (or loose objects) which are\n>> + either new packfiles, or packfiles close to the same size as\n>> + another packfile.\n>\n> I wonder if a simpler approach may be nearly efficient as this one:\n> keep the largest pack out, repack the rest at fetch/push time so there\n> are at most 2 packs at a time. Or we we could do the repack at 'gc\n> --auto' time, but with lower pack threshold (about 10 or so). When the\n> second pack is as big as, say half the size of the first, merge them\n> into one at \"gc --auto\" time. This can be easily implemented in\n> git-repack.sh.\n\nAnother random thought.\n\nImagine we have a cheap way to enumerate the young objects without\nthe usual history traversal. For example, list of all loose objects\nand what appears in the .idx files that are young.\n\nWe can reconstruct \"names\" for trees and blobs from such a list of\nobject names; if a commit in the list refers to a tree, that tree is\nthe top level, and a blob or a tree that appears in such a top-level\ntree can be given a \"name\" for its place in the tree (recursively).\nI suspect we would end up giving names to large majority of trees\nand blobs in such a list by doing so.\n\nIf these suspicions turn out to be true, then we could:\n\n - run that enumeration algorithm to come up with a set of object\n names;\n\n - emit the tag objects in that set in the tagger timestamp order;\n\n - emit the commit objects in that set in the commit timestamp\n order, while noting the tree objects contained in the set, giving\n them name \"\";\n\n - \"traverse\" the trees and blobs in that set, giving the found ones\n names (do so without stepping outside the set);\n\n - emit the trees and blobs with their names. Some objects may not\n have given any name, but that is OK as long as they are in the\n minority.\n\nAnd feeding it to pack-objects to produce a single pack, and then\nprune away the source of these young objects in the end.\n\nThe above could turn out to be much cheaper than the traditional\nhistory traversal.\n"},{"id":"224725","messageId":"201308061810.46562.mfick@codeaurora.org","threadId":"34621","inReplyTo":"CACsJy8CGWJ07Uk8EBjfejdyshKB1NKk=_7VUoeyZWZgJFqCSkg@mail.gmail.com","subject":"Re: [PATCH] git exproll: steps to tackle gc aggression","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2013-08-07T00:10:46Z","receivedAt":"2013-08-07T00:10:46Z","isPatch":true,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"On Tuesday, August 06, 2013 06:24:50 am Duy Nguyen wrote:\n> On Tue, Aug 6, 2013 at 9:38 AM, Ramkumar Ramachandra \n wrote:\n> > + Garbage collect using a pseudo\n> > logarithmic packfile maintenance + \n> > approach. This approach attempts to minimize packfile\n> > churn + by keeping several generations\n> > of varying sized packfiles around + and\n> > only consolidating packfiles (or loose objects) which\n> > are + either new packfiles, or packfiles\n> > close to the same size as + another\n> > packfile.\n> \n> I wonder if a simpler approach may be nearly efficient as\n> this one: keep the largest pack out, repack the rest at\n> fetch/push time so there are at most 2 packs at a time.\n> Or we we could do the repack at 'gc --auto' time, but\n> with lower pack threshold (about 10 or so). When the\n> second pack is as big as, say half the size of the\n> first, merge them into one at \"gc --auto\" time. This can\n> be easily implemented in git-repack.sh.\n\nIt would definitely be better than the current gc approach. \n\nHowever, I suspect it is still at least one to two orders of \nmagnitude off from where it should be. To give you a real \nworld example, on our server today when gitexproll ran on \nour kernel/msm repo, it consolidated 317 pack files into one \nalmost 8M packfile (it compresses/dedupes shockingly well, \none of those new packs was 33M). Our largest packfile in \nthat repo is 1.5G! \n\nSo let's now imagine that the second closest packfile is \nonly 100M, it would keep getting consolidated with 8M worth \nof data every day (assuming the same conditions and no extra \ncompression). That would take (750M-100M)/8M ~ 81 days to \nfinally build up large enough to no longer consolidate the \nnew packs with the second largest pack file daily. During \nthose 80+ days, it will be on average writing 325M too much \nper day (when it should be writing just 8M).\n\nSo I can see the appeal of a simple solution, unfortunately \nI think one layer would still \"suck\" though. And if you are \ngoing to add even just one extra layer, I suspect that you \nmight as well go the full distance since you probably \nalready need to implement the logic to do so?\n\n-Martin\n\n-- \nThe Qualcomm Innovation Center, Inc. is a member of Code \nAurora Forum, hosted by The Linux Foundation\n \n"},{"id":"224726","messageId":"201308061825.28579.mfick@codeaurora.org","threadId":"34621","inReplyTo":"1375756727-1275-1-git-send-email-artagnon@gmail.com","subject":"Re: [PATCH] git exproll: steps to tackle gc aggression","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2013-08-07T00:25:28Z","receivedAt":"2013-08-07T00:25:28Z","isPatch":true,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"On Monday, August 05, 2013 08:38:47 pm Ramkumar Ramachandra \nwrote:\n> This is the rough explanation I wrote down after reading\n> it:\n> \n> So, the problem is that my .git/objects/pack is polluted\n> with little packs everytime I fetch (or push, if you're\n> the server), and this is problematic from the\n> perspective of a overtly (naively) aggressive gc that\n> hammers out all fragmentation. So, on the first run,\n> the little packfiles I have are all \"consolidated\" into\n> big packfiles; you also write .keep files to say that\n> \"don't gc these big packs we just generated\". In\n> subsequent runs, the little packfiles from the fetch are\n> absorbed into a pack that is immune to gc. You're also\n> using a size heuristic, to consolidate similarly sized\n> packfiles. You also have a --ratio to tweak the ratio\n> of sizes.\n> \n> From: Martin Fick\n> See: https://gerrit-review.googlesource.com/#/c/35215/\n> Thread:\n> http://thread.gmane.org/gmane.comp.version-control.git/2\n> 31555 (Martin's emails are missing from the archive)\n> ---\n\nAfter analyzing today's data, I recognize that in some \ncircumstances the size estimation after consolidation can be \noff by huge amounts. The script naively just adds the \ncurrent sizes together. This gives a very rough estimate, \nof the new packfile size, but sometimes it can be off by \nover 2 orders of magnitude. :( While many new packfiles are \ntiny (several K only), it seems like the larger new \npackfiles have a terrible tendency to throw the estimate way \noff (I suspect they simply have many duplicate objects). \nBut despite this poor estimate, the script still offers \ndrastic improvements over plain git gc.\n\nSo, it has me wondering if there isn't a more accurate way \nto estimate the new packfile without wasting a ton of time?\n\nIf not, one approach which might be worth experimenting with \nis to just assume that new packfiles have size 0! Then just \nconsolidate them with any other packfile which is ready for \nconsolidation, or if none are ready, with the smallest \npackfile. I would not be surprised to see this work on \naverage better than the current summation,\n\n-Martin\n\n\n-- \nThe Qualcomm Innovation Center, Inc. is a member of Code \nAurora Forum, hosted by The Linux Foundation\n \n"},{"id":"224729","messageId":"CALkWK0=41FNXQk1cAKdgAd3t3Bzh1KEc3bksu0M1LjdSgfmr3Q@mail.gmail.com","threadId":"34621","inReplyTo":"201308061825.28579.mfick@codeaurora.org","subject":"Re: [PATCH] git exproll: steps to tackle gc aggression","fromName":"Ramkumar Ramachandra","fromEmail":"artagnon@gmail.com","sentAt":"2013-08-07T04:36:38Z","receivedAt":"2013-08-07T04:36:38Z","isPatch":true,"sender":{"key":"r@artagnon.com","avatar":"https://avatars.githubusercontent.com/u/37226?v=4"},"body":"Martin Fick wrote:\n> So, it has me wondering if there isn't a more accurate way\n> to estimate the new packfile without wasting a ton of time?\n\nI'm not sure there is. Adding the sizes of individual packs can be off\nby a lot, because your deltification will be more effective if you\nhave more data to slide windows over and compress. For the purposes of\nillustration, take a simple example:\n\npackfile-1 has a 30M Makefile and several tiny deltas. Total = 40M.\npackfile-2 has a 31M Makefile.um and several tiny deltas. Total = 40M.\n\nNow, what is the size of packfile-3 which contains the contents of\nboth packfile-1 and packfile-2? 80M is a bad estimate, because you can\nstore deltas against just one Makefile.\n\nSo, unless you do an in-depth analysis of the objects in the packfiles\n(which can be terribly expensive), I don't see how you can arrive at a\nbetter estimate.\n\n> If not, one approach which might be worth experimenting with\n> is to just assume that new packfiles have size 0! Then just\n> consolidate them with any other packfile which is ready for\n> consolidation, or if none are ready, with the smallest\n> packfile. I would not be surprised to see this work on\n> average better than the current summation,\n\nThat is assuming that all fetches (or pushes) are small, which is\nprobably a good rule; you might like to have a \"smallness threshold\",\nalthough I haven't thought hard about the problem.\n"},{"id":"224730","messageId":"CALkWK0kmx8bi1ZT1CSk+iVnmmQJV4bNu1D7h1AHnRk7_TfhJ3Q@mail.gmail.com","threadId":"34621","inReplyTo":"7v61vihg6k.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] git exproll: steps to tackle gc aggression","fromName":"Ramkumar Ramachandra","fromEmail":"artagnon@gmail.com","sentAt":"2013-08-07T04:43:13Z","receivedAt":"2013-08-07T04:43:13Z","isPatch":true,"sender":{"key":"r@artagnon.com","avatar":"https://avatars.githubusercontent.com/u/37226?v=4"},"body":"Junio C Hamano wrote:\n> Imagine we have a cheap way to enumerate the young objects without\n> the usual history traversal.\n\nBefore we discuss the advantages, can you outline how we can possibly\nget this data without actually walking downwards from the roots\n(refs)? One way to do it is to pull data out of a log of ref updates\n(aka. reflog), but we both know how unreliable that can be.\n"},{"id":"224782","messageId":"CACsJy8DoZkKP5QVN33=6VXc10mhEDyA6khaDww+L9eeyc20B1w@mail.gmail.com","threadId":"34621","inReplyTo":"201308061810.46562.mfick@codeaurora.org","subject":"Re: [PATCH] git exproll: steps to tackle gc aggression","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-08-08T02:18:47Z","receivedAt":"2013-08-08T02:18:47Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Wed, Aug 7, 2013 at 7:10 AM, Martin Fick wrote:\n>> I wonder if a simpler approach may be nearly efficient as\n>> this one: keep the largest pack out, repack the rest at\n>> fetch/push time so there are at most 2 packs at a time.\n>> Or we we could do the repack at 'gc --auto' time, but\n>> with lower pack threshold (about 10 or so). When the\n>> second pack is as big as, say half the size of the\n>> first, merge them into one at \"gc --auto\" time. This can\n>> be easily implemented in git-repack.sh.\n>\n> It would definitely be better than the current gc approach.\n>\n> However, I suspect it is still at least one to two orders of\n> magnitude off from where it should be. To give you a real\n> world example, on our server today when gitexproll ran on\n> our kernel/msm repo, it consolidated 317 pack files into one\n> almost 8M packfile (it compresses/dedupes shockingly well,\n> one of those new packs was 33M). Our largest packfile in\n> that repo is 1.5G!\n>\n> So let's now imagine that the second closest packfile is\n> only 100M, it would keep getting consolidated with 8M worth\n> of data every day (assuming the same conditions and no extra\n> compression). That would take (750M-100M)/8M ~ 81 days to\n> finally build up large enough to no longer consolidate the\n> new packs with the second largest pack file daily. During\n> those 80+ days, it will be on average writing 325M too much\n> per day (when it should be writing just 8M).\n>\n> So I can see the appeal of a simple solution, unfortunately\n> I think one layer would still \"suck\" though. And if you are\n> going to add even just one extra layer, I suspect that you\n> might as well go the full distance since you probably\n> already need to implement the logic to do so?\n\nI see. It looks like your way is the best way to go.\n-- \nDuy\n"},{"id":"224793","messageId":"7va9ksbqpl.fsf@alter.siamese.dyndns.org","threadId":"34621","inReplyTo":"CALkWK0kmx8bi1ZT1CSk+iVnmmQJV4bNu1D7h1AHnRk7_TfhJ3Q@mail.gmail.com","subject":"Re: [PATCH] git exproll: steps to tackle gc aggression","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-08-08T07:13:10Z","receivedAt":"2013-08-08T07:13:10Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ramkumar Ramachandra writes:\n\n> Junio C Hamano wrote:\n>> Imagine we have a cheap way to enumerate the young objects without\n>> the usual history traversal.\n>\n> Before we discuss the advantages, can you outline how we can possibly\n> get this data without actually walking downwards from the roots\n> (refs)? One way to do it is to pull data out of a log of ref updates\n> (aka. reflog), but we both know how unreliable that can be.\n\nMy understanding of the topic is to come up with a way that is much\ncheaper than the current \"gc --auto\" that involves recent history\nwalk to consolidate both loose objects and small young packs into\none, so that we can use that logic for \"gc --auto\".\n\nThe key phrase is \"without the usual history traversal\". We are\ntalking about young objects, and they are likely to be reachable\nfrom something (like reflog entries, if not refs). We may include\nunreachable cruft in the result in the \"let's be quick and collect\nthem into a single young pack\", and you will need to keep them while\nreflog entries are alive, and you will need periodic sweeps with the\nusual history walking to remove older crufts that recently have\nbecome unreachable due to reflog expiry from packs anyway, so it is\nnot a problem for the pack that consolidates young objects into a\nsingle pack to contain some unreachable crufts.\n\nIf you start from that assumption [*1*], the way to enumerate the\nyoung objects without the usual history traversal should be fairly\nobvious.\n\nBy definition, loose objects are all young because they were created\nsince the last \"gc --auto\". Also pack .idx files know their own\ncreation timestamp to let you decide how old they are, you can see\nhow many objects there are in the corresponding .pack and how big it\nis.\n\nBy doing an equivalent of \"find .git/objects/[0-9a-f][0-9a-f]/\", you\ncan enumerate the loose objects, and an equivalent of \"show-ref\"\nwill enumerate the objects in the pack that the .idx file you\ndetermined to be small and young.\n\nNote that *1* is an assumption. I do not know offhand if such a\n\"consolidate young objects quickly into one to keep the number of\npacks small\" strategy is an overall win.\n"},{"id":"224795","messageId":"CALkWK0mxd35OGDG2fMaRsfycvBPPxDHWrPX8og5y2+4y1dfOpw@mail.gmail.com","threadId":"34621","inReplyTo":"7va9ksbqpl.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] git exproll: steps to tackle gc aggression","fromName":"Ramkumar Ramachandra","fromEmail":"artagnon@gmail.com","sentAt":"2013-08-08T07:44:52Z","receivedAt":"2013-08-08T07:44:52Z","isPatch":true,"sender":{"key":"r@artagnon.com","avatar":"https://avatars.githubusercontent.com/u/37226?v=4"},"body":"Junio C Hamano wrote:\n> it is\n> not a problem for the pack that consolidates young objects into a\n> single pack to contain some unreachable crufts.\n\nSo far, we have never considered putting unreachable objects in packs.\nLet me ask the obvious question first: what happens when I push? Do I\npack up all the loose objects quickly (without bothering about\nreachability) and send unreachable cruft to the server? Who is\nultimately going to clean up this cruft, and when?\n\n> Note that *1* is an assumption. I do not know offhand if such a\n> \"consolidate young objects quickly into one to keep the number of\n> packs small\" strategy is an overall win.\n\nThe way I see it, you're just delaying the reachability analysis\nbeyond the usual pack-time. The whole point of separating out loose\nobjects from packfiles was to not make the user wait everytime she\ndoes common repository operations locally: delay the reachability\nanalysis and compression (aka. packing) until a network operation\nkicks in.\n\nTo see if introducing another stage is an overall win, think about\nwhat the bottlenecks are: in network operations, it's always the data\nbeing sent over. If I understand correctly, during a network\ntransaction, there's very minimal computation where the server-client\njust quickly tell each other where their refs are: therefore, it's\ntrivial to figure out what's missing and pack that up to send it over.\nThe strategy of including unreachable cruft in these packs might make\nsense from the point of view of a local gc, but will ultimately slow\ndown network operations, no?\n"},{"id":"224826","messageId":"7v61vgazp5.fsf@alter.siamese.dyndns.org","threadId":"34621","inReplyTo":"CALkWK0mxd35OGDG2fMaRsfycvBPPxDHWrPX8og5y2+4y1dfOpw@mail.gmail.com","subject":"Re: [PATCH] git exproll: steps to tackle gc aggression","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-08-08T16:56:38Z","receivedAt":"2013-08-08T16:56:38Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ramkumar Ramachandra writes:\n\n> Junio C Hamano wrote:\n>> it is\n>> not a problem for the pack that consolidates young objects into a\n>> single pack to contain some unreachable crufts.\n>\n> So far, we have never considered putting unreachable objects in packs.\n> Let me ask the obvious question first: what happens when I push? Do I\n> pack up all the loose objects quickly (without bothering about\n> reachability) and send unreachable cruft to the server?\n\nNo.\n\nI thought the discussion was about making the local gc cheaper, and\nthe \"Imagine we have a cheap way\" was to address it by assuming that\nthe daily \"pack young objects into a single pack\" can be sped up if\nwe did not have to traverse history. More permanent packs (the\nolder ones in \"set of packs staggered by age\" Martin proposes) in\nthe repository should go through the normal history traversal route.\n\nAnd of course we do not transfer objects that are not asked for from\nor to a repository over pack tranfer.\n\nMost importantly, it is not about butchering the pack machinery in\nsuch a way that we can create _only_ such \"non history traversal\"\npacks.\n\nSo I do not see how that question is \"obvious\". The question\nobviously pointless and misses the mark by wide margin? The\nquestion makes it obvious that whoever asks it does not understand\nhow Git works?\n"},{"id":"224830","messageId":"201308081134.35735.mfick@codeaurora.org","threadId":"34621","inReplyTo":"7v61vgazp5.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] git exproll: steps to tackle gc aggression","fromName":"Martin Fick","fromEmail":"mfick@codeaurora.org","sentAt":"2013-08-08T17:34:35Z","receivedAt":"2013-08-08T17:34:35Z","isPatch":true,"sender":{"key":"mfick@codeaurora.org","avatar":null},"body":"On Thursday, August 08, 2013 10:56:38 am Junio C Hamano \nwrote:\n> I thought the discussion was about making the local gc\n> cheaper, and the \"Imagine we have a cheap way\" was to\n> address it by assuming that the daily \"pack young\n> objects into a single pack\" can be sped up if we did not\n> have to traverse history. More permanent packs (the\n> older ones in \"set of packs staggered by age\" Martin\n> proposes) in the repository should go through the normal\n> history traversal route.\n\nAssuming I understand what you are suggesting, would these \n\"young object\" likely still get \"deduped\" in an efficient \nway without doing history traversal (it sounds like they \nwould)? In other words, if I understand correctly, it would \nsave time by not pruning unreferenced objects, but it would \nstill be deduping things and delta compressing also, so you \nwould still likely get a great benefit from creating these \nyoung object packs? In other words, is there still a good \nchance that my 317 new pack files which included a 33M pack \nfile will still get consolidated down to something near 8M? \n\nIf so, then yeah this might be nice, especially if the \nhistory traversal is what would speed this up. Because \ntoday, my solution mostly saves IO and not time. I think it \nstill saves time, I believe I have seen up to a 50% savings, \nbut that is nothing compared to massive, several orders of \nmagnitude IO savings. But if what you suggest could also \ngive massive time (orders of magnitude) savings along with \nthe IO improvements I am seeing, then suddenly repacking \nregularly would become very cheap even on large repos. \n\nThe only time consuming piece would be pruning then? Could \nbitmaps eventually help out there?\n\n-Martin\n\n\n-- \nThe Qualcomm Innovation Center, Inc. is a member of Code \nAurora Forum, hosted by The Linux Foundation\n \n"},{"id":"224831","messageId":"CALkWK0kqE8azzxp_GkzhPNT41nD8NzeLqXSe1xi0jbVo=7Xz3A@mail.gmail.com","threadId":"34621","inReplyTo":"7v61vgazp5.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] git exproll: steps to tackle gc aggression","fromName":"Ramkumar Ramachandra","fromEmail":"artagnon@gmail.com","sentAt":"2013-08-08T17:36:02Z","receivedAt":"2013-08-08T17:36:02Z","isPatch":true,"sender":{"key":"r@artagnon.com","avatar":"https://avatars.githubusercontent.com/u/37226?v=4"},"body":"Junio C Hamano wrote:\n> So I do not see how that question is \"obvious\". The question\n> obviously pointless and misses the mark by wide margin? The\n> question makes it obvious that whoever asks it does not understand\n> how Git works?\n\nShall we all sit and mourn over the fact that I don't understand how\nGit works, or are you willing to explain it to me?\n\n> And of course we do not transfer objects that are not asked for from\n> or to a repository over pack tranfer.\n>\n> Most importantly, it is not about butchering the pack machinery in\n> such a way that we can create _only_ such \"non history traversal\"\n> packs.\n\nI asked you a very simple question: what happens when I do \"git push\"?\nInstead of answering the question, you butchered the pack machinery to\n\"only\" create packs with garbage in them (aka. stripped out the\nreachability analysis code completely), and blamed me for doing it.\n\nExplain it to me in plain English without getting agitated:\n\n1. I'm on my terminal doing various repository operations: constantly\ncreating new objects and moving my refs around to create unreachable\nobjects. I have lots of loose objects.\n\n2. I say \"git push\". What happens? A reachability analysis is\nperformed on my loose objects, and the ones reachable by the ref I'm\nsending are packed up and sent over the network. Now, I no longer have\nany loose objects.\n\n3. After a few days of working, the gc heuristics figure out that I\nhave too much garbage and too many packs; a cleanup is required. The\ngc --auto which doesn't tolerate fragmentation: it tries to put\neverything into one large pack.\n\nLoop.\n\nWe're talking about tackling the gc aggression problem in 3. And you\npropose putting the young objects in a pack without performing\nreachability analysis: I'm asking how this is going to benefit me;\nwhen I say \"git push\" (or when gc decides to repack), won't I need to\nexplode the young pack into loose objects, do a reachability analysis,\nand repack anyway?\n"},{"id":"224843","messageId":"7va9ks9frm.fsf@alter.siamese.dyndns.org","threadId":"34621","inReplyTo":"201308081134.35735.mfick@codeaurora.org","subject":"Re: [PATCH] git exproll: steps to tackle gc aggression","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-08-08T18:52:29Z","receivedAt":"2013-08-08T18:52:29Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Martin Fick writes:\n\n> Assuming I understand what you are suggesting, would these \n> \"young object\" likely still get \"deduped\" in an efficient \n> way without doing history traversal (it sounds like they \n> would)?\n\nYes.\n\nThe very first thing pack-object machinery does is to get the list\nof object names and sort them in a certain order to help producing\ngood deltas, and this initial input preprocessing will dedup them.\n\n> If so, then yeah this might be nice, especially if the history\n> traversal is what would speed this up.\n\nThat was the assumption behind the \"it might help\" suggestion. If\nthat helps or not is not known yet, and since Ram started this\nsubthread telling me not to talk about performance improvements, my\ntime on this thread is _not_ spent on that (yet).\n"},{"id":"224847","messageId":"CALkWK0mE=Gov1YocbGMs4cUGf+-uEorvkFwBEpP0JXfDLPwuyQ@mail.gmail.com","threadId":"34621","inReplyTo":"7va9ks9frm.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] git exproll: steps to tackle gc aggression","fromName":"Ramkumar Ramachandra","fromEmail":"artagnon@gmail.com","sentAt":"2013-08-08T19:14:01Z","receivedAt":"2013-08-08T19:14:01Z","isPatch":true,"sender":{"key":"r@artagnon.com","avatar":"https://avatars.githubusercontent.com/u/37226?v=4"},"body":"Junio C Hamano wrote:\n> Martin Fick writes:\n>> Assuming I understand what you are suggesting, would these\n>> \"young object\" likely still get \"deduped\" in an efficient\n>> way without doing history traversal (it sounds like they\n>> would)?\n>\n> Yes.\n>\n> The very first thing pack-object machinery does is to get the list\n> of object names and sort them in a certain order to help producing\n> good deltas, and this initial input preprocessing will dedup them.\n\nSo, the proposal is to create an index of young objects without doing\nreachability analysis (I still didn't get the point of packing them;\nas I pointed out, it seems to be rather counter-productive) to help\nthe actual packing? From what I vaguely understood:\n\n1. Index all the young objects to save a history traversal (?)\n\n2. Perform the reachability analysis using the index in step 1, and\nthen generate the pack.\n\nI'm not yet clear about what information 1 contains to help 2. Is it\nthe rough ordering? (The big important objects come near the top of\nthe pack, and the deltas are generated against them). I say \"rough\"\nbecause the ordering might change after the unreachable objects are\npruned.\n\n*scratches head*\n"},{"id":"224850","messageId":"7vwqnw7z47.fsf@alter.siamese.dyndns.org","threadId":"34621","inReplyTo":"CALkWK0kqE8azzxp_GkzhPNT41nD8NzeLqXSe1xi0jbVo=7Xz3A@mail.gmail.com","subject":"Re: [PATCH] git exproll: steps to tackle gc aggression","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-08-08T19:37:28Z","receivedAt":"2013-08-08T19:37:28Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ramkumar Ramachandra writes:\n\n> I asked you a very simple question: what happens when I do \"git push\"?\n\nYou asked \"does push send unreachable cruft?\" and I said No. Does\nthat answer your question?\n\n> 3. After a few days of working, the gc heuristics figure out that I\n> have too much garbage and too many packs; a cleanup is required. The\n> gc --auto which doesn't tolerate fragmentation: it tries to put\n> everything into one large pack.\n\nToday's \"gc --auto\" skims the history shallowly and packs loose\nobjects into a single _new_ pack. If you start from a single pack\nand enough loose objects and run \"gc --auto\", you will have two\npacks, one intact from the original, one new.\n\n> We're talking about tackling the gc aggression problem in 3.\n\n> when I say \"git push\" (or when gc decides to repack), won't I need\n> to explode the young pack into loose objects, do a reachability\n> analysis, and repack anyway?\n\nYou do not explode anything. \"push\" will read objects from\nanywhere, either from loose or packed, and send a newly created pack\nover the wire.\n\nAnd I see from \"(or when ...)\" part that you do not know what you\nare talking about. \"push\" will not stream existing pack to the\nother end without computation, and it never will. It will reuse\nexisting individual pieces when it can, and having data in a pack\n(even without deltifying, or as a suboptimal delta) is much better\nfor push performance than having the same data in a loose object if\nonly for this reason, as you do not have to recompress and reencode\nit in a different way (loose objects and undelitifed object in pack\nare encoded differently).\n\n> ... are you willing to explain it to me?\n\nHope that the above clarifies.\n\nI've treated this thread as a design discussion, not an education\nsession, but the above ended up having more education material than\nanything that would advance the design.\n"},{"id":"224851","messageId":"CALkWK0=nerszb3_YA8P=qXbfAd4Y1rNsHXhfVKzwtj-x80iqkg@mail.gmail.com","threadId":"34621","inReplyTo":"7vwqnw7z47.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] git exproll: steps to tackle gc aggression","fromName":"Ramkumar Ramachandra","fromEmail":"artagnon@gmail.com","sentAt":"2013-08-08T20:04:48Z","receivedAt":"2013-08-08T20:04:48Z","isPatch":true,"sender":{"key":"r@artagnon.com","avatar":"https://avatars.githubusercontent.com/u/37226?v=4"},"body":"Junio C Hamano wrote:\n>> 3. After a few days of working, the gc heuristics figure out that I\n>> have too much garbage and too many packs; a cleanup is required. The\n>> gc --auto which doesn't tolerate fragmentation: it tries to put\n>> everything into one large pack.\n>\n> Today's \"gc --auto\" skims the history shallowly and packs loose\n> objects into a single _new_ pack. If you start from a single pack\n> and enough loose objects and run \"gc --auto\", you will have two\n> packs, one intact from the original, one new.\n\nThat is when I have lots of loose objects and few packs. We are\ndiscussing gc aggression when there are too many packs (how did we get\nthere in the first place if new packs aren't created?): in which case\nit doesn't tolerate fragmentation, and tries to put everything in one\npack. That is both IO and CPU intensive, and we've been trying to\ntackle that since the start of the thread.\n\n> And I see from \"(or when ...)\" part that you do not know what you\n> are talking about. \"push\" will not stream existing pack to the\n> other end without computation, and it never will. It will reuse\n> existing individual pieces when it can, and having data in a pack\n> (even without deltifying, or as a suboptimal delta) is much better\n> for push performance than having the same data in a loose object if\n> only for this reason, as you do not have to recompress and reencode\n> it in a different way (loose objects and undelitifed object in pack\n> are encoded differently).\n\nCertainly. A push will never use an existing pack as-is, as it's very\nhighly unlikely that the server requested exactly what gc --auto\npacked for us locally.\n\nSure, undeltified objects in the pack are probably better for push\nperformance, but I'm talking about the majority: deltified objects.\nDon't you need to apply the deltas (ie. explode the pack), before you\ncan recompute the deltas for the information you're sending across for\nthe push?\n\n> I've treated this thread as a design discussion, not an education\n> session, but the above ended up having more education material than\n> anything that would advance the design.\n\nYou will need to educate your contributors and potential contributors\nif you want these problems to be fixed.\n"},{"id":"224856","messageId":"CACPiFCLPA=ih5PVgqoi763YL2CYvJ1friC1YMG5ziLrSPUpYZg@mail.gmail.com","threadId":"34621","inReplyTo":"CALkWK0=nerszb3_YA8P=qXbfAd4Y1rNsHXhfVKzwtj-x80iqkg@mail.gmail.com","subject":"Re: [PATCH] git exproll: steps to tackle gc aggression","fromName":"Martin Langhoff","fromEmail":"martin.langhoff@gmail.com","sentAt":"2013-08-08T21:09:16Z","receivedAt":"2013-08-08T21:09:16Z","isPatch":true,"sender":{"key":"martin.langhoff@gmail.com","avatar":"https://gravatar.com/avatar/1e3f311b6c4c15836501901ca58f8c0b0667246488084ba524d8bc9867e22fd9?d=mp&s=160"},"body":"On Thu, Aug 8, 2013 at 4:04 PM, Ramkumar Ramachandra wrote:\n> You will need to educate your contributors and potential contributors\n> if you want these problems to be fixed.\n\nTBH, I think Junio is exceedingly kind and generous with his time.\n\nIME (and there's quite a few years of it :-) ), good contributors\nlearn a little bit asking, and ton on their own.\n\nYour tone is quite demanding, which I personally find... rather out of place.\n\n\n\nm\n-- \n martin.langhoff@gmail.com\n - ask interesting questions\n - don't get distracted with shiny stuff - working code first\n ~ http://docs.moodle.org/en/User:Martin_Langhoff\n"},{"id":"224893","messageId":"20130809110000.GD18878@sigill.intra.peff.net","threadId":"34621","inReplyTo":"CALkWK0=nerszb3_YA8P=qXbfAd4Y1rNsHXhfVKzwtj-x80iqkg@mail.gmail.com","subject":"Re: [PATCH] git exproll: steps to tackle gc aggression","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-08-09T11:00:00Z","receivedAt":"2013-08-09T11:00:00Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 09, 2013 at 01:34:48AM +0530, Ramkumar Ramachandra wrote:\n\n> Certainly. A push will never use an existing pack as-is, as it's very\n> highly unlikely that the server requested exactly what gc --auto\n> packed for us locally.\n> \n> Sure, undeltified objects in the pack are probably better for push\n> performance, but I'm talking about the majority: deltified objects.\n> Don't you need to apply the deltas (ie. explode the pack), before you\n> can recompute the deltas for the information you're sending across for\n> the push?\n\nIt depends on what each side has it, doesn't it? We generally try to\nreuse on-disk deltas when we can, since they require no computation. If\nI have object A delta'd against B, and I know that the other side wants\nA and has B (or I am also sending B), I can simply send what I have on\ndisk. So we do not just blit out the existing pack as-is, but we may\nreuse portions of it as appropriate.\n\nOf course we may have to reconstruct deltas for trees in order to find\nthe correct set of objects (i.e., the history traversal). But that is a\nseparate phase from generating the pack's object content, and we do not\nreuse any of the traversal work in later phases.\n\n-Peff\n"},{"id":"224904","messageId":"CALkWK0nSC-Aty55QO+DrM5Zf2t=DK8iMfbhv_HD44Z_m8d19Pg@mail.gmail.com","threadId":"34621","inReplyTo":"20130809110000.GD18878@sigill.intra.peff.net","subject":"Re: [PATCH] git exproll: steps to tackle gc aggression","fromName":"Ramkumar Ramachandra","fromEmail":"artagnon@gmail.com","sentAt":"2013-08-09T13:34:23Z","receivedAt":"2013-08-09T13:34:23Z","isPatch":true,"sender":{"key":"r@artagnon.com","avatar":"https://avatars.githubusercontent.com/u/37226?v=4"},"body":"Jeff King wrote:\n> It depends on what each side has it, doesn't it? We generally try to\n> reuse on-disk deltas when we can, since they require no computation. If\n> I have object A delta'd against B, and I know that the other side wants\n> A and has B (or I am also sending B), I can simply send what I have on\n> disk. So we do not just blit out the existing pack as-is, but we may\n> reuse portions of it as appropriate.\n\nI'll raise some (hopefully interesting) points. Let's take the example\nof a simple push: I start send-pack, which in turn starts receive_pack\non the server and connects its stdin/stdout to it (using git_connect).\nNow, it reads the (sha1, ref) pairs it receives on stdin and spawns\npack-objects --stdout with the right arguments as the response, right?\nOverall, nothing special: just pack-objects invoked with specific\narguments.\n\nHow does pack-objects work? ll_find_deltas() spawns some worker\nthreads to find_deltas(). This is where this get fuzzy for me: it\ncalls try_delta() in a nested loop, trying to find the smallest delta,\nright? I'm not sure whether the interfaces it uses to read objects\ndifferentiates between packed deltas versus packed undeltified objects\nversus loose objects at all.\n\nNow, the main problem I see is that a pack has to be self-contained: I\ncan't have an object \"bar\" which is a delta against an object that is\nnot present in the pack, right? Therefore no matter what the server\nalready has, I have to prepare deltas only against the data that I'm\nsending across.\n\n> Of course we may have to reconstruct deltas for trees in order to find\n> the correct set of objects (i.e., the history traversal). But that is a\n> separate phase from generating the pack's object content, and we do not\n> reuse any of the traversal work in later phases.\n\nI see. Are we talking about tree-walk.c here? This is not unique to\npacking at all; we need to do this kind of traversal for any git\noperation that digs into older history, no? I recall a discussion\nabout using generation numbers to speed up the walk: I tried playing\nwith your series (where you use a cache to keep the generation\nnumbers), but got nowhere. Does it make sense to think about speeding\nup the walk (how?).\n"},{"id":"224923","messageId":"7vr4e26a40.fsf@alter.siamese.dyndns.org","threadId":"34621","inReplyTo":"CALkWK0nSC-Aty55QO+DrM5Zf2t=DK8iMfbhv_HD44Z_m8d19Pg@mail.gmail.com","subject":"Re: [PATCH] git exproll: steps to tackle gc aggression","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-08-09T17:35:11Z","receivedAt":"2013-08-09T17:35:11Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ramkumar Ramachandra writes:\n\n> I'll raise some (hopefully interesting) points. Let's take the example\n> of a simple push: I start send-pack, which in turn starts receive_pack\n> on the server and connects its stdin/stdout to it (using git_connect).\n> Now, it reads the (sha1, ref) pairs it receives on stdin and spawns\n> pack-objects --stdout with the right arguments as the response, right?\n> Overall, nothing special: just pack-objects invoked with specific\n> arguments.\n>\n> How does pack-objects work? ...\n\nYou've been here long enough to know that you can and should learn\nthings yourself instead of repeating \"tell me tell me\" ;-)\n\n> threads to find_deltas(). This is where this get fuzzy for me: it\n> calls try_delta() in a nested loop, trying to find the smallest delta,\n> right?\n\nYes.\n\n> I'm not sure whether the interfaces it uses to read objects\n> differentiates between packed deltas versus packed undeltified objects\n> versus loose objects at all.\n\nYes, but that happens way before that. Start reading from\npack-heuristics document to get the general overall feel of what\ngoes on, and then go back to the source.\n\n> Now, the main problem I see is that a pack has to be self-contained: I\n> can't have an object \"bar\" which is a delta against an object that is\n> not present in the pack, right? Therefore no matter what the server\n> already has, I have to prepare deltas only against the data that I'm\n> sending across.\n\nThere is a --thin option to allow deltas against base objects that\nare known to exist on the other end to be used in the pack without\nincluding the base objects. The receiving end then re-adds the base\nobjects to the received data to complete the pack.\n"},{"id":"224966","messageId":"20130809221615.GA7160@sigill.intra.peff.net","threadId":"34621","inReplyTo":"CALkWK0nSC-Aty55QO+DrM5Zf2t=DK8iMfbhv_HD44Z_m8d19Pg@mail.gmail.com","subject":"Re: [PATCH] git exproll: steps to tackle gc aggression","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-08-09T22:16:15Z","receivedAt":"2013-08-09T22:16:15Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 09, 2013 at 07:04:23PM +0530, Ramkumar Ramachandra wrote:\n\n> I'll raise some (hopefully interesting) points. Let's take the example\n> of a simple push: I start send-pack, which in turn starts receive_pack\n> on the server and connects its stdin/stdout to it (using git_connect).\n> Now, it reads the (sha1, ref) pairs it receives on stdin and spawns\n> pack-objects --stdout with the right arguments as the response, right?\n> Overall, nothing special: just pack-objects invoked with specific\n> arguments.\n> \n> How does pack-objects work? ll_find_deltas() spawns some worker\n> threads to find_deltas(). This is where this get fuzzy for me: it\n> calls try_delta() in a nested loop, trying to find the smallest delta,\n> right? I'm not sure whether the interfaces it uses to read objects\n> differentiates between packed deltas versus packed undeltified objects\n> versus loose objects at all.\n\nYou are missing a step in the preparation of the delta list. If we\nalready have a delta on-disk, we will check whether it is usable and\nkeep a note in the list (see check_object). Then when we\nprepare the list of objects to delta, it is omitted from the list (see\nprepare_pack).\n\nThat is why you may see a much smaller number objects in the progress\neye candy for \"Compressing objects...\" than we are actually sending.\n\n> Now, the main problem I see is that a pack has to be self-contained: I\n> can't have an object \"bar\" which is a delta against an object that is\n> not present in the pack, right? Therefore no matter what the server\n> already has, I have to prepare deltas only against the data that I'm\n> sending across.\n\nAs Junio mentioned, that is what \"--thin\" is about; the sender omits the\nbase and the receiver adds it back in (\"index-pack --fix-thin\"). And if\nyou think about it, that is likely where most of Martin's \"317 packs\nturned into 8MB\" space savings are coming from.\n\nSomebody pushes X, which deltas against Y. They send only the delta for\nX->Y, but the receiver stores that delta plus a full copy of Y, even\nthough we already have Y in another pack. Repacking throws away the\nextra copy of Y.\n\nAnd that is why something like Junio's suggestion of \"do not traverse\nhistory; just concatenate the packs and throw away duplicate objects\"\nmight be helpful. You would not find new deltas, but you would get rid\nof these duplicate objects, and doing so would be relatively cheap.\n\nAnother solution could involve not writing the duplicate of Y in the\nfirst place. The reason we do not store thin-packs on disk is that you\nrun into problems with cycles in the delta graph (e.g., A deltas against\nB, which deltas against C, which deltas against A; at one point you had\na full copy of one object which let you create the cycle, but you later\ndeleted it as redundant with the delta, and now you cannot reconstruct\nany of the objects).\n\nYou could possibly solve this with cycle detection, though it would be\ncomplicated (you need to do it not just when getting rid of objects, but\nwhen sending a pack, to make sure you don't send a cycle of deltas that\nthe other end cannot use). You _might_ be able to get by with a kind of\n\"two-level\" hack: consider your main pack as \"group A\" and newly pushed\npacks as \"group B\". Allow storing thin deltas on disk from group B\nagainst group A, but never the reverse (nor within group B). That makes\nsure you don't have cycles, and it eliminates even more I/O than any\nrepacking solution (because you never write the extra copy of Y to disk\nin the first place). But I can think of two problems:\n\n 1. You still want to repack more often than every 300 packs, because\n having many packs cost both in space, but also in object lookup\n time (we can do a log(N) search through each pack index, but have\n to search linearly through the set of indices).\n\n 2. As you accumulate group B packs with new objects, the deltas that\n people send will tend to be against objects in group B. They are\n closer to the tip of history, and therefore make better deltas for\n history built on top.\n\nThat's all just off the top of my head. There are probably other flaws,\ntoo, as I haven't considered it too hard. But if you are really\nconcerned about I/O on a busy repo (and I think for hosting sites, it is\na real problem), the best-performing solution will probably not involve\npacks at all, but some kind of delta-capable storage that you can\nincrementally add to without rewriting the whole repository. The\ndownside is that it would be significantly more complicated.\n\n> > Of course we may have to reconstruct deltas for trees in order to find\n> > the correct set of objects (i.e., the history traversal). But that is a\n> > separate phase from generating the pack's object content, and we do not\n> > reuse any of the traversal work in later phases.\n> \n> I see. Are we talking about tree-walk.c here? This is not unique to\n> packing at all; we need to do this kind of traversal for any git\n> operation that digs into older history, no? I recall a discussion\n> about using generation numbers to speed up the walk: I tried playing\n> with your series (where you use a cache to keep the generation\n> numbers), but got nowhere. Does it make sense to think about speeding\n> up the walk (how?).\n\nIt's actually list-objects.c, and no, it is not unique to packing (you\ncan run the same code with \"git rev-list --objects\"). The CPU time for such\na traversal is generally spent in:\n\n 1. Accessing commit objects data from disk (this shows up as libz in\n perf runs).\n\n 2. Accessing tree object data from disk (libz again).\n\n 3. Reconstructing tree deltas (this shows up as memcpy in perf, but of\n course we have to access base objects, which increases item 2).\n\n 4. Converting sha1s into \"struct object\" via hash table lookup\n (lookup_object in perf).\n\nGeneration numbers can make some commit walks faster by cutting off the\ntraversal early. But they don't really apply here, for a few reasons.\nOne, our worst case is actually a full clone or prune, and there is no\ncutoff; we must go down to the roots. Two, we use commit timestamps as a\nproxy for generation numbers. Most of the traversal algorithms use the\ntimestamps in a priority queue, and are written such that we always get\nthe right answer in the face of skewed timestamps, but we may go deeper\nthan necessary if they are skewed. The exception is the depth-first\n\"tag --contains\" algorithm, which typically goes to the roots (and if\nyou limit on timestamp, will give the wrong answer in the face of skew).\nAnd that is the algorithm that is sped up by having generation numbers.\n\nSo I do not think they help with (1). You can speed up (1) by storing\ncommit information in a more readily accessible format (e.g., see the\n\"commit metapack\" patches I posted in March or April of this year). But\nyou cannot win all that much here. Try \"git rev-list --all\" on the\nkernel versus \"git rev-list --objects --all\". The former touches only\nthe commits, and takes about 5 seconds. The latter touches all objects\nand takes about 30 seconds. So even if you could make the commit access\nand traversal instantaneous, you could save only 5 out of 30 seconds.\n\nFor (2), I experimented with leaving tree objects uncompressed in the\npack. It does help (and you do not lose much space, because tree objects\ncompress horribly, as they are mostly random sha1 bytes). But not that\nmuch.\n\nFor (3), we keep a cache of delta bases to avoid re-accessing the same\ntree bases over and over. Usually this works fine, but I can into a case\nrecently where \"rev-list --objects\" was halved by bumping\ncore.deltabasecachelimit from its default of 16m to 128m (this\nparticular repository had some large trees, and a very odd pattern of\nmerges that I think made the locality of tree access very poor).\n\nWhich leaves (4), the hash lookup. We have to do a _lot_ of these,\nbecause we have to look up each entry of each tree. So we end up looking\nup the same sha1s over and over again (e.g., we see that \"Makefile\" is at\nsha1 \"1234abcd\", and we output it. Then we go to the tree of the parent\ncommit, and we look at its \"Makefile\" entry. Guess where it almost\ncertainly still points, because any given commit only touches a handful\nof paths?).\n\nThere have been several attempts to make this faster. Micro-optimizing\nhashcmp, which helps a little. I looked at quadratic probing in the hash\ntable, and Junio looked at cuckoo hashing. Neither provided good\nresults. I looked at exploiting locality of the repeated lookups, which\nresulted in 9a41448.\n\nBut ultimately, something like reachability bitmaps is going to perform\na lot better, because you can avoid doing the traversal at all. Another\nsolution which we've discussed but AFAIK nobody has ever implemented is\nhaving a cache to show which entries changed between two trees (e.g.,\nthe tree of a commit and the tree of one of its children). That would\nlet us skip the repeated hash lookups (you would know whether you\nalready processed the child's tree and its entries, and if so, you know\nthat you only need to process the differences to get complete coverage).\n\n\nThat rambled off topic a bit and got long. But you seem to have a lot of\nquestions in this area, so the simplest thing seemed to be to just dump\nthe current state of affairs. I hope it is useful.\n\n-Peff\n"},{"id":"224981","messageId":"CACsJy8BZv0nr92foiYpbscpg86awFZVerpeXcz5CuYWeg3guEA@mail.gmail.com","threadId":"34621","inReplyTo":"20130809221615.GA7160@sigill.intra.peff.net","subject":"Re: [PATCH] git exproll: steps to tackle gc aggression","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-08-10T01:24:39Z","receivedAt":"2013-08-10T01:24:39Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sat, Aug 10, 2013 at 5:16 AM, Jeff King wrote:\n> Another solution could involve not writing the duplicate of Y in the\n> first place. The reason we do not store thin-packs on disk is that you\n> run into problems with cycles in the delta graph (e.g., A deltas against\n> B, which deltas against C, which deltas against A; at one point you had\n> a full copy of one object which let you create the cycle, but you later\n> deleted it as redundant with the delta, and now you cannot reconstruct\n> any of the objects).\n>\n> You could possibly solve this with cycle detection, though it would be\n> complicated (you need to do it not just when getting rid of objects, but\n> when sending a pack, to make sure you don't send a cycle of deltas that\n> the other end cannot use). You _might_ be able to get by with a kind of\n> \"two-level\" hack: consider your main pack as \"group A\" and newly pushed\n> packs as \"group B\". Allow storing thin deltas on disk from group B\n> against group A, but never the reverse (nor within group B). That makes\n> sure you don't have cycles, and it eliminates even more I/O than any\n> repacking solution (because you never write the extra copy of Y to disk\n> in the first place). But I can think of two problems:\n>\n> 1. You still want to repack more often than every 300 packs, because\n> having many packs cost both in space, but also in object lookup\n> time (we can do a log(N) search through each pack index, but have\n> to search linearly through the set of indices).\n>\n> 2. As you accumulate group B packs with new objects, the deltas that\n> people send will tend to be against objects in group B. They are\n> closer to the tip of history, and therefore make better deltas for\n> history built on top.\n>\n> That's all just off the top of my head. There are probably other flaws,\n> too, as I haven't considered it too hard.\n\nSome refinements on this idea\n\n - We could keep packs in group B ordered as the packs come in. The\nnew pack can depend on the previous ones.\n - A group index in addition to separate index for each pack would\nsolve linear search object lookup problem.\n-- \nDuy\n"},{"id":"224985","messageId":"7vbo562k1i.fsf@alter.siamese.dyndns.org","threadId":"34621","inReplyTo":"20130809221615.GA7160@sigill.intra.peff.net","subject":"Re: [PATCH] git exproll: steps to tackle gc aggression","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-08-10T05:26:33Z","receivedAt":"2013-08-10T05:26:33Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> ... The reason we do not store thin-packs on disk is that you\n> run into problems with cycles in the delta graph (e.g., A deltas against\n> B, which deltas against C, which deltas against A; at one point you had\n> a full copy of one object which let you create the cycle, but you later\n> deleted it as redundant with the delta, and now you cannot reconstruct\n> any of the objects).\n\nAs an extension to that is that a thin-pack will make the \"validity\"\nof a single pack dependent on its surroundings, making \"verify-pack\"\nuseless. It may say \"everything is fine\", but corruption of another\npack that holds a base object a delta in it depends on will render\nthe pack unusable.\n\nWith the current arrangement, if you grab a single pack and re-idx\nit, you know you can reconstruct all the objects in it.\n\nThe original reason was not cycles; it was primarily because we did\nnot want to have to map more than one packfile while reconstructing\nthe delta chain for a single object (this was way before the \"open\nsmall mmap windows into a large packfile\" was invented).\n"},{"id":"225000","messageId":"CALkWK0kpqyxTyai2Lue7=D4z0kvhxuxKdYSWekT22zUhRis0Og@mail.gmail.com","threadId":"34621","inReplyTo":"20130809221615.GA7160@sigill.intra.peff.net","subject":"Re: [PATCH] git exproll: steps to tackle gc aggression","fromName":"Ramkumar Ramachandra","fromEmail":"artagnon@gmail.com","sentAt":"2013-08-10T08:42:46Z","receivedAt":"2013-08-10T08:42:46Z","isPatch":true,"sender":{"key":"r@artagnon.com","avatar":"https://avatars.githubusercontent.com/u/37226?v=4"},"body":"Jeff King wrote:\n> [...]\n\nFirst off, thanks for the fabulous writeup. I hope more contributors\nread this, and get interested in tackling the problems.\n\n> You are missing a step in the preparation of the delta list. If we\n> already have a delta on-disk, we will check whether it is usable and\n> keep a note in the list (see check_object). Then when we\n> prepare the list of objects to delta, it is omitted from the list (see\n> prepare_pack).\n\nAh, prepare_pack() calls get_object_details(), which then calls\ncheck_object(): reuse_delta is what I was looking for.\n\n> That is why you may see a much smaller number objects in the progress\n> eye candy for \"Compressing objects...\" than we are actually sending.\n\nI see.\n\n> As Junio mentioned, that is what \"--thin\" is about; the sender omits the\n> base and the receiver adds it back in (\"index-pack --fix-thin\").\n\nYeah, I read about the --thin option. However, it's only for\nnetwork-packs (i.e --stdout; why?). Also, is it turned on by default?\nThe documentation says so, but I ran it and found that the value of\nthin is 0 in builtin/push.c:316. What is going on?\n\n> And if\n> you think about it, that is likely where most of Martin's \"317 packs\n> turned into 8MB\" space savings are coming from.\n\nThin packs have nothing to do with git-exproll per-se, but I think I\nunderstand why pack generations work.\n\n> The reason we do not store thin-packs on disk is that you\n> run into problems with cycles in the delta graph (e.g., A deltas against\n> B, which deltas against C, which deltas against A; at one point you had\n> a full copy of one object which let you create the cycle, but you later\n> deleted it as redundant with the delta, and now you cannot reconstruct\n> any of the objects).\n\nAh, that's why.\n\n> Somebody pushes X, which deltas against Y. They send only the delta for\n> X->Y, but the receiver stores that delta plus a full copy of Y, even\n> though we already have Y in another pack. Repacking throws away the\n> extra copy of Y.\n\nRight, I got that.\n\n> And that is why something like Junio's suggestion of \"do not traverse\n> history; just concatenate the packs and throw away duplicate objects\"\n> might be helpful. You would not find new deltas, but you would get rid\n> of these duplicate objects, and doing so would be relatively cheap.\n\n... but we've already determined that git pack-objects does a good job\nof reusing deltas, so I'm not sure what we can do over and above this.\n\nIf I understand correctly, the proposal is to use existing (but\nsub-optimal) deltas more aggressively when repacking?\n\n> Another solution could involve not writing the duplicate of Y in the\n> first place.\n\n> [...]\n\n> You could possibly solve this with cycle detection, though it would be\n> complicated (you need to do it not just when getting rid of objects, but\n> when sending a pack, to make sure you don't send a cycle of deltas that\n> the other end cannot use). You _might_ be able to get by with a kind of\n> \"two-level\" hack: consider your main pack as \"group A\" and newly pushed\n> packs as \"group B\". Allow storing thin deltas on disk from group B\n> against group A, but never the reverse (nor within group B). That makes\n> sure you don't have cycles, and it eliminates even more I/O than any\n> repacking solution (because you never write the extra copy of Y to disk\n> in the first place). But I can think of two problems:\n\nHm, having two kinds of packs: full packs and thin packs, and\ndifferent codepaths to handle them.\n\n> 1. You still want to repack more often than every 300 packs, because\n> having many packs cost both in space, but also in object lookup\n> time (we can do a log(N) search through each pack index, but have\n> to search linearly through the set of indices).\n\nOnce you narrow it down to a pack-index, you can bisect it since the\ntable is sorted. How do you find the right pack-index though? Do I\nhave to do the bisection-search on each one to see if the object\nexists? Can this be improved by generating a global index for all\npacks that contains packfile-name in addition to offset for each\nobject?\n\n> 2. As you accumulate group B packs with new objects, the deltas that\n> people send will tend to be against objects in group B. They are\n> closer to the tip of history, and therefore make better deltas for\n> history built on top.\n\nActually, I'm not sure it's worth the additional complexity at all.\nKeeping packs self-contained means that simpler code and easier\nisolation in the face of corruption: the space isn't a big trade-off,\nunless there are lots of really tiny packs (in which case we\nconsolidate them into larger packs).\n\nThe way I see it, we'll be saving on some IO by creating thin packs.\nBut the trade-off seems to be quite heavy: self-contained packs means\nthat I can just mmap() that pack-index, look for objects and apply\ndeltas without bothering about any other packs. Thin packs means that\nI'll have to mmap() a lot more than one pack-index, and spend a lot\nmore time searching for the base object to apply the delta to, right?\n\n> That's all just off the top of my head. There are probably other flaws,\n> too, as I haven't considered it too hard. But if you are really\n> concerned about I/O on a busy repo (and I think for hosting sites, it is\n> a real problem), the best-performing solution will probably not involve\n> packs at all, but some kind of delta-capable storage that you can\n> incrementally add to without rewriting the whole repository. The\n> downside is that it would be significantly more complicated.\n\nI think packs are an excellent solution. The reason is quite simple:\nif you use incremental delta storage, those deltas will be useless\n(aka. completely suboptimal) after a few days of additional data.\nGenerating effective deltas is an expensive operation that involves\nlining up objects using heuristics (like size), and sliding windows\nover them to get the most optimal delta. If you generate lots of\nsuboptimal deltas, pack-objects can't reuse them and your server will\nnot be able to do network operations effectively.\n\n> It's actually list-objects.c, and no, it is not unique to packing (you\n> can run the same code with \"git rev-list --objects\"). The CPU time for such\n> a traversal is generally spent in:\n>\n> 1. Accessing commit objects data from disk (this shows up as libz in\n> perf runs).\n>\n> 2. Accessing tree object data from disk (libz again).\n>\n> 3. Reconstructing tree deltas (this shows up as memcpy in perf, but of\n> course we have to access base objects, which increases item 2).\n>\n> 4. Converting sha1s into \"struct object\" via hash table lookup\n> (lookup_object in perf).\n\nMakes sense.\n\n> Generation numbers can make some commit walks faster by cutting off the\n> traversal early. But they don't really apply here, for a few reasons.\n> One, our worst case is actually a full clone or prune, and there is no\n> cutoff; we must go down to the roots. Two, we use commit timestamps as a\n> proxy for generation numbers. Most of the traversal algorithms use the\n> timestamps in a priority queue, and are written such that we always get\n> the right answer in the face of skewed timestamps, but we may go deeper\n> than necessary if they are skewed.\n\nYeah, I noticed. The main advantage of using generation numbers seemed\nto be the elimination of SLOP from revision.c:limit_list(); slightly\ncleaner code, but not much else. I was wondering if there was\nsomething more to it.\n\n> The exception is the depth-first\n> \"tag --contains\" algorithm, which typically goes to the roots (and if\n> you limit on timestamp, will give the wrong answer in the face of skew).\n> And that is the algorithm that is sped up by having generation numbers.\n\nAh, I see.\n\n> So I do not think they help with (1). You can speed up (1) by storing\n> commit information in a more readily accessible format (e.g., see the\n> \"commit metapack\" patches I posted in March or April of this year). But\n> you cannot win all that much here. Try \"git rev-list --all\" on the\n> kernel versus \"git rev-list --objects --all\". The former touches only\n> the commits, and takes about 5 seconds. The latter touches all objects\n> and takes about 30 seconds. So even if you could make the commit access\n> and traversal instantaneous, you could save only 5 out of 30 seconds.\n\nOh, ouch. I haven't gotten around to reading the \"commit metapack\" series yet.\n\n> For (2), I experimented with leaving tree objects uncompressed in the\n> pack. It does help (and you do not lose much space, because tree objects\n> compress horribly, as they are mostly random sha1 bytes). But not that\n> much.\n\nInteresting point: tree objects cannot be compressed: if I do one\nfile/directory rename, the old 20-byte hash and new 20-byte hash have\nno relationship to each other: so, we're wasting time trying to find\npatterns (for compression) in trees. But yeah, eliminating tree\ncompression might not help much, because there are so few trees: on a\ntypical repository, there are very few renames.\n\n> For (3), we keep a cache of delta bases to avoid re-accessing the same\n> tree bases over and over. Usually this works fine, but I can into a case\n> recently where \"rev-list --objects\" was halved by bumping\n> core.deltabasecachelimit from its default of 16m to 128m (this\n> particular repository had some large trees, and a very odd pattern of\n> merges that I think made the locality of tree access very poor).\n\nYeah, I saw the LRU delta_base_cache in sha1_file.c. It's probably\nalready as optimal as it can be.\n\n> Which leaves (4), the hash lookup. We have to do a _lot_ of these,\n> because we have to look up each entry of each tree. So we end up looking\n> up the same sha1s over and over again (e.g., we see that \"Makefile\" is at\n> sha1 \"1234abcd\", and we output it. Then we go to the tree of the parent\n> commit, and we look at its \"Makefile\" entry. Guess where it almost\n> certainly still points, because any given commit only touches a handful\n> of paths?).\n>\n> There have been several attempts to make this faster. Micro-optimizing\n> hashcmp, which helps a little. I looked at quadratic probing in the hash\n> table, and Junio looked at cuckoo hashing. Neither provided good\n> results. I looked at exploiting locality of the repeated lookups, which\n> resulted in 9a41448.\n\nTo lower the cost of linear lookup during a collision, you move the\nobject you hit up the chain for subsequent lookups. Very interesting.\n\n> But ultimately, something like reachability bitmaps is going to perform\n> a lot better, because you can avoid doing the traversal at all. Another\n> solution which we've discussed but AFAIK nobody has ever implemented is\n> having a cache to show which entries changed between two trees (e.g.,\n> the tree of a commit and the tree of one of its children). That would\n> let us skip the repeated hash lookups (you would know whether you\n> already processed the child's tree and its entries, and if so, you know\n> that you only need to process the differences to get complete coverage).\n\nIt'll take me some time to digest this information and come up with\nquestions/ patches.\n\nThanks for the food for thought.\n"},{"id":"225001","messageId":"CACsJy8DtiSupsvDgeBXGGnGE06pDxWvYTNrk3bpta9Bwk5MZwg@mail.gmail.com","threadId":"34621","inReplyTo":"CALkWK0kpqyxTyai2Lue7=D4z0kvhxuxKdYSWekT22zUhRis0Og@mail.gmail.com","subject":"Re: [PATCH] git exproll: steps to tackle gc aggression","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-08-10T09:24:48Z","receivedAt":"2013-08-10T09:24:48Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sat, Aug 10, 2013 at 3:42 PM, Ramkumar Ramachandra\n wrote:\n>> As Junio mentioned, that is what \"--thin\" is about; the sender omits the\n>> base and the receiver adds it back in (\"index-pack --fix-thin\").\n>\n> Yeah, I read about the --thin option. However, it's only for\n> network-packs (i.e --stdout; why?). Also, is it turned on by default?\n> The documentation says so, but I ran it and found that the value of\n> thin is 0 in builtin/push.c:316. What is going on?\n\n--thin is enabled by default for fetch (see\ntransport.c:transport_get()) but it's only effective when the server\nadvertises \"thin-pack\" capability (see protocol-capabilities.txt).\npush has --thin turned off by default favoring server resources over\nnetwork traffic, see a4503a1 (Make --no-thin the default in git-push\nto save server resources - 2007-09-09)\n-- \nDuy\n"},{"id":"225002","messageId":"CACsJy8CBBy+T4XtRSRT4WONRfGEuZbXPaNGAbROeRUPvyNHU3Q@mail.gmail.com","threadId":"34621","inReplyTo":"CACsJy8DtiSupsvDgeBXGGnGE06pDxWvYTNrk3bpta9Bwk5MZwg@mail.gmail.com","subject":"Re: [PATCH] git exproll: steps to tackle gc aggression","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-08-10T09:28:58Z","receivedAt":"2013-08-10T09:28:58Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sat, Aug 10, 2013 at 4:24 PM, Duy Nguyen wrote:\n> push has --thin turned off by default favoring server resources over\n> network traffic, see a4503a1 (Make --no-thin the default in git-push\n> to save server resources - 2007-09-09)\n\nSide note, I think the server should be able to control the default\nbehavior. Maybe if the server advertises \"thin-pack\" capability and\nthe user does not explicitly specify --no-thin, then --thin is\nautomatically turned on at the client.\n-- \nDuy\n"},{"id":"225003","messageId":"20130810093827.GA2518@sigill.intra.peff.net","threadId":"34621","inReplyTo":"CALkWK0kpqyxTyai2Lue7=D4z0kvhxuxKdYSWekT22zUhRis0Og@mail.gmail.com","subject":"Re: [PATCH] git exproll: steps to tackle gc aggression","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-08-10T09:38:28Z","receivedAt":"2013-08-10T09:38:28Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Aug 10, 2013 at 02:12:46PM +0530, Ramkumar Ramachandra wrote:\n\n> First off, thanks for the fabulous writeup. I hope more contributors\n> read this, and get interested in tackling the problems.\n\nYou're welcome. I'll just respond to a few questions/points you raised\nin your response:\n\n> Yeah, I read about the --thin option. However, it's only for\n> network-packs (i.e --stdout; why?). Also, is it turned on by default?\n> The documentation says so, but I ran it and found that the value of\n> thin is 0 in builtin/push.c:316. What is going on?\n\nI'm not sure whether \"push --thin\" actually does anything anymore. It\nlooks like we always turn on thin-packs for the git transport in\ntransport_get, and have ever since 9b28851 (Push code for transport\nlibrary, 2007-09-10). And you cannot turn off thin-packing with\n\"--no-thin\".\n\nSo I suspect it is historical cruft at this point.\n\n> > And if\n> > you think about it, that is likely where most of Martin's \"317 packs\n> > turned into 8MB\" space savings are coming from.\n> \n> Thin packs have nothing to do with git-exproll per-se, but I think I\n> understand why pack generations work.\n\nI think it matters in terms of understanding the workload, and why the\nrepo benefits from repacking. In a normal git repo that accumulates\npacks via incremental \"git repack\" (e.g., by running \"gc --auto\" until\nwe hit the pack limit), you will not have duplicate objects (only\nobjects which could be delta'd across the pack boundary but are not).\nBut if you accumulate packs by repeated thin-pack pushing, you will have\ngood deltas, but extra copies of base objects.\n\n> > And that is why something like Junio's suggestion of \"do not traverse\n> > history; just concatenate the packs and throw away duplicate objects\"\n> > might be helpful. You would not find new deltas, but you would get rid\n> > of these duplicate objects, and doing so would be relatively cheap.\n> \n> ... but we've already determined that git pack-objects does a good job\n> of reusing deltas, so I'm not sure what we can do over and above this.\n\nIf I understand the proposal correctly, the problem space is something\nlike:\n\n A fully packed repository is the best way to store objects, both in\n terms of space efficiency and for delta reuse when clients fetch from\n us. But it is too expensive to do a full repack after each push. What\n makes it expensive, and how can we get around that?\n\nI think the answer to \"why is it expensive\" is two-fold:\n\n 1. We spend a lot of CPU on history traversal. Even if we have only 10\n new commits to pack, we have to traverse the _whole_ history to\n generate the pack.\n\n 2. We spend some CPU on delta compression. This scales nicely (10\n commits means we only do deltas for those 10 commits).\n\n 3. We do a lot of I/O, as we rewrite the whole of the old pack content\n into the new pack, along with the extra objects (so again, we might\n rewrite millions of objects just to add 10 more to the pack).\n\nI do not think (2) is that big a deal. It scales nicely already, and the\ndeltas you get are worth it (and you would have to compute them on the\nfly for the next clone anyway). But (1) and (3) are bad, because they\nare based on the size of the repository, not the size of the new\ncontent.\n\nIf we were to simply append the objects from the new packs onto\nthe big, old pack, dropping any duplicates but retaining the deltas we\nhave, we would make (1) and (3) go away. Our pack probably wouldn't be\nas good as a \"real\" repack, as it would potentially contain unreachable\nobjects, and we might miss some delta opportunities. But we could\ncheaply run the \"concatenate\" repack after each push, and then do a real\nrepack less frequently.\n\nI am not sure if that is exactly what Junio is proposing. There are some\nlogistical complications (fixing up the pack header and footer, along\nwith the filename, and updating the pack index).\n\n> > 1. You still want to repack more often than every 300 packs, because\n> > having many packs cost both in space, but also in object lookup\n> > time (we can do a log(N) search through each pack index, but have\n> > to search linearly through the set of indices).\n> \n> Once you narrow it down to a pack-index, you can bisect it since the\n> table is sorted. How do you find the right pack-index though? Do I\n> have to do the bisection-search on each one to see if the object\n> exists? Can this be improved by generating a global index for all\n> packs that contains packfile-name in addition to offset for each\n> object?\n\nRight. The bisection-search is the \"log(N)\" I mention above; you can do\nthat on each pack index. But you have to search the packs linearly,\nsince there is no indication of which pack the object might be found in.\n\nA global index would solve that. Right now, the way to create such an\nindex is \"git repack -ad\". :)\n\nBut there is nothing to say that we could not have a meta-index on top\nof the existing pack indices (however it does introduce complications\nwith lifetimes, as right now we can delete redundant packs and their\nindices).\n\n> > 2. As you accumulate group B packs with new objects, the deltas that\n> > people send will tend to be against objects in group B. They are\n> > closer to the tip of history, and therefore make better deltas for\n> > history built on top.\n> \n> Actually, I'm not sure it's worth the additional complexity at all.\n\nOh, I'm not either. I was mostly thinking out loud. :)\n\n> Keeping packs self-contained means that simpler code and easier\n> isolation in the face of corruption: the space isn't a big trade-off,\n> unless there are lots of really tiny packs (in which case we\n> consolidate them into larger packs).\n\nExactly. The system right now is simple and robust, even if it has some\ninefficiencies.\n\n> The way I see it, we'll be saving on some IO by creating thin packs.\n> But the trade-off seems to be quite heavy: self-contained packs means\n> that I can just mmap() that pack-index, look for objects and apply\n> deltas without bothering about any other packs. Thin packs means that\n> I'll have to mmap() a lot more than one pack-index, and spend a lot\n> more time searching for the base object to apply the delta to, right?\n\nYes. Right now when we search for a base, we know it is in the same\npack. So right now if you have N packs, we might do N binary searches to\nlook up a single object. But with cross-pack deltas, we might do N\nsearches per delta link; an object with a 50-deep delta chain might do\n50N such lookups.\n\nSo any solution along these lines would probably want to have a global\nindex for the thin packs, or some other way of mitigating this.\n\n> I think packs are an excellent solution. The reason is quite simple:\n> if you use incremental delta storage, those deltas will be useless\n> (aka. completely suboptimal) after a few days of additional data.\n> Generating effective deltas is an expensive operation that involves\n> lining up objects using heuristics (like size), and sliding windows\n> over them to get the most optimal delta. If you generate lots of\n> suboptimal deltas, pack-objects can't reuse them and your server will\n> not be able to do network operations effectively.\n\nI don't know that the deltas are useless or suboptimal after a few days.\nYes, we might have better deltas if we did a full repack, but I think it\nwould very much depend on the workload and the quality of deltas the\nclients are pushing to you.\n\nHowever, there is one thing we didn't talk about yet: the direction of\ndeltas. When we repack, we try to store the most recent items as bases,\nand then delta going further back in history. This makes accessing\nrecent objects (which most workloads should do more of) cheaper, and I\nimagine it helps with the delta base cache, too (since we traverse\nbackwards in time).\n\nBut deltas you get from other packs may not be in that order (in fact,\nif they are from thin packs, they are almost certainly in the opposite\norder, as the server and client have some shared objects that are older,\nand then the client pushes a delta for the new object against the old).\n\n> Interesting point: tree objects cannot be compressed: if I do one\n> file/directory rename, the old 20-byte hash and new 20-byte hash have\n> no relationship to each other: so, we're wasting time trying to find\n> patterns (for compression) in trees. But yeah, eliminating tree\n> compression might not help much, because there are so few trees: on a\n> typical repository, there are very few renames.\n\nThere are a lot of trees in a typical repository. The breakdown of\nobjects in the kernel is:\n\n blob 992707 (30%)\n commit 417959 (13%)\n tree 1898643 (57%)\n\nThe reason there are more trees than blobs is that the sha1 changes\ncascade through the hierarchy. If you put a new blob in foo/bar/baz,\nwe need to update the foo/bar, foo, and root trees.\n\nI think dropping tree compression _does_ help; it's just that zlib\ninflation is already reasonably fast, and our time is dominated by the\nhash table performance. I posted some numbers a while back here:\n\n http://article.gmane.org/gmane.comp.version-control.git/212278\n\nIt uses about 3% more disk space, but \"--objects\" traversals are about\n10-20% faster.\n\nI didn't measure the time to _create_ packs, though. We would be\navoiding zlib deflate there, which is much more expensive than inflate.\nStill, I don't think that zlib is all that big a deal when creating\npacks; most of the time goes to the traversal and to looking for deltas.\n\n-Peff\n"},{"id":"225004","messageId":"20130810094339.GB2518@sigill.intra.peff.net","threadId":"34621","inReplyTo":"CACsJy8DtiSupsvDgeBXGGnGE06pDxWvYTNrk3bpta9Bwk5MZwg@mail.gmail.com","subject":"Re: [PATCH] git exproll: steps to tackle gc aggression","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-08-10T09:43:40Z","receivedAt":"2013-08-10T09:43:40Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Aug 10, 2013 at 04:24:48PM +0700, Nguyen Thai Ngoc Duy wrote:\n\n> > Yeah, I read about the --thin option. However, it's only for\n> > network-packs (i.e --stdout; why?). Also, is it turned on by default?\n> > The documentation says so, but I ran it and found that the value of\n> > thin is 0 in builtin/push.c:316. What is going on?\n> \n> --thin is enabled by default for fetch (see\n> transport.c:transport_get()) but it's only effective when the server\n> advertises \"thin-pack\" capability (see protocol-capabilities.txt).\n> push has --thin turned off by default favoring server resources over\n> network traffic, see a4503a1 (Make --no-thin the default in git-push\n> to save server resources - 2007-09-09)\n\nHmm. I don't think that is the case anymore.\n\nIf I do:\n\n git init parent &&\n (cd parent && seq 1 10000 >file &&\n git add file && git commit -m base\n ) &&\n git clone parent child &&\n cd child && seq 1 10001 >file &&\n git commit -a -m more &&\n GIT_TRACE=1 git push origin HEAD:foo\n\nI see:\n\n trace: run_command: 'pack-objects' '--all-progress-implied' '--revs'\n '--stdout' '--thin' '--delta-base-offset' '--progress'\n\n-Peff\n"},{"id":"225005","messageId":"20130810095000.GC2518@sigill.intra.peff.net","threadId":"34621","inReplyTo":"CACsJy8BZv0nr92foiYpbscpg86awFZVerpeXcz5CuYWeg3guEA@mail.gmail.com","subject":"Re: [PATCH] git exproll: steps to tackle gc aggression","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-08-10T09:50:00Z","receivedAt":"2013-08-10T09:50:00Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Aug 10, 2013 at 08:24:39AM +0700, Nguyen Thai Ngoc Duy wrote:\n\n> > the other end cannot use). You _might_ be able to get by with a kind of\n> > \"two-level\" hack: consider your main pack as \"group A\" and newly pushed\n> > packs as \"group B\". Allow storing thin deltas on disk from group B\n> > against group A, but never the reverse (nor within group B). That makes\n> > sure you don't have cycles, and it eliminates even more I/O than any\n> > repacking solution (because you never write the extra copy of Y to disk\n> > in the first place). But I can think of two problems:\n> [...]\n> \n> Some refinements on this idea\n> \n> - We could keep packs in group B ordered as the packs come in. The\n> new pack can depend on the previous ones.\n\nI think you could dispense with the two-level altogether and simply give\na definite ordering to packs, whereby newer packs can only depend on\nolder packs. Enforcing that with filesystem mtime feels a bit\nerror-prone; I think you'd want to explicitly store a counter somewhere.\n\n> - A group index in addition to separate index for each pack would\n> solve linear search object lookup problem.\n\nYeah. I do not even think it would be that much work. It is a pure\noptimization, so you can ignore issues like \"what happens if I search\nfor an object, but the pack it is supposed to be in went away?\". The\nanswer is \"you fall back to a linear search through the packs\", and\nassume it happens infrequently enough not to care.\n\nI'd wait to see how other proposed optimizations work out before doing a\nglobal index, though. The current wisdom is \"don't have a ton of packs,\nfor both the index issue and other reasons, like wasting space and\non-the-fly deltas for fetches\". If the \"other reasons\" go away, then a\nglobal index would make sense to solve the remaining issue. But if the\nsolution for the other issues is to make it cheaper to repack so you can\ndo it more often, then the index issue just goes away.\n\n-Peff\n"},{"id":"225006","messageId":"CACsJy8CPM2jwWu0g+mamnA89UtWR=3B=8Q+j2mu-CMB=TRm7Og@mail.gmail.com","threadId":"34621","inReplyTo":"20130810094339.GB2518@sigill.intra.peff.net","subject":"Re: [PATCH] git exproll: steps to tackle gc aggression","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-08-10T09:50:15Z","receivedAt":"2013-08-10T09:50:15Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sat, Aug 10, 2013 at 4:43 PM, Jeff King wrote:\n>> push has --thin turned off by default favoring server resources over\n>> network traffic, see a4503a1 (Make --no-thin the default in git-push\n>> to save server resources - 2007-09-09)\n>\n> Hmm. I don't think that is the case anymore.\n>\n> If I do:\n>\n> git init parent &&\n> (cd parent && seq 1 10000 >file &&\n> git add file && git commit -m base\n> ) &&\n> git clone parent child &&\n> cd child && seq 1 10001 >file &&\n> git commit -a -m more &&\n> GIT_TRACE=1 git push origin HEAD:foo\n>\n> I see:\n>\n> trace: run_command: 'pack-objects' '--all-progress-implied' '--revs'\n> '--stdout' '--thin' '--delta-base-offset' '--progress'\n>\n\nRight. transport_get() is also run for push and it sets\nsmart_options->thin = 1 unconditionally. Thanks for correcting.\n-- \nDuy\n"},{"id":"225008","messageId":"CALkWK0=cZyKO7tjjtgE+tvwkkHGN7xLUy0uKHwXd8zkrM7o2Wg@mail.gmail.com","threadId":"34621","inReplyTo":"CACsJy8CPM2jwWu0g+mamnA89UtWR=3B=8Q+j2mu-CMB=TRm7Og@mail.gmail.com","subject":"Re: [PATCH] git exproll: steps to tackle gc aggression","fromName":"Ramkumar Ramachandra","fromEmail":"artagnon@gmail.com","sentAt":"2013-08-10T10:05:50Z","receivedAt":"2013-08-10T10:05:50Z","isPatch":true,"sender":{"key":"r@artagnon.com","avatar":"https://avatars.githubusercontent.com/u/37226?v=4"},"body":"Duy Nguyen wrote:\n> Right. transport_get() is also run for push and it sets\n> smart_options->thin = 1 unconditionally.\n\nSo, it looks like smart http implies the thin capability. I think\nsop's patch (6 years ago) was about turning off thin on dumb http: can\nwe check that before deciding that push --[no-]thin is historical\ncruft?\n\nAlso, a documentation update is required.\n"},{"id":"225010","messageId":"CACsJy8AnY0pgHSxYDvqLonojGxSyAXUCGwzWwuZWQRVwAVnsFg@mail.gmail.com","threadId":"34621","inReplyTo":"CALkWK0=cZyKO7tjjtgE+tvwkkHGN7xLUy0uKHwXd8zkrM7o2Wg@mail.gmail.com","subject":"Re: [PATCH] git exproll: steps to tackle gc aggression","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-08-10T10:16:00Z","receivedAt":"2013-08-10T10:16:00Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sat, Aug 10, 2013 at 5:05 PM, Ramkumar Ramachandra\n wrote:\n> Duy Nguyen wrote:\n>> Right. transport_get() is also run for push and it sets\n>> smart_options->thin = 1 unconditionally.\n>\n> So, it looks like smart http implies the thin capability.\n\n\"smart_options\" is a bit misleading. This applies to both smart\nhttp://, git:// and ssh://\n\n> I think\n> sop's patch (6 years ago) was about turning off thin on dumb http\n\nNo, dumb http walks through the remote repository object database,\nthere's no temporary pack created for transferring data. Dumb http has\nnothing to do with this flag.\n-- \nDuy\n"}]}