Fix #580 by using a fixed-point implementation for unit conversions using integer representations

[burnpanck]

This PR provides an implementation of what I played with in this comment to issue 580. Basically, it completely distinguishes floating-point and integral paths. For floating-point paths, the conversion implementation remains the same (a single multiplication with a floating-point representation of the conversion factor). For the integral paths, it now also uses a single multiplication, but now with a fixed-point representation. (mixed conversions take the floating-point path). Fixed-point multiplications have the advantage that they are comparatively cheap (much cheaper than a division) and can accurately describe all reasonable conversion factors between two n-bit numbers using a n.n (2n total) fixed-point representation. Unreasonable conversion factors are those larger than 2^n or smaller than 2^-n, i.e. those which either overflow for all input values or underflow for all input values. The cost of such a fixed-point multiplication is at most that of 4x n-bit integer multiplication plus some bookkeeping if their output is restricted to n-bit (as in the C++ standard; unlike typical hardware); if the output of a n-bit multiplication can be 2n (most instruction-sets provide those), it will just take two of them.

With the implementation change here, the computation of conversions between two quantity types of the same dimension and both integer type stay tightly within the types mandated by the source and destination type, without expanding to intmax unless necessary. In general, this will never cause overflows unless the result type actually cannot carry the result (the fixed-point multiplication is guaranteed to be sufficient). However, this practice triggered the weakly related #614, where it turned a silent overflow into a compilation failure. For now, this PR just disables those two test. Once we have a fix for that one, we should re-enable those tests and rebase this PR.

[burnpanck]

Most of the review concerns should be fixed now. Also, I "fixed" the CI failure in the trigonometry tests by allowing the affected test-cases to deviate by two instead of one epsilon. I believe this appears because now, for double quantities, the conversion factor is now a double instead of a long double - an intentional change of making the conversion accuracy just "good enough" for the values involved. In fact, that test previously failed on my mac M1 anyway - because on my platform, long double and double are the same thing. In general, guaranteeing one epsilon accuracy is probably unrealistic for reasonable computations anyway (my previous discussions on the topic used the term "of the order of the epsilon" on purpose).

What I did not yet address are the discussions about making the implementation details private. The aim was to keep the types "literal types", so we could use them in NTTPs if needed (maybe for large point-offsets?). That said, I'm not sure we really need it, and it's easy to change, so whatever you prefer. Also, if we start using such wide integers as repr inside quantities, we may need even wider ones to achieve our guarantees in conversions. The design of the double_width_int here could be relatively easily extended into a compile-time arbitrary-width integer if that need arose. But probably, that's a task for another PR.

[burnpanck]

That CI failure for GCC 12 and GCC 13 error: extra ‘;’ [-Werror=pedantic] after a class template partial specialisation is obviously wrong. Should I re-write this as three separate classes and use something like std::conditional_t to get those compilers to accept?

[mpusz]

The aim was to keep the types "literal types", so we could use them in NTTPs if needed (maybe for large point-offsets?)

I was not aware of this. This makes sense... But in such a case, I would obfuscate the names much more (similar to what we have in quantity) so users will not depend on those, as we might hide them if the language rules for literal types will change in the future.

[mpusz]

That CI failure for GCC 12 and GCC 13 error: extra ‘;’ [-Werror=pedantic] after a class template partial specialisation is obviously wrong. Should I re-write this as three separate classes and use something like std::conditional_t to get those compilers to accept?

I think you did not check if properly. GCC complains about ; put after a function definition (not class).

[burnpanck]

I think you did not check if properly. GCC complains about ; put after a function definition (not class).

You are right of course. It just happens that sudo_cast.h had a template class specialisation end on the same line number, and I never properly checked the file name (it's fixed_point.h).

[burnpanck]

I should probably increase the test coverage for that double_width_int quite a bit more. The value_cast use-case actually only uses the multiplication operator and constructor from long double now (though I should still change that for purely rational conversion factors), but once it's in the code-base, people might get tempted to use it for something else. Also, testing is easier if a more complete set of arithmetic is available.

[mpusz]

Hi @burnpanck, do you plan to work on this in the near future? I would love to see fixed-point-scaling in action. Also, @JohelEGP is writing API Reference for ISO papers now, and we do not know what to describe.

Also, talking about ISO papers, it would be great if you could contribute an add this small chapter about scaling that we talked about some time ago.

[burnpanck]

Hey @mpusz , sorry for the long pause, as usual, paid work did interfere. Could you point me to a good location where to start drafting the design rationale behind this change?

[mpusz]

@burnpanck, it's great to hear from you again 😃

The best way to contribute to the ISO proposal is by doing a PR to a 3045R4 file at https://github.com/mpusz/wg21-papers. Please note that this repo has git submodules. To generate the paper, go to the src directory and do make update followed by make <name of the file>.html.

[mpusz]

I would recommend putting the chapter somewhere inside of https://mpusz.github.io/wg21-papers/papers/3045R4_quantities_and_units_library.html#quantities.

[burnpanck]

I just merged latest master, I believe it should pass the tests again now. Given that it does pass all the tests, I think it is potentially mergeable. Perhaps you want to review again, or do you want to wait for a first draft of the rationale doc?

Before I remove the "draft" state, there are two areas where I'd like your input:

• Currently, we never use any implementation-provided __int128, because it is non-standard. The corresponding #if defined(...) is currently set as #if false && defined(...). An implementation may however potentially provide a "hand-optimised" 128 bit integer type that outperforms what the compiler synthesizes with our C++ implementation. What is our stance here?
• Similarly, min_width_uint_t can either be implemented elegantly in terms of the C++20 std::bit_width and std::has_single_bit, or somewhat less elegant with older tools. Should we use feature macros to select between either implemenation, or just stick with one? (According to cppreference, recent releases of the four major compilers should support the feature).
• (Found this while fixing a merge bug) The current tests in custom_rep_test_min_impl.cpp do not contain any units conversion that is not either a pure multiplication or division. If it had, the tests would fail, because currently the fixed point implementation doesn't play well with the custom integer min_impl<T> (with T being an integral type). We may want to refine the interface specification towards custom representation types:
  • I believe we already have something like treat_as_floating_point, which should probably be explicitly checked in order to select between fixed-point and floating-point implementations.
  • If fixed-point is selected, we will need a way to access the range/bit-width and potentially the "epsilon" (= 1 for actual integers, but there could be a custom fixed-point representation as-well) of the custom representation type; also, we'll either want to cast to our internal integer/fixed-point representation, do the computation, then cast back, or we'd require further access to bit-shift operators at least.
  • Alternatively, we could instead just create a customisation point for "scaling by a magnitude", and plug the fixed-point and floating-point implementation as default implementations; then we ask any custom integral types which would not work with our simplest fixed-point implementation (we should formalise what that means) to provide a custom implementation of that customisation point.

[mpusz]

or do you want to wait for a first draft of the rationale doc?

No, I would like to merge it ASAP. Having a rationale discussion in the ISO paper would be great, but it is a separate task.

[mpusz]

Currently, we never use any implementation-provided __int128

This is not exposed in the public API, so it does not affect our users' code. This is why I believe that if it improves performance (compile-time or runtime), we should use such types wherever we can and are sure they exist. A generic and portable implementation should be used only in the remaining cases.

[mpusz]

min_width_uint_t can either be implemented...

If those features are available on all the supported compilers, then there is no need for alternatives. We always compile with at least C++20.

[mpusz]

The current tests in custom_rep_test_min_impl.cpp do not contain any units conversion

Those tests may be cleaned up and refactored if needed.

We may want to refine the interface specification towards custom representation types

Sure, please note that I am also working on refactoring the Representation concepts. For scalar, the basic idea is to have something like:

template<typename T>
concept WeaklyRegular = std::copyable<T> && std::equality_comparable<T>;

template<typename T>
concept Scalar = is_scalar<T>;

template<typename T>
concept ScalarRepresentation = Scalar<T> && WeaklyRegular<T> && requires(T a, T b, std::intmax_t i, long double f) {
  // scaling
  { a* i } -> Scalar;
  { i* a } -> Scalar;
  { a / i } -> Scalar;
  { a* f } -> Scalar;  // TODO How this affects freestanding?
  { f* a } -> Scalar;
  { a / f } -> Scalar;

  // scalar operations
  { a + b } -> Scalar;
  { a - b } -> Scalar;
  { a* b } -> Scalar;
  { a / b } -> Scalar;
};

template<typename T>
concept Representation =
  detail::ScalarRepresentation<T> || detail::ComplexRepresentation<T> || detail::VectorRepresentation<T> ||
  detail::Tensor2Representation<T> || detail::Tensor4Representation<T>;

The scaling part probably needs modifications after your change?

[burnpanck]

The scaling part probably needs modifications after your change?

Probably. I see two options. Option one is to distinguish two types of representations: "floating point" and "fixed point" (integers fall under this). The former ones are easy, because they have a a large enough range so we don't care about over- and underflow, and scaling them usually does not risk loosing precision, because the "epsilon" scales with the number. The later ones require us to carefully reason about range and resolution, because every scaling operation "shifts out" bits either above or below. I should really get a draft in of that rationale, to clarify why these are essential considerations.

The more I think of this however, I believe what we really want from a representation is that it can be scaled by a magnitude. Thus, I think we should actually use that as the "defining property"; we define an API such as scale(magnitude, value [, out_representation_specification]) which acts as a customisation point, and with suitable default implementations. Then, we just require that representations are "scalable", which shall imply that they are suitable for the value argument of scale (with the default out_representation_specification of requesting the same type as value). Note that this PR almost contains an implementation of that API in mp_units::detail::conversion_value_traits::scale, but without provisions for being a customisation point.

What would be the preferred mechanism for customisation points? I recall a discussion in the "std::execution" proposal for C++26 where they considered several possible choices for customisation points; they deemed the free-function approach of "std::ranges" not suitable for their use-case, but I believe that was because they essentially need something like "multiple-dispatch"; multiple unrelated entities each should have a shot at customising operations involving each other. In this case, the magnitude is not a customisable object, so free functions should work fine.

[burnpanck]

Right, that's why I had the "__int128" implementation set to #if false; it fails -Werror -Wpedantic. Whats the preferred way to disable pedantic warnings for a short subsection of code? #pragma GCC diagnostic push hidden behind suitable guards to detect GCC compatible compilers would likely make the tests pass, is that what I should do?

[mpusz]

Whats the preferred way to disable pedantic warnings for a short subsection of code?

https://github.com/mpusz/mp-units/blob/2892fd83b0551cd6ccbb63d448b3474e7c1c66b6/src/core/include/mp-units/bits/hacks.h#L42-L43

[mpusz]

I pushed some additional tests for std::complex usage so you can check your scaling facility with it. I've also added the initial version of the new Representation concepts. Please feel free to refactor them based on your framework. Their scaling part should reflect whatever sudo_cast is doing.

[burnpanck]

Ok, I'll have a look. Any idea why the Conan CI for Clang 17 and 18 in C++20 mode passes, but in C++23 mode complains about unknown namespace members std::bit_width and std::has_single_bit? According to cppreferences' compiler support it should be in libc++ since version 12...

[mpusz]

C++23 build on clang uses modules. Maybe there is a bug in libc++ that it does not export those types from the std module?

[mpusz]

Please try adding <bit> to core_gmf.h.

[burnpanck]

Hm, I seem to be unable to get GCC 12 to accept any form of friend declaration so that an unsigned instantiation of double_width_int can refer to it's signed counterpart and vice-versa. This looks like a compiler bug, though I couldn't find anything. I tried both a general template friend and a dedicated friend instantiation. Any other ideas? Otherwise, we'd either have to make the hi_ and lo_ members public again, or provide public accessors, which kind of feels the same (or ditch GCC 12).

[mpusz]

I tried as well and I couldn't make it for gcc-12 as well. So I cheated 😜

[burnpanck]

I just pushed another take at the Representation concept, in particular with respect to their "scaling" behaviour. The reasoning behind it is the following:

1. Units of measurement form a (mathematical) vector space over the real numbers (i.e. any scaling of a unit by a real number is still a reasonable unit for the same dimension; so is the sum of any two units of the same dimension)
2. quantity models the semantics of physical quantities, through their representation by the product of a "number" and a unit. Because every physical quantity has exactly one such representation for each unit of that dimension (which are all equivalent), the mathematical space from which the "numbers" are drawn also necessarily needs to embed a (mathematical) vector space over the real numbers. (The real numbers obviously do, but so do the complex numbers, as well as the "cartesian vectors" in R^N, and many other mathematical spaces).
3. Any change of representation of a quantity as a different unit requires the ratio between the original unit and the new unit (in mp_units represented as a Magnitude) to be multiplied to the "number". Thus, the fundamental requirement on the C++ representation of the "number" requires some way to at least approximately represent the result of rescaling an input number by real number represented by a Magnitude. Therefore, this latest commit explicitly encodes that operation as mp_units::scale(Magnitude auto M, typename Value), along with a number of customisation points for that implementation (more on that below).
4. We probably would like to require that the "numbers" are dimensionless (i.e. neither quantity nor std::chrono::duration should be allowed for the "number" representation).

Both 3 & 4 may be difficult to fully express as C++ concepts; the problem with 3 is that we ideally would like to verify scaling against all possible magnitudes, and with 4 it may not even be clear what exactly should be allowed and what not. Thus, for now, I simply check 3 my testing for mag<1>, and 4 continues to be handled through the explicit opt-in that you @mpusz recently implemented for the Representation concept via the character opt-ins.

Note that I included two slightly different spellings of scale; one that takes an explicit specification of the out-representation (through an instance of std::type_identity<R> as a boost::hana::type<R>-like type tag), while the other leaves the out-representation free to scaling implementation. The intent is for the former to be used when the user explicitly asks for a representation, whereas the latter should be used when only a change of units is requested (e.g. in a sum of two compatible quantities expressed in different units). The goal is to enable fancy number representations as those provided by the CNL to intelligently limit the precision of the scaling factor when the output is narrow anyway (first case), or allow to tailor the precision of the output representation to the precision of the input representation and the scaling factor (second case).

Finally, you may want to review the customisation rules of the scaling operation. The implementation of the two mp_units::scale overloads currently proceed as follows:

1. Check if the source representation type has a suitable member .scale; if it does, use this
2. Check if mp_units::scaling_traits<R> is defined; if it is, use nested static member functions (if no suitable one is found, fail to compile)
3. Check if mp_units::treat_as_floating_point is true for either the input or the output representation (if given); if it is, approximate the scaling factor using a suitable standard floating point (long double unless we know that the representation's precision is comparable to a smaller floating point type), and use operator* (or operator/ for pure divisions).
4. Check if both types are standard integral types (or at least their value_type_ts are and the representation type is implicitly convertible from and to their value_type_t); then approximate the scaling factor using a fixed-point representation with as many integral and fractional bits (each) as the larger of the two types, and perform a fixed-point multiplication.
5. Otherwise, the program is ill-formed.

In general, I believe that is more or less all that I would put into this PR, and therefore remove the "draft" mark as soon as all tests pass.

[burnpanck]

While merging the latest changes, I ran into the following (now) failing test: static_assert(quantity<s>{1ms} == 1 * ms); (in static/chrono_test.cpp). I should investigate more, but shouldn't this be a test for almost equal instead of exactly equal, given the floating-point types?

[burnpanck]

Looks like I failed to correctly export mp_units::scale from mp-units/bits/scale.h and now the module-enabled tests fail. Unfortunately, I don't have any experience with modules so far; what is needed to properly export a name? That file is definitely indirectly included from mp-units-core.cpp, through mp-units/framework/representation_concepts.h...

Also, I presume mp-units/bits/scale.h is anyway the wrong place to export it from, and it should go somewhere into mp-units/framework/ instead, correct?

[mpusz]

what is needed to properly export a name?

https://github.com/mpusz/mp-units/blob/master/src/core/include/mp-units/bits/module_macros.h

[mpusz]

Also, I presume mp-units/bits/scale.h is anyway the wrong place to export it from, and it should go somewhere into mp-units/framework/ instead, correct?

Yes, bits/... are implementation details and should not contain anything that is the library's public API. This is why all of them start with namespace mp_units::detail {.

[mpusz]

Hi @burnpanck, will you have some time to finish the work on your open PRs soon?