{"action":"created","issue":{"url":"https://api.github.com/repos/php/php-src/issues/4126","repository_url":"https://api.github.com/repos/php/php-src","labels_url":"https://api.github.com/repos/php/php-src/issues/4126/labels{/name}","comments_url":"https://api.github.com/repos/php/php-src/issues/4126/comments","events_url":"https://api.github.com/repos/php/php-src/issues/4126/events","html_url":"https://github.com/php/php-src/pull/4126","id":441246204,"node_id":"MDExOlB1bGxSZXF1ZXN0Mjc2NjA5Mjgw","number":4126,"title":"use multiplies and load 8 bytes at a time in hash_func","user":{"login":"sebpop","id":568397,"node_id":"MDQ6VXNlcjU2ODM5Nw==","avatar_url":"https://avatars1.githubusercontent.com/u/568397?v=4","gravatar_id":"","url":"https://api.github.com/users/sebpop","html_url":"https://github.com/sebpop","followers_url":"https://api.github.com/users/sebpop/followers","following_url":"https://api.github.com/users/sebpop/following{/other_user}","gists_url":"https://api.github.com/users/sebpop/gists{/gist_id}","starred_url":"https://api.github.com/users/sebpop/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/sebpop/subscriptions","organizations_url":"https://api.github.com/users/sebpop/orgs","repos_url":"https://api.github.com/users/sebpop/repos","events_url":"https://api.github.com/users/sebpop/events{/privacy}","received_events_url":"https://api.github.com/users/sebpop/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":3,"created_at":"2019-05-07T13:53:38Z","updated_at":"2019-05-07T22:54:49Z","closed_at":null,"author_association":"CONTRIBUTOR","pull_request":{"url":"https://api.github.com/repos/php/php-src/pulls/4126","html_url":"https://github.com/php/php-src/pull/4126","diff_url":"https://github.com/php/php-src/pull/4126.diff","patch_url":"https://github.com/php/php-src/pull/4126.patch"},"body":"By using multiplies the dependence chain `hash = ((hash << 5) + hash)` is broken\r\ninto independent computations that the compiler and the processor can use to\r\ncreate more instruction level parallelism.  Lemire described this technique in\r\nhttps://lemire.me/blog/2016/07/21/accelerating-php-hashing-by-unoptimizing-it/\r\n\r\nThe patch also loads by chunks of 8 bytes and then reference each byte using\r\narithmetic.  This is beneficial on modern architectures because it reduces the\r\ntotal number of reads from memory: reading a byte usually takes as many cycles\r\nto execute as reading 8 bytes.\r\n\r\n```\r\nZEND_DONT_UNLOAD_MODULES=1 valgrind --tool=cachegrind sapi/cgi/php-cgi -d opcache.jit=0 -T100 wordpress/index.php > /dev/null\r\n\r\nbefore the patch: I   refs:      2,523,364,053\r\nwith the patch:   I   refs:      2,522,139,713\r\n```\r\nThat is 0.1% fewer instructions.\r\n\r\n```\r\nbefore the patch: D   refs:        966,807,101  (647,691,647 rd   + 319,115,454 wr)\r\nwith the patch:   D   refs:        961,943,551  (642,828,274 rd   + 319,115,277 wr)\r\n```\r\nThat is 5M fewer loads, about 0.5% fewer loads.\r\n\r\nOn a Graviton A1 instance, google-benchmark measure before and after the patch:\r\n```\r\n--------------------------------------------------------------\r\nBenchmark                Time             CPU   Iterations\r\n--------------------------------------------------------------\r\nBM_hash_original      33.8 ns         33.8 ns     20671964\r\nBM_hash_lemire        18.7 ns         18.7 ns     37442214\r\n```\r\n\r\nHistogram for hashed strings length in multiples of 8 bytes:\r\n```\r\nlen[0] represents strings of 0 to 7 bytes,\r\nlen[1] represents strings of 8 to 15 bytes, ...\r\n\r\n    micro_bench.php  bench.php        make test\r\n    len[0] = 1970    len[0] = 83120   len[0] = 733803\r\n    len[1] = 2818    len[1] = 2700    len[1] = 613280\r\n    len[2] = 1038    len[2] = 1019    len[2] = 1301848\r\n    len[3] = 203     len[3] = 206     len[3] = 322507\r\n    len[4] = 33      len[4] = 32      len[4] = 206156\r\n    len[5] = 0       len[5] = 0       len[5] = 102598\r\n    len[6] = 3       len[6] = 3       len[6] = 92028\r\n    len[7] = 0       len[7] = 0       len[7] = 50240\r\n    len[8] = 0       len[8] = 0       len[8] = 51042\r\n    len[9] = 0       len[9] = 0       len[9] = 40486\r\n    len[10] = 0      len[10] = 0      len[10] = 44392\r\n```"},"comment":{"url":"https://api.github.com/repos/php/php-src/issues/comments/490283607","html_url":"https://github.com/php/php-src/pull/4126#issuecomment-490283607","issue_url":"https://api.github.com/repos/php/php-src/issues/4126","id":490283607,"node_id":"MDEyOklzc3VlQ29tbWVudDQ5MDI4MzYwNw==","user":{"login":"lemire","id":391987,"node_id":"MDQ6VXNlcjM5MTk4Nw==","avatar_url":"https://avatars3.githubusercontent.com/u/391987?v=4","gravatar_id":"","url":"https://api.github.com/users/lemire","html_url":"https://github.com/lemire","followers_url":"https://api.github.com/users/lemire/followers","following_url":"https://api.github.com/users/lemire/following{/other_user}","gists_url":"https://api.github.com/users/lemire/gists{/gist_id}","starred_url":"https://api.github.com/users/lemire/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/lemire/subscriptions","organizations_url":"https://api.github.com/users/lemire/orgs","repos_url":"https://api.github.com/users/lemire/repos","events_url":"https://api.github.com/users/lemire/events{/privacy}","received_events_url":"https://api.github.com/users/lemire/received_events","type":"User","site_admin":false},"created_at":"2019-05-07T22:54:49Z","updated_at":"2019-05-07T22:54:49Z","author_association":"NONE","body":"Only a stupid compiler would miss that one, but you can safely replace\r\n\r\n```\r\n(chunk >> (8 * 7)) & 0xFF\r\n```\r\n\r\nby \r\n\r\n```\r\n(chunk >> (8 * 7)).\r\n```\r\n\r\n(Duh!)"}}
{"actor":{"display_login":"lemire"}}