{"id":13720,"date":"2016-03-01T14:19:35","date_gmt":"2016-03-01T19:19:35","guid":{"rendered":"http:\/\/mjtsai.com\/blog\/?p=13720"},"modified":"2016-03-01T21:33:20","modified_gmt":"2016-03-02T02:33:20","slug":"fast-ordered-collections-for-swift-using-in-memory-b-trees","status":"publish","type":"post","link":"https:\/\/mjtsai.com\/blog\/2016\/03\/01\/fast-ordered-collections-for-swift-using-in-memory-b-trees\/","title":{"rendered":"Fast Ordered Collections for Swift Using In-memory B-trees"},"content":{"rendered":"<p><a href=\"https:\/\/github.com\/lorentey\/BTree#laundry-list-of-issues-with-standard-collection-types\">K&aacute;roly L&#337;rentey<\/a> (via <a href=\"https:\/\/twitter.com\/nicklockwood\/status\/704445016735924224\">Nick Lockwood<\/a>):<\/p>\n<blockquote cite=\"https:\/\/github.com\/lorentey\/BTree#laundry-list-of-issues-with-standard-collection-types\"><p>The benchmark above demonstrates this really well: insertion into a sorted array is O(n^2) when there are\nmany items, but it is still much faster than a red-black tree with its attractive-looking O(n * log(n)) \nsolution. At the beginning of the curve, up to about <em>eighteen thousand items<\/em>, a sorted array \nimplementation imported from an external module is very consistently about 6-7 faster than a red-black tree, \nwith a slope that is indistinguishable from O(n * log(n)). Even after it catches up to quadratic complexity, \nit takes about a <em>hundred thousand items<\/em> for the sorted array to become slower than the red-black tree!\nThis remarkable result is due in large part to the vast number of (to a CPU, random-looking) memory references that are\nneeded to operate on red-black trees.<\/p><p>[&#8230;]<\/p><p>Note that the big gap between collections imported from stdlib and those imported from external modules is caused by a limitation in the current Swift compiler\/ABI: when this limitation is lifted, the gap will narrow considerably, which will reduce the element count at which you&rsquo;ll be able to reap the benefits of lower asymptotic complexity.<\/p><p>[&#8230;]<\/p><p>The all-or-nothing <a href=\"https:\/\/en.wikipedia.org\/wiki\/Copy-on-write\">copy-on-write behavior<\/a> of <code>Array<\/code>, <code>Dictionary<\/code> and <code>Set<\/code> can lead to performance problems\nthat are hard to detect and fix.\nIf the underlying storage buffer is being shared by multiple collection instances, the modification of a single element \nin any of the instances requires creating a full copy of every element. <\/p><p>It is not at all obvious from the code when this happens, and it is even harder to reliably check for. \nYou can&rsquo;t (easily) write unit tests to check against accidental copying of items with value semantics!<\/p><p>With standard collection types, you often need to think about memory management.<\/p><\/blockquote>","protected":false},"excerpt":{"rendered":"<p>K&aacute;roly L&#337;rentey (via Nick Lockwood): The benchmark above demonstrates this really well: insertion into a sorted array is O(n^2) when there are many items, but it is still much faster than a red-black tree with its attractive-looking O(n * log(n)) solution. At the beginning of the curve, up to about eighteen thousand items, a sorted [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"apple_news_api_created_at":"","apple_news_api_id":"","apple_news_api_modified_at":"","apple_news_api_revision":"","apple_news_api_share_url":"","apple_news_coverimage":0,"apple_news_coverimage_caption":"","apple_news_is_hidden":false,"apple_news_is_paid":false,"apple_news_is_preview":false,"apple_news_is_sponsored":false,"apple_news_maturity_rating":"","apple_news_metadata":"\"\"","apple_news_pullquote":"","apple_news_pullquote_position":"","apple_news_slug":"","apple_news_sections":"\"\"","apple_news_suppress_video_url":false,"apple_news_use_image_component":false,"footnotes":""},"categories":[4],"tags":[289,263,74,138,71,901],"class_list":["post-13720","post","type-post","status-publish","format-standard","hentry","category-programming-category","tag-algorithm","tag-theory","tag-opensource","tag-optimization","tag-programming","tag-swift-programming-language"],"apple_news_notices":[],"_links":{"self":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/13720","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/comments?post=13720"}],"version-history":[{"count":1,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/13720\/revisions"}],"predecessor-version":[{"id":13721,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/13720\/revisions\/13721"}],"wp:attachment":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/media?parent=13720"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/categories?post=13720"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/tags?post=13720"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}