{"action":"created","issue":{"url":"https://api.github.com/repos/ocaml/ocaml/issues/368","labels_url":"https://api.github.com/repos/ocaml/ocaml/issues/368/labels{/name}","comments_url":"https://api.github.com/repos/ocaml/ocaml/issues/368/comments","events_url":"https://api.github.com/repos/ocaml/ocaml/issues/368/events","html_url":"https://github.com/ocaml/ocaml/pull/368","id":123520158,"number":368,"title":"Improve the speed of register allocation","user":{"login":"mshinwell","id":1315488,"avatar_url":"https://avatars.githubusercontent.com/u/1315488?v=3","gravatar_id":"","url":"https://api.github.com/users/mshinwell","html_url":"https://github.com/mshinwell","followers_url":"https://api.github.com/users/mshinwell/followers","following_url":"https://api.github.com/users/mshinwell/following{/other_user}","gists_url":"https://api.github.com/users/mshinwell/gists{/gist_id}","starred_url":"https://api.github.com/users/mshinwell/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mshinwell/subscriptions","organizations_url":"https://api.github.com/users/mshinwell/orgs","repos_url":"https://api.github.com/users/mshinwell/repos","events_url":"https://api.github.com/users/mshinwell/events{/privacy}","received_events_url":"https://api.github.com/users/mshinwell/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/ocaml/ocaml/labels/flambda-weak-prerequisite","name":"flambda-weak-prerequisite","color":"d4c5f9"}],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":19,"created_at":"2015-12-22T17:09:01Z","updated_at":"2015-12-28T16:22:12Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/ocaml/ocaml/pulls/368","html_url":"https://github.com/ocaml/ocaml/pull/368","diff_url":"https://github.com/ocaml/ocaml/pull/368.diff","patch_url":"https://github.com/ocaml/ocaml/pull/368.patch"},"body":"The increased compilation time spent in Flambda passes has prompted us to look for any other places in the compilation pipeline where time may be saved.  This is particularly important in two cases:\r\n(a) emulating the existing \"Closure\" mode;\r\n(b) otherwise, when significantly larger amounts of code may be generated due to increased inlining.\r\n\r\nI tried changing [Interf] so instead of using a set it used a hash table.  This gave a significant speed-up in register allocation.  Then I tried something else, shown in this patch: just use a large array unless the number of pseudoregisters is very large.  By using bytes instead of whole words to represent the interference matrix, and a trick to avoid having to clear the array, performance seems to be improved without excessive memory consumption.  @lpw25 notes that the code could perhaps be improved by not just ditching the array when lots of registers are required, but still using it for the first (say) 4000.\r\n\r\nI used the new \"-dtimings\" option to count up the \"regalloc\" time for building the components of ocamlopt.opt (133 source files, not including the standard library).  This patch reduces the time spent in that pass by a modest 70%."},"comment":{"url":"https://api.github.com/repos/ocaml/ocaml/issues/comments/167597778","html_url":"https://github.com/ocaml/ocaml/pull/368#issuecomment-167597778","issue_url":"https://api.github.com/repos/ocaml/ocaml/issues/368","id":167597778,"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-28T16:22:11Z","updated_at":"2015-12-28T16:22:11Z","body":" My only concern is @xavierleroy <https://github.com/xavierleroy> comments\n> about the worst-case behavior of hash tables. Xavier: has it been an issue\n> in practice?\n>\n Yes, see Mantis PR#2470.  (You still haven't read \"git log asmcomp/\ninterf.ml\", have you?)  This said, the custom hash function used back then\nwas truly horrible; don't repeat that mistake.\n"}}