{"action":"created","issue":{"url":"https://api.github.com/repos/rust-lang/rust/issues/29454","labels_url":"https://api.github.com/repos/rust-lang/rust/issues/29454/labels{/name}","comments_url":"https://api.github.com/repos/rust-lang/rust/issues/29454/comments","events_url":"https://api.github.com/repos/rust-lang/rust/issues/29454/events","html_url":"https://github.com/rust-lang/rust/pull/29454","id":114103699,"number":29454,"title":"Fix excessive memory allocation in RawVec::reserve","user":{"login":"stepancheg","id":28969,"avatar_url":"https://avatars.githubusercontent.com/u/28969?v=3","gravatar_id":"","url":"https://api.github.com/users/stepancheg","html_url":"https://github.com/stepancheg","followers_url":"https://api.github.com/users/stepancheg/followers","following_url":"https://api.github.com/users/stepancheg/following{/other_user}","gists_url":"https://api.github.com/users/stepancheg/gists{/gist_id}","starred_url":"https://api.github.com/users/stepancheg/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/stepancheg/subscriptions","organizations_url":"https://api.github.com/users/stepancheg/orgs","repos_url":"https://api.github.com/users/stepancheg/repos","events_url":"https://api.github.com/users/stepancheg/events{/privacy}","received_events_url":"https://api.github.com/users/stepancheg/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":{"login":"aturon","id":709807,"avatar_url":"https://avatars.githubusercontent.com/u/709807?v=3","gravatar_id":"","url":"https://api.github.com/users/aturon","html_url":"https://github.com/aturon","followers_url":"https://api.github.com/users/aturon/followers","following_url":"https://api.github.com/users/aturon/following{/other_user}","gists_url":"https://api.github.com/users/aturon/gists{/gist_id}","starred_url":"https://api.github.com/users/aturon/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/aturon/subscriptions","organizations_url":"https://api.github.com/users/aturon/orgs","repos_url":"https://api.github.com/users/aturon/repos","events_url":"https://api.github.com/users/aturon/events{/privacy}","received_events_url":"https://api.github.com/users/aturon/received_events","type":"User","site_admin":false},"milestone":null,"comments":11,"created_at":"2015-10-29T17:29:18Z","updated_at":"2015-10-30T19:25:35Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/rust-lang/rust/pulls/29454","html_url":"https://github.com/rust-lang/rust/pull/29454","diff_url":"https://github.com/rust-lang/rust/pull/29454.diff","patch_url":"https://github.com/rust-lang/rust/pull/29454.patch"},"body":"Before this patch `reserve` function allocated twice as requested\r\namount elements (not twice as capacity).  It leaded to unnecessary\r\nexcessive memory usage in scenarios like this:\r\n\r\n```\r\nlet mut v = Vec::new();\r\nv.push(17);\r\nv.extend(0..10);\r\nprintln!(\"{}\", v.capacity());\r\n```\r\n\r\n`Vec` allocated 22 elements, while it could allocate just 11.\r\n\r\n`reserve` function must have a property of keeping `push` operation\r\ncost (which calls `reserve`) `O(1)`. To achieve this `reserve` must\r\nexponentialy grow its capacity when it does reallocation.\r\n\r\nThere's better strategy to implement `reserve`:\r\n\r\n```\r\nlet new_capacity = max(current_capacity * 2, requested_capacity);\r\n```\r\n\r\nThis strategy still guarantees that capacity grows at `O(1)` with\r\n`reserve`, and fixes the issue with `extend`.\r\n\r\nPatch imlpements this strategy."},"comment":{"url":"https://api.github.com/repos/rust-lang/rust/issues/comments/152624772","html_url":"https://github.com/rust-lang/rust/pull/29454#issuecomment-152624772","issue_url":"https://api.github.com/repos/rust-lang/rust/issues/29454","id":152624772,"user":{"login":"Gankro","id":1136864,"avatar_url":"https://avatars.githubusercontent.com/u/1136864?v=3","gravatar_id":"","url":"https://api.github.com/users/Gankro","html_url":"https://github.com/Gankro","followers_url":"https://api.github.com/users/Gankro/followers","following_url":"https://api.github.com/users/Gankro/following{/other_user}","gists_url":"https://api.github.com/users/Gankro/gists{/gist_id}","starred_url":"https://api.github.com/users/Gankro/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Gankro/subscriptions","organizations_url":"https://api.github.com/users/Gankro/orgs","repos_url":"https://api.github.com/users/Gankro/repos","events_url":"https://api.github.com/users/Gankro/events{/privacy}","received_events_url":"https://api.github.com/users/Gankro/received_events","type":"User","site_admin":false},"created_at":"2015-10-30T19:25:35Z","updated_at":"2015-10-30T19:25:35Z","body":"r? @bluss \r\n\r\nYou seem to have a good handle on the issues at play here. I skimmed the code but am a bit fuzzy on if this will have the same crash behaviour when inserting into ZST collections. In particular, they rely on RawVec to crash to elide their own overflow checks for `len`."}}