Pass by Reference vs Pass by Value Computational Speed

Question

Hi
I have these two codes that produce all combinations for pairs in a multimap. The first one passes the multimap by value:
https://code.sololearn.com/ca10a22A72A1
and the second one by reference:
https://code.sololearn.com/ca1A13a09a16
When I run them, the pass-by-reference one seems to run much faster, just by naively subtracting the end and start times (see the end of both of the code outputs for the time calculation). Why is this?

Answer 1

passing by value means copying the values themselves (so the function do not modify original values but only copy of them), while passing by reference means copying only the addresses of the values...

in case of data structures, that means passing by reference copy only a pointer, while passing by values copy whole structure: that could make less or more time difference for large data structures and or lot of calls to the function ;)

Answer 2

In the first code, the whole std::multimap is copied to make a new one. So the multimap used in Combi() is not the one that was made in main(), they are copies of each other. In fact, the multimap being used in main() is copied each time you pass it to Combi() (4 times according to the for-loop in your code and more in recursion).

In the second one, it is not copied. The multimap that is being used in main() is being used in Combi().

Naturally, as no copy is created when using references, it will be faster. Much faster as the multimap is being copied several times in the first code, and the time for copying each time has to be taken into consideration.

The time taken for copying a structure can be quite significant, which is why it is recommended to use references wherever you don't want a new copy of the structure instance.

Answer 3

Thanks visph and XXX, that makes sense. So it seems to me that if the data being copied is large like an array or multimap then it pays to pass it by reference, whereas non-container variables should be passed by value unless there is a need to change its value in the function?

Answer 4

yes, if you make attention to not change the values if that's not intended ;P

Answer 5

... but that's often makes only micro-optimisations wich are not so often needed: algorithms used to do the computations is mostly the source of loose of times ^^

Answer 6

I didn't said that your algorithm is not good, i just said that often it's more important to focus on algorithm than to such micro-optimisation ;)

in fact, I did not even have looked at your codes ;P

Answer 7

ok: so your data structure should be very big to make so much diffrence ^^

Answer 8

(also, as you call the function recursively to do combinations, the number of call would be very big too ^^)

Answer 9

Yes, that must be the reason, thanks!

Answer 10

visph Ah, but in this case the difference is quite substantial. You may argue that the algorithm is recursive so inherently inefficient, but I tried iterative approaches in the internet that in practice were both 2x slower than this recursive function, though if you have suggestions to make it faster I would of course welcome that :)

Answer 11

visph Ok. But I think you might be surprised if you look at the two codes 🤔

Answer 12

maybe I would be, maybe not: I'm very few experiemented in c/c++, and I don't be aware of 'multimap', so I guess I will not understand enough well your code ;)

Answer 13

visph Ok fine I will stop bothering you 😔. The point I was hoping you would see is that in this example, pass by reference is literally 100 times faster than pass by value. At the very bottom of the output is the time taken for the computation.