{"thread":{"id":"27206","subject":"[PATCH] lookup_object(): Speed up 'git gc' by 12%, by reducing hash chain length","startedAt":"2011-04-27T21:35:02Z","lastAt":"2011-05-01T13:21:40Z","messageCount":9,"participants":["Ingo Molnar","Junio C Hamano","Sverre Rabbelier","Shawn Pearce","Avi Kivity"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"166560","messageId":"20110427213502.GA13647@elte.hu","threadId":"27206","inReplyTo":null,"subject":"[PATCH] lookup_object(): Speed up 'git gc' by 12%, by reducing hash chain length","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2011-04-27T21:35:02Z","receivedAt":"2011-04-27T21:35:02Z","isPatch":true,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\nI was looking at the 'git gc' stalled-cycles profile and noticed that \nlookup_object() was the top entry:\n\n aldebaran:~/git> perf record -e stalled-cycles -F 10000 ./git gc \n Counting objects: 32459, done .\n Delta compression using up to 16 threads.\n Compressing objects: 100% (8161/8161), done.\n Writing objects: 100% (32459/32459), done.\n Total 32459 (delta 24077), reused 32459 (delta 24077)\n [ perf record: Woken up 5 times to write data ]\n [ perf record: Captured and wrote 1.199 MB perf.data (~52366 samples) ]\n\n aldebaran:~/git> perf report | head\n # Events: 30K stalled-cycles\n #\n # Overhead     Command          Shared Object                                     Symbol\n # ........  ..........  .....................  .........................................\n #\n    36.36%         git  git                    [.] lookup_object\n     6.55%         git  git                    [.] find_pack_entry_one\n     6.53%         git  libz.so.1.2.5          [.] 0xc416          \n     5.94%         git  libz.so.1.2.5          [.] inflate\n     4.12%         git  [kernel.kallsyms]      [k] do_raw_spin_lock\n\nAnnotated output showed the culprit:\n\n         :              if (!obj_hash)\n         :                      return NULL;\n         :\n         :              i = hashtable_index(sha1);\n         :              while ((obj = obj_hash[i]) != NULL) {\n    4.13 :        498316:       eb 1f                   jmp    498337 <lookup_object+0x47>\n    0.00 :        498318:       0f 1f 84 00 00 00 00    nopl   0x0(%rax,%rax,1)\n    0.00 :        49831f:       00 \n         :                      if (!hashcmp(sha1, obj->sha1))\n    1.48 :        498320:       48 8d 78 04             lea    0x4(%rax),%rdi\n    0.02 :        498324:       4c 89 d6                mov    %r10,%rsi\n    0.00 :        498327:       4c 89 d9                mov    %r11,%rcx\n   26.12 :        49832a:       f3 a6                   repz cmpsb %es:(%rdi),%ds:(%rsi)\n   17.12 :        49832c:       74 14                   je     498342 <lookup_object+0x52>\n         :                              break;\n         :                      i++;\n    6.88 :        49832e:       83 c2 01                add    $0x1,%edx\n         :                      if (i == obj_hash_size)\n         :                              i = 0;\n    2.28 :        498331:       44 39 ca                cmp    %r9d,%edx\n    0.24 :        498334:       0f 44 d3                cmove  %ebx,%edx\n\n\"perf stat --detailed\" shows us the following picture:\n\n Performance counter stats for './git gc':\n\n       3145.596314 task-clock               #    0.877 CPUs utilized          \n             1,760 context-switches         #    0.001 M/sec                  \n               174 CPU-migrations           #    0.000 M/sec                  \n            41,509 page-faults              #    0.013 M/sec                  \n     9,753,859,587 cycles                   #    3.101 GHz                      (22.91%)\n     2,555,944,921 stalled-cycles           #   26.20% of all cycles are idle   (33.89%)\n     8,976,468,086 instructions             #    0.92  insns per cycle        \n                                            #    0.28  stalled cycles per insn  (44.83%)\n     1,782,743,476 branches                 #  566.743 M/sec                    (55.70%)\n        85,045,367 branch-misses            #    4.77% of all branches          (66.54%)\n     1,982,452,996 L1-dcache-loads          #  630.231 M/sec                    (66.18%)\n       152,320,833 L1-dcache-load-misses    #    7.68% of all L1-dcache hits    (55.50%)\n        43,358,073 LLC-loads                #   13.784 M/sec                    (45.33%)\n         2,636,774 LLC-load-misses          #    0.838 M/sec                    (11.50%)\n\n        3.586922714  seconds time elapsed\n\n... so git gc is still fitting into the L1 cache mostly, and it rarely falls \nout of the L2 cache. So CPU execution is stalling processing longish hash \nchains and comparing sha1's.\n\nSo i tried the quick patch below, which just increases the object hash size \nmore aggressively, to 16x of the object count, not the previous 2x sizing.\n\nThe results are (run against the Git repo itself, on ec014ea (\"Git 1.7.5\")):\n\n #\n # Before:\n #\n\n Performance counter stats for './git gc' (10 runs):\n\n       3147.437358 task-clock               #    0.793 CPUs utilized            ( +-  0.18% )\n             1,753 context-switches         #    0.001 M/sec                    ( +-  3.09% )\n               165 CPU-migrations           #    0.000 M/sec                    ( +-  2.86% )\n            42,587 page-faults              #    0.014 M/sec                    ( +-  0.04% )\n    10,041,078,653 cycles                   #    3.190 GHz                      ( +-  0.18% )\n     2,613,923,719 stalled-cycles           #   26.03% of all cycles are idle   ( +-  0.45% )\n     9,110,524,009 instructions             #    0.91  insns per cycle        \n                                            #    0.29  stalled cycles per insn  ( +-  0.03% )\n     1,796,732,369 branches                 #  570.856 M/sec                    ( +-  0.04% )\n        84,828,313 branch-misses            #    4.72% of all branches          ( +-  0.06% )\n\n        3.971525714  seconds time elapsed  ( +-  8.56% )\n\n #\n # After:\n #\n\n Performance counter stats for './git gc' (10 runs):\n\n       2805.034899 task-clock               #    0.757 CPUs utilized            ( +-  0.16% )\n             1,709 context-switches         #    0.001 M/sec                    ( +-  2.51% )\n               169 CPU-migrations           #    0.000 M/sec                    ( +-  1.73% )\n            42,963 page-faults              #    0.015 M/sec                    ( +-  0.23% )\n     8,944,314,899 cycles                   #    3.189 GHz                      ( +-  0.17% )\n     2,118,720,399 stalled-cycles           #   23.69% of all cycles are idle   ( +-  0.52% )\n     9,017,027,059 instructions             #    1.01  insns per cycle        \n                                            #    0.23  stalled cycles per insn  ( +-  0.03% )\n     1,780,388,097 branches                 #  634.712 M/sec                    ( +-  0.04% )\n        76,104,907 branch-misses            #    4.27% of all branches          ( +-  0.07% )\n\n        3.707549437  seconds time elapsed  ( +-  7.13% )\n\nThe takeaway is that stalled cycles dropped by 23%:\n\n     2,613,923,719 stalled-cycles           #   26.03% of all cycles are idle   ( +-  0.45% )\n     2,118,720,399 stalled-cycles           #   23.69% of all cycles are idle   ( +-  0.52% )\n\nAnd total runtime (measured in cycles) decreased by 12.2%:\n\n    10,041,078,653 cycles                   #    3.190 GHz                      ( +-  0.18% )\n     8,944,314,899 cycles                   #    3.189 GHz                      ( +-  0.17% )\n\nElapsed time dropped as well as expected, but measurement noise [last column] \nis high there, due to IO effects.\n\nCache misses are down as well:\n\n # Before:\n\n     1,982,452,996 L1-dcache-loads          #  630.231 M/sec                    (66.18%)\n       152,320,833 L1-dcache-load-misses    #    7.68% of all L1-dcache hits    (55.50%)\n        43,358,073 LLC-loads                #   13.784 M/sec                    (45.33%)\n         2,636,774 LLC-load-misses          #    0.838 M/sec                    (11.50%)\n\n # After:\n\n     1,946,597,133 L1-dcache-loads          #  687.078 M/sec                    (67.61%)\n       125,634,149 L1-dcache-load-misses    #    6.45% of all L1-dcache hits    (56.38%)\n        30,778,323 LLC-loads                #   10.864 M/sec                    (44.40%)\n         2,697,827 LLC-load-misses          #    0.952 M/sec                    (10.94%)\n\nThis is somewhat surprising, the hash table got larger after all. Cachemisses \nwent down probably due to less chain-walking reducing the effective working set \nsize of git gc.\n\nSo oversizing the hash seems to works well for git gc. I tried a 4x and 8x \noversizing as well, it was an improvement but 16x clearly beats it. Larger\nthan 16x seems like overkill.\n\nI guess the hash function itself is as good as it gets:\n\n static unsigned int hashtable_index(const unsigned char *sha1)\n {\n         unsigned int i;\n         memcpy(&i, sha1, sizeof(unsigned int));\n         return i % obj_hash_size;\n }\n\nas sha1's ought to be fairly well distributed. The problem i suspect is that \neven with perfectly random distribution of the hash, there will always be \nsecond, third and higher order chains, which get more and more expensive to \nwalk. So a 2x sized hash table becomes overcrowded.\n\nThanks,\n\n\tIngo\n\nSigned-off-by: Ingo Molnar <mingo@elte.hu>\n\ndiff --git a/object.c b/object.c\nindex 7e1f2bb..b3fe485 100644\n--- a/object.c\n+++ b/object.c\n@@ -91,7 +91,7 @@ struct object *lookup_object(const unsigned char *sha1)\n static void grow_object_hash(void)\n {\n \tint i;\n-\tint new_hash_size = obj_hash_size < 32 ? 32 : 2 * obj_hash_size;\n+\tint new_hash_size = obj_hash_size < 32 ? 32 : 16 * obj_hash_size;\n \tstruct object **new_hash;\n \n \tnew_hash = xcalloc(new_hash_size, sizeof(struct object *));\n@@ -116,7 +116,7 @@ void *create_object(const unsigned char *sha1, int type, void *o)\n \tobj->flags = 0;\n \thashcpy(obj->sha1, sha1);\n \n-\tif (obj_hash_size - 1 <= nr_objs * 2)\n+\tif (obj_hash_size - 1 <= nr_objs * 16)\n \t\tgrow_object_hash();\n \n \tinsert_obj_hash(obj, obj_hash, obj_hash_size);\n"},{"id":"166708","messageId":"20110429062234.GA13608@elte.hu","threadId":"27206","inReplyTo":"20110427213502.GA13647@elte.hu","subject":"Re: [PATCH] lookup_object(): Speed up 'git gc' by 12%, by reducing hash chain length","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2011-04-29T06:22:34Z","receivedAt":"2011-04-29T06:22:34Z","isPatch":true,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\nGot no feedback for this patch - might have been drowned in the hashcmp \ndiscussion :)\n\n\nI tried various levels of object hash spreading factor and 16x seemed like a \ngood one, but i can try a different patch as well if there's other ideas to fix \nthis source of CPU utilization inefficiency.\n\nThanks,\n\n\tIngo\n\n* Ingo Molnar <mingo@elte.hu> wrote:\n\n> I was looking at the 'git gc' stalled-cycles profile and noticed that \n> lookup_object() was the top entry:\n> \n>  aldebaran:~/git> perf record -e stalled-cycles -F 10000 ./git gc \n>  Counting objects: 32459, done .\n>  Delta compression using up to 16 threads.\n>  Compressing objects: 100% (8161/8161), done.\n>  Writing objects: 100% (32459/32459), done.\n>  Total 32459 (delta 24077), reused 32459 (delta 24077)\n>  [ perf record: Woken up 5 times to write data ]\n>  [ perf record: Captured and wrote 1.199 MB perf.data (~52366 samples) ]\n> \n>  aldebaran:~/git> perf report | head\n>  # Events: 30K stalled-cycles\n>  #\n>  # Overhead     Command          Shared Object                                     Symbol\n>  # ........  ..........  .....................  .........................................\n>  #\n>     36.36%         git  git                    [.] lookup_object\n>      6.55%         git  git                    [.] find_pack_entry_one\n>      6.53%         git  libz.so.1.2.5          [.] 0xc416          \n>      5.94%         git  libz.so.1.2.5          [.] inflate\n>      4.12%         git  [kernel.kallsyms]      [k] do_raw_spin_lock\n> \n> Annotated output showed the culprit:\n> \n>          :              if (!obj_hash)\n>          :                      return NULL;\n>          :\n>          :              i = hashtable_index(sha1);\n>          :              while ((obj = obj_hash[i]) != NULL) {\n>     4.13 :        498316:       eb 1f                   jmp    498337 <lookup_object+0x47>\n>     0.00 :        498318:       0f 1f 84 00 00 00 00    nopl   0x0(%rax,%rax,1)\n>     0.00 :        49831f:       00 \n>          :                      if (!hashcmp(sha1, obj->sha1))\n>     1.48 :        498320:       48 8d 78 04             lea    0x4(%rax),%rdi\n>     0.02 :        498324:       4c 89 d6                mov    %r10,%rsi\n>     0.00 :        498327:       4c 89 d9                mov    %r11,%rcx\n>    26.12 :        49832a:       f3 a6                   repz cmpsb %es:(%rdi),%ds:(%rsi)\n>    17.12 :        49832c:       74 14                   je     498342 <lookup_object+0x52>\n>          :                              break;\n>          :                      i++;\n>     6.88 :        49832e:       83 c2 01                add    $0x1,%edx\n>          :                      if (i == obj_hash_size)\n>          :                              i = 0;\n>     2.28 :        498331:       44 39 ca                cmp    %r9d,%edx\n>     0.24 :        498334:       0f 44 d3                cmove  %ebx,%edx\n> \n> \"perf stat --detailed\" shows us the following picture:\n> \n>  Performance counter stats for './git gc':\n> \n>        3145.596314 task-clock               #    0.877 CPUs utilized          \n>              1,760 context-switches         #    0.001 M/sec                  \n>                174 CPU-migrations           #    0.000 M/sec                  \n>             41,509 page-faults              #    0.013 M/sec                  \n>      9,753,859,587 cycles                   #    3.101 GHz                      (22.91%)\n>      2,555,944,921 stalled-cycles           #   26.20% of all cycles are idle   (33.89%)\n>      8,976,468,086 instructions             #    0.92  insns per cycle        \n>                                             #    0.28  stalled cycles per insn  (44.83%)\n>      1,782,743,476 branches                 #  566.743 M/sec                    (55.70%)\n>         85,045,367 branch-misses            #    4.77% of all branches          (66.54%)\n>      1,982,452,996 L1-dcache-loads          #  630.231 M/sec                    (66.18%)\n>        152,320,833 L1-dcache-load-misses    #    7.68% of all L1-dcache hits    (55.50%)\n>         43,358,073 LLC-loads                #   13.784 M/sec                    (45.33%)\n>          2,636,774 LLC-load-misses          #    0.838 M/sec                    (11.50%)\n> \n>         3.586922714  seconds time elapsed\n> \n> ... so git gc is still fitting into the L1 cache mostly, and it rarely falls \n> out of the L2 cache. So CPU execution is stalling processing longish hash \n> chains and comparing sha1's.\n> \n> So i tried the quick patch below, which just increases the object hash size \n> more aggressively, to 16x of the object count, not the previous 2x sizing.\n> \n> The results are (run against the Git repo itself, on ec014ea (\"Git 1.7.5\")):\n> \n>  #\n>  # Before:\n>  #\n> \n>  Performance counter stats for './git gc' (10 runs):\n> \n>        3147.437358 task-clock               #    0.793 CPUs utilized            ( +-  0.18% )\n>              1,753 context-switches         #    0.001 M/sec                    ( +-  3.09% )\n>                165 CPU-migrations           #    0.000 M/sec                    ( +-  2.86% )\n>             42,587 page-faults              #    0.014 M/sec                    ( +-  0.04% )\n>     10,041,078,653 cycles                   #    3.190 GHz                      ( +-  0.18% )\n>      2,613,923,719 stalled-cycles           #   26.03% of all cycles are idle   ( +-  0.45% )\n>      9,110,524,009 instructions             #    0.91  insns per cycle        \n>                                             #    0.29  stalled cycles per insn  ( +-  0.03% )\n>      1,796,732,369 branches                 #  570.856 M/sec                    ( +-  0.04% )\n>         84,828,313 branch-misses            #    4.72% of all branches          ( +-  0.06% )\n> \n>         3.971525714  seconds time elapsed  ( +-  8.56% )\n> \n>  #\n>  # After:\n>  #\n> \n>  Performance counter stats for './git gc' (10 runs):\n> \n>        2805.034899 task-clock               #    0.757 CPUs utilized            ( +-  0.16% )\n>              1,709 context-switches         #    0.001 M/sec                    ( +-  2.51% )\n>                169 CPU-migrations           #    0.000 M/sec                    ( +-  1.73% )\n>             42,963 page-faults              #    0.015 M/sec                    ( +-  0.23% )\n>      8,944,314,899 cycles                   #    3.189 GHz                      ( +-  0.17% )\n>      2,118,720,399 stalled-cycles           #   23.69% of all cycles are idle   ( +-  0.52% )\n>      9,017,027,059 instructions             #    1.01  insns per cycle        \n>                                             #    0.23  stalled cycles per insn  ( +-  0.03% )\n>      1,780,388,097 branches                 #  634.712 M/sec                    ( +-  0.04% )\n>         76,104,907 branch-misses            #    4.27% of all branches          ( +-  0.07% )\n> \n>         3.707549437  seconds time elapsed  ( +-  7.13% )\n> \n> The takeaway is that stalled cycles dropped by 23%:\n> \n>      2,613,923,719 stalled-cycles           #   26.03% of all cycles are idle   ( +-  0.45% )\n>      2,118,720,399 stalled-cycles           #   23.69% of all cycles are idle   ( +-  0.52% )\n> \n> And total runtime (measured in cycles) decreased by 12.2%:\n> \n>     10,041,078,653 cycles                   #    3.190 GHz                      ( +-  0.18% )\n>      8,944,314,899 cycles                   #    3.189 GHz                      ( +-  0.17% )\n> \n> Elapsed time dropped as well as expected, but measurement noise [last column] \n> is high there, due to IO effects.\n> \n> Cache misses are down as well:\n> \n>  # Before:\n> \n>      1,982,452,996 L1-dcache-loads          #  630.231 M/sec                    (66.18%)\n>        152,320,833 L1-dcache-load-misses    #    7.68% of all L1-dcache hits    (55.50%)\n>         43,358,073 LLC-loads                #   13.784 M/sec                    (45.33%)\n>          2,636,774 LLC-load-misses          #    0.838 M/sec                    (11.50%)\n> \n>  # After:\n> \n>      1,946,597,133 L1-dcache-loads          #  687.078 M/sec                    (67.61%)\n>        125,634,149 L1-dcache-load-misses    #    6.45% of all L1-dcache hits    (56.38%)\n>         30,778,323 LLC-loads                #   10.864 M/sec                    (44.40%)\n>          2,697,827 LLC-load-misses          #    0.952 M/sec                    (10.94%)\n> \n> This is somewhat surprising, the hash table got larger after all. Cachemisses \n> went down probably due to less chain-walking reducing the effective working set \n> size of git gc.\n> \n> So oversizing the hash seems to works well for git gc. I tried a 4x and 8x \n> oversizing as well, it was an improvement but 16x clearly beats it. Larger\n> than 16x seems like overkill.\n> \n> I guess the hash function itself is as good as it gets:\n> \n>  static unsigned int hashtable_index(const unsigned char *sha1)\n>  {\n>          unsigned int i;\n>          memcpy(&i, sha1, sizeof(unsigned int));\n>          return i % obj_hash_size;\n>  }\n> \n> as sha1's ought to be fairly well distributed. The problem i suspect is that \n> even with perfectly random distribution of the hash, there will always be \n> second, third and higher order chains, which get more and more expensive to \n> walk. So a 2x sized hash table becomes overcrowded.\n> \n> Thanks,\n> \n> \tIngo\n> \n> Signed-off-by: Ingo Molnar <mingo@elte.hu>\n> \n> diff --git a/object.c b/object.c\n> index 7e1f2bb..b3fe485 100644\n> --- a/object.c\n> +++ b/object.c\n> @@ -91,7 +91,7 @@ struct object *lookup_object(const unsigned char *sha1)\n>  static void grow_object_hash(void)\n>  {\n>  \tint i;\n> -\tint new_hash_size = obj_hash_size < 32 ? 32 : 2 * obj_hash_size;\n> +\tint new_hash_size = obj_hash_size < 32 ? 32 : 16 * obj_hash_size;\n>  \tstruct object **new_hash;\n>  \n>  \tnew_hash = xcalloc(new_hash_size, sizeof(struct object *));\n> @@ -116,7 +116,7 @@ void *create_object(const unsigned char *sha1, int type, void *o)\n>  \tobj->flags = 0;\n>  \thashcpy(obj->sha1, sha1);\n>  \n> -\tif (obj_hash_size - 1 <= nr_objs * 2)\n> +\tif (obj_hash_size - 1 <= nr_objs * 16)\n>  \t\tgrow_object_hash();\n>  \n>  \tinsert_obj_hash(obj, obj_hash, obj_hash_size);\n\n-- \nThanks,\n\n\tIngo\n"},{"id":"166711","messageId":"7vtydh1r3q.fsf@alter.siamese.dyndns.org","threadId":"27206","inReplyTo":"20110427213502.GA13647@elte.hu","subject":"Re: [PATCH] lookup_object(): Speed up 'git gc' by 12%, by reducing hash chain length","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-04-29T06:58:17Z","receivedAt":"2011-04-29T06:58:17Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ingo Molnar <mingo@elte.hu> writes:\n\n> diff --git a/object.c b/object.c\n> index 7e1f2bb..b3fe485 100644\n> --- a/object.c\n> +++ b/object.c\n> @@ -91,7 +91,7 @@ struct object *lookup_object(const unsigned char *sha1)\n>  static void grow_object_hash(void)\n>  {\n>  \tint i;\n> -\tint new_hash_size = obj_hash_size < 32 ? 32 : 2 * obj_hash_size;\n> +\tint new_hash_size = obj_hash_size < 32 ? 32 : 16 * obj_hash_size;\n>  \tstruct object **new_hash;\n>  \n>  \tnew_hash = xcalloc(new_hash_size, sizeof(struct object *));\n> @@ -116,7 +116,7 @@ void *create_object(const unsigned char *sha1, int type, void *o)\n>  \tobj->flags = 0;\n>  \thashcpy(obj->sha1, sha1);\n>  \n> -\tif (obj_hash_size - 1 <= nr_objs * 2)\n> +\tif (obj_hash_size - 1 <= nr_objs * 16)\n>  \t\tgrow_object_hash();\n>  \n>  \tinsert_obj_hash(obj, obj_hash, obj_hash_size);\n\nShawn was telling me about this exact topic a few months ago, and I do\nagree that object hash grows too slowly when you need to slurp in many\nobjects.\n\nA few random thoughts, some are related and others are unrelated to what\nyour patch does:\n\n - We start out from a tiny table of 32 entries.  Would it make things\n   noticeably worse if we start with a larger table for a workload that\n   touch only a few dozen objects?  How about starting from a table with\n   say 4 pages worth of pointers, or something?  Note that this is not\n   about helping the case with near full-walk.\n\n - I agree x2 is growing the table too slowly, but at the same time, I do\n   not think x16 is growing fast enough, if you will end up slurping\n   millions of objects.  You would still need to rehash 5 times (maybe 4,\n   I cannot count).\n\n   Worse yet, the later rehash costs proportionally more (IOW having to\n   rehash 5 times is not just 25% more expensive than having to rehash 4\n   times).\n\n - If we grow the table too fast, wouldn't it make the largest table we\n   could use smaller?  When we try to grow a large but crowded table by\n   x2, we may be able to get enough core to rehash, but we may not be able\n   to allocate x16 such an already large table.\n\nI have this hunch that the workloads that truly require to hold huge\nnumber of objects are limited, and we can enumerate them relatively\neasily.  The callchain from gc to repack to pack-objects is one.  The\ncodepath in pack-objects that is called from \"repack -a -d\" should be able\nto guess that it needs to slurp everything from the fact that there is no\nnegative ref given in the revision walking machinery.  It also should be\nable to guess if the repository has large number of objects by looking at\nthe existing pack .idx files (they record the number of objects the\ncorresponding .pack files contain in a way that is cheap to read).\n\nIt might make sense to give an explicit hit to grow_object_hash() in such\na case (i.e. the caller e.g. pack-objects sets a flag for it to notice),\nand have grow_object_hash() immediately jump to a huge hash size.\n"},{"id":"166713","messageId":"20110429072604.GA16371@elte.hu","threadId":"27206","inReplyTo":"7vtydh1r3q.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] lookup_object(): Speed up 'git gc' by 12%, by reducing hash chain length","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2011-04-29T07:26:04Z","receivedAt":"2011-04-29T07:26:04Z","isPatch":true,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Junio C Hamano <gitster@pobox.com> wrote:\n\n> Ingo Molnar <mingo@elte.hu> writes:\n> \n> > diff --git a/object.c b/object.c\n> > index 7e1f2bb..b3fe485 100644\n> > --- a/object.c\n> > +++ b/object.c\n> > @@ -91,7 +91,7 @@ struct object *lookup_object(const unsigned char *sha1)\n> >  static void grow_object_hash(void)\n> >  {\n> >  \tint i;\n> > -\tint new_hash_size = obj_hash_size < 32 ? 32 : 2 * obj_hash_size;\n> > +\tint new_hash_size = obj_hash_size < 32 ? 32 : 16 * obj_hash_size;\n> >  \tstruct object **new_hash;\n> >  \n> >  \tnew_hash = xcalloc(new_hash_size, sizeof(struct object *));\n> > @@ -116,7 +116,7 @@ void *create_object(const unsigned char *sha1, int type, void *o)\n> >  \tobj->flags = 0;\n> >  \thashcpy(obj->sha1, sha1);\n> >  \n> > -\tif (obj_hash_size - 1 <= nr_objs * 2)\n> > +\tif (obj_hash_size - 1 <= nr_objs * 16)\n> >  \t\tgrow_object_hash();\n> >  \n> >  \tinsert_obj_hash(obj, obj_hash, obj_hash_size);\n> \n> Shawn was telling me about this exact topic a few months ago, and I do\n> agree that object hash grows too slowly when you need to slurp in many\n> objects.\n\nI think the main effect might not be the rate of growth and reduced overhead of \nreallocating and reconstructing the hash 4-6 times, but the *spread* of objects \nwithin the hash table - i.e. the maximum (i.e. optimal) size of the hash.\n\nIn a git gc run the hash grows to the max very quickly, then 99% of execution \ntime is spent with that optimally sized hash - so growth rate per se does not \nmatter much. (it might matter in other usecases)\n\nFind below a debug patch i use to run with a configurable spread.\n\nNote, i just ran the patch on a different system and there the effect was much \nless pronounced. So i'd prefer independent confirmation as well that it speeds \nup things for others as well.\n\nI'll run more numbers - maybe we are just very sensitive to the exact layout of \nthe object hash and a 16x spread created a different, more optimal layout.\n\nThanks,\n\n\tIngo\n\n---\n\n git.c    |    6 ++++++\n object.c |    5 +++--\n object.h |    1 +\n 3 files changed, 10 insertions(+), 2 deletions(-)\n\ndiff --git a/git.c b/git.c\nindex 4b7dbfa..4c59316 100644\n--- a/git.c\n+++ b/git.c\n@@ -4,6 +4,7 @@\n #include \"help.h\"\n #include \"quote.h\"\n #include \"run-command.h\"\n+#include \"object.h\"\n \n const char git_usage_string[] =\n \t\"git [--version] [--exec-path[=<path>]] [--html-path]\\n\"\n@@ -97,6 +98,11 @@ static int handle_options(const char ***argv, int *argc, int *envchanged)\n \t\t\texit(0);\n \t\t} else if (!strcmp(cmd, \"-p\") || !strcmp(cmd, \"--paginate\")) {\n \t\t\tuse_pager = 1;\n+\t\t} else if (!strcmp(cmd, \"--object-hash-spread\")) {\n+\t\t\tobject_hash_spread = atol((*argv)[1]);\n+\t\t\tprintf(\"object hash spread: %d\\n\", object_hash_spread);\n+\t\t\t(*argv)++;\n+\t\t\t(*argc)--;\n \t\t} else if (!strcmp(cmd, \"--no-pager\")) {\n \t\t\tuse_pager = 0;\n \t\t\tif (envchanged)\ndiff --git a/object.c b/object.c\nindex 7e1f2bb..3d16a8a 100644\n--- a/object.c\n+++ b/object.c\n@@ -7,6 +7,7 @@\n \n static struct object **obj_hash;\n static int nr_objs, obj_hash_size;\n+int object_hash_spread = 2;\n \n unsigned int get_max_object_index(void)\n {\n@@ -91,7 +92,7 @@ struct object *lookup_object(const unsigned char *sha1)\n static void grow_object_hash(void)\n {\n \tint i;\n-\tint new_hash_size = obj_hash_size < 32 ? 32 : 2 * obj_hash_size;\n+\tint new_hash_size = obj_hash_size < 32 ? 32 : object_hash_spread * obj_hash_size;\n \tstruct object **new_hash;\n \n \tnew_hash = xcalloc(new_hash_size, sizeof(struct object *));\n@@ -116,7 +117,7 @@ void *create_object(const unsigned char *sha1, int type, void *o)\n \tobj->flags = 0;\n \thashcpy(obj->sha1, sha1);\n \n-\tif (obj_hash_size - 1 <= nr_objs * 2)\n+\tif (obj_hash_size - 1 <= nr_objs * object_hash_spread)\n \t\tgrow_object_hash();\n \n \tinsert_obj_hash(obj, obj_hash, obj_hash_size);\ndiff --git a/object.h b/object.h\nindex b6618d9..180a6c1 100644\n--- a/object.h\n+++ b/object.h\n@@ -75,5 +75,6 @@ int object_list_contains(struct object_list *list, struct object *obj);\n void add_object_array(struct object *obj, const char *name, struct object_array *array);\n void add_object_array_with_mode(struct object *obj, const char *name, struct object_array *array, unsigned mode);\n void object_array_remove_duplicates(struct object_array *);\n+extern int object_hash_spread;\n \n #endif /* OBJECT_H */\n"},{"id":"166714","messageId":"20110429073825.GA16941@elte.hu","threadId":"27206","inReplyTo":"20110429072604.GA16371@elte.hu","subject":"Re: [PATCH] lookup_object(): Speed up 'git gc' by 12%, by reducing hash chain length","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2011-04-29T07:38:25Z","receivedAt":"2011-04-29T07:38:25Z","isPatch":true,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Ingo Molnar <mingo@elte.hu> wrote:\n\n> Find below a debug patch i use to run with a configurable spread.\n> \n> Note, i just ran the patch on a different system and there the effect was \n> much less pronounced. So i'd prefer independent confirmation as well that it \n> speeds up things for others as well.\n> \n> I'll run more numbers - maybe we are just very sensitive to the exact layout \n> of the object hash and a 16x spread created a different, more optimal layout.\n\nHere are those numbers:\n\n $ for ((size=2; size<24; size++)); do printf \"%5d: \" $size; perf stat -e instructions:u -e cycles:u -e task-clock --sync --repeat 10 ./git --object-hash-spread $size gc 2>&1 | grep cycles; done \n\n    2:      9,362,801,669 cycles:u                 #    2.982 GHz                      ( +-  0.25% )\n    3:      9,464,946,158 cycles:u                 #    2.993 GHz                      ( +-  1.17% )\n    4:      9,382,214,358 cycles:u                 #    2.981 GHz                      ( +-  0.26% )\n    5:      9,373,537,954 cycles:u                 #    2.986 GHz                      ( +-  0.24% )\n    6:      9,492,635,404 cycles:u                 #    2.988 GHz                      ( +-  1.25% )\n    7:      9,427,037,835 cycles:u                 #    2.982 GHz                      ( +-  0.19% )\n    8:      9,311,764,604 cycles:u                 #    2.987 GHz                      ( +-  0.23% )\n    9:      9,384,331,920 cycles:u                 #    2.985 GHz                      ( +-  0.27% )\n   10:      9,388,460,044 cycles:u                 #    2.983 GHz                      ( +-  0.31% )\n   11:      9,374,380,165 cycles:u                 #    2.984 GHz                      ( +-  0.25% )\n   12:      9,417,466,827 cycles:u                 #    2.984 GHz                      ( +-  0.27% )\n   13:      9,348,550,619 cycles:u                 #    2.982 GHz                      ( +-  0.12% )\n   14:      9,369,435,508 cycles:u                 #    2.982 GHz                      ( +-  0.31% )\n   15:      9,361,127,598 cycles:u                 #    2.983 GHz                      ( +-  0.27% )\n   16:      9,402,077,866 cycles:u                 #    2.987 GHz                      ( +-  0.20% )\n   17:      9,390,950,850 cycles:u                 #    2.985 GHz                      ( +-  0.27% )\n   18:      9,355,126,542 cycles:u                 #    2.986 GHz                      ( +-  0.30% )\n   19:      9,357,143,371 cycles:u                 #    2.974 GHz                      ( +-  0.33% )\n   20:      9,372,977,607 cycles:u                 #    2.985 GHz                      ( +-  0.34% )\n   21:      9,355,406,722 cycles:u                 #    2.985 GHz                      ( +-  0.45% )\n   22:      9,342,730,882 cycles:u                 #    2.982 GHz                      ( +-  0.31% )\n   23:      9,372,321,792 cycles:u                 #    2.982 GHz                      ( +-  0.28% )\n\nThey are utterly unconvincing - there seems to be no improvement, it's all \nwithin noise.\n\nThanks,\n\n\tIngo\n"},{"id":"166715","messageId":"BANLkTinGn0WFNm805PeWuTp+71yby1ySNw@mail.gmail.com","threadId":"27206","inReplyTo":"20110429073825.GA16941@elte.hu","subject":"Re: [PATCH] lookup_object(): Speed up 'git gc' by 12%, by reducing hash chain length","fromName":"Sverre Rabbelier","fromEmail":"srabbelier@gmail.com","sentAt":"2011-04-29T07:46:09Z","receivedAt":"2011-04-29T07:46:09Z","isPatch":true,"sender":{"key":"srabbelier@gmail.com","avatar":"https://avatars.githubusercontent.com/u/3098?v=4"},"body":"Heya,\n\nOn Fri, Apr 29, 2011 at 09:38, Ingo Molnar <mingo@elte.hu> wrote:\n>   16:      9,402,077,866 cycles:u                 #    2.987 GHz                      ( +-  0.20% )\n>\n> They are utterly unconvincing - there seems to be no improvement, it's all\n> within noise.\n\nIs this in a different repository from the one you ran the numbers on\ninitially, or did something else change to negate that 12.2% decrease?\n\n-- \nCheers,\n\nSverre Rabbelier\n"},{"id":"166726","messageId":"20110429095045.GA22919@elte.hu","threadId":"27206","inReplyTo":"BANLkTinGn0WFNm805PeWuTp+71yby1ySNw@mail.gmail.com","subject":"Re: [PATCH] lookup_object(): Speed up 'git gc' by 12%, by reducing hash chain length","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2011-04-29T09:50:45Z","receivedAt":"2011-04-29T09:50:45Z","isPatch":true,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Sverre Rabbelier <srabbelier@gmail.com> wrote:\n\n> Heya,\n> \n> On Fri, Apr 29, 2011 at 09:38, Ingo Molnar <mingo@elte.hu> wrote:\n> >   16:      9,402,077,866 cycles:u                 #    2.987 GHz                      ( +-  0.20% )\n> >\n> > They are utterly unconvincing - there seems to be no improvement, it's all\n> > within noise.\n> \n> Is this in a different repository from the one you ran the numbers on\n> initially, or did something else change to negate that 12.2% decrease?\n\nYes, a newer Git repository with more objects in it.\n\nThanks,\n\n\tIngo\n"},{"id":"166756","messageId":"BANLkTinKCmaAY_qrdvfW78zHCfJ6rftgZQ@mail.gmail.com","threadId":"27206","inReplyTo":"7vtydh1r3q.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] lookup_object(): Speed up 'git gc' by 12%, by reducing hash chain length","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2011-04-29T16:57:55Z","receivedAt":"2011-04-29T16:57:55Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"On Thu, Apr 28, 2011 at 23:58, Junio C Hamano <gitster@pobox.com> wrote:\n> Ingo Molnar <mingo@elte.hu> writes:\n>\n>> diff --git a/object.c b/object.c\n>> index 7e1f2bb..b3fe485 100644\n>> --- a/object.c\n>> +++ b/object.c\n>> @@ -91,7 +91,7 @@ struct object *lookup_object(const unsigned char *sha1)\n>>  static void grow_object_hash(void)\n>>  {\n>>       int i;\n>> -     int new_hash_size = obj_hash_size < 32 ? 32 : 2 * obj_hash_size;\n>> +     int new_hash_size = obj_hash_size < 32 ? 32 : 16 * obj_hash_size;\n>>       struct object **new_hash;\n>\n> Shawn was telling me about this exact topic a few months ago, and I do\n> agree that object hash grows too slowly when you need to slurp in many\n> objects.\n\nMy experience in JGit with this data structure isn't directly\nrepeatable in C Git. In Java I am battling more than just telling the\ncompiler what assembly instructions to emit. :-)\n\nThe table starts out too small, yes. JGit now has two different table\nrepresentations; one allocates at 2048 entries initially. With a load\nfactor of 50% (matches current C Git code before Ingo's x16 patch), we\nfit 1024 objects before doubling in size. Within a hash chain JGit's\nhashcmp() function evaluates like this:\n\n  !memcmp(a + 4, b + 4, 16) && memcmp(a, b, 4)\n\nbecause the 1st word was already used as the hash index. This does\nseem to help break away from a non-match quickly. But remember, this\nis in Java where some stuff is pretty damn costly. A good x86 chip and\na halfway decent C compiler might be penalized with this variant of\nhashcmp(), I don't know.\n\n\nOur second table in JGit is very different from what C Git uses... but\nit works better for the purpose we are discussing. We extended our\nequivalent of \"struct object\" to have a chained \"struct object *next\"\nfield within the object itself, rather than using the table to contain\nthe chain. This does limit the object to being placed into only one\nobject hashtable, but this isn't actually a problem for either\nimplementation. The entire point of struct object and this table in\nobject.c is to have only one of them for the process.\n\nThe table is actually a variable sized array, similar to dynamic\nhashing. There is a directory array of 1024 entries that points to\nsegment arrays; each segment array is 2048 struct object* entries.\nGrowing the array is just a matter of malloc(sizeof(struct object*) *\n2048) and linking it into the next free slot of the directory array.\nThis avoids needing to grow the array and pay memory management\npenalties associated with dropping the old one and picking up the new\none. glibc malloc/free might handle this workload OK, the Java GC\ndidn't so we had to use this more complex table. The table still\ndoubles in size, so during the 2nd grow we have to malloc 2 segment\narrays, 3rd grow we malloc 4 segment arrays, 4th grow we malloc 8\nsegment arrays.\n\nSearching in the table is a matter of taking the first 4 bytes of the\nSHA-1, applying a mask to find which index of the directory array\nholds the relevant segment array to scan. The higher bits get used to\naccess the index in the segment, and then the hash chain is walked\nusing a classical singly linked list:\n\n  unsigned int h = *((unsigned int*)obj_sha1);\n  V obj = directory[h & mask][h >>> SEGMENT_SHIFT];\n  for (; obj; obj = obj->next) {\n    if (!hashcmp(obj->sha1, obj_sha1))\n      return obj;\n\nWith this approach we run the table at 100% capacity, which means the\ntable is much smaller. Its approximately only 1 segment entry per\nobject. But each object is 1 pointer larger. For 1,886,362 objects,\nthis approach wastes 200,000 pointers, even though each object has a\n\"next\" pointer field within it. This is because the table doubling\nwith a 50% load factor has to grow to 4,194,304 pointers to store\n1,886,362 objects. That's wasting 2,307,942 pointers.\n\nA nice thing about the table is, it grows in small allocation bursts\nand doesn't need to find 32 MiB of contiguous heap. Again this may not\nmatter much in a short-lived C process that has a relatively clean\nheap. It matters a lot in a Java process that has been running for a\nwhile and whose heap is pretty fragmented. Its also nice that the\nolder part of the table remains with us. We reuse the old segments as\nwe rehash objects on the chain. The rehashing is also very efficient,\nwe only need to inspect 1 additional bit on each object in the chain\nto determine if it stays in the old segment, or moves to the newly\nallocated sister segment.\n\n\nAround this same time I did look at the chain lengths. The repository\nin question was linux-2.6, but from around January 2011:\n\n------\nAs far as chain lengths go, we're not that bad.\n\nHere is the raw data. Objects is the number of items in the table at\nthe end, table is the size of the obj_hash array, wasted is the\ndifference. A hit is a successful get() returning an object, a miss is\na get that returned null and later turns into an insert. The number of\ncalls on chain lengths above 18 falls off fast so I elided it out.\nWith a 50% load factor, most operations have shorter than 7 items in\ntheir chain. A wide majority are below 2.\n\nobjects: 1886362\ntable: 4194304\n (wasted 2307942)\nchains (hit):\n length   0 : 42396217 get calls\n length   1 : 13675300 get calls\n length   2 : 6756795 get calls\n length   3 : 3759100 get calls\n length   4 : 2213449 get calls\n length   5 : 1413852 get calls\n length   6 : 1046289 get calls\n length   7 : 812226 get calls\n length   8 : 596076 get calls\n length   9 : 529995 get calls\n length  10 : 357039 get calls\n length  11 : 321895 get calls\n length  12 : 261752 get calls\n length  13 : 162623 get calls\n length  14 : 163727 get calls\n length  15 : 112538 get calls\n length  16 : 78401 get calls\n length  17 : 103203 get calls\n length  18 : 81563 get calls\n ...\n length >63 : 11553 get calls\n\nchains (miss):\n length   0 : 872894 get calls\n length   1 : 345177 get calls\n length   2 : 187751 get calls\n length   3 : 117402 get calls\n length   4 : 78825 get calls\n length   5 : 55710 get calls\n length   6 : 41359 get calls\n length   7 : 31547 get calls\n length   8 : 24517 get calls\n length   9 : 19507 get calls\n length  10 : 15565 get calls\n length  11 : 12767 get calls\n length  12 : 10550 get calls\n length  13 : 8895 get calls\n length  14 : 7573 get calls\n length  15 : 6382 get calls\n length  16 : 5542 get calls\n length  17 : 4847 get calls\n length  18 : 4162 get calls\n ...\n length >63 : 1096 get calls\n------\n\nI unfortunately didn't rerun the chain data with the newer table\ndesign. Our goals weren't to reduce chain length, it was to reduce\nmemory management overheads associated with using the table in Java.\nWe succeeded there.\n\n-- \nShawn.\n"},{"id":"166816","messageId":"4DBD5E64.507@redhat.com","threadId":"27206","inReplyTo":"20110427213502.GA13647@elte.hu","subject":"Re: [PATCH] lookup_object(): Speed up 'git gc' by 12%, by reducing hash chain length","fromName":"Avi Kivity","fromEmail":"avi@redhat.com","sentAt":"2011-05-01T13:21:40Z","receivedAt":"2011-05-01T13:21:40Z","isPatch":true,"sender":{"key":"avi@redhat.com","avatar":null},"body":"On 04/28/2011 12:35 AM, Ingo Molnar wrote:\n>           :              while ((obj = obj_hash[i]) != NULL) {\n>      4.13 :        498316:       eb 1f                   jmp    498337<lookup_object+0x47>\n>      0.00 :        498318:       0f 1f 84 00 00 00 00    nopl   0x0(%rax,%rax,1)\n>      0.00 :        49831f:       00\n>           :                      if (!hashcmp(sha1, obj->sha1))\n>      1.48 :        498320:       48 8d 78 04             lea    0x4(%rax),%rdi\n>      0.02 :        498324:       4c 89 d6                mov    %r10,%rsi\n>      0.00 :        498327:       4c 89 d9                mov    %r11,%rcx\n>     26.12 :        49832a:       f3 a6                   repz cmpsb %es:(%rdi),%ds:(%rsi)\n>     17.12 :        49832c:       74 14                   je     498342<lookup_object+0x52>\n>           :                              break;\n\nrep cmps can be very slow on some machines, and in particular, rep cmpsb \nis optimized for really small strings (the tail of a larger rep cmps[lq] \nrun).\n\nI think that if you'll replace hashcmp() by something like\n\nstatic inline bool hashcmp(const unsigned char *sha1, const unsigned \nchar *sha2)\n{\n      unsigned long cmp;\n\n      cmp = *(uint64_t *)sha1 ^ *(unint64_t *)sha2;\n      cmp |= *(uint64_t *)(sha1 + 8) ^ *(unint64_t *)(sha2 + 8);\n      cmp |= *(uint32_t *)(sha1 + 16) ^ *(unint32_t *)(sha2 + 16);\n      return cmp == 0;\n}\n\nYou'll see much better results.\n\nOf course this only works in general if the hashes are aligned.\n\n-- \nerror compiling committee.c: too many arguments to function\n"}]}