Fibonacci memoization - pass by lvalue vs rvalue reference-CodePudding

I'm learning about memoization and decided to apply this technique to a recursive function calculating the n-th Fibonacci number. I am not sure whether I should pass my memo map by lvalue reference or rvalue reference.
Is there any difference (regarding performance and generally how the program behaves) in the two snippets presented below? Which one would be preferred? Also, is there a way to provide a default argument to the first function (map& memo = map{} doesn't work because an lvalue reference doesn't bind with an rvalue...)?

Version #1

using map = std::unordered_map<int, unsigned long long>;
unsigned long long fib(int n, map& memo){
    if(memo.find(n) != memo.cend()) return memo[n];
    if(n <= 2) return 1;
    memo[n] = fib(n - 1, memo)   fib(n - 2, memo);
    return memo[n];
}

Version #2

using map = std::unordered_map<int, unsigned long long>;
unsigned long long fib(int n, map&& memo = map{}){
    if(memo.find(n) != memo.cend()) return memo[n];
    if( n <= 2) return 1;
    memo[n] = fib(n - 1, std::move(memo))   fib(n - 2, std::move(memo));
    return memo[n];
}

CodePudding user response：

In C , moving an object corresponds to the following contract:

I am never planning on using this object again. Person I am moving the object to: you are free to do whatever you'd like with this object's resources. I promise not to use the object again without first assigning it a new value, so I will never see the effects of anything you did. So please, do Cruel and Unusual things to my object if it makes you happy.

Now, consider this line of code:

memo[n] = fib(n - 1, std::move(memo))   fib(n - 2, std::move(memo));

Here, you are calling std::move(memo), which signals "I promise never to use memo again." However, in the same line of code, you are then assigning to memo[n], which means that you are indeed planning on using memo later. That breaks the contract that you're making with whomever you std::move the object to. Imagine this as a dialog between you and the calls to Fibonacci:

You: Hey, Mr. Fibonacci! I got you a memoization table. It's 100% yours and I am never going to use it again.
Fibonacci: Great! Thanks!
You: Okay, now that I just gave you the memoization table, I'd like to paint it blue and put flowers on it.
Fibonacci: Wait, hold on! It's not your table any more!
You: Well, I'm going to do it anyway.
Fibonacci: Why, you little! (Violence ensues)

So, yeah. That's not going to work.

Ignoring the assignment to memo[n], there's another issue here. You are trying to move the same object twice to two different people. Think about what that means from the perspective of a conversation between you, the first call to Fibonacci, and the second call to Fibonacci.

You: Hey, Mr. First Call to Fibonacci! Here's memo. It's yours. Do whatever you'd like with it. No one else is going to see it.
Mr. First Call to Fibonacci: Woohoo! That's awesome!
You: Hey, Mr. Second Call to Fibonacci! Here's memo. It's yours. Do whatever you'd like with it. No one else is going to see it.
Mr. Second Call to Fibonacci: Woohoo! That's awesome!
Mr. First Call to Fibonacci: Wait, hold on! They gave me that object! They can't give it to you!
Mr. Second Call to Fibonacci: Weren't you listening? They just gave me that object! It's mine!
Mr. First Call to Fibonacci: Why, you little! (Violence ensues)

So yeah, that isn't going to end well. :-)

Fundamentally, only use std::move when you or anyone else is planning on using that object again. In the case of memoization, when a bunch of function calls all need to coordinate to share the same memoization table across the calls, that requirement isn't held, so you shouldn't use rvalue semantics here.