{"action":"created","issue":{"url":"https://api.github.com/repos/ocaml-batteries-team/batteries-included/issues/560","labels_url":"https://api.github.com/repos/ocaml-batteries-team/batteries-included/issues/560/labels{/name}","comments_url":"https://api.github.com/repos/ocaml-batteries-team/batteries-included/issues/560/comments","events_url":"https://api.github.com/repos/ocaml-batteries-team/batteries-included/issues/560/events","html_url":"https://github.com/ocaml-batteries-team/batteries-included/issues/560","id":32146935,"number":560,"title":"BatHashtbl modify functions never resize","user":{"login":"jj-issuu","id":5585703,"avatar_url":"https://avatars.githubusercontent.com/u/5585703?v=3","gravatar_id":"","url":"https://api.github.com/users/jj-issuu","html_url":"https://github.com/jj-issuu","followers_url":"https://api.github.com/users/jj-issuu/followers","following_url":"https://api.github.com/users/jj-issuu/following{/other_user}","gists_url":"https://api.github.com/users/jj-issuu/gists{/gist_id}","starred_url":"https://api.github.com/users/jj-issuu/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jj-issuu/subscriptions","organizations_url":"https://api.github.com/users/jj-issuu/orgs","repos_url":"https://api.github.com/users/jj-issuu/repos","events_url":"https://api.github.com/users/jj-issuu/events{/privacy}","received_events_url":"https://api.github.com/users/jj-issuu/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/ocaml-batteries-team/batteries-included/labels/performance%20bug","name":"performance bug","color":"e11d21"}],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":3,"created_at":"2014-04-24T13:12:51Z","updated_at":"2015-11-05T10:21:02Z","closed_at":null,"body":"The functions `modify_opt` and `modify_def` in BatHashtbl never resize the hash table, so they have O(n) performance if the table is never modified through a function like `add` or `replace`. This should at the very least be documented, but resizing really must be implemented in order for those functions to be useful.\r\n\r\nLooking at the source code, it's hard to see how to keep the non-inserting case highly efficient while also supporting resize and not depending too much on implementation details of stdlib/hashtbl.ml.\r\n\r\nPerhaps the most robust solution is to implement  `modify_opt` and `modify_def` through the standard add/remove/replace/find functions. This makes the non-inserting cases slower but keeps all cases at O(1) average."},"comment":{"url":"https://api.github.com/repos/ocaml-batteries-team/batteries-included/issues/comments/154018888","html_url":"https://github.com/ocaml-batteries-team/batteries-included/issues/560#issuecomment-154018888","issue_url":"https://api.github.com/repos/ocaml-batteries-team/batteries-included/issues/560","id":154018888,"user":{"login":"jj-issuu","id":5585703,"avatar_url":"https://avatars.githubusercontent.com/u/5585703?v=3","gravatar_id":"","url":"https://api.github.com/users/jj-issuu","html_url":"https://github.com/jj-issuu","followers_url":"https://api.github.com/users/jj-issuu/followers","following_url":"https://api.github.com/users/jj-issuu/following{/other_user}","gists_url":"https://api.github.com/users/jj-issuu/gists{/gist_id}","starred_url":"https://api.github.com/users/jj-issuu/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jj-issuu/subscriptions","organizations_url":"https://api.github.com/users/jj-issuu/orgs","repos_url":"https://api.github.com/users/jj-issuu/repos","events_url":"https://api.github.com/users/jj-issuu/events{/privacy}","received_events_url":"https://api.github.com/users/jj-issuu/received_events","type":"User","site_admin":false},"created_at":"2015-11-05T10:21:02Z","updated_at":"2015-11-05T10:21:02Z","body":"I think the changes in #603 optimized this code so much that it can't be considered a performance bug. There's still room for improvement, but that would come at a high cost in code complexity and dependence on how Hashtbl is implemented in the standard library.\r\nIMHO, this issue can be closed."}}