Prime numbers (unit magnitude) unfit for standardization

[JohelEGP]

Prime numbers (unit magnitude) unfit for standardization

The current mp-units library (v2.0), since #300,
implements the amount of an unit, its magnitude, as a sum of prime numbers.
[ Note:
10 km = 10⋅10³ m = 10 000 m.
In code, 10 km is 10⋅10³ m, a quantity with runtime value 10 and compile-time values 10³ m.
10³ is the magnitude of the unit m.
-- end note ]

P2980 R0 and R1 mention, in "Plan for standardization" (§8 and §9, respectively),

2024.1 (Tokyo) | Paper on prime numbers to SG6

What follows are my opinions, previously voiced and still unchanged.
What's changed since then is the appearance of P2980 with the quote above.
The exchanges sparked by my opinions gained me some insights.
This issue themes my insights around the expectation of std::quantity.

The implementation uses known_first_factor.
It is to be specialized for prime numbers it can't compute due to limits.
Before v2.0, it was exercised at

mp-units/test/unit_test/static/magnitude_test.cpp

Lines 30 to 31 in 5cc7fb1

	template<>
	inline constexpr std::optional<std::intmax_t> units::known_first_factor<9223372036854775783> = 9223372036854775783;

mp-units/test/unit_test/static/magnitude_test.cpp

Lines 181 to 193 in 5cc7fb1

	// SECTION("Can bypass computing primes by providing known_first_factor<N>")
	// {
	// // Sometimes, even wheel factorization isn't enough to handle the compilers' limits on constexpr steps and/or
	// // iterations. To work around these cases, we can explicitly provide the correct answer directly to the
	// compiler.
	// //
	// // In this case, we test that we can represent the largest prime that fits in a signed 64-bit int. The reason
	// this
	// // test can pass is that we have provided the answer, by specializing the `known_first_factor` variable template
	// // above in this file.
	// mag<9'223'372'036'854'775'783>();
	// }
	// }

I have argued that such an interface is unfit for standardization.
I suggested that the unit magnitude should be implementation-defined
(with minimal requirements, e.g., at least as much support as std::chrono::duration with std::ratio;
possibly with implementation-defined limits https://wg21.link/implimits).
My intent was to allow for better implementations to emerge.
@mpusz rightly argued that it would make for less portable code as the limits of implementations diverge.

Considering this, for standardization, I think we're left with a single option.
Standardize the current implementation as-is.
Code will be portable, with the limits of the unit magnitude fixed
(and with known_first_factor for working around those limits).

The intent of the "Paper on prime numbers to SG6" is to make
the would-be implementation-defined interfaces std::quantity uses for unit magnitudes
just another library part of the C++ standard library.
But I think those prime number interfaces are unfit for standardization.

And so, I have thought, can't we use expression templates instead of prime numbers?
There remains the need to simplify (which #300 achieved by definition).
There remains the need to tell whether two magnitudes are equal.
Or maybe we could fall back to using expression templates when specializing known_first_factor would be needed.

I'm not sure what we would lose by foregoing #300 for expression templates on the unit magnitudes.
Would we have to use more explicit casts?
How would it affect what can be done by the library?
I'd like to know that in terms of possibility, simplicity, and safety.
Would it make existing use cases impossible to express, or
would it actually permit more without going through known_first_factor?
For certain, if we had to use more explicit casts, it wouldn't be simpler.
And if we had to use more casts, we'd shadow the casts with actual safety concerns.

[chiphogg]

I have argued that such an interface is unfit for standardization.

I can't tell: are you saying that known_first_factor is "unfit for standardization", or vector space magnitudes generally?

[JohelEGP]

I have argued that such an interface is unfit for standardization.

I can't tell: are you saying that known_first_factor is "unfit for standardization", or vector space magnitudes generally?

A definite yes for the former (again, my own opinion).
The latter one,

For the latter one,
"vector space magnitudes", which must refer to the current implementation with prime numbers,
I'm torn.
That's why this issue is in this repository.
The reference design for std::quantity is this mp-units library.
So the last two paragraphs in the opening comment
are dedicated to possible alternatives and musings
that should be addressed in this library for the sake of standardization.
Should, not must;
as suggested, I'm not against standardizing it as an implementation detail.
Even if known_first_factor has to be exposed.

I do find it unfortunate to close the door to improvements.
Said otherwise, that the C++ standard library can't evolve.

[chiphogg]

I think the unfitness of known_first_factor for standardization is a consensus opinion on our team, including me.

The plan for the prime number paper is to outline the problem that motivated known_first_factor, and to suggest two possible solutions.

1. A dedicated standard library function that provides the first prime factor for any integer. (Perhaps it can use "compiler magic" in the implementation.)
2. Some standardized way for an author to guarantee that a given section of (compile-time executed) code will terminate, and that the compiler should therefore not use a heuristic iteration limit there.

These aren't mutually exclusive, but either is sufficient to obviate known_first_factor.

As for vector space magnitudes; well, it's the only known solution that satisfies our most basic requirements. Namely:

• Closed under products and rational powers.
• Unique representation for each number.
• Able to compute the represented value, for storage in a numeric type.

(These are off the top of my head; there may be one or two more.)

If there's a viable alternative to vector space magnitudes (using prime numbers as a basis for that vector space), then I think we'd need to see an implementation and get real-world experience with it.

[JohelEGP]

The plan for the prime number paper is to outline the problem that motivated known_first_factor, and to suggest two possible solutions.

This is good.
I didn't know it had developed into its own effort.
That means I'm wrong here:

The intent of the "Paper on prime numbers to SG6" is to make
the would-be implementation-defined interfaces std::quantity uses for unit magnitudes
just another library part of the C++ standard library.

1. A dedicated standard library function that provides the first prime factor for any integer.  (Perhaps it can use "compiler magic" in the implementation.)

I was under the impression that some WG21 papers treated primers.
I couldn't find anything.
So perhaps I'm misremembering https://www.reddit.com/r/cpp/comments/pan4al/would_stdis_prime_be_a_good_addition_to_the/.

Ah, but https://cpplang.slack.com/archives/C2PQKRWJU/p1518448215000036 does mention "the prime testing paper".
So maybe it just never became a P-paper.

You might want to get in contact with those folks,
although your paper would be more than "prime testing".

2. Some standardized way for an author to guarantee that a given section of (compile-time executed) code will terminate, and that the compiler should therefore not use a heuristic iteration limit there.

This might not be a good strategy.
I remember raising the limit of Clang.
I think it was for my own implementation of a constexpr bigint
for use in unit magnitudes and just general goodness.
IIRC, the compile-time got exponentially worse.
My guess is that they chose a limit that's still performant.

[mpusz]

Hi everyone.

Thank you, @JohelEGP, for raising your concerns. It is always good to get feedback if something doesn't look right or seems wrong.

It is also important for all of us to stay on the same page. Missing one or two online meetings may be enough to fall behind the discussions and then be confused about the general direction. I would like to encourage everyone to raise their concerns (if there are any), as @JohelEGP just did. Thanks to that, we can improve or clarify the issues.

Said that, I think that this time, we are dealing with the miscommunication issue, and it seems we have a coherent view of how to proceed with magnitudes.

Regarding P2980, it says:

Paper on prime numbers to SG6

but it also says in External dependencies:

Feature	Priority	Description
Compile-time prime numbers	1	Compile-time facilities to break any integral value to a product of prime numbers and their powers

As @chiphogg mentioned above, this is not about standardizing our algorithm as a part of the units library. It is about getting tools to implement this not only by us but by any other vendor in a portable way.

The implementation uses known_first_factor.

Yes, this is really unfortunate, and that is why we want to provide the above paper to SG6 to get compile-time-friendly utilities in the language that would allow a better implementation of vector space magnitudes without the need for such customization points.

I have argued that such an interface is unfit for standardization.

Totally agree.

I suggested that the unit magnitude should be implementation-defined

That is what #505 is about. The user-facing interface should use expression templates, which will improve the readability of generated types and will hide the actual algorithm below. Please share feedback there if you have some ideas on how to improve this feature.

As we can't be sure that someone will not find a better algorithm for expressing magnitudes in the future and clearly we are not fully satisfied with the exciting solution (even though it works), we always planned to make it implementation-defined.
As @JohelEGP said,

I do find it unfortunate to close the door to improvements.
Said otherwise, that the C++ standard library can't evolve.

We should prevent that. We already made many errors in the C++ standard library by standardizing the implementation details (e.g. std::map), and now we can't improve the library because of it. We should prevent that if only possible.

Moreover, we also ask SG6 for guidance on this subject with "Unit magnitudes" chapter in P2982. Maybe the Committee members or some readers of this paper will be able to come up with some improvements.

[JohelEGP]

I suggested that the unit magnitude should be implementation-defined

That is what #505 is about.

Not really.
That's just improving an user-facing part.
By "unit magnitude should be implementation-defined"
I mean being able to change the back-end used to implement unit magnitude.

For example, at some point in the future,
I might once again explore using a SAS (#377 (comment)).
I think it's possible to build something better.

[mpusz]

That's just improving an user-facing part.

I am not sure if I agree with that. We have to standardize the user-facing part somehow. Expression templates could be the official interface. Breaking it to powers of prime numbers done under the hood should be implementation-defined and not standardized. I think that is consistent with what you propose?

[JohelEGP]

In that case, yes, I agree it's the right direction.

[chiphogg]

Ah, but https://cpplang.slack.com/archives/C2PQKRWJU/p1518448215000036 does mention "the prime testing paper". So maybe it just never became a P-paper.

You might want to get in contact with those folks, although your paper would be more than "prime testing".

Sorry, I can't view this link.

2. Some standardized way for an author to guarantee that a given section of (compile-time executed) code will terminate, and that the compiler should therefore not use a heuristic iteration limit there.

This might not be a good strategy. I remember raising the limit of Clang. I think it was for my own implementation of a constexpr bigint for use in unit magnitudes and just general goodness. IIRC, the compile-time got exponentially worse. My guess is that they chose a limit that's still performant.

That's fascinating! I have a hard time understanding how raising the iteration limit for a linear algorithm could lead to exponentially worse performance. Maybe your algorithm was different?

[JohelEGP]

That's fascinating! I have a hard time understanding how raising the iteration limit for a linear algorithm could lead to exponentially worse performance. Maybe your algorithm was different?

I suppose the it's because I tested the compilers' behavior with this quadratic algorithm.
It's a nested loop calculating i * j.

constexpr unsigned f() {
  unsigned res = 0;
  for (unsigned i = 0; i != MAX; ++i)
    for (unsigned j = 0; j != MAX; ++j)
      res = i * j;
  return res;
}
#if defined(__GNUC__) && !defined(__clang__)
constexpr unsigned i = f();
int main() { return i; }
#endif

These are the times:

$ time clang++ -std=c++20 -c x.cpp -DMAX=1000

real  0m2.241s
user  0m2.215s
sys 0m0.020s
$ time clang++ -std=c++20 -c x.cpp -DMAX=2000 -fconstexpr-steps=5000000

real  0m9.272s
user  0m9.242s
sys 0m0.020s
$ time g++ -std=c++20 -c x.cpp -DMAX=1000

real  0m1.177s
user  0m1.131s
sys 0m0.015s
$ time g++ -std=c++20 -c x.cpp -DMAX=2000 -fconstexpr-ops-limit=100000000

real  0m4.653s
user  0m4.601s
sys 0m0.035s

Compiler	MAX	Steps/limit	Time
Clang	1000	?	2.241s
Clang	2000	5000000	9.272s
GCC	1000	33554432	1.177s
GCC	2000	100000000	4.653s

Once you need to raise the limit, times just get much worse.
Granted, it's a quadratic algorithm.
But if you need to raise the limit,
even for a O(N) algorithm,
compile times will be very sensitive to any constant.

In my example here,
raising MAX from 1000 to 2000
is like switching from int to unsigned
to gain that extra bit for non-negative numbers.
You'll run out of it again soon.

[chiphogg]

Is that a valid test? With the iteration limit for compilers, the failure mode isn't "gracefully exit the loop". The failure mode is "produce a hard compiler error".

Maybe this would be a better test?

constexpr unsigned f() {
  unsigned res = 0;
  for (unsigned i = 0; i != MAX; ++i)
    for (unsigned j = 0; j != i; ++j)
      res = i * j;
  return res;
}
#if defined(__GNUC__) && !defined(__clang__)
constexpr unsigned i = f();
int main() { return i; }
#endif

It would be interesting to see how long it takes to find the largest "first prime factor" in uint64_t. I guess the way to go would be something like:

• Find the largest prime in uint32_t
• Cast it to uint64_t and square it
• Raise the iteration limit and find the first prime factor

This would be a good data point on the feasibility of this approach. I think I'll need to get around to doing this for the prime paper.