{"id":37214,"date":"2022-10-04T15:00:34","date_gmt":"2022-10-04T19:00:34","guid":{"rendered":"https:\/\/mjtsai.com\/blog\/?p=37214"},"modified":"2022-10-04T15:00:12","modified_gmt":"2022-10-04T19:00:12","slug":"accidentally-quadratic-kvo","status":"publish","type":"post","link":"https:\/\/mjtsai.com\/blog\/2022\/10\/04\/accidentally-quadratic-kvo\/","title":{"rendered":"Accidentally Quadratic KVO"},"content":{"rendered":"<p><a href=\"https:\/\/twitter.com\/_saagarjha\/status\/1577087596118781953\">Saagar Jha<\/a>:<\/p>\n<blockquote cite=\"https:\/\/twitter.com\/_saagarjha\/status\/1577087596118781953\"><p>Here&rsquo;s an interesting instance of quadratic complexity: adding and removing KVO observers on an object (FB11644022). A graph of its performance as I scale the number of observations is so perfect it could probably feel right at home in an algorithmic complexity textbook!<\/p><p>It&rsquo;s probably not surprising in the least that observers are stored internally in a set of hash tables. But when you add observations on an object, part of the lookup process calls for computing a hash value over all the observers. This <em>would<\/em> be <em>O(n)<\/em> on each KVO update except Foundation caches this hash value whenever the observers change, so lookups are <em>O(1)<\/em>. This is good, except this just hoists the (one-time) <em>O(n)<\/em> calculation on each update of the observers, because adding and removing observers causes a full rehash.<\/p><p>[&#8230;]<\/p><p>By the way, if you&rsquo;re interested in how KVO is implemented, you can reverse Foundation like I did&#8230;or find out after some searching that someone has basically <a href=\"https:\/\/github.com\/renjinkui2719\/DIS_KVC_KVO\">decompiled the entire thing<\/a>[&#8230;]<\/p><\/blockquote>\n\n<p><a href=\"https:\/\/twitter.com\/kcase\/status\/1577356740928364544\">Ken Case<\/a>:<\/p>\n<blockquote cite=\"https:\/\/twitter.com\/kcase\/status\/1577356740928364544\"><p>Ventura fixes an issue (FB9876193) where KVO rehashing would trigger 300-1400 autoreleases per operation while rebucketing, leading to a performance cliff where we&rsquo;d see hundreds of millions of pending <code>NSKeyValueObservationInfo<\/code> releases.<\/p><\/blockquote>","protected":false},"excerpt":{"rendered":"<p>Saagar Jha: Here&rsquo;s an interesting instance of quadratic complexity: adding and removing KVO observers on an object (FB11644022). A graph of its performance as I scale the number of observations is so perfect it could probably feel right at home in an algorithmic complexity textbook!It&rsquo;s probably not surprising in the least that observers are stored [&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":"2022-10-04T18:59:36Z","apple_news_api_id":"dffe706a-9f89-47ba-a2b8-c052ea995cb6","apple_news_api_modified_at":"2022-10-04T19:00:15Z","apple_news_api_revision":"AAAAAAAAAAAAAAAAAAAAAA==","apple_news_api_share_url":"https:\/\/apple.news\/A3_5wap-JR7qiuMBS6plctg","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":[69,31,2185,275,30,2077,2223,74,138,71],"class_list":["post-37214","post","type-post","status-publish","format-standard","hentry","category-programming-category","tag-cocoa","tag-ios","tag-ios-16","tag-keyvalueobserving","tag-mac","tag-macos-12","tag-macos-13-ventura","tag-opensource","tag-optimization","tag-programming"],"apple_news_notices":[],"_links":{"self":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/37214","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=37214"}],"version-history":[{"count":1,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/37214\/revisions"}],"predecessor-version":[{"id":37215,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/37214\/revisions\/37215"}],"wp:attachment":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/media?parent=37214"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/categories?post=37214"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/tags?post=37214"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}