{"action":"created","issue":{"url":"https://api.github.com/repos/cockroachdb/cockroach/issues/5337","repository_url":"https://api.github.com/repos/cockroachdb/cockroach","labels_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/5337/labels{/name}","comments_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/5337/comments","events_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/5337/events","html_url":"https://github.com/cockroachdb/cockroach/pull/5337","id":141520138,"number":5337,"title":"encoding: Replace float and decimal encodings with faster approaches","user":{"login":"nvanbenschoten","id":5438456,"avatar_url":"https://avatars.githubusercontent.com/u/5438456?v=3","gravatar_id":"","url":"https://api.github.com/users/nvanbenschoten","html_url":"https://github.com/nvanbenschoten","followers_url":"https://api.github.com/users/nvanbenschoten/followers","following_url":"https://api.github.com/users/nvanbenschoten/following{/other_user}","gists_url":"https://api.github.com/users/nvanbenschoten/gists{/gist_id}","starred_url":"https://api.github.com/users/nvanbenschoten/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nvanbenschoten/subscriptions","organizations_url":"https://api.github.com/users/nvanbenschoten/orgs","repos_url":"https://api.github.com/users/nvanbenschoten/repos","events_url":"https://api.github.com/users/nvanbenschoten/events{/privacy}","received_events_url":"https://api.github.com/users/nvanbenschoten/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/cockroachdb/cockroach/labels/enhancement","name":"enhancement","color":"84b6eb"},{"url":"https://api.github.com/repos/cockroachdb/cockroach/labels/noteworthy","name":"noteworthy","color":"d4c5f9"}],"state":"open","locked":false,"assignee":{"login":"petermattis","id":6201335,"avatar_url":"https://avatars.githubusercontent.com/u/6201335?v=3","gravatar_id":"","url":"https://api.github.com/users/petermattis","html_url":"https://github.com/petermattis","followers_url":"https://api.github.com/users/petermattis/followers","following_url":"https://api.github.com/users/petermattis/following{/other_user}","gists_url":"https://api.github.com/users/petermattis/gists{/gist_id}","starred_url":"https://api.github.com/users/petermattis/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/petermattis/subscriptions","organizations_url":"https://api.github.com/users/petermattis/orgs","repos_url":"https://api.github.com/users/petermattis/repos","events_url":"https://api.github.com/users/petermattis/events{/privacy}","received_events_url":"https://api.github.com/users/petermattis/received_events","type":"User","site_admin":false},"milestone":{"url":"https://api.github.com/repos/cockroachdb/cockroach/milestones/1","html_url":"https://github.com/cockroachdb/cockroach/milestones/Beta","labels_url":"https://api.github.com/repos/cockroachdb/cockroach/milestones/1/labels","id":778698,"number":1,"title":"Beta","description":"","creator":{"login":"andybons","id":365204,"avatar_url":"https://avatars.githubusercontent.com/u/365204?v=3","gravatar_id":"","url":"https://api.github.com/users/andybons","html_url":"https://github.com/andybons","followers_url":"https://api.github.com/users/andybons/followers","following_url":"https://api.github.com/users/andybons/following{/other_user}","gists_url":"https://api.github.com/users/andybons/gists{/gist_id}","starred_url":"https://api.github.com/users/andybons/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/andybons/subscriptions","organizations_url":"https://api.github.com/users/andybons/orgs","repos_url":"https://api.github.com/users/andybons/repos","events_url":"https://api.github.com/users/andybons/events{/privacy}","received_events_url":"https://api.github.com/users/andybons/received_events","type":"User","site_admin":false},"open_issues":97,"closed_issues":450,"state":"open","created_at":"2014-09-04T16:42:18Z","updated_at":"2016-03-17T10:07:18Z","due_on":null,"closed_at":null},"comments":1,"created_at":"2016-03-17T09:00:45Z","updated_at":"2016-03-17T12:37:05Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/cockroachdb/cockroach/pulls/5337","html_url":"https://github.com/cockroachdb/cockroach/pull/5337","diff_url":"https://github.com/cockroachdb/cockroach/pull/5337.diff","patch_url":"https://github.com/cockroachdb/cockroach/pull/5337.patch"},"body":"## Float Encoding\r\n\r\nFixes #5192.\r\n\r\nThis approach was inspired by [orderedcode.go](https://github.com/google/orderedcode/blob/master/orderedcode.go#L246). It reinterprets the bits\r\nof a float64 as an int64, and messes with this reinterpretation to get\r\nthe ordering correct. For positive floats, the encoding of the 64 bits\r\n(in IEEE 754 format) is directly encoded using `EncodeUint64Ascending`.\r\nFor negative floats, we keep the sign bit and invert all other bits,\r\nencoding this value using `EncodeUint64Descending`.\r\n\r\n```\r\nname           old time/op    new time/op    delta\r\nEncodeFloat-4     314ns ± 7%      23ns ± 3%  -92.53%         (p=0.000 n=10+9)\r\nDecodeFloat-4     308ns ±12%      30ns ± 1%  -90.24%         (p=0.000 n=10+9)\r\n\r\nname           old alloc/op   new alloc/op   delta\r\nEncodeFloat-4    0.00B ±NaN%    0.00B ±NaN%     ~     (all samples are equal)\r\nDecodeFloat-4    0.00B ±NaN%    0.00B ±NaN%     ~     (all samples are equal)\r\n\r\nname           old allocs/op  new allocs/op  delta\r\nEncodeFloat-4     0.00 ±NaN%     0.00 ±NaN%     ~     (all samples are equal)\r\nDecodeFloat-4     0.00 ±NaN%     0.00 ±NaN%     ~     (all samples are equal)\r\n```\r\n\r\n## Decimal Encoding\r\n\r\nNow that we are no longer tied to the sqlLite float encoding for\r\ndecimals, we can go nuts with a custom encoding. This commit proposes a\r\nnew encoding that uses the bytes directly from the underlying `big.Int`\r\nto represent the decimal's mantissa. After a lot of tinkering the\r\napproach reduced decimal encoding to zero allocations! It uses a\r\ncouple of tricks to achieve that, including a binary digit lookup table\r\n(because we absolutely **do not** want to have to string format the decimal!)\r\nand a few routines working on slices of little-endian `big.Words` so that\r\nwe can flip the bytes into the encoding key directly. Decoding was also\r\nimproved by reducing allocations in a few key spots. These included\r\nusing the binary digit lookup table, performing ones-complements on the\r\nkeys themselves, and better handling the decimal's underlying `big.Int`.\r\n\r\n```\r\nname             old time/op    new time/op    delta\r\nEncodeDecimal-4     470ns ± 2%     161ns ± 1%   -65.81%    (p=0.000 n=9+9)\r\nDecodeDecimal-4     622ns ± 2%     239ns ± 1%   -61.66%  (p=0.000 n=10+10)\r\n\r\nname             old alloc/op   new alloc/op   delta\r\nEncodeDecimal-4     89.0B ± 0%     0.0B ±NaN%  -100.00%  (p=0.000 n=10+10)\r\nDecodeDecimal-4      176B ± 0%       96B ± 0%   -45.45%  (p=0.000 n=10+10)\r\n\r\nname             old allocs/op  new allocs/op  delta\r\nEncodeDecimal-4      3.00 ± 0%     0.00 ±NaN%  -100.00%  (p=0.000 n=10+10)\r\nDecodeDecimal-4      4.00 ± 0%      2.00 ± 0%   -50.00%  (p=0.000 n=10+10)\r\n```\r\n\r\n### Disclaimer\r\n\r\n_I marked this as noteworthy because this will **break existing clusters**. It also \r\n**needs** to be resolved by beta._\n\n<!-- Reviewable:start -->\n---\nThis change is [<img src=\"https://reviewable.io/review_button.svg\" height=\"35\" align=\"absmiddle\" alt=\"Reviewable\"/>](https://reviewable.io/reviews/cockroachdb/cockroach/5337)\n<!-- Reviewable:end -->\n"},"comment":{"url":"https://api.github.com/repos/cockroachdb/cockroach/issues/comments/197858445","html_url":"https://github.com/cockroachdb/cockroach/pull/5337#issuecomment-197858445","issue_url":"https://api.github.com/repos/cockroachdb/cockroach/issues/5337","id":197858445,"user":{"login":"knz","id":642886,"avatar_url":"https://avatars.githubusercontent.com/u/642886?v=3","gravatar_id":"","url":"https://api.github.com/users/knz","html_url":"https://github.com/knz","followers_url":"https://api.github.com/users/knz/followers","following_url":"https://api.github.com/users/knz/following{/other_user}","gists_url":"https://api.github.com/users/knz/gists{/gist_id}","starred_url":"https://api.github.com/users/knz/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/knz/subscriptions","organizations_url":"https://api.github.com/users/knz/orgs","repos_url":"https://api.github.com/users/knz/repos","events_url":"https://api.github.com/users/knz/events{/privacy}","received_events_url":"https://api.github.com/users/knz/received_events","type":"User","site_admin":false},"created_at":"2016-03-17T12:37:05Z","updated_at":"2016-03-17T12:37:05Z","body":"I'm not sure it's a great idea to merge the encoding for positive and negative zero. This break math. \r\n\r\nConsider for example the following basic principle: x / ceil(x) should have the same sign as x for all x. \r\nWith signed zero you get -0.5 / ceil(-0.5) = -0.5 / -0.0 = -Inf.    If you store +/- 0 in the same way, that means that the formula loses its sign property if you store the operand in a table. Do we really want that?"}}