{"id":106669,"date":"2022-05-18T07:00:00","date_gmt":"2022-05-18T14:00:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/oldnewthing\/?p=106669"},"modified":"2022-05-18T06:33:29","modified_gmt":"2022-05-18T13:33:29","slug":"20220518-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20220518-00\/?p=106669\/","title":{"rendered":"Writing a sort comparison function, part 2: avoid unnecessary expense"},"content":{"rendered":"

Last time, we wrote a basic multi-level sort<\/a>. I reiterate that the best way to do this is not to write your own multi-level comparison function but rather to rely on std::pair<\/code> or std::tuple<\/code> to do the work for you.<\/p>\n

It may be that calculating one of the secondary keys is expensive, and you don’t want to do it unless it turns out to be necessary. In that case, you’ll have to break down the comparison manually into components. But don’t try to be clever about it. Just write the most obvious version:<\/p>\n

\/\/ three-way comparison\r\nint compare_3way_for_sorting(T const& a, T const& b)\r\n{\r\n    \/\/ First compare by name\r\n    if (a.name < b.name) return -1;\r\n    if (a.name > b.name) return +1;\r\n\r\n    \/\/ Names are equal, check connector names\r\n    auto&& a_connector = a.GetConnector();\r\n    auto&& b_connector = b.GetConnector();\r\n\r\n    if (a_connector.name < b_connector.name) return -1;\r\n    if (a_connector.name > b_connector.name) return +1;\r\n\r\n    \/\/ Names and connector names are equal,\r\n    \/\/ check manufacturing date\r\n    auto&& a_date = LookupManufacturingDate(a.part_number);\r\n    auto&& b_date = LookupManufacturingDate(b.part_number);\r\n\r\n    if (a_date < b_date) return -1;\r\n    if (a_date > b_date) return +1;\r\n\r\n    \/\/ All keys match\r\n    return 0;\r\n}\r\n\r\n\/\/ less-than comparison\r\nbool compare_less_for_sorting(T const& a, T const& b)\r\n{\r\n    \/\/ First compare by name\r\n    if (a.name < b.name) return true;\r\n    if (a.name > b.name) return false;\r\n\r\n    \/\/ Names are equal, check connector names\r\n    auto&& a_connector = a.GetConnector();\r\n    auto&& b_connector = b.GetConnector();\r\n\r\n    if (a_connector.name < b_connector.name) return true;\r\n    if (a_connector.name > b_connector.name) return false;\r\n\r\n    \/\/ Names and connector names are equal,\r\n    \/\/ check manufacturing date\r\n    auto&& a_date = LookupManufacturingDate(a.part_number);\r\n    auto&& b_date = LookupManufacturingDate(b.part_number);\r\n\r\n    if (a_date < b_date) return true;\r\n    if (a_date > b_date) return false;\r\n\r\n    \/\/ All keys match\r\n    return false;\r\n}\r\n<\/pre>\n
I’ve seen code that tried to do the multi-level comparison manually, but they were too clever and tried to cram it all into one line for style points, but messed it up. Resist the temptation to earn style points. Write the simplest, most straightforward code. Not only is it easier for humans to understand, it’s also  easier for the compiler to understand<\/a>.<\/p>\n
Next time, we’ll look at how to do this with spaceships.<\/p>\n
Bonus chatter<\/b>: I considered embracing the “Don’t do this, just use tuples” principle by creating a delayed-comparison wrapper:<\/p>\n
template<typename Lambda>\r\nstruct defer_comparison\r\n{    \r\n    defer_comparison(Lambda lambda) : key(std::move(lambda)){}\r\n    Lambda key;\r\n\r\n    auto operator<=>(defer_comparison const& other) const\r\n        { return compare_3way(key(), other.key() ); }\r\n};\r\n \r\nauto key(T const& t)\r\n{\r\n    return std::make_tuple(std::ref(t.name),\r\n                          defer_comparison([&] { return t.GetConnector(); }),\r\n                          defer_comparison([&] { return LookupManufacturingDate(t.part_number); }));\r\n}\r\n\r\nstd::weak_ordering\r\ncompare_3way_for_sorting(T const& a, T const& b)\r\n{\r\n    return key(a) <=> key(b);\r\n}\r\n\r\nbool compare_less_for_sorting(T const& a, T const& b)\r\n{\r\n    return key(a) < key(b);\r\n}\r\n<\/pre>\n
However, this generates unnecessary calls to Get\u00adConnector()<\/code> and Lookup\u00adManufacturingsDate()<\/code> because it breaks down as<\/p>\n
bool compare_less_for_sorting(T const& a, T const& b)\r\n{\r\n    auto a_tuple = key(a);\r\n    auto b_tuple = key(b);\r\n\r\n    if (std::get<0>(a) < std::get<0>(b)) return true;\r\n    if (std::get<0>(a) > std::get<0>(b)) return false;\r\n\r\n    if (std::get<1>(a) < std::get<1>(b)) return true;\r\n    if (std::get<1>(a) > std::get<1>(b)) return false;\r\n\r\n    if (std::get<2>(a) < std::get<2>(b)) return true;\r\n    if (std::get<2>(a) > std::get<2>(b)) return false;\r\n\r\n    return false;\r\n}\r\n<\/pre>\n
In our case, std::get<1>()<\/code> returns a defer_comparison<\/code>, so we end up comparing the same two defer_comparison<\/code> objects twice.<\/p>\n
We could try to solve this by using a std::async<\/code> with deferred execution to memoize the result of the lambda, but this introduces extra memory allocations and virtual function tables and memory barriers, so it feels like we’d be heading in the wrong direction.<\/p>\n","protected":false},"excerpt":{"rendered":"
Avoid doing the work until needed.<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-106669","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
Avoid doing the work until needed.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/106669","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=106669"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/106669\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=106669"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=106669"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=106669"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}