From c73ae711bf403585de403bcfeb7519dd989d4c15 Mon Sep 17 00:00:00 2001 From: Jacques Lucke Date: Tue, 8 Nov 2022 15:50:49 +0100 Subject: BLI: new basic CacheMutex This patch introduces a new `CacheMutex` which makes it easy to implement lazily computed caches in e.g. `Curves`. For more details see `BLI_cache_mutex.hh`. Differential Revision: https://developer.blender.org/D16419 --- source/blender/blenkernel/BKE_curves.hh | 25 ++--- .../blender/blenkernel/intern/curves_geometry.cc | 120 +++++---------------- source/blender/blenlib/BLI_cache_mutex.hh | 106 ++++++++++++++++++ source/blender/blenlib/CMakeLists.txt | 2 + source/blender/blenlib/intern/cache_mutex.cc | 25 +++++ 5 files changed, 167 insertions(+), 111 deletions(-) create mode 100644 source/blender/blenlib/BLI_cache_mutex.hh create mode 100644 source/blender/blenlib/intern/cache_mutex.cc (limited to 'source') diff --git a/source/blender/blenkernel/BKE_curves.hh b/source/blender/blenkernel/BKE_curves.hh index 4c7ff8c1813..a479dcb574d 100644 --- a/source/blender/blenkernel/BKE_curves.hh +++ b/source/blender/blenkernel/BKE_curves.hh @@ -11,6 +11,7 @@ #include +#include "BLI_cache_mutex.hh" #include "BLI_float3x3.hh" #include "BLI_float4x4.hh" #include "BLI_generic_virtual_array.hh" @@ -80,17 +81,14 @@ class CurvesGeometryRuntime { */ mutable Vector evaluated_offsets_cache; mutable Vector bezier_evaluated_offsets; - mutable std::mutex offsets_cache_mutex; - mutable bool offsets_cache_dirty = true; + mutable CacheMutex offsets_cache_mutex; mutable Vector nurbs_basis_cache; - mutable std::mutex nurbs_basis_cache_mutex; - mutable bool nurbs_basis_cache_dirty = true; + mutable CacheMutex nurbs_basis_cache_mutex; /** Cache of evaluated positions. */ mutable Vector evaluated_position_cache; - mutable std::mutex position_cache_mutex; - mutable bool position_cache_dirty = true; + mutable CacheMutex position_cache_mutex; /** * The evaluated positions result, using a separate span in case all curves are poly curves, * in which case a separate array of evaluated positions is unnecessary. @@ -103,18 +101,15 @@ class CurvesGeometryRuntime { * make slicing this array for a curve fast, an extra float is stored for every curve. */ mutable Vector evaluated_length_cache; - mutable std::mutex length_cache_mutex; - mutable bool length_cache_dirty = true; + mutable CacheMutex length_cache_mutex; /** Direction of the curve at each evaluated point. */ mutable Vector evaluated_tangent_cache; - mutable std::mutex tangent_cache_mutex; - mutable bool tangent_cache_dirty = true; + mutable CacheMutex tangent_cache_mutex; /** Normal direction vectors for each evaluated point. */ mutable Vector evaluated_normal_cache; - mutable std::mutex normal_cache_mutex; - mutable bool normal_cache_dirty = true; + mutable CacheMutex normal_cache_mutex; }; /** @@ -909,13 +904,13 @@ inline int CurvesGeometry::evaluated_points_num() const inline IndexRange CurvesGeometry::evaluated_points_for_curve(int index) const { - BLI_assert(!this->runtime->offsets_cache_dirty); + BLI_assert(this->runtime->offsets_cache_mutex.is_cached()); return offsets_to_range(this->runtime->evaluated_offsets_cache.as_span(), index); } inline IndexRange CurvesGeometry::evaluated_points_for_curves(const IndexRange curves) const { - BLI_assert(!this->runtime->offsets_cache_dirty); + BLI_assert(this->runtime->offsets_cache_mutex.is_cached()); BLI_assert(this->curve_num > 0); const int offset = this->runtime->evaluated_offsets_cache[curves.start()]; const int offset_next = this->runtime->evaluated_offsets_cache[curves.one_after_last()]; @@ -940,7 +935,7 @@ inline IndexRange CurvesGeometry::lengths_range_for_curve(const int curve_index, inline Span CurvesGeometry::evaluated_lengths_for_curve(const int curve_index, const bool cyclic) const { - BLI_assert(!this->runtime->length_cache_dirty); + BLI_assert(this->runtime->length_cache_mutex.is_cached()); const IndexRange range = this->lengths_range_for_curve(curve_index, cyclic); return this->runtime->evaluated_length_cache.as_span().slice(range); } diff --git a/source/blender/blenkernel/intern/curves_geometry.cc b/source/blender/blenkernel/intern/curves_geometry.cc index 7c338480c71..43bdb8e7b8c 100644 --- a/source/blender/blenkernel/intern/curves_geometry.cc +++ b/source/blender/blenkernel/intern/curves_geometry.cc @@ -511,17 +511,7 @@ static void calculate_evaluated_offsets(const CurvesGeometry &curves, void CurvesGeometry::ensure_evaluated_offsets() const { - if (!this->runtime->offsets_cache_dirty) { - return; - } - - /* A double checked lock. */ - std::scoped_lock lock{this->runtime->offsets_cache_mutex}; - if (!this->runtime->offsets_cache_dirty) { - return; - } - - threading::isolate_task([&]() { + this->runtime->offsets_cache_mutex.ensure([&]() { this->runtime->evaluated_offsets_cache.resize(this->curves_num() + 1); if (this->has_curve_with_type(CURVE_TYPE_BEZIER)) { @@ -534,8 +524,6 @@ void CurvesGeometry::ensure_evaluated_offsets() const calculate_evaluated_offsets( *this, this->runtime->evaluated_offsets_cache, this->runtime->bezier_evaluated_offsets); }); - - this->runtime->offsets_cache_dirty = false; } Span CurvesGeometry::evaluated_offsets() const @@ -569,17 +557,7 @@ Array CurvesGeometry::point_to_curve_map() const void CurvesGeometry::ensure_nurbs_basis_cache() const { - if (!this->runtime->nurbs_basis_cache_dirty) { - return; - } - - /* A double checked lock. */ - std::scoped_lock lock{this->runtime->nurbs_basis_cache_mutex}; - if (!this->runtime->nurbs_basis_cache_dirty) { - return; - } - - threading::isolate_task([&]() { + this->runtime->nurbs_basis_cache_mutex.ensure([&]() { Vector nurbs_indices; const IndexMask nurbs_mask = this->indices_for_curve_type(CURVE_TYPE_NURBS, nurbs_indices); if (nurbs_mask.is_empty()) { @@ -619,23 +597,11 @@ void CurvesGeometry::ensure_nurbs_basis_cache() const } }); }); - - this->runtime->nurbs_basis_cache_dirty = false; } Span CurvesGeometry::evaluated_positions() const { - if (!this->runtime->position_cache_dirty) { - return this->runtime->evaluated_positions_span; - } - - /* A double checked lock. */ - std::scoped_lock lock{this->runtime->position_cache_mutex}; - if (!this->runtime->position_cache_dirty) { - return this->runtime->evaluated_positions_span; - } - - threading::isolate_task([&]() { + this->runtime->position_cache_mutex.ensure([&]() { if (this->is_single_type(CURVE_TYPE_POLY)) { this->runtime->evaluated_positions_span = this->positions(); this->runtime->evaluated_position_cache.clear_and_make_inline(); @@ -699,24 +665,12 @@ Span CurvesGeometry::evaluated_positions() const } }); }); - - this->runtime->position_cache_dirty = false; return this->runtime->evaluated_positions_span; } Span CurvesGeometry::evaluated_tangents() const { - if (!this->runtime->tangent_cache_dirty) { - return this->runtime->evaluated_tangent_cache; - } - - /* A double checked lock. */ - std::scoped_lock lock{this->runtime->tangent_cache_mutex}; - if (!this->runtime->tangent_cache_dirty) { - return this->runtime->evaluated_tangent_cache; - } - - threading::isolate_task([&]() { + this->runtime->tangent_cache_mutex.ensure([&]() { const Span evaluated_positions = this->evaluated_positions(); const VArray cyclic = this->cyclic(); @@ -732,9 +686,9 @@ Span CurvesGeometry::evaluated_tangents() const } }); - /* Correct the first and last tangents of non-cyclic Bezier curves so that they align with the - * inner handles. This is a separate loop to avoid the cost when Bezier type curves are not - * used. */ + /* Correct the first and last tangents of non-cyclic Bezier curves so that they align with + * the inner handles. This is a separate loop to avoid the cost when Bezier type curves are + * not used. */ Vector bezier_indices; const IndexMask bezier_mask = this->indices_for_curve_type(CURVE_TYPE_BEZIER, bezier_indices); if (!bezier_mask.is_empty()) { @@ -765,8 +719,6 @@ Span CurvesGeometry::evaluated_tangents() const }); } }); - - this->runtime->tangent_cache_dirty = false; return this->runtime->evaluated_tangent_cache; } @@ -781,17 +733,7 @@ static void rotate_directions_around_axes(MutableSpan directions, Span CurvesGeometry::evaluated_normals() const { - if (!this->runtime->normal_cache_dirty) { - return this->runtime->evaluated_normal_cache; - } - - /* A double checked lock. */ - std::scoped_lock lock{this->runtime->normal_cache_mutex}; - if (!this->runtime->normal_cache_dirty) { - return this->runtime->evaluated_normal_cache; - } - - threading::isolate_task([&]() { + this->runtime->normal_cache_mutex.ensure([&]() { const Span evaluated_tangents = this->evaluated_tangents(); const VArray cyclic = this->cyclic(); const VArray normal_mode = this->normal_mode(); @@ -842,8 +784,6 @@ Span CurvesGeometry::evaluated_normals() const } }); }); - - this->runtime->normal_cache_dirty = false; return this->runtime->evaluated_normal_cache; } @@ -851,8 +791,8 @@ void CurvesGeometry::interpolate_to_evaluated(const int curve_index, const GSpan src, GMutableSpan dst) const { - BLI_assert(!this->runtime->offsets_cache_dirty); - BLI_assert(!this->runtime->nurbs_basis_cache_dirty); + BLI_assert(this->runtime->offsets_cache_mutex.is_cached()); + BLI_assert(this->runtime->nurbs_basis_cache_mutex.is_cached()); const IndexRange points = this->points_for_curve(curve_index); BLI_assert(src.size() == points.size()); BLI_assert(dst.size() == this->evaluated_points_for_curve(curve_index).size()); @@ -881,8 +821,8 @@ void CurvesGeometry::interpolate_to_evaluated(const int curve_index, void CurvesGeometry::interpolate_to_evaluated(const GSpan src, GMutableSpan dst) const { - BLI_assert(!this->runtime->offsets_cache_dirty); - BLI_assert(!this->runtime->nurbs_basis_cache_dirty); + BLI_assert(this->runtime->offsets_cache_mutex.is_cached()); + BLI_assert(this->runtime->nurbs_basis_cache_mutex.is_cached()); const VArray types = this->curve_types(); const VArray resolution = this->resolution(); const VArray cyclic = this->cyclic(); @@ -923,17 +863,7 @@ void CurvesGeometry::interpolate_to_evaluated(const GSpan src, GMutableSpan dst) void CurvesGeometry::ensure_evaluated_lengths() const { - if (!this->runtime->length_cache_dirty) { - return; - } - - /* A double checked lock. */ - std::scoped_lock lock{this->runtime->length_cache_mutex}; - if (!this->runtime->length_cache_dirty) { - return; - } - - threading::isolate_task([&]() { + this->runtime->length_cache_mutex.ensure([&]() { /* Use an extra length value for the final cyclic segment for a consistent size * (see comment on #evaluated_length_cache). */ const int total_num = this->evaluated_points_num() + this->curves_num(); @@ -954,8 +884,6 @@ void CurvesGeometry::ensure_evaluated_lengths() const } }); }); - - this->runtime->length_cache_dirty = false; } void CurvesGeometry::ensure_can_interpolate_to_evaluated() const @@ -986,23 +914,23 @@ void CurvesGeometry::resize(const int points_num, const int curves_num) void CurvesGeometry::tag_positions_changed() { - this->runtime->position_cache_dirty = true; - this->runtime->tangent_cache_dirty = true; - this->runtime->normal_cache_dirty = true; - this->runtime->length_cache_dirty = true; + this->runtime->position_cache_mutex.tag_dirty(); + this->runtime->tangent_cache_mutex.tag_dirty(); + this->runtime->normal_cache_mutex.tag_dirty(); + this->runtime->length_cache_mutex.tag_dirty(); } void CurvesGeometry::tag_topology_changed() { - this->runtime->position_cache_dirty = true; - this->runtime->tangent_cache_dirty = true; - this->runtime->normal_cache_dirty = true; - this->runtime->offsets_cache_dirty = true; - this->runtime->nurbs_basis_cache_dirty = true; - this->runtime->length_cache_dirty = true; + this->runtime->position_cache_mutex.tag_dirty(); + this->runtime->tangent_cache_mutex.tag_dirty(); + this->runtime->normal_cache_mutex.tag_dirty(); + this->runtime->offsets_cache_mutex.tag_dirty(); + this->runtime->nurbs_basis_cache_mutex.tag_dirty(); + this->runtime->length_cache_mutex.tag_dirty(); } void CurvesGeometry::tag_normals_changed() { - this->runtime->normal_cache_dirty = true; + this->runtime->normal_cache_mutex.tag_dirty(); } static void translate_positions(MutableSpan positions, const float3 &translation) diff --git a/source/blender/blenlib/BLI_cache_mutex.hh b/source/blender/blenlib/BLI_cache_mutex.hh new file mode 100644 index 00000000000..8e2a0d1b1a5 --- /dev/null +++ b/source/blender/blenlib/BLI_cache_mutex.hh @@ -0,0 +1,106 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ + +#pragma once + +/** + * A #CacheMutex is used to protect a lazily computed cache from being computed more than once. + * Using #CacheMutex instead of a "raw mutex" to protect a cache has some benefits: + * - Avoid common pitfalls like forgetting to use task isolation or a double checked lock. + * - Cleaner and less redundant code because the same locking patterns don't have to be repeated + * everywhere. + * - One can benefit from potential future improvements to #CacheMutex of which there are a few + * mentioned below. + * + * The data protected by #CacheMutex is not part of #CacheMutex. Instead, the #CacheMutex and its + * protected data should generally be placed next to each other. + * + * Each #CacheMutex protects exactly one cache, so multiple cache mutexes have to be used when a + * class has multiple caches. That is contrary to a "custom" solution using `std::mutex` where one + * mutex could protect multiple caches at the cost of higher lock contention. + * + * To make sure the cache is up to date, call `CacheMutex::ensure` and pass in the function that + * computes the cache. + * + * To tell the #CacheMutex that the cache is invalidated and to be re-evaluated upon next access + * use `CacheMutex::tag_dirty`. + * + * This example shows how one could implement a lazily computed average vertex position in an + * imaginary `Mesh` data structure: + * + * \code{.cpp} + * class Mesh { + * private: + * mutable CacheMutex average_position_cache_mutex_; + * mutable float3 average_position_cache_; + * + * public: + * const float3 &average_position() const + * { + * average_position_cache_mutex_.ensure([&]() { + * average_position_cache_ = actually_compute_average_position(); + * }); + * return average_position_cache_; + * } + * + * void tag_positions_changed() + * { + * average_position_cache_mutex_.tag_dirty(); + * } + * }; + * \endcode + * + * Possible future improvements: + * - Avoid task isolation when we know that the cache computation does not use threading. + * - Try to use a smaller mutex. The mutex does not have to be fair for this use case. + * - Try to join the cache computation instead of blocking if another thread is computing the cache + * already. + */ + +#include +#include + +#include "BLI_function_ref.hh" + +namespace blender { + +class CacheMutex { + private: + std::mutex mutex_; + std::atomic cache_valid_ = false; + + public: + /** + * Make sure the cache exists and is up to date. This calls `compute_cache` once to update the + * cache (which is stored outside of this class) if it is dirty, otherwise it does nothing. + * + * This function is thread-safe under the assumption that the same parameters are passed from + * every thread. + */ + void ensure(FunctionRef compute_cache); + + /** + * Reset the cache. The next time #ensure is called, it will recompute that code. + */ + void tag_dirty() + { + cache_valid_.store(false); + } + + /** + * Return true if the cache currently does not exist or has been invalidated. + */ + bool is_dirty() const + { + return !this->is_cached(); + } + + /** + * Return true if the cache exists and is valid. + */ + bool is_cached() const + { + return cache_valid_.load(std::memory_order_relaxed); + } +}; + +} // namespace blender diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt index 2ac77f000e9..693a4d98675 100644 --- a/source/blender/blenlib/CMakeLists.txt +++ b/source/blender/blenlib/CMakeLists.txt @@ -54,6 +54,7 @@ set(SRC intern/bitmap_draw_2d.c intern/boxpack_2d.c intern/buffer.c + intern/cache_mutex.cc intern/compute_context.cc intern/convexhull_2d.c intern/cpp_type.cc @@ -178,6 +179,7 @@ set(SRC BLI_bounds.hh BLI_boxpack_2d.h BLI_buffer.h + BLI_cache_mutex.hh BLI_color.hh BLI_color_mix.hh BLI_compiler_attrs.h diff --git a/source/blender/blenlib/intern/cache_mutex.cc b/source/blender/blenlib/intern/cache_mutex.cc new file mode 100644 index 00000000000..db474b1ef87 --- /dev/null +++ b/source/blender/blenlib/intern/cache_mutex.cc @@ -0,0 +1,25 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ + +#include "BLI_cache_mutex.hh" +#include "BLI_task.hh" + +namespace blender { + +void CacheMutex::ensure(const FunctionRef compute_cache) +{ + if (cache_valid_.load(std::memory_order_acquire)) { + return; + } + std::scoped_lock lock{mutex_}; + /* Double checked lock. */ + if (cache_valid_.load(std::memory_order_relaxed)) { + return; + } + /* Use task isolation because a mutex is locked and the cache computation might use + * multi-threading. */ + threading::isolate_task(compute_cache); + + cache_valid_.store(true, std::memory_order_release); +} + +} // namespace blender -- cgit v1.2.3