1

I am a newbie c++ developper transitionning from Fortran. I am trying to write the most efficient possible function to compute the norm of the difference of two compile-time known size std::arrays (typically between 1 and 10, most often < 100). Of course, a simple for-loop easily does the trick, but I wonder how it compares (in terms of efficiency) to more modern style of programming, (possibly using std::accumulate, or std::inner_product ?).

Maybe a simple solution already exists in a dedicated library (like Boost or Eigen) ? I understand too little of those to make sure.

Best,

G. Fougeron
  • 318
  • 1
  • 13
  • 2
    You have to measure to be sure, but I would say they should be equivalent. – Jarod42 Aug 01 '19 at 09:19
  • 1
    If you are wondering then the next step is to try these alternatives and time them. There really is no generally applicable answer to questions about efficiency. – john Aug 01 '19 at 09:19
  • the standard algorithms usually dont perform worse than a handwritten code. The deal is: awesome abstractions for zero overhead. It is **not**: automagically your code gets faster – 463035818_is_not_an_ai Aug 01 '19 at 09:22
  • 1
    Depending on the problem (and the platform you want to solve it on), you can gain some speed by parallelising. Many standard algorithms allow parallelisation via [execution policies](https://en.cppreference.com/w/cpp/algorithm/execution_policy_tag_t) (e. g. [`std::sort`](https://en.cppreference.com/w/cpp/algorithm/sort)), you might use these for. If you find nothing appropriate, there are parallelisation libraries like [Open MP](https://www.openmp.org/). – Aconcagua Aug 01 '19 at 09:36
  • 2
    Something not mentioned yet, if your arrays are filled (or can be filled) at compile time, you can use `constexpr` to calculate this kind of thing then (no runtime cost!). You will have to write your own function for this as the standard ones are not yet constexpr. See https://stackoverflow.com/questions/33157731/compile-time-equivalent-to-stdaccumulate for details – Madden Aug 01 '19 at 09:45

1 Answers1

2

Both hand-written loops and standard algorithms will most likely result in the same code. In any case, I would not expect a meaningful performance difference on a reasonable compiler.

The real performance gain here will have to come from vectorization.

  • Auto-vectorization varies very strongly between compilers (and may be off by default for floating point operations because those are not associative). In theory, using standard algorithms with the std::execution::parallel_unsequenced_policy (or std::execution::unsequenced_policy in C++20) should hint to the compiler that they can/should vectorize the loop code, but compiler adoption of this is low at the moment.

  • You could hand-write the vectorized code, but that may be tricky to get good/right. It's certainly not a productive investment of your time unless you know the section is performance-critical.

  • Some libraries may already have properly vectorized code for such operations. I would expect Eigen and possibly ublas, armadillo or lapack to have this figured out. But you would have to check them yourself and whether they do what you need for your given platform.

As always: If you care about performance, measure and compare. There is no universal answer.

Max Langhof
  • 23,383
  • 5
  • 39
  • 72