{"thread":{"id":"5531","subject":"{RFC/PATCH] micro-optimize get_sha1_hex()","startedAt":"2006-09-09T21:55:09Z","lastAt":"2006-09-10T00:53:14Z","messageCount":4,"participants":["Junio C Hamano","Jeff Garzik","Linus Torvalds"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"26654","messageId":"7vzmd8vh6q.fsf@assigned-by-dhcp.cox.net","threadId":"5531","inReplyTo":null,"subject":"{RFC/PATCH] micro-optimize get_sha1_hex()","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-09-09T21:55:09Z","receivedAt":"2006-09-09T21:55:09Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"I was profiling 'git-rev-list v2.16.12..', because I suspected\ninsert_by_date() might be expensive (the function inserts into\nsingly-linked ordered list, so the data structure has to become\narray based to allow optimization).  But profiling showed it was\nnot the bottleneck.  Probably because the kernel history is not\nthat bushy and we do not have too many \"active\" heads during\ntraversal.\n\nBut I noticed something else.\n\nFlat profile:\n\nEach sample counts as 0.01 seconds.\n  %   cumulative   self              self     total           \n time   seconds   seconds    calls  ms/call  ms/call  name    \n 21.52      0.17     0.17  2800320     0.00     0.00  hexval\n 15.19      0.29     0.12    70008     0.00     0.00  get_sha1_hex\n 15.19      0.41     0.12    70008     0.00     0.00  lookup_object\n 15.19      0.53     0.12    68495     0.00     0.00  find_pack_entry_one\n 11.39      0.62     0.09   198667     0.00     0.00  insert_obj_hash\n  7.60      0.68     0.06    34675     0.00     0.00  unpack_object_header_gently\n  3.80      0.71     0.03    33819     0.00     0.02  parse_commit_buffer\n  1.27      0.72     0.01   103822     0.00     0.00  commit_list_insert\n  1.27      0.73     0.01    67640     0.00     0.00  prepare_packed_git\n  1.27      0.74     0.01    67611     0.00     0.00  created_object\n  1.27      0.75     0.01    33820     0.00     0.00  use_packed_git\n  1.27      0.76     0.01    33819     0.00     0.00  lookup_tree\n  1.27      0.77     0.01        1    10.00    10.00  prepare_packed_git_one\n  1.27      0.78     0.01                             parse_tree_indirect\n  1.27      0.79     0.01                             verify_filename\n  ...\n\nThe attached brings get_sha1_hex() down from 15.19% to 5.41%,\nbut I feel we should be able to do better.\n\nIs this barking up the wrong tree?  Or did I pick a good target\nbut the shooter wasn't skilled enough?\n\n\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 428d791..00aa364 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -26,26 +26,30 @@ const unsigned char null_sha1[20];\n \n static unsigned int sha1_file_open_flag = O_NOATIME;\n \n-static unsigned hexval(char c)\n-{\n-\tif (c >= '0' && c <= '9')\n-\t\treturn c - '0';\n-\tif (c >= 'a' && c <= 'f')\n-\t\treturn c - 'a' + 10;\n-\tif (c >= 'A' && c <= 'F')\n-\t\treturn c - 'A' + 10;\n-\treturn ~0;\n-}\n+static const unsigned char hexval[] = {\n+\t  0,   1,   2,   3,    4,   5,   6,   7, /* 30-37 */\n+\t  8,   9, 255, 255,  255, 255, 255, 255, /* 38-3F */\n+\t255,  10,  11,  12,   13,  14,  15, 255, /* 40-47 */\n+\t255, 255, 255, 255,  255, 255, 255, 255, /* 48-4F */\n+\t255, 255, 255, 255,  255, 255, 255, 255, /* 50-57 */\n+\t255, 255, 255, 255,  255, 255, 255, 255, /* 58-5F */\n+\t255,  10,  11,  12,   13,  14,  15, 255, /* 60-67 */\n+};\n \n int get_sha1_hex(const char *hex, unsigned char *sha1)\n {\n \tint i;\n \tfor (i = 0; i < 20; i++) {\n-\t\tunsigned int val = (hexval(hex[0]) << 4) | hexval(hex[1]);\n-\t\tif (val & ~0xff)\n+\t\tunsigned int v, w, val;\n+\t\tv = *hex++;\n+\t\tif ((v < '0') || ('f' < v) ||\n+\t\t    ((v = hexval[v-'0']) == 255))\n+\t\t\treturn -1;\n+\t\tw = *hex++;\n+\t\tif ((w < '0') || ('f' < w) ||\n+\t\t    ((w = hexval[w-'0']) == 255))\n \t\t\treturn -1;\n-\t\t*sha1++ = val;\n-\t\thex += 2;\n+\t\t*sha1++ = (v << 4) | w;\n \t}\n \treturn 0;\n }\n"},{"id":"26657","messageId":"45034143.4050308@garzik.org","threadId":"5531","inReplyTo":"7vzmd8vh6q.fsf@assigned-by-dhcp.cox.net","subject":"Re: {RFC/PATCH] micro-optimize get_sha1_hex()","fromName":"Jeff Garzik","fromEmail":"jeff@garzik.org","sentAt":"2006-09-09T22:33:39Z","receivedAt":"2006-09-09T22:33:39Z","isPatch":false,"sender":{"key":"jeff@garzik.org","avatar":null},"body":"Junio C Hamano wrote:\n>  int get_sha1_hex(const char *hex, unsigned char *sha1)\n>  {\n>  \tint i;\n>  \tfor (i = 0; i < 20; i++) {\n> -\t\tunsigned int val = (hexval(hex[0]) << 4) | hexval(hex[1]);\n> -\t\tif (val & ~0xff)\n> +\t\tunsigned int v, w, val;\n> +\t\tv = *hex++;\n> +\t\tif ((v < '0') || ('f' < v) ||\n> +\t\t    ((v = hexval[v-'0']) == 255))\n> +\t\t\treturn -1;\n> +\t\tw = *hex++;\n> +\t\tif ((w < '0') || ('f' < w) ||\n> +\t\t    ((w = hexval[w-'0']) == 255))\n>  \t\t\treturn -1;\n> -\t\t*sha1++ = val;\n> -\t\thex += 2;\n> +\t\t*sha1++ = (v << 4) | w;\n\nWhy not just make the table include the range of all possible \ncharacters?  That would eliminate some comparisons and subtractions \nagainst '0'.\n\nThe end result would look more like the current (unpatched) form, except \nwith a function replaced by the table.\n\n\tJeff\n"},{"id":"26659","messageId":"Pine.LNX.4.64.0609091639110.27779@g5.osdl.org","threadId":"5531","inReplyTo":"7vzmd8vh6q.fsf@assigned-by-dhcp.cox.net","subject":"Re: {RFC/PATCH] micro-optimize get_sha1_hex()","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-09-10T00:06:41Z","receivedAt":"2006-09-10T00:06:41Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 9 Sep 2006, Junio C Hamano wrote:\n>\n> I was profiling 'git-rev-list v2.16.12..', because I suspected\n> insert_by_date() might be expensive (the function inserts into\n> singly-linked ordered list, so the data structure has to become\n> array based to allow optimization).\n\nI _suspect_ that you profiled using \"gprof\" and the \"-pg\" flag to \nthe compiler?\n\nThe thing is, that generates almost totally bogus profiles. It makes \nsimple function calls look extremely - and unrealistically - expensive, \nbecause the profiling code itself adds lots of overhead, and it then ends \nup showing on the tick-based profile too in a way that it wouldn't show \nin real life.\n\nIt tends to be much better to profile unmodified binaries using \n\"oprofile\", which doesn't end up giving the exact number of calls, but \nwhere the time-based profiling is a _lot_ more reliable.\n\nThat said, clearly \"hexval()\" can be optimized, and it's quite possible \nthat it would show up even in oprofile data too.\n\n> The attached brings get_sha1_hex() down from 15.19% to 5.41%,\n> but I feel we should be able to do better.\n\nI doubt it's 5% in real life, but your optimization looks fine to me.\n\nYou can make it even _more_ optimized by not even bothering to test at \neach point, but just inlining hexval(), and making it a single array \nlookup. The point being that if you get -1 for _either_ of the two \nlookups, since we shift them and or them together, the end result will be \ninvalid, and you only need to _test_ once.\n\nSo this patch should generate much better code, where the inner loop is \nsomething like\n\n<get_sha1_hex+16>:\n\tadd    $0x1,%esi\t\t# count of result bytes..\n\tcmp    $0x14,%esi\t\t# did we have 20 already?\n\tmov    %dl,(%ebx)\t\t# save the \"last loop\" result\n\tje     0x807630b <get_sha1_hex+75>\t# break out\n\tadd    $0x1,%ebx\t\t# update dest pointer (one byte at a time)\n\tadd    $0x2,%ecx\t\t# update source pointer (two hex chars at a time)\n\tmovsbl (%ecx),%eax\t\t# get first character\n\tmovsbl 0x80989e0(%eax),%edx\t# get the hexval for it\n\tmovsbl 0x1(%ecx),%eax\t\t# get the second character\n\tshl    $0x4,%edx\t\t# shift first character hexval up by 4\n\tmovsbl 0x80989e0(%eax),%eax\t# get second character hexval\n\tor     %eax,%edx\t\t# get the byte value\n\ttest   $0xffffff00,%edx\t\t# was it ok (0x00 - 0xff)?\n\tje     <get_sha1_hex+16>\t# yeah, continue\n\nwhich should perform very well (just two comparisons - one for the \"wrong \nbits set\" at the end, and one for the 20-byte-counter test at the \nbeginning). Small and sweet.\n\nIn fact, I don't see how you can much improve on that code even if you \nwere to hand-code it, so gcc actually generates good code once the \n\"hexval()\" function has been written like this.\n\nNot very much tested, but it looks obvious enough.. And it's actually \nconceptually a smaller diff than yours (ie it doesn't change anything but \nthe \"hexval()\" function, and all the bulk of it is the stupid array \ninitializer).\n\n\t\tLinus\n\n---\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 428d791..b64b92d 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -26,15 +26,43 @@ const unsigned char null_sha1[20];\n \n static unsigned int sha1_file_open_flag = O_NOATIME;\n \n-static unsigned hexval(char c)\n-{\n-\tif (c >= '0' && c <= '9')\n-\t\treturn c - '0';\n-\tif (c >= 'a' && c <= 'f')\n-\t\treturn c - 'a' + 10;\n-\tif (c >= 'A' && c <= 'F')\n-\t\treturn c - 'A' + 10;\n-\treturn ~0;\n+static inline unsigned int hexval(unsigned int c)\n+{\n+\tstatic signed char val[256] = {\n+\t\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 00-07 */\n+\t\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 08-0f */\n+\t\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 10-17 */\n+\t\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 18-1f */\n+\t\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 20-27 */\n+\t\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 28-2f */\n+\t\t  0,  1,  2,  3,  4,  5,  6,  7,\t\t/* 30-37 */\n+\t\t  8,  9, -1, -1, -1, -1, -1, -1,\t\t/* 38-3f */\n+\t\t -1, 10, 11, 12, 13, 14, 15, -1,\t\t/* 40-47 */\n+\t\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 48-4f */\n+\t\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 50-57 */\n+\t\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 58-5f */\n+\t\t -1, 10, 11, 12, 13, 14, 15, -1,\t\t/* 60-67 */\n+\t\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 68-67 */\n+\t\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 70-77 */\n+\t\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 78-7f */\n+\t\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 80-87 */\n+\t\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 88-8f */\n+\t\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 90-97 */\n+\t\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 98-9f */\n+\t\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* a0-a7 */\n+\t\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* a8-af */\n+\t\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* b0-b7 */\n+\t\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* b8-bf */\n+\t\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* c0-c7 */\n+\t\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* c8-cf */\n+\t\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* d0-d7 */\n+\t\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* d8-df */\n+\t\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* e0-e7 */\n+\t\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* e8-ef */\n+\t\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* f0-f7 */\n+\t\t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* f8-ff */\n+\t};\n+\treturn val[c];\n }\n \n int get_sha1_hex(const char *hex, unsigned char *sha1)\n"},{"id":"26661","messageId":"Pine.LNX.4.64.0609091741420.27779@g5.osdl.org","threadId":"5531","inReplyTo":"Pine.LNX.4.64.0609091639110.27779@g5.osdl.org","subject":"Re: {RFC/PATCH] micro-optimize get_sha1_hex()","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-09-10T00:53:14Z","receivedAt":"2006-09-10T00:53:14Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 9 Sep 2006, Linus Torvalds wrote:\n>\n> I _suspect_ that you profiled using \"gprof\" and the \"-pg\" flag to \n> the compiler?\n\nBtw, in the absense of oprofile (which is very useful, and has the \nadvantage that you can run many programs multiple times and get a \n\"combined data\" output from it all), what you can do (and which is more \nreliable) is:\n\n - the \"minor pagefault\" count that /usr/bin/time prints out is very \n   useful. It gives a pretty much direct view into what the total memory \n   use of the program was over its lifetime, in a way that very few other \n   things do.\n\n - using \"gprof\" to try to find _potential_ hotspots, but then not \n   trusting the profiling numbers at all for actual improvement, but \n   simply recompiling (witout profiling) and timing it for real after any \n   change. The real timings will almost certainly not match what you \n   thought you'd get from profiling, but now they'll be real numbers.\n\n - using \"-pg\" to link in the profiling code, BUT ONLY AT THE FINAL LINK \n   TIME! This will give you the \"% time\" and \"cumulative seconds\" part, \n   but it will mean that you will _not_ get the call-graph, because now \n   the actual code generation is not affected, and the compiler won't be \n   inserting all the call-graph-generation code. \n\nNote that the last use makes gprof much more accurate, but it also means \nthat it won't _work_ very well for things that are fast. You usually have \na 1/100th of a second profiling setup, so anything that is less than a \nsecond won't have much of a profile. So this only works for longer-running \nthings.\n\n\t\tLinus\n"}]}