{"thread":{"id":"20269","subject":"[PATCHv3 0/8] RESEND: git notes","startedAt":"2009-07-29T02:25:18Z","lastAt":"2009-08-27T11:56:37Z","messageCount":30,"participants":["Johan Herland","Thomas Rast","Alex Riesen","Shawn O. Pearce","Johannes Schindelin","Andreas Ericsson"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"119004","messageId":"1248834326-31488-1-git-send-email-johan@herland.net","threadId":"20269","inReplyTo":null,"subject":"[PATCHv3 0/8] RESEND: git notes","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-07-29T02:25:18Z","receivedAt":"2009-07-29T02:25:18Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"Hi,\n\nHere is a long overdue resend and improvement of the jh/notes topic in 'pu'.\n\nThe 5 first patches are pretty much unchanged (except for better attribution\nof the various people who have helped improve this patch series).\n\nThe 6th patch introduces a first draft of notes tree parsing with support for\nfanout subtrees. This first draft is just a straightforward implementation of\nwhat I have picked up from the (many) discussions on this topic. As such,\nthis first draft focuses on correctness, rather than performance. BTW, did I\nmention this was a first draft?\n\nThe 7th patch is stolen from the jh/vcs-cvs topic in 'pu', and teaches\ngit-fast-import to import note objects.\n\nThe final 8th patch is a relatively straightforward optimization of t3302.\n\n\nHave fun! :)\n\n...Johan\n\n\nJohan Herland (4):\n Teach \"-m \" and \"-F \" to \"git notes edit\"\n First draft of notes tree parser with support for fanout subtrees\n fast-import: Add support for importing commit notes\n t3302-notes-index-expensive: Speed up create_repo()\n\nJohannes Schindelin (4):\n Introduce commit notes\n Add a script to edit/inspect notes\n Speed up git notes lookup\n Add an expensive test for git-notes\n\n .gitignore | 1 +\n Documentation/config.txt | 13 ++\n Documentation/git-fast-import.txt | 45 +++++-\n Documentation/git-notes.txt | 60 ++++++++\n Makefile | 3 +\n cache.h | 4 +\n command-list.txt | 1 +\n commit.c | 1 +\n config.c | 5 +\n environment.c | 1 +\n fast-import.c | 88 +++++++++++-\n git-notes.sh | 121 +++++++++++++++\n notes.c | 295 +++++++++++++++++++++++++++++++++++++\n notes.h | 7 +\n pretty.c | 5 +\n t/t3301-notes.sh | 149 +++++++++++++++++++\n t/t3302-notes-index-expensive.sh | 118 +++++++++++++++\n t/t3303-notes-subtrees.sh | 206 ++++++++++++++++++++++++++\n t/t9300-fast-import.sh | 166 +++++++++++++++++++++\n 19 files changed, 1279 insertions(+), 10 deletions(-)\n create mode 100644 Documentation/git-notes.txt\n create mode 100755 git-notes.sh\n create mode 100644 notes.c\n create mode 100644 notes.h\n create mode 100755 t/t3301-notes.sh\n create mode 100755 t/t3302-notes-index-expensive.sh\n create mode 100755 t/t3303-notes-subtrees.sh\n"},{"id":"119005","messageId":"1248834326-31488-2-git-send-email-johan@herland.net","threadId":"20269","inReplyTo":"1248834326-31488-1-git-send-email-johan@herland.net","subject":"[PATCHv3 1/8] Introduce commit notes","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-07-29T02:25:19Z","receivedAt":"2009-07-29T02:25:19Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"From: Johannes Schindelin \n\nCommit notes are blobs which are shown together with the commit\nmessage. These blobs are taken from the notes ref, which you can\nconfigure by the config variable core.notesRef, which in turn can\nbe overridden by the environment variable GIT_NOTES_REF.\n\nThe notes ref is a branch which contains \"files\" whose names are\nthe names of the corresponding commits (i.e. the SHA-1).\n\nThe rationale for putting this information into a ref is this: we\nwant to be able to fetch and possibly union-merge the notes,\nmaybe even look at the date when a note was introduced, and we\nwant to store them efficiently together with the other objects.\n\nThis patch has been improved by the following contributions:\n- Thomas Rast: fix core.notesRef documentation\n- Tor Arne Vestbø: fix printing of multi-line notes\n\nSigned-off-by: Johannes Schindelin \nSigned-off-by: Thomas Rast \nSigned-off-by: Tor Arne Vestbø \nSigned-off-by: Johan Herland \nSigned-off-by: Junio C Hamano \n---\n Documentation/config.txt | 13 ++++++++\n Makefile | 2 +\n cache.h | 4 ++\n commit.c | 1 +\n config.c | 5 +++\n environment.c | 1 +\n notes.c | 69 ++++++++++++++++++++++++++++++++++++++++++++++\n notes.h | 7 ++++\n pretty.c | 5 +++\n 9 files changed, 107 insertions(+), 0 deletions(-)\n create mode 100644 notes.c\n create mode 100644 notes.h\n\ndiff --git a/Documentation/config.txt b/Documentation/config.txt\nindex 792dd42..6788958 100644\n--- a/Documentation/config.txt\n+++ b/Documentation/config.txt\n@@ -439,6 +439,19 @@ On some file system/operating system combinations, this is unreliable.\n Set this config setting to 'rename' there; However, This will remove the\n check that makes sure that existing object files will not get overwritten.\n \n+core.notesRef::\n+\tWhen showing commit messages, also show notes which are stored in\n+\tthe given ref. This ref is expected to contain files named\n+\tafter the full SHA-1 of the commit they annotate.\n++\n+If such a file exists in the given ref, the referenced blob is read, and\n+appended to the commit message, separated by a \"Notes:\" line. If the\n+given ref itself does not exist, it is not an error, but means that no\n+notes should be printed.\n++\n+This setting defaults to \"refs/notes/commits\", and can be overridden by\n+the `GIT_NOTES_REF` environment variable.\n+\n add.ignore-errors::\n \tTells 'git-add' to continue adding files when some files cannot be\n \tadded due to indexing errors. Equivalent to the '--ignore-errors'\ndiff --git a/Makefile b/Makefile\nindex ce082cf..cc188ca 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -429,6 +429,7 @@ LIB_H += ll-merge.h\n LIB_H += log-tree.h\n LIB_H += mailmap.h\n LIB_H += merge-recursive.h\n+LIB_H += notes.h\n LIB_H += object.h\n LIB_H += pack.h\n LIB_H += pack-refs.h\n@@ -512,6 +513,7 @@ LIB_OBJS += match-trees.o\n LIB_OBJS += merge-file.o\n LIB_OBJS += merge-recursive.o\n LIB_OBJS += name-hash.o\n+LIB_OBJS += notes.o\n LIB_OBJS += object.o\n LIB_OBJS += pack-check.o\n LIB_OBJS += pack-refs.o\ndiff --git a/cache.h b/cache.h\nindex 1a2a3c9..3d761b8 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -371,6 +371,8 @@ static inline enum object_type object_type(unsigned int mode)\n #define GITATTRIBUTES_FILE \".gitattributes\"\n #define INFOATTRIBUTES_FILE \"info/attributes\"\n #define ATTRIBUTE_MACRO_PREFIX \"[attr]\"\n+#define GIT_NOTES_REF_ENVIRONMENT \"GIT_NOTES_REF\"\n+#define GIT_NOTES_DEFAULT_REF \"refs/notes/commits\"\n \n extern int is_bare_repository_cfg;\n extern int is_bare_repository(void);\n@@ -566,6 +568,8 @@ enum object_creation_mode {\n \n extern enum object_creation_mode object_creation_mode;\n \n+extern char *notes_ref_name;\n+\n extern int grafts_replace_parents;\n \n #define GIT_REPO_VERSION 0\ndiff --git a/commit.c b/commit.c\nindex e2bcbe8..ae6bff4 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -5,6 +5,7 @@\n #include \"utf8.h\"\n #include \"diff.h\"\n #include \"revision.h\"\n+#include \"notes.h\"\n \n int save_commit_buffer = 1;\n \ndiff --git a/config.c b/config.c\nindex 1b3823d..9d99319 100644\n--- a/config.c\n+++ b/config.c\n@@ -469,6 +469,11 @@ static int git_default_core_config(const char *var, const char *value)\n \t\treturn 0;\n \t}\n \n+\tif (!strcmp(var, \"core.notesref\")) {\n+\t\tnotes_ref_name = xstrdup(value);\n+\t\treturn 0;\n+\t}\n+\n \tif (!strcmp(var, \"core.pager\"))\n \t\treturn git_config_string(&pager_program, var, value);\n \ndiff --git a/environment.c b/environment.c\nindex d478125..36c7776 100644\n--- a/environment.c\n+++ b/environment.c\n@@ -51,6 +51,7 @@ enum push_default_type push_default = PUSH_DEFAULT_MATCHING;\n #define OBJECT_CREATION_MODE OBJECT_CREATION_USES_HARDLINKS\n #endif\n enum object_creation_mode object_creation_mode = OBJECT_CREATION_MODE;\n+char *notes_ref_name;\n int grafts_replace_parents = 1;\n \n /* Parallel index stat data preload? */\ndiff --git a/notes.c b/notes.c\nnew file mode 100644\nindex 0000000..b0cf553\n--- /dev/null\n+++ b/notes.c\n@@ -0,0 +1,69 @@\n+#include \"cache.h\"\n+#include \"commit.h\"\n+#include \"notes.h\"\n+#include \"refs.h\"\n+#include \"utf8.h\"\n+#include \"strbuf.h\"\n+\n+static int initialized;\n+\n+void get_commit_notes(const struct commit *commit, struct strbuf *sb,\n+\t\tconst char *output_encoding)\n+{\n+\tstatic const char *utf8 = \"utf-8\";\n+\tstruct strbuf name = STRBUF_INIT;\n+\tconst char *hex;\n+\tunsigned char sha1[20];\n+\tchar *msg, *msg_p;\n+\tunsigned long linelen, msglen;\n+\tenum object_type type;\n+\n+\tif (!initialized) {\n+\t\tconst char *env = getenv(GIT_NOTES_REF_ENVIRONMENT);\n+\t\tif (env)\n+\t\t\tnotes_ref_name = getenv(GIT_NOTES_REF_ENVIRONMENT);\n+\t\telse if (!notes_ref_name)\n+\t\t\tnotes_ref_name = GIT_NOTES_DEFAULT_REF;\n+\t\tif (notes_ref_name && read_ref(notes_ref_name, sha1))\n+\t\t\tnotes_ref_name = NULL;\n+\t\tinitialized = 1;\n+\t}\n+\n+\tif (!notes_ref_name)\n+\t\treturn;\n+\n+\tstrbuf_addf(&name, \"%s:%s\", notes_ref_name,\n+\t\t\tsha1_to_hex(commit->object.sha1));\n+\tif (get_sha1(name.buf, sha1))\n+\t\treturn;\n+\n+\tif (!(msg = read_sha1_file(sha1, &type, &msglen)) || !msglen ||\n+\t\t\ttype != OBJ_BLOB)\n+\t\treturn;\n+\n+\tif (output_encoding && *output_encoding &&\n+\t\t\tstrcmp(utf8, output_encoding)) {\n+\t\tchar *reencoded = reencode_string(msg, output_encoding, utf8);\n+\t\tif (reencoded) {\n+\t\t\tfree(msg);\n+\t\t\tmsg = reencoded;\n+\t\t\tmsglen = strlen(msg);\n+\t\t}\n+\t}\n+\n+\t/* we will end the annotation by a newline anyway */\n+\tif (msglen && msg[msglen - 1] == '\\n')\n+\t\tmsglen--;\n+\n+\tstrbuf_addstr(sb, \"\\nNotes:\\n\");\n+\n+\tfor (msg_p = msg; msg_p < msg + msglen; msg_p += linelen + 1) {\n+\t\tlinelen = strchrnul(msg_p, '\\n') - msg_p;\n+\n+\t\tstrbuf_addstr(sb, \" \");\n+\t\tstrbuf_add(sb, msg_p, linelen);\n+\t\tstrbuf_addch(sb, '\\n');\n+\t}\n+\n+\tfree(msg);\n+}\ndiff --git a/notes.h b/notes.h\nnew file mode 100644\nindex 0000000..79d21b6\n--- /dev/null\n+++ b/notes.h\n@@ -0,0 +1,7 @@\n+#ifndef NOTES_H\n+#define NOTES_H\n+\n+void get_commit_notes(const struct commit *commit, struct strbuf *sb,\n+\t\tconst char *output_encoding);\n+\n+#endif\ndiff --git a/pretty.c b/pretty.c\nindex e5328da..fee6789 100644\n--- a/pretty.c\n+++ b/pretty.c\n@@ -6,6 +6,7 @@\n #include \"string-list.h\"\n #include \"mailmap.h\"\n #include \"log-tree.h\"\n+#include \"notes.h\"\n #include \"color.h\"\n \n static char *user_format;\n@@ -963,5 +964,9 @@ void pretty_print_commit(enum cmit_fmt fmt, const struct commit *commit,\n \t */\n \tif (fmt == CMIT_FMT_EMAIL && sb->len <= beginning_of_body)\n \t\tstrbuf_addch(sb, '\\n');\n+\n+\tif (fmt != CMIT_FMT_ONELINE)\n+\t\tget_commit_notes(commit, sb, encoding);\n+\n \tfree(reencoded);\n }\n-- \n1.6.4.rc3.138.ga6b98.dirty\n"},{"id":"119006","messageId":"1248834326-31488-3-git-send-email-johan@herland.net","threadId":"20269","inReplyTo":"1248834326-31488-1-git-send-email-johan@herland.net","subject":"[PATCHv3 2/8] Add a script to edit/inspect notes","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-07-29T02:25:20Z","receivedAt":"2009-07-29T02:25:20Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"From: Johannes Schindelin \n\nThe script 'git notes' allows you to edit and show commit notes, by\ncalling either\n\n\tgit notes show \n\nor\n\n\tgit notes edit \n\nThis patch has been improved by the following contributions:\n- Tor Arne Vestbø: fix printing of multi-line notes\n- Michael J Gruber: test and handle empty notes gracefully\n- Thomas Rast:\n - only clean up message file when editing\n - use GIT_EDITOR and core.editor over VISUAL/EDITOR\n - t3301: fix confusing quoting in test for valid notes ref\n - t3301: use test_must_fail instead of !\n - refuse to edit notes outside refs/notes/\n- Junio C Hamano: tests: fix \"export var=val\"\n- Christian Couder: documentation: fix 'linkgit' macro in \"git-notes.txt\"\n- Johan Herland: minor cleanup and bugfixing in git-notes.sh (v2)\n\nSigned-off-by: Johannes Schindelin \nSigned-off-by: Tor Arne Vestbø \nSigned-off-by: Michael J Gruber \nSigned-off-by: Thomas Rast \nSigned-off-by: Christian Couder \nSigned-off-by: Johan Herland \nSigned-off-by: Junio C Hamano \n---\n .gitignore | 1 +\n Documentation/git-notes.txt | 46 +++++++++++++++++\n Makefile | 1 +\n command-list.txt | 1 +\n git-notes.sh | 73 +++++++++++++++++++++++++++\n t/t3301-notes.sh | 114 +++++++++++++++++++++++++++++++++++++++++++\n 6 files changed, 236 insertions(+), 0 deletions(-)\n create mode 100644 Documentation/git-notes.txt\n create mode 100755 git-notes.sh\n create mode 100755 t/t3301-notes.sh\n\ndiff --git a/.gitignore b/.gitignore\nindex 10808e3..04926fc 100644\n--- a/.gitignore\n+++ b/.gitignore\n@@ -86,6 +86,7 @@ git-mktag\n git-mktree\n git-name-rev\n git-mv\n+git-notes\n git-pack-redundant\n git-pack-objects\n git-pack-refs\ndiff --git a/Documentation/git-notes.txt b/Documentation/git-notes.txt\nnew file mode 100644\nindex 0000000..7136016\n--- /dev/null\n+++ b/Documentation/git-notes.txt\n@@ -0,0 +1,46 @@\n+git-notes(1)\n+============\n+\n+NAME\n+----\n+git-notes - Add/inspect commit notes\n+\n+SYNOPSIS\n+--------\n+[verse]\n+'git-notes' (edit | show) [commit]\n+\n+DESCRIPTION\n+-----------\n+This command allows you to add notes to commit messages, without\n+changing the commit. To discern these notes from the message stored\n+in the commit object, the notes are indented like the message, after\n+an unindented line saying \"Notes:\".\n+\n+To disable commit notes, you have to set the config variable\n+core.notesRef to the empty string. Alternatively, you can set it\n+to a different ref, something like \"refs/notes/bugzilla\". This setting\n+can be overridden by the environment variable \"GIT_NOTES_REF\".\n+\n+\n+SUBCOMMANDS\n+-----------\n+\n+edit::\n+\tEdit the notes for a given commit (defaults to HEAD).\n+\n+show::\n+\tShow the notes for a given commit (defaults to HEAD).\n+\n+\n+Author\n+------\n+Written by Johannes Schindelin \n+\n+Documentation\n+-------------\n+Documentation by Johannes Schindelin\n+\n+GIT\n+---\n+Part of the linkgit:git[7] suite\ndiff --git a/Makefile b/Makefile\nindex cc188ca..c9003d7 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -319,6 +319,7 @@ SCRIPT_SH += git-merge-one-file.sh\n SCRIPT_SH += git-merge-resolve.sh\n SCRIPT_SH += git-mergetool.sh\n SCRIPT_SH += git-mergetool--lib.sh\n+SCRIPT_SH += git-notes.sh\n SCRIPT_SH += git-parse-remote.sh\n SCRIPT_SH += git-pull.sh\n SCRIPT_SH += git-quiltimport.sh\ndiff --git a/command-list.txt b/command-list.txt\nindex fb03a2e..4296941 100644\n--- a/command-list.txt\n+++ b/command-list.txt\n@@ -74,6 +74,7 @@ git-mktag plumbingmanipulators\n git-mktree plumbingmanipulators\n git-mv mainporcelain common\n git-name-rev plumbinginterrogators\n+git-notes mainporcelain\n git-pack-objects plumbingmanipulators\n git-pack-redundant plumbinginterrogators\n git-pack-refs ancillarymanipulators\ndiff --git a/git-notes.sh b/git-notes.sh\nnew file mode 100755\nindex 0000000..f06c254\n--- /dev/null\n+++ b/git-notes.sh\n@@ -0,0 +1,73 @@\n+#!/bin/sh\n+\n+USAGE=\"(edit | show) [commit]\"\n+. git-sh-setup\n+\n+test -n \"$3\" && usage\n+\n+test -z \"$1\" && usage\n+ACTION=\"$1\"; shift\n+\n+test -z \"$GIT_NOTES_REF\" && GIT_NOTES_REF=\"$(git config core.notesref)\"\n+test -z \"$GIT_NOTES_REF\" && GIT_NOTES_REF=\"refs/notes/commits\"\n+\n+COMMIT=$(git rev-parse --verify --default HEAD \"$@\") ||\n+die \"Invalid commit: $@\"\n+\n+case \"$ACTION\" in\n+edit)\n+\tif [ \"${GIT_NOTES_REF#refs/notes/}\" = \"$GIT_NOTES_REF\" ]; then\n+\t\tdie \"Refusing to edit notes in $GIT_NOTES_REF (outside of refs/notes/)\"\n+\tfi\n+\n+\tMSG_FILE=\"$GIT_DIR/new-notes-$COMMIT\"\n+\tGIT_INDEX_FILE=\"$MSG_FILE.idx\"\n+\texport GIT_INDEX_FILE\n+\n+\ttrap '\n+\t\ttest -f \"$MSG_FILE\" && rm \"$MSG_FILE\"\n+\t\ttest -f \"$GIT_INDEX_FILE\" && rm \"$GIT_INDEX_FILE\"\n+\t' 0\n+\n+\tGIT_NOTES_REF= git log -1 $COMMIT | sed \"s/^/#/\" > \"$MSG_FILE\"\n+\n+\tCURRENT_HEAD=$(git show-ref \"$GIT_NOTES_REF\" | cut -f 1 -d ' ')\n+\tif [ -z \"$CURRENT_HEAD\" ]; then\n+\t\tPARENT=\n+\telse\n+\t\tPARENT=\"-p $CURRENT_HEAD\"\n+\t\tgit read-tree \"$GIT_NOTES_REF\" || die \"Could not read index\"\n+\t\tgit cat-file blob :$COMMIT >> \"$MSG_FILE\" 2> /dev/null\n+\tfi\n+\n+\tcore_editor=\"$(git config core.editor)\"\n+\t${GIT_EDITOR:-${core_editor:-${VISUAL:-${EDITOR:-vi}}}} \"$MSG_FILE\"\n+\n+\tgrep -v ^# < \"$MSG_FILE\" | git stripspace > \"$MSG_FILE\".processed\n+\tmv \"$MSG_FILE\".processed \"$MSG_FILE\"\n+\tif [ -s \"$MSG_FILE\" ]; then\n+\t\tBLOB=$(git hash-object -w \"$MSG_FILE\") ||\n+\t\t\tdie \"Could not write into object database\"\n+\t\tgit update-index --add --cacheinfo 0644 $BLOB $COMMIT ||\n+\t\t\tdie \"Could not write index\"\n+\telse\n+\t\ttest -z \"$CURRENT_HEAD\" &&\n+\t\t\tdie \"Will not initialise with empty tree\"\n+\t\tgit update-index --force-remove $COMMIT ||\n+\t\t\tdie \"Could not update index\"\n+\tfi\n+\n+\tTREE=$(git write-tree) || die \"Could not write tree\"\n+\tNEW_HEAD=$(echo Annotate $COMMIT | git commit-tree $TREE $PARENT) ||\n+\t\tdie \"Could not annotate\"\n+\tgit update-ref -m \"Annotate $COMMIT\" \\\n+\t\t\"$GIT_NOTES_REF\" $NEW_HEAD $CURRENT_HEAD\n+;;\n+show)\n+\tgit rev-parse -q --verify \"$GIT_NOTES_REF\":$COMMIT > /dev/null ||\n+\t\tdie \"No note for commit $COMMIT.\"\n+\tgit show \"$GIT_NOTES_REF\":$COMMIT\n+;;\n+*)\n+\tusage\n+esac\ndiff --git a/t/t3301-notes.sh b/t/t3301-notes.sh\nnew file mode 100755\nindex 0000000..73e53be\n--- /dev/null\n+++ b/t/t3301-notes.sh\n@@ -0,0 +1,114 @@\n+#!/bin/sh\n+#\n+# Copyright (c) 2007 Johannes E. Schindelin\n+#\n+\n+test_description='Test commit notes'\n+\n+. ./test-lib.sh\n+\n+cat > fake_editor.sh << \\EOF\n+echo \"$MSG\" > \"$1\"\n+echo \"$MSG\" >& 2\n+EOF\n+chmod a+x fake_editor.sh\n+VISUAL=./fake_editor.sh\n+export VISUAL\n+\n+test_expect_success 'cannot annotate non-existing HEAD' '\n+\t(MSG=3 && export MSG && test_must_fail git notes edit)\n+'\n+\n+test_expect_success setup '\n+\t: > a1 &&\n+\tgit add a1 &&\n+\ttest_tick &&\n+\tgit commit -m 1st &&\n+\t: > a2 &&\n+\tgit add a2 &&\n+\ttest_tick &&\n+\tgit commit -m 2nd\n+'\n+\n+test_expect_success 'need valid notes ref' '\n+\t(MSG=1 GIT_NOTES_REF=/ && export MSG GIT_NOTES_REF &&\n+\t test_must_fail git notes edit) &&\n+\t(MSG=2 GIT_NOTES_REF=/ && export MSG GIT_NOTES_REF &&\n+\t test_must_fail git notes show)\n+'\n+\n+test_expect_success 'refusing to edit in refs/heads/' '\n+\t(MSG=1 GIT_NOTES_REF=refs/heads/bogus &&\n+\t export MSG GIT_NOTES_REF &&\n+\t test_must_fail git notes edit)\n+'\n+\n+test_expect_success 'refusing to edit in refs/remotes/' '\n+\t(MSG=1 GIT_NOTES_REF=refs/remotes/bogus &&\n+\t export MSG GIT_NOTES_REF &&\n+\t test_must_fail git notes edit)\n+'\n+\n+# 1 indicates caught gracefully by die, 128 means git-show barked\n+test_expect_success 'handle empty notes gracefully' '\n+\tgit notes show ; test 1 = $?\n+'\n+\n+test_expect_success 'create notes' '\n+\tgit config core.notesRef refs/notes/commits &&\n+\tMSG=b1 git notes edit &&\n+\ttest ! -f .git/new-notes &&\n+\ttest 1 = $(git ls-tree refs/notes/commits | wc -l) &&\n+\ttest b1 = $(git notes show) &&\n+\tgit show HEAD^ &&\n+\ttest_must_fail git notes show HEAD^\n+'\n+\n+cat > expect << EOF\n+commit 268048bfb8a1fb38e703baceb8ab235421bf80c5\n+Author: A U Thor \n+Date: Thu Apr 7 15:14:13 2005 -0700\n+\n+ 2nd\n+\n+Notes:\n+ b1\n+EOF\n+\n+test_expect_success 'show notes' '\n+\t! (git cat-file commit HEAD | grep b1) &&\n+\tgit log -1 > output &&\n+\ttest_cmp expect output\n+'\n+test_expect_success 'create multi-line notes (setup)' '\n+\t: > a3 &&\n+\tgit add a3 &&\n+\ttest_tick &&\n+\tgit commit -m 3rd &&\n+\tMSG=\"b3\n+c3c3c3c3\n+d3d3d3\" git notes edit\n+'\n+\n+cat > expect-multiline << EOF\n+commit 1584215f1d29c65e99c6c6848626553fdd07fd75\n+Author: A U Thor \n+Date: Thu Apr 7 15:15:13 2005 -0700\n+\n+ 3rd\n+\n+Notes:\n+ b3\n+ c3c3c3c3\n+ d3d3d3\n+EOF\n+\n+printf \"\\n\" >> expect-multiline\n+cat expect >> expect-multiline\n+\n+test_expect_success 'show multi-line notes' '\n+\tgit log -2 > output &&\n+\ttest_cmp expect-multiline output\n+'\n+\n+test_done\n-- \n1.6.4.rc3.138.ga6b98.dirty\n"},{"id":"119007","messageId":"1248834326-31488-4-git-send-email-johan@herland.net","threadId":"20269","inReplyTo":"1248834326-31488-1-git-send-email-johan@herland.net","subject":"[PATCHv3 3/8] Speed up git notes lookup","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-07-29T02:25:21Z","receivedAt":"2009-07-29T02:25:21Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"From: Johannes Schindelin \n\nTo avoid looking up each and every commit in the notes ref's tree\nobject, which is very expensive, speed things up by slurping the tree\nobject's contents into a hash_map.\n\nThe idea for the hashmap singleton is from David Reiss, initial\nbenchmarking by Jeff King.\n\nNote: the implementation allows for arbitrary entries in the notes\ntree object, ignoring those that do not reference a valid object. This\nallows you to annotate arbitrary branches, or objects.\n\nThis patch has been improved by the following contributions:\n- Junio C Hamano: fixed an obvious error in initialize_hash_map()\n\nSigned-off-by: Johannes Schindelin \nSigned-off-by: Johan Herland \nSigned-off-by: Junio C Hamano \n---\n notes.c | 113 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++------\n 1 files changed, 102 insertions(+), 11 deletions(-)\n\ndiff --git a/notes.c b/notes.c\nindex b0cf553..bd73784 100644\n--- a/notes.c\n+++ b/notes.c\n@@ -4,16 +4,112 @@\n #include \"refs.h\"\n #include \"utf8.h\"\n #include \"strbuf.h\"\n+#include \"tree-walk.h\"\n+\n+struct entry {\n+\tunsigned char commit_sha1[20];\n+\tunsigned char notes_sha1[20];\n+};\n+\n+struct hash_map {\n+\tstruct entry *entries;\n+\toff_t count, size;\n+};\n \n static int initialized;\n+static struct hash_map hash_map;\n+\n+static int hash_index(struct hash_map *map, const unsigned char *sha1)\n+{\n+\tint i = ((*(unsigned int *)sha1) % map->size);\n+\n+\tfor (;;) {\n+\t\tunsigned char *current = map->entries[i].commit_sha1;\n+\n+\t\tif (!hashcmp(sha1, current))\n+\t\t\treturn i;\n+\n+\t\tif (is_null_sha1(current))\n+\t\t\treturn -1 - i;\n+\n+\t\tif (++i == map->size)\n+\t\t\ti = 0;\n+\t}\n+}\n+\n+static void add_entry(const unsigned char *commit_sha1,\n+\t\tconst unsigned char *notes_sha1)\n+{\n+\tint index;\n+\n+\tif (hash_map.count + 1 > hash_map.size >> 1) {\n+\t\tint i, old_size = hash_map.size;\n+\t\tstruct entry *old = hash_map.entries;\n+\n+\t\thash_map.size = old_size ? old_size << 1 : 64;\n+\t\thash_map.entries = (struct entry *)\n+\t\t\txcalloc(sizeof(struct entry), hash_map.size);\n+\n+\t\tfor (i = 0; i < old_size; i++)\n+\t\t\tif (!is_null_sha1(old[i].commit_sha1)) {\n+\t\t\t\tindex = -1 - hash_index(&hash_map,\n+\t\t\t\t\t\told[i].commit_sha1);\n+\t\t\t\tmemcpy(hash_map.entries + index, old + i,\n+\t\t\t\t\tsizeof(struct entry));\n+\t\t\t}\n+\t\tfree(old);\n+\t}\n+\n+\tindex = hash_index(&hash_map, commit_sha1);\n+\tif (index < 0) {\n+\t\tindex = -1 - index;\n+\t\thash_map.count++;\n+\t}\n+\n+\thashcpy(hash_map.entries[index].commit_sha1, commit_sha1);\n+\thashcpy(hash_map.entries[index].notes_sha1, notes_sha1);\n+}\n+\n+static void initialize_hash_map(const char *notes_ref_name)\n+{\n+\tunsigned char sha1[20], commit_sha1[20];\n+\tunsigned mode;\n+\tstruct tree_desc desc;\n+\tstruct name_entry entry;\n+\tvoid *buf;\n+\n+\tif (!notes_ref_name || read_ref(notes_ref_name, commit_sha1) ||\n+\t get_tree_entry(commit_sha1, \"\", sha1, &mode))\n+\t\treturn;\n+\n+\tbuf = fill_tree_descriptor(&desc, sha1);\n+\tif (!buf)\n+\t\tdie(\"Could not read %s for notes-index\", sha1_to_hex(sha1));\n+\n+\twhile (tree_entry(&desc, &entry))\n+\t\tif (!get_sha1(entry.path, commit_sha1))\n+\t\t\tadd_entry(commit_sha1, entry.sha1);\n+\tfree(buf);\n+}\n+\n+static unsigned char *lookup_notes(const unsigned char *commit_sha1)\n+{\n+\tint index;\n+\n+\tif (!hash_map.size)\n+\t\treturn NULL;\n+\n+\tindex = hash_index(&hash_map, commit_sha1);\n+\tif (index < 0)\n+\t\treturn NULL;\n+\treturn hash_map.entries[index].notes_sha1;\n+}\n \n void get_commit_notes(const struct commit *commit, struct strbuf *sb,\n \t\tconst char *output_encoding)\n {\n \tstatic const char *utf8 = \"utf-8\";\n-\tstruct strbuf name = STRBUF_INIT;\n-\tconst char *hex;\n-\tunsigned char sha1[20];\n+\tunsigned char *sha1;\n \tchar *msg, *msg_p;\n \tunsigned long linelen, msglen;\n \tenum object_type type;\n@@ -24,17 +120,12 @@ void get_commit_notes(const struct commit *commit, struct strbuf *sb,\n \t\t\tnotes_ref_name = getenv(GIT_NOTES_REF_ENVIRONMENT);\n \t\telse if (!notes_ref_name)\n \t\t\tnotes_ref_name = GIT_NOTES_DEFAULT_REF;\n-\t\tif (notes_ref_name && read_ref(notes_ref_name, sha1))\n-\t\t\tnotes_ref_name = NULL;\n+\t\tinitialize_hash_map(notes_ref_name);\n \t\tinitialized = 1;\n \t}\n \n-\tif (!notes_ref_name)\n-\t\treturn;\n-\n-\tstrbuf_addf(&name, \"%s:%s\", notes_ref_name,\n-\t\t\tsha1_to_hex(commit->object.sha1));\n-\tif (get_sha1(name.buf, sha1))\n+\tsha1 = lookup_notes(commit->object.sha1);\n+\tif (!sha1)\n \t\treturn;\n \n \tif (!(msg = read_sha1_file(sha1, &type, &msglen)) || !msglen ||\n-- \n1.6.4.rc3.138.ga6b98.dirty\n"},{"id":"119008","messageId":"1248834326-31488-5-git-send-email-johan@herland.net","threadId":"20269","inReplyTo":"1248834326-31488-1-git-send-email-johan@herland.net","subject":"[PATCHv3 4/8] Add an expensive test for git-notes","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-07-29T02:25:22Z","receivedAt":"2009-07-29T02:25:22Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"From: Johannes Schindelin \n\ngit-notes have the potential of being pretty expensive, so test with\na lot of commits. A lot. So to make things cheaper, you have to\nopt-in explicitely, by setting the environment variable\nGIT_NOTES_TIMING_TESTS.\n\nThis patch has been improved by the following contributions:\n- Junio C Hamano: tests: fix \"export var=val\"\n\nSigned-off-by: Johannes Schindelin \nSigned-off-by: Johan Herland \nSigned-off-by: Junio C Hamano \n---\n t/t3302-notes-index-expensive.sh | 98 ++++++++++++++++++++++++++++++++++++++\n 1 files changed, 98 insertions(+), 0 deletions(-)\n create mode 100755 t/t3302-notes-index-expensive.sh\n\ndiff --git a/t/t3302-notes-index-expensive.sh b/t/t3302-notes-index-expensive.sh\nnew file mode 100755\nindex 0000000..0ef3e95\n--- /dev/null\n+++ b/t/t3302-notes-index-expensive.sh\n@@ -0,0 +1,98 @@\n+#!/bin/sh\n+#\n+# Copyright (c) 2007 Johannes E. Schindelin\n+#\n+\n+test_description='Test commit notes index (expensive!)'\n+\n+. ./test-lib.sh\n+\n+test -z \"$GIT_NOTES_TIMING_TESTS\" && {\n+\tsay Skipping timing tests\n+\ttest_done\n+\texit\n+}\n+\n+create_repo () {\n+\tnumber_of_commits=$1\n+\tnr=0\n+\tparent=\n+\ttest -d .git || {\n+\tgit init &&\n+\ttree=$(git write-tree) &&\n+\twhile [ $nr -lt $number_of_commits ]; do\n+\t\ttest_tick &&\n+\t\tcommit=$(echo $nr | git commit-tree $tree $parent) ||\n+\t\t\treturn\n+\t\tparent=\"-p $commit\"\n+\t\tnr=$(($nr+1))\n+\tdone &&\n+\tgit update-ref refs/heads/master $commit &&\n+\t{\n+\t\tGIT_INDEX_FILE=.git/temp; export GIT_INDEX_FILE;\n+\t\tgit rev-list HEAD | cat -n | sed \"s/^[ \t][ \t]*/ /g\" |\n+\t\twhile read nr sha1; do\n+\t\t\tblob=$(echo note $nr | git hash-object -w --stdin) &&\n+\t\t\techo $sha1 | sed \"s/^/0644 $blob 0\t/\"\n+\t\tdone | git update-index --index-info &&\n+\t\ttree=$(git write-tree) &&\n+\t\ttest_tick &&\n+\t\tcommit=$(echo notes | git commit-tree $tree) &&\n+\t\tgit update-ref refs/notes/commits $commit\n+\t} &&\n+\tgit config core.notesRef refs/notes/commits\n+\t}\n+}\n+\n+test_notes () {\n+\tcount=$1 &&\n+\tgit config core.notesRef refs/notes/commits &&\n+\tgit log | grep \"^ \" > output &&\n+\ti=1 &&\n+\twhile [ $i -le $count ]; do\n+\t\techo \" $(($count-$i))\" &&\n+\t\techo \" note $i\" &&\n+\t\ti=$(($i+1));\n+\tdone > expect &&\n+\tgit diff expect output\n+}\n+\n+cat > time_notes << \\EOF\n+\tmode=$1\n+\ti=1\n+\twhile [ $i -lt $2 ]; do\n+\t\tcase $1 in\n+\t\tno-notes)\n+\t\t\tGIT_NOTES_REF=non-existing; export GIT_NOTES_REF\n+\t\t;;\n+\t\tnotes)\n+\t\t\tunset GIT_NOTES_REF\n+\t\t;;\n+\t\tesac\n+\t\tgit log >/dev/null\n+\t\ti=$(($i+1))\n+\tdone\n+EOF\n+\n+time_notes () {\n+\tfor mode in no-notes notes\n+\tdo\n+\t\techo $mode\n+\t\t/usr/bin/time sh ../time_notes $mode $1\n+\tdone\n+}\n+\n+for count in 10 100 1000 10000; do\n+\n+\tmkdir $count\n+\t(cd $count;\n+\n+\ttest_expect_success \"setup $count\" \"create_repo $count\"\n+\n+\ttest_expect_success 'notes work' \"test_notes $count\"\n+\n+\ttest_expect_success 'notes timing' \"time_notes 100\"\n+\t)\n+done\n+\n+test_done\n-- \n1.6.4.rc3.138.ga6b98.dirty\n"},{"id":"119009","messageId":"1248834326-31488-6-git-send-email-johan@herland.net","threadId":"20269","inReplyTo":"1248834326-31488-1-git-send-email-johan@herland.net","subject":"[PATCHv3 5/8] Teach \"-m \" and \"-F \" to \"git notes edit\"","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-07-29T02:25:23Z","receivedAt":"2009-07-29T02:25:23Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"The \"-m\" and \"-F\" options are already the established method\n(in both git-commit and git-tag) to specify a commit/tag message\nwithout invoking the editor. This patch teaches \"git notes edit\"\nto respect the same options for specifying a notes message without\ninvoking the editor.\n\nMultiple \"-m\" and/or \"-F\" options are concatenated as separate\nparagraphs.\n\nThe patch also updates the \"git notes\" documentation and adds\nselftests for the new functionality. Unfortunately, the added\nselftests include a couple of lines with trailing whitespace\n(without these the test will fail). This may cause git to warn\nabout \"whitespace errors\".\n\nSigned-off-by: Johan Herland \n---\n Documentation/git-notes.txt | 16 ++++++++++-\n git-notes.sh | 64 +++++++++++++++++++++++++++++++++++++-----\n t/t3301-notes.sh | 35 +++++++++++++++++++++++\n 3 files changed, 106 insertions(+), 9 deletions(-)\n\ndiff --git a/Documentation/git-notes.txt b/Documentation/git-notes.txt\nindex 7136016..94cceb1 100644\n--- a/Documentation/git-notes.txt\n+++ b/Documentation/git-notes.txt\n@@ -8,7 +8,7 @@ git-notes - Add/inspect commit notes\n SYNOPSIS\n --------\n [verse]\n-'git-notes' (edit | show) [commit]\n+'git-notes' (edit [-F | -m ] | show) [commit]\n \n DESCRIPTION\n -----------\n@@ -33,6 +33,20 @@ show::\n \tShow the notes for a given commit (defaults to HEAD).\n \n \n+OPTIONS\n+-------\n+-m ::\n+\tUse the given note message (instead of prompting).\n+\tIf multiple `-m` (or `-F`) options are given, their\n+\tvalues are concatenated as separate paragraphs.\n+\n+-F ::\n+\tTake the note message from the given file. Use '-' to\n+\tread the note message from the standard input.\n+\tIf multiple `-F` (or `-m`) options are given, their\n+\tvalues are concatenated as separate paragraphs.\n+\n+\n Author\n ------\n Written by Johannes Schindelin \ndiff --git a/git-notes.sh b/git-notes.sh\nindex f06c254..e642e47 100755\n--- a/git-notes.sh\n+++ b/git-notes.sh\n@@ -1,16 +1,59 @@\n #!/bin/sh\n \n-USAGE=\"(edit | show) [commit]\"\n+USAGE=\"(edit [-F | -m ] | show) [commit]\"\n . git-sh-setup\n \n-test -n \"$3\" && usage\n-\n test -z \"$1\" && usage\n ACTION=\"$1\"; shift\n \n test -z \"$GIT_NOTES_REF\" && GIT_NOTES_REF=\"$(git config core.notesref)\"\n test -z \"$GIT_NOTES_REF\" && GIT_NOTES_REF=\"refs/notes/commits\"\n \n+MESSAGE=\n+while test $# != 0\n+do\n+\tcase \"$1\" in\n+\t-m)\n+\t\ttest \"$ACTION\" = \"edit\" || usage\n+\t\tshift\n+\t\tif test \"$#\" = \"0\"; then\n+\t\t\tdie \"error: option -m needs an argument\"\n+\t\telse\n+\t\t\tif [ -z \"$MESSAGE\" ]; then\n+\t\t\t\tMESSAGE=\"$1\"\n+\t\t\telse\n+\t\t\t\tMESSAGE=\"$MESSAGE\n+\n+$1\"\n+\t\t\tfi\n+\t\t\tshift\n+\t\tfi\n+\t\t;;\n+\t-F)\n+\t\ttest \"$ACTION\" = \"edit\" || usage\n+\t\tshift\n+\t\tif test \"$#\" = \"0\"; then\n+\t\t\tdie \"error: option -F needs an argument\"\n+\t\telse\n+\t\t\tif [ -z \"$MESSAGE\" ]; then\n+\t\t\t\tMESSAGE=\"$(cat \"$1\")\"\n+\t\t\telse\n+\t\t\t\tMESSAGE=\"$MESSAGE\n+\n+$(cat \"$1\")\"\n+\t\t\tfi\n+\t\t\tshift\n+\t\tfi\n+\t\t;;\n+\t-*)\n+\t\tusage\n+\t\t;;\n+\t*)\n+\t\tbreak\n+\t\t;;\n+\tesac\n+done\n+\n COMMIT=$(git rev-parse --verify --default HEAD \"$@\") ||\n die \"Invalid commit: $@\"\n \n@@ -29,19 +72,24 @@ edit)\n \t\ttest -f \"$GIT_INDEX_FILE\" && rm \"$GIT_INDEX_FILE\"\n \t' 0\n \n-\tGIT_NOTES_REF= git log -1 $COMMIT | sed \"s/^/#/\" > \"$MSG_FILE\"\n-\n \tCURRENT_HEAD=$(git show-ref \"$GIT_NOTES_REF\" | cut -f 1 -d ' ')\n \tif [ -z \"$CURRENT_HEAD\" ]; then\n \t\tPARENT=\n \telse\n \t\tPARENT=\"-p $CURRENT_HEAD\"\n \t\tgit read-tree \"$GIT_NOTES_REF\" || die \"Could not read index\"\n-\t\tgit cat-file blob :$COMMIT >> \"$MSG_FILE\" 2> /dev/null\n \tfi\n \n-\tcore_editor=\"$(git config core.editor)\"\n-\t${GIT_EDITOR:-${core_editor:-${VISUAL:-${EDITOR:-vi}}}} \"$MSG_FILE\"\n+\tif [ -z \"$MESSAGE\" ]; then\n+\t\tGIT_NOTES_REF= git log -1 $COMMIT | sed \"s/^/#/\" > \"$MSG_FILE\"\n+\t\tif [ ! -z \"$CURRENT_HEAD\" ]; then\n+\t\t\tgit cat-file blob :$COMMIT >> \"$MSG_FILE\" 2> /dev/null\n+\t\tfi\n+\t\tcore_editor=\"$(git config core.editor)\"\n+\t\t${GIT_EDITOR:-${core_editor:-${VISUAL:-${EDITOR:-vi}}}} \"$MSG_FILE\"\n+\telse\n+\t\techo \"$MESSAGE\" > \"$MSG_FILE\"\n+\tfi\n \n \tgrep -v ^# < \"$MSG_FILE\" | git stripspace > \"$MSG_FILE\".processed\n \tmv \"$MSG_FILE\".processed \"$MSG_FILE\"\ndiff --git a/t/t3301-notes.sh b/t/t3301-notes.sh\nindex 73e53be..9eaa338 100755\n--- a/t/t3301-notes.sh\n+++ b/t/t3301-notes.sh\n@@ -110,5 +110,40 @@ test_expect_success 'show multi-line notes' '\n \tgit log -2 > output &&\n \ttest_cmp expect-multiline output\n '\n+test_expect_success 'create -m and -F notes (setup)' '\n+\t: > a4 &&\n+\tgit add a4 &&\n+\ttest_tick &&\n+\tgit commit -m 4th &&\n+\techo \"xyzzy\" > note5 &&\n+\tgit notes edit -m spam -F note5 -m \"foo\n+bar\n+baz\"\n+'\n+\n+cat > expect-m-and-F << EOF\n+commit 15023535574ded8b1a89052b32673f84cf9582b8\n+Author: A U Thor \n+Date: Thu Apr 7 15:16:13 2005 -0700\n+\n+ 4th\n+\n+Notes:\n+ spam\n+ \n+ xyzzy\n+ \n+ foo\n+ bar\n+ baz\n+EOF\n+\n+printf \"\\n\" >> expect-m-and-F\n+cat expect-multiline >> expect-m-and-F\n+\n+test_expect_success 'show -m and -F notes' '\n+\tgit log -3 > output &&\n+\ttest_cmp expect-m-and-F output\n+'\n \n test_done\n-- \n1.6.4.rc3.138.ga6b98.dirty\n"},{"id":"119010","messageId":"1248834326-31488-7-git-send-email-johan@herland.net","threadId":"20269","inReplyTo":"1248834326-31488-1-git-send-email-johan@herland.net","subject":"[PATCHv3 6/8] First draft of notes tree parser with support for fanout subtrees","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-07-29T02:25:24Z","receivedAt":"2009-07-29T02:25:24Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"This is a relatively straightforward implementation of parsing notes trees\nthat use fanout directories to limit the size of individual tree objects.\nThis first draft uses a simple linked list for holding unparsed subtree\nreferences (to be parsed on demand), and as such, this first draft\nconcentrates more on correctness than performance (AFAICS from t3302, there\nis no measurable performance impact when no fanout subtrees are present).\n\nThe semantics used when parsing notes trees (with regards to fanout subtrees)\nfollow Dscho's proposal fairly closely:\n- No concatenation/merging of notes is performed. If there are several notes\n objects referencing a given commit, only one of those objects are used.\n- If a notes object for a given commit is present in the \"root\" notes tree,\n no subtrees are consulted; the object in the root tree is used directly.\n- If there are more than one subtree that prefix-matches the given commit,\n only the subtree with the _longest_ matching prefix is consulted. This\n means that if the given commit is e.g. \"deadbeef\", and the notes tree have\n subtrees \"de\" and \"dead\", then the following paths in the notes tree are\n searched: \"deadbeef\", \"dead/beef\". Note that \"de/adbeef\" is NOT searched.\n (This might change in the future)\n- Fanout directories (subtrees) must references a whole number of bytes\n from the SHA1 sum they subdivide. E.g. subtrees \"dead\" and \"de\" are\n acceptable; \"d\" and \"dea\" are not.\n- Multiple levels of fanout is allowed. All the above rules apply recursively.\n E.g. \"de/adbeef\" is preferred over \"de/adbe/ef\", etc.\n\nThe patch includes new selftests for verifying the expected behaviour when\nloading notes trees with various fanout schemes.\n\nCc: Johannes Schindelin \nSigned-off-by: Johan Herland \n---\n notes.c | 165 ++++++++++++++++++++++++++++++++----\n t/t3303-notes-subtrees.sh | 206 +++++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 356 insertions(+), 15 deletions(-)\n create mode 100755 t/t3303-notes-subtrees.sh\n\ndiff --git a/notes.c b/notes.c\nindex bd73784..7b50a70 100644\n--- a/notes.c\n+++ b/notes.c\n@@ -16,8 +16,19 @@ struct hash_map {\n \toff_t count, size;\n };\n \n+struct subtree_entry {\n+\t/*\n+\t * SHA1 prefix is stored in the first 19 bytes (w/trailing NUL bytes);\n+\t * length of SHA1 prefix is stored in the last byte\n+\t */\n+\tunsigned char sha1_prefix_w_len[20];\n+\tunsigned char subtree_sha1[20];\n+\tstruct subtree_entry *next;\n+};\n+\n static int initialized;\n static struct hash_map hash_map;\n+static struct subtree_entry *subtree_list;\n \n static int hash_index(struct hash_map *map, const unsigned char *sha1)\n {\n@@ -70,39 +81,163 @@ static void add_entry(const unsigned char *commit_sha1,\n \thashcpy(hash_map.entries[index].notes_sha1, notes_sha1);\n }\n \n+/*\n+ * Convert a partial SHA1 sum (hex format) to a SHA1 value.\n+ * - hex - ASCII hex SHA1 segment\n+ * - hex_len - Length of above segment. Must be multiple of 2 between 0 and 40\n+ * - sha1 - Value of SHA1 is written here\n+ * - sha1_len - Max #bytes to store in sha1, Must be between 0 and 20,\n+ * and >= hex_len / 2\n+ * Returns -1 on error (invalid arguments or invalid ASCII hex SHA1 format).\n+ * Otherwise, returns number of bytes written to sha1 (hex_len / 2).\n+ * Pads sha1 with NULs up to sha1_len (not included in returned length).\n+ */\n+static int get_sha1_hex_segment(const char *hex, unsigned int hex_len,\n+\t\tunsigned char *sha1, unsigned int sha1_len)\n+{\n+\tunsigned int i, len = hex_len >> 1;\n+\tif (hex_len % 2 != 0 || len > sha1_len)\n+\t\treturn -1;\n+\tfor (i = 0; i < len; i++) {\n+\t\tunsigned int val = (hexval(hex[0]) << 4) | hexval(hex[1]);\n+\t\tif (val & ~0xff)\n+\t\t\treturn -1;\n+\t\t*sha1++ = val;\n+\t\thex += 2;\n+\t}\n+\tfor (; i < sha1_len; i++)\n+\t\t*sha1++ = 0;\n+\treturn len;\n+}\n+\n+static void load_subtree(struct subtree_entry *se)\n+{\n+\tunsigned char commit_sha1[20];\n+\tunsigned int prefix_len;\n+\tvoid *buf;\n+\tstruct tree_desc desc;\n+\tstruct name_entry entry;\n+\tstruct subtree_entry *tmp_list = NULL, *tmp_last = NULL;\n+\n+\tbuf = fill_tree_descriptor(&desc, se->subtree_sha1);\n+\tif (!buf)\n+\t\tdie(\"Could not read %s for notes-index\",\n+\t\t sha1_to_hex(se->subtree_sha1));\n+\n+\tprefix_len = se->sha1_prefix_w_len[19];\n+\tmemcpy(commit_sha1, se->sha1_prefix_w_len, prefix_len);\n+\twhile (tree_entry(&desc, &entry)) {\n+\t\tint len = get_sha1_hex_segment(entry.path, strlen(entry.path),\n+\t\t\t\tcommit_sha1 + prefix_len, 20 - prefix_len);\n+\t\tif (len < 0)\n+\t\t\tcontinue; /* entry.path is not a SHA1 sum. Skip */\n+\t\tlen += prefix_len;\n+\n+\t\t/* If commit SHA1 is complete, assume note object */\n+\t\tif (len == 20)\n+\t\t\tadd_entry(commit_sha1, entry.sha1);\n+\t\t/* If commit SHA1 is incomplete, assume note subtree */\n+\t\telse if (len < 20 && entry.mode == S_IFDIR) {\n+\t\t\tstruct subtree_entry *n = (struct subtree_entry *)\n+\t\t\t\txcalloc(sizeof(struct subtree_entry), 1);\n+\t\t\thashcpy(n->sha1_prefix_w_len, commit_sha1);\n+\t\t\tn->sha1_prefix_w_len[19] = (unsigned char) len;\n+\t\t\thashcpy(n->subtree_sha1, entry.sha1);\n+\n+\t\t\tif (!tmp_list) {\n+\t\t\t\ttmp_list = n;\n+\t\t\t\ttmp_last = n;\n+\t\t\t}\n+\t\t\telse {\n+\t\t\t\tassert(!tmp_last->next);\n+\t\t\t\tassert(hashcmp(n->sha1_prefix_w_len,\n+\t\t\t\t\ttmp_last->sha1_prefix_w_len) > 0);\n+\t\t\t\ttmp_last->next = n;\n+\t\t\t\ttmp_last = n;\n+\t\t\t}\n+\t\t}\n+\t}\n+\tfree(buf);\n+\tif (tmp_list) {\n+\t\t/* insert tmp_list immediately after se */\n+\t\tassert(hashcmp(tmp_list->sha1_prefix_w_len,\n+\t\t\t\tse->sha1_prefix_w_len) > 0);\n+\t\tif (se->next) {\n+\t\t\tassert(hashcmp(se->next->sha1_prefix_w_len,\n+\t\t\t\t\ttmp_last->sha1_prefix_w_len) > 0);\n+\t\t\ttmp_last->next = se->next;\n+\t\t}\n+\t\tse->next = tmp_list;\n+\t}\n+}\n+\n static void initialize_hash_map(const char *notes_ref_name)\n {\n \tunsigned char sha1[20], commit_sha1[20];\n \tunsigned mode;\n-\tstruct tree_desc desc;\n-\tstruct name_entry entry;\n-\tvoid *buf;\n+\tstruct subtree_entry root_tree;\n \n \tif (!notes_ref_name || read_ref(notes_ref_name, commit_sha1) ||\n \t get_tree_entry(commit_sha1, \"\", sha1, &mode))\n \t\treturn;\n \n-\tbuf = fill_tree_descriptor(&desc, sha1);\n-\tif (!buf)\n-\t\tdie(\"Could not read %s for notes-index\", sha1_to_hex(sha1));\n+\thashclr(root_tree.sha1_prefix_w_len);\n+\thashcpy(root_tree.subtree_sha1, sha1);\n+\troot_tree.next = NULL;\n+\tload_subtree(&root_tree);\n+\tsubtree_list = root_tree.next;\n+}\n \n-\twhile (tree_entry(&desc, &entry))\n-\t\tif (!get_sha1(entry.path, commit_sha1))\n-\t\t\tadd_entry(commit_sha1, entry.sha1);\n-\tfree(buf);\n+/*\n+ * Compare the given commit SHA1 against the given subtree entry.\n+ * Return -1 if the commit SHA1 cannot exist within the given subtree, or any\n+ * subtree following it.\n+ * Return 0 if the commit SHA1 _may_ exist within the given subtree.\n+ * Return 1 if the commit SHA1 cannot exist within the given subtree, but may\n+ * exist within a subtree following it.\n+ */\n+static int commit_subtree_cmp(const unsigned char *commit_sha1,\n+\t\tconst struct subtree_entry *entry)\n+{\n+\tunsigned int prefix_len = entry->sha1_prefix_w_len[19];\n+\treturn memcmp(commit_sha1, entry->sha1_prefix_w_len, prefix_len);\n+}\n+\n+static struct subtree_entry *lookup_subtree(const unsigned char *commit_sha1)\n+{\n+\tstruct subtree_entry *found = NULL, *cur = subtree_list;\n+\twhile (cur) {\n+\t\tint cmp = commit_subtree_cmp(commit_sha1, cur);\n+\t\tif (!cmp)\n+\t\t\tfound = cur;\n+\t\tif (cmp < 0)\n+\t\t\tbreak;\n+\t\tcur = cur->next;\n+\t}\n+\treturn found;\n }\n \n static unsigned char *lookup_notes(const unsigned char *commit_sha1)\n {\n \tint index;\n+\tstruct subtree_entry *subtree;\n \n-\tif (!hash_map.size)\n-\t\treturn NULL;\n+\t/* First, try to find the commit SHA1 directly in hash map */\n+\tindex = hash_map.size ? hash_index(&hash_map, commit_sha1) : -1;\n+\tif (index >= 0)\n+\t\treturn hash_map.entries[index].notes_sha1;\n \n-\tindex = hash_index(&hash_map, commit_sha1);\n-\tif (index < 0)\n+\t/* Next, try finding a subtree that may contain the commit SHA1 */\n+\tsubtree = lookup_subtree(commit_sha1);\n+\n+\t/* Give up if no subtree found, or if subtree is already loaded */\n+\tif (!subtree || is_null_sha1(subtree->subtree_sha1))\n \t\treturn NULL;\n-\treturn hash_map.entries[index].notes_sha1;\n+\n+\t/* Load subtree into hash_map, and retry lookup recursively */\n+\tload_subtree(subtree);\n+\thashclr(subtree->subtree_sha1);\n+\treturn lookup_notes(commit_sha1);\n }\n \n void get_commit_notes(const struct commit *commit, struct strbuf *sb,\ndiff --git a/t/t3303-notes-subtrees.sh b/t/t3303-notes-subtrees.sh\nnew file mode 100755\nindex 0000000..40bb3f4\n--- /dev/null\n+++ b/t/t3303-notes-subtrees.sh\n@@ -0,0 +1,206 @@\n+#!/bin/sh\n+\n+test_description='Test commit notes organized in subtrees'\n+\n+. ./test-lib.sh\n+\n+number_of_commits=100\n+\n+start_note_commit () {\n+\ttest_tick &&\n+\tcat < $GIT_COMMITTER_DATE\n+data < output &&\n+\ti=$number_of_commits &&\n+\twhile [ $i -gt 0 ]; do\n+\t\techo \" commit #$i\" &&\n+\t\techo \" note for commit #$i\" &&\n+\t\ti=$(($i-1));\n+\tdone > expect &&\n+\ttest_cmp expect output\n+}\n+\n+test_expect_success 'setup: create $number_of_commits commits' '\n+\n+\t(\n+\t\tnr=0 &&\n+\t\twhile [ $nr -lt $number_of_commits ]; do\n+\t\t\tnr=$(($nr+1)) &&\n+\t\t\ttest_tick &&\n+\t\t\tcat < $GIT_COMMITTER_DATE\n+data < $GIT_COMMITTER_DATE\n+data <\nSigned-off-by: Johan Herland \n---\n Documentation/git-fast-import.txt | 45 +++++++++--\n fast-import.c | 88 +++++++++++++++++++-\n t/t9300-fast-import.sh | 166 +++++++++++++++++++++++++++++++++++++\n 3 files changed, 289 insertions(+), 10 deletions(-)\n\ndiff --git a/Documentation/git-fast-import.txt b/Documentation/git-fast-import.txt\nindex c2f483a..288032c 100644\n--- a/Documentation/git-fast-import.txt\n+++ b/Documentation/git-fast-import.txt\n@@ -316,7 +316,7 @@ change to the project.\n \tdata\n \t('from' SP LF)?\n \t('merge' SP LF)?\n-\t(filemodify | filedelete | filecopy | filerename | filedeleteall)*\n+\t(filemodify | filedelete | filecopy | filerename | filedeleteall | notemodify)*\n \tLF?\n ....\n \n@@ -339,14 +339,13 @@ commit message use a 0 length data. Commit messages are free-form\n and are not interpreted by Git. Currently they must be encoded in\n UTF-8, as fast-import does not permit other encodings to be specified.\n \n-Zero or more `filemodify`, `filedelete`, `filecopy`, `filerename`\n-and `filedeleteall` commands\n+Zero or more `filemodify`, `filedelete`, `filecopy`, `filerename`,\n+`filedeleteall` and `notemodify` commands\n may be included to update the contents of the branch prior to\n creating the commit. These commands may be supplied in any order.\n However it is recommended that a `filedeleteall` command precede\n-all `filemodify`, `filecopy` and `filerename` commands in the same\n-commit, as `filedeleteall`\n-wipes the branch clean (see below).\n+all `filemodify`, `filecopy`, `filerename` and `notemodify` commands in\n+the same commit, as `filedeleteall` wipes the branch clean (see below).\n \n The `LF` after the command is optional (it used to be required).\n \n@@ -595,6 +594,40 @@ more memory per active branch (less than 1 MiB for even most large\n projects); so frontends that can easily obtain only the affected\n paths for a commit are encouraged to do so.\n \n+`notemodify`\n+^^^^^^^^^^^^\n+Included in a `commit` command to add a new note (annotating a given\n+commit) or change the content of an existing note. This command has\n+two different means of specifying the content of the note.\n+\n+External data format::\n+\tThe data content for the note was already supplied by a prior\n+\t`blob` command. The frontend just needs to connect it to the\n+\tcommit that is to be annotated.\n++\n+....\n+\t'N' SP SP LF\n+....\n++\n+Here `` can be either a mark reference (`:`)\n+set by a prior `blob` command, or a full 40-byte SHA-1 of an\n+existing Git blob object.\n+\n+Inline data format::\n+\tThe data content for the note has not been supplied yet.\n+\tThe frontend wants to supply it as part of this modify\n+\tcommand.\n++\n+....\n+\t'N' SP 'inline' SP LF\n+\tdata\n+....\n++\n+See below for a detailed description of the `data` command.\n+\n+In both formats `` is any of the commit specification\n+expressions also accepted by `from` (see above).\n+\n `mark`\n ~~~~~~\n Arranges for fast-import to save a reference to the current object, allowing\ndiff --git a/fast-import.c b/fast-import.c\nindex 7ef9865..97e6e9e 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -22,8 +22,8 @@ Format of STDIN stream:\n ('author' sp name sp '<' email '>' sp when lf)?\n 'committer' sp name sp '<' email '>' sp when lf\n commit_msg\n- ('from' sp (ref_str | hexsha1 | sha1exp_str | idnum) lf)?\n- ('merge' sp (ref_str | hexsha1 | sha1exp_str | idnum) lf)*\n+ ('from' sp committish lf)?\n+ ('merge' sp committish lf)*\n file_change*\n lf?;\n commit_msg ::= data;\n@@ -41,15 +41,18 @@ Format of STDIN stream:\n file_obm ::= 'M' sp mode sp (hexsha1 | idnum) sp path_str lf;\n file_inm ::= 'M' sp mode sp 'inline' sp path_str lf\n data;\n+ note_obm ::= 'N' sp (hexsha1 | idnum) sp committish lf;\n+ note_inm ::= 'N' sp 'inline' sp committish lf\n+ data;\n \n new_tag ::= 'tag' sp tag_str lf\n- 'from' sp (ref_str | hexsha1 | sha1exp_str | idnum) lf\n+ 'from' sp committish lf\n ('tagger' sp name sp '<' email '>' sp when lf)?\n tag_msg;\n tag_msg ::= data;\n \n reset_branch ::= 'reset' sp ref_str lf\n- ('from' sp (ref_str | hexsha1 | sha1exp_str | idnum) lf)?\n+ ('from' sp committish lf)?\n lf?;\n \n checkpoint ::= 'checkpoint' lf\n@@ -88,6 +91,7 @@ Format of STDIN stream:\n # stream formatting is: \\, \" and LF. Otherwise these values\n # are UTF8.\n #\n+ committish ::= (ref_str | hexsha1 | sha1exp_str | idnum);\n ref_str ::= ref;\n sha1exp_str ::= sha1exp;\n tag_str ::= tag;\n@@ -2003,6 +2007,80 @@ static void file_change_cr(struct branch *b, int rename)\n \t\tleaf.tree);\n }\n \n+static void note_change_n(struct branch *b)\n+{\n+\tconst char *p = command_buf.buf + 2;\n+\tstatic struct strbuf uq = STRBUF_INIT;\n+\tstruct object_entry *oe = oe;\n+\tstruct branch *s;\n+\tunsigned char sha1[20], commit_sha1[20];\n+\tuint16_t inline_data = 0;\n+\n+\t/* or 'inline' */\n+\tif (*p == ':') {\n+\t\tchar *x;\n+\t\toe = find_mark(strtoumax(p + 1, &x, 10));\n+\t\thashcpy(sha1, oe->sha1);\n+\t\tp = x;\n+\t} else if (!prefixcmp(p, \"inline\")) {\n+\t\tinline_data = 1;\n+\t\tp += 6;\n+\t} else {\n+\t\tif (get_sha1_hex(p, sha1))\n+\t\t\tdie(\"Invalid SHA1: %s\", command_buf.buf);\n+\t\toe = find_object(sha1);\n+\t\tp += 40;\n+\t}\n+\tif (*p++ != ' ')\n+\t\tdie(\"Missing space after SHA1: %s\", command_buf.buf);\n+\n+\t/* */\n+\ts = lookup_branch(p);\n+\tif (s) {\n+\t\thashcpy(commit_sha1, s->sha1);\n+\t} else if (*p == ':') {\n+\t\tuintmax_t commit_mark = strtoumax(p + 1, NULL, 10);\n+\t\tstruct object_entry *commit_oe = find_mark(commit_mark);\n+\t\tif (commit_oe->type != OBJ_COMMIT)\n+\t\t\tdie(\"Mark :%\" PRIuMAX \" not a commit\", commit_mark);\n+\t\thashcpy(commit_sha1, commit_oe->sha1);\n+\t} else if (!get_sha1(p, commit_sha1)) {\n+\t\tunsigned long size;\n+\t\tchar *buf = read_object_with_reference(commit_sha1,\n+\t\t\tcommit_type, &size, commit_sha1);\n+\t\tif (!buf || size < 46)\n+\t\t\tdie(\"Not a valid commit: %s\", p);\n+\t\tfree(buf);\n+\t} else\n+\t\tdie(\"Invalid ref name or SHA1 expression: %s\", p);\n+\n+\tif (inline_data) {\n+\t\tstatic struct strbuf buf = STRBUF_INIT;\n+\n+\t\tif (p != uq.buf) {\n+\t\t\tstrbuf_addstr(&uq, p);\n+\t\t\tp = uq.buf;\n+\t\t}\n+\t\tread_next_command();\n+\t\tparse_data(&buf);\n+\t\tstore_object(OBJ_BLOB, &buf, &last_blob, sha1, 0);\n+\t} else if (oe) {\n+\t\tif (oe->type != OBJ_BLOB)\n+\t\t\tdie(\"Not a blob (actually a %s): %s\",\n+\t\t\t\ttypename(oe->type), command_buf.buf);\n+\t} else {\n+\t\tenum object_type type = sha1_object_info(sha1, NULL);\n+\t\tif (type < 0)\n+\t\t\tdie(\"Blob not found: %s\", command_buf.buf);\n+\t\tif (type != OBJ_BLOB)\n+\t\t\tdie(\"Not a blob (actually a %s): %s\",\n+\t\t\t typename(type), command_buf.buf);\n+\t}\n+\n+\ttree_content_set(&b->branch_tree, sha1_to_hex(commit_sha1), sha1,\n+\t\tS_IFREG | 0644, NULL);\n+}\n+\n static void file_change_deleteall(struct branch *b)\n {\n \trelease_tree_content_recursive(b->branch_tree.tree);\n@@ -2172,6 +2250,8 @@ static void parse_new_commit(void)\n \t\t\tfile_change_cr(b, 1);\n \t\telse if (!prefixcmp(command_buf.buf, \"C \"))\n \t\t\tfile_change_cr(b, 0);\n+\t\telse if (!prefixcmp(command_buf.buf, \"N \"))\n+\t\t\tnote_change_n(b);\n \t\telse if (!strcmp(\"deleteall\", command_buf.buf))\n \t\t\tfile_change_deleteall(b);\n \t\telse {\ndiff --git a/t/t9300-fast-import.sh b/t/t9300-fast-import.sh\nindex 821be7c..b49815d 100755\n--- a/t/t9300-fast-import.sh\n+++ b/t/t9300-fast-import.sh\n@@ -1088,4 +1088,170 @@ INPUT_END\n test_expect_success 'P: fail on blob mark in gitlink' '\n test_must_fail git fast-import input < $GIT_COMMITTER_DATE\n+data < $GIT_COMMITTER_DATE\n+data < $GIT_COMMITTER_DATE\n+data < $GIT_COMMITTER_DATE\n+data <expect < $GIT_COMMITTER_DATE\n+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE\n+\n+first (:3)\n+EOF\n+test_expect_success \\\n+\t'Q: verify first commit' \\\n+\t'git cat-file commit notes-test~2 | sed 1d >actual &&\n+\ttest_cmp expect actual'\n+\n+cat >expect < $GIT_COMMITTER_DATE\n+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE\n+\n+second (:5)\n+EOF\n+test_expect_success \\\n+\t'Q: verify second commit' \\\n+\t'git cat-file commit notes-test^ | sed 1d >actual &&\n+\ttest_cmp expect actual'\n+\n+cat >expect < $GIT_COMMITTER_DATE\n+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE\n+\n+third (:6)\n+EOF\n+test_expect_success \\\n+\t'Q: verify third commit' \\\n+\t'git cat-file commit notes-test | sed 1d >actual &&\n+\ttest_cmp expect actual'\n+\n+cat >expect < $GIT_COMMITTER_DATE\n+committer $GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE\n+\n+notes (:9)\n+EOF\n+test_expect_success \\\n+\t'Q: verify notes commit' \\\n+\t'git cat-file commit refs/notes/foobar | sed 1d >actual &&\n+\ttest_cmp expect actual'\n+\n+cat >expect.unsorted <expect\n+test_expect_success \\\n+\t'Q: verify notes tree' \\\n+\t'git cat-file -p refs/notes/foobar^{tree} | sed \"s/ [0-9a-f]*\t/ /\" >actual &&\n+\t test_cmp expect actual'\n+\n+echo \"$note1_data\" >expect\n+test_expect_success \\\n+\t'Q: verify note for first commit' \\\n+\t'git cat-file blob refs/notes/foobar:$commit1 >actual && test_cmp expect actual'\n+\n+echo \"$note2_data\" >expect\n+test_expect_success \\\n+\t'Q: verify note for second commit' \\\n+\t'git cat-file blob refs/notes/foobar:$commit2 >actual && test_cmp expect actual'\n+\n+echo \"$note3_data\" >expect\n+test_expect_success \\\n+\t'Q: verify note for third commit' \\\n+\t'git cat-file blob refs/notes/foobar:$commit3 >actual && test_cmp expect actual'\n+\n test_done\n-- \n1.6.4.rc3.138.ga6b98.dirty\n"},{"id":"119011","messageId":"1248834326-31488-9-git-send-email-johan@herland.net","threadId":"20269","inReplyTo":"1248834326-31488-1-git-send-email-johan@herland.net","subject":"[PATCHv3 8/8] t3302-notes-index-expensive: Speed up create_repo()","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-07-29T02:25:26Z","receivedAt":"2009-07-29T02:25:26Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"Creating repos with 10/100/1000/10000 commits and notes takes a lot of time.\nHowever, using git-fast-import to do the job is a lot more efficient than\nusing plumbing commands to do the same.\n\nThis patch decreases the overall run-time of this test on my machine from\n~3 to ~1 minutes.\n\nSigned-off-by: Johan Herland \n---\n t/t3302-notes-index-expensive.sh | 74 ++++++++++++++++++++++++--------------\n 1 files changed, 47 insertions(+), 27 deletions(-)\n\ndiff --git a/t/t3302-notes-index-expensive.sh b/t/t3302-notes-index-expensive.sh\nindex 0ef3e95..ee84fc4 100755\n--- a/t/t3302-notes-index-expensive.sh\n+++ b/t/t3302-notes-index-expensive.sh\n@@ -16,30 +16,50 @@ test -z \"$GIT_NOTES_TIMING_TESTS\" && {\n create_repo () {\n \tnumber_of_commits=$1\n \tnr=0\n-\tparent=\n \ttest -d .git || {\n \tgit init &&\n-\ttree=$(git write-tree) &&\n-\twhile [ $nr -lt $number_of_commits ]; do\n-\t\ttest_tick &&\n-\t\tcommit=$(echo $nr | git commit-tree $tree $parent) ||\n-\t\t\treturn\n-\t\tparent=\"-p $commit\"\n-\t\tnr=$(($nr+1))\n-\tdone &&\n-\tgit update-ref refs/heads/master $commit &&\n-\t{\n-\t\tGIT_INDEX_FILE=.git/temp; export GIT_INDEX_FILE;\n-\t\tgit rev-list HEAD | cat -n | sed \"s/^[ \t][ \t]*/ /g\" |\n-\t\twhile read nr sha1; do\n-\t\t\tblob=$(echo note $nr | git hash-object -w --stdin) &&\n-\t\t\techo $sha1 | sed \"s/^/0644 $blob 0\t/\"\n-\t\tdone | git update-index --index-info &&\n-\t\ttree=$(git write-tree) &&\n+\t(\n+\t\twhile [ $nr -lt $number_of_commits ]; do\n+\t\t\tnr=$(($nr+1))\n+\t\t\tmark=$(($nr+$nr))\n+\t\t\tnotemark=$(($mark+1))\n+\t\t\ttest_tick &&\n+\t\t\tcat < $GIT_COMMITTER_DATE\n+data <> note_commit\n+\t\tdone &&\n \t\ttest_tick &&\n-\t\tcommit=$(echo notes | git commit-tree $tree) &&\n-\t\tgit update-ref refs/notes/commits $commit\n-\t} &&\n+\t\tcat < $GIT_COMMITTER_DATE\n+data < output &&\n-\ti=1 &&\n-\twhile [ $i -le $count ]; do\n-\t\techo \" $(($count-$i))\" &&\n-\t\techo \" note $i\" &&\n-\t\ti=$(($i+1));\n+\ti=$count &&\n+\twhile [ $i -gt 0 ]; do\n+\t\techo \" commit #$i\" &&\n+\t\techo \" note for commit #$i\" &&\n+\t\ti=$(($i-1));\n \tdone > expect &&\n-\tgit diff expect output\n+\ttest_cmp expect output\n }\n \n cat > time_notes << \\EOF\n-- \n1.6.4.rc3.138.ga6b98.dirty\n"},{"id":"119027","messageId":"200907290957.36000.trast@student.ethz.ch","threadId":"20269","inReplyTo":"1248834326-31488-6-git-send-email-johan@herland.net","subject":"Re: [PATCHv3 5/8] Teach \"-m \" and \"-F \" to \"git notes edit\"","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2009-07-29T07:57:34Z","receivedAt":"2009-07-29T07:57:34Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Johan Herland wrote:\n> diff --git a/t/t3301-notes.sh b/t/t3301-notes.sh\n[...]\n> +cat > expect-m-and-F << EOF\n> +commit 15023535574ded8b1a89052b32673f84cf9582b8\n> +Author: A U Thor \n> +Date: Thu Apr 7 15:16:13 2005 -0700\n> +\n> + 4th\n> +\n> +Notes:\n> + spam\n> + \n> + xyzzy\n> + \n> + foo\n\nThere's significant trailing whitespace here (in the lines between\nspam, xyzzy and foo) that initially broke the test for me because I\nuse apply.whitespace=fix. Can you guard the whitespace if it is\nreally important, with something like\n\nsed 's/#$//' > expect < wrote:\n> +void get_commit_notes(const struct commit *commit, struct strbuf *sb,\n> +               const char *output_encoding)\n> +{\n> +       static const char *utf8 = \"utf-8\";\n\nUsing an array\n\n const char utf8[] = \"utf-8\";\n\ncosts you less BSS (no separate storage for the pointer).\n\n> @@ -963,5 +964,9 @@ void pretty_print_commit(enum cmit_fmt fmt, const struct commit *commit,\n> +\n> +       if (fmt != CMIT_FMT_ONELINE)\n> +               get_commit_notes(commit, sb, encoding);\n> +\n\nSomeday we will need a way to switch off the display of notes\nwithout resolving to oneline format.\nIs there a notes specifier for the printf-like log message formatting\n(--pretty=format: or --format) planned, BTW?\n"},{"id":"119063","messageId":"20090729142121.GB1033@spearce.org","threadId":"20269","inReplyTo":"1248834326-31488-8-git-send-email-johan@herland.net","subject":"Re: [PATCHv3 7/8] fast-import: Add support for importing commit notes","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-07-29T14:21:21Z","receivedAt":"2009-07-29T14:21:21Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Johan Herland wrote:\n> Introduce a 'notemodify' subcommand of the 'commit' command. This subcommand\n> is similar to 'filemodify', except that no mode is supplied (all notes have\n> mode 0644), and the path is set to the hex SHA1 of the given \"comittish\".\n> \n> This enables fast import of note objects along with their associated commits,\n> since the notes can now be named using the mark references of their\n> corresponding commits.\n> \n> The patch also includes a test case of the added functionality.\n\nSeems sane to me.\n\nAcked-by: Shawn O. Pearce \n \n> +static void note_change_n(struct branch *b)\n> +{\n...\n> +\ttree_content_set(&b->branch_tree, sha1_to_hex(commit_sha1), sha1,\n> +\t\tS_IFREG | 0644, NULL);\n\nI thought you wanted to use the note code to handle the name\nformatting here?\n\n-- \nShawn.\n"},{"id":"119079","messageId":"alpine.DEB.1.00.0907291839350.7626@intel-tinevez-2-302","threadId":"20269","inReplyTo":"81b0412b0907290152w27c1b5b5l9efbd6980d4f904e@mail.gmail.com","subject":"Re: [PATCHv3 1/8] Introduce commit notes","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-07-29T16:40:41Z","receivedAt":"2009-07-29T16:40:41Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Wed, 29 Jul 2009, Alex Riesen wrote:\n\n> On Wed, Jul 29, 2009 at 04:25, Johan Herland wrote:\n> > +void get_commit_notes(const struct commit *commit, struct strbuf *sb,\n> > +               const char *output_encoding)\n> > +{\n> > +       static const char *utf8 = \"utf-8\";\n> \n> Using an array\n> \n> const char utf8[] = \"utf-8\";\n> \n> costs you less BSS (no separate storage for the pointer).\n\nGood to know!\n\n> > @@ -963,5 +964,9 @@ void pretty_print_commit(enum cmit_fmt fmt, const struct commit *commit,\n> > +\n> > +       if (fmt != CMIT_FMT_ONELINE)\n> > +               get_commit_notes(commit, sb, encoding);\n> > +\n> \n> Someday we will need a way to switch off the display of notes\n> without resolving to oneline format.\n> Is there a notes specifier for the printf-like log message formatting\n> (--pretty=format: or --format) planned, BTW?\n\nThat would probably be something like \"GIT_NOTES_REF=nyanyanya git log\"?\n\nCiao,\nDscho\n"},{"id":"119080","messageId":"alpine.DEB.1.00.0907291842360.7626@intel-tinevez-2-302","threadId":"20269","inReplyTo":"1248834326-31488-7-git-send-email-johan@herland.net","subject":"Re: [PATCHv3 6/8] First draft of notes tree parser with support for fanout subtrees","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-07-29T16:45:36Z","receivedAt":"2009-07-29T16:45:36Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Wed, 29 Jul 2009, Johan Herland wrote:\n\n> This is a relatively straightforward implementation of parsing notes \n> trees that use fanout directories to limit the size of individual tree \n> objects. This first draft uses a simple linked list for holding unparsed \n> subtree references (to be parsed on demand), and as such, this first \n> draft concentrates more on correctness than performance (AFAICS from \n> t3302, there is no measurable performance impact when no fanout subtrees \n> are present).\n\nI know you want to have something working first and optimize then, but I \nimagined that the hashmap can actually contain the entries of the partial \nhashes, too. You'll need to extend the data type, of course, to be able \nto say just how many digits of the SHA-1 are valid, and I guess for \nconsistency you'll need to pad with 0s.\n\nBTW have you done any performance benchmarks? If so, how do they look?\n\nCiao,\nDscho\n"},{"id":"119081","messageId":"alpine.DEB.1.00.0907291845540.7626@intel-tinevez-2-302","threadId":"20269","inReplyTo":"1248834326-31488-9-git-send-email-johan@herland.net","subject":"Re: [PATCHv3 8/8] t3302-notes-index-expensive: Speed up create_repo()","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-07-29T16:46:06Z","receivedAt":"2009-07-29T16:46:06Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Wed, 29 Jul 2009, Johan Herland wrote:\n\n> Creating repos with 10/100/1000/10000 commits and notes takes a lot of time.\n> However, using git-fast-import to do the job is a lot more efficient than\n> using plumbing commands to do the same.\n> \n> This patch decreases the overall run-time of this test on my machine from\n> ~3 to ~1 minutes.\n\nACK!\n\nCiao,\nDscho\n"},{"id":"119128","messageId":"200907300218.40203.johan@herland.net","threadId":"20269","inReplyTo":"alpine.DEB.1.00.0907291842360.7626@intel-tinevez-2-302","subject":"Testing performance of the notes lookup code (Was: [PATCHv3 6/8] First draft of notes tree parser with support for fanout subtrees)","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-07-30T00:18:39Z","receivedAt":"2009-07-30T00:18:39Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Wednesday 29 July 2009, Johannes Schindelin wrote:\n> On Wed, 29 Jul 2009, Johan Herland wrote:\n> > This is a relatively straightforward implementation of parsing notes\n> > trees that use fanout directories to limit the size of individual tree\n> > objects. This first draft uses a simple linked list for holding\n> > unparsed subtree references (to be parsed on demand), and as such, this\n> > first draft concentrates more on correctness than performance (AFAICS\n> > from t3302, there is no measurable performance impact when no fanout\n> > subtrees are present).\n>\n> I know you want to have something working first and optimize then, but I\n> imagined that the hashmap can actually contain the entries of the partial\n> hashes, too. You'll need to extend the data type, of course, to be able\n> to say just how many digits of the SHA-1 are valid, and I guess for\n> consistency you'll need to pad with 0s.\n\nThanks for the ideas. I will look into this once I have a set of\nperformance tests that I feel give a better picture of the notes parsing\nperformance.\n\n> BTW have you done any performance benchmarks? If so, how do they look?\n\nI've just started. As I said above, t3302 (which has no fanout) is not\nnegatively affected by my current implementation. However this does not\nsay much (only that the current draft doesn't screw up completely...).\n\nI've started making some scripts for more accurately testing the\nperformance of the notes parsing code at different fanout levels.\nAt the end of this email you will find a patch with my current state of\nthese scripts. (This patch is not meant to be included in the jh/notes\ntopic. It is only extra scripts for those interested in testing the\nperformance of this particular piece of code.)\n\n\nMETHODOLOGY\n\nSo far, there are 3 scripts:\n- create_test_repo.sh: Creates a repo with 100,000 commits and one note\n object per commit. Also creates 3 notes trees, each holding all\n 100,000 notes, but in different fanout structures:\n - refs/notes/fanout0: all 100,000 notes directly inside the root tree.\n - refs/notes/fanout1: notes are stored in a 2/38 structure (i.e. split\n into 256 subtrees within the root tree).\n - refs/notes/fanout2: notes are stored in a 2/2/36 structure (i.e. an\n additional 256-fanout within each of the 256 subtrees).\n\n- verify_correctness.sh: Verify that the \"git log\" output for each of the\n 3 notes refs is as expected. This is just to verify that the notes\n parsing code is actually doing the right job.\n\n- test_performance.sh: For each of the 3 notes refs, run \"git log -n 10\"\n 100 times, and report the time used. I feel this gives a more accurate\n impression of the real-world performance of the notes parsing code,\n since we:\n - Test the code at several fanout levels\n - Only lookup _some_ of the notes (looking up _all_ of the notes, i.e.\n \"git log\" without -n, is clearly the worst-case scenario for any code\n that loads subtree on-demand).\n\nThere is also a config script - config.sh - where you can tweak all of\nthe above test parameters.\n\n\nPRELIMINARY RESULTS\n\nRunning the above test_performance.sh on the current state of jh/notes\ngive the following output on my machine:\n\n $ ./test_performance.sh\n Timing 100 reps of 'git log -n 10 refs/heads/master >/dev/null' at fanout level 0...\n 30.56user 2.08system 0:32.71elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n 0inputs+0outputs (0major+1038490minor)pagefaults 0swaps\n\n Timing 100 reps of 'git log -n 10 refs/heads/master >/dev/null' at fanout level 1...\n 1.64user 0.20system 0:01.88elapsed 98%CPU (0avgtext+0avgdata 0maxresident)k\n 0inputs+0outputs (0major+104883minor)pagefaults 0swaps\n\n Timing 100 reps of 'git log -n 10 refs/heads/master >/dev/null' at fanout level 2...\n 0.48user 0.18system 0:00.65elapsed 101%CPU (0avgtext+0avgdata 0maxresident)k\n 0inputs+0outputs (0major+94283minor)pagefaults 0swaps\n\n...which indicates that even with my straightforward first draft based on\na simple linked list, there are huge performance wins in using one or more\nfanout levels.\n\n\nTHE SCRIPTS\n\n---\n notes_performance/config.sh | 9 +++\n notes_performance/create_test_repo.sh | 90 +++++++++++++++++++++++++++++++\n notes_performance/test_performance.sh | 31 +++++++++++\n notes_performance/verify_correctness.sh | 32 +++++++++++\n 4 files changed, 162 insertions(+), 0 deletions(-)\n create mode 100644 notes_performance/config.sh\n create mode 100755 notes_performance/create_test_repo.sh\n create mode 100755 notes_performance/test_performance.sh\n create mode 100755 notes_performance/verify_correctness.sh\n\ndiff --git a/notes_performance/config.sh b/notes_performance/config.sh\nnew file mode 100644\nindex 0000000..13abae8\n--- /dev/null\n+++ b/notes_performance/config.sh\n@@ -0,0 +1,9 @@\n+#!/bin/sh\n+\n+GIT=../../git\n+\n+num_commits=100000\n+repo_dir=test_repo\n+\n+log_length=10\n+log_reps=100\ndiff --git a/notes_performance/create_test_repo.sh b/notes_performance/create_test_repo.sh\nnew file mode 100755\nindex 0000000..fee3535\n--- /dev/null\n+++ b/notes_performance/create_test_repo.sh\n@@ -0,0 +1,90 @@\n+#!/bin/sh\n+\n+source ./config.sh\n+\n+# Create a test repo with $num_commits commits, and one note object per commit.\n+# The repo has the following refs:\n+# - refs/heads/master pointing to the last commit\n+# - refs/notes/fanout0 referencing all notes with no fanout\n+# - refs/notes/fanout1 referencing all notes with 2/38 fanout\n+# - refs/notes/fanout2 referencing all notes with 2/2/36 fanout\n+\n+if [ -d $repo_dir ]; then\n+\techo \"Skipping repo creation, $repo_dir already exists\"\n+\texit 1\n+fi\n+\n+mkdir $repo_dir &&\n+cd $repo_dir &&\n+$GIT init &&\n+nr=0 &&\n+echo \"Creating $num_commits commits...\" 1>&2 &&\n+while [ $nr -lt $num_commits ]; do\n+\tnr=$(($nr+1)) &&\n+\tcat < 1234567890 +0000\n+data <&2 &&\n+(\n+\techo \"Creating $num_commits notes...\" 1>&2 &&\n+\tnr=0 &&\n+\twhile [ $nr -lt $num_commits ]; do\n+\t\tnr=$(($nr+1)) &&\n+\t\tcat <&2 &&\n+\tfor fanout_levels in 0 1 2; do\n+\t\tnotes_ref=\"refs/notes/fanout$fanout_levels\" &&\n+\t\techo \"Creating notes tree with fanout level $fanout_levels...\" 1>&2 &&\n+\t\tcat < 1234567890 +0000\n+data <&2\n+\tdone\n+) |\n+$GIT fast-import --quiet &&\n+$GIT gc\ndiff --git a/notes_performance/test_performance.sh b/notes_performance/test_performance.sh\nnew file mode 100755\nindex 0000000..65a5dbf\n--- /dev/null\n+++ b/notes_performance/test_performance.sh\n@@ -0,0 +1,31 @@\n+#!/bin/sh\n+\n+source ./config.sh\n+\n+# Test \"git log -n $log_length\" for each of the 3 notes refs\n+# - refs/notes/fanout0\n+# - refs/notes/fanout1\n+# - refs/notes/fanout2\n+\n+if [ ! -d $repo_dir ]; then\n+\techo \"Cannot test performance, $repo_dir missing\"\n+\texit 1\n+fi\n+\n+cd $repo_dir &&\n+cat > time_notes </dev/null &&\n+\t\ti=\\$((\\$i+1))\n+\tdone\n+\n+EOF\n+\n+for fanout_levels in 0 1 2; do\n+\techo \"Timing $log_reps reps of 'git log -n $log_length refs/heads/master >/dev/null' at fanout level $fanout_levels...\" &&\n+\tnotes_ref=\"refs/notes/fanout$fanout_levels\" &&\n+\t$GIT config core.notesRef $notes_ref &&\n+\t/usr/bin/time sh time_notes &&\n+\techo\n+done\ndiff --git a/notes_performance/verify_correctness.sh b/notes_performance/verify_correctness.sh\nnew file mode 100755\nindex 0000000..ca40223\n--- /dev/null\n+++ b/notes_performance/verify_correctness.sh\n@@ -0,0 +1,32 @@\n+#!/bin/sh\n+\n+source ./config.sh\n+\n+# Verify proper contents of git log for each of the 3 notes refs\n+# - refs/notes/fanout0\n+# - refs/notes/fanout1\n+# - refs/notes/fanout2\n+\n+if [ ! -d $repo_dir ]; then\n+\techo \"Cannot verify correctness, $repo_dir missing\"\n+\texit 1\n+fi\n+\n+cd $repo_dir &&\n+for fanout_levels in 0 1 2; do\n+\techo \"Verifying correct git log at fanout level $fanout_levels\" &&\n+\tnotes_ref=\"refs/notes/fanout$fanout_levels\" &&\n+\t$GIT config core.notesRef $notes_ref &&\n+\t$GIT log | grep \"^ \" > output &&\n+\tnr=$num_commits &&\n+\twhile [ $nr -gt 0 ]; do\n+\t\techo \" commit #$nr\" &&\n+\t\techo \" note for commit #$nr\" &&\n+\t\tnr=$(($nr-1));\n+\tdone > expect &&\n+\techo \"done\" &&\n+\tdiff -u expect output || {\n+\t\techo \"Failed verification of fanout level $fanout_levels\"\n+\t\texit 1\n+\t}\n+done\n-- \n1.6.4.rc3.138.ga6b98.dirty\n\n\nHave fun!\n\n...Johan\n\n-- \nJohan Herland, \nwww.herland.net\n"},{"id":"119135","messageId":"200907300242.38844.johan@herland.net","threadId":"20269","inReplyTo":"81b0412b0907290152w27c1b5b5l9efbd6980d4f904e@mail.gmail.com","subject":"Re: [PATCHv3 1/8] Introduce commit notes","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-07-30T00:42:38Z","receivedAt":"2009-07-30T00:42:38Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Wednesday 29 July 2009, Alex Riesen wrote:\n> On Wed, Jul 29, 2009 at 04:25, Johan Herland wrote:\n> > +void get_commit_notes(const struct commit *commit, struct strbuf *sb,\n> > + const char *output_encoding)\n> > +{\n> > + static const char *utf8 = \"utf-8\";\n>\n> Using an array\n>\n> const char utf8[] = \"utf-8\";\n>\n> costs you less BSS (no separate storage for the pointer).\n\nThanks, will be fixed in the next iteration of this topic.\n\n...Johan\n\n-- \nJohan Herland, \nwww.herland.net\n"},{"id":"119136","messageId":"200907300250.03485.johan@herland.net","threadId":"20269","inReplyTo":"alpine.DEB.1.00.0907291839350.7626@intel-tinevez-2-302","subject":"Re: [PATCHv3 1/8] Introduce commit notes","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-07-30T00:50:03Z","receivedAt":"2009-07-30T00:50:03Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Wednesday 29 July 2009, Johannes Schindelin wrote:\n> On Wed, 29 Jul 2009, Alex Riesen wrote:\n> > On Wed, Jul 29, 2009 at 04:25, Johan Herland wrote:\n> > > @@ -963,5 +964,9 @@ void pretty_print_commit(enum cmit_fmt fmt, const\n> > > struct commit *commit, +\n> > > + if (fmt != CMIT_FMT_ONELINE)\n> > > + get_commit_notes(commit, sb, encoding);\n> > > +\n> >\n> > Someday we will need a way to switch off the display of notes\n> > without resolving to oneline format.\n> > Is there a notes specifier for the printf-like log message formatting\n> > (--pretty=format: or --format) planned, BTW?\n>\n> That would probably be something like \"GIT_NOTES_REF=nyanyanya git log\"?\n\nYes, that works, although I suspect some users will prefer a command-line\nargument instead.\n\nNonetheless, I think it makes sense to add a notes specifier to be used in \n--pretty/--format.\n\nI'll try to remember to look into this later, but I'll be grateful if \nsomeone gets to it before me.\n\n\n...Johan\n\n-- \nJohan Herland, \nwww.herland.net\n"},{"id":"119140","messageId":"200907300302.48337.johan@herland.net","threadId":"20269","inReplyTo":"200907290957.36000.trast@student.ethz.ch","subject":"Re: [PATCHv3 5/8] Teach \"-m \" and \"-F \" to \"git notes edit\"","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-07-30T01:02:48Z","receivedAt":"2009-07-30T01:02:48Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Wednesday 29 July 2009, Thomas Rast wrote:\n> Johan Herland wrote:\n> > diff --git a/t/t3301-notes.sh b/t/t3301-notes.sh\n>\n> [...]\n>\n> > +cat > expect-m-and-F << EOF\n> > +commit 15023535574ded8b1a89052b32673f84cf9582b8\n> > +Author: A U Thor \n> > +Date: Thu Apr 7 15:16:13 2005 -0700\n> > +\n> > + 4th\n> > +\n> > +Notes:\n> > + spam\n> > +\n> > + xyzzy\n> > +\n> > + foo\n>\n> There's significant trailing whitespace here (in the lines between\n> spam, xyzzy and foo) that initially broke the test for me because I\n> use apply.whitespace=fix. Can you guard the whitespace if it is\n> really important, with something like\n>\n> sed 's/#$//' > expect < whitespace: #\n> EOF\n\nThanks! Will be fixed in the next iteration of this topic.\n\n\n...Johan\n\n-- \nJohan Herland, \nwww.herland.net\n"},{"id":"119143","messageId":"alpine.DEB.1.00.0907300313440.8306@pacific.mpi-cbg.de","threadId":"20269","inReplyTo":"200907300250.03485.johan@herland.net","subject":"Re: [PATCHv3 1/8] Introduce commit notes","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-07-30T01:14:56Z","receivedAt":"2009-07-30T01:14:56Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Thu, 30 Jul 2009, Johan Herland wrote:\n\n> On Wednesday 29 July 2009, Johannes Schindelin wrote:\n> > On Wed, 29 Jul 2009, Alex Riesen wrote:\n> > > On Wed, Jul 29, 2009 at 04:25, Johan Herland wrote:\n> > > > @@ -963,5 +964,9 @@ void pretty_print_commit(enum cmit_fmt fmt, const\n> > > > struct commit *commit, +\n> > > > + if (fmt != CMIT_FMT_ONELINE)\n> > > > + get_commit_notes(commit, sb, encoding);\n> > > > +\n> > >\n> > > Someday we will need a way to switch off the display of notes\n> > > without resolving to oneline format.\n> > > Is there a notes specifier for the printf-like log message formatting\n> > > (--pretty=format: or --format) planned, BTW?\n> >\n> > That would probably be something like \"GIT_NOTES_REF=nyanyanya git log\"?\n> \n> Yes, that works, although I suspect some users will prefer a command-line\n> argument instead.\n> \n> Nonetheless, I think it makes sense to add a notes specifier to be used in \n> --pretty/--format.\n> \n> I'll try to remember to look into this later, but I'll be grateful if \n> someone gets to it before me.\n\nProbably you will not want to show the \"\\nNotes:\" prefix, and also not \nindent the string, but that is something you could make conditional upon a \nflag to get_commit_notes(). But this should get you started:\n\n-- snipsnap --\ndiff --git a/Documentation/pretty-formats.txt b/Documentation/pretty-formats.txt\nindex 2a845b1..5fb10b3 100644\n--- a/Documentation/pretty-formats.txt\n+++ b/Documentation/pretty-formats.txt\n@@ -123,6 +123,7 @@ The placeholders are:\n - '%s': subject\n - '%f': sanitized subject line, suitable for a filename\n - '%b': body\n+- '%N': commit notes\n - '%Cred': switch color to red\n - '%Cgreen': switch color to green\n - '%Cblue': switch color to blue\ndiff --git a/pretty.c b/pretty.c\nindex fee6789..7349697 100644\n--- a/pretty.c\n+++ b/pretty.c\n@@ -690,6 +690,10 @@ static size_t format_commit_item(struct strbuf *sb, const char *placeholder,\n \tcase 'd':\n \t\tformat_decoration(sb, commit);\n \t\treturn 1;\n+\tcase 'N':\n+\t\tget_commit_notes(commit, sb, git_log_output_encoding ?\n+\t\t\t\tgit_log_output_encoding : git_commit_encoding);\n+\t\treturn 1;\n \t}\n \n \t/* For the rest we have to parse the commit header. */\n"},{"id":"119144","messageId":"200907300329.48585.johan@herland.net","threadId":"20269","inReplyTo":"20090729142121.GB1033@spearce.org","subject":"Re: [PATCHv3 7/8] fast-import: Add support for importing commit notes","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-07-30T01:29:48Z","receivedAt":"2009-07-30T01:29:48Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Wednesday 29 July 2009, Shawn O. Pearce wrote:\n> Johan Herland wrote:\n> > +static void note_change_n(struct branch *b)\n> > +{\n>\n> ...\n>\n> > +\ttree_content_set(&b->branch_tree, sha1_to_hex(commit_sha1), sha1,\n> > +\t\tS_IFREG | 0644, NULL);\n>\n> I thought you wanted to use the note code to handle the name\n> formatting here?\n\nYes, I do, as soon as the notes code knows how to format/write note names \n(which I plan to tackle after nailing the _reading_ part of the code).\n\n\nHave fun! :)\n\n...Johan\n\n-- \nJohan Herland, \nwww.herland.net\n"},{"id":"119313","messageId":"200908010436.57480.johan@herland.net","threadId":"20269","inReplyTo":"200907300218.40203.johan@herland.net","subject":"[RFC] First draft of 256-tree structure for storing notes","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-08-01T02:36:57Z","receivedAt":"2009-08-01T02:36:57Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"This patch stores note entries and unexpanded fanout subtree entries in a\ncustomized 256-tree structure.\n\nInitial performance numbers are encouraging:\n\n$ ./test_performance.sh\nTiming 100 reps of 'git log -n 10 refs/heads/master >/dev/null' at fanout level 0...\n14.92user 4.84system 0:20.39elapsed 96%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+2164780minor)pagefaults 0swaps\n\nTiming 100 reps of 'git log -n 10 refs/heads/master >/dev/null' at fanout level 1...\n0.71user 0.32system 0:01.06elapsed 97%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+154090minor)pagefaults 0swaps\n\nTiming 100 reps of 'git log -n 10 refs/heads/master >/dev/null' at fanout level 2...\n0.44user 0.18system 0:00.63elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+94183minor)pagefaults 0swaps\n\nThis is pretty much twice as fast as the existing version (which uses a hash map\nfor notes, and a linked list for unexpanded fanout subtrees).\n\nSigned-off-by: Johan Herland \n---\n\nHi,\n\nJust a quick update before I leave for a week of vacation (with spotty\nInternet access, at best).\n\nI've been thinking about various data structures for the notes code for\nthe last couple of days, and here is a quick first draft of the idea that\nI found most promising: Storing both notes and unexpanded subtrees as leaf\nnodes in a customized 256-tree structure. The initial performance numbers\nlook very promising (~twice as fast as the previous implementation at\nfanout levels 0 and 1), and there are still probably several optimization\nthat can be done (an obvious example is reducing malloc pressure by\nmemory pooling leaf_node objects).\n\nAFAICS, this implementation is semantically equivalent the previous code\n(longer prefixes are preferred, no merging of notes, multiple/nested\nfanout levels are allowed, etc.).\n\n\nHave fun! :)\n\n...Johan\n\n\n notes.c | 325 ++++++++++++++++++++++++++++++++++-----------------------------\n 1 files changed, 174 insertions(+), 151 deletions(-)\n\ndiff --git a/notes.c b/notes.c\nindex 7e9dc49..9282b16 100644\n--- a/notes.c\n+++ b/notes.c\n@@ -6,79 +6,165 @@\n #include \"strbuf.h\"\n #include \"tree-walk.h\"\n \n-struct entry {\n-\tunsigned char commit_sha1[20];\n-\tunsigned char notes_sha1[20];\n+/*\n+ * Use a non-balancing simple 256-tree structure with struct int_node as\n+ * internal nodes, and struct leaf_node as leaf nodes. Each int_node has a\n+ * 256-array of pointers to its children\n+ * The bottom 2 bits of each pointer is used to identify the pointer type\n+ * - ptr & 3 == 0 - NULL pointer, assert(ptr == NULL)\n+ * - ptr & 3 == 1 - pointer to next internal node - cast to struct int_node *\n+ * - ptr & 3 == 2 - pointer to note entry - cast to struct leaf_node *\n+ * - ptr & 3 == 3 - pointer to subtree entry - cast to struct leaf_node *\n+ *\n+ * The root node is always an inline struct int_node.\n+ * An array_entry always starts out with all pointers set to NULL.\n+ *\n+ * To add a leaf_node:\n+ * 1. Start at the root node, with n = 0\n+ * 2. Use the nth byte of the key as an index into a:\n+ * - If NULL, store the tweaked pointer directly into a[n]\n+ * - If an int_node, recurse into that node and increment n\n+ * - If a leaf_node:\n+ * 1. Check if they're equal, and handle that (abort? overwrite?)\n+ * 2. Create a new int_node, and store both leaf_nodes there\n+ * 3. Store the new int_node into a[n].\n+ *\n+ * To find a leaf_node:\n+ * 1. Start at the root node, with n = 0\n+ * 2. Use the nth byte of the key as an index into a:\n+ * - If an int_node, recurse into that node and increment n\n+ * - If a leaf_node with matching key, return leaf_node (assert note entry)\n+ * - If a matching subtree entry, unpack that subtree entry (and remove it);\n+ * restart search at the current level.\n+ * - Otherwise, we end up at a NULL pointer, or a non-matching leaf_node.\n+ * Backtrack out of the recursion, one level at a time and check a[0]:\n+ * - If a[0] at the current level is a matching subtree entry, unpack that\n+ * subtree entry (and remove it); restart search at the current level.\n+ */\n+struct int_node {\n+\tvoid *a[256];\n };\n \n-struct hash_map {\n-\tstruct entry *entries;\n-\toff_t count, size;\n+/*\n+ * Leaf nodes come in two variants, note entries and subtree entries,\n+ * distinguished by the LSb of the leaf node pointer (see above).\n+ * As a note entry, the key is the SHA1 of the referenced commit, and the value\n+ * is the SHA1 of the note object.\n+ * As a subtree entry, the key is the prefix SHA1 (w/trailing NULs) of the\n+ * referenced commit, including the prefix length in the last byte of the key.\n+ * The value is the SHA1 of the tree object containing the notes subtree.\n+ */\n+struct leaf_node {\n+\tunsigned char key_sha1[20];\n+\tunsigned char val_sha1[20];\n };\n \n-struct subtree_entry {\n-\t/*\n-\t * SHA1 prefix is stored in the first 19 bytes (w/trailing NUL bytes);\n-\t * length of SHA1 prefix is stored in the last byte\n-\t */\n-\tunsigned char sha1_prefix_w_len[20];\n-\tunsigned char subtree_sha1[20];\n-\tstruct subtree_entry *next;\n-};\n+#define PTR_TYPE_NULL 0\n+#define PTR_TYPE_INTERNAL 1\n+#define PTR_TYPE_NOTE 2\n+#define PTR_TYPE_SUBTREE 3\n \n-static int initialized;\n-static struct hash_map hash_map;\n-static struct subtree_entry *subtree_list;\n+#define GET_PTR_TYPE(ptr) ((uintptr_t) (ptr) & 3)\n+#define CLR_PTR_TYPE(ptr) ((void *) ((uintptr_t) (ptr) & ~3))\n+#define SET_PTR_TYPE(ptr, type) ((void *) ((uintptr_t) (ptr) | (type)))\n \n-static int hash_index(struct hash_map *map, const unsigned char *sha1)\n-{\n-\tint i = ((*(unsigned int *)sha1) % map->size);\n+#define MATCHING_SUBTREE(key_sha1, subtree_sha1) \\\n+\t(!memcmp(key_sha1, subtree_sha1, subtree_sha1[19]))\n \n-\tfor (;;) {\n-\t\tunsigned char *current = map->entries[i].commit_sha1;\n+static struct int_node root_node;\n \n-\t\tif (!hashcmp(sha1, current))\n-\t\t\treturn i;\n+static int initialized;\n \n-\t\tif (is_null_sha1(current))\n-\t\t\treturn -1 - i;\n \n-\t\tif (++i == map->size)\n-\t\t\ti = 0;\n-\t}\n-}\n+static void load_subtree(struct leaf_node *subtree, struct int_node *node,\n+\t\tunsigned int n);\n \n-static void add_entry(const unsigned char *commit_sha1,\n-\t\tconst unsigned char *notes_sha1)\n+static struct leaf_node *note_tree_find(struct int_node *tree, unsigned char n,\n+\t\tconst unsigned char *key_sha1)\n {\n-\tint index;\n-\n-\tif (hash_map.count + 1 > hash_map.size >> 1) {\n-\t\tint i, old_size = hash_map.size;\n-\t\tstruct entry *old = hash_map.entries;\n-\n-\t\thash_map.size = old_size ? old_size << 1 : 64;\n-\t\thash_map.entries = (struct entry *)\n-\t\t\txcalloc(sizeof(struct entry), hash_map.size);\n-\n-\t\tfor (i = 0; i < old_size; i++)\n-\t\t\tif (!is_null_sha1(old[i].commit_sha1)) {\n-\t\t\t\tindex = -1 - hash_index(&hash_map,\n-\t\t\t\t\t\told[i].commit_sha1);\n-\t\t\t\tmemcpy(hash_map.entries + index, old + i,\n-\t\t\t\t\tsizeof(struct entry));\n-\t\t\t}\n-\t\tfree(old);\n+\tstruct leaf_node *l;\n+\tunsigned char i = key_sha1[n];\n+\tvoid *p = tree->a[i];\n+\n+\tswitch(GET_PTR_TYPE(p)) {\n+\tcase PTR_TYPE_INTERNAL:\n+\t\tl = note_tree_find(CLR_PTR_TYPE(p), n + 1, key_sha1);\n+\t\tif (l)\n+\t\t\treturn l;\n+\t\tbreak;\n+\tcase PTR_TYPE_NOTE:\n+\t\tl = (struct leaf_node *) CLR_PTR_TYPE(p);\n+\t\tif (!hashcmp(key_sha1, l->key_sha1))\n+\t\t\treturn l; /* return note object matching given key */\n+\t\tbreak;\n+\tcase PTR_TYPE_SUBTREE:\n+\t\tl = (struct leaf_node *) CLR_PTR_TYPE(p);\n+\t\tif (MATCHING_SUBTREE(key_sha1, l->key_sha1)) {\n+\t\t\t/* unpack tree and resume search */\n+\t\t\ttree->a[i] = NULL;\n+\t\t\tload_subtree(l, tree, n);\n+\t\t\tfree(l);\n+\t\t\treturn note_tree_find(tree, n, key_sha1);\n+\t\t}\n+\t\tbreak;\n+\tcase PTR_TYPE_NULL:\n+\tdefault:\n+\t\tassert(!p);\n+\t\tbreak;\n \t}\n \n-\tindex = hash_index(&hash_map, commit_sha1);\n-\tif (index < 0) {\n-\t\tindex = -1 - index;\n-\t\thash_map.count++;\n+\t/*\n+\t * Did not find key at this (or any lower) level.\n+\t * Check if there's a matching subtree entry in tree->a[0].\n+\t * If so, unpack tree and resume search.\n+\t */\n+\tp = tree->a[0];\n+\tif (GET_PTR_TYPE(p) != PTR_TYPE_SUBTREE)\n+\t\treturn NULL;\n+\tl = (struct leaf_node *) CLR_PTR_TYPE(p);\n+\tif (MATCHING_SUBTREE(key_sha1, l->key_sha1)) {\n+\t\t/* unpack tree and resume search */\n+\t\ttree->a[0] = NULL;\n+\t\tload_subtree(l, tree, n);\n+\t\tfree(l);\n+\t\treturn note_tree_find(tree, n, key_sha1);\n \t}\n+\treturn NULL;\n+}\n \n-\thashcpy(hash_map.entries[index].commit_sha1, commit_sha1);\n-\thashcpy(hash_map.entries[index].notes_sha1, notes_sha1);\n+static int note_tree_insert(struct int_node *tree, unsigned char n,\n+\t\tconst struct leaf_node *entry, unsigned char type)\n+{\n+\tstruct int_node *new_node;\n+\tconst struct leaf_node *l;\n+\tint ret;\n+\tunsigned char i = entry->key_sha1[n];\n+\tvoid *p = tree->a[i];\n+\tassert(GET_PTR_TYPE(entry) == PTR_TYPE_NULL);\n+\tswitch(GET_PTR_TYPE(p)) {\n+\tcase PTR_TYPE_NULL:\n+\t\tassert(!p);\n+\t\ttree->a[i] = SET_PTR_TYPE(entry, type);\n+\t\treturn 0;\n+\tcase PTR_TYPE_INTERNAL:\n+\t\treturn note_tree_insert(CLR_PTR_TYPE(p), n + 1, entry, type);\n+\tdefault:\n+\t\tassert(GET_PTR_TYPE(p) == PTR_TYPE_NOTE ||\n+\t\t\tGET_PTR_TYPE(p) == PTR_TYPE_SUBTREE);\n+\t\tl = (const struct leaf_node *) CLR_PTR_TYPE(p);\n+\t\tif (!hashcmp(entry->key_sha1, l->key_sha1))\n+\t\t\treturn -1; /* abort insert on matching key */\n+\t\tnew_node = (struct int_node *)\n+\t\t\txcalloc(sizeof(struct int_node), 1);\n+\t\tret = note_tree_insert(new_node, n + 1,\n+\t\t\tCLR_PTR_TYPE(p), GET_PTR_TYPE(p));\n+\t\tif (ret) {\n+\t\t\tfree(new_node);\n+\t\t\treturn -1;\n+\t\t}\n+\t\ttree->a[i] = SET_PTR_TYPE(new_node, PTR_TYPE_INTERNAL);\n+\t\treturn note_tree_insert(new_node, n + 1, entry, type);\n+\t}\n }\n \n /*\n@@ -110,22 +196,23 @@ static int get_sha1_hex_segment(const char *hex, unsigned int hex_len,\n \treturn len;\n }\n \n-static void load_subtree(struct subtree_entry *se)\n+static void load_subtree(struct leaf_node *subtree, struct int_node *node,\n+\t\tunsigned int n)\n {\n \tunsigned char commit_sha1[20];\n \tunsigned int prefix_len;\n \tvoid *buf;\n \tstruct tree_desc desc;\n \tstruct name_entry entry;\n-\tstruct subtree_entry *tmp_list = NULL, *tmp_last = NULL;\n \n-\tbuf = fill_tree_descriptor(&desc, se->subtree_sha1);\n+\tbuf = fill_tree_descriptor(&desc, subtree->val_sha1);\n \tif (!buf)\n \t\tdie(\"Could not read %s for notes-index\",\n-\t\t sha1_to_hex(se->subtree_sha1));\n+\t\t sha1_to_hex(subtree->val_sha1));\n \n-\tprefix_len = se->sha1_prefix_w_len[19];\n-\tmemcpy(commit_sha1, se->sha1_prefix_w_len, prefix_len);\n+\tprefix_len = subtree->key_sha1[19];\n+\tassert(prefix_len >= n);\n+\tmemcpy(commit_sha1, subtree->key_sha1, prefix_len);\n \twhile (tree_entry(&desc, &entry)) {\n \t\tint len = get_sha1_hex_segment(entry.path, strlen(entry.path),\n \t\t\t\tcommit_sha1 + prefix_len, 20 - prefix_len);\n@@ -133,111 +220,47 @@ static void load_subtree(struct subtree_entry *se)\n \t\t\tcontinue; /* entry.path is not a SHA1 sum. Skip */\n \t\tlen += prefix_len;\n \n-\t\t/* If commit SHA1 is complete, assume note object */\n-\t\tif (len == 20)\n-\t\t\tadd_entry(commit_sha1, entry.sha1);\n-\t\t/* If commit SHA1 is incomplete, assume note subtree */\n-\t\telse if (len < 20 && entry.mode == S_IFDIR) {\n-\t\t\tstruct subtree_entry *n = (struct subtree_entry *)\n-\t\t\t\txcalloc(sizeof(struct subtree_entry), 1);\n-\t\t\thashcpy(n->sha1_prefix_w_len, commit_sha1);\n-\t\t\tn->sha1_prefix_w_len[19] = (unsigned char) len;\n-\t\t\thashcpy(n->subtree_sha1, entry.sha1);\n-\n-\t\t\tif (!tmp_list) {\n-\t\t\t\ttmp_list = n;\n-\t\t\t\ttmp_last = n;\n-\t\t\t}\n-\t\t\telse {\n-\t\t\t\tassert(!tmp_last->next);\n-\t\t\t\tassert(hashcmp(n->sha1_prefix_w_len,\n-\t\t\t\t\ttmp_last->sha1_prefix_w_len) > 0);\n-\t\t\t\ttmp_last->next = n;\n-\t\t\t\ttmp_last = n;\n+\t\t/*\n+\t\t * If commit SHA1 is complete (len == 20), assume note object\n+\t\t * If commit SHA1 is incomplete (len < 20), assume note subtree\n+\t\t */\n+\t\tif (len <= 20) {\n+\t\t\tunsigned char type = PTR_TYPE_NOTE;\n+\t\t\tstruct leaf_node *l = (struct leaf_node *)\n+\t\t\t\txcalloc(sizeof(struct leaf_node), 1);\n+\t\t\thashcpy(l->key_sha1, commit_sha1);\n+\t\t\thashcpy(l->val_sha1, entry.sha1);\n+\t\t\tif (len < 20) {\n+\t\t\t\tl->key_sha1[19] = (unsigned char) len;\n+\t\t\t\ttype = PTR_TYPE_SUBTREE;\n \t\t\t}\n+\t\t\tassert(!note_tree_insert(node, n, l, type));\n \t\t}\n \t}\n \tfree(buf);\n-\tif (tmp_list) {\n-\t\t/* insert tmp_list immediately after se */\n-\t\tassert(hashcmp(tmp_list->sha1_prefix_w_len,\n-\t\t\t\tse->sha1_prefix_w_len) > 0);\n-\t\tif (se->next) {\n-\t\t\tassert(hashcmp(se->next->sha1_prefix_w_len,\n-\t\t\t\t\ttmp_last->sha1_prefix_w_len) > 0);\n-\t\t\ttmp_last->next = se->next;\n-\t\t}\n-\t\tse->next = tmp_list;\n-\t}\n }\n \n-static void initialize_hash_map(const char *notes_ref_name)\n+static void initialize_notes(const char *notes_ref_name)\n {\n \tunsigned char sha1[20], commit_sha1[20];\n \tunsigned mode;\n-\tstruct subtree_entry root_tree;\n+\tstruct leaf_node root_tree;\n \n \tif (!notes_ref_name || read_ref(notes_ref_name, commit_sha1) ||\n \t get_tree_entry(commit_sha1, \"\", sha1, &mode))\n \t\treturn;\n \n-\thashclr(root_tree.sha1_prefix_w_len);\n-\thashcpy(root_tree.subtree_sha1, sha1);\n-\troot_tree.next = NULL;\n-\tload_subtree(&root_tree);\n-\tsubtree_list = root_tree.next;\n-}\n-\n-/*\n- * Compare the given commit SHA1 against the given subtree entry.\n- * Return -1 if the commit SHA1 cannot exist within the given subtree, or any\n- * subtree following it.\n- * Return 0 if the commit SHA1 _may_ exist within the given subtree.\n- * Return 1 if the commit SHA1 cannot exist within the given subtree, but may\n- * exist within a subtree following it.\n- */\n-static int commit_subtree_cmp(const unsigned char *commit_sha1,\n-\t\tconst struct subtree_entry *entry)\n-{\n-\tunsigned int prefix_len = entry->sha1_prefix_w_len[19];\n-\treturn memcmp(commit_sha1, entry->sha1_prefix_w_len, prefix_len);\n-}\n-\n-static struct subtree_entry *lookup_subtree(const unsigned char *commit_sha1)\n-{\n-\tstruct subtree_entry *found = NULL, *cur = subtree_list;\n-\twhile (cur) {\n-\t\tint cmp = commit_subtree_cmp(commit_sha1, cur);\n-\t\tif (!cmp)\n-\t\t\tfound = cur;\n-\t\tif (cmp < 0)\n-\t\t\tbreak;\n-\t\tcur = cur->next;\n-\t}\n-\treturn found;\n+\thashclr(root_tree.key_sha1);\n+\thashcpy(root_tree.val_sha1, sha1);\n+\tload_subtree(&root_tree, &root_node, 0);\n }\n \n static unsigned char *lookup_notes(const unsigned char *commit_sha1)\n {\n-\tint index;\n-\tstruct subtree_entry *subtree;\n-\n-\t/* First, try to find the commit SHA1 directly in hash map */\n-\tindex = hash_map.size ? hash_index(&hash_map, commit_sha1) : -1;\n-\tif (index >= 0)\n-\t\treturn hash_map.entries[index].notes_sha1;\n-\n-\t/* Next, try finding a subtree that may contain the commit SHA1 */\n-\tsubtree = lookup_subtree(commit_sha1);\n-\n-\t/* Give up if no subtree found, or if subtree is already loaded */\n-\tif (!subtree || is_null_sha1(subtree->subtree_sha1))\n-\t\treturn NULL;\n-\n-\t/* Load subtree into hash_map, and retry lookup recursively */\n-\tload_subtree(subtree);\n-\thashclr(subtree->subtree_sha1);\n-\treturn lookup_notes(commit_sha1);\n+\tstruct leaf_node *found = note_tree_find(&root_node, 0, commit_sha1);\n+\tif (found)\n+\t\treturn found->val_sha1;\n+\treturn NULL;\n }\n \n void get_commit_notes(const struct commit *commit, struct strbuf *sb,\n@@ -255,7 +278,7 @@ void get_commit_notes(const struct commit *commit, struct strbuf *sb,\n \t\t\tnotes_ref_name = getenv(GIT_NOTES_REF_ENVIRONMENT);\n \t\telse if (!notes_ref_name)\n \t\t\tnotes_ref_name = GIT_NOTES_DEFAULT_REF;\n-\t\tinitialize_hash_map(notes_ref_name);\n+\t\tinitialize_notes(notes_ref_name);\n \t\tinitialized = 1;\n \t}\n \n-- \n1.6.4.rc3.138.ga6b98.dirty\n\n-- \nJohan Herland, \nwww.herland.net\n"},{"id":"120473","messageId":"200908130500.51135.johan@herland.net","threadId":"20269","inReplyTo":"200908010436.57480.johan@herland.net","subject":"[RFC] Store subtree entries in the same hash map as the note entries","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-08-13T03:00:50Z","receivedAt":"2009-08-13T03:00:50Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"This is a first draft at implementing Dscho's idea of improving note parser\nperformance by storing the subtree entries in the same hash map as the note\nentries.\n\nIn order to tell subtree entries and note entries apart, another member has\nbeen added to struct entry: unsigned char commit_sha1_len. This member\nstores the number of \"valid\" bytes in the commit_sha1 member, meaning that\na value of 1-19 indicates a subtree entry, and a value of 20 indicates a\nnote entry. There are two more special values for this new member as well:\n\n- Since a null SHA1 is also a valid subtree entry (e.g. the \"00/*\" subtree\n in a 2/38 fanout scheme), we can no longer use is_null_sha1() to identify\n unused entries in the hash map. Instead, a value of 0 in the new\n commit_sha1_len member indicates that this is entry is null/unused.\n\n There is one exception to this rule: the root notes tree which is just a\n special case of a subtree entry with 0 \"valid\" bytes in the commit_sha1\n member. However, this exception is acceptable, as the root entry is never\n stored in the hash map (the hash map is initialized by unpacking this\n root tree entry).\n\n- The second special commit_sha1_len value is 255, and is used to indicate\n a subtree entry that has already been unpacked, and should therefore be\n removed from the hash map. It is expensive and non-trivial to _delete_\n an entry in the hash map, and we therefore use this special value to\n _ignore_ the entry. If/when the hash map is grown/reallocated, we simply\n avoid bringing the unpacked subtree entries into the new hash map.\n\n$ ./test_performance.sh\nTiming 100 reps of 'git log -n 10 refs/heads/master >/dev/null' at fanout level 0...\n21.80user 2.15system 0:24.12elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+1051886minor)pagefaults 0swaps\n\nTiming 100 reps of 'git log -n 10 refs/heads/master >/dev/null' at fanout level 1...\n1.24user 0.24system 0:01.49elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+120478minor)pagefaults 0swaps\n\nTiming 100 reps of 'git log -n 10 refs/heads/master >/dev/null' at fanout level 2...\n0.73user 0.20system 0:00.95elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+105782minor)pagefaults 0swaps\n\nSigned-off-by: Johan Herland \n---\n\nOn Wednesday 29 July 2009, Johannes Schindelin wrote:\n> I know you want to have something working first and optimize then, but I\n> imagined that the hashmap can actually contain the entries of the partial\n> hashes, too. You'll need to extend the data type, of course, to be able\n> to say just how many digits of the SHA-1 are valid, and I guess for\n> consistency you'll need to pad with 0s.\n\nOk. Here's a draft implementation of your proposal to store the subtree\nentries in the same hash map as the note entries.\n\nThis code is somewhat faster than my first subtree-in-linked-list draft,\nbut considerably slower than my 256-tree proposal:\n\n fanout level 0 fanout level 1 fanout level 2\n subtree-in-ll 32.71s 1.88s 0.65s\n all-in-hash-map 24.12s 1.49s 0.95s\n all-in-256-tree 20.39s 1.06s 0.63s\n\nI'm not sure how closely my implementation follows your vision, so please\nsuggest improvements, fixes, etc.\n\n\nHave fun! :)\n\n...Johan\n\n\n notes.c | 155 +++++++++++++++++++++++++--------------------------------------\n 1 files changed, 62 insertions(+), 93 deletions(-)\n\ndiff --git a/notes.c b/notes.c\nindex 7e9dc49..34b8892 100644\n--- a/notes.c\n+++ b/notes.c\n@@ -9,6 +9,15 @@\n struct entry {\n \tunsigned char commit_sha1[20];\n \tunsigned char notes_sha1[20];\n+\t/*\n+\t * The following member can have the following values:\n+\t * 0 - This is a NULL/blank entry in the hash_map\n+\t * (Exception: The root_tree entry in initialize_hash_map())\n+\t * 1-19 - This is a subtree with the given number of valid prefix bytes\n+\t * 20 - This is a note\n+\t * 255 - This is a subtree which has been unpacked, please ignore\n+\t */\n+\tunsigned char commit_sha1_len;\n };\n \n struct hash_map {\n@@ -16,43 +25,35 @@ struct hash_map {\n \toff_t count, size;\n };\n \n-struct subtree_entry {\n-\t/*\n-\t * SHA1 prefix is stored in the first 19 bytes (w/trailing NUL bytes);\n-\t * length of SHA1 prefix is stored in the last byte\n-\t */\n-\tunsigned char sha1_prefix_w_len[20];\n-\tunsigned char subtree_sha1[20];\n-\tstruct subtree_entry *next;\n-};\n-\n static int initialized;\n static struct hash_map hash_map;\n-static struct subtree_entry *subtree_list;\n \n static int hash_index(struct hash_map *map, const unsigned char *sha1)\n {\n \tint i = ((*(unsigned int *)sha1) % map->size);\n \n \tfor (;;) {\n-\t\tunsigned char *current = map->entries[i].commit_sha1;\n+\t\tstruct entry *current = &(map->entries[i]);\n \n-\t\tif (!hashcmp(sha1, current))\n-\t\t\treturn i;\n-\n-\t\tif (is_null_sha1(current))\n+\t\tif (!current->commit_sha1_len)\n \t\t\treturn -1 - i;\n \n+\t\tif (!hashcmp(sha1, current->commit_sha1)\n+\t\t && current->commit_sha1_len <= 20)\n+\t\t\treturn i;\n+\n \t\tif (++i == map->size)\n \t\t\ti = 0;\n \t}\n }\n \n static void add_entry(const unsigned char *commit_sha1,\n-\t\tconst unsigned char *notes_sha1)\n+\t\tconst unsigned char *notes_sha1,\n+\t\tunsigned char commit_sha1_len)\n {\n \tint index;\n \n+\tassert(commit_sha1_len > 0 && commit_sha1_len <= 20);\n \tif (hash_map.count + 1 > hash_map.size >> 1) {\n \t\tint i, old_size = hash_map.size;\n \t\tstruct entry *old = hash_map.entries;\n@@ -61,13 +62,20 @@ static void add_entry(const unsigned char *commit_sha1,\n \t\thash_map.entries = (struct entry *)\n \t\t\txcalloc(sizeof(struct entry), hash_map.size);\n \n-\t\tfor (i = 0; i < old_size; i++)\n-\t\t\tif (!is_null_sha1(old[i].commit_sha1)) {\n+\t\tfor (i = 0; i < old_size; i++) {\n+\t\t\tswitch (old[i].commit_sha1_len) {\n+\t\t\tcase 255:\n+\t\t\t\thash_map.count--;\n+\t\t\t\t/* fall through */\n+\t\t\tcase 0:\n+\t\t\t\tcontinue;\n+\t\t\tdefault:\n \t\t\t\tindex = -1 - hash_index(&hash_map,\n \t\t\t\t\t\told[i].commit_sha1);\n \t\t\t\tmemcpy(hash_map.entries + index, old + i,\n \t\t\t\t\tsizeof(struct entry));\n \t\t\t}\n+\t\t}\n \t\tfree(old);\n \t}\n \n@@ -79,6 +87,7 @@ static void add_entry(const unsigned char *commit_sha1,\n \n \thashcpy(hash_map.entries[index].commit_sha1, commit_sha1);\n \thashcpy(hash_map.entries[index].notes_sha1, notes_sha1);\n+\thash_map.entries[index].commit_sha1_len = commit_sha1_len;\n }\n \n /*\n@@ -110,22 +119,26 @@ static int get_sha1_hex_segment(const char *hex, unsigned int hex_len,\n \treturn len;\n }\n \n-static void load_subtree(struct subtree_entry *se)\n+static void load_subtree(struct entry *subtree)\n {\n \tunsigned char commit_sha1[20];\n \tunsigned int prefix_len;\n \tvoid *buf;\n \tstruct tree_desc desc;\n \tstruct name_entry entry;\n-\tstruct subtree_entry *tmp_list = NULL, *tmp_last = NULL;\n \n-\tbuf = fill_tree_descriptor(&desc, se->subtree_sha1);\n+\tbuf = fill_tree_descriptor(&desc, subtree->notes_sha1);\n \tif (!buf)\n \t\tdie(\"Could not read %s for notes-index\",\n-\t\t sha1_to_hex(se->subtree_sha1));\n+\t\t sha1_to_hex(subtree->notes_sha1));\n+\n+\tprefix_len = subtree->commit_sha1_len;\n+\tassert(prefix_len < 20);\n+\tmemcpy(commit_sha1, subtree->commit_sha1, prefix_len);\n+\n+\t/* Invalidate this subtree from further consideration */\n+\tsubtree->commit_sha1_len = 255;\n \n-\tprefix_len = se->sha1_prefix_w_len[19];\n-\tmemcpy(commit_sha1, se->sha1_prefix_w_len, prefix_len);\n \twhile (tree_entry(&desc, &entry)) {\n \t\tint len = get_sha1_hex_segment(entry.path, strlen(entry.path),\n \t\t\t\tcommit_sha1 + prefix_len, 20 - prefix_len);\n@@ -133,110 +146,66 @@ static void load_subtree(struct subtree_entry *se)\n \t\t\tcontinue; /* entry.path is not a SHA1 sum. Skip */\n \t\tlen += prefix_len;\n \n-\t\t/* If commit SHA1 is complete, assume note object */\n-\t\tif (len == 20)\n-\t\t\tadd_entry(commit_sha1, entry.sha1);\n-\t\t/* If commit SHA1 is incomplete, assume note subtree */\n-\t\telse if (len < 20 && entry.mode == S_IFDIR) {\n-\t\t\tstruct subtree_entry *n = (struct subtree_entry *)\n-\t\t\t\txcalloc(sizeof(struct subtree_entry), 1);\n-\t\t\thashcpy(n->sha1_prefix_w_len, commit_sha1);\n-\t\t\tn->sha1_prefix_w_len[19] = (unsigned char) len;\n-\t\t\thashcpy(n->subtree_sha1, entry.sha1);\n-\n-\t\t\tif (!tmp_list) {\n-\t\t\t\ttmp_list = n;\n-\t\t\t\ttmp_last = n;\n-\t\t\t}\n-\t\t\telse {\n-\t\t\t\tassert(!tmp_last->next);\n-\t\t\t\tassert(hashcmp(n->sha1_prefix_w_len,\n-\t\t\t\t\ttmp_last->sha1_prefix_w_len) > 0);\n-\t\t\t\ttmp_last->next = n;\n-\t\t\t\ttmp_last = n;\n-\t\t\t}\n-\t\t}\n+\t\tif (len == 20 || (len < 20 && entry.mode == S_IFDIR))\n+\t\t\tadd_entry(commit_sha1, entry.sha1, len);\n \t}\n \tfree(buf);\n-\tif (tmp_list) {\n-\t\t/* insert tmp_list immediately after se */\n-\t\tassert(hashcmp(tmp_list->sha1_prefix_w_len,\n-\t\t\t\tse->sha1_prefix_w_len) > 0);\n-\t\tif (se->next) {\n-\t\t\tassert(hashcmp(se->next->sha1_prefix_w_len,\n-\t\t\t\t\ttmp_last->sha1_prefix_w_len) > 0);\n-\t\t\ttmp_last->next = se->next;\n-\t\t}\n-\t\tse->next = tmp_list;\n-\t}\n }\n \n static void initialize_hash_map(const char *notes_ref_name)\n {\n \tunsigned char sha1[20], commit_sha1[20];\n \tunsigned mode;\n-\tstruct subtree_entry root_tree;\n+\tstruct entry root_tree;\n \n \tif (!notes_ref_name || read_ref(notes_ref_name, commit_sha1) ||\n \t get_tree_entry(commit_sha1, \"\", sha1, &mode))\n \t\treturn;\n \n-\thashclr(root_tree.sha1_prefix_w_len);\n-\thashcpy(root_tree.subtree_sha1, sha1);\n-\troot_tree.next = NULL;\n+\thashclr(root_tree.commit_sha1);\n+\thashcpy(root_tree.notes_sha1, sha1);\n+\troot_tree.commit_sha1_len = 0;\n \tload_subtree(&root_tree);\n-\tsubtree_list = root_tree.next;\n }\n \n-/*\n- * Compare the given commit SHA1 against the given subtree entry.\n- * Return -1 if the commit SHA1 cannot exist within the given subtree, or any\n- * subtree following it.\n- * Return 0 if the commit SHA1 _may_ exist within the given subtree.\n- * Return 1 if the commit SHA1 cannot exist within the given subtree, but may\n- * exist within a subtree following it.\n- */\n-static int commit_subtree_cmp(const unsigned char *commit_sha1,\n-\t\tconst struct subtree_entry *entry)\n+static struct entry *lookup_subtree(const unsigned char *commit_sha1)\n {\n-\tunsigned int prefix_len = entry->sha1_prefix_w_len[19];\n-\treturn memcmp(commit_sha1, entry->sha1_prefix_w_len, prefix_len);\n-}\n+\tunsigned char prefix_sha1[20];\n+\tunsigned char i;\n+\tint index;\n \n-static struct subtree_entry *lookup_subtree(const unsigned char *commit_sha1)\n-{\n-\tstruct subtree_entry *found = NULL, *cur = subtree_list;\n-\twhile (cur) {\n-\t\tint cmp = commit_subtree_cmp(commit_sha1, cur);\n-\t\tif (!cmp)\n-\t\t\tfound = cur;\n-\t\tif (cmp < 0)\n-\t\t\tbreak;\n-\t\tcur = cur->next;\n+\thashcpy(prefix_sha1, commit_sha1);\n+\tfor (i = 19; i; --i) {\n+\t\tprefix_sha1[i] = 0;\n+\t\tindex = hash_index(&hash_map, prefix_sha1);\n+\t\tif (index >= 0 && hash_map.entries[index].commit_sha1_len == i)\n+\t\t\treturn &(hash_map.entries[index]);\n \t}\n-\treturn found;\n+\treturn NULL;\n }\n \n static unsigned char *lookup_notes(const unsigned char *commit_sha1)\n {\n \tint index;\n-\tstruct subtree_entry *subtree;\n+\tstruct entry *subtree;\n+\n+\tif (!hash_map.size)\n+\t\treturn NULL;\n \n \t/* First, try to find the commit SHA1 directly in hash map */\n-\tindex = hash_map.size ? hash_index(&hash_map, commit_sha1) : -1;\n+\tindex = hash_index(&hash_map, commit_sha1);\n \tif (index >= 0)\n \t\treturn hash_map.entries[index].notes_sha1;\n \n \t/* Next, try finding a subtree that may contain the commit SHA1 */\n \tsubtree = lookup_subtree(commit_sha1);\n \n-\t/* Give up if no subtree found, or if subtree is already loaded */\n-\tif (!subtree || is_null_sha1(subtree->subtree_sha1))\n+\t/* Give up if no subtree found */\n+\tif (!subtree)\n \t\treturn NULL;\n \n \t/* Load subtree into hash_map, and retry lookup recursively */\n \tload_subtree(subtree);\n-\thashclr(subtree->subtree_sha1);\n \treturn lookup_notes(commit_sha1);\n }\n \n-- \n1.6.4.rc3.138.ga6b98.dirty\n"},{"id":"121791","messageId":"200908261231.01616.johan@herland.net","threadId":"20269","inReplyTo":"200908010436.57480.johan@herland.net","subject":"[RFC] Use a 16-tree instead of a 256-tree for storing notes","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-08-26T10:31:01Z","receivedAt":"2009-08-26T10:31:01Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"The 256-tree structure is considerably faster than storing all entries in a\nhash_map. Also, the memory consumption of the 256-tree structure is lower\nthan the hash_map, provided that you're only loading a few notes from a\n\"properly fanned-out\" notes tree (i.e. 100000 notes in a 2/2/36 structure).\nHowever, in the worst case (loading all 100000 notes), the memory usage of\nthe 256-tree structure (62.64 MB) is significantly worse than the hash_map\napproach (10.25 MB).\n\nThis patch modifies the 256-tree structure into a 16-tree structure. This\nsignificantly improves the memory situation. The result uses less memory\nthan both the 256-tree structure, and the hash_map approach, with a worst\ncase usage of 8.54 MB. Additionally, it seems to slightly improve the\nruntime performance as well (probably because of the improved memory usage).\n\nIn conclusion, this is faster and smaller than all the previous drafts.\n\n$ ./test_performance.sh\nTiming 100 reps of 'git log -n 10 refs/heads/master >/dev/null' at fanout level 0...\n15.05user 1.44system 0:16.59elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+782490minor)pagefaults 0swaps\n\nTiming 100 reps of 'git log -n 10 refs/heads/master >/dev/null' at fanout level 1...\n0.68user 0.17system 0:00.87elapsed 98%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+99585minor)pagefaults 0swaps\n\nTiming 100 reps of 'git log -n 10 refs/heads/master >/dev/null' at fanout level 2...\n0.41user 0.17system 0:00.61elapsed 97%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+94084minor)pagefaults 0swaps\n\nSigned-off-by: Johan Herland \n---\n\nHi,\n\nThis patch goes on top of the 256-tree RFC I sent earlier.\n\nIf nobody suggests further improvements, this patch will be\nincluded in the next iteration of the jh/notes topic.\n\n\nHave fun! :)\n\n...Johan\n\n\n notes.c | 26 ++++++++++++++------------\n 1 files changed, 14 insertions(+), 12 deletions(-)\n\ndiff --git a/notes.c b/notes.c\nindex 9282b16..32b1e01 100644\n--- a/notes.c\n+++ b/notes.c\n@@ -7,9 +7,9 @@\n #include \"tree-walk.h\"\n \n /*\n- * Use a non-balancing simple 256-tree structure with struct int_node as\n+ * Use a non-balancing simple 16-tree structure with struct int_node as\n * internal nodes, and struct leaf_node as leaf nodes. Each int_node has a\n- * 256-array of pointers to its children\n+ * 16-array of pointers to its children\n * The bottom 2 bits of each pointer is used to identify the pointer type\n * - ptr & 3 == 0 - NULL pointer, assert(ptr == NULL)\n * - ptr & 3 == 1 - pointer to next internal node - cast to struct int_node *\n@@ -21,18 +21,18 @@\n *\n * To add a leaf_node:\n * 1. Start at the root node, with n = 0\n- * 2. Use the nth byte of the key as an index into a:\n- * - If NULL, store the tweaked pointer directly into a[n]\n- * - If an int_node, recurse into that node and increment n\n- * - If a leaf_node:\n+ * 2. Use the nth nibble of the key as an index into a:\n+ * - If a[n] is NULL, store the tweaked pointer directly into a[n]\n+ * - If a[n] is an int_node, recurse into that node and increment n\n+ * - If a[n] is a leaf_node:\n * 1. Check if they're equal, and handle that (abort? overwrite?)\n * 2. Create a new int_node, and store both leaf_nodes there\n * 3. Store the new int_node into a[n].\n *\n * To find a leaf_node:\n * 1. Start at the root node, with n = 0\n- * 2. Use the nth byte of the key as an index into a:\n- * - If an int_node, recurse into that node and increment n\n+ * 2. Use the nth nibble of the key as an index into a:\n+ * - If a[n] is an int_node, recurse into that node and increment n\n * - If a leaf_node with matching key, return leaf_node (assert note entry)\n * - If a matching subtree entry, unpack that subtree entry (and remove it);\n * restart search at the current level.\n@@ -42,7 +42,7 @@\n * subtree entry (and remove it); restart search at the current level.\n */\n struct int_node {\n-\tvoid *a[256];\n+\tvoid *a[16];\n };\n \n /*\n@@ -79,11 +79,13 @@ static int initialized;\n static void load_subtree(struct leaf_node *subtree, struct int_node *node,\n \t\tunsigned int n);\n \n+#define GET_NIBBLE(n, sha1) (((sha1[n >> 1]) >> ((n & 0x01) << 2)) & 0x0f)\n+\n static struct leaf_node *note_tree_find(struct int_node *tree, unsigned char n,\n \t\tconst unsigned char *key_sha1)\n {\n \tstruct leaf_node *l;\n-\tunsigned char i = key_sha1[n];\n+\tunsigned char i = GET_NIBBLE(n, key_sha1);\n \tvoid *p = tree->a[i];\n \n \tswitch(GET_PTR_TYPE(p)) {\n@@ -138,7 +140,7 @@ static int note_tree_insert(struct int_node *tree, unsigned char n,\n \tstruct int_node *new_node;\n \tconst struct leaf_node *l;\n \tint ret;\n-\tunsigned char i = entry->key_sha1[n];\n+\tunsigned char i = GET_NIBBLE(n, entry->key_sha1);\n \tvoid *p = tree->a[i];\n \tassert(GET_PTR_TYPE(entry) == PTR_TYPE_NULL);\n \tswitch(GET_PTR_TYPE(p)) {\n@@ -211,7 +213,7 @@ static void load_subtree(struct leaf_node *subtree, struct int_node *node,\n \t\t sha1_to_hex(subtree->val_sha1));\n \n \tprefix_len = subtree->key_sha1[19];\n-\tassert(prefix_len >= n);\n+\tassert(prefix_len * 2 >= n);\n \tmemcpy(commit_sha1, subtree->key_sha1, prefix_len);\n \twhile (tree_entry(&desc, &entry)) {\n \t\tint len = get_sha1_hex_segment(entry.path, strlen(entry.path),\n-- \n1.6.4.304.g1365c.dirty\n"},{"id":"121794","messageId":"81b0412b0908260505m233d9a5cmefdd81e1ef51a299@mail.gmail.com","threadId":"20269","inReplyTo":"200908261231.01616.johan@herland.net","subject":"Re: [RFC] Use a 16-tree instead of a 256-tree for storing notes","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2009-08-26T12:05:52Z","receivedAt":"2009-08-26T12:05:52Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"On Wed, Aug 26, 2009 at 12:31, Johan Herland wrote:\n> The 256-tree structure is considerably faster than storing all entries in a\n\nThis part is confusing. Was 256-tree better (as in \"faster\") then?\n\n> hash_map. Also, the memory consumption of the 256-tree structure is lower\n> than the hash_map, provided that you're only loading a few notes from a\n> \"properly fanned-out\" notes tree (i.e. 100000 notes in a 2/2/36 structure).\n> However, in the worst case (loading all 100000 notes), the memory usage of\n> the 256-tree structure (62.64 MB) is significantly worse than the hash_map\n> approach (10.25 MB).\n>\n> This patch modifies the 256-tree structure into a 16-tree structure. This\n> significantly improves the memory situation. The result uses less memory\n> than both the 256-tree structure, and the hash_map approach, with a worst\n> case usage of 8.54 MB. Additionally, it seems to slightly improve the\n> runtime performance as well (probably because of the improved memory usage).\n"},{"id":"121798","messageId":"200908261456.55906.johan@herland.net","threadId":"20269","inReplyTo":"81b0412b0908260505m233d9a5cmefdd81e1ef51a299@mail.gmail.com","subject":"Re: [RFC] Use a 16-tree instead of a 256-tree for storing notes","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-08-26T12:56:55Z","receivedAt":"2009-08-26T12:56:55Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Wednesday 26 August 2009, Alex Riesen wrote:\n> On Wed, Aug 26, 2009 at 12:31, Johan Herland wrote:\n> > The 256-tree structure is considerably faster than storing all\n> > entries in a\n>\n> This part is confusing. Was 256-tree better (as in \"faster\") then?\n\n256-tree is faster than the everything-in-hash_map draft.\n16-tree is slightly faster than 256-tree\n\n256-tree uses more memory (in the worst case) that the \neverything-in-hash-map draft.\n16-tree uses less memory than both.\n\n\nMakes sense?\n\n\n...Johan\n\n-- \nJohan Herland, \nwww.herland.net\n"},{"id":"121800","messageId":"81b0412b0908260624v30d32cc1m96e798076b51cbc9@mail.gmail.com","threadId":"20269","inReplyTo":"200908261456.55906.johan@herland.net","subject":"Re: [RFC] Use a 16-tree instead of a 256-tree for storing notes","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2009-08-26T13:24:25Z","receivedAt":"2009-08-26T13:24:25Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"On Wed, Aug 26, 2009 at 14:56, Johan Herland wrote:\n> On Wednesday 26 August 2009, Alex Riesen wrote:\n>> On Wed, Aug 26, 2009 at 12:31, Johan Herland wrote:\n>> > The 256-tree structure is considerably faster than storing all\n>> > entries in a\n>>\n>> This part is confusing. Was 256-tree better (as in \"faster\") then?\n>\n> 256-tree is faster than the everything-in-hash_map draft.\n> 16-tree is slightly faster than 256-tree\n>\n> 256-tree uses more memory (in the worst case) that the\n> everything-in-hash-map draft.\n> 16-tree uses less memory than both.\n>\n> Makes sense?\n\nOh, it does, it is just confusingly presented. How about:\n\nThe 16-tree is both faster and has lower footprint then 256-tree\ncode, which in its turn is noticably faster and smaller then existing\nhash_map implementation. ...\n"},{"id":"121801","messageId":"4A95383A.4080104@op5.se","threadId":"20269","inReplyTo":"81b0412b0908260624v30d32cc1m96e798076b51cbc9@mail.gmail.com","subject":"Re: [RFC] Use a 16-tree instead of a 256-tree for storing notes","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2009-08-26T13:27:22Z","receivedAt":"2009-08-26T13:27:22Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Alex Riesen wrote:\n> On Wed, Aug 26, 2009 at 14:56, Johan Herland wrote:\n>> On Wednesday 26 August 2009, Alex Riesen wrote:\n>>> On Wed, Aug 26, 2009 at 12:31, Johan Herland wrote:\n>>>> The 256-tree structure is considerably faster than storing all\n>>>> entries in a\n>>> This part is confusing. Was 256-tree better (as in \"faster\") then?\n>> 256-tree is faster than the everything-in-hash_map draft.\n>> 16-tree is slightly faster than 256-tree\n>>\n>> 256-tree uses more memory (in the worst case) that the\n>> everything-in-hash-map draft.\n>> 16-tree uses less memory than both.\n>>\n>> Makes sense?\n> \n> Oh, it does, it is just confusingly presented. How about:\n> \n> The 16-tree is both faster and has lower footprint then 256-tree\n> code, which in its turn is noticably faster and smaller then existing\n> hash_map implementation. ...\n\nIf it's to be squashed in, why mention the 256-tree at all (except\nfor possibly as something to compare with at the end)?\nIf it goes on top, why mention the hash_map at all?\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n\nConsidering the successes of the wars on alcohol, poverty, drugs and\nterror, I think we should give some serious thought to declaring war\non peace.\n"},{"id":"121805","messageId":"200908261643.45097.johan@herland.net","threadId":"20269","inReplyTo":"4A95383A.4080104@op5.se","subject":"Re: [RFC] Use a 16-tree instead of a 256-tree for storing notes","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-08-26T14:43:44Z","receivedAt":"2009-08-26T14:43:44Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Wednesday 26 August 2009, Andreas Ericsson wrote:\n> Alex Riesen wrote:\n> > On Wed, Aug 26, 2009 at 14:56, Johan Herland \nwrote:\n> >> On Wednesday 26 August 2009, Alex Riesen wrote:\n> >>> On Wed, Aug 26, 2009 at 12:31, Johan Herland \nwrote:\n> >>>> The 256-tree structure is considerably faster than storing all\n> >>>> entries in a\n> >>>\n> >>> This part is confusing. Was 256-tree better (as in \"faster\")\n> >>> then?\n> >>\n> >> 256-tree is faster than the everything-in-hash_map draft.\n> >> 16-tree is slightly faster than 256-tree\n> >>\n> >> 256-tree uses more memory (in the worst case) that the\n> >> everything-in-hash-map draft.\n> >> 16-tree uses less memory than both.\n> >>\n> >> Makes sense?\n> >\n> > Oh, it does, it is just confusingly presented. How about:\n> >\n> > The 16-tree is both faster and has lower footprint then 256-tree\n> > code, which in its turn is noticably faster and smaller then\n> > existing hash_map implementation. ...\n>\n> If it's to be squashed in, why mention the 256-tree at all (except\n> for possibly as something to compare with at the end)?\n> If it goes on top, why mention the hash_map at all?\n\nAh. Sorry for the confusion. These patches are not meant to standalone \npatches in the jh/notes series. They just compare various solutions to \nthe problem of parsing a notes tree structure with fanout in an \nefficient manner.\n\nThe next iteration of the jh/notes series will include the preferred \nsolution (16-tree unless something better shows up), _without_ talking \nabout the differences between alternative solutions. As such the \nhash_map and 256-tree will not be mentioned at all.\n\n\n...Johan\n\n-- \nJohan Herland, \nwww.herland.net\n"},{"id":"121861","messageId":"alpine.DEB.1.00.0908271356020.7562@intel-tinevez-2-302","threadId":"20269","inReplyTo":"4A95383A.4080104@op5.se","subject":"Re: [RFC] Use a 16-tree instead of a 256-tree for storing notes","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-08-27T11:56:37Z","receivedAt":"2009-08-27T11:56:37Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Wed, 26 Aug 2009, Andreas Ericsson wrote:\n\n\n> If it's to be squashed in, why mention the 256-tree at all\n\nIt was labeled RFC, so I think it is perfectly fine to compare with other \ncontenders.\n\nThanks,\nDscho\n"}]}