diff --git a/libcxx/benchmarks/CMakeLists.txt b/libcxx/benchmarks/CMakeLists.txt --- a/libcxx/benchmarks/CMakeLists.txt +++ b/libcxx/benchmarks/CMakeLists.txt @@ -176,6 +176,7 @@ algorithms/sort.bench.cpp algorithms/sort_heap.bench.cpp algorithms/stable_sort.bench.cpp + libcxxabi/dynamic_cast.bench.cpp allocation.bench.cpp deque.bench.cpp deque_iterator.bench.cpp diff --git a/libcxx/benchmarks/libcxxabi/dynamic_cast.bench.cpp b/libcxx/benchmarks/libcxxabi/dynamic_cast.bench.cpp new file mode 100644 --- /dev/null +++ b/libcxx/benchmarks/libcxxabi/dynamic_cast.bench.cpp @@ -0,0 +1,172 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +#include "benchmark/benchmark.h" + +template +struct Chain : Chain {}; + +template <> +struct Chain<0> { + virtual ~Chain() noexcept = default; +}; + +template +struct Dag : Dag, Dag {}; + +template +struct Dag { + virtual ~Dag() noexcept = default; +}; + +template +struct VChain : virtual VChain {}; + +template <> +struct VChain<0> { + virtual ~VChain() noexcept = default; +}; + +template +struct VDag : virtual VDag, virtual VDag {}; + +template +struct VDag { + virtual ~VDag() noexcept = default; +}; + +template +static void DynCast(benchmark::State& state) { + Dyn obj; + From* from_ptr = &obj; + for (auto _ : state) { + To* to_ptr = dynamic_cast(from_ptr); + benchmark::DoNotOptimize(to_ptr); + } +} + +static void StaticCast(benchmark::State& state) { + Chain<9> obj; + Chain<0>* from_ptr = &obj; + for (auto _ : state) { + Chain<9>* to_ptr = static_cast*>(from_ptr); + benchmark::DoNotOptimize(to_ptr); + } +} + +// Downcast along a chain from base to the most derived type +BENCHMARK(DynCast, Chain<0>>)->Name("Chain, 1 level"); +BENCHMARK(DynCast, Chain<0>>)->Name("Chain, 2 levels"); +BENCHMARK(DynCast, Chain<0>>)->Name("Chain, 3 levels"); +BENCHMARK(DynCast, Chain<0>>)->Name("Chain, 4 levels"); +BENCHMARK(DynCast, Chain<0>>)->Name("Chain, 5 levels"); +BENCHMARK(DynCast, Chain<0>>)->Name("Chain, 6 levels"); +BENCHMARK(DynCast, Chain<0>>)->Name("Chain, 7 levels"); +BENCHMARK(DynCast, Chain<0>>)->Name("Chain, 8 levels"); +BENCHMARK(DynCast, Chain<0>>)->Name("Chain, 9 levels"); + +// Downcast along a chain from base to the middle of the chain +BENCHMARK(DynCast, Chain<0>, Chain<1>>)->Name("Chain middle, 1 level"); +BENCHMARK(DynCast, Chain<0>, Chain<2>>)->Name("Chain middle, 2 levels"); +BENCHMARK(DynCast, Chain<0>, Chain<3>>)->Name("Chain middle, 3 levels"); +BENCHMARK(DynCast, Chain<0>, Chain<4>>)->Name("Chain middle, 4 levels"); + +// Downcast along a chain that fails +BENCHMARK(DynCast, Chain<0>, Chain<9>>)->Name("Chain fail, 1 level"); +BENCHMARK(DynCast, Chain<0>, Chain<9>>)->Name("Chain fail, 2 levels"); +BENCHMARK(DynCast, Chain<0>, Chain<9>>)->Name("Chain fail, 3 levels"); +BENCHMARK(DynCast, Chain<0>, Chain<9>>)->Name("Chain fail, 4 levels"); +BENCHMARK(DynCast, Chain<0>, Chain<9>>)->Name("Chain fail, 5 levels"); +BENCHMARK(DynCast, Chain<0>, Chain<9>>)->Name("Chain fail, 6 levels"); +BENCHMARK(DynCast, Chain<0>, Chain<9>>)->Name("Chain fail, 7 levels"); +BENCHMARK(DynCast, Chain<0>, Chain<9>>)->Name("Chain fail, 8 levels"); + +// Downcast along a virtual inheritance chain from base to the most derived type +BENCHMARK(DynCast, VChain<0>>)->Name("VChain, 1 level"); +BENCHMARK(DynCast, VChain<0>>)->Name("VChain, 2 levels"); +BENCHMARK(DynCast, VChain<0>>)->Name("VChain, 3 levels"); +BENCHMARK(DynCast, VChain<0>>)->Name("VChain, 4 levels"); +BENCHMARK(DynCast, VChain<0>>)->Name("VChain, 5 levels"); + +// Downcast along a virtual inheritance chain from base to the middle of the chain +BENCHMARK(DynCast, VChain<0>, VChain<1>>)->Name("VChain middle, 1 level"); +BENCHMARK(DynCast, VChain<0>, VChain<2>>)->Name("VChain middle, 2 levels"); +BENCHMARK(DynCast, VChain<0>, VChain<3>>)->Name("VChain middle, 3 levels"); +BENCHMARK(DynCast, VChain<0>, VChain<4>>)->Name("VChain middle, 4 levels"); + +// Downcast along a virtual chain that fails +BENCHMARK(DynCast, VChain<0>, VChain<8>>)->Name("VChain fail, 1 level"); +BENCHMARK(DynCast, VChain<0>, VChain<8>>)->Name("VChain fail, 2 levels"); +BENCHMARK(DynCast, VChain<0>, VChain<8>>)->Name("VChain fail, 3 levels"); +BENCHMARK(DynCast, VChain<0>, VChain<8>>)->Name("VChain fail, 4 levels"); +BENCHMARK(DynCast, VChain<0>, VChain<8>>)->Name("VChain fail, 5 levels"); + +// Downcast along a DAG from base to the most derived type +BENCHMARK(DynCast, Dag<3, 0>>)->Name("DAG rightmost, 3 levels"); +BENCHMARK(DynCast, Dag<4, 0>>)->Name("DAG rightmost, 4 levels"); +BENCHMARK(DynCast, Dag<5, 0>>)->Name("DAG rightmost, 5 levels"); +BENCHMARK(DynCast, Dag<0, 0>>)->Name("DAG leftmost, 3 levels"); +BENCHMARK(DynCast, Dag<0, 0>>)->Name("DAG leftmost, 4 levels"); +BENCHMARK(DynCast, Dag<0, 0>>)->Name("DAG leftmost, 5 levels"); + +// Downcast along a DAG from base to the middle of the DAG +BENCHMARK(DynCast, Dag<4, 0>, Dag<3, 1>>)->Name("DAG rightmost middle, 1 level"); +BENCHMARK(DynCast, Dag<4, 0>, Dag<2, 2>>)->Name("DAG rightmost middle, 2 levels"); +BENCHMARK(DynCast, Dag<4, 0>, Dag<1, 3>>)->Name("DAG rightmost middle, 3 levels"); +BENCHMARK(DynCast, Dag<0, 0>, Dag<0, 1>>)->Name("DAG leftmost middle, 1 level"); +BENCHMARK(DynCast, Dag<0, 0>, Dag<0, 2>>)->Name("DAG leftmost middle, 2 levels"); +BENCHMARK(DynCast, Dag<0, 0>, Dag<0, 3>>)->Name("DAG leftmost middle, 3 levels"); + +// Sidecast along a DAG +BENCHMARK(DynCast, Dag<3, 0>, Dag<0, 0>>)->Name("DAG sidecast, 3 levels"); +BENCHMARK(DynCast, Dag<2, 1>, Dag<0, 1>>)->Name("DAG sidecast, 2 levels"); +BENCHMARK(DynCast, Dag<1, 2>, Dag<0, 2>>)->Name("DAG sidecast, 1 level"); + +// Sidecast along a DAG that fails +BENCHMARK(DynCast, Dag<3, 0>, Dag<0, 4>>)->Name("DAG sidecast fail, 3 levels"); +BENCHMARK(DynCast, Dag<2, 1>, Dag<0, 4>>)->Name("DAG sidecast fail, 2 levels"); +BENCHMARK(DynCast, Dag<1, 2>, Dag<0, 4>>)->Name("DAG sidecast fail, 1 level"); + +// Downcast along a virtual inheritance DAG from base to the most derived type +BENCHMARK(DynCast, VDag<3, 0>>)->Name("VDAG rightmost, 3 levels"); +BENCHMARK(DynCast, VDag<4, 0>>)->Name("VDAG rightmost, 4 levels"); +BENCHMARK(DynCast, VDag<5, 0>>)->Name("VDAG rightmost, 5 levels"); +BENCHMARK(DynCast, VDag<0, 0>>)->Name("VDAG leftmost, 3 levels"); +BENCHMARK(DynCast, VDag<0, 0>>)->Name("VDAG leftmost, 4 levels"); +BENCHMARK(DynCast, VDag<0, 0>>)->Name("VDAG leftmost, 5 levels"); + +// Downcast along a virtual inheritance DAG from base to the middle of the DAG +BENCHMARK(DynCast, VDag<3, 0>, VDag<2, 1>>)->Name("VDAG rightmost middle, 1 level"); +BENCHMARK(DynCast, VDag<4, 0>, VDag<2, 2>>)->Name("VDAG rightmost middle, 2 levels"); +BENCHMARK(DynCast, VDag<5, 0>, VDag<2, 3>>)->Name("VDAG rightmost middle, 3 levels"); +BENCHMARK(DynCast, VDag<0, 0>, VDag<0, 1>>)->Name("VDAG leftmost middle, 1 level"); +BENCHMARK(DynCast, VDag<0, 0>, VDag<0, 2>>)->Name("VDAG leftmost middle, 2 levels"); +BENCHMARK(DynCast, VDag<0, 0>, VDag<0, 3>>)->Name("VDAG leftmost middle, 3 levels"); + +// Sidecast along a virtual inheritance DAG +BENCHMARK(DynCast, VDag<3, 0>, VDag<0, 0>>)->Name("VDAG sidecast, 3 levels"); +BENCHMARK(DynCast, VDag<2, 1>, VDag<0, 1>>)->Name("VDAG sidecast, 2 levels"); +BENCHMARK(DynCast, VDag<1, 2>, VDag<0, 2>>)->Name("VDAG sidecast, 1 level"); + +// Sidecast along a virtual inheritance DAG that fails +BENCHMARK(DynCast, VDag<3, 0>, VDag<0, 4>>)->Name("VDAG sidecast fail, 3 levels"); +BENCHMARK(DynCast, VDag<2, 1>, VDag<0, 4>>)->Name("VDAG sidecast fail, 2 levels"); +BENCHMARK(DynCast, VDag<1, 2>, VDag<0, 4>>)->Name("VDAG sidecast fail, 1 level"); + +// Cast to complete object pointer +BENCHMARK(DynCast, Chain<0>, void>)->Name("Chain to complete"); +BENCHMARK(DynCast, VChain<0>, void>)->Name("VChain to complete"); +BENCHMARK(DynCast, Dag<3, 0>, void>)->Name("DAG to complete"); +BENCHMARK(DynCast, VDag<3, 0>, void>)->Name("VDAG to complete"); + +// Static cast as the baseline. +BENCHMARK(StaticCast)->Name("Static"); + +BENCHMARK_MAIN(); diff --git a/libcxx/docs/ReleaseNotes.rst b/libcxx/docs/ReleaseNotes.rst --- a/libcxx/docs/ReleaseNotes.rst +++ b/libcxx/docs/ReleaseNotes.rst @@ -48,6 +48,9 @@ - ``std::string_view`` now provides iterators that check for out-of-bounds accesses when the safe libc++ mode is enabled. +- The performance of ``dynamic_cast`` on its hot paths is greatly improved and is as efficient as the + ``libsupc++`` implementation. Note that the performance improvements are shipped in ``libcxxabi``. + Deprecations and Removals ------------------------- diff --git a/libcxxabi/src/private_typeinfo.cpp b/libcxxabi/src/private_typeinfo.cpp --- a/libcxxabi/src/private_typeinfo.cpp +++ b/libcxxabi/src/private_typeinfo.cpp @@ -41,6 +41,7 @@ // Defining _LIBCXXABI_FORGIVING_DYNAMIC_CAST does not help since can_catch() calls // is_equal() with use_strcmp=false so the string names are not compared. +#include #include #ifdef _LIBCXXABI_FORGIVING_DYNAMIC_CAST @@ -656,77 +657,138 @@ // Find out if we can use a giant short cut in the search if (is_equal(dynamic_type, dst_type, false)) { - // Using giant short cut. Add that information to info. - info.number_of_dst_type = 1; - // Do the search - dynamic_type->search_above_dst(&info, dynamic_ptr, dynamic_ptr, public_path, false); -#ifdef _LIBCXXABI_FORGIVING_DYNAMIC_CAST - // The following if should always be false because we should definitely - // find (static_ptr, static_type), either on a public or private path - if (info.path_dst_ptr_to_static_ptr == unknown) + // We're downcasting from src_type to the complete object's dynamic + // type. This is a really hot path that can be further optimized + // with the `src2dst_offset` hint. + // In such a case, dynamic_ptr already gives the casting result if the + // casting ever succeeds. All we have to do now is to check + // static_ptr points to a public base sub-object of dynamic_ptr. + + if (src2dst_offset >= 0) { - // We get here only if there is some kind of visibility problem - // in client code. - static_assert(std::atomic::is_always_lock_free, ""); - static std::atomic error_count(0); - size_t error_count_snapshot = error_count.fetch_add(1, std::memory_order_relaxed); - if ((error_count_snapshot & (error_count_snapshot-1)) == 0) - syslog(LOG_ERR, "dynamic_cast error 1: Both of the following type_info's " - "should have public visibility. At least one of them is hidden. %s" - ", %s.\n", static_type->name(), dynamic_type->name()); - // Redo the search comparing type_info's using strcmp - info = {dst_type, static_ptr, static_type, src2dst_offset, 0}; - info.number_of_dst_type = 1; - dynamic_type->search_above_dst(&info, dynamic_ptr, dynamic_ptr, public_path, true); + // The static type is a unique public non-virtual base type of + // dst_type at offset `src2dst_offset` from the origin of dst. + // Note that there might be other non-public static_type bases. The + // hint only guarantees that the public base is non-virtual and + // unique. So we have to check whether static_ptr points to that + // unique public base sub-object. + if (offset_to_derived == -src2dst_offset) + dst_ptr = dynamic_ptr; + } + else if (src2dst_offset == -2) + { + // static_type is not a public base of dst_type. + dst_ptr = nullptr; } + else + { + // If src2dst_offset == -3, then: + // src_type is a multiple public base type but never a virtual + // base type. We can't conclude that static_ptr points to those + // public base sub-objects because there might be other non- + // public static_type bases. The search is inevitable. + + // Fallback to the slow path to check that static_type is a public + // base type of dynamic_type. + // Using giant short cut. Add that information to info. + info.number_of_dst_type = 1; + // Do the search + dynamic_type->search_above_dst(&info, dynamic_ptr, dynamic_ptr, public_path, false); +#ifdef _LIBCXXABI_FORGIVING_DYNAMIC_CAST + // The following if should always be false because we should + // definitely find (static_ptr, static_type), either on a public + // or private path + if (info.path_dst_ptr_to_static_ptr == unknown) + { + // We get here only if there is some kind of visibility problem + // in client code. + static_assert(std::atomic::is_always_lock_free, ""); + static std::atomic error_count(0); + size_t error_count_snapshot = error_count.fetch_add(1, std::memory_order_relaxed); + if ((error_count_snapshot & (error_count_snapshot-1)) == 0) + syslog(LOG_ERR, "dynamic_cast error 1: Both of the following type_info's " + "should have public visibility. At least one of them is hidden. %s" + ", %s.\n", static_type->name(), dynamic_type->name()); + // Redo the search comparing type_info's using strcmp + info = {dst_type, static_ptr, static_type, src2dst_offset, 0}; + info.number_of_dst_type = 1; + dynamic_type->search_above_dst(&info, dynamic_ptr, dynamic_ptr, public_path, true); + } #endif // _LIBCXXABI_FORGIVING_DYNAMIC_CAST - // Query the search. - if (info.path_dst_ptr_to_static_ptr == public_path) - dst_ptr = dynamic_ptr; + // Query the search. + if (info.path_dst_ptr_to_static_ptr == public_path) + dst_ptr = dynamic_ptr; + } } else { - // Not using giant short cut. Do the search - dynamic_type->search_below_dst(&info, dynamic_ptr, public_path, false); - #ifdef _LIBCXXABI_FORGIVING_DYNAMIC_CAST - // The following if should always be false because we should definitely - // find (static_ptr, static_type), either on a public or private path - if (info.path_dst_ptr_to_static_ptr == unknown && - info.path_dynamic_ptr_to_static_ptr == unknown) + if (src2dst_offset >= 0) { - static_assert(std::atomic::is_always_lock_free, ""); - static std::atomic error_count(0); - size_t error_count_snapshot = error_count.fetch_add(1, std::memory_order_relaxed); - if ((error_count_snapshot & (error_count_snapshot-1)) == 0) - syslog(LOG_ERR, "dynamic_cast error 2: One or more of the following type_info's " - "has hidden visibility or is defined in more than one translation " - "unit. They should all have public visibility. " - "%s, %s, %s.\n", static_type->name(), dynamic_type->name(), - dst_type->name()); - // Redo the search comparing type_info's using strcmp - info = {dst_type, static_ptr, static_type, src2dst_offset, 0}; - dynamic_type->search_below_dst(&info, dynamic_ptr, public_path, true); + // Optimize toward downcasting: dst_type has one unique public + // static_type bases. Let's first try to do a downcast before + // falling back to the slow path. The downcast succeeds if there + // is at least one path regardless of visibility from + // dynamic_type to dst_type. + const void* dst_ptr_to_static = reinterpret_cast(static_ptr) - src2dst_offset; + if (reinterpret_cast(dst_ptr_to_static) >= reinterpret_cast(dynamic_ptr)) + { + // Try to search a path from dynamic_type to dst_type. + __dynamic_cast_info dynamic_to_dst_info = {dynamic_type, dst_ptr_to_static, dst_type, src2dst_offset}; + dynamic_to_dst_info.number_of_dst_type = 1; + dynamic_type->search_above_dst(&dynamic_to_dst_info, dynamic_ptr, dynamic_ptr, public_path, false); + if (dynamic_to_dst_info.path_dst_ptr_to_static_ptr != unknown) { + // We have found at least one path from dynamic_ptr to + // dst_ptr. The downcast can succeed. + dst_ptr = dst_ptr_to_static; + } + } } -#endif // _LIBCXXABI_FORGIVING_DYNAMIC_CAST - // Query the search. - switch (info.number_to_static_ptr) + + if (!dst_ptr) { - case 0: - if (info.number_to_dst_ptr == 1 && - info.path_dynamic_ptr_to_static_ptr == public_path && - info.path_dynamic_ptr_to_dst_ptr == public_path) - dst_ptr = info.dst_ptr_not_leading_to_static_ptr; - break; - case 1: - if (info.path_dst_ptr_to_static_ptr == public_path || - ( - info.number_to_dst_ptr == 0 && - info.path_dynamic_ptr_to_static_ptr == public_path && - info.path_dynamic_ptr_to_dst_ptr == public_path - ) - ) - dst_ptr = info.dst_ptr_leading_to_static_ptr; - break; + // Not using giant short cut. Do the search + dynamic_type->search_below_dst(&info, dynamic_ptr, public_path, false); +#ifdef _LIBCXXABI_FORGIVING_DYNAMIC_CAST + // The following if should always be false because we should + // definitely find (static_ptr, static_type), either on a public + // or private path + if (info.path_dst_ptr_to_static_ptr == unknown && + info.path_dynamic_ptr_to_static_ptr == unknown) + { + static_assert(std::atomic::is_always_lock_free, ""); + static std::atomic error_count(0); + size_t error_count_snapshot = error_count.fetch_add(1, std::memory_order_relaxed); + if ((error_count_snapshot & (error_count_snapshot-1)) == 0) + syslog(LOG_ERR, "dynamic_cast error 2: One or more of the following type_info's " + "has hidden visibility or is defined in more than one translation " + "unit. They should all have public visibility. " + "%s, %s, %s.\n", static_type->name(), dynamic_type->name(), + dst_type->name()); + // Redo the search comparing type_info's using strcmp + info = {dst_type, static_ptr, static_type, src2dst_offset, 0}; + dynamic_type->search_below_dst(&info, dynamic_ptr, public_path, true); + } +#endif // _LIBCXXABI_FORGIVING_DYNAMIC_CAST + // Query the search. + switch (info.number_to_static_ptr) + { + case 0: + if (info.number_to_dst_ptr == 1 && + info.path_dynamic_ptr_to_static_ptr == public_path && + info.path_dynamic_ptr_to_dst_ptr == public_path) + dst_ptr = info.dst_ptr_not_leading_to_static_ptr; + break; + case 1: + if (info.path_dst_ptr_to_static_ptr == public_path || + ( + info.number_to_dst_ptr == 0 && + info.path_dynamic_ptr_to_static_ptr == public_path && + info.path_dynamic_ptr_to_dst_ptr == public_path + ) + ) + dst_ptr = info.dst_ptr_leading_to_static_ptr; + break; + } } } return const_cast(dst_ptr);