{"action":"opened","issue":{"url":"https://api.github.com/repos/mndrix/ddata/issues/8","repository_url":"https://api.github.com/repos/mndrix/ddata","labels_url":"https://api.github.com/repos/mndrix/ddata/issues/8/labels{/name}","comments_url":"https://api.github.com/repos/mndrix/ddata/issues/8/comments","events_url":"https://api.github.com/repos/mndrix/ddata/issues/8/events","html_url":"https://github.com/mndrix/ddata/issues/8","id":184361634,"number":8,"title":"use lazy hashes","user":{"login":"mndrix","id":43997,"avatar_url":"https://avatars.githubusercontent.com/u/43997?v=3","gravatar_id":"","url":"https://api.github.com/users/mndrix","html_url":"https://github.com/mndrix","followers_url":"https://api.github.com/users/mndrix/followers","following_url":"https://api.github.com/users/mndrix/following{/other_user}","gists_url":"https://api.github.com/users/mndrix/gists{/gist_id}","starred_url":"https://api.github.com/users/mndrix/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mndrix/subscriptions","organizations_url":"https://api.github.com/users/mndrix/orgs","repos_url":"https://api.github.com/users/mndrix/repos","events_url":"https://api.github.com/users/mndrix/events{/privacy}","received_events_url":"https://api.github.com/users/mndrix/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":0,"created_at":"2016-10-20T23:00:29Z","updated_at":"2016-10-20T23:00:29Z","closed_at":null,"body":"When profiling map and pmap, the biggest consumers of CPU time (after GC) is computations related to the hash.  Part of this is converting the hash bytes into a big integer.  The other is performing math operations on this big integer.\r\n\r\nBy using a list of bytes as the hash, we should be able to defer most of that computation until later.  For sparse maps, deferring the computation effectively eliminates it.\r\n\r\nI don't think this will cause extra GC pressure because the hash lists will be shared between trees.\r\n\r\nThe basic design is to store the hash in a term like `hash(AvailableBits,NextByte,Bytes)`.  A quick sketch of using this term in `hash_residue_n/3`\r\n\r\n```prolog\r\nhash_residue_n(hash(Available,Byte,Bytes),Residue,N) :-\r\n    plump_shift(Shift),\r\n    compare(Ord,Available,Shift),\r\n    hash_residue_n(Ord,hash(Available,Byte,Bytes),Residue,N).\r\n\r\nhash_residue_n((=),hash(_,N,[NextByte|Bytes]),hash(8,NextByte,Bytes),N).\r\nhash_residue_n((>),hash(Available,Byte0,Bytes),hash(Left,Byte,Bytes),N) :-\r\n    plump_shift(Shift),\r\n    plump_mask(Mask),\r\n    N is Mask /\\ Byte,\r\n    Byte is Byte0 >> Shift,\r\n    Left is Available - Shift.\r\nhash_residue_n((<),hash(Available,Byte0,[NextByte|Bytes]),hash(Left,Byte1,Bytes),N) :-\r\n    plump_shift(Shift),\r\n    NeedMoreBits is Shift - Available,\r\n    Mask is (1 << NeedMoreBits) - 1,\r\n    ExtraBits is ByteNext /\\ Mask,\r\n    N is (ExtraBits << NeedMoreBits) /\\ Byte0,\r\n    Byte1 is (ByteNext >> NeedMoreBits),\r\n    Left is 8 - NeedMoreBits.\r\n```"}}
{"actor":{"display_login":"mndrix"}}