{"comment":{"url":"https://api.github.com/repos/dlibenzi/akaros/comments/13773385","html_url":"https://github.com/dlibenzi/akaros/commit/2b7e6c06c689a7b386d4fed5c9613b17bf2916fb#commitcomment-13773385","id":13773385,"user":{"login":"dlibenzi","id":14933084,"avatar_url":"https://avatars.githubusercontent.com/u/14933084?v=3","gravatar_id":"","url":"https://api.github.com/users/dlibenzi","html_url":"https://github.com/dlibenzi","followers_url":"https://api.github.com/users/dlibenzi/followers","following_url":"https://api.github.com/users/dlibenzi/following{/other_user}","gists_url":"https://api.github.com/users/dlibenzi/gists{/gist_id}","starred_url":"https://api.github.com/users/dlibenzi/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/dlibenzi/subscriptions","organizations_url":"https://api.github.com/users/dlibenzi/orgs","repos_url":"https://api.github.com/users/dlibenzi/repos","events_url":"https://api.github.com/users/dlibenzi/events{/privacy}","received_events_url":"https://api.github.com/users/dlibenzi/received_events","type":"User","site_admin":false},"position":null,"line":null,"path":"","commit_id":"2b7e6c06c689a7b386d4fed5c9613b17bf2916fb","created_at":"2015-10-14T17:28:26Z","updated_at":"2015-10-14T17:28:26Z","body":"It mostly depends on the size of the array, and the access pattern. I would\nsay in the majority of cases yes, otherwise O(N) would rule data structures.\nUnless you means sorted array, which has similar lookup complexity, but\nworse insert/remove ones. This is why no known, non toy, VM implementation\nuses arrays for VMA management.\nRB (but mostly many other implementations as well) trees have predictable\nlatency.\nI chose RB trees because they are the ones I used most, and because they\nare used in the VM I know better (the Linux one). Which is not too shabby\nin terms of scalability ☺\n\n\nOn Wed, Oct 14, 2015 at 9:39 AM, Dan Cross <notifications@github.com> wrote:\n\n> I'm not sure if github sent my comment (above); perhaps if I write here it\n> will.\n>\n> —\n> Reply to this email directly or view it on GitHub\n> <https://github.com/dlibenzi/akaros/commit/2b7e6c06c689a7b386d4fed5c9613b17bf2916fb#commitcomment-13772308>\n> .\n>\n"}}