{"thread":{"id":"26943","subject":"fast-import: use struct hash_table","startedAt":"2011-03-31T11:59:56Z","lastAt":"2012-04-11T12:15:31Z","messageCount":13,"participants":["David Barr","Jonathan Nieder"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"164778","messageId":"1301572798-9973-1-git-send-email-david.barr@cordelta.com","threadId":"26943","inReplyTo":null,"subject":"fast-import: use struct hash_table","fromName":"David Barr","fromEmail":"david.barr@cordelta.com","sentAt":"2011-03-31T11:59:56Z","receivedAt":"2011-03-31T11:59:56Z","isPatch":false,"sender":{"key":"david.barr@cordelta.com","avatar":"https://avatars.githubusercontent.com/u/220594?v=4"},"body":"The current custom hash tables in fast-import.c do not grow.\nThis causes poor performance for very large imports.\nFortunately, we have struct hash_table and friends so there's\nno need to write cumbersome hash table growth code.\n\nIf anyone is interested, I think the hash API documentation\ncould use an example or two.\n"},{"id":"164779","messageId":"1301572798-9973-2-git-send-email-david.barr@cordelta.com","threadId":"26943","inReplyTo":"1301572798-9973-1-git-send-email-david.barr@cordelta.com","subject":"[PATCH 1/2] fast-import: use struct hash_table for atom strings","fromName":"David Barr","fromEmail":"david.barr@cordelta.com","sentAt":"2011-03-31T11:59:57Z","receivedAt":"2011-03-31T11:59:57Z","isPatch":true,"sender":{"key":"david.barr@cordelta.com","avatar":"https://avatars.githubusercontent.com/u/220594?v=4"},"body":"Signed-off-by: David Barr <david.barr@cordelta.com>\n---\n fast-import.c |   17 ++++++++++-------\n 1 files changed, 10 insertions(+), 7 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex 65d65bf..0592b21 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -300,9 +300,8 @@ static size_t total_allocd;\n static struct mem_pool *mem_pool;\n \n /* Atom management */\n-static unsigned int atom_table_sz = 4451;\n static unsigned int atom_cnt;\n-static struct atom_str **atom_table;\n+static struct hash_table atom_table;\n \n /* The .pack file being generated */\n static unsigned int pack_id;\n@@ -680,10 +679,11 @@ static struct object_entry *find_mark(uintmax_t idnum)\n \n static struct atom_str *to_atom(const char *s, unsigned short len)\n {\n-\tunsigned int hc = hc_str(s, len) % atom_table_sz;\n+\tunsigned int hc = hc_str(s, len);\n \tstruct atom_str *c;\n+\tvoid **pos;\n \n-\tfor (c = atom_table[hc]; c; c = c->next_atom)\n+\tfor (c = lookup_hash(hc, &atom_table); c; c = c->next_atom)\n \t\tif (c->str_len == len && !strncmp(s, c->str_dat, len))\n \t\t\treturn c;\n \n@@ -691,8 +691,12 @@ static struct atom_str *to_atom(const char *s, unsigned short len)\n \tc->str_len = len;\n \tstrncpy(c->str_dat, s, len);\n \tc->str_dat[len] = 0;\n-\tc->next_atom = atom_table[hc];\n-\tatom_table[hc] = c;\n+\tc->next_atom = NULL;\n+\tpos = insert_hash(hc, c, &atom_table);\n+\tif (pos) {\n+\t\tc->next_atom = *pos;\n+\t\t*pos = c;\n+\t}\n \tatom_cnt++;\n \treturn c;\n }\n@@ -3263,7 +3267,6 @@ int main(int argc, const char **argv)\n \n \talloc_objects(object_entry_alloc);\n \tstrbuf_init(&command_buf, 0);\n-\tatom_table = xcalloc(atom_table_sz, sizeof(struct atom_str*));\n \tbranch_table = xcalloc(branch_table_sz, sizeof(struct branch*));\n \tavail_tree_table = xcalloc(avail_tree_table_sz, sizeof(struct avail_tree_content*));\n \tmarks = pool_calloc(1, sizeof(struct mark_set));\n-- \n1.7.3.2.846.gf4b062\n"},{"id":"164780","messageId":"1301572798-9973-3-git-send-email-david.barr@cordelta.com","threadId":"26943","inReplyTo":"1301572798-9973-1-git-send-email-david.barr@cordelta.com","subject":"[PATCH 2/2] fast-import: use struct hash_table for objects","fromName":"David Barr","fromEmail":"david.barr@cordelta.com","sentAt":"2011-03-31T11:59:58Z","receivedAt":"2011-03-31T11:59:58Z","isPatch":true,"sender":{"key":"david.barr@cordelta.com","avatar":"https://avatars.githubusercontent.com/u/220594?v=4"},"body":"Signed-off-by: David Barr <david.barr@cordelta.com>\n---\n fast-import.c |   19 ++++++++++++-------\n 1 files changed, 12 insertions(+), 7 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex 0592b21..8fd8ea9 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -313,7 +313,7 @@ static off_t pack_size;\n /* Table of objects we've written. */\n static unsigned int object_entry_alloc = 5000;\n static struct object_entry_pool *blocks;\n-static struct object_entry *object_table[1 << 16];\n+static struct hash_table object_table;\n static struct mark_set *marks;\n static const char *export_marks_file;\n static const char *import_marks_file;\n@@ -555,9 +555,9 @@ static struct object_entry *new_object(unsigned char *sha1)\n \n static struct object_entry *find_object(unsigned char *sha1)\n {\n-\tunsigned int h = sha1[0] << 8 | sha1[1];\n+\tunsigned int h = sha1[0] << 24 | sha1[1] << 16 | sha1[2] << 8 | sha1[3];\n \tstruct object_entry *e;\n-\tfor (e = object_table[h]; e; e = e->next)\n+\tfor (e = lookup_hash(h, &object_table); e; e = e->next)\n \t\tif (!hashcmp(sha1, e->idx.sha1))\n \t\t\treturn e;\n \treturn NULL;\n@@ -565,8 +565,9 @@ static struct object_entry *find_object(unsigned char *sha1)\n \n static struct object_entry *insert_object(unsigned char *sha1)\n {\n-\tunsigned int h = sha1[0] << 8 | sha1[1];\n-\tstruct object_entry *e = object_table[h];\n+\tunsigned int h = sha1[0] << 24 | sha1[1] << 16 | sha1[2] << 8 | sha1[3];\n+\tstruct object_entry *e = lookup_hash(h, &object_table);\n+\tvoid **pos;\n \n \twhile (e) {\n \t\tif (!hashcmp(sha1, e->idx.sha1))\n@@ -575,9 +576,13 @@ static struct object_entry *insert_object(unsigned char *sha1)\n \t}\n \n \te = new_object(sha1);\n-\te->next = object_table[h];\n+\te->next = NULL;\n \te->idx.offset = 0;\n-\tobject_table[h] = e;\n+\tpos = insert_hash(h, e, &object_table);\n+\tif (pos) {\n+\t\te->next = *pos;\n+\t\t*pos = e;\n+\t}\n \treturn e;\n }\n \n-- \n1.7.3.2.846.gf4b062\n"},{"id":"164939","messageId":"20110402024209.GA6039@elie","threadId":"26943","inReplyTo":"1301572798-9973-2-git-send-email-david.barr@cordelta.com","subject":"Re: [PATCH 1/2] fast-import: use struct hash_table for atom strings","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2011-04-02T02:42:09Z","receivedAt":"2011-04-02T02:42:09Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Hi,\n\nDavid Barr wrote:\n\n> Signed-off-by: David Barr <david.barr@cordelta.com>\n\nThanks, this is a welcome change.  But perhaps it would be nice to\nexplain why, here? :)\n\nE.g., what is stored in the atom table? does it tend to get big?  does\nthe existing code allow it to grow? this change will allow it to grow,\nright? what is the downside to this change (if any)?\n\nEspecially, numbers (timings) illustrating the effect on typical\nuse and effect on scalability would be interesting.\n\n> ---\n>  fast-import.c |   17 ++++++++++-------\n>  1 files changed, 10 insertions(+), 7 deletions(-)\n> \n> diff --git a/fast-import.c b/fast-import.c\n> index 65d65bf..0592b21 100644\n> --- a/fast-import.c\n> +++ b/fast-import.c\n> @@ -300,9 +300,8 @@ static size_t total_allocd;\n>  static struct mem_pool *mem_pool;\n>  \n>  /* Atom management */\n> -static unsigned int atom_table_sz = 4451;\n>  static unsigned int atom_cnt;\n> -static struct atom_str **atom_table;\n> +static struct hash_table atom_table;\n>  \n>  /* The .pack file being generated */\n>  static unsigned int pack_id;\n> @@ -680,10 +679,11 @@ static struct object_entry *find_mark(uintmax_t idnum)\n>  \n>  static struct atom_str *to_atom(const char *s, unsigned short len)\n>  {\n> -\tunsigned int hc = hc_str(s, len) % atom_table_sz;\n> +\tunsigned int hc = hc_str(s, len);\n>  \tstruct atom_str *c;\n> +\tvoid **pos;\n>  \n> -\tfor (c = atom_table[hc]; c; c = c->next_atom)\n> +\tfor (c = lookup_hash(hc, &atom_table); c; c = c->next_atom)\n>  \t\tif (c->str_len == len && !strncmp(s, c->str_dat, len))\n>  \t\t\treturn c;\n>  \n> @@ -691,8 +691,12 @@ static struct atom_str *to_atom(const char *s, unsigned short len)\n>  \tc->str_len = len;\n>  \tstrncpy(c->str_dat, s, len);\n>  \tc->str_dat[len] = 0;\n> -\tc->next_atom = atom_table[hc];\n> -\tatom_table[hc] = c;\n> +\tc->next_atom = NULL;\n> +\tpos = insert_hash(hc, c, &atom_table);\n> +\tif (pos) {\n> +\t\tc->next_atom = *pos;\n> +\t\t*pos = c;\n> +\t}\n\nIf I understand correctly, this puts new atoms at the start of the\nchain, just like v1.7.4-rc0~40^2 (fast-import: insert new object\nentries at start of hash bucket, 2010-11-23) did for objects.  Did you\nmeasure and find this faster, or is it just for simplicity or\nconsistency?  (I'd personally be fine with it either way, but it seems\nprudent to ask.)\n\n>  \tatom_cnt++;\n>  \treturn c;\n>  }\n> @@ -3263,7 +3267,6 @@ int main(int argc, const char **argv)\n>  \n>  \talloc_objects(object_entry_alloc);\n>  \tstrbuf_init(&command_buf, 0);\n> -\tatom_table = xcalloc(atom_table_sz, sizeof(struct atom_str*));\n>  \tbranch_table = xcalloc(branch_table_sz, sizeof(struct branch*));\n>  \tavail_tree_table = xcalloc(avail_tree_table_sz, sizeof(struct avail_tree_content*));\n>  \tmarks = pool_calloc(1, sizeof(struct mark_set));\n\nWe never call init_hash.  That's technically safe because init_hash\njust zeroes out the table, but I think I'd rather see us using it\nanyway or documenting in api-hash.txt that it's safe not to use.\n\nLooks good.  Will queue to give it some testing.\n"},{"id":"164940","messageId":"20110402024636.GB6039@elie","threadId":"26943","inReplyTo":"1301572798-9973-3-git-send-email-david.barr@cordelta.com","subject":"Re: [PATCH 2/2] fast-import: use struct hash_table for objects","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2011-04-02T02:46:36Z","receivedAt":"2011-04-02T02:46:36Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"David Barr wrote:\n\n> Signed-off-by: David Barr <david.barr@cordelta.com>\n\nThanks, this one is even more welcome. :)  Same comments as the other\npatch apply.  Keeping the patch in full below so others can comment.\n\nOne comment below (search for object.c to find it; sorry).\n\n> ---\n>  fast-import.c |   19 ++++++++++++-------\n>  1 files changed, 12 insertions(+), 7 deletions(-)\n> \n> diff --git a/fast-import.c b/fast-import.c\n> index 0592b21..8fd8ea9 100644\n> --- a/fast-import.c\n> +++ b/fast-import.c\n> @@ -313,7 +313,7 @@ static off_t pack_size;\n>  /* Table of objects we've written. */\n>  static unsigned int object_entry_alloc = 5000;\n>  static struct object_entry_pool *blocks;\n> -static struct object_entry *object_table[1 << 16];\n> +static struct hash_table object_table;\n>  static struct mark_set *marks;\n>  static const char *export_marks_file;\n>  static const char *import_marks_file;\n> @@ -555,9 +555,9 @@ static struct object_entry *new_object(unsigned char *sha1)\n>  \n>  static struct object_entry *find_object(unsigned char *sha1)\n>  {\n> -\tunsigned int h = sha1[0] << 8 | sha1[1];\n> +\tunsigned int h = sha1[0] << 24 | sha1[1] << 16 | sha1[2] << 8 | sha1[3];\n>  \tstruct object_entry *e;\n> -\tfor (e = object_table[h]; e; e = e->next)\n> +\tfor (e = lookup_hash(h, &object_table); e; e = e->next)\n>  \t\tif (!hashcmp(sha1, e->idx.sha1))\n>  \t\t\treturn e;\n>  \treturn NULL;\n> @@ -565,8 +565,9 @@ static struct object_entry *find_object(unsigned char *sha1)\n>  \n>  static struct object_entry *insert_object(unsigned char *sha1)\n>  {\n> -\tunsigned int h = sha1[0] << 8 | sha1[1];\n> -\tstruct object_entry *e = object_table[h];\n> +\tunsigned int h = sha1[0] << 24 | sha1[1] << 16 | sha1[2] << 8 | sha1[3];\n> +\tstruct object_entry *e = lookup_hash(h, &object_table);\n> +\tvoid **pos;\n\nobject.c uses memcpy for this, like so:\n\n\tmemcpy(&h, sha1, sizeof(unsigned int));\n\nwhich strikes me as sensible (to avoid fighting with the machine about\nendianness since this table is only in memory).\n\n>  \n>  \twhile (e) {\n>  \t\tif (!hashcmp(sha1, e->idx.sha1))\n> @@ -575,9 +576,13 @@ static struct object_entry *insert_object(unsigned char *sha1)\n>  \t}\n>  \n>  \te = new_object(sha1);\n> -\te->next = object_table[h];\n> +\te->next = NULL;\n>  \te->idx.offset = 0;\n> -\tobject_table[h] = e;\n> +\tpos = insert_hash(h, e, &object_table);\n> +\tif (pos) {\n> +\t\te->next = *pos;\n> +\t\t*pos = e;\n> +\t}\n>  \treturn e;\n>  }\n>  \n> -- \n> 1.7.3.2.846.gf4b062\n> \n"},{"id":"164941","messageId":"20110402024803.GC6039@elie","threadId":"26943","inReplyTo":"1301572798-9973-1-git-send-email-david.barr@cordelta.com","subject":"Re: fast-import: use struct hash_table","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2011-04-02T02:48:03Z","receivedAt":"2011-04-02T02:48:03Z","isPatch":false,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"David Barr wrote:\n\n> If anyone is interested, I think the hash API documentation\n> could use an example or two.\n\nYes, please. :)  At the very least, a \"here is a quick checklist\nfor how to use it\" tutorial would be very nice.\n"},{"id":"164942","messageId":"20110402033321.GA7023@elie","threadId":"26943","inReplyTo":"20110402024209.GA6039@elie","subject":"Re: [PATCH 1/2] fast-import: use struct hash_table for atom strings","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2011-04-02T03:33:21Z","receivedAt":"2011-04-02T03:33:21Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Jonathan Nieder wrote:\n\n>> @@ -691,8 +691,12 @@ static struct atom_str *to_atom(const char *s, unsigned short len)\n>>  \tc->str_len = len;\n>>  \tstrncpy(c->str_dat, s, len);\n>>  \tc->str_dat[len] = 0;\n>> -\tc->next_atom = atom_table[hc];\n>> -\tatom_table[hc] = c;\n>> +\tc->next_atom = NULL;\n>> +\tpos = insert_hash(hc, c, &atom_table);\n>> +\tif (pos) {\n>> +\t\tc->next_atom = *pos;\n>> +\t\t*pos = c;\n>> +\t}\n>\n> If I understand correctly, this puts new atoms at the start of the\n> chain, just like v1.7.4-rc0~40^2 (fast-import: insert new object\n> entries at start of hash bucket, 2010-11-23) did for objects.  Did you\n> measure and find this faster, or is it just for simplicity or\n> consistency?  (I'd personally be fine with it either way, but it seems\n> prudent to ask.)\n\nAgh.  Too-quick reading on my part (or rather, I lazily made an\nassumption and didn't pay much attention to the old code at all).  I\nhave no reason to believe inserting at the end of the bucket would be\nbetter, and it would certainly be more complex.\n\nSorry, folks.  Don't mind me.\n"},{"id":"188949","messageId":"20120411121116.GA19568@burratino","threadId":"26943","inReplyTo":"1301572798-9973-1-git-send-email-david.barr@cordelta.com","subject":"[PATCH/RFC v2 0/4] Re: fast-import: use struct hash_table","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2012-04-11T12:11:16Z","receivedAt":"2012-04-11T12:11:16Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Hi David,\n\nDavid Barr wrote:\n\n> The current custom hash tables in fast-import.c do not grow.\n> This causes poor performance for very large imports.\n> Fortunately, we have struct hash_table and friends so there's\n> no need to write cumbersome hash table growth code.\n\nThanks for these patches.  I've tentatively queued the following\npatches at\n\n  git://repo.or.cz/git/jrn.git fast-import-pu\n\nand would be happy to ask Junio to pull them if they look sane to you.\n\nSorry for the long delay.\n\nDavid Barr (2):\n  fast-import: allow object_table to grow dynamically\n  fast-import: allow atom_table to grow dynamically\n\nJonathan Nieder (2):\n  fast-import: allow branch_table to grow dynamically\n  fast-import: use DIV_ROUND_UP\n\n fast-import.c |  153 ++++++++++++++++++++++++++++++++++++++-------------------\n 1 file changed, 102 insertions(+), 51 deletions(-)\n"},{"id":"188950","messageId":"20120411121259.GB19568@burratino","threadId":"26943","inReplyTo":"1301572798-9973-1-git-send-email-david.barr@cordelta.com","subject":"[PATCH/RFC v2 0/4 resend] Re: fast-import: use struct hash_table","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2012-04-11T12:12:59Z","receivedAt":"2012-04-11T12:12:59Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"(resending with newer address for David.  Sorry for the noise)\nHi David,\n\nDavid Barr wrote:\n\n> The current custom hash tables in fast-import.c do not grow.\n> This causes poor performance for very large imports.\n> Fortunately, we have struct hash_table and friends so there's\n> no need to write cumbersome hash table growth code.\n\nThanks for these patches.  I've tentatively queued the following\npatches at\n\n  git://repo.or.cz/git/jrn.git fast-import-pu\n\nand would be happy to ask Junio to pull them if they look sane to you.\n\nSorry for the long delay.\n\nDavid Barr (2):\n  fast-import: allow object_table to grow dynamically\n  fast-import: allow atom_table to grow dynamically\n\nJonathan Nieder (2):\n  fast-import: allow branch_table to grow dynamically\n  fast-import: use DIV_ROUND_UP\n\n fast-import.c |  153 ++++++++++++++++++++++++++++++++++++++-------------------\n 1 file changed, 102 insertions(+), 51 deletions(-)\n"},{"id":"188951","messageId":"20120411121342.GC19568@burratino","threadId":"26943","inReplyTo":"20120411121259.GB19568@burratino","subject":"[PATCH 1/4] fast-import: allow object_table to grow dynamically","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2012-04-11T12:13:42Z","receivedAt":"2012-04-11T12:13:42Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"From: David Barr <david.barr@cordelta.com>\nDate: Thu, 31 Mar 2011 22:59:58 +1100\n\nThe current custom hash tables in fast-import.c do not grow.  This\ncauses poor performance for very large imports.\n\nShawn O. Pearce writes:\n\n> I can tell you why its fixed size... when I wrote fast-import to\n> support the Mozilla repository import, we had an estimate on the\n> number of objects that we needed fast-import to handle in a given run.\n> From that estimate we concluded that a table of 2^16 was sufficiently\n> large enough, as the hash chains would only be some small N long given\n> the total number of objects we needed to handle for Mozilla.  Doubling\n> that into 2^17 or larger wasn't useful, and using a smaller table like\n> 2^14 produced too long of a chain.\n>\n> Once this code was working, we moved on to other features, and never\n> reconsidered the table size.  This table should be growing if the\n> initial 2^16 isn't big enough.  Its just that nobody has ever noticed\n> that I hardcoded the size.  :-)\n\nFortunately, we have struct hash_table and friends so there's no need\nto write cumbersome hash table growth code.\n\n[jn: using native endianness for hash, new commit message; with\n init_hash call, even though it's not currently needed]\n\nSigned-off-by: David Barr <david.barr@cordelta.com>\nSigned-off-by: Jonathan Nieder <jrnieder@gmail.com>\n---\n fast-import.c |   27 ++++++++++++++++++++-------\n 1 file changed, 20 insertions(+), 7 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex 78d97868..a79a1260 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -313,7 +313,7 @@ static off_t pack_size;\n /* Table of objects we've written. */\n static unsigned int object_entry_alloc = 5000;\n static struct object_entry_pool *blocks;\n-static struct object_entry *object_table[1 << 16];\n+static struct hash_table object_table;\n static struct mark_set *marks;\n static const char *export_marks_file;\n static const char *import_marks_file;\n@@ -553,11 +553,18 @@ static struct object_entry *new_object(unsigned char *sha1)\n \treturn e;\n }\n \n+static unsigned int hash_sha1(const unsigned char *sha1)\n+{\n+\tunsigned int h;\n+\tmemcpy(&h, sha1, sizeof(unsigned int));\n+\treturn h;\n+}\n+\n static struct object_entry *find_object(unsigned char *sha1)\n {\n-\tunsigned int h = sha1[0] << 8 | sha1[1];\n+\tunsigned int h = hash_sha1(sha1);\n \tstruct object_entry *e;\n-\tfor (e = object_table[h]; e; e = e->next)\n+\tfor (e = lookup_hash(h, &object_table); e; e = e->next)\n \t\tif (!hashcmp(sha1, e->idx.sha1))\n \t\t\treturn e;\n \treturn NULL;\n@@ -565,8 +572,9 @@ static struct object_entry *find_object(unsigned char *sha1)\n \n static struct object_entry *insert_object(unsigned char *sha1)\n {\n-\tunsigned int h = sha1[0] << 8 | sha1[1];\n-\tstruct object_entry *e = object_table[h];\n+\tunsigned int h = hash_sha1(sha1);\n+\tstruct object_entry *e = lookup_hash(h, &object_table);\n+\tvoid **pos;\n \n \twhile (e) {\n \t\tif (!hashcmp(sha1, e->idx.sha1))\n@@ -575,9 +583,13 @@ static struct object_entry *insert_object(unsigned char *sha1)\n \t}\n \n \te = new_object(sha1);\n-\te->next = object_table[h];\n+\te->next = NULL;\n \te->idx.offset = 0;\n-\tobject_table[h] = e;\n+\tpos = insert_hash(h, e, &object_table);\n+\tif (pos) {\n+\t\te->next = *pos;\n+\t\t*pos = e;\n+\t}\n \treturn e;\n }\n \n@@ -3261,6 +3273,7 @@ int main(int argc, const char **argv)\n \tatom_table = xcalloc(atom_table_sz, sizeof(struct atom_str*));\n \tbranch_table = xcalloc(branch_table_sz, sizeof(struct branch*));\n \tavail_tree_table = xcalloc(avail_tree_table_sz, sizeof(struct avail_tree_content*));\n+\tinit_hash(&object_table);\n \tmarks = pool_calloc(1, sizeof(struct mark_set));\n \n \tglobal_argc = argc;\n-- \n1.7.10\n"},{"id":"188952","messageId":"20120411121414.GD19568@burratino","threadId":"26943","inReplyTo":"20120411121259.GB19568@burratino","subject":"[PATCH 2/4] fast-import: allow atom_table to grow dynamically","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2012-04-11T12:14:14Z","receivedAt":"2012-04-11T12:14:14Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"From: David Barr <david.barr@cordelta.com>\nDate: Thu, 31 Mar 2011 22:59:57 +1100\n\nUse a struct hash_table to allow the table for atom strings to\ngrow.  See the previous commit for explanations.\n\n[jn: with init_hash call, even though it's technically not needed]\n\nSigned-off-by: David Barr <david.barr@cordelta.com>\nSigned-off-by: Jonathan Nieder <jrnieder@gmail.com>\n---\n fast-import.c |   18 +++++++++++-------\n 1 file changed, 11 insertions(+), 7 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex a79a1260..67769573 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -299,9 +299,8 @@ static size_t total_allocd;\n static struct mem_pool *mem_pool;\n \n /* Atom management */\n-static unsigned int atom_table_sz = 4451;\n static unsigned int atom_cnt;\n-static struct atom_str **atom_table;\n+static struct hash_table atom_table;\n \n /* The .pack file being generated */\n static unsigned int pack_id;\n@@ -691,10 +690,11 @@ static struct object_entry *find_mark(uintmax_t idnum)\n \n static struct atom_str *to_atom(const char *s, unsigned short len)\n {\n-\tunsigned int hc = hc_str(s, len) % atom_table_sz;\n+\tunsigned int hc = hc_str(s, len);\n \tstruct atom_str *c;\n+\tvoid **pos;\n \n-\tfor (c = atom_table[hc]; c; c = c->next_atom)\n+\tfor (c = lookup_hash(hc, &atom_table); c; c = c->next_atom)\n \t\tif (c->str_len == len && !strncmp(s, c->str_dat, len))\n \t\t\treturn c;\n \n@@ -702,8 +702,12 @@ static struct atom_str *to_atom(const char *s, unsigned short len)\n \tc->str_len = len;\n \tstrncpy(c->str_dat, s, len);\n \tc->str_dat[len] = 0;\n-\tc->next_atom = atom_table[hc];\n-\tatom_table[hc] = c;\n+\tc->next_atom = NULL;\n+\tpos = insert_hash(hc, c, &atom_table);\n+\tif (pos) {\n+\t\tc->next_atom = *pos;\n+\t\t*pos = c;\n+\t}\n \tatom_cnt++;\n \treturn c;\n }\n@@ -3270,7 +3274,7 @@ int main(int argc, const char **argv)\n \n \talloc_objects(object_entry_alloc);\n \tstrbuf_init(&command_buf, 0);\n-\tatom_table = xcalloc(atom_table_sz, sizeof(struct atom_str*));\n+\tinit_hash(&atom_table);\n \tbranch_table = xcalloc(branch_table_sz, sizeof(struct branch*));\n \tavail_tree_table = xcalloc(avail_tree_table_sz, sizeof(struct avail_tree_content*));\n \tinit_hash(&object_table);\n-- \n1.7.10\n"},{"id":"188953","messageId":"20120411121500.GE19568@burratino","threadId":"26943","inReplyTo":"20120411121259.GB19568@burratino","subject":"[PATCH 3/4] fast-import: allow branch_table to grow dynamically","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2012-04-11T12:15:01Z","receivedAt":"2012-04-11T12:15:01Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Date: Mon, 30 May 2011 22:25:35 -0500\n\nUse a struct hash_table to allow the table for branches to grow.  The\nmain benefit is to make the code more self-consistent and avoid a\nmagic number for table size.\n\nSigned-off-by: Jonathan Nieder <jrnieder@gmail.com>\n---\n fast-import.c |  104 ++++++++++++++++++++++++++++++++++++++-------------------\n 1 file changed, 69 insertions(+), 35 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex 67769573..ebb27006 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -334,8 +334,7 @@ static struct strbuf new_tree = STRBUF_INIT;\n /* Branch data */\n static unsigned long max_active_branches = 5;\n static unsigned long cur_active_branches;\n-static unsigned long branch_table_sz = 1039;\n-static struct branch **branch_table;\n+static struct hash_table branch_table;\n static struct branch *active_branches;\n \n /* Tag data */\n@@ -364,8 +363,10 @@ static void parse_argv(void);\n static void parse_cat_blob(void);\n static void parse_ls(struct branch *b);\n \n-static void write_branch_report(FILE *rpt, struct branch *b)\n+static int write_branch_report(struct branch *b, void *cb)\n {\n+\tFILE *rpt = cb;\n+\n \tfprintf(rpt, \"%s:\\n\", b->name);\n \n \tfprintf(rpt, \"  status      :\");\n@@ -388,6 +389,36 @@ static void write_branch_report(FILE *rpt, struct branch *b)\n \tfputc('\\n', rpt);\n \n \tfputc('\\n', rpt);\n+\n+\treturn 0;\n+}\n+\n+struct for_each_branch_data {\n+\tint (*fn)(struct branch *, void *);\n+\tvoid *data;\n+};\n+\n+static int for_each_branch_helper(void *bucket, void *helper_data)\n+{\n+\tstruct for_each_branch_data *cb = helper_data;\n+\tstruct branch *b;\n+\tint sum = 0;\n+\n+\tfor (b = bucket; b; b = b->table_next_branch) {\n+\t\tint val = cb->fn(b, cb->data);\n+\t\tif (val < 0)\n+\t\t\treturn val;\n+\t\tsum += val;\n+\t}\n+\treturn sum;\n+}\n+\n+static int for_each_branch(int (*fn)(struct branch *, void *), void *data)\n+{\n+\tstruct for_each_branch_data cb;\n+\tcb.fn = fn;\n+\tcb.data = data;\n+\treturn for_each_hash(&branch_table, for_each_branch_helper, &cb);\n }\n \n static void dump_marks_helper(FILE *, uintmax_t, struct mark_set *);\n@@ -445,10 +476,7 @@ static void write_crash_report(const char *err)\n \tfputc('\\n', rpt);\n \tfputs(\"Inactive Branches\\n\", rpt);\n \tfputs(\"-----------------\\n\", rpt);\n-\tfor (lu = 0; lu < branch_table_sz; lu++) {\n-\t\tfor (b = branch_table[lu]; b; b = b->table_next_branch)\n-\t\t\twrite_branch_report(rpt, b);\n-\t}\n+\tfor_each_branch(write_branch_report, rpt);\n \n \tif (first_tag) {\n \t\tstruct tag *tg;\n@@ -714,10 +742,10 @@ static struct atom_str *to_atom(const char *s, unsigned short len)\n \n static struct branch *lookup_branch(const char *name)\n {\n-\tunsigned int hc = hc_str(name, strlen(name)) % branch_table_sz;\n+\tunsigned int hc = hc_str(name, strlen(name));\n \tstruct branch *b;\n \n-\tfor (b = branch_table[hc]; b; b = b->table_next_branch)\n+\tfor (b = lookup_hash(hc, &branch_table); b; b = b->table_next_branch)\n \t\tif (!strcmp(name, b->name))\n \t\t\treturn b;\n \treturn NULL;\n@@ -725,8 +753,9 @@ static struct branch *lookup_branch(const char *name)\n \n static struct branch *new_branch(const char *name)\n {\n-\tunsigned int hc = hc_str(name, strlen(name)) % branch_table_sz;\n+\tunsigned int hc = hc_str(name, strlen(name));\n \tstruct branch *b = lookup_branch(name);\n+\tvoid **pos;\n \n \tif (b)\n \t\tdie(\"Invalid attempt to create duplicate branch: %s\", name);\n@@ -740,13 +769,16 @@ static struct branch *new_branch(const char *name)\n \n \tb = pool_calloc(1, sizeof(struct branch));\n \tb->name = pool_strdup(name);\n-\tb->table_next_branch = branch_table[hc];\n \tb->branch_tree.versions[0].mode = S_IFDIR;\n \tb->branch_tree.versions[1].mode = S_IFDIR;\n \tb->num_notes = 0;\n \tb->active = 0;\n \tb->pack_id = MAX_PACK_ID;\n-\tbranch_table[hc] = b;\n+\tpos = insert_hash(hc, b, &branch_table);\n+\tif (pos) {\n+\t\tb->table_next_branch = *pos;\n+\t\t*pos = b;\n+\t}\n \tbranch_count++;\n \treturn b;\n }\n@@ -956,6 +988,15 @@ static void unkeep_all_packs(void)\n \t}\n }\n \n+static int print_sha1_if_same_pack(struct branch *b, void *cb)\n+{\n+\tconst unsigned int *pack_id = cb;\n+\n+\tif (b->pack_id == *pack_id)\n+\t\tfprintf(pack_edges, \" %s\", sha1_to_hex(b->sha1));\n+\treturn 0;\n+}\n+\n static void end_packfile(void)\n {\n \tstruct packed_git *old_p = pack_data, *new_p;\n@@ -964,8 +1005,6 @@ static void end_packfile(void)\n \tif (object_count) {\n \t\tunsigned char cur_pack_sha1[20];\n \t\tchar *idx_name;\n-\t\tint i;\n-\t\tstruct branch *b;\n \t\tstruct tag *t;\n \n \t\tclose_pack_windows(pack_data);\n@@ -986,12 +1025,7 @@ static void end_packfile(void)\n \t\t/* Print the boundary */\n \t\tif (pack_edges) {\n \t\t\tfprintf(pack_edges, \"%s:\", new_p->pack_name);\n-\t\t\tfor (i = 0; i < branch_table_sz; i++) {\n-\t\t\t\tfor (b = branch_table[i]; b; b = b->table_next_branch) {\n-\t\t\t\t\tif (b->pack_id == pack_id)\n-\t\t\t\t\t\tfprintf(pack_edges, \" %s\", sha1_to_hex(b->sha1));\n-\t\t\t\t}\n-\t\t\t}\n+\t\t\tfor_each_branch(print_sha1_if_same_pack, &pack_id);\n \t\t\tfor (t = first_tag; t; t = t->next_tag) {\n \t\t\t\tif (t->pack_id == pack_id)\n \t\t\t\t\tfprintf(pack_edges, \" %s\", sha1_to_hex(t->sha1));\n@@ -1667,7 +1701,8 @@ static int tree_content_get(\n \treturn 0;\n }\n \n-static int update_branch(struct branch *b)\n+/* 1 means failure; -1 means stop. */\n+static int update_branch(struct branch *b, void *unused)\n {\n \tstatic const char *msg = \"fast-import\";\n \tstruct ref_lock *lock;\n@@ -1678,8 +1713,10 @@ static int update_branch(struct branch *b)\n \tif (read_ref(b->name, old_sha1))\n \t\thashclr(old_sha1);\n \tlock = lock_any_ref_for_update(b->name, old_sha1, 0);\n-\tif (!lock)\n-\t\treturn error(\"Unable to lock %s\", b->name);\n+\tif (!lock) {\n+\t\terror(\"Unable to lock %s\", b->name);\n+\t\treturn 1;\n+\t}\n \tif (!force_update && !is_null_sha1(old_sha1)) {\n \t\tstruct commit *old_cmit, *new_cmit;\n \n@@ -1687,7 +1724,8 @@ static int update_branch(struct branch *b)\n \t\tnew_cmit = lookup_commit_reference_gently(b->sha1, 0);\n \t\tif (!old_cmit || !new_cmit) {\n \t\t\tunlock_ref(lock);\n-\t\t\treturn error(\"Branch %s is missing commits.\", b->name);\n+\t\t\terror(\"Branch %s is missing commits.\", b->name);\n+\t\t\treturn 1;\n \t\t}\n \n \t\tif (!in_merge_bases(old_cmit, &new_cmit, 1)) {\n@@ -1695,23 +1733,19 @@ static int update_branch(struct branch *b)\n \t\t\twarning(\"Not updating %s\"\n \t\t\t\t\" (new tip %s does not contain %s)\",\n \t\t\t\tb->name, sha1_to_hex(b->sha1), sha1_to_hex(old_sha1));\n-\t\t\treturn -1;\n+\t\t\treturn 1;\n \t\t}\n \t}\n-\tif (write_ref_sha1(lock, b->sha1, msg) < 0)\n-\t\treturn error(\"Unable to update %s\", b->name);\n+\tif (write_ref_sha1(lock, b->sha1, msg) < 0) {\n+\t\terror(\"Unable to update %s\", b->name);\n+\t\treturn 1;\n+\t}\n \treturn 0;\n }\n \n static void dump_branches(void)\n {\n-\tunsigned int i;\n-\tstruct branch *b;\n-\n-\tfor (i = 0; i < branch_table_sz; i++) {\n-\t\tfor (b = branch_table[i]; b; b = b->table_next_branch)\n-\t\t\tfailure |= update_branch(b);\n-\t}\n+\tfailure |= for_each_branch(update_branch, NULL);\n }\n \n static void dump_tags(void)\n@@ -3275,7 +3309,7 @@ int main(int argc, const char **argv)\n \talloc_objects(object_entry_alloc);\n \tstrbuf_init(&command_buf, 0);\n \tinit_hash(&atom_table);\n-\tbranch_table = xcalloc(branch_table_sz, sizeof(struct branch*));\n+\tinit_hash(&branch_table);\n \tavail_tree_table = xcalloc(avail_tree_table_sz, sizeof(struct avail_tree_content*));\n \tinit_hash(&object_table);\n \tmarks = pool_calloc(1, sizeof(struct mark_set));\n-- \n1.7.10\n"},{"id":"188954","messageId":"20120411121531.GF19568@burratino","threadId":"26943","inReplyTo":"20120411121259.GB19568@burratino","subject":"[PATCH 4/4] fast-import: use DIV_ROUND_UP","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2012-04-11T12:15:31Z","receivedAt":"2012-04-11T12:15:31Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Date: Mon, 30 May 2011 22:45:43 -0500\n\nfast-import keeps tree structures for reuse in pools arranged by size:\none for trees with 0 entries, one for 8-entry trees, one for 16-entry\ntrees, and so on up to 784-entry trees, plus another pool for larger\ntrees.  Use the DIV_ROUND_UP macro to determine which pool a\ngiven-sized tree belongs in to avoid some confusing bit-twiddling.\n\nSigned-off-by: Jonathan Nieder <jrnieder@gmail.com>\n---\nThanks for reading.\n\n fast-import.c |    4 ++--\n 1 file changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/fast-import.c b/fast-import.c\nindex ebb27006..fc1b549d 100644\n--- a/fast-import.c\n+++ b/fast-import.c\n@@ -785,7 +785,7 @@ static struct branch *new_branch(const char *name)\n \n static unsigned int hc_entries(unsigned int cnt)\n {\n-\tcnt = cnt & 7 ? (cnt / 8) + 1 : cnt / 8;\n+\tcnt = DIV_ROUND_UP(cnt, 8);\n \treturn cnt < avail_tree_table_sz ? cnt : avail_tree_table_sz - 1;\n }\n \n@@ -805,7 +805,7 @@ static struct tree_content *new_tree_content(unsigned int cnt)\n \t\telse\n \t\t\tavail_tree_table[hc] = f->next_avail;\n \t} else {\n-\t\tcnt = cnt & 7 ? ((cnt / 8) + 1) * 8 : cnt;\n+\t\tcnt = DIV_ROUND_UP(cnt, 8) * 8;\n \t\tf = pool_alloc(sizeof(*t) + sizeof(t->entries[0]) * cnt);\n \t\tf->entry_capacity = cnt;\n \t}\n-- \n1.7.10\n"}]}