Signature Question

[habemus-papadum]

Thanks very much for posting your code -- it is very helpful and fun to study! I have a small question...

Q: Is there are reason you chose to define the signature as:

template <class BidirIter, class Function>
Function
for_each_permutation(BidirIter first, BidirIter mid,
                     BidirIter last, Function f)

instead of using references for Function e.g.:

template <class BidirIter, class Function>
Function &
for_each_permutation(BidirIter first, BidirIter mid,
                     BidirIter last, Function &f)

I noticed the return std::move(f); but its proper usage is not something I fully understand (every time I've tried return std::move(...), clang says I'm being silly...).

Anyway, apologies in advance for asking a c++ question rather than a combinatorics question -- i've got those as well, but this was the first hurdle I hit...

cheers, nehal

[HowardHinnant]

The Function& f signature wouldn't bind to rvalue functions which I expect to be popular now as it could be a temporary lambda (which is a rvalue).

On the second question clang is right. I should change this to just return f; This library was written prior to a language change that said that this form of return would implicitly move. I should change the code to reflect that.

[habemus-papadum]

(I feel less silly for having tried return std:move(...))

What you consider the following thoughts about the signature:

template <class BidirIter, class Function>
void
for_each_permutation(BidirIter first, BidirIter mid,
                     BidirIter last, const Function &f)

So, in this case, one might rewrite the example app as:

const int r = 3;
const int n = 5;
std::uint64_t count = 0; 
std::vector<int> v(n);
std::iota(v.begin(), v.end(), 0);
for_each_permutation(
   v.begin(),
   v.begin() + r,
   v.end(),
   [&](auto first, auto last) {
     count++;
     display(first, last);
   });
std::cout << "Found " << count << std::endl;

Reasoning I've notice a couple of new languages (Swift in the llvm world and Kotlin in the jvm world; I'm sure there are others) allow the programmer to annotate a function parameter (typically of callable type) as "non-escaping" (similar to how c++ provides annotation facilities such as const, noexcept, etc.).

"non-escaping" is meant to indicate (in effect) that the callable object may be used by the function, but no references are kept to the object pass the function invocation. These languages then guarantee that when such functions are called with lambda's -- the entire function application is always inlined and the lambda is utilized "directly" (i.e. also inlined)

In the case of Swift, this allows it to, for instance, ban c-style for-loops(!), and rather force programmers to encapsulate their control flow constructs as functions that take non-escaping callables (and presumably these control-flow functions have descriptive names such as for_each_permutation) but incur no performance penalty for this increased abstraction. (I suppose you might already know all of this...)

Now, I don't know to what extent current C++ compilers are able to detect non-escaping lambdas and do similar optimizations, or whether this might possibly become part of the language spec, but I do think it is one of the more clever things that swift/kotlin are doing and marketing, and should be leeched by C++ if it has not already (I won't be surprised if C++ invented this...).

A step in this direction might be to write control flow libraries (which is how I think of combinatorics) in a way that would benefit should these optimization guarantees become part of the spec.

cheers, nehal

[HowardHinnant]

It appears to me that "non-escaping" in Swift mimics pass-by-value in C++. The function gets a possibly moved-from copy of the argument, and then no one else in the program has a reference to that argument inside the function. Now for_each_permutation can do non-const things with that argument and it does't impact that outside world (the call operator is allowed to be non-const).

But just in case it is a stateful functor, for_each_permutation passes the functor back to the caller at the end so that the caller can observe the new state if desired.

I like the pass-by-value signature much better.

[habemus-papadum]

gets a possibly moved-from copy

Ok -- I think this is the source of my confusion. I hadn't considered an invocation of the form: f = for_each_permutation(..., std::move(f)) which presumably involves only moves going in and moves going out -- I now see that is in fact quite a useful pattern to add to my repertoire -- thanks!

--
Separately, I still feel there is something to be said for worrying about the whether the callable gets "inlined" either via explicit guarantee or at least in practice on most modern compliers. (Here's an analogy/use case, simulating a classical physical system might involve 6 nested for-loops, simulating a quantum system might involve iterating over of k combinations of n vectors -- in both scenarios, the underlying "physics" is modeled by what gets done in the innermost loop and is usually quite simple (evaluating a linear function or some low order polynomial) -- i.e. ideally you want to structure your code so that you have the flexibility to try variations to the inner logic, but also don't want to pay the price of 100,000,000 function calls. At this point I don't quite know enough to predict what is the best way to proceed in c++, but I think I have enough to do a few experiments and look at the disassembly.

I really appreciate your pointers!

[HowardHinnant]

I too have been frustrated with the C++ inline facility. inline is a hint and not a directive. For many programmers, this actually allows better code generation because too many programmers tend to overuse inline simply because it is syntactically easier to write (e.g. write all your member functions within the class declaration).

For those of us who use inline judiciously it can be very frustrating when the compiler refuses to actually inline a function. I've been known to reach for compiler-specific "always inline" syntax for some cases.