{"thread":{"id":"35203","subject":"What's cooking in git.git (Oct 2013, #06; Fri, 25)","startedAt":"2013-10-25T23:23:55Z","lastAt":"2013-11-14T19:38:01Z","messageCount":9,"participants":["Junio C Hamano","Duy Nguyen","Vicent Martí","Karsten Blees"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"229537","messageId":"xmqqeh79hr3o.fsf@gitster.dls.corp.google.com","threadId":"35203","inReplyTo":null,"subject":"What's cooking in git.git (Oct 2013, #06; Fri, 25)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-10-25T23:23:55Z","receivedAt":"2013-10-25T23:23:55Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Here are the topics that have been cooking.  Commits prefixed with\n'-' are only in 'pu' (proposed updates) while commits prefixed with\n'+' are in 'next'.\n\nYou can find the changes described here in the integration branches\nof the repositories listed at\n\n    http://git-blame.blogspot.com/p/git-public-repositories.html\n\n--------------------------------------------------\n[New Topics]\n\n* bc/http-100-continue (2013-10-23) 1 commit\n - http: add option to enable 100 Continue responses\n\n Conditionally allow \"100 Continue\" responses to help use of\n GSS-Negotiate authentication scheme over HTTP transport.\n\n Seems to be still under discussion.\n\n\n* jc/merge-base-reflog (2013-10-25) 2 commits\n - merge-base: teach \"--fork-point\" mode\n - merge-base: use OPT_CMDMODE and clarify the command line parsing\n\n Code the logic in \"pull --rebase\" that figures out a fork point\n from reflog entries in C.\n\n\n* jk/date-c-double-semicolon (2013-10-24) 1 commit\n - drop redundant semicolon in empty while\n\n Will merge to 'next'.\n\n\n* jk/for-each-ref-skip-parsing (2013-10-24) 1 commit\n - for-each-ref: avoid loading objects to print %(objectname)\n\n Will merge to 'next'.\n\n\n* jk/pack-bitmap (2013-10-25) 19 commits\n - pack-bitmap: implement optional name_hash cache\n - t: add basic bitmap functionality tests\n - repack: consider bitmaps when performing repacks\n - repack: handle optional files created by pack-objects\n - repack: turn exts array into array-of-struct\n - repack: stop using magic number for ARRAY_SIZE(exts)\n - pack-objects: implement bitmap writing\n - rev-list: add bitmap mode to speed up object lists\n - pack-objects: use bitmaps when packing objects\n - pack-bitmap: add support for bitmap indexes\n - documentation: add documentation for the bitmap format\n - ewah: compressed bitmap implementation\n - compat: add endianness helpers\n - sha1_file: export `git_open_noatime`\n - revision: allow setting custom limiter function\n - pack-objects: factor out name_hash\n - pack-objects: refactor the packing list\n - revindex: export new APIs\n - sha1write: make buffer const-correct\n\n Borrows the bitmap index into packfiles from JGit to speed up\n enumeration of objects involved in a commit range without having to\n fully traverse the history.\n\n\n* jk/refs-c-squelch-gcc (2013-10-24) 1 commit\n - silence gcc array-bounds warning\n\n Will merge to 'next'.\n\n\n* jk/robustify-parse-commit (2013-10-24) 6 commits\n - checkout: do not die when leaving broken detached HEAD\n - use parse_commit_or_die instead of custom message\n - use parse_commit_or_die instead of segfaulting\n - assume parse_commit checks for NULL commit\n - assume parse_commit checks commit->object.parsed\n - log_tree_diff: die when we fail to parse a commit\n\n Will merge to 'next' after taking another look.\n\n\n* mh/fetch-tags-in-addition-to-normal-refs (2013-10-24) 16 commits\n - fetch, remote: properly convey --no-prune options to subprocesses\n - builtin/remote.c:update(): use struct argv_array\n - builtin/remote.c: reorder function definitions\n - query_refspecs(): move some constants out of the loop\n - fetch --prune: prune only based on explicit refspecs\n - SQUASH??? --tags is no longer a short-hand\n - fetch --tags: fetch tags *in addition to* other stuff\n - builtin/fetch.c: reorder function definitions\n - ref_remove_duplicates(): improve documentation comment\n - ref_remove_duplicates(): simplify function\n - ref_remove_duplicates(): avoid redundant bisection\n - get_ref_map(): rename local variables\n - api-remote.txt: correct section \"struct refspec\"\n - t5510: check that \"git fetch --prune --tags\" does not prune branches\n - t5510: prepare test refs more straightforwardly\n - t5510: use the correct tag name in test\n\n Some questionable paragraphs in the doc updates, but other than\n that looks reasonably solid.\n\n\n* nd/lift-path-max (2013-10-24) 2 commits\n - checkout_entry(): clarify the use of topath[] parameter\n - entry.c: convert checkout_entry to use strbuf\n\n Will merge to 'next'.\n\n\n* jk/pack-corruption-post-mortem (2013-10-25) 1 commit\n - howto: add article on recovering a corrupted object\n\n Will merge to 'next'.\n\n\n* jk/reset-p-current-head-fix (2013-10-25) 2 commits\n - reset: pass real rev name to add--interactive\n - add-interactive: handle unborn branch in patch mode\n\n \"git reset -p HEAD\" has codepath to special case it from resetting\n to contents of other commits, but recent change broke it.\n\n Will merge to 'next'.\n\n\n* mf/graph-show-root (2013-10-25) 1 commit\n - graph.c: mark root commit differently\n\n Needs adjustments to some tests.\n\n\n* nv/parseopt-opt-arg (2013-10-25) 1 commit\n - rev-parse --parseopt: add the --sticked-long mode\n\n Enhance \"rev-parse --parseopt\" mode to help parsing options with\n an optional parameter.\n\n--------------------------------------------------\n[Stalled]\n\n* np/pack-v4 (2013-09-18) 90 commits\n . packv4-parse.c: add tree offset caching\n . t1050: replace one instance of show-index with verify-pack\n . index-pack, pack-objects: allow creating .idx v2 with .pack v4\n . unpack-objects: decode v4 trees\n . unpack-objects: allow to save processed bytes to a buffer\n - ...\n\n Nico and Duy advancing the eternal vaporware pack-v4.  This is here\n primarily for wider distribution of the preview edition.\n\n Temporarily ejected from 'pu', to try out jk/pack-bitmap, which\n this topic conflicts with.\n\n\n* sc/doc-howto-dumb-http (2013-10-16) 1 commit\n . doc/howto: warn about (dumb)http server document being too old\n\n The new text needs to go somewhere in the body of the document,\n not before the title line.\n\n\n* tg/perf-lib-test-perf-cleanup (2013-09-19) 2 commits\n - perf-lib: add test_perf_cleanup target\n - perf-lib: split starting the test from the execution\n\n Add test_perf_cleanup shell function to the perf suite, that allows\n the script writers to define a test with a clean-up action.\n\n Holding until needed.\n\n\n* yt/shortened-rename (2013-10-18) 2 commits\n - SQUASH??? style fixes and s/omit/shorten/ where appropriate\n - diff.c: keep arrow(=>) on show_stats()'s shortened filename part to make rename visible\n\n Attempts to give more weight on the fact that a filepair represents\n a rename than showing substring of the actual path when diffstat\n lines are not wide enough.\n\n I am not sure if that is solving a right problem, though.\n\n\n* tr/merge-recursive-index-only (2013-07-07) 3 commits\n - merge-recursive: -Xindex-only to leave worktree unchanged\n - merge-recursive: untangle double meaning of o->call_depth\n - merge-recursive: remove dead conditional in update_stages()\n\n Holding until there is a caller to learn from.\n\n\n* jc/ref-excludes (2013-09-03) 2 commits\n - document --exclude option\n - revision: introduce --exclude=<glob> to tame wildcards\n\n People often wished a way to tell \"git log --branches\" (and \"git\n log --remotes --not --branches\") to exclude some local branches\n from the expansion of \"--branches\" (similarly for \"--tags\", \"--all\"\n and \"--glob=<pattern>\").  Now they have one.\n\n Needs a matching change to rev-parse.\n\n\n* rv/send-email-cache-generated-mid (2013-08-21) 2 commits\n - git-send-email: Cache generated message-ids, use them when prompting\n - git-send-email: add optional 'choices' parameter to the ask sub\n\n\n* rj/read-default-config-in-show-ref-pack-refs (2013-06-17) 3 commits\n - ### DONTMERGE: needs better explanation on what config they need\n - pack-refs.c: Add missing call to git_config()\n - show-ref.c: Add missing call to git_config()\n\n The changes themselves are probably good, but it is unclear what\n basic setting needs to be read for which exact operation.\n\n Waiting for clarification.\n $gmane/228294\n\n\n* jc/format-patch (2013-04-22) 2 commits\n - format-patch: --inline-single\n - format-patch: rename \"no_inline\" field\n\n A new option to send a single patch to the standard output to be\n appended at the bottom of a message.  I personally have no need for\n this, but it was easy enough to cobble together.  Tests, docs and\n stripping out more MIMEy stuff are left as exercises to interested\n parties.\n\n\n* jk/gitweb-utf8 (2013-04-08) 4 commits\n - gitweb: Fix broken blob action parameters on blob/commitdiff pages\n - gitweb: Don't append ';js=(0|1)' to external links\n - gitweb: Make feed title valid utf8\n - gitweb: Fix utf8 encoding for blob_plain, blobdiff_plain, commitdiff_plain, and patch\n\n Various fixes to gitweb.\n\n Drew Northup volunteered to take a look into this.\n $gmane/226216\n\n\n* jc/show-branch (2013-06-07) 5 commits\n - show-branch: use commit slab to represent bitflags of arbitrary width\n - show-branch.c: remove \"all_mask\"\n - show-branch.c: abstract out \"flags\" operation\n - show-branch.c: lift all_mask/all_revs to a global static\n - show-branch.c: update comment style\n\n Waiting for the final step to lift the hard-limit before sending it out.\n\n--------------------------------------------------\n[Cooking]\n\n* ap/remote-hg-unquote-cquote (2013-10-23) 1 commit\n - remote-hg: unquote C-style paths when exporting\n\n A fast-import stream expresses a pathname with funny characters by\n quoting them in C style; remote-hg remote helper forgot to unquote\n such a path.\n\n Will merge to 'next'.\n\n\n* jl/pack-transfer-avoid-double-close (2013-10-23) 1 commit\n - Clear fd after closing to avoid double-close error\n\n The codepath that send_pack() calls pack_objects() mistakenly\n closed the same file descriptor twice, leading to potentially\n closing a wrong file descriptor that was opened in the meantime.\n\n Will merge to 'next'.\n Needs to be merged later to 'maint'.\n\n\n* nd/magic-pathspec (2013-10-22) 1 commit\n - Fix calling parse_pathspec with no paths nor PATHSPEC_PREFER_* flags\n\n All callers to parse_pathspec() must choose between getting no\n pathspec or one path that is limited to the current directory\n when there is no paths given on the command line, but there were\n two callers that violated this rule, triggering a BUG().\n\n Will merge to 'next'.\n\n\n* sb/git-svn-docs-indent-with-ht (2013-10-22) 1 commit\n - git-svn docs: Use tabs consistently within the ascii doc\n\n Will merge to 'next'.\n\n\n* tr/gitk-doc-update (2013-10-22) 1 commit\n - Documentation: revamp gitk(1)\n\n Will merge to 'next'.\n\n\n* tr/valgrind-test-fix (2013-10-22) 2 commits\n - Revert \"test-lib: allow prefixing a custom string before \"ok N\" etc.\"\n - Revert \"test-lib: support running tests under valgrind in parallel\"\n\n Will merge to 'next'.\n\n\n* sb/repack-in-c (2013-10-22) 1 commit\n  (merged to 'next' on 2013-10-23 at 5d7ac72)\n + Reword repack documentation to no longer state it's a script\n\n Finishing touches to update documentation.\n\n Will merge to 'master'.\n\n\n* mm/checkout-auto-track-fix (2013-10-18) 2 commits\n - checkout: proper error message on 'git checkout foo bar --'\n - checkout: allow dwim for branch creation for \"git checkout $branch --\"\n\n \"git checkout topic\", when there is not yet a local \"topic\" branch\n but there is a unique remote-tracking branch for a remote \"topic\"\n branch, pretended as if \"git checkout -t -b topic remote/$r/topic\"\n (for that unique remote $r) was run. This hack however was not\n implemented for \"git checkout topic --\".\n\n Will merge to 'next'.\n\n\n* hn/log-graph-color-octopus (2013-10-18) 1 commit\n - graph: fix coloring around octopus merges\n\n Will merge to 'next'.\n\n\n* nd/gc-lock-against-each-other (2013-10-18) 1 commit\n - gc: remove gc.pid file at end of execution\n\n Will merge to 'next'.\n\n\n* fc/styles (2013-10-16) 7 commits\n - block-sha1/sha1.c: have SP around arithmetic operators\n - base85.c: have SP around arithmetic operators\n - archive.c: have SP around arithmetic operators\n - alloc.c: have SP around arithmetic operators\n - abspath.c: have SP around arithmetic operators\n - alias: have SP around arithmetic operators\n - C: have space around && and || operators\n\n C coding style fixes.  The ones near the tip have not been sent to\n the list yet (they cover the same kind of style violation as the\n second one) and I should send them to the list.\n\n Will merge to 'next'.\n\n\n* jk/remote-literal-string-leakfix (2013-10-15) 1 commit\n  (merged to 'next' on 2013-10-18 at 6abddac)\n + remote: do not copy \"origin\" string literal\n\n Will merge to 'master'.\n\n\n* jk/split-broken-ident (2013-10-15) 1 commit\n  (merged to 'next' on 2013-10-18 at 8f4b8b7)\n + split_ident: parse timestamp from end of line\n\n Make the fall-back parsing of commit objects with broken author or\n committer lines more robust to pick up the timestamps.\n\n Will merge to 'master'.\n\n\n* sg/prompt-svn-remote-fix (2013-10-15) 1 commit\n  (merged to 'next' on 2013-10-18 at 20b47eb)\n + bash prompt: don't use '+=' operator in show upstream code path\n\n Bash portability fix.\n\n Will merge to 'master'.\n\n\n* sg/t3600-nul-sha1-fix (2013-10-16) 1 commit\n - t3600: fix broken \"choking git rm\" test\n\n Will merge to 'next'.\n\n\n* ak/submodule-foreach-quoting (2013-09-27) 1 commit\n  (merged to 'next' on 2013-10-14 at d77c5f1)\n + submodule foreach: skip eval for more than one argument\n\n A behavior change, but a worthwhile one: \"git submodule foreach\"\n was treating its arguments as part of a single command to be\n concatenated and passed to a shell, making writing buggy\n scripts too easy.\n\n This patch preserves the old \"just pass it to the shell\" behavior\n when a single argument is passed to 'git submodule foreach' and\n moves to a new \"skip the shell and use the arguments passed\n unmolested\" behavior when more than one argument is passed.\n\n The old behavior (always concatenating and passing to the shell)\n was similar to the 'ssh' command, while the new behavior (switching\n on the number of arguments) is what 'xterm -e' does.\n\n May need more thought to make sure this change is advertised well\n so that scripts that used multiple arguments but added their own\n extra layer of quoting are not broken.\n\n Will cook in 'next' for the rest of this cycle.\n\n\n* ew/keepalive (2013-10-16) 2 commits\n  (merged to 'next' on 2013-10-16 at 56fd9f3)\n + http: use curl's tcp keepalive if available\n  (merged to 'next' on 2013-10-14 at 24d786f)\n + http: enable keepalive on TCP sockets\n\n Will merge to 'master'.\n\n\n* jk/http-auth-redirects (2013-10-24) 10 commits\n  (merged to 'next' on 2013-10-24 at 4bebb66)\n + http.c: Spell the null pointer as NULL\n + remote-curl: rewrite base url from info/refs redirects\n + remote-curl: store url as a strbuf\n + remote-curl: make refs_url a strbuf\n + http: update base URLs when we see redirects\n + http: provide effective url to callers\n + http: hoist credential request out of handle_curl_result\n  (merged to 'next' on 2013-10-14 at a0642be)\n + http: refactor options to http_get_*\n + http_request: factor out curlinfo_strbuf\n + http_get_file: style fixes\n\n Handle the case where http transport gets redirected during the\n authorization request better.\n\n Will merge to 'master'.\n\n\n* jl/submodule-mv (2013-10-13) 1 commit\n - mv: Fix spurious warning when moving a file in presence of submodules\n\n Moving a regular file in a repository with a .gitmodules file was\n producing a warning 'Could not find section in .gitmodules where\n path=<filename>'.\n\n Will merge to 'next'.\n\n\n* kb/fast-hashmap (2013-10-22) 12 commits\n - remove old hash.[ch] implementation\n - read-cache.c: fix memory leaks caused by removed cache entries\n - name-hash.c: remove cache entries instead of marking them CE_UNHASHED\n - name-hash.c: use new hash map implementation for cache entries\n - name-hash.c: remove unreferenced directory entries\n - name-hash.c: use new hash map implementation for directories\n - diffcore-rename.c: use new hash map implementation\n - diffcore-rename.c: simplify finding exact renames\n - diffcore-rename.c: move code around to prepare for the next patch\n - buitin/describe.c: use new hash map implementation\n - add a hashtable implementation that supports O(1) removal\n - submodule: don't access the .gitmodules cache entry after removing it\n\n Improvements to our hash table to get it to meet the needs of the\n msysgit fscache project, with some nice performance improvements.\n\n The preparatory clean-up to submodule from Jens is at the bottom. I\n also squashed in a fix-up by Karsten found at $gmane/236468 (please\n double-check the result).\n\n Will merge to 'next'.\n\n\n* jc/revision-range-unpeel (2013-10-15) 1 commit\n  (merged to 'next' on 2013-10-16 at d04ddfe)\n + revision: do not peel tags used in range notation\n\n \"git rev-list --objects ^v1.0^ v1.0\" gave v1.0 tag itself in the\n output, but \"git rev-list --objects v1.0^..v1.0\" did not.\n\n Will merge to 'master'.\n\n\n* jc/upload-pack-send-symref (2013-10-22) 10 commits\n  (merged to 'next' on 2013-10-23 at 8ef5660)\n + t5570: Update for clone-progress-to-stderr branch\n + Merge branch 'jk/clone-progress-to-stderr' into jc/upload-pack-send-symref\n + t5570: Update for symref capability\n  (merged to 'next' on 2013-10-16 at eb1ae25)\n + clone: test the new HEAD detection logic\n + connect: annotate refs with their symref information in get_remote_head()\n + connect.c: make parse_feature_value() static\n + upload-pack: send non-HEAD symbolic refs\n + upload-pack: send symbolic ref information as capability\n + upload-pack.c: do not pass confusing cb_data to mark_our_ref()\n + t5505: fix \"set-head --auto with ambiguous HEAD\" test\n\n One long-standing flaw in the pack transfer protocol used by \"git\n clone\" was that there was no way to tell the other end which branch\n \"HEAD\" points at, and the receiving end needed to guess.  A new\n capability has been defined in the pack protocol to convey this\n information so that cloning from a repository with more than one\n branches pointing at the same commit where the HEAD is at now\n reliably sets the initial branch in the resulting repository.\n\n Will merge to 'master'.\n\n\n* jx/relative-path-regression-fix (2013-10-14) 3 commits\n  (merged to 'next' on 2013-10-18 at b4af45f)\n + Use simpler relative_path when set_git_dir\n  (merged to 'next' on 2013-10-14 at 704b9ee)\n + relative_path should honor dos-drive-prefix\n + test: use unambigous leading path (/foo) for MSYS\n\n Will merge to 'master' and later to 'maint'.\n\n\n* jn/add-2.0-u-A-sans-pathspec (2013-04-26) 1 commit\n - git add: -u/-A now affects the entire working tree\n\n Will merge to and cook in 'next' until Git 2.0.\n\n\n* jc/core-checkstat-2.0 (2013-05-06) 1 commit\n - core.statinfo: remove as promised in Git 2.0\n\n Will merge to and cook in 'next' until Git 2.0.\n\n\n* jc/push-2.0-default-to-simple (2013-06-18) 1 commit\n - push: switch default from \"matching\" to \"simple\"\n\n Will merge to and cook in 'next' until Git 2.0.\n\n\n* jc/add-2.0-ignore-removal (2013-04-22) 1 commit\n - git add <pathspec>... defaults to \"-A\"\n\n Updated endgame for \"git add <pathspec>\" that defaults to \"--all\"\n aka \"--no-ignore-removal\".\n\n Will merge to and cook in 'next' until Git 2.0.\n\n\n* jc/hold-diff-remove-q-synonym-for-no-deletion (2013-07-19) 1 commit\n - diff: remove \"diff-files -q\" in a version of Git in a distant future\n\n Will merge to and cook in 'next' until a distant future.\n\n--------------------------------------------------\n[Discarded]\n\n* jh/shorten-refname (2013-05-07) 4 commits\n . t1514: refname shortening is done after dereferencing symbolic refs\n . shorten_unambiguous_ref(): Fix shortening refs/remotes/origin/HEAD to origin\n . t1514: Demonstrate failure to correctly shorten \"refs/remotes/origin/HEAD\"\n . t1514: Add tests of shortening refnames in strict/loose mode\n\n When remotes/origin/HEAD is not a symbolic ref, \"rev-parse\n --abbrev-ref remotes/origin/HEAD\" ought to show \"origin\", not\n \"origin/HEAD\", which is fixed with this series (if it is a symbolic\n ref that points at remotes/origin/something, then it should show\n \"origin/something\" and it already does).\n\n Has been expecting a reroll, as an early part of a larger series.\n $gmane/225137\n\n Discarded due to inactivity, without prejudice.\n"},{"id":"229562","messageId":"CACsJy8A3s4TUmUOC+i-k97GxxvBQ7mQmdoPJizfy1yS3rqLEkA@mail.gmail.com","threadId":"35203","inReplyTo":"xmqqeh79hr3o.fsf@gitster.dls.corp.google.com","subject":"Re: What's cooking in git.git (Oct 2013, #06; Fri, 25)","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-10-26T10:30:42Z","receivedAt":"2013-10-26T10:30:42Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sat, Oct 26, 2013 at 6:23 AM, Junio C Hamano <gitster@pobox.com> wrote:\n> * kb/fast-hashmap (2013-10-22) 12 commits\n>  - remove old hash.[ch] implementation\n>  - read-cache.c: fix memory leaks caused by removed cache entries\n>  - name-hash.c: remove cache entries instead of marking them CE_UNHASHED\n>  - name-hash.c: use new hash map implementation for cache entries\n>  - name-hash.c: remove unreferenced directory entries\n>  - name-hash.c: use new hash map implementation for directories\n>  - diffcore-rename.c: use new hash map implementation\n>  - diffcore-rename.c: simplify finding exact renames\n>  - diffcore-rename.c: move code around to prepare for the next patch\n>  - buitin/describe.c: use new hash map implementation\n>  - add a hashtable implementation that supports O(1) removal\n>  - submodule: don't access the .gitmodules cache entry after removing it\n>\n>  Improvements to our hash table to get it to meet the needs of the\n>  msysgit fscache project, with some nice performance improvements.\n>\n>  The preparatory clean-up to submodule from Jens is at the bottom. I\n>  also squashed in a fix-up by Karsten found at $gmane/236468 (please\n>  double-check the result).\n\njk/pack-bitmap adds khash.h, which from a first glance looks like yet\nanother hash table implementation. I was just wondering if kb's new\nhash tables can cover the need of pack-bitmap.c too so we can remove\nkhash.h later..\n-- \nDuy\n"},{"id":"229645","messageId":"xmqq61shgzvn.fsf@gitster.dls.corp.google.com","threadId":"35203","inReplyTo":"CACsJy8A3s4TUmUOC+i-k97GxxvBQ7mQmdoPJizfy1yS3rqLEkA@mail.gmail.com","subject":"Re: What's cooking in git.git (Oct 2013, #06; Fri, 25)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-10-28T15:48:44Z","receivedAt":"2013-10-28T15:48:44Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Duy Nguyen <pclouds@gmail.com> writes:\n\n> On Sat, Oct 26, 2013 at 6:23 AM, Junio C Hamano <gitster@pobox.com> wrote:\n>> * kb/fast-hashmap (2013-10-22) 12 commits\n>>  - remove old hash.[ch] implementation\n>>  - read-cache.c: fix memory leaks caused by removed cache entries\n>>  - name-hash.c: remove cache entries instead of marking them CE_UNHASHED\n>>  - name-hash.c: use new hash map implementation for cache entries\n>>  - name-hash.c: remove unreferenced directory entries\n>>  - name-hash.c: use new hash map implementation for directories\n>>  - diffcore-rename.c: use new hash map implementation\n>>  - diffcore-rename.c: simplify finding exact renames\n>>  - diffcore-rename.c: move code around to prepare for the next patch\n>>  - buitin/describe.c: use new hash map implementation\n>>  - add a hashtable implementation that supports O(1) removal\n>>  - submodule: don't access the .gitmodules cache entry after removing it\n>>\n>>  Improvements to our hash table to get it to meet the needs of the\n>>  msysgit fscache project, with some nice performance improvements.\n>>\n>>  The preparatory clean-up to submodule from Jens is at the bottom. I\n>>  also squashed in a fix-up by Karsten found at $gmane/236468 (please\n>>  double-check the result).\n>\n> jk/pack-bitmap adds khash.h, which from a first glance looks like yet\n> another hash table implementation. I was just wondering if kb's new\n> hash tables can cover the need of pack-bitmap.c too so we can remove\n> khash.h later..\n\nGood thinking ;-).\n"},{"id":"229646","messageId":"CAFFjANSnuS6_+uAd43AayojJyK-wj2wMxQ6DBD6JyN=A7xh2_A@mail.gmail.com","threadId":"35203","inReplyTo":"xmqq61shgzvn.fsf@gitster.dls.corp.google.com","subject":"Re: What's cooking in git.git (Oct 2013, #06; Fri, 25)","fromName":"Vicent Martí","fromEmail":"tanoku@gmail.com","sentAt":"2013-10-28T16:16:02Z","receivedAt":"2013-10-28T16:16:02Z","isPatch":false,"sender":{"key":"tanoku@gmail.com","avatar":"https://gravatar.com/avatar/271386991cb4c2b8f1e1ed1d059f3422cc3485de7a598f65043f70be021d095b?d=mp&s=160"},"body":"On Mon, Oct 28, 2013 at 4:48 PM, Junio C Hamano <gitster@pobox.com> wrote:\n>> jk/pack-bitmap adds khash.h, which from a first glance looks like yet\n>> another hash table implementation. I was just wondering if kb's new\n>> hash tables can cover the need of pack-bitmap.c too so we can remove\n>> khash.h later..\n>\n> Good thinking ;-).\n\nWe use the khash tables to map:\n\n    - sha1 (const char *) to (void *)\n    - sha1 (const char *) to int\n\nThe new `hashmap.c` covers the first case quite well (albeit slightly\nmore verbosely than I'd like), but in the second case it doesn't quite\nwork. Since the new hash needs to embed the \"struct hashmap_entry\" on\nall its values (to allow for separate chaining), having it map to\n`int` keys requires a struct like this:\n\n    struct sha1_position {\n        struct hashmap_entry {\n            struct hashmap_entry *next;\n            unsigned int hash;\n        };\n        int position;\n    }\n\nkhash on the other hand is capable of storing the position values as\npart of the hash table itself (i.e. `int **buckets`), and saves us\nfrom thousands of bytes of allocations + indirection.\n\nI am not sure whether the consistency of having a single hash map\nwarrants the performance and memory hits when operating on the\nextended index.\n\nPlease advice.\n\nluv,\nvmg\n"},{"id":"229648","messageId":"xmqqwqkxfiv4.fsf@gitster.dls.corp.google.com","threadId":"35203","inReplyTo":"CAFFjANSnuS6_+uAd43AayojJyK-wj2wMxQ6DBD6JyN=A7xh2_A@mail.gmail.com","subject":"Re: What's cooking in git.git (Oct 2013, #06; Fri, 25)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-10-28T16:41:35Z","receivedAt":"2013-10-28T16:41:35Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Vicent Martí <tanoku@gmail.com> writes:\n\n> On Mon, Oct 28, 2013 at 4:48 PM, Junio C Hamano <gitster@pobox.com> wrote:\n>>> jk/pack-bitmap adds khash.h, which from a first glance looks like yet\n>>> another hash table implementation. I was just wondering if kb's new\n>>> hash tables can cover the need of pack-bitmap.c too so we can remove\n>>> khash.h later..\n>> ...\n> khash on the other hand is capable of storing the position values as\n> part of the hash table itself (i.e. `int **buckets`), and saves us\n> from thousands of bytes of allocations + indirection.\n\nMy \"Good thinking ;-)\" comment was primarily meant as \"somebody\nneeds to at least think about the possibility and consider pros and\ncons\", and you thought about it already ;-).\n\nIn short, kb's hash table does not cover the need for pack-bitmap,\nso we should keep two at least for now, until (and/or unless) either\nside can be shown (and/or extended) to cover the need for the other\none as well.\n\nThanks. \n"},{"id":"229662","messageId":"526EBEE8.7070807@gmail.com","threadId":"35203","inReplyTo":"CAFFjANSnuS6_+uAd43AayojJyK-wj2wMxQ6DBD6JyN=A7xh2_A@mail.gmail.com","subject":"Re: What's cooking in git.git (Oct 2013, #06; Fri, 25)","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2013-10-28T19:45:44Z","receivedAt":"2013-10-28T19:45:44Z","isPatch":false,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"Am 28.10.2013 17:16, schrieb Vicent Martí:\n> On Mon, Oct 28, 2013 at 4:48 PM, Junio C Hamano <gitster@pobox.com> wrote:\n>>> jk/pack-bitmap adds khash.h, which from a first glance looks like yet\n>>> another hash table implementation. I was just wondering if kb's new\n>>> hash tables can cover the need of pack-bitmap.c too so we can remove\n>>> khash.h later..\n>>\n>> Good thinking ;-).\n> \n> We use the khash tables to map:\n> \n>     - sha1 (const char *) to (void *)\n>     - sha1 (const char *) to int\n> \n> The new `hashmap.c` covers the first case quite well (albeit slightly\n> more verbosely than I'd like), but in the second case it doesn't quite\n> work. Since the new hash needs to embed the \"struct hashmap_entry\" on\n> all its values (to allow for separate chaining), having it map to\n> `int` keys requires a struct like this:\n> \n>     struct sha1_position {\n>         struct hashmap_entry {\n>             struct hashmap_entry *next;\n>             unsigned int hash;\n>         };\n>         int position;\n>     }\n> \n\nHmm...isn't that position rather an index into two separately maintained arrays? So you'd rather have:\n\n    struct sha1_position {\n        struct hashmap_entry {\n            struct hashmap_entry *next;\n            unsigned int hash;\n        };\n        uint32_t pack_name_hash;\n        struct object *object;\n     }\n\n> khash on the other hand is capable of storing the position values as\n> part of the hash table itself (i.e. `int **buckets`), and saves us\n> from thousands of bytes of allocations + indirection.\n> \n\nHowever, khash keeps separate arrays for flags, keys and values, all of them overallocated by 1 / load factor (so there's lots of unused space). ext_index.objects and ext_index.hashes are also overallocated by the usual alloc_nr() factor 1.5.\n\nRegarding memory consumption, I think both implementations will be pretty similar. Hashmap allocates many small regions while khash re-allocates a few big ones...I really don't know which is better, ideally entries would be allocated in chunks to minimize both heap overhead and memcpy disadvantes.\n\nRegarding performance, khash uses open addressing, which requires more key comparisons (O(1/(1-load_factor))) than chaining (O(1+load_factor)). However, any measurable differences will most likely be dwarfed by IO costs in this particular use case.\n\n\nBtw., pack-objects.c::rehash_objects() in patch 03 unnecessarily checks for duplicates. That's probably the reason for the high hashcmp times you found in the first round of the patch series.\n\nCheers,\nKarsten\n"},{"id":"229669","messageId":"CAFFjANRaphYdg6VM8cqJY3NmPz+gNE7S9S1jAgPPctUZio7+Tw@mail.gmail.com","threadId":"35203","inReplyTo":"526EBEE8.7070807@gmail.com","subject":"Re: What's cooking in git.git (Oct 2013, #06; Fri, 25)","fromName":"Vicent Martí","fromEmail":"tanoku@gmail.com","sentAt":"2013-10-28T21:04:17Z","receivedAt":"2013-10-28T21:04:17Z","isPatch":false,"sender":{"key":"tanoku@gmail.com","avatar":"https://gravatar.com/avatar/271386991cb4c2b8f1e1ed1d059f3422cc3485de7a598f65043f70be021d095b?d=mp&s=160"},"body":"On Mon, Oct 28, 2013 at 8:45 PM, Karsten Blees <karsten.blees@gmail.com> wrote:\n>> The new `hashmap.c` covers the first case quite well (albeit slightly\n>> more verbosely than I'd like), but in the second case it doesn't quite\n>> work. Since the new hash needs to embed the \"struct hashmap_entry\" on\n>> all its values (to allow for separate chaining), having it map to\n>> `int` keys requires a struct like this:\n>>\n>>     struct sha1_position {\n>>         struct hashmap_entry {\n>>             struct hashmap_entry *next;\n>>             unsigned int hash;\n>>         };\n>>         int position;\n>>     }\n>>\n>\n> Hmm...isn't that position rather an index into two separately maintained arrays? So you'd rather have:\n>\n>     struct sha1_position {\n>         struct hashmap_entry {\n>             struct hashmap_entry *next;\n>             unsigned int hash;\n>         };\n>         uint32_t pack_name_hash;\n>         struct object *object;\n>      }\n\nNo, this is not quite right. We use the separate arrays because the\nnormal operation mode is to index by position (e.g. we need the nth\nobject in the extended index); the hash table is an auxiliary\nstructure to reverse that indexing (e.g. what position does this SHA1\nhave on the extended index). The information which is always required\nto construct bitmaps is position, so we need to store the indexes in a\nmap.\n\n>> khash on the other hand is capable of storing the position values as\n>> part of the hash table itself (i.e. `int **buckets`), and saves us\n>> from thousands of bytes of allocations + indirection.\n>>\n>\n> However, khash keeps separate arrays for flags, keys and values, all of them overallocated by 1 / load factor (so there's lots of unused space). ext_index.objects and ext_index.hashes are also overallocated by the usual alloc_nr() factor 1.5.\n\nFWIW The flags for khash are compacted, so they are stored much more\ntightly than pointers, even when overallocated.\n\n>\n> Regarding memory consumption, I think both implementations will be pretty similar. Hashmap allocates many small regions while khash re-allocates a few big ones...I really don't know which is better, ideally entries would be allocated in chunks to minimize both heap overhead and memcpy disadvantes.\n\nI agree, both implementations probably have very similar memory\ncharacteristics, probably enough not to matter.\n\n> Regarding performance, khash uses open addressing, which requires more key comparisons (O(1/(1-load_factor))) than chaining (O(1+load_factor)). However, any measurable differences will most likely be dwarfed by IO costs in this particular use case.\n\nI don't think this is true. If you actually run a couple insertion and\nlookup benchmarks comparing the two implementations, you'll find khash\nto be around ~30% faster for most workloads (venturing a guess from\npast experience). I am obviously not the author of khash, but I've\nfound that the theoretical increase in key comparisons is completely\ndwarfed by the benefit of increased cache locality during the probing\nfase. I still haven't found a faster C hash table implementation than\nkhash for the general case, that's why I normally use it despite the\nworrisome preprocessor crash-party going on in that header file.\n\n> Btw., pack-objects.c::rehash_objects() in patch 03 unnecessarily checks for duplicates. That's probably the reason for the high hashcmp times you found in the first round of the patch series.\n\nPatch 03 is a refactoring -- the duplicate checking code has been in\npack-objects.c for years. I am not sure duplicate checking is\nsuperfluous at all, there are many cases where you could be\ndouble-inserting objects in a pack-objects run, and you really don't\nwant to generate packfiles with dupe objects.\n\nThanks for the feedback!\n\nluv,\nvmg\n"},{"id":"229717","messageId":"CAH7EuMHgH6Oe_SvjyutBaakRfyZGHpp_iimaAzpV09AnHTYntw@mail.gmail.com","threadId":"35203","inReplyTo":"CAFFjANRaphYdg6VM8cqJY3NmPz+gNE7S9S1jAgPPctUZio7+Tw@mail.gmail.com","subject":"Re: What's cooking in git.git (Oct 2013, #06; Fri, 25)","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2013-10-29T09:09:11Z","receivedAt":"2013-10-29T09:09:11Z","isPatch":false,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"On Mon, Oct 28, 2013 at 10:04 PM, Vicent Martí <tanoku@gmail.com> wrote:\n>\n> On Mon, Oct 28, 2013 at 8:45 PM, Karsten Blees <karsten.blees@gmail.com> wrote:\n>\n> > Regarding performance, khash uses open addressing, which requires more key comparisons (O(1/(1-load_factor))) than chaining (O(1+load_factor)). However, any measurable differences will most likely be dwarfed by IO costs in this particular use case.\n>\n> I don't think this is true. If you actually run a couple insertion and\n> lookup benchmarks comparing the two implementations, you'll find khash\n> to be around ~30% faster for most workloads (venturing a guess from\n> past experience). I am obviously not the author of khash, but I've\n> found that the theoretical increase in key comparisons is completely\n> dwarfed by the benefit of increased cache locality during the probing\n> fase. I still haven't found a faster C hash table implementation than\n> khash for the general case, that's why I normally use it despite the\n> worrisome preprocessor crash-party going on in that header file.\n\nYes, cache locality is where open addressing shines, however, you\nloose that benefit when the keys are pointers (e.g. sha1's).\n\n>\n>\n> > Btw., pack-objects.c::rehash_objects() in patch 03 unnecessarily checks for duplicates. That's probably the reason for the high hashcmp times you found in the first round of the patch series.\n>\n> Patch 03 is a refactoring -- the duplicate checking code has been in\n> pack-objects.c for years. I am not sure duplicate checking is\n> superfluous at all, there are many cases where you could be\n> double-inserting objects in a pack-objects run, and you really don't\n> want to generate packfiles with dupe objects.\n\nThe point is that its in _rehash_. Duplicate checking should be in\nadd/put. Rehash only rearranges entries that are alread _in_ the map,\nand it usually only needs the hash code for that. So pack-objects\nimplements rehash in terms of a full clear + add-all instead, which is\nof course slower than what khash, hashmap etc. would do.\n\nCiao,\nKarsten\n"},{"id":"230650","messageId":"52852699.3000408@gmail.com","threadId":"35203","inReplyTo":"CAH7EuMHgH6Oe_SvjyutBaakRfyZGHpp_iimaAzpV09AnHTYntw@mail.gmail.com","subject":"Re: What's cooking in git.git (Oct 2013, #06; Fri, 25)","fromName":"Karsten Blees","fromEmail":"karsten.blees@gmail.com","sentAt":"2013-11-14T19:38:01Z","receivedAt":"2013-11-14T19:38:01Z","isPatch":false,"sender":{"key":"karsten.blees@gmail.com","avatar":"https://avatars.githubusercontent.com/u/1111200?v=4"},"body":"Am 29.10.2013 10:09, schrieb Karsten Blees:\n> On Mon, Oct 28, 2013 at 10:04 PM, Vicent Martí <tanoku@gmail.com> wrote:\n>>\n>> On Mon, Oct 28, 2013 at 8:45 PM, Karsten Blees <karsten.blees@gmail.com> wrote:\n>>\n>>> Regarding performance, khash uses open addressing, which requires more key comparisons (O(1/(1-load_factor))) than chaining (O(1+load_factor)). However, any measurable differences will most likely be dwarfed by IO costs in this particular use case.\n>>\n>> I don't think this is true. If you actually run a couple insertion and\n>> lookup benchmarks comparing the two implementations, you'll find khash\n>> to be around ~30% faster for most workloads (venturing a guess from\n>> past experience). I am obviously not the author of khash, but I've\n...\n\nJust out of curiosity, I added performance test code for khash to the test in my current hashmap patch series [1]. It turns out that khash is by far the slowest of the bunch, especially with many collisions.\n\nAgain, I don't think that performance matters all that much (or in other words: _any_ hash table implementation will probably be fast enough compared to the rest that's going on). Its more a question of whether we really need two different hash table implementations (and a queasy feeling about the macro kludge in khash.h...).\n\n\nKhash doesn't store the hash codes along with the entries (as both hash.[ch] and hashmap.[ch] do), so it needs to re-calculate hash codes on every resize. For a fair comparison, the \"khash\" test uses keys with pre-calculated hash codes in the key structure. This should be similar to a hash function that just copies 4 bytes from a sha1 key. Khash maps with more complex hash functions will be slower (see khstr).\n\nThe \"khstr\" test uses khash's predefined string map and khash's X31 hash function for strings (therefore no separate values for different hash functions here).\n\nThe table is similar to what I posted for hashmap-v2 [2] (i.e. real time in seconds for 1,000 rounds á 100,000 entries). I just turned it around a bit to make room for khash columns.\n\ntest | hash_fn | hashmap |  hash   |  khash  | khstr  |\n-----+---------+---------+---------+---------+--------+\n     | FNV     |   2.429 |  14.366 |  11.780 | 18.677 |\n     | FNV  x2 |   2.946 |  14.558 |  10.922 |        |\n add | i       |   1.708 |   7.419 |   4.132 |        |\n     | i    x2 |   1.791 |   8.565 |   4.502 |        |\n     | i/10    |   1.555 |   1.805 | 344.691 |        |\n     | i/10 x2 |   1.543 |   1.808 | 319.559 |        |\n-----+---------+---------+---------+---------+--------+\n     | FNV     |   1.822 |   3.452 |   4.922 |  8.309 |\nget  | FNV  x2 |   2.298 |   3.194 |   4.473 |        |\n100% | i       |   1.252 |   1.344 |   0.944 |        |\nhits | i    x2 |   1.286 |   1.434 |   1.220 |        |\n     | i/10    |   6.720 |   5.138 | 281.815 |        |\n     | i/10 x2 |   6.297 |   5.188 | 257.021 |        |\n-----+---------+---------+---------+---------+--------+\n     | FNV     |   1.023 |   3.949 |   4.115 |  4.878 |\nget  | FNV  x2 |   1.538 |   3.915 |   4.571 |        |\n10%  | i       |   0.654 | 397.457 |  38.125 |        |\nhits | i    x2 |   0.718 |   0.722 |   9.111 |        |\n     | i/10    |   1.128 |  30.235 |  60.376 |        |\n     | i/10 x2 |   1.260 |   1.082 |  43.354 |        |\n-----+---------+---------+---------+---------+--------+\n\n[1] https://github.com/kblees/git/commits/kb/hashmap-v5-khash\n[2] http://article.gmane.org/gmane.comp.version-control.git/235290\n"}]}