This is an archive of the discontinued LLVM Phabricator instance.

[libc][math] Improve the performance and error printing of UInt.
ClosedPublic

Authored by lntue on Nov 11 2022, 3:13 PM.

Details

Summary

Use add_with_carry builtin to improve the performance of
addition and multiplication of UInt class. For 128-bit, it is as
fast as using __uint128_t.

Microbenchmark for addition:
https://quick-bench.com/q/-5a6xM4T8rIXBhqMTtLE-DD2h8w

Microbenchmark for multiplication:
https://quick-bench.com/q/P2muLAzJ_W-VqWCuxEJ0CU0bLDg

Microbenchmark for shift right:
https://quick-bench.com/q/N-jkKXaVsGQ4AAv3k8VpsVkua5Y

Microbenchmark for shift left:
https://quick-bench.com/q/5-RzwF8UdslC-zuhNajXtXdzLRM

Diff Detail

Event Timeline

lntue created this revision.Nov 11 2022, 3:13 PM
Herald added projects: Restricted Project, Restricted Project. · View Herald TranscriptNov 11 2022, 3:13 PM
lntue requested review of this revision.Nov 11 2022, 3:13 PM
lntue edited the summary of this revision. (Show Details)Nov 11 2022, 3:15 PM
lntue updated this revision to Diff 475161.Nov 14 2022, 8:35 AM
lntue edited the summary of this revision. (Show Details)

Imnprove shift left and shift right performance.

lntue edited the summary of this revision. (Show Details)Nov 14 2022, 8:41 AM
lntue updated this revision to Diff 475204.Nov 14 2022, 10:23 AM
lntue edited the summary of this revision. (Show Details)

Use __uint128_t builtin for shift left if available.

michaelrj added inline comments.Nov 14 2022, 11:12 AM
libc/src/__support/UInt.h
24

is there a reason this is changed?

298

for clarity could this be j > 0?

lntue marked an inline comment as done.Nov 14 2022, 11:39 AM
lntue added inline comments.
libc/src/__support/UInt.h
24

I put everything in this class as public for 3 reasons:

  • To access to WordCount without recomputing it
  • To make this class behave as a value class, I'm going to remove the operator[], and simply use .val[i] directly if we want to access to its ith uint64_t block.
  • Utility functions low and high (and MASK32 constant) will be removed and switched completely to use split(uint64_t) instead. That would separate what we want to do with the class vs what we want to do with uint64_t.
lntue updated this revision to Diff 475229.Nov 14 2022, 11:41 AM

Address comment.

sivachandra added inline comments.Nov 14 2022, 12:04 PM
libc/src/__support/UInt.h
24

I put everything in this class as public for 3 reasons:

  • To access to WordCount without recomputing it

You can make that public alone?

  • To make this class behave as a value class, I'm going to remove the operator[], and simply use .val[i] directly if we want to access to its ith uint64_t block.

Whats wrong with operator[] for such word access?

  • Utility functions low and high (and MASK32 constant) will be removed and switched completely to use split(uint64_t) instead. That would separate what we want to do with the class vs what we want to do with uint64_t.

I did not get how this is related to class vs struct.

libc/src/__support/number_pair.h
37

The full_mul functions should not belong here or name this file something else. May be integer_utils.h.

libc/utils/UnitTest/LibcTest.cpp
281

Ideally, these specializations should be in a different file, say integer_test_utils.cpp, right next to where UInt is defined. May be it leads to a CMake cyclic directory problem?

lntue marked an inline comment as done.Nov 14 2022, 12:40 PM
lntue added inline comments.
libc/src/__support/UInt.h
24

It's just that accessing a specific uint64_t block is clearer with .val[i] vs [i], especially when we have an array of UInt. And with low and high functions being factored out to number_pair.h, there is no need for private members, and we can simply keep everything public.

libc/utils/UnitTest/LibcTest.cpp
281

Since we UInt<128> is required here as replacement for __uint128_t if not available, instantiate other UInt here is the most suitable, without complicating the dependency, I think.

lntue updated this revision to Diff 475247.Nov 14 2022, 12:46 PM

Move full_mul to integer_utils.h and update bazel layout.

lntue updated this revision to Diff 475254.Nov 14 2022, 1:13 PM

Fix bazel build.

sivachandra added inline comments.Nov 14 2022, 2:35 PM
libc/src/__support/UInt.h
24

I don't find the reasoning compelling enough to not hide the implementation detail. But, there is not a lot of implementation detail so I am on the fence.

295

What is a ?

525

I think we can make this a template like this:

template <size_t S>
struct is_integral<UInt<S>> : public cpp::true_type { static_assert(valid S); };
529

We can use a template instead of a specialization here also.

libc/src/__support/number_pair.h
24

Few questions:

  1. Is this the only reason why the rest of the content from this file is not in integer_utils.h?
  2. Is lo, hi split for a DoubleDouble the correct nomenclature?

I am still not convinced of the different styles used here. For example, why is number_pair not NumberPair or DoubleDouble not double_double? We should follow a uniform style. The exceptions are only applicable for the cpp directory. So, I suggest this:

  1. Add a simple cpp::pair<T1, T2> class.
  2. Instead of number_pair, define IntegerSplit:
template <typename T>
class IntegerSplit : protected cpp::pair<T, T> {
public:
  IntegerSplit() = default;
  IntegerSplit(T l, T h) : first(l), second(h) {}
  T &lo() { return cpp::pair<T, T>::first; }
  T &hi() { return cpp::pair<T, T>::second; }
  const T &lo() const { return cpp::pair<T, T>::first; }
  const T &hi() const { return cpp::pair<T, T>::second; }
};
  1. Not in this patch, but when required:
class DoubleDouble : protected cpp::pair<double, double> {
public:
  DoubleDouble() = default;
  Double(double m, double d) : cpp::pair<T, T>(m, d) {}
  double &main() { return cpp::pair<T, T>::first; }
  double &delta() { return cpp::pair<T, T>::second; }
  const double &main() const { return cpp::pair<T, T>::first; }
  const double &delta() const { return cpp::pair<T, T>::second; }
};
libc/utils/UnitTest/LibcTest.cpp
281

We can keep specializations of only standard types here. Everything else, including those for __uint128_t, should go to another file.

lntue added inline comments.Nov 14 2022, 3:21 PM
libc/src/__support/UInt.h
295

Thanks for finding the bug! It turns out that I missed extra __ at the end of the macro in #ifdef, hence dead-code here.

libc/src/__support/number_pair.h
24

Yes, I think the normal splitting in the literature with double-double data type will call high/low parts, with abbreviations hi/lo. I do update the style name to NumberPair, but IntegerSplit does not seem fit, since it could be more generic and applied to double to get DoubleDouble type.

On the other hand, I don't see any benefit of a more complicated class structure over a simple POD struct for this yet. If there is a need for them, I'd be happy to update its definition.

libc/utils/UnitTest/LibcTest.cpp
281

Does it also mean that by default we will need to link to the other file, in addition to LibcTest ?

lntue updated this revision to Diff 475299.Nov 14 2022, 3:34 PM

Fix SIZEOF_INT128 macro detection and fix naming style.

sivachandra added inline comments.Nov 14 2022, 3:38 PM
libc/src/__support/number_pair.h
24

Ah! If the normal convention is to use hi and lo for the main and delta components of a double-double, then having a single definition is OK.

libc/utils/UnitTest/LibcTest.cpp
281

Yes, like other custom matchers we have.

lntue added inline comments.Nov 14 2022, 4:13 PM
libc/utils/UnitTest/LibcTest.cpp
281

The template test that is instantiated here is actually only defined internally inside LibcTest.cpp. Untangle and refactoring it out to a common header so that we can have a separate instantiation target for UInt<192> and UInt<256> feel like out-of-scope for this patch. It should be a separate task / patch to refactor this file instead.

sivachandra added inline comments.Nov 14 2022, 5:38 PM
libc/utils/UnitTest/LibcTest.cpp
281

Yes - what I am describing is the end situation. You don't have to do it in this patch. The main point is that we can't keep adding specializations here. I agree it will take much more surgery than just moving it out. It is probably also exposing a deficiency in the current design.

sivachandra accepted this revision.Nov 15 2022, 10:48 AM
This revision is now accepted and ready to land.Nov 15 2022, 10:48 AM
This revision was landed with ongoing or failed builds.Nov 15 2022, 11:18 AM
This revision was automatically updated to reflect the committed changes.