{"action":"created","issue":{"url":"https://api.github.com/repos/ocaml/ocaml/issues/328","labels_url":"https://api.github.com/repos/ocaml/ocaml/issues/328/labels{/name}","comments_url":"https://api.github.com/repos/ocaml/ocaml/issues/328/comments","events_url":"https://api.github.com/repos/ocaml/ocaml/issues/328/events","html_url":"https://github.com/ocaml/ocaml/pull/328","id":120235924,"number":328,"title":"Optim hashtbl","user":{"login":"alainfrisch","id":3305274,"avatar_url":"https://avatars.githubusercontent.com/u/3305274?v=3","gravatar_id":"","url":"https://api.github.com/users/alainfrisch","html_url":"https://github.com/alainfrisch","followers_url":"https://api.github.com/users/alainfrisch/followers","following_url":"https://api.github.com/users/alainfrisch/following{/other_user}","gists_url":"https://api.github.com/users/alainfrisch/gists{/gist_id}","starred_url":"https://api.github.com/users/alainfrisch/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/alainfrisch/subscriptions","organizations_url":"https://api.github.com/users/alainfrisch/orgs","repos_url":"https://api.github.com/users/alainfrisch/repos","events_url":"https://api.github.com/users/alainfrisch/events{/privacy}","received_events_url":"https://api.github.com/users/alainfrisch/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/ocaml/ocaml/labels/after-next-release","name":"after-next-release","color":"bfe5bf"}],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":26,"created_at":"2015-12-03T18:17:58Z","updated_at":"2015-12-09T12:31:23Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/ocaml/ocaml/pulls/328","html_url":"https://github.com/ocaml/ocaml/pull/328","diff_url":"https://github.com/ocaml/ocaml/pull/328.diff","patch_url":"https://github.com/ocaml/ocaml/pull/328.patch"},"body":"This is a follow up to http://caml.inria.fr/mantis/view.php?id=4747.\r\n\r\nI propose to implement buckets of hash tables using inline records, to allow keeping the same concrete compact representation as today while allowing to mutate the field of each bucket cell.  Thanks to this change, one can avoid all non tailrec functions (and hence fix the original bug) and many allocations.\r\n\r\nInterestingly, all three fields of cells can be mutated:\r\n\r\n - The `key` and `data` fields are modified by `Hashtbl.replace` so that it doesn't allocate at all when a binding with an equal key was already in the table (one needs to update the `key` to keep the previous behavior, although one could consider a faster version of replace which does not update it -- this would be fine for the vast majority of uses and avoid 1/2 of the mutations in that case).\r\n\r\n - The `rest` field is modified in `Hashtbl.remove` in order to remove a cell from the bucket list, and in `resize` in order to append to the tail of a bucket (allowing to treat all cells sequentially and keep the function tailrec).\r\n\r\nOne downside of this approach is that `Hashtbl.copy` cannot simply do a shallow copy the array of buckets anymore. It needs to copy each bucket.  This is done in a tailrec function again, but obviously, this can be quite costly.  I doubt this function is used a lot, and `Hashtbl.copy` is not completely cheap anyway.\r\n\r\nI've attached a micro-benchmark on Mantis, with results in a note below.  Except for `Hashtbl.copy`, the result are quite encouraging, with gains often above 25%.  Considering that Hashtbl is used very pervasively, this is certainly worth considering.  (I'm also quite confident that gains would be even higher for js_of_ocaml.)\r\n\r\n[EDIT: this is no longer WIP; this should be ready for inclusion.]"},"comment":{"url":"https://api.github.com/repos/ocaml/ocaml/issues/comments/163212528","html_url":"https://github.com/ocaml/ocaml/pull/328#issuecomment-163212528","issue_url":"https://api.github.com/repos/ocaml/ocaml/issues/328","id":163212528,"user":{"login":"xavierleroy","id":3845810,"avatar_url":"https://avatars.githubusercontent.com/u/3845810?v=3","gravatar_id":"","url":"https://api.github.com/users/xavierleroy","html_url":"https://github.com/xavierleroy","followers_url":"https://api.github.com/users/xavierleroy/followers","following_url":"https://api.github.com/users/xavierleroy/following{/other_user}","gists_url":"https://api.github.com/users/xavierleroy/gists{/gist_id}","starred_url":"https://api.github.com/users/xavierleroy/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/xavierleroy/subscriptions","organizations_url":"https://api.github.com/users/xavierleroy/orgs","repos_url":"https://api.github.com/users/xavierleroy/repos","events_url":"https://api.github.com/users/xavierleroy/events{/privacy}","received_events_url":"https://api.github.com/users/xavierleroy/received_events","type":"User","site_admin":false},"created_at":"2015-12-09T12:31:23Z","updated_at":"2015-12-09T12:31:23Z","body":"For #238 (CamlinternalOO), I convinced myself that objects are still outside the bootstrap cycle..."}}