2

There was 5 different versions of pow, in C++98:

double pow (double base, double exponent);
float pow (float base, float exponent);
long double pow (long double base, long double exponent);
double pow (double base, int exponent);
long double pow (long double base, int exponent);

My teacher told me, that before c++11 (before adding template version of pow), there could be an error where c++ can't deduce which overloading to choose. That seemed reasonable to me. For example consider this code:

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    cout << pow(4, 3);
    cin.get();
}

I'm calling pow() function with two integer arguments. I don't have such overloading of pow(), so maybe I should do some implicit conversions? Ok, but which one to choose? I can't choose how to convert since I have ambiguity in choosing of the overloading. But I tried to compile this piece of code (in std=c++98 mode) and it worked. Why?

Ok, maybe it's because of second argument being integer. Therefore I have to choose only between double pow (double base, int exponent) and long double pow (long double base, int exponent). But still which one compiler decides to choose? What if I called pow(4, 3ll)? It still compiles but type deducing for me is less obvious.

upd: Maybe it is a bad idea to see how deducing works here, because I may never know how pow really implemented. Or is it?

Learpcs
  • 282
  • 3
  • 10
  • The behavior is the same for user defined functions, so you can try it out. For example when it is ambiguous: https://godbolt.org/z/GKEdfbs83 – mch Dec 06 '21 at 11:43
  • 2
    [overload_resolution](https://en.cppreference.com/w/cpp/language/overload_resolution) is not a simple subject, when we go into details. – Jarod42 Dec 06 '21 at 11:47
  • 1
    @mch Okey, I see why in your example is ambiguity here. So I decided to do the same but with mine example. And I got the compile error: https://godbolt.org/z/Tz7xhqxce – Learpcs Dec 06 '21 at 11:48

2 Answers2

3

The compiler will use the name pow to find a set of candidate functions. Since you wrote using namespace std; (bad idea) this includes std::pow overloads. There are [edit]at least[/edit] 5 such overloads. (Compilers may add more overloads for efficiency).

Next up, for each overload that can accept 2 arguments, the compiler will determine 2 conversion sequences. So in total the compiler ends up with (at least) 5x2 conversion sequences

In overload resolution, the overload with the best conversion sequences is chosen. This requires that there is one overall winner amongst all overloads. If there is no clear winner, it would be ambiguous. This can easily happen with 5 overloads and 2 conversion sequences each: one overload can have the best conversion sequence for the first sequence, and another overload for the second sequence.

Note that in this case, you expect ties between conversion sequences. For instance,

double pow (double base, double exponent);
double pow (double base, int exponent);

will have the same conversion sequence for their first arguments (in your case, from int to double. Ties are not a big problem , as they will affect only one of the two conversion sequences.

The exact rules for conversion sequences are a bit complicated, but the main rules are: no conversion is best, conversion from floating-point types to integral types or vice versa is not good, user-defined conversions are the worst type of conversion, and if you need more than one type of conversion in a sequence that's even worse.

For pow(3,4) in this example, no user-defined conversions are needed, so the two deciding factors are whether you need any conversion, and if so, if it's a conversion from int to a floating-point type.

The rationale for extra overloads is that some implementations of pow(x,y) can be optimized using pow(x,y)==pow(x*x,y/2). That optimization works best if y is an integer, of course. In particular, this allows the compiler to calculate pow(3,4) as just pow((3*3)*(3*3), 1) . This will still produce 81.0 but it uses integer arithmetic for the intermediate results.

MSalters
  • 173,980
  • 10
  • 155
  • 350
  • The program works even if we remove `using namespace std;` as can be seen [here](https://godbolt.org/z/rsvcssM8K). Can you explain why the program given [here](https://godbolt.org/z/Tz7xhqxce) doesn't not work while the program given by OP(in his/her original question) works. Both program have the same overloads. –  Dec 06 '21 at 16:01
  • @AanchalSharma why does pow works without std? O.o I thought it was some ADL stuff but then realised I can't anyhow look at the right namespace without right arguments. Or maybe when invoking `operator<<` ADL involved here? upd: it works without `cout <<` therefore maybe there's no ADL at all? – Learpcs Dec 06 '21 at 18:58
  • @Learpcs: Backwards compatibility with C. ADL depends on the arguments, and `int` has no associated namespace – MSalters Dec 07 '21 at 11:30
3

tl;dr:

  • std::pow is a difficult example due to compilers providing more overloads & the c version being considered a builtin in gcc, so your problem is rather hard to demonstrate with it.
  • yes the call will actually be ambigous if the 5 functions you listed are the only ones competing in overload resolution.

pow() is a rather tricky function to use for this, since there are a few gotchas:

  • In your godbolt example your actually calling std::pow<int, int>, i.e. a templated version of it. This is because you're using a rather new version of gcc that provides a templated overload of std::pow for better performance.

    You can see this quite nicely in the generated assembly, line 6: (look at the end)

    call    __gnu_cxx::__promote_2<int, int, __gnu_cxx::__promote<int, std::__is_integer<int>::__value>::__type, __gnu_cxx::__promote<int, std::__is_integer<int>::__value>::__type>::__type std::pow<int, int>(int, int)

    So for testing this you could do a few things:

    • switch to an older version of gcc that doesn't have the templated overload yet, i.e. gcc 4.1.2:
      godbolt example
    • or test it with user-specified functions, like the example from @mch:
      godbolt example

  • Another problem is <cmath> itself - since it is the c++ equivalent of <math.h> in c, gcc and clang do expose the c pow function as well in it (without std:: prefix) - this is why your code works even when removing using namespace std;.
    Since c doesn't allow function overloads there's only one version with double's. (the float version is powf, the long double one powl).
    Additionally gcc considers them to be built-ins, so in this case it can just completely get rid of the pow call since it uses constants as arguments, even at -O0.
    This is what happened in the example provided by @ Aanchal Sharma: godbolt example

    mov     rax, QWORD PTR .LC0[rip]
movq    xmm0, rax
// calculated value (64 as a double)
.LC0:
      .long   0
      .long   1078984704

    so gcc just calculated the result at compile-time and inlined it. (note there's no overload resolution problem at all here, since there's only one pow function in c - and the c++ functions aren't available because using namespace std; is not commented in)

    You can suppress this by passing -fno-builtin as a compiler argument, in which case gcc will dutifully emit the call to double pow(double, double): godbolt example

    movsd   xmm0, QWORD PTR .LC0[rip]
mov     rax, QWORD PTR .LC1[rip]
movapd  xmm1, xmm0
movq    xmm0, rax
call    pow

.LC0: // 3 as a double
   .long   0
   .long   1074266112
.LC1: // 4 as a double
   .long   0
   .long   1074790400

So to answer your questions:

1. Why does it work?

Because gcc actually provides a templated overload of std::pow that is a perfect match in this case:

template<typename _Tp, typename _Up>
inline typename __gnu_cxx::__promote_2<_Tp, _Up>::__type pow(_Tp __x, _Up __y);

2. Assuming there would be no template overload, how would the compiler decide which overload to use?

The rules for determining the best overload are rather complicated, so i'll simplify them a bit (i'll completely ignore user-defined conversion functions, templated functions, variadic functions and a few other things not relevant to the question)

If you want to get a more complete picture of the actual rules you can take a look at the c++98 standard, section 13.3 Overload resolution is what you're looking for.

Now to get into it:

  • First all functions are eliminated that don't have the right number of arguments. i.e. if there would be a pow function taking three arguments (and the third argument doesn't have a default value) - it would be directly eliminated.

    13.3.2 Viable functions

    (1) First, to be a viable function, a candidate function shall have enough parameters to agree in number with the arguments in the list.

  • Secondly the parameters you provided actually need to be convertible to the parameters of the overload in question. If there's no way to convert between them the overload would be eliminated.

    13.3.2 Viable functions

    (3) Second, for F to be a viable function, there shall exist for each argument an implicit conversion sequence (13.3.3.1) that converts that argument to the corresponding parameter of F.

  • After that the compiler has a set of overloads left - the standard calls them Viable functions - that could be called in the given context. Now the compiler needs to actually decide which of those is the best one, i.e. the Best Viable Function, that should end up being called.

  • Now we get to the fun part - rating overloads based on how good of a fit they are. There are basically three primary categories a parameter conversion can have:
    Exact Match > Promotion > Conversion ¹

    • Exact Match is the best one, this applies if the types match exactly or if it's just decaying an array to a pointer or function to a function pointer.
    • Promotion is slightly worse, this applies if you e.g. convert from one integral type to a bigger one or from a floating point type to a bigger one (but not between integral and floating points, and not to smaller types)
    • Conversion is the worst one and covers "downgrading" of int and float types (e.g. int -> char, double -> float) and conversion between integral and floating point types, e.g. int -> double.

    The compiler doesn't care what the exact conversion is, only in which of the three categories it falls. ²

    So you could think of it that way: ³

    • Each function gets a score based on the conversions needed for the arguments
    • Exact Match is worth 0 points
    • Promotion is worth -1 points
    • Conversion is worth -2 points
    • the function with the highest score gets called
    • it there's a draw, the call is ambigous

  • So now to actually rank the std::pow overloads:

    // when called as pow(1, 1)

// 2x Conversion -> score -4
double pow (double base, double exponent);

// 2x Conversion -> score -4
float pow (float base, float exponent);

// 2x Conversion -> score -4
long double pow (long double base, long double exponent);

// 1x Conversion, 1x Exact -> score -2
double pow (double base, int exponent);

// 1x Conversion, 1x Exact -> score -2
long double pow (long double base, int exponent);

    So the first 3 are already off the table, because their score is worse.
    This leaves the last 2, but those actually have the same score, so it's a draw!
    -> You'll get an ambigous function call error

Footnotes:
¹ there are a few more rules for user-defined conversion functions, vararg functions and templates
  (see 13.3.3.1 Implicit conversion sequences)
² In reality there are quite a few more things to consider
  (see 13.3.3.2 Ranking implicit conversion sequences for a complete list)
³ Extremely simplified version. This is not how an actual compiler would do it.

Turtlefight
  • 9,420
  • 2
  • 23
  • 40