{"id":18831,"date":"2017-09-06T14:59:51","date_gmt":"2017-09-06T18:59:51","guid":{"rendered":"https:\/\/mjtsai.com\/blog\/?p=18831"},"modified":"2017-09-06T15:31:45","modified_gmt":"2017-09-06T19:31:45","slug":"data-locality-and-stl-vs-swift","status":"publish","type":"post","link":"https:\/\/mjtsai.com\/blog\/2017\/09\/06\/data-locality-and-stl-vs-swift\/","title":{"rendered":"Data Locality and STL vs. Swift"},"content":{"rendered":"

David Owens II<\/a> (tweet<\/a>):<\/p>\n

\n

What if I told you that even in an array of 10,000 items and a linked list of 10,000 items, insertion into the middle is still going to be faster in the array? Would you believe me?<\/p>\n

[…]<\/p>\n

The problem is that the -><\/code> operator (de-referrencing) is a relatively expensive operation.<\/p>\n<\/blockquote>\n

He also found that for the simple case of an array of integers, Swift’s Array<\/code> was about half the speed of std::vector<\/code>. This is pretty good, and it looks like there’s room for it to be improved.<\/p>\n

Joe<\/a> Groff<\/a>:<\/p>\n

The optimizer is also not great at telling that insert\/append-type operations maintain uniqueness so it can leave out checks.<\/p><\/blockquote>\n

If you’re seeing protocol overhead it’s probably also failing to specialize something.<\/p><\/blockquote>\n\n

Update (2017-09-06): David Owens II<\/a>:<\/p>\n

Actually, they are even perf now. I was using Int instead of Int32, so the size was 64bits instead of 32bits like the C++ version. 🙄<\/p><\/blockquote>\n\n

Joe<\/a> Groff<\/a>:<\/p>\n

Another linked list variant is a contiguous array of (value, next index) pairs, so you get locality and can efficiently insert by appending<\/p><\/blockquote>\n\n

and you can easily sort in-place into an ordered vector as a pre-pass to benefit from sequential memory access<\/p><\/blockquote>","protected":false},"excerpt":{"rendered":"

David Owens II (tweet): What if I told you that even in an array of 10,000 items and a linked list of 10,000 items, insertion into the middle is still going to be faster in the array? Would you believe me? […] The problem is that the -> operator (de-referrencing) is a relatively expensive operation. […]<\/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,326,263,138,71,901],"class_list":["post-18831","post","type-post","status-publish","format-standard","hentry","category-programming-category","tag-algorithm","tag-c-plus-plus","tag-theory","tag-optimization","tag-programming","tag-swift-programming-language"],"apple_news_notices":[],"_links":{"self":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/18831","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=18831"}],"version-history":[{"count":2,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/18831\/revisions"}],"predecessor-version":[{"id":18838,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/18831\/revisions\/18838"}],"wp:attachment":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/media?parent=18831"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/categories?post=18831"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/tags?post=18831"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}