[libc++] `std::cmp_less` and other integer comparison functions could be improved

[eisenwave]

The current implementation of the safe comparison functions is less not optimal:

llvm-project/libcxx/include/__utility/cmp.h

Lines 65 to 75 in 22044f0

	template<__is_safe_integral_cmp _Tp, __is_safe_integral_cmp _Up>
	_LIBCPP_INLINE_VISIBILITY constexpr
	bool cmp_less(_Tp __t, _Up __u) noexcept
	{
	if constexpr (is_signed_v<_Tp> == is_signed_v<_Up>)
	return __t < __u;
	else if constexpr (is_signed_v<_Tp>)
	return __t < 0 ? true : make_unsigned_t<_Tp>(__t) < __u;
	else
	return __u < 0 ? false : __t < make_unsigned_t<_Up>(__u);
	}

For two maximally wide integers (i.e. unsigned long), this is the best you can do. However, if a wider integer type is available, then all comparisons can be made safe by converting to the wider integer.

For example, a comparison unsigned int < signed int could be implemented through long long < long long, which is either zero-cost, or involves a sign extension for one of the operands. Indeed, if we compare std::cmp_less to such an extending implementation: (https://godbolt.org/z/M1s5dxh11)

bool std_less(unsigned int a, signed int b) { return std::cmp_less(a, b); }
bool ext_less(unsigned int a, signed int b) { return static_cast<long long>(a) < static_cast<long long>(b); }

The output for ext_less is slightly better, although it's not strikingly obvious. The additional mov and setl in ext_less are artifacts of the ABI, and movsxd could also disappear through inlining.

std_less(unsigned int, int):
        test    esi, esi
        setns   cl
        cmp     edi, esi
        setb    al
        and     al, cl
        ret
ext_less(unsigned int, int):
        mov     eax, edi
        movsxd  rcx, esi
        cmp     rax, rcx
        setl    al
        ret

When we add __builtin_assume(a <= INT_MAX); to both functions, the difference becomes more striking. std_less is completely unchanged, but ext_less becomes:

ext_less(unsigned int, int):
        cmp     edi, esi
        setl    al
        ret

This would turn std::cmp_less into a true zero-overhead utility, since LLVM could now always fall back onto a simple cmp instruction if it knows that the unsigned operand is restricted in its value range (which is quite plausible).

Proposed Change

template<__is_safe_integral_cmp _Tp, __is_safe_integral_cmp _Up>
_LIBCPP_INLINE_VISIBILITY constexpr
bool cmp_less(_Tp __t, _Up __u) noexcept
{
+  if constexpr (sizeof(_Tp) <= sizeof(long long) && sizeof(_Up) <= sizeof(long long))
+    return static_cast<long long>(__t) < static_cast<long long>(__u);
-  if constexpr (is_signed_v<_Tp> == is_signed_v<_Up>)
+  else if constexpr (is_signed_v<_Tp> == is_signed_v<_Up>)
    return __t < __u;
  else if constexpr (is_signed_v<_Tp>)
    return __t < 0 ? true : make_unsigned_t<_Tp>(__t) < __u;
  else
    return __u < 0 ? false : __t < make_unsigned_t<_Up>(__u);
}

The same style of change could be applied to the std::cmp_equal.

[philnik777]

Is there any performance improvement with this change, or is this purely a code size improvement?

[eisenwave]

Is there any performance improvement with this change, or is this purely a code size improvement?

Yes it is faster https://quick-bench.com/q/Rpl1iKtGdr5x3GIpzkMEMzw1K-s; although I couldn't provide conclusive results for larger benchmarks (https://quick-bench.com/q/YsD5uemWyzJxwHRi0XNRc6mEqtQ) because the cost is so small overall.

Also note that the benchmarks are using libstdc++ (which has basically the same implementation) because currently, quickbench is broken for libc++.

[eisenwave]

@philnik777 I believe this would be a good first issue. You could add that label, right? It seems like a relatively easy change, unless I'm missing some nuance.

[llvmbot]

Hi!

This issue may be a good introductory issue for people new to working on LLVM. If you would like to work on this issue, your first steps are:

1. Ask for the issue to be assigned to you.
2. Fix the issue locally.
3. Run the test suite locally.
4. Create a git commit
5. Run git clang-format HEAD~1 to format your changes.
6. Submit the patch.

For more instructions on how to submit a patch to LLVM, see our documentation.

If you have any further questions about this issue, don't hesitate to ask via a comment on this Github issue.

@llvm/issue-subscribers-good-first-issue

[mvvsmk]

Hey, I would love to work on this issue @philnik777 . Could you assign it to me?

@eisenwave , I am new to llvm, so I hope it is suitable for you if I ping you in this thread about any doubts regarding this implementation.

[eisenwave]

@mvvsmk if I was more familiar with the code base, I would have asked for it to be assigned to me. I only know what the general approach should be, not necessarily LLVM specifics.

In particular, I'm unsure if the sign extending approach should be used on 32-bit platforms for 32-bit integer types. Those could still be extended to a 64-bit long long, but that wouldn't be a native type anymore, and I'm not sure what the idiomatic way in LLVM is to detect this platform detail.

There's also the same question about long long being extended to a 128-bit type potentially.

The solution is likely still small and simple, but possibly not the three-line change in the diff I've suggested.