Page MenuHomePhabricator

[libc++] Forward to std::memcmp for trivially comparable types in equal
Needs ReviewPublic

Authored by philnik on Dec 7 2022, 9:42 AM.

Details

Reviewers
None
Group Reviewers
Restricted Project

Diff Detail

Unit TestsFailed

TimeTest
1,020 mslibcxx CI C++03 > llvm-libc++-shared-cfg-in.std/algorithms/alg_nonmodifying/alg_equal::equal.pass.cpp
Script: -- : 'COMPILED WITH'; /usr/bin/clang++-16 /home/libcxx-builder/.buildkite-agent/builds/a2776cc79bd9-1/llvm-project/libcxx-ci/libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/equal.pass.cpp --target=x86_64-unknown-linux-gnu -nostdinc++ -I /home/libcxx-builder/.buildkite-agent/builds/a2776cc79bd9-1/llvm-project/libcxx-ci/build/generic-cxx03/include/c++/v1 -I /home/libcxx-builder/.buildkite-agent/builds/a2776cc79bd9-1/llvm-project/libcxx-ci/build/generic-cxx03/include/c++/v1 -I /home/libcxx-builder/.buildkite-agent/builds/a2776cc79bd9-1/llvm-project/libcxx-ci/libcxx/test/support -std=c++03 -Werror -Wall -Wctad-maybe-unsupported -Wextra -Wshadow -Wundef -Wno-unused-command-line-argument -Wno-attributes -Wno-pessimizing-move -Wno-c++11-extensions -Wno-noexcept-type -Wno-atomic-alignment -Wno-user-defined-literals -Wno-tautological-compare -Wsign-compare -Wunused-variable -Wunused-parameter -Wunreachable-code -Wno-unused-local-typedef -D_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER -D_LIBCPP_ENABLE_EXPERIMENTAL -D_LIBCPP_DISABLE_AVAILABILITY -fcoroutines-ts -Werror=thread-safety -Wuser-defined-warnings -lc++experimental -nostdlib++ -L /home/libcxx-builder/.buildkite-agent/builds/a2776cc79bd9-1/llvm-project/libcxx-ci/build/generic-cxx03/lib -Wl,-rpath,/home/libcxx-builder/.buildkite-agent/builds/a2776cc79bd9-1/llvm-project/libcxx-ci/build/generic-cxx03/lib -lc++ -pthread -o /home/libcxx-builder/.buildkite-agent/builds/a2776cc79bd9-1/llvm-project/libcxx-ci/build/generic-cxx03/test/std/algorithms/alg.nonmodifying/alg.equal/Output/equal.pass.cpp.dir/t.tmp.exe
10,080 mslibcxx CI C++2b > llvm-libc++-shared-cfg-in.libcxx/algorithms/alg_modifying_operations::copy_move_nontrivial.pass.cpp
Script: -- : 'COMPILED WITH'; /usr/bin/clang++-16 /home/libcxx-builder/.buildkite-agent/builds/88a78d78de3b-1/llvm-project/libcxx-ci/libcxx/test/libcxx/algorithms/alg.modifying.operations/copy_move_nontrivial.pass.cpp --target=x86_64-unknown-linux-gnu -nostdinc++ -I /home/libcxx-builder/.buildkite-agent/builds/88a78d78de3b-1/llvm-project/libcxx-ci/build/generic-cxx2b/include/c++/v1 -I /home/libcxx-builder/.buildkite-agent/builds/88a78d78de3b-1/llvm-project/libcxx-ci/build/generic-cxx2b/include/c++/v1 -I /home/libcxx-builder/.buildkite-agent/builds/88a78d78de3b-1/llvm-project/libcxx-ci/libcxx/test/support -std=c++2b -Werror -Wall -Wctad-maybe-unsupported -Wextra -Wshadow -Wundef -Wno-unused-command-line-argument -Wno-attributes -Wno-pessimizing-move -Wno-c++11-extensions -Wno-noexcept-type -Wno-atomic-alignment -Wno-user-defined-literals -Wno-tautological-compare -Wsign-compare -Wunused-variable -Wunused-parameter -Wunreachable-code -Wno-unused-local-typedef -D_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER -D_LIBCPP_ENABLE_EXPERIMENTAL -D_LIBCPP_DISABLE_AVAILABILITY -fcoroutines-ts -Werror=thread-safety -Wuser-defined-warnings -lc++experimental -nostdlib++ -L /home/libcxx-builder/.buildkite-agent/builds/88a78d78de3b-1/llvm-project/libcxx-ci/build/generic-cxx2b/lib -Wl,-rpath,/home/libcxx-builder/.buildkite-agent/builds/88a78d78de3b-1/llvm-project/libcxx-ci/build/generic-cxx2b/lib -lc++ -pthread -o /home/libcxx-builder/.buildkite-agent/builds/88a78d78de3b-1/llvm-project/libcxx-ci/build/generic-cxx2b/test/libcxx/algorithms/alg.modifying.operations/Output/copy_move_nontrivial.pass.cpp.dir/t.tmp.exe
2,420 mslibcxx CI Modular build > llvm-libc++-shared-cfg-in.libcxx/algorithms::ranges_robust_against_copying_comparators.pass.cpp
Script: -- : 'COMPILED WITH'; /usr/bin/clang++-16 /home/libcxx-builder/.buildkite-agent/builds/a3d04245fddf-1/llvm-project/libcxx-ci/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp --target=x86_64-unknown-linux-gnu -nostdinc++ -I /home/libcxx-builder/.buildkite-agent/builds/a3d04245fddf-1/llvm-project/libcxx-ci/build/generic-modules/include/c++/v1 -I /home/libcxx-builder/.buildkite-agent/builds/a3d04245fddf-1/llvm-project/libcxx-ci/build/generic-modules/include/c++/v1 -I /home/libcxx-builder/.buildkite-agent/builds/a3d04245fddf-1/llvm-project/libcxx-ci/libcxx/test/support -std=c++2b -fmodules -fcxx-modules -Werror -Wall -Wctad-maybe-unsupported -Wextra -Wshadow -Wundef -Wno-unused-command-line-argument -Wno-attributes -Wno-pessimizing-move -Wno-c++11-extensions -Wno-noexcept-type -Wno-atomic-alignment -Wno-user-defined-literals -Wno-tautological-compare -Wsign-compare -Wunused-variable -Wunused-parameter -Wunreachable-code -Wno-unused-local-typedef -D_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER -D_LIBCPP_ENABLE_EXPERIMENTAL -D_LIBCPP_DISABLE_AVAILABILITY -fcoroutines-ts -Werror=thread-safety -Wuser-defined-warnings -lc++experimental -nostdlib++ -L /home/libcxx-builder/.buildkite-agent/builds/a3d04245fddf-1/llvm-project/libcxx-ci/build/generic-modules/lib -Wl,-rpath,/home/libcxx-builder/.buildkite-agent/builds/a3d04245fddf-1/llvm-project/libcxx-ci/build/generic-modules/lib -lc++ -pthread -o /home/libcxx-builder/.buildkite-agent/builds/a3d04245fddf-1/llvm-project/libcxx-ci/build/generic-modules/test/libcxx/algorithms/Output/ranges_robust_against_copying_comparators.pass.cpp.dir/t.tmp.exe
2,810 mslibcxx CI Modular build > llvm-libc++-shared-cfg-in.libcxx/algorithms::ranges_robust_against_copying_projections.pass.cpp
Script: -- : 'COMPILED WITH'; /usr/bin/clang++-16 /home/libcxx-builder/.buildkite-agent/builds/a3d04245fddf-1/llvm-project/libcxx-ci/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp --target=x86_64-unknown-linux-gnu -nostdinc++ -I /home/libcxx-builder/.buildkite-agent/builds/a3d04245fddf-1/llvm-project/libcxx-ci/build/generic-modules/include/c++/v1 -I /home/libcxx-builder/.buildkite-agent/builds/a3d04245fddf-1/llvm-project/libcxx-ci/build/generic-modules/include/c++/v1 -I /home/libcxx-builder/.buildkite-agent/builds/a3d04245fddf-1/llvm-project/libcxx-ci/libcxx/test/support -std=c++2b -fmodules -fcxx-modules -Werror -Wall -Wctad-maybe-unsupported -Wextra -Wshadow -Wundef -Wno-unused-command-line-argument -Wno-attributes -Wno-pessimizing-move -Wno-c++11-extensions -Wno-noexcept-type -Wno-atomic-alignment -Wno-user-defined-literals -Wno-tautological-compare -Wsign-compare -Wunused-variable -Wunused-parameter -Wunreachable-code -Wno-unused-local-typedef -D_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER -D_LIBCPP_ENABLE_EXPERIMENTAL -D_LIBCPP_DISABLE_AVAILABILITY -fcoroutines-ts -Werror=thread-safety -Wuser-defined-warnings -lc++experimental -nostdlib++ -L /home/libcxx-builder/.buildkite-agent/builds/a3d04245fddf-1/llvm-project/libcxx-ci/build/generic-modules/lib -Wl,-rpath,/home/libcxx-builder/.buildkite-agent/builds/a3d04245fddf-1/llvm-project/libcxx-ci/build/generic-modules/lib -lc++ -pthread -o /home/libcxx-builder/.buildkite-agent/builds/a3d04245fddf-1/llvm-project/libcxx-ci/build/generic-modules/test/libcxx/algorithms/Output/ranges_robust_against_copying_projections.pass.cpp.dir/t.tmp.exe
5,350 mslibcxx CI Modular build > llvm-libc++-shared-cfg-in.libcxx/diagnostics::ranges.nodiscard_extensions.compile.pass.cpp
Script: -- : 'COMPILED WITH'; /usr/bin/clang++-16 /home/libcxx-builder/.buildkite-agent/builds/a3d04245fddf-1/llvm-project/libcxx-ci/libcxx/test/libcxx/diagnostics/ranges.nodiscard_extensions.compile.pass.cpp --target=x86_64-unknown-linux-gnu -nostdinc++ -I /home/libcxx-builder/.buildkite-agent/builds/a3d04245fddf-1/llvm-project/libcxx-ci/build/generic-modules/include/c++/v1 -I /home/libcxx-builder/.buildkite-agent/builds/a3d04245fddf-1/llvm-project/libcxx-ci/build/generic-modules/include/c++/v1 -I /home/libcxx-builder/.buildkite-agent/builds/a3d04245fddf-1/llvm-project/libcxx-ci/libcxx/test/support -std=c++2b -fmodules -fcxx-modules -Werror -Wall -Wctad-maybe-unsupported -Wextra -Wshadow -Wundef -Wno-unused-command-line-argument -Wno-attributes -Wno-pessimizing-move -Wno-c++11-extensions -Wno-noexcept-type -Wno-atomic-alignment -Wno-user-defined-literals -Wno-tautological-compare -Wsign-compare -Wunused-variable -Wunused-parameter -Wunreachable-code -Wno-unused-local-typedef -D_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER -D_LIBCPP_ENABLE_EXPERIMENTAL -D_LIBCPP_DISABLE_AVAILABILITY -fcoroutines-ts -Werror=thread-safety -Wuser-defined-warnings -D_LIBCPP_DISABLE_NODISCARD_EXT -fsyntax-only
View Full Test Results (10 Failed)

Event Timeline

philnik created this revision.Dec 7 2022, 9:42 AM
Herald added a project: Restricted Project. · View Herald TranscriptDec 7 2022, 9:42 AM
philnik updated this revision to Diff 481166.Dec 8 2022, 12:20 AM

Add a benchmark and tests

philnik updated this revision to Diff 481274.Dec 8 2022, 7:43 AM

Generate files

philnik updated this revision to Diff 481463.Dec 8 2022, 3:28 PM

Fix some stuff

philnik retitled this revision from [libc++] Forward to std::memcmp for trivially comparable types to [libc++] Forward to std::memcmp for trivially comparable types in equal.Dec 8 2022, 4:33 PM
philnik updated this revision to Diff 481490.Dec 8 2022, 6:09 PM

Try to fix CI

philnik updated this revision to Diff 481597.Dec 9 2022, 3:53 AM

Try to fix CI

philnik updated this revision to Diff 481867.Dec 10 2022, 9:18 AM

Fix C++03

philnik published this revision for review.Dec 10 2022, 3:23 PM
--------------------------------------------------------
Benchmark                              old           new
--------------------------------------------------------
bm_equal_iter/1                   0.926 ns       2.08 ns
bm_equal_iter/2                    1.36 ns       2.20 ns
bm_equal_iter/3                    1.78 ns       2.10 ns
bm_equal_iter/4                    2.26 ns       2.10 ns
bm_equal_iter/5                    2.72 ns       2.09 ns
bm_equal_iter/6                    3.20 ns       2.10 ns
bm_equal_iter/7                    3.63 ns       2.10 ns
bm_equal_iter/8                    4.11 ns       2.10 ns
bm_equal_iter/16                   7.84 ns       2.10 ns
bm_equal_iter/64                   30.6 ns       1.89 ns
bm_equal_iter/512                   241 ns       6.41 ns
bm_equal_iter/4096                 1895 ns       40.9 ns
bm_equal_iter/32768               15152 ns        485 ns
bm_equal_iter/262144             120923 ns       4331 ns
bm_equal_iter/1048576            484883 ns      20014 ns
bm_equal/1                         1.16 ns       2.31 ns
bm_equal/2                         1.51 ns       2.32 ns
bm_equal/3                         1.85 ns       2.32 ns
bm_equal/4                         2.31 ns       2.32 ns
bm_equal/5                         2.87 ns       2.32 ns
bm_equal/6                         3.27 ns       2.32 ns
bm_equal/7                         3.75 ns       2.32 ns
bm_equal/8                         4.19 ns       2.32 ns
bm_equal/16                        7.88 ns       2.32 ns
bm_equal/64                        30.4 ns       2.09 ns
bm_equal/512                        241 ns       6.54 ns
bm_equal/4096                      1892 ns       41.1 ns
bm_equal/32768                    15078 ns        483 ns
bm_equal/262144                  120725 ns       4318 ns
bm_equal/1048576                 482791 ns      19228 ns
bm_ranges_equal/1                  1.16 ns       2.08 ns
bm_ranges_equal/2                  1.50 ns       2.09 ns
bm_ranges_equal/3                  1.85 ns       2.09 ns
bm_ranges_equal/4                  2.20 ns       2.09 ns
bm_ranges_equal/5                  2.54 ns       2.09 ns
bm_ranges_equal/6                  2.89 ns       2.09 ns
bm_ranges_equal/7                  3.24 ns       2.10 ns
bm_ranges_equal/8                  3.58 ns       2.09 ns
bm_ranges_equal/16                 6.36 ns       2.10 ns
bm_ranges_equal/64                 28.5 ns       1.87 ns
bm_ranges_equal/512                 183 ns       6.41 ns
bm_ranges_equal/4096               1428 ns       41.3 ns
bm_ranges_equal/32768             11390 ns        483 ns
bm_ranges_equal/262144            91268 ns       4187 ns
bm_ranges_equal/1048576          363866 ns      20177 ns

Note that this decreases binary size at the same time, since this forwards to a C library function now.

Herald added a project: Restricted Project. · View Herald TranscriptDec 10 2022, 3:23 PM
Herald added a reviewer: Restricted Project. · View Herald Transcript
--------------------------------------------------------
Benchmark                              old           new
--------------------------------------------------------
bm_equal_iter/1                   0.926 ns       2.08 ns
bm_equal_iter/2                    1.36 ns       2.20 ns
bm_equal_iter/3                    1.78 ns       2.10 ns

I assume these are slower due to the extra function call overhead.

bm_equal_iter/32768 15152 ns 485 ns
bm_equal_iter/262144 120923 ns 4331 ns
bm_equal_iter/1048576 484883 ns 20014 ns

nice improvements!

Note that this decreases binary size at the same time, since this forwards to a C library function now.

For my curiosity can you share these numbers?

I'm in general happy with the patch, but I've some concern regarding one of the new type traits. I think it would be good to have a second pair of eyes for ranges experts.

libcxx/benchmarks/CMakeLists.txt
111

Why is this needed? Is it portable on all (Linux) platforms?

libcxx/benchmarks/algorithms/equal.bench.cpp
2

Please add the copyright header.

libcxx/include/__algorithm/comp.h
14

Can you add these to the type_traits header too.

libcxx/include/__algorithm/ranges_equal.h
24

Was pair already required?
Or is this to fix the modular build?
When it's the latter, the proper fix would be to export this header from __algorithm/unwrap_range.h.

libcxx/include/__type_traits/is_comparable.h
38

This looks really odd, and it would be nice to have comment why this design is chosen.
Why are the following types not in the set, floating-point values, enums, pointers.

Is __is_trivially_equality_comparable<int, float> true? The other way around isn't.

I really want some internal tests for this type trait.

libcxx/test/std/algorithms/robust_against_adl.compile.pass.cpp
14

Not entirely happy with this, but lets see what gcc-13 brings in the future.

philnik updated this revision to Diff 482961.Dec 14 2022, 12:24 PM
philnik marked 4 inline comments as done.

Address comments

libcxx/benchmarks/CMakeLists.txt
111

I'm not actually sure why it's needed, but on my system libbenchmark.a is in lib64 and not lib. I don't really see how it wouldn't be portable, since the directory just gets ignored if it doesn't exist. I didn't actually plan to change it in this patch, but it shouldn't be a huge problem.

libcxx/include/__type_traits/is_comparable.h
38

This looks really odd, and it would be nice to have comment why this design is chosen.

Could you elaborate on what's really odd about this design?

Why are the following types not in the set, floating-point values, enums, pointers.

floating-point: 0.f == -0.f is true, but they have different binary representations.
enum: AFAIK you are allowed to define your own operator== for enums, so we don't know that UserEnum::Value1 == UserEnum::Value2 is actually the same as comparing their binary representations unless we have compiler support. (That would even allow us to optimize for structs that have bool operator==(const Struct&) = default;)
pointers: are added through the specialization in line 40.

Is __is_trivially_equality_comparable<int, float> true? The other way around isn't.

No, is_same_v<inf, float> is false.

I really want some internal tests for this type trait.

I'll add some.

Mordante added inline comments.Dec 15 2022, 10:30 AM
libcxx/benchmarks/CMakeLists.txt
111

I've no strong objection against it, if breaks the benchmarks for users we can revert it.

libcxx/include/__algorithm/unwrap_iter.h
71

This will only be used in C++20 or later.

72
libcxx/include/__type_traits/is_comparable.h
38

Thanks I see I missed the is_same. I still feel it would be good to add some comment to this file what you mean with trivially equality comparable. It's not a "normal" term and it may be misleading

struct foo {
  int bar;
  bool operator==(const foo&) = default;
};

This struct is trivial, but not trivially equality comparable. I would not be surprised to see a paper proposing a similar type trait.

libcxx/test/libcxx/type_traits/is_trivially_comparable.compile.pass.cpp
38

Please add static_assert(!std::__is_trivially_equality_comparable<float, float>::value, ""); test

philnik updated this revision to Diff 487156.Sun, Jan 8, 3:43 AM
philnik marked 3 inline comments as done.

Address comments

libcxx/include/__type_traits/is_comparable.h
38

I would actually consider your example to be trivially equality comparable, since memcmp would give the correct result. It's just that we can't detect this as trivially equality comparable without compiler support. (kind-of a tangent: would it be possible to detect with reflection? That would be really neat.)

philnik updated this revision to Diff 492360.Thu, Jan 26, 1:48 AM

Try to fix CI