This is an archive of the discontinued LLVM Phabricator instance.

[libc] Implement a high-precision floating point class.
ClosedPublic

Authored by lntue on Oct 26 2022, 3:07 PM.

Details

Summary

Implement a high-precision floating point class using UInt<> as its
mantissa. This will be used in accurate pass for double precision math
functions.

Diff Detail

Event Timeline

lntue created this revision.Oct 26 2022, 3:07 PM
Herald added projects: Restricted Project, Restricted Project. · View Herald TranscriptOct 26 2022, 3:07 PM
lntue requested review of this revision.Oct 26 2022, 3:07 PM

Overall this looks promising, but I'd like to see some unit tests for the big float class if possible.

libc/src/__support/FPUtil/big_float.h
46 ↗(On Diff #470951)

this could probably be templated by using FloatProperties<T>::MantissaWidth

75 ↗(On Diff #470951)

same as above, I think you can make this either an operator or a templated to_float<T>

87 ↗(On Diff #470951)

did you mean to have this twice?

209 ↗(On Diff #470951)

nit: please fix

libc/src/__support/UInt.h
28–31

The pair class should probably be in a separate file.

592–602

is it possible to have this as <T> instead of specifying 128, 196, and 256? Same below.

There is a similar class by name XFloat but it does not have addition operation: https://github.com/llvm/llvm-project/blob/main/libc/src/__support/FPUtil/XFloat.h
Remove it if you don't like it.

libc/src/__support/FPUtil/big_float.h
30 ↗(On Diff #470951)

Explain why this is better or preferred over the conventional exponent.

42 ↗(On Diff #470951)

You can drop this assumption by using NormalFloat.

180 ↗(On Diff #470951)

You should explain why these functiona have quick_ prefix in their name, and why they are not member operators.

libc/src/__support/UInt.h
28–31

Agree - you can choose to add a cpp:pair class.

61

These functions just seem to me like specializations of the UInt ful_add and ful_mul. If you really need these separately, you need to add some commentary to justify.

590

There could be a symbolic constant for this number.

tschuett added inline comments.Oct 27 2022, 6:58 AM
libc/src/__support/FPUtil/big_float.h
22 ↗(On Diff #470951)

What is libc`s stand on nested namespaces?

orex added inline comments.Oct 27 2022, 11:08 AM
libc/src/__support/FPUtil/big_float.h
32 ↗(On Diff #470951)

static_assert in UInt is stricter than this one (https://github.com/llvm/llvm-project/blob/7f93ae808634e33e4dc9bce753c909aa5f9a6eb4/libc/src/__support/UInt.h#L25) Probably you should remove or adjust this?

55 ↗(On Diff #470951)

Will it be better to put M_LENGTH >= MANTISSA_LENGTH? For "highly templated" cases it can be easy to generalize such conversion.

75 ↗(On Diff #470951)

General idea. Probably it is good to have conversion to double double? It can be precise for 64 bits mantissa?

84 ↗(On Diff #470951)

The if is not needed. The operations in the if statement probably can be even faster than check and conditional jump?

90 ↗(On Diff #470951)

Nit: Probably it is good to have 53 54 and 55 like some constexpr?

120 ↗(On Diff #470951)

I'm not an expert in C++ standard, but pair with one template argument looks suspicious for me. Does C++ standard saying how it should be expanded?

123 ↗(On Diff #470951)

Is this static cast by standard drop higher part of the variable?

129 ↗(On Diff #470951)

Am I understand right, that rounding and sign of zero in this function is not important?

136 ↗(On Diff #470951)

Probably to put this normalization to dedicated function?

  1. It is quite general.
  2. Remove the code duplication.
orex added inline comments.Oct 28 2022, 12:38 AM
libc/src/__support/FPUtil/big_float.h
120 ↗(On Diff #470951)

The comment is not valid. Sorry.

lntue marked 6 inline comments as done.Oct 31 2022, 10:34 AM
lntue added inline comments.
libc/src/__support/FPUtil/big_float.h
22 ↗(On Diff #470951)

I think we are totally fine with nested namespaces. This is mostly my part of copy-pasting from other headers in the same directory.

32 ↗(On Diff #470951)

I was debating about letting this class using other uint types for the mantissa. But it's probably better to just let the UInt class taking care of it. Removed this static_assert.

42 ↗(On Diff #470951)

I was thinking about using NormalFloat but there are some difference in the expectation between them that will need some extra work to be done in order to merge this and NormalFloat:

  • currently NormalFloat expected to use floating point type as the template parameter, while we want to explicitly control the bits
84 ↗(On Diff #470951)

The current <<= op in UInt is non-trivial and more expensive than a conditional jump. Other option is to put the check for trivial case into UInt itself.

123 ↗(On Diff #470951)

Yes, it is specified for unsigned integers.

129 ↗(On Diff #470951)

Yes, for now its main purpose is to aid the computation of polynomial approximations. So we don't pay too much attention on signed zeroes and rounding, which in turns giving us a tiny bit of performance gain.

libc/src/__support/UInt.h
28–31

I was debating about it, because the standard std::pair has members named first and second, while I want to named them hi and lo to signify the high part and the low part of the numbers. I'm not sure what's the best way to have such distinction yet. Maybe rename this to cpp::number_pair or something similar?

lntue updated this revision to Diff 480937.Dec 7 2022, 8:56 AM
lntue marked an inline comment as done.

Change the name of the class to DyadicFloat, add normalization, and add tests.

lntue marked 4 inline comments as done.Dec 7 2022, 9:04 AM
lntue added inline comments.
libc/src/__support/UInt.h
28–31

These are refactored and cleaned up in https://reviews.llvm.org/D137871 and https://reviews.llvm.org/D138182

61

The optimizations and updates for UInt add and mul are done in https://reviews.llvm.org/D137871 and https://reviews.llvm.org/D138541

lntue marked an inline comment as done.Dec 7 2022, 9:04 AM

LGTM with minor nits

libc/src/__support/FPUtil/dyadic_float.h
14

I think dyadic_float.h should include float_properties.h directly.

libc/src/__support/UInt.h
368–369

shouldn't this be above the ifdef __SIZEOF_INT128__?

Mostly LGTM. I am not yet accepting as I have asked for definitions.

libc/src/__support/FPUtil/dyadic_float.h
2

Will this class be ever used from outside of the math directory? If no, then it probably should live in src/math.

22

This sentence feels incomplete.

25

One can read the code but couple of things should be described here I think:

  1. That bits is the number of bits of mantissa and that it should be a multiple of 64.
  2. Define the meaning of normalization.
  3. Add a note next to the constructors that the object created is normalized as per the above definition.
27

Type name should be MantissaType.

35

This should like have additional constraints. For example, should this allow a quad-precision number to be converted to DyadicFloat<64>?

74

Why is this assumption required?

109

Add definition of "Quick Add".

110

Again, why?

160

Same comments as those for quick_add.

lntue updated this revision to Diff 482516.Dec 13 2022, 9:12 AM
lntue marked 7 inline comments as done.

Address comments.

libc/src/__support/FPUtil/dyadic_float.h
2

I plan to use this to replace NormalFloat and XFloat classes, along with their usages in DivisionAndRemainderOperations or NearestIntegerOperations. Once the replacement completes, we will move them to src/math together.

35

Added checks for mantissa lengths.

74

Added explanation.

lntue marked an inline comment as done.Dec 13 2022, 10:31 AM
lntue added inline comments.
libc/src/__support/UInt.h
368–369

I intentially put it only for non 128-bit / without builtin. Since the built-in 128-bit shifts are quite efficient, so adding an extra check for the special case s == 0 does not improve the performance much, but actually reduce the throughput due to extra branching. For bigger size, the extra branching cost is much smaller compared with the work saving from avoiding all the shifting loops.

sivachandra accepted this revision.Dec 13 2022, 12:41 PM
sivachandra added inline comments.
libc/src/__support/FPUtil/dyadic_float.h
48

This can lead to truncation if Bits is less than MANTISSA_WIDTH. Should we add a static check here, may be extending the above enable_if:

template <typename T, cpp::enable_if_t<cpp::is_floating_point_v<T> && FloatProperties<T>::MANTISSA_WIDTH <= Bits, int> = 0>
122

Add a mathematical expression which illustrates what actually is quick_add doing. Something like:

quick_add.exponent = max(...)
// aligning exponents - explain why
quick_add.mantissa = a.mantissa + b.mantissa;
175

Same mathematical explanation as that for quick_add.

This revision is now accepted and ready to land.Dec 13 2022, 12:41 PM
This revision was automatically updated to reflect the committed changes.
lntue marked an inline comment as done.
lntue marked 2 inline comments as done.Dec 13 2022, 9:47 PM