{"action":"created","comment":{"url":"https://api.github.com/repos/ocaml/ocaml/pulls/comments/46696109","id":46696109,"diff_hunk":"@@ -186,7 +186,10 @@ Standard library:\n   * Sys.time (and [@@noalloc])\n   * Pervasives.ldexp (and [@@noalloc])\n   * Pervasives.compare for float, nativeint, int32, int64.\n-  (Bobot François)\n+  (François Bobot)\n+- GPR#22: Add the Ephemeron module that implements ephemerons and weak\n+  hash table (François Bobot, review by Damien Doligez, Daniel Bünzli,\n+  Alain Frisch)","path":"Changes","position":8,"original_position":8,"commit_id":"9c8231755b578d6cf54cd4467535ffa621c625e1","original_commit_id":"9c8231755b578d6cf54cd4467535ffa621c625e1","user":{"login":"damiendoligez","id":19104,"avatar_url":"https://avatars.githubusercontent.com/u/19104?v=3","gravatar_id":"","url":"https://api.github.com/users/damiendoligez","html_url":"https://github.com/damiendoligez","followers_url":"https://api.github.com/users/damiendoligez/followers","following_url":"https://api.github.com/users/damiendoligez/following{/other_user}","gists_url":"https://api.github.com/users/damiendoligez/gists{/gist_id}","starred_url":"https://api.github.com/users/damiendoligez/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/damiendoligez/subscriptions","organizations_url":"https://api.github.com/users/damiendoligez/orgs","repos_url":"https://api.github.com/users/damiendoligez/repos","events_url":"https://api.github.com/users/damiendoligez/events{/privacy}","received_events_url":"https://api.github.com/users/damiendoligez/received_events","type":"User","site_admin":false},"body":"Add Pierre to this list.","created_at":"2015-12-04T15:54:27Z","updated_at":"2015-12-04T15:54:27Z","html_url":"https://github.com/ocaml/ocaml/pull/22#discussion_r46696109","pull_request_url":"https://api.github.com/repos/ocaml/ocaml/pulls/22","_links":{"self":{"href":"https://api.github.com/repos/ocaml/ocaml/pulls/comments/46696109"},"html":{"href":"https://github.com/ocaml/ocaml/pull/22#discussion_r46696109"},"pull_request":{"href":"https://api.github.com/repos/ocaml/ocaml/pulls/22"}}},"pull_request":{"url":"https://api.github.com/repos/ocaml/ocaml/pulls/22","id":13967630,"html_url":"https://github.com/ocaml/ocaml/pull/22","diff_url":"https://github.com/ocaml/ocaml/pull/22.diff","patch_url":"https://github.com/ocaml/ocaml/pull/22.patch","issue_url":"https://api.github.com/repos/ocaml/ocaml/issues/22","number":22,"state":"open","locked":false,"title":"Add Ephemerons to OCaml","user":{"login":"bobot","id":102849,"avatar_url":"https://avatars.githubusercontent.com/u/102849?v=3","gravatar_id":"","url":"https://api.github.com/users/bobot","html_url":"https://github.com/bobot","followers_url":"https://api.github.com/users/bobot/followers","following_url":"https://api.github.com/users/bobot/following{/other_user}","gists_url":"https://api.github.com/users/bobot/gists{/gist_id}","starred_url":"https://api.github.com/users/bobot/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/bobot/subscriptions","organizations_url":"https://api.github.com/users/bobot/orgs","repos_url":"https://api.github.com/users/bobot/repos","events_url":"https://api.github.com/users/bobot/events{/privacy}","received_events_url":"https://api.github.com/users/bobot/received_events","type":"User","site_admin":false},"body":"#### Ephemerons\r\nThe current OCaml runtime proposes two kinds of pointers:\r\n\r\n- `A` points hardly to `B`: if `A` is alive, `B` is alive (usual pointers)\r\n- `A` points weakly to `B`: when the GC decide that `B` stops to be alive, `A` stops to point to `B`\r\n\r\nWeak pointers are very handy when you want to be able to access a data without creating memory leaks. For example hashconsing can be done using the weaksets defined in `Weak.Make`. However you can't create general weaktable with the current runtime: associative table that keep a data until the key is not needed anymore. The problematic case is when the data points to the key(cf [10]).\r\n\r\nBarry Hayes proposed in 1997 (cf [9]) the notion of ephemerons which allow to code such table. In its simplest form an ephemeron `A` with key `K` and data `D` keeps `D` alive while `A` **and** `K` are alive. To sum up ephemerons add the possibility to express conjunctions where you normally have only disjunctions.\r\n\r\n#### Request for Comment and Merge-Request\r\nThis merge-request adds ephemerons to ocaml with particularly a modification of the runtime, [4], and a new module in the standard library, [6]. An untyped API with an arbitrary number of keys is given in `Ephemerons.Obj` and two specialized API for one and two keys are provided in `Ephemerons.K1` and `Ephemerons.K2`. Each of these three APIs define a functor for constructing weaktables with the same signature than `Hashtbl`.\r\n\r\nBefore an actual review of the C or OCaml implementation parts, comments about the OCaml interface are more than welcomed.\r\n\r\nThe modifications are splitted as follows:\r\n\r\n- [1], [2]: code factorization that can be removed from the merge request but at the end without them some functions start to be very big\r\n- [3]: A correction of the behavior of the weak pointer when more than one weak array points to one value\r\n- [4]: Add the ephemerons in the runtime (simple but inefficient way). The stdlib is modified in another commit in order to simplify rebase and bootstrapping.\r\n- [5]: just add a getter for Hashtbl.randomized\r\n- [6]: Add the module Ephemeron in the stdlib and some tests in the testsuites\r\n- [7]: Shortcut clean phase if possible (can be removed from the merge request)\r\n- [8]: Optimize the implementation of the ephemerons and mitigate the worst case\r\n\r\nThe code have been evaluated on Why3, \"don't use\" correspond to why3 commit [11] and \"use\" to why3 commit [12] that replace the half-satisfying weak-table solution by weak-table provided by Ephemeron.\r\n\r\n|           |     [0]      |     [1]      |     [2]      |     [3]      |     [4]      |     [5]      |     [6]      |     [7]      |     [8]      |\r\n|:----------|:------------:|:------------:|:------------:|:------------:|:------------:|:------------:|:------------:|:------------:|:------------:|\r\n| don't use | 12.96 (0.02) | 12.96 (0.13) | 12.93 (0.03) | 13.26 (0.06) | 13.70 (0.27) | 13.87 (0.16) | 13.30 (0.04) | 13.37 (0.10) | 13.10 (0.09) |\r\n|       use |      NA      |      NA      |      NA      |      NA      |      NA      |      NA      | 12.08 (0.06) | 12.02 (0.05) | 11.88 (0.05) |\r\n\r\n\r\nWe can see that the slowdown for a code that heavily use weak pointers is of 1-2%, and the speedup when using weak-pointers (weaksets) and weaktable is of 8% without counting the fact that the weaktable is \"perfect\" and simple to use.\r\n\r\n\r\n*nb: the branch is not directly mergeable because of `boot/ocaml...`, but at the end of the review process I will rebase the branch and doing the bootstrap.*\r\n\r\n#### How to reproduce the bench\r\nclone why3, `configure --enable-local`,  `bin/why3config --detect`. Add this section to `why3.conf`:\r\n\r\n```\r\n[prover]\r\ncommand = \"/bin/true %t %f\"\r\ndriver = \"drivers/null_smt.drv\"\r\neditor = \"\"\r\nin_place = false\r\ninteractive = false\r\nname = \"null\"\r\nversion = \"0\"\r\n```\r\n\r\nBench with the command:\r\n\r\n```\r\n(exec bin/why3session.opt output --output /tmp --filter-prover null $(git ls-files \"examples/**/why3session.xml\") -L examples/bitvectors -F -L examples/vacid_0_binary_heaps/) >& /dev/null\r\n```\r\n\r\n[0]: ccf516168fc5c2570c77ed3dfe8ec973c342e97e\r\n[1]: https://github.com/bobot/ocaml/commit/3caeca0b32c45e7200e692c49a90555c641abbe7\r\n[2]: https://github.com/bobot/ocaml/commit/3a27d09a2938cf872880c03e1e849fefe3d0edfd\r\n[3]: https://github.com/bobot/ocaml/commit/e1dac1c1b563ae44f5255d2166d81ba641a4f66d\r\n[4]: https://github.com/bobot/ocaml/commit/85e173203df770d443cf74c5eede969cc339fd4a\r\n[5]: https://github.com/bobot/ocaml/commit/99db66f3e86bca69c68407d42b4e5727a421c3fe\r\n[6]: https://github.com/bobot/ocaml/commit/47e1e6730acd39529b63a8345a4b9c4c5f659a8c\r\n[7]: https://github.com/bobot/ocaml/commit/a75d8130323e378a89a348de56f537a0c86c6448\r\n[8]: https://github.com/bobot/ocaml/commit/b83f7bbd415dea05127bd11c0fadae965b88cf37\r\n[9]: http://pdf.aminer.org/000/522/273/ephemerons_a_new_finalization_mechanism.pdf\r\n[10]: http://forge.ocamlcore.org/plugins/mediawiki/wiki/ocaml-meeting/index.php/OCamlMeeting2011#The_Eternal_Solution_for_Memoisation:_Ephemerons.2C_by_Fran.C3.A7ois_Bobot\r\n[11]: https://gforge.inria.fr/plugins/scmgit/cgi-bin/gitweb.cgi?p=why3/why3.git;a=commitdiff;h=838ea132ad07ddd9c4a6a2843b5023b82caa5bfd\r\n[12]: https://gforge.inria.fr/plugins/scmgit/cgi-bin/gitweb.cgi?p=why3/why3.git;a=commitdiff;h=f17551ce9d36035ef8d0ffae256872611e798b29","created_at":"2014-03-25T18:10:10Z","updated_at":"2015-12-04T15:54:28Z","closed_at":null,"merged_at":null,"merge_commit_sha":"a1d7929e328cc27a5cb5f50f68f342eba7c2aefc","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/ocaml/ocaml/pulls/22/commits","review_comments_url":"https://api.github.com/repos/ocaml/ocaml/pulls/22/comments","review_comment_url":"https://api.github.com/repos/ocaml/ocaml/pulls/comments{/number}","comments_url":"https://api.github.com/repos/ocaml/ocaml/issues/22/comments","statuses_url":"https://api.github.com/repos/ocaml/ocaml/statuses/9c8231755b578d6cf54cd4467535ffa621c625e1","head":{"label":"bobot:feature/ephemerons","ref":"feature/ephemerons","sha":"9c8231755b578d6cf54cd4467535ffa621c625e1","user":{"login":"bobot","id":102849,"avatar_url":"https://avatars.githubusercontent.com/u/102849?v=3","gravatar_id":"","url":"https://api.github.com/users/bobot","html_url":"https://github.com/bobot","followers_url":"https://api.github.com/users/bobot/followers","following_url":"https://api.github.com/users/bobot/following{/other_user}","gists_url":"https://api.github.com/users/bobot/gists{/gist_id}","starred_url":"https://api.github.com/users/bobot/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/bobot/subscriptions","organizations_url":"https://api.github.com/users/bobot/orgs","repos_url":"https://api.github.com/users/bobot/repos","events_url":"https://api.github.com/users/bobot/events{/privacy}","received_events_url":"https://api.github.com/users/bobot/received_events","type":"User","site_admin":false},"repo":{"id":14594404,"name":"ocaml","full_name":"bobot/ocaml","owner":{"login":"bobot","id":102849,"avatar_url":"https://avatars.githubusercontent.com/u/102849?v=3","gravatar_id":"","url":"https://api.github.com/users/bobot","html_url":"https://github.com/bobot","followers_url":"https://api.github.com/users/bobot/followers","following_url":"https://api.github.com/users/bobot/following{/other_user}","gists_url":"https://api.github.com/users/bobot/gists{/gist_id}","starred_url":"https://api.github.com/users/bobot/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/bobot/subscriptions","organizations_url":"https://api.github.com/users/bobot/orgs","repos_url":"https://api.github.com/users/bobot/repos","events_url":"https://api.github.com/users/bobot/events{/privacy}","received_events_url":"https://api.github.com/users/bobot/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/bobot/ocaml","description":"Read-only mirror of INRIA SVN","fork":true,"url":"https://api.github.com/repos/bobot/ocaml","forks_url":"https://api.github.com/repos/bobot/ocaml/forks","keys_url":"https://api.github.com/repos/bobot/ocaml/keys{/key_id}","collaborators_url":"https://api.github.com/repos/bobot/ocaml/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/bobot/ocaml/teams","hooks_url":"https://api.github.com/repos/bobot/ocaml/hooks","issue_events_url":"https://api.github.com/repos/bobot/ocaml/issues/events{/number}","events_url":"https://api.github.com/repos/bobot/ocaml/events","assignees_url":"https://api.github.com/repos/bobot/ocaml/assignees{/user}","branches_url":"https://api.github.com/repos/bobot/ocaml/branches{/branch}","tags_url":"https://api.github.com/repos/bobot/ocaml/tags","blobs_url":"https://api.github.com/repos/bobot/ocaml/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/bobot/ocaml/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/bobot/ocaml/git/refs{/sha}","trees_url":"https://api.github.com/repos/bobot/ocaml/git/trees{/sha}","statuses_url":"https://api.github.com/repos/bobot/ocaml/statuses/{sha}","languages_url":"https://api.github.com/repos/bobot/ocaml/languages","stargazers_url":"https://api.github.com/repos/bobot/ocaml/stargazers","contributors_url":"https://api.github.com/repos/bobot/ocaml/contributors","subscribers_url":"https://api.github.com/repos/bobot/ocaml/subscribers","subscription_url":"https://api.github.com/repos/bobot/ocaml/subscription","commits_url":"https://api.github.com/repos/bobot/ocaml/commits{/sha}","git_commits_url":"https://api.github.com/repos/bobot/ocaml/git/commits{/sha}","comments_url":"https://api.github.com/repos/bobot/ocaml/comments{/number}","issue_comment_url":"https://api.github.com/repos/bobot/ocaml/issues/comments{/number}","contents_url":"https://api.github.com/repos/bobot/ocaml/contents/{+path}","compare_url":"https://api.github.com/repos/bobot/ocaml/compare/{base}...{head}","merges_url":"https://api.github.com/repos/bobot/ocaml/merges","archive_url":"https://api.github.com/repos/bobot/ocaml/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/bobot/ocaml/downloads","issues_url":"https://api.github.com/repos/bobot/ocaml/issues{/number}","pulls_url":"https://api.github.com/repos/bobot/ocaml/pulls{/number}","milestones_url":"https://api.github.com/repos/bobot/ocaml/milestones{/number}","notifications_url":"https://api.github.com/repos/bobot/ocaml/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/bobot/ocaml/labels{/name}","releases_url":"https://api.github.com/repos/bobot/ocaml/releases{/id}","created_at":"2013-11-21T17:21:31Z","updated_at":"2014-04-04T16:31:18Z","pushed_at":"2015-12-01T14:34:52Z","git_url":"git://github.com/bobot/ocaml.git","ssh_url":"git@github.com:bobot/ocaml.git","clone_url":"https://github.com/bobot/ocaml.git","svn_url":"https://github.com/bobot/ocaml","homepage":null,"size":89407,"stargazers_count":0,"watchers_count":0,"language":"OCaml","has_issues":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":1,"forks":0,"open_issues":1,"watchers":0,"default_branch":"feature/ephemeron_kn"}},"base":{"label":"ocaml:trunk","ref":"trunk","sha":"42ebc0469bd89b89c33a2e0fcf758c9f1c654113","user":{"login":"ocaml","id":1841483,"avatar_url":"https://avatars.githubusercontent.com/u/1841483?v=3","gravatar_id":"","url":"https://api.github.com/users/ocaml","html_url":"https://github.com/ocaml","followers_url":"https://api.github.com/users/ocaml/followers","following_url":"https://api.github.com/users/ocaml/following{/other_user}","gists_url":"https://api.github.com/users/ocaml/gists{/gist_id}","starred_url":"https://api.github.com/users/ocaml/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ocaml/subscriptions","organizations_url":"https://api.github.com/users/ocaml/orgs","repos_url":"https://api.github.com/users/ocaml/repos","events_url":"https://api.github.com/users/ocaml/events{/privacy}","received_events_url":"https://api.github.com/users/ocaml/received_events","type":"Organization","site_admin":false},"repo":{"id":6786166,"name":"ocaml","full_name":"ocaml/ocaml","owner":{"login":"ocaml","id":1841483,"avatar_url":"https://avatars.githubusercontent.com/u/1841483?v=3","gravatar_id":"","url":"https://api.github.com/users/ocaml","html_url":"https://github.com/ocaml","followers_url":"https://api.github.com/users/ocaml/followers","following_url":"https://api.github.com/users/ocaml/following{/other_user}","gists_url":"https://api.github.com/users/ocaml/gists{/gist_id}","starred_url":"https://api.github.com/users/ocaml/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ocaml/subscriptions","organizations_url":"https://api.github.com/users/ocaml/orgs","repos_url":"https://api.github.com/users/ocaml/repos","events_url":"https://api.github.com/users/ocaml/events{/privacy}","received_events_url":"https://api.github.com/users/ocaml/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/ocaml/ocaml","description":"The core OCaml system: compilers, runtime system, base libraries","fork":false,"url":"https://api.github.com/repos/ocaml/ocaml","forks_url":"https://api.github.com/repos/ocaml/ocaml/forks","keys_url":"https://api.github.com/repos/ocaml/ocaml/keys{/key_id}","collaborators_url":"https://api.github.com/repos/ocaml/ocaml/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/ocaml/ocaml/teams","hooks_url":"https://api.github.com/repos/ocaml/ocaml/hooks","issue_events_url":"https://api.github.com/repos/ocaml/ocaml/issues/events{/number}","events_url":"https://api.github.com/repos/ocaml/ocaml/events","assignees_url":"https://api.github.com/repos/ocaml/ocaml/assignees{/user}","branches_url":"https://api.github.com/repos/ocaml/ocaml/branches{/branch}","tags_url":"https://api.github.com/repos/ocaml/ocaml/tags","blobs_url":"https://api.github.com/repos/ocaml/ocaml/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/ocaml/ocaml/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/ocaml/ocaml/git/refs{/sha}","trees_url":"https://api.github.com/repos/ocaml/ocaml/git/trees{/sha}","statuses_url":"https://api.github.com/repos/ocaml/ocaml/statuses/{sha}","languages_url":"https://api.github.com/repos/ocaml/ocaml/languages","stargazers_url":"https://api.github.com/repos/ocaml/ocaml/stargazers","contributors_url":"https://api.github.com/repos/ocaml/ocaml/contributors","subscribers_url":"https://api.github.com/repos/ocaml/ocaml/subscribers","subscription_url":"https://api.github.com/repos/ocaml/ocaml/subscription","commits_url":"https://api.github.com/repos/ocaml/ocaml/commits{/sha}","git_commits_url":"https://api.github.com/repos/ocaml/ocaml/git/commits{/sha}","comments_url":"https://api.github.com/repos/ocaml/ocaml/comments{/number}","issue_comment_url":"https://api.github.com/repos/ocaml/ocaml/issues/comments{/number}","contents_url":"https://api.github.com/repos/ocaml/ocaml/contents/{+path}","compare_url":"https://api.github.com/repos/ocaml/ocaml/compare/{base}...{head}","merges_url":"https://api.github.com/repos/ocaml/ocaml/merges","archive_url":"https://api.github.com/repos/ocaml/ocaml/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/ocaml/ocaml/downloads","issues_url":"https://api.github.com/repos/ocaml/ocaml/issues{/number}","pulls_url":"https://api.github.com/repos/ocaml/ocaml/pulls{/number}","milestones_url":"https://api.github.com/repos/ocaml/ocaml/milestones{/number}","notifications_url":"https://api.github.com/repos/ocaml/ocaml/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/ocaml/ocaml/labels{/name}","releases_url":"https://api.github.com/repos/ocaml/ocaml/releases{/id}","created_at":"2012-11-20T22:18:22Z","updated_at":"2015-12-04T11:49:39Z","pushed_at":"2015-12-04T15:52:04Z","git_url":"git://github.com/ocaml/ocaml.git","ssh_url":"git@github.com:ocaml/ocaml.git","clone_url":"https://github.com/ocaml/ocaml.git","svn_url":"https://github.com/ocaml/ocaml","homepage":"","size":160158,"stargazers_count":567,"watchers_count":567,"language":"OCaml","has_issues":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":200,"mirror_url":null,"open_issues_count":73,"forks":200,"open_issues":73,"watchers":567,"default_branch":"trunk"}},"_links":{"self":{"href":"https://api.github.com/repos/ocaml/ocaml/pulls/22"},"html":{"href":"https://github.com/ocaml/ocaml/pull/22"},"issue":{"href":"https://api.github.com/repos/ocaml/ocaml/issues/22"},"comments":{"href":"https://api.github.com/repos/ocaml/ocaml/issues/22/comments"},"review_comments":{"href":"https://api.github.com/repos/ocaml/ocaml/pulls/22/comments"},"review_comment":{"href":"https://api.github.com/repos/ocaml/ocaml/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/ocaml/ocaml/pulls/22/commits"},"statuses":{"href":"https://api.github.com/repos/ocaml/ocaml/statuses/9c8231755b578d6cf54cd4467535ffa621c625e1"}}}}