{"thread":{"id":"16086","subject":"a few git notes numbers","startedAt":"2008-10-29T21:40:04Z","lastAt":"2008-10-29T21:40:04Z","messageCount":1,"participants":["Jeff King"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"94231","messageId":"20081029214003.GA19458@sigill.intra.peff.net","threadId":"16086","inReplyTo":null,"subject":"a few git notes numbers","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2008-10-29T21:40:04Z","receivedAt":"2008-10-29T21:40:04Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"I looked a little bit at how bad tree lookup speed would be for notes.\n\nMy test implementation was a notes tree made like this:\n\n blob=`echo this is a note | git hash-object -w --stdin`\n export GIT_INDEX_FILE=.git/notes\n # attach the note to every commit;\n # note that this uses a less-efficient ascii encoding\n git rev-list HEAD | while read commit; do\n   echo -e \"100644 blob $blob\\t$commit\"\n done | git update-index --index-info\n tree=`git write-tree`\n commit=`echo notes | git commit-tree $tree`\n git update-ref refs/notes $tree\n\nThen I added a %N format specifier that looked up the note in the\nrefs/notes tree for every commit. For a baseline, here is just looking\nat the subject of a commit message:\n\n   /usr/bin/time git log --pretty=format:'%s' >/dev/null\n   0.57user 0.00system 0:00.58elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n   0inputs+0outputs (0major+3497minor)pagefaults 0swaps\n\nSo it takes about half a second without notes. When I used the regular\ninit_tree_desc() and tree_entry() walk, that bumped to about 37 seconds\n(sorry, I didn't save the /usr/bin/time output). Converting the stupid\nascii filename format to binary brought it down to 27 seconds. So both\nobviously crappy due to the linear walk.\n\nThen at somebody (David Reiss?)'s suggestion, I used our hash table\nimplementation and pre-seeded the table. I kept with the ascii\nfilenames in the tree, since they are a little easier to create, and\nsince we only pay the price for conversion when seeding the hash table.\nAnd I got these numbers:\n\n  $ /usr/bin/time git log --pretty=format:'%s: %N' >/dev/null\n  0.85user 0.12system 0:00.98elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n  0inputs+0outputs (0major+20914minor)pagefaults 0swaps\n\nSo not too bad, though check out those minor page faults. Patch is\nbelow:\n\n---\ndiff --git a/pretty.c b/pretty.c\nindex f6ff312..c4930ac 100644\n--- a/pretty.c\n+++ b/pretty.c\n@@ -498,6 +498,67 @@ static void format_decoration(struct strbuf *sb, const struct commit *commit)\n \t\tstrbuf_addch(sb, ')');\n }\n \n+struct note_entry {\n+\tunsigned char from[20];\n+\tunsigned char to[20];\n+\tstruct note_entry *next;\n+};\n+\n+static struct hash_table *notes_tree(void)\n+{\n+\tstatic int initialized;\n+\tstatic struct hash_table table;\n+\n+\tif (!initialized) {\n+\t\tunsigned char sha1[20];\n+\t\tstruct tree *tree;\n+\t\tstruct tree_desc desc;\n+\t\tstruct name_entry entry;\n+\n+\t\tinit_hash(&table);\n+\t\tif(get_sha1(\"refs/notes\", sha1) == 0)\n+\t\t\ttree = parse_tree_indirect(sha1);\n+\t\tinit_tree_desc(&desc, tree->buffer, tree->size);\n+\t\twhile (tree_entry(&desc, &entry)) {\n+\t\t\tstruct note_entry *note;\n+\t\t\tunsigned int hash;\n+\t\t\tvoid **pos;\n+\n+\t\t\tnote = malloc(sizeof *note);\n+\t\t\tif (get_sha1_hex(entry.path, note->from) < 0) {\n+\t\t\t\tfree(note);\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\t\t\tmemcpy(note->to, entry.sha1, 20);\n+\t\t\tmemcpy(&hash, note->from, sizeof(hash));\n+\t\t\tpos = insert_hash(hash, note, &table);\n+\t\t\tif (pos) {\n+\t\t\t\tnote->next = *pos;\n+\t\t\t\t*pos = note;\n+\t\t\t}\n+\t\t}\n+\n+\t\tinitialized = 1;\n+\t}\n+\treturn &table;\n+}\n+\n+static char *lookup_note(const unsigned char *sha1, unsigned long *size) {\n+\tstruct hash_table *table = notes_tree();\n+\tstruct note_entry *note;\n+\tunsigned int hash;\n+\n+\tmemcpy(&hash, sha1, sizeof(hash));\n+\tnote = lookup_hash(hash, table);\n+\twhile (note) {\n+\t\tif (!memcmp(sha1, note->from, 20)) {\n+\t\t\tenum object_type type;\n+\t\t\treturn read_sha1_file(note->to, &type, size);\n+\t\t}\n+\t}\n+\treturn NULL;\n+}\n+\n static size_t format_commit_item(struct strbuf *sb, const char *placeholder,\n                                void *context)\n {\n@@ -537,6 +598,17 @@ static size_t format_commit_item(struct strbuf *sb, const char *placeholder,\n \t\t\treturn 3;\n \t\t} else\n \t\t\treturn 0;\n+\tcase 'N':\n+\t\t{\n+\t\t\tunsigned long size;\n+\t\t\tchar *buf;\n+\t\t\tbuf = lookup_note(commit->object.sha1, &size);\n+\t\t\tif (buf) {\n+\t\t\t\tstrbuf_add(sb, buf, size);\n+\t\t\t\tfree(buf);\n+\t\t\t}\n+\t\t}\n+\t\treturn 1;\n \t}\n \n \t/* these depend on the commit */\n"}]}