{"id":11903,"date":"2015-08-01T11:36:58","date_gmt":"2015-08-01T15:36:58","guid":{"rendered":"http:\/\/mjtsai.com\/blog\/?p=11903"},"modified":"2015-08-03T09:50:32","modified_gmt":"2015-08-03T13:50:32","slug":"swift-array-performance","status":"publish","type":"post","link":"https:\/\/mjtsai.com\/blog\/2015\/08\/01\/swift-array-performance\/","title":{"rendered":"Swift Array Performance"},"content":{"rendered":"

Airspeed Velocity<\/a>:<\/p>\n

\n

Your reminder that building arrays with reduce, while fun, is accidentally quadratic.<\/p>\n<\/blockquote>\n

I would have thought that extending an array would be optimized to not make a copy.<\/p>\n

Update (2015-08-01): Joe Groff<\/a>:<\/p>\n

I don’t think +<\/code> is implemented to check for unique referencing at all.<\/p><\/blockquote>\n

Update (2015-08-03): Airspeed Velocity<\/a> (tweet<\/a>):<\/p>\n

I was surprised at how surprising some found this. Quite a few people suggested the reduce<\/code> version could be changed to not do the array copy (I don’t think<\/em> it can). Some suggested maybe +<\/code> could be optimized so it doesn’t perform a copy (I don’t think that it could easily, as we’ll see shortly).<\/p>\n

[…]<\/p>\n

Assuming combine<\/code> here is { $0 + [transform($1)] }<\/code>, you can see that +<\/code> similarly has no knowledge of the fact that we’re actually going to assign the outcome directly to the result<\/code> variable. We know, on inspecting the code, that it’ll just be fine to add the right-hand side onto the left-hand side, if that were even possible (in theory it is, since even though the array is passed immutably by value, the buffer is a class and so could be mutated since it has reference semantics). But +<\/code> can’t know that from where it sits. It definitely knows it’s copy of the left-hand side isn’t the only owner of the buffer. There is another owner too: reduce<\/code> holds a copy of result<\/code> – and is about to throw it away and replace it with a new result, but that’s coming after<\/em> +<\/code> has run.<\/p><\/blockquote>\n

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

Swift’s parameter convention is callee-release, so isUniquelyRefd can work inside +. It’d only succeed if + is the last use.<\/p><\/blockquote>\n

That optimization could lead to optimizer-dependent algorithmic complexity though, sorta like TCO.<\/p><\/blockquote>\n

“TCO” refers to tail call optimization<\/a>.<\/p>","protected":false},"excerpt":{"rendered":"

Airspeed Velocity: Your reminder that building arrays with reduce, while fun, is accidentally quadratic. I would have thought that extending an array would be optimized to not make a copy. Update (2015-08-01): Joe Groff: I don’t think + is implemented to check for unique referencing at all. Update (2015-08-03): Airspeed Velocity (tweet): I was surprised […]<\/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":[46,138,71,901],"class_list":["post-11903","post","type-post","status-publish","format-standard","hentry","category-programming-category","tag-languagedesign","tag-optimization","tag-programming","tag-swift-programming-language"],"apple_news_notices":[],"_links":{"self":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/11903","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=11903"}],"version-history":[{"count":3,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/11903\/revisions"}],"predecessor-version":[{"id":11919,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/11903\/revisions\/11919"}],"wp:attachment":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/media?parent=11903"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/categories?post=11903"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/tags?post=11903"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}