More ergonomic / convenient STL algorithm calls -- sort order & member field extraction using std::invoke

Question

While we patiently wait for ranges in C++20, it can still get somewhat frustrating to write begin(), end() and micro-lambdas to specify "sort order" and "field extraction".

It is the latter, "field extraction" which I find is very commonly needed, but rarely discussed. The C++11 lambda has made it easier but the syntax is still very verbose for a very common task. There was even a recent slack/cpplang question about it. Inspired by a comment in Sean Parent's famous Seasoning talk, where he suggested using std::bind to abstract this syntax, I looked into modern alternatives. std::bind has a bad name for being large and slow. More modern is std::invoke from C++17.

So my proof of concept below tries to get to some terser syntax for these common operations using std::invoke.

I am looking for feedback on:

• Coding style
• Constraining that template - with / without c++20 concepts (it's wide open right now)
• The new, terser calling syntax for STL algos which operate on some user defined class and require field/member extraction and potentially sorting on those.
• std::sort is just one example. This could work for std::accumulate or anything really. Would I need up to 115 such wrapper templates? is there a better way.

Code size may still be a concern (even with std::invoke rather than std::bind) as shown by the the generated ASM here. The base case of the traditional lambda generates ~2000 lines of assembly code (LOA). Then each of the "new syntax" lines generates a further 2000 LOA -bringin it to ~8000 LOA in total for clang-9 -O3. Because the sortby template is stamped out for each type of lambda.

I haven't measured performance. Will all this code slow it down significantly with a lot of boilerplate and indirection, or is it just code size that suffers?

EDIT: Benchmark data has now been added below.

#include <algorithm>
#include <functional>
#include <iostream>
#include <ostream>
#include <string>
#include <vector>

struct Employee {
  int         id;
  std::string firstname;
  std::string lastname;
  int         yob;

  [[nodiscard]] int getAge() const noexcept { return 2020 - yob; }

  friend std::ostream& operator<<(std::ostream& stream, const Employee& e) {
    return stream << e.id << ", " << e.firstname << ", " << e.lastname << ", " << e.yob << ", "
                  << e.getAge();
  }
};

namespace os::algo {

// the following 6 lines make it possible
template <typename Container, typename Member, typename Comparison = std::less<>>
void sortby(Container& c, Member&& m, Comparison comp = Comparison()) {
  std::sort(c.begin(), c.end(), [&m, &comp](const auto& a, const auto& b) {
    return comp(std::invoke(m, a), std::invoke(m, b));
  });
}

} // namespace os::algo

int main() {

  using os::algo::sortby;

  auto employees = std::vector<Employee>{
      {1, "James", "Smith", 2008},
      {2, "John", "Jones", 1998},
      {3, "Sarah", "Evans", 1968},
      {4, "Michelle", "Harris", 1978},
  };

  // BEFORE: This is what's required with normal STL calls
  std::sort(employees.begin(), employees.end(),
            [](const auto& a, const auto& b) { return a.firstname < b.firstname; });

  // AFTER: and now we can do this...

  // the easy part -- no begin(), end()

  // trivial, terse sorting by any member field
  sortby(employees, &Employee::firstname);

  // trivially specify sort direction
  sortby(employees, &Employee::yob, std::greater<>());

  // can use getters too
  sortby(employees, &Employee::getAge, std::greater<>());

  for (const auto& e: employees) std::cout << e << "\n";

  // std::sort is but one example. The same technique applies to any STL algorithm

  return 0;
}

Answer 1

Indeed, your sortby when used in the style shown, with data members, will not be quite as fast as if you used the STL with a lambda. Look at the difference in assembly between

struct Date {
    int year, month, day;
};

void test1(std::array<Date, 100>& a) {
    sortby(a, &Date::month);
    sortby(a, &Date::year);
}

void test2(std::array<Date, 100>& a) {
    sortby(a, [](const auto& x){ return x.month; });
    sortby(a, [](const auto& x){ return x.year; });
}

In test1, the difference between &Date::month and &Date::year is encoded in the runtime value of the member pointer. In test2, the difference is encoded in the compile-time type of the lambda. So test2 instantiates two different template instantiations, whereas test1 calls the same instantiation twice with different inputs. (But if both calls are inlined, the optimizer might be able to hide the difference.)

However, this is not the fault of your sortby helper; it's the fault of using member pointers instead of custom lambdas. You can observe the same differences happening if you call std::sort with a function pointer, versus calling std::sort with an instance of some bespoke type such as std::less<> or std::greater<>.

---

You pass Member&& m by forwarding reference, but then you use it as an lvalue (without forwarding it again). I think I've mentioned before: if you don't intend to forward an argument, then you shouldn't be using a forwarding reference with it. In this case, you just need to look at the value of the member-pointer m without modifying it, so const Member& m would be appropriate. Or, since member data pointers and custom lambdas are both going to be small trivial types, and member function pointers are also trivial types (if slightly larger), we should seriously think about taking Member m directly by value.

Notice that you already take Comparison comp by value.

The comment about using std::begin(c) over c.begin() is accurate. If you want your sortby template to work for C-style arrays, then you should use std::begin(c). Remember, you can't pass arrays by value (they decay to pointers) — but you can certainly pass arrays by reference, and that's what you're doing here when you sortby an array "in place."

The vast majority of lambdas you write should just take [&]. I don't see any benefit to writing [&m, &comp] when it ends up meaning the same thing as [&].

So I'd write your helper like this:

template<class Container, class Member, class Comparison = std::less<>>
void sortby(Container& c, Member m, Comparison comp = Comparison()) {
    using std::begin; using std::end;
    std::sort(begin(c), end(c), [&](const auto& a, const auto& b) {
        return comp(std::invoke(m, a), std::invoke(m, b));
    });
}

using std::begin; is the "std::swap two-step," familiar to anyone who's used std::swap before. It means "consider using std::begin for unqualified calls, but if someone has provided a better-matching ADL version of begin, then we'll happily use that version instead." This is certainly overkill — I mean we could just write std::begin(c), std::end(c), — but the two-step is how all the standard customization points are meant to be used as far as I know, so we might as well stick to it.

Vice versa, I would personally shy away from using the two-step in main —

using os::algo::sortby;

This seems more confusing than helpful. Are you expecting that someone else might provide a better-matching ADL sortby? If not, then sortby(x,y,z) will always mean os::algo::sortby(x,y,z)... and if it is os::algo::sortby, why not say so?

Answer 2

Some benchmarking data as promised:

Cut to the chase, results:

--------------------------------------------------------
Benchmark              Time             CPU   Iterations
--------------------------------------------------------
stl/100             3940 ns         3940 ns       173735
member/100          4756 ns         4756 ns       147187
lambda/100          3979 ns         3979 ns       177405
getter/100          8768 ns         8768 ns        79665
stlgetter/100       3993 ns         3993 ns       179926

Summary:

• Passing a member variable to the helper does incur a cost (~15-20%, and ~ 10% for bigger containers) as predicted by @Quuxplusone and using a lambda (ie fixing the offset in a distinct compile time type) does get rid of that extra cost (back to normal STL levels).
• Slight shock (for me at least) was that passing the address of a getter into our helper slows things down by ~2x. Put in an extra benchmark with the STL using the getters, and as expected that is ~nil cost compared to base case.

Attempt at a conclusion:

• This is not a zero cost abstraction.
• However, for the most commonly requested use-case (eg slack/cpplang query), which is "sort by this public member", there is "only" a 15-20% (and ~10% for bigger containers) penalty relative to a custom lambda, but this has a code size benefit and is not actually caused by the abstraction as such (but to do with static/runtime resolution of the "address").
• passing "getters" seems to have a weirdly large costs, needs further investigation.

Here is the benchmark code (using Google Benchmark):

#include <algorithm>
#include <benchmark/benchmark.h>
#include <functional>
#include <iostream>
#include <random>
#include <vector>

struct Date {
  int year, month, day;
  [[nodiscard]] int get_year() const noexcept { return year; }
  [[nodiscard]] int get_month() const noexcept { return month; }
  [[nodiscard]] int get_day() const noexcept { return day; }
};

namespace os::algo {

// the following 6 lines make it possible
template <typename Container, typename Member, typename Comparison = std::less<>>
void sortby(Container& c, const Member& m, const Comparison& comp = Comparison()) {
  std::sort(std::begin(c), std::end(c), [&](const auto& a, const auto& b) {
    return comp(std::invoke(m, a), std::invoke(m, b));
  });
}

} // namespace os::algo

std::vector<Date> get_random_dates(std::size_t size) {
  std::random_device                 rnd_device;
  std::mt19937                       engine{1}; // rnd_device()};
  std::uniform_int_distribution<int> year_dist{1940, 2025};
  std::uniform_int_distribution<int> month_dist{1, 12};
  std::uniform_int_distribution<int> day_dist{1, 28}; // ignore complexities

  auto dates = std::vector<Date>{};
  dates.reserve(size);
  for (std::size_t i = 0; i < size; ++i) {
    dates.push_back({year_dist(engine), month_dist(engine), day_dist(engine)});
  }
  return dates;
}

void stl(benchmark::State& state) {
  auto ds = get_random_dates(state.range(0));
  for (auto _: state) {
    std::sort(ds.begin(), ds.end(), [](const auto& a, const auto& b) { return a.month < b.month; });
    std::sort(ds.begin(), ds.end(), [](const auto& a, const auto& b) { return a.year < b.year; });
  }
}
BENCHMARK(stl)->Arg(100);

void member(benchmark::State& state) {
  auto ds = get_random_dates(state.range(0));
  for (auto _: state) {
    os::algo::sortby(ds, &Date::month);
    os::algo::sortby(ds, &Date::year);
  }
}
BENCHMARK(member)->Arg(100);

void lambda(benchmark::State& state) {
  auto ds = get_random_dates(state.range(0));
  for (auto _: state) {
    os::algo::sortby(ds, [](const auto& x) { return x.month; });
    os::algo::sortby(ds, [](const auto& x) { return x.year; });
  }
}
BENCHMARK(lambda)->Arg(100);

void getter(benchmark::State& state) {
  auto ds = get_random_dates(state.range(0));
  for (auto _: state) {
    os::algo::sortby(ds, &Date::get_month);
    os::algo::sortby(ds, &Date::get_year);
  }
}
BENCHMARK(getter)->Arg(100);

void stlgetter(benchmark::State& state) {
  auto ds = get_random_dates(state.range(0));
  for (auto _: state) {
    std::sort(ds.begin(), ds.end(), [](const auto& a, const auto& b) { return a.get_month() < b.get_month(); });
    std::sort(ds.begin(), ds.end(), [](const auto& a, const auto& b) { return a.get_year() < b.get_year(); });
  }
}
BENCHMARK(stlgetter)->Arg(100);

I also did a quick study on code size. I compiled a stripped down version of above code (no random gen, and no google benchmark lib) using clang-9 with -O3 and checked the binary executable size. I commented out all sorting for the base case and then uncommented each one of the methods in turn. As well as binary size I recorded "lines of assembly" (LOA) shown in godbolt.

Results:

// base size without any sort function: 17248 bytes / 219 LOA

// size with stl: 21864 bytes / 1913 LOA

// size with member: 17984 bytes / 970 LOA

// size with lambda: 22072 bytes / 1941 LOA

// size with getter: 22656 bytes / 1128 LOA

The only anomaly is the highest binary size and very low LOA for "getter". But otherwise this makes sense. Generally:

"Info encoded in Fixed types" (ie lambdas) => 
bigger binary => 
higher LOA => 
and (from above) faster performance 

This "code size conclusion" is quite different from my initial impression in the original post. There I thought that the sortby helper was increasing code size. It is not. If that was really happening it was a compiler optimisation artefact. This more proper test shows the logical conclusion just above.