[libc] add fast path to string to float conversion

[michaelrj]

Summary

Add the fast path first described by Clinger [1] with additions by Gay [2].
This speeds up conversion by about 10% by handling numbers with fewer digits
more efficiently.

[1] Clinger WD. How to Read Floating Point Numbers Accurately.
SIGPLAN Not 1990 Jun;25(6):92–101. https://doi.org/10.1145/93548.93557.
[2] Gay DM, Correctly rounded binary-decimal and decimal-binary conversions;

1990. AT&T Bell Laboratories Numerical Analysis Manuscript 90-10.

[sivachandra]

libc/src/__support/str_to_float.h

321

Is it necessary to declare the members? Can we not get by with just a class declaration like this:

template <typename T> class ClingerConsts;

421

Can we add specific tests for the newly added conditions? Existing tests probably cover them, but having separated tests helps in isolating and debugging in future.

[michaelrj]

add unit tests and clean up the fast path.

libc/src/__support/str_to_float.h

321

That was something I added when it would've allowed types without a specific set to just skip this path. I've changed it to be what you said since as it was it would return incorrect values if someone attempted to use it with a long double.

libc/src/__support/str_to_float.h

if (hpd.getNumDigits() == 0) {
     *outputExp2 = 0;
     return;
   }
 
   // If the exponent is too large and can't be represented in this size of
   // float, return inf.
   if (hpd.getDecimalPoint() > 0 &&
       exp10ToExp2(hpd.getDecimalPoint() - 1) >
-          static_cast<int32_t>(fputil::FloatProperties<T>::exponentBias)) {
+          static_cast<int64_t>(fputil::FloatProperties<T>::exponentBias)) {
     *outputMantissa = 0;
     *outputExp2 = fputil::FPBits<T>::maxExponent;
     errno = ERANGE; // NOLINT
     return;
   }
   // If the exponent is too small even for a subnormal, return 0.
   if (hpd.getDecimalPoint() < 0 &&
       exp10ToExp2(-hpd.getDecimalPoint()) >
-          static_cast<int32_t>(fputil::FloatProperties<T>::exponentBias +
+          static_cast<int64_t>(fputil::FloatProperties<T>::exponentBias +
                                fputil::FloatProperties<T>::mantissaWidth)) {
     *outputMantissa = 0;
     *outputExp2 = 0;
     errno = ERANGE; // NOLINT
     return;
   }
 
   // Right shift until the number is smaller than 1.
if (finalMantissa == typename fputil::FPBits<T>::UIntType(2)
     finalMantissa >>= 1;
     ++exp2;
   }
 
   *outputMantissa = finalMantissa;
   *outputExp2 = exp2;
 }
 
+// This class is used for templating the constants for Clinger's Fast Path,
+// described as a method of approximation in
+// Clinger WD. How to Read Floating Point Numbers Accurately. SIGPLAN Not 1990
+// Jun;25(6):92–101. https://doi.org/10.1145/93548.93557.
+// As well as the additions by Gay that extend the useful range by the number of
+// exact digits stored by the float type, described in
+// Gay DM, Correctly rounded binary-decimal and decimal-binary conversions;
+// 1990. AT&T Bell Laboratories Numerical Analysis Manuscript 90-10.
+template <class T> class ClingerConsts;
+
+template <> class ClingerConsts<float> {
+public:
+  static constexpr float powersOfTenArray[] = {1e0, 1e1, 1e2, 1e3, 1e4, 1e5,
+                                               1e6, 1e7, 1e8, 1e9, 1e10};
+  static constexpr int32_t exactPowersOfTen = 10;
+  static constexpr int32_t digitsInMantissa = 7;
+  static constexpr float maxExactInt = 16777215.0;
+};
+
+template <> class ClingerConsts<double> {
+public:
+  static constexpr double powersOfTenArray[] = {
+      1e0,  1e1,  1e2,  1e3,  1e4,  1e5,  1e6,  1e7,  1e8,  1e9,  1e10, 1e11,
+      1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19, 1e20, 1e21, 1e22};
+  static constexpr int32_t exactPowersOfTen = 22;
+  static constexpr int32_t digitsInMantissa = 15;
+  static constexpr double maxExactInt = 9007199254740991.0;
+};
+
+// Take an exact mantissa and exponent and attempt to convert it using only
+// exact floating point arithmetic. This only handles numbers with low
+// exponents, but handles them quickly. This is an implementation of Clinger's
+// Fast Path, as described above.
+template <class T>
+static inline bool
+clingerFastPath(typename fputil::FPBits<T>::UIntType mantissa, int32_t exp10,
+                typename fputil::FPBits<T>::UIntType *outputMantissa,
+                uint32_t *outputExp2) {
+  if (mantissa >> fputil::FloatProperties<T>::mantissaWidth > 0) {
+    return false;
+  }
+
+  fputil::FPBits<T> result;
+  T floatMantissa = static_cast<T>(mantissa);
+
+  if (exp10 == 0) {
+    result = fputil::FPBits<T>(floatMantissa);
+  }
+  if (exp10 > 0) {
+    if (exp10 > ClingerConsts<T>::exactPowersOfTen +
+                    ClingerConsts<T>::digitsInMantissa) {
+      return false;
+    }
+    if (exp10 > ClingerConsts<T>::exactPowersOfTen) {
+      floatMantissa =
+          floatMantissa *
+          ClingerConsts<
+              T>::powersOfTenArray[exp10 - ClingerConsts<T>::exactPowersOfTen];
+      exp10 = ClingerConsts<T>::exactPowersOfTen;
+    }
+    if (floatMantissa > ClingerConsts<T>::maxExactInt) {
+      return false;
+    }
+    result = fputil::FPBits<T>(floatMantissa *
+                               ClingerConsts<T>::powersOfTenArray[exp10]);
+  } else if (exp10 < 0) {
+    if (-exp10 > ClingerConsts<T>::exactPowersOfTen) {
+      return false;
+    }
+    result = fputil::FPBits<T>(floatMantissa /
+                               ClingerConsts<T>::powersOfTenArray[-exp10]);
+  }
+  *outputMantissa = result.getMantissa();
+  *outputExp2 = result.getUnbiasedExponent();
+  return true;
+}
+
 // Takes a mantissa and base 10 exponent and converts it into its closest
 // floating point type T equivalient. First we try the Eisel-Lemire algorithm,
 // then if that fails then we fall back to a more accurate algorithm for
 // accuracy. The resulting mantissa and exponent are placed in outputMantissa
 // and outputExp2.
 template <class T>
 static inline void
 decimalExpToFloat(typename fputil::FPBits<T>::UIntType mantissa, int32_t exp10,
                   const char *__restrict numStart, bool truncated,
                   typename fputil::FPBits<T>::UIntType *outputMantissa,
                   uint32_t *outputExp2) {
+  // If the exponent is too large and can't be represented in this size of
+  // float, return inf. These bounds are very loose, but are mostly serving as a
+  // first pass. Some close numbers getting through is okay.
+  if (exp10 >
+      static_cast<int64_t>(fputil::FloatProperties<T>::exponentBias) / 3) {
+    *outputMantissa = 0;
+    *outputExp2 = fputil::FPBits<T>::maxExponent;
+    errno = ERANGE; // NOLINT
+    return;
+  }
+  // If the exponent is too small even for a subnormal, return 0.
+  if (exp10 < 0 &&
+      -static_cast<int64_t>(exp10) >
+          static_cast<int64_t>(fputil::FloatProperties<T>::exponentBias +
+                               fputil::FloatProperties<T>::mantissaWidth) /
+              2) {
+    *outputMantissa = 0;
+    *outputExp2 = 0;
+    errno = ERANGE; // NOLINT
+    return;
+  }
 
-  // TODO: Implement Clinger's fast path, as well as other shortcuts here.
+  if (!truncated) {
+    if (clingerFastPath<T>(mantissa, exp10, outputMantissa, outputExp2)) {
+      return;
+    }
+  }
 
   // Try Eisel-Lemire
   if (eiselLemire<T>(mantissa, exp10, outputMantissa, outputExp2)) {
     if (!truncated) {
       return;
     }
     // If the mantissa is truncated, then the result may be off by the LSB, so
     // check if rounding the mantissa up changes the result. If not, then it's
if (base == 16) {
       exponent *= 4;
     }
 
     if ((*src | 32) == exponentMarker) {
       if (*(src + 1) == '+' || *(src + 1) == '-' || isdigit(*(src + 1))) {
         ++src;
         char *tempStrEnd;
         int32_t add_to_exponent = strtointeger<int32_t>(src, &tempStrEnd, 10);
+        if (add_to_exponent > 100000) {
+          add_to_exponent = 100000;
+        } else if (add_to_exponent < -100000) {
+          add_to_exponent = -100000;
+        }
         src += tempStrEnd - src;
         exponent += add_to_exponent;
       }
     }
 
     if (mantissa == 0) { // if we have a 0, then also 0 the exponent.
       exponent = 0;
     } else if (base == 16) {

libc/test/src/__support/str_to_float_test.cpp

 //===-- Unittests for str_to_float ----------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "src/__support/FPUtil/FPBits.h"
 #include "src/__support/str_to_float.h"
 
 #include "utils/UnitTest/Test.h"
 
 class LlvmLibcStrToFloatTest : public __llvm_libc::testing::Test {
 public:
   template <class T>
+  void ClingerFastPathTest(
+      const typename __llvm_libc::fputil::FPBits<T>::UIntType inputMantissa,
+      const int32_t inputExp10,
+      const typename __llvm_libc::fputil::FPBits<T>::UIntType
+          expectedOutputMantissa,
+      const uint32_t expectedOutputExp2) {
+    typename __llvm_libc::fputil::FPBits<T>::UIntType actualOutputMantissa = 0;
+    uint32_t actualOutputExp2 = 0;
+
+    ASSERT_TRUE(__llvm_libc::internal::clingerFastPath<T>(
+        inputMantissa, inputExp10, &actualOutputMantissa, &actualOutputExp2));
+    EXPECT_EQ(actualOutputMantissa, expectedOutputMantissa);
+    EXPECT_EQ(actualOutputExp2, expectedOutputExp2);
+  }
+
+  template <class T>
+  void ClingerFastPathFailsTest(
+      const typename __llvm_libc::fputil::FPBits<T>::UIntType inputMantissa,
+      const int32_t inputExp10) {
+    typename __llvm_libc::fputil::FPBits<T>::UIntType actualOutputMantissa = 0;
+    uint32_t actualOutputExp2 = 0;
+
+    ASSERT_FALSE(__llvm_libc::internal::clingerFastPath<T>(
+        inputMantissa, inputExp10, &actualOutputMantissa, &actualOutputExp2));
+  }
+
+  template <class T>
   void EiselLemireTest(
       const typename __llvm_libc::fputil::FPBits<T>::UIntType inputMantissa,
       const int32_t inputExp10,
       const typename __llvm_libc::fputil::FPBits<T>::UIntType
           expectedOutputMantissa,
       const uint32_t expectedOutputExp2) {
     typename __llvm_libc::fputil::FPBits<T>::UIntType actualOutputMantissa = 0;
     uint32_t actualOutputExp2 = 0;
TEST(LlvmLibcStrToFloatTest, LeadingZeroes) {
   for (; numOfZeroes < 32; testNum32 <<= 1, numOfZeroes--) {
     EXPECT_EQ(__llvm_libc::internal::leadingZeroes<uint32_t>(testNum32),
               numOfZeroes);
   }
 
   EXPECT_EQ(__llvm_libc::internal::leadingZeroes<uint32_t>(0xffffffff), 0u);
 }
 
+TEST_F(LlvmLibcStrToFloatTest, ClingerFastPathFloat64Simple) {
+  ClingerFastPathTest<double>(123, 0, 0xEC00000000000, 1029);
+  ClingerFastPathTest<double>(1234567890123456, 1, 0x5ee2a2eb5a5c0, 1076);
+  ClingerFastPathTest<double>(1234567890, -10, 0xf9add3739635f, 1019);
+}
+
+TEST_F(LlvmLibcStrToFloatTest, ClingerFastPathFloat64ExtendedExp) {
+  ClingerFastPathTest<double>(1, 30, 0x93e5939a08cea, 1122);
+  ClingerFastPathTest<double>(1, 37, 0xe17b84357691b, 1145);
+  ClingerFastPathFailsTest<double>(10, 37);
+  ClingerFastPathFailsTest<double>(1, 100);
+}
+
+TEST_F(LlvmLibcStrToFloatTest, ClingerFastPathFloat64NegativeExp) {
+  ClingerFastPathTest<double>(1, -10, 0xb7cdfd9d7bdbb, 989);
+  ClingerFastPathTest<double>(1, -20, 0x79ca10c924223, 956);
+  ClingerFastPathFailsTest<double>(1, -25);
+}
+
+TEST_F(LlvmLibcStrToFloatTest, ClingerFastPathFloat32Simple) {
+  ClingerFastPathTest<float>(123, 0, 0x760000, 133);
+  ClingerFastPathTest<float>(1234567, 1, 0x3c6146, 150);
+  ClingerFastPathTest<float>(12345, -5, 0x7cd35b, 123);
+}
+
+TEST_F(LlvmLibcStrToFloatTest, ClingerFastPathFloat32ExtendedExp) {
+  ClingerFastPathTest<float>(1, 15, 0x635fa9, 176);
+  ClingerFastPathTest<float>(1, 17, 0x31a2bc, 183);
+  ClingerFastPathFailsTest<float>(10, 17);
+  ClingerFastPathFailsTest<float>(1, 50);
+}
+
+TEST_F(LlvmLibcStrToFloatTest, ClingerFastPathFloat32NegativeExp) {
+  ClingerFastPathTest<float>(1, -5, 0x27c5ac, 110);
+  ClingerFastPathTest<float>(1, -10, 0x5be6ff, 93);
+  ClingerFastPathFailsTest<float>(1, -15);
+}
+
 TEST_F(LlvmLibcStrToFloatTest, EiselLemireFloat64Simple) {
   EiselLemireTest<double>(12345678901234567890u, 1, 0x1AC53A7E04BCDA, 1089);
   EiselLemireTest<double>(123, 0, 0x1EC00000000000, 1029);
   EiselLemireTest<double>(12345678901234568192u, 0, 0x156A95319D63E2, 1086);
 }
 
 TEST_F(LlvmLibcStrToFloatTest, EiselLemireFloat64SpecificFailures) {
   // These test cases have caused failures in the past.