nicovank created this revision.
Herald added subscribers: carlosgalvezp, xazax.hun, mgorny.
Herald added a project: All.
nicovank edited the summary of this revision.
nicovank edited the summary of this revision.
nicovank updated this revision to Diff 452886.
nicovank updated this revision to Diff 452894.
nicovank added a comment.
nicovank updated this revision to Diff 452896.
Eugene.Zelenko added reviewers: alex, aaron.ballman, njames93,
LegalizeAdulthood.
Eugene.Zelenko added a project: clang-tools-extra.
nicovank updated this revision to Diff 453026.
nicovank marked an inline comment as done.
nicovank published this revision for review.
nicovank added subscribers: marksantaniello, ivanmurashko, 0x1eaf.
nicovank marked an inline comment as done.
Herald added a subscriber: cfe-commits.
Rename second test file
nicovank added a comment.
Add isLanguageVersionSupported.
================
Comment at:
clang-tools-extra/clang-tidy/performance/ExpensiveFlatContainerOperationCheck.h:31
+ void storeOptions(ClangTidyOptions::OptionMap &Opts) override;
+
+private:
----------------
Please add `isLanguageVersionSupported`.
================
Comment at:
clang-tools-extra/docs/clang-tidy/checks/performance/expensive-flat-container-operation.rst:6
+
+This check operates on vector-based containers such as
+``boost::container::flat_(map|set)`` and ``folly::sorted_vector_(map|set)``.
----------------
Please synchronize first statement with Release Notes.
This check has been enabled internally at Facebook for a few months now (with
`OnlyWarnInLoops` disabled), where `folly::sorted_vector_map` is pretty widely
used.
I saw `std::flat_(map|set)` and `std::flat_multi(map|set)` will appear in
C++23, at which point this check can be updated to include these.
`folly::heap_vector_(map|set)` is another example of such containers, though
still relatively new so not included here yet.
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D131939
Files:
clang-tools-extra/clang-tidy/performance/CMakeLists.txt
clang-tools-extra/clang-tidy/performance/ExpensiveFlatContainerOperationCheck.cpp
clang-tools-extra/clang-tidy/performance/ExpensiveFlatContainerOperationCheck.h
clang-tools-extra/clang-tidy/performance/PerformanceTidyModule.cpp
clang-tools-extra/docs/ReleaseNotes.rst
clang-tools-extra/docs/clang-tidy/checks/list.rst
clang-tools-extra/docs/clang-tidy/checks/performance/expensive-flat-container-operation.rst
clang-tools-extra/test/clang-tidy/checkers/performance/expensive-flat-container-operation-only-warn-in-loops.cpp
clang-tools-extra/test/clang-tidy/checkers/performance/expensive-flat-container-operation.cpp
Index: clang-tools-extra/test/clang-tidy/checkers/performance/expensive-flat-container-operation.cpp
===================================================================
--- /dev/null
+++ clang-tools-extra/test/clang-tidy/checkers/performance/expensive-flat-container-operation.cpp
@@ -0,0 +1,383 @@
+// RUN: %check_clang_tidy %s performance-expensive-flat-container-operation %t -- \
+// RUN: -config="{CheckOptions: \
+// RUN: [{key: performance-expensive-flat-container-operation.OnlyWarnInLoops, \
+// RUN: value: false}] \
+// RUN: }"
+
+namespace std {
+template <class T1, class T2>
+struct pair {
+ pair(T1, T2);
+};
+
+template<class T>
+struct initializer_list {
+ initializer_list();
+};
+
+template<class T> struct remove_reference { typedef T type; };
+template<class T> struct remove_reference<T&> { typedef T type; };
+template<class T> struct remove_reference<T&&> { typedef T type; };
+
+template<class T>
+typename std::remove_reference<T>::type&& move(T&&) noexcept;
+} // namespace std
+
+// Copied from boost/container/flat_map.hpp and boost/container/flat_set.hpp and simplified.
+namespace boost {
+namespace container {
+struct ordered_unique_range_t {};
+
+template <typename Key, typename T>
+struct flat_map {
+ typedef Key key_type;
+ typedef T mapped_type;
+ typedef std::pair<Key, T> value_type;
+
+ typedef int size_type;
+ typedef struct {} iterator;
+ typedef struct {} const_iterator;
+
+ const_iterator begin() const noexcept;
+ const_iterator end() const noexcept;
+
+ template <class... Args> std::pair<iterator, bool> emplace(Args&&...);
+
+ template <class... Args> iterator emplace_hint(const_iterator, Args&&...);
+
+ template <class... Args> std::pair<iterator, bool> try_emplace(const key_type&, Args&&...);
+ template <class... Args> iterator try_emplace(const_iterator, const key_type&, Args&&...);
+ template <class... Args> std::pair<iterator, bool> try_emplace(key_type&&, Args&&...);
+ template <class... Args> iterator try_emplace(const_iterator, key_type&&, Args&&...);
+
+ std::pair<iterator, bool> insert(const value_type&);
+ std::pair<iterator, bool> insert(value_type&&);
+ iterator insert(const_iterator, const value_type&);
+ iterator insert(const_iterator, value_type&&);
+ template <typename InputIterator> void insert(InputIterator, InputIterator);
+ template <typename InputIterator> void insert(ordered_unique_range_t, InputIterator, InputIterator);
+ void insert(std::initializer_list<value_type>);
+ void insert(ordered_unique_range_t, std::initializer_list<value_type>);
+
+ iterator erase(const_iterator);
+ size_type erase(const key_type&);
+ iterator erase(const_iterator, const_iterator);
+};
+
+template <typename Key>
+struct flat_set {
+ typedef Key key_type;
+ typedef Key value_type;
+
+ typedef int size_type;
+ typedef struct {} iterator;
+ typedef struct {} const_iterator;
+
+ const_iterator begin() const noexcept;
+ const_iterator end() const noexcept;
+
+ template <class... Args> std::pair<iterator, bool> emplace(Args&&...);
+
+ template <class... Args> iterator emplace_hint(const_iterator, Args&&...);
+
+ std::pair<iterator, bool> insert(const value_type&);
+ std::pair<iterator, bool> insert(value_type&&);
+ iterator insert(const_iterator, const value_type&);
+ iterator insert(const_iterator, value_type&&);
+ template <typename InputIterator> void insert(InputIterator, InputIterator);
+ template <typename InputIterator> void insert(ordered_unique_range_t, InputIterator, InputIterator);
+ void insert(std::initializer_list<value_type>);
+ void insert(ordered_unique_range_t, std::initializer_list<value_type>);
+
+ iterator erase(const_iterator);
+ size_type erase(const key_type&);
+ iterator erase(const_iterator, const_iterator);
+};
+} // namespace container
+} // namespace boost
+
+// Copied from folly/sorted_vector_types.h and simplified.
+namespace folly {
+template <class Key, class Value> struct sorted_vector_map {
+ typedef Key key_type;
+ typedef Value mapped_type;
+ typedef std::pair<Key, Value> value_type;
+
+ typedef int size_type;
+ typedef struct {} iterator;
+ typedef struct {} const_iterator;
+
+ const_iterator begin() const;
+ const_iterator end() const;
+
+ std::pair<iterator, bool> insert(const value_type&);
+ std::pair<iterator, bool> insert(value_type&&);
+ iterator insert(const_iterator, const value_type&);
+ iterator insert(const_iterator, value_type&&);
+ template <class InputIterator> void insert(InputIterator, InputIterator);
+ void insert(std::initializer_list<value_type>);
+
+ template <typename... Args> std::pair<iterator, bool> emplace(Args&&...);
+ std::pair<iterator, bool> emplace(const value_type&);
+ std::pair<iterator, bool> emplace(value_type&&);
+
+ template <typename... Args> iterator emplace_hint(const_iterator, Args&&...);
+ iterator emplace_hint(const_iterator, const value_type&);
+ iterator emplace_hint(const_iterator, value_type&&);
+
+ size_type erase(const key_type&);
+ iterator erase(const_iterator);
+ iterator erase(const_iterator, const_iterator);
+};
+
+template <class T> struct sorted_vector_set {
+ typedef T value_type;
+ typedef T key_type;
+
+ typedef int size_type;
+ typedef struct {} iterator;
+ typedef struct {} const_iterator;
+
+ const_iterator begin() const;
+ const_iterator end() const;
+
+ std::pair<iterator, bool> insert(const value_type&);
+ std::pair<iterator, bool> insert(value_type&&);
+ iterator insert(const_iterator, const value_type&);
+ iterator insert(const_iterator, value_type&&);
+ template <class InputIterator> void insert(InputIterator, InputIterator);
+ void insert(std::initializer_list<value_type>);
+
+ template <typename... Args> std::pair<iterator, bool> emplace(Args&&...);
+ std::pair<iterator, bool> emplace(const value_type&);
+ std::pair<iterator, bool> emplace(value_type&&);
+
+ template <typename... Args> iterator emplace_hint(const_iterator, Args&&...);
+ iterator emplace_hint(const_iterator, const value_type&);
+ iterator emplace_hint(const_iterator, value_type&&);
+
+ size_type erase(const key_type&);
+ iterator erase(const_iterator);
+ iterator erase(const_iterator, const_iterator);
+};
+} // namespace folly
+
+struct Foo {
+ Foo() {}
+ Foo(const Foo&) = default;
+ Foo(Foo&&) = default;
+};
+
+void TestBoostFlapMap() {
+ boost::container::flat_map<Foo, int> bfm;
+ std::pair<Foo, int> foo(Foo(), 13);
+ boost::container::ordered_unique_range_t bar;
+
+ bfm.emplace(Foo(), 13);
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ bfm.emplace_hint(bfm.begin(), Foo(), 13);
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ bfm.try_emplace(Foo(), 13);
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ bfm.try_emplace(bfm.begin(), Foo(), 13);
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ bfm.try_emplace(Foo(), 13);
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ bfm.try_emplace(bfm.begin(), Foo(), 13);
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ bfm.insert(foo);
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ bfm.insert(std::move(foo));
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ bfm.insert(bfm.begin(), foo);
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ bfm.insert(bfm.begin(), std::move(foo));
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ bfm.insert(bfm.begin(), bfm.end());
+ bfm.insert(bar, bfm.begin(), bfm.end());
+ bfm.insert(std::initializer_list<std::pair<Foo, int>>());
+ bfm.insert(bar, std::initializer_list<std::pair<Foo, int>>());
+
+ bfm.erase(Foo());
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ bfm.erase(bfm.begin());
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ bfm.erase(bfm.begin(), bfm.end());
+}
+
+void TestBoostFlatSet() {
+ boost::container::flat_set<Foo> bfs;
+ Foo foo;
+ boost::container::ordered_unique_range_t bar;
+
+ bfs.emplace();
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ bfs.emplace_hint(bfs.begin());
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ bfs.insert(foo);
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ bfs.insert(std::move(foo));
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ bfs.insert(bfs.begin(), foo);
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ bfs.insert(bfs.begin(), std::move(foo));
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ bfs.insert(bfs.begin(), bfs.end());
+ bfs.insert(bar, bfs.begin(), bfs.end());
+ bfs.insert(std::initializer_list<Foo>());
+ bfs.insert(bar, std::initializer_list<Foo>());
+
+ bfs.erase(foo);
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ bfs.erase(bfs.begin());
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ bfs.erase(bfs.begin(), bfs.end());
+}
+
+void TestFollySortedVectorMap() {
+ folly::sorted_vector_map<Foo, int> fsvm;
+ std::pair<Foo, int> foo(Foo(), 13);
+
+ fsvm.insert(foo);
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ fsvm.insert(std::move(foo));
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ fsvm.insert(fsvm.begin(), foo);
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ fsvm.insert(fsvm.begin(), std::move(foo));
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ fsvm.insert(fsvm.begin(), fsvm.end());
+ fsvm.insert(std::initializer_list<std::pair<Foo, int>>());
+
+ fsvm.emplace(Foo(), 13);
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ fsvm.emplace(foo);
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ fsvm.emplace(std::move(foo));
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ fsvm.emplace_hint(fsvm.begin(), Foo(), 13);
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ fsvm.emplace_hint(fsvm.begin(), foo);
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ fsvm.emplace_hint(fsvm.begin(), std::move(foo));
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ fsvm.erase(Foo());
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ fsvm.erase(fsvm.begin());
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ fsvm.erase(fsvm.begin(), fsvm.end());
+}
+
+void TestFollySortedVectorSet() {
+ folly::sorted_vector_set<Foo> fsvs;
+ Foo foo;
+
+ fsvs.insert(foo);
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ fsvs.insert(std::move(foo));
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ fsvs.insert(fsvs.begin(), foo);
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ fsvs.insert(fsvs.begin(), std::move(foo));
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ fsvs.insert(fsvs.begin(), fsvs.end());
+ fsvs.insert(std::initializer_list<Foo>());
+
+ fsvs.emplace();
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ fsvs.emplace(foo);
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ fsvs.emplace(std::move(foo));
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ fsvs.emplace_hint(fsvs.begin());
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ fsvs.emplace_hint(fsvs.begin(), foo);
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ fsvs.emplace_hint(fsvs.begin(), std::move(foo));
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ fsvs.erase(foo);
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ fsvs.erase(fsvs.begin());
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ fsvs.erase(fsvs.begin(), fsvs.end());
+}
+
+struct A {};
+struct B : A {};
+
+static int key = 13;
+static int value = 31;
+
+void TestPossibleFalseNegatives() {
+ folly::sorted_vector_set<long> fsvs;
+ fsvs.insert(5);
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ folly::sorted_vector_set<A> fsvs2;
+ fsvs2.insert(B());
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ folly::sorted_vector_set<std::pair<int, int>> fsvs3;
+ fsvs3.insert(std::pair<int, int>(13, 31));
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ using CustomSortedVectorMapType = folly::sorted_vector_map<int, int>;
+ CustomSortedVectorMapType map;
+ map.insert(std::pair<int, int>(5, 5));
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ folly::sorted_vector_map<int, int>* fsvmp = new folly::sorted_vector_map<int, int>;
+ fsvmp->emplace(std::move(key), value);
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ (&(*fsvmp))->emplace(std::move(key), value);
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ auto& fsvmr = *fsvmp;
+ fsvmr.emplace(key, value);
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+}
Index: clang-tools-extra/test/clang-tidy/checkers/performance/expensive-flat-container-operation-only-warn-in-loops.cpp
===================================================================
--- /dev/null
+++ clang-tools-extra/test/clang-tidy/checkers/performance/expensive-flat-container-operation-only-warn-in-loops.cpp
@@ -0,0 +1,106 @@
+// RUN: %check_clang_tidy %s performance-expensive-flat-container-operation %t -- \
+// RUN: -config="{CheckOptions: \
+// RUN: [{key: performance-expensive-flat-container-operation.OnlyWarnInLoops, \
+// RUN: value: true}] \
+// RUN: }"
+
+namespace std {
+template <class T1, class T2>
+struct pair {
+ pair(T1, T2);
+};
+
+template<class T>
+struct initializer_list {
+ initializer_list();
+};
+} // namespace std
+
+// Copied from boost/container/flat_map.hpp and simplified.
+namespace boost {
+namespace container {
+struct ordered_unique_range_t {};
+
+template <typename Key>
+struct flat_set {
+ typedef Key key_type;
+ typedef Key value_type;
+
+ typedef int size_type;
+ typedef struct {} iterator;
+ typedef struct {} const_iterator;
+
+ const_iterator begin() const noexcept;
+ const_iterator end() const noexcept;
+
+ template <class... Args> std::pair<iterator, bool> emplace(Args&&...);
+
+ template <class... Args> iterator emplace_hint(const_iterator, Args&&...);
+
+ std::pair<iterator, bool> insert(const value_type&);
+ std::pair<iterator, bool> insert(value_type&&);
+ iterator insert(const_iterator, const value_type&);
+ iterator insert(const_iterator, value_type&&);
+ template <typename InputIterator> void insert(InputIterator, InputIterator);
+ template <typename InputIterator> void insert(ordered_unique_range_t, InputIterator, InputIterator);
+ void insert(std::initializer_list<value_type>);
+ void insert(ordered_unique_range_t, std::initializer_list<value_type>);
+
+ iterator erase(const_iterator);
+ size_type erase(const key_type&);
+ iterator erase(const_iterator, const_iterator);
+};
+} // namespace container
+} // namespace boost
+
+static boost::container::flat_set<int> gbfs;
+boost::container::flat_set<int>& getGlobalSetRef() {
+ return gbfs;
+};
+
+void TestCheckWithLoops() {
+ boost::container::flat_set<int> bfs;
+ bfs.insert(13);
+ bfs.erase(13);
+
+ for (int i = 0; i < 10; ++i) {
+ bfs.insert(i);
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ if (i % 2 == 0) {
+ bfs.erase(i);
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+ }
+ }
+
+ while (true) {
+ bfs.erase(bfs.begin());
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+ }
+
+ do {
+ (&bfs)->emplace(13);
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+ } while (false);
+
+ for (int i = 0; i < 10; ++i) {
+ boost::container::flat_set<long> bfs;
+ if (i % 2 == 0) {
+ bfs.insert(i);
+
+ gbfs.insert(i);
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ getGlobalSetRef().insert(i);
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+
+ (gbfs).insert(i);
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+ }
+
+ for (int j = 0; j < i; ++j) {
+ bfs.insert(2 * j);
+ // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers.
+ }
+ }
+}
Index: clang-tools-extra/docs/clang-tidy/checks/performance/expensive-flat-container-operation.rst
===================================================================
--- /dev/null
+++ clang-tools-extra/docs/clang-tidy/checks/performance/expensive-flat-container-operation.rst
@@ -0,0 +1,68 @@
+.. title:: clang-tidy - performance-expensive-flat-container-operation
+
+performance-expensive-flat-container-operation
+==============================================
+
+Warns when calling an O(N) operation on a flat container.
+
+This check operates on vector-based flat containers such as
+``boost::container::flat_(map|set)`` and ``folly::sorted_vector_(map|set)``.
+While these containers' behavior is identical to usual maps/sets, the insert and
+erase operations are O(N). This check flags such operations, which are a common
+bad pattern, notably in loops.
+
+Below is an example of a typical bad pattern: inserting some values one by one
+into a flat container. This is O(N^2), as the container will need to shift
+elements right after each insertion.
+
+.. code-block:: c++
+
+ std::random_device generator;
+ std::uniform_int_distribution<int> distribution;
+
+ boost::container::flat_set<int> set;
+ for (auto i = 0; i < N; ++i) {
+ set.insert(distribution(generator));
+ }
+
+The code above can be improved using a temporary vector, later inserting all
+values at once into the ``flat_set``.
+
+.. code-block:: c++
+
+ std::vector<int> temporary;
+ for (auto i = 0; i < N; ++i) {
+ temporary.push_back(distribution(generator));
+ }
+ boost::container::flat_set<int> set(temporary.begin(), temporary.end());
+
+For expensive-to-copy objects, ``std::move_iterator`` should be used. It is also
+possible to move the temporary vector and use it directly as the underlying
+container when using folly's ``sorted_vector_(map|set)``.
+
+Other solutions exist, including notably using a different map such as
+``std::unordered_map`` when order is not important, bulk insertion with
+iterators, ``boost::transform_iterator`` and ``erase_if``.
+
+This check is not capable of flagging insertions into a map via ``operator[]``,
+as it is not possible at compile-time to know whether this will trigger an
+insertion. These cases will have to be detected via dynamic profiling.
+
+Options
+-------
+
+.. option:: OnlyWarnInLoops
+
+ When enabled, the check will only warn when the single element operation is
+ directly enclosed by a loop, hence directly actionable. At the very least,
+ these cases can be improved using some temporary container.
+
+ Default is `true`.
+
+.. option:: FlatContainers
+
+ A semicolon-separated list of flat containers, with ``insert``, ``emplace``
+ and/or ``erase`` operations.
+
+ Default includes ``boost::container::flat_(map|set)`` and
+ ``folly::sorted_vector_(map|set)``.
Index: clang-tools-extra/docs/clang-tidy/checks/list.rst
===================================================================
--- clang-tools-extra/docs/clang-tidy/checks/list.rst
+++ clang-tools-extra/docs/clang-tidy/checks/list.rst
@@ -302,6 +302,7 @@
`objc-super-self <objc/super-self.html>`_, "Yes"
`openmp-exception-escape <openmp/exception-escape.html>`_,
`openmp-use-default-none <openmp/use-default-none.html>`_,
+ `performance-expensive-flat-container-operation <performance/expensive-flat-container-operation.html>`_,
`performance-faster-string-find <performance/faster-string-find.html>`_, "Yes"
`performance-for-range-copy <performance/for-range-copy.html>`_, "Yes"
`performance-implicit-conversion-in-loop <performance/implicit-conversion-in-loop.html>`_,
Index: clang-tools-extra/docs/ReleaseNotes.rst
===================================================================
--- clang-tools-extra/docs/ReleaseNotes.rst
+++ clang-tools-extra/docs/ReleaseNotes.rst
@@ -104,6 +104,11 @@
Warns when a struct or class uses const or reference (lvalue or rvalue) data members.
+- New :doc:`performance-expensive-flat-container-operation
+ <clang-tidy/checks/performance/expensive-flat-container-operation>` check.
+
+ Warns when calling an O(N) operation on a flat container.
+
New check aliases
^^^^^^^^^^^^^^^^^
Index: clang-tools-extra/clang-tidy/performance/PerformanceTidyModule.cpp
===================================================================
--- clang-tools-extra/clang-tidy/performance/PerformanceTidyModule.cpp
+++ clang-tools-extra/clang-tidy/performance/PerformanceTidyModule.cpp
@@ -9,6 +9,7 @@
#include "../ClangTidy.h"
#include "../ClangTidyModule.h"
#include "../ClangTidyModuleRegistry.h"
+#include "ExpensiveFlatContainerOperationCheck.h"
#include "FasterStringFindCheck.h"
#include "ForRangeCopyCheck.h"
#include "ImplicitConversionInLoopCheck.h"
@@ -32,6 +33,8 @@
class PerformanceModule : public ClangTidyModule {
public:
void addCheckFactories(ClangTidyCheckFactories &CheckFactories) override {
+ CheckFactories.registerCheck<ExpensiveFlatContainerOperationCheck>(
+ "performance-expensive-flat-container-operation");
CheckFactories.registerCheck<FasterStringFindCheck>(
"performance-faster-string-find");
CheckFactories.registerCheck<ForRangeCopyCheck>(
Index: clang-tools-extra/clang-tidy/performance/ExpensiveFlatContainerOperationCheck.h
===================================================================
--- /dev/null
+++ clang-tools-extra/clang-tidy/performance/ExpensiveFlatContainerOperationCheck.h
@@ -0,0 +1,44 @@
+//===--- ExpensiveFlatContainerOperationCheck.h - clang-tidy ----*- C++ -*-===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_PERFORMANCE_EXPENSIVEFLATCONTAINEROPERATIONCHECK_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_PERFORMANCE_EXPENSIVEFLATCONTAINEROPERATIONCHECK_H
+
+#include "../ClangTidyCheck.h"
+
+#include <vector>
+
+namespace clang {
+namespace tidy {
+namespace performance {
+
+/// Warns when calling an O(N) operation on a flat container.
+///
+/// For the user-facing documentation see:
+/// http://clang.llvm.org/extra/clang-tidy/checks/performance/expensive-flat-container-operation.html
+class ExpensiveFlatContainerOperationCheck : public ClangTidyCheck {
+public:
+ ExpensiveFlatContainerOperationCheck(StringRef Name,
+ ClangTidyContext *Context);
+ void registerMatchers(ast_matchers::MatchFinder *Finder) override;
+ void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
+ void storeOptions(ClangTidyOptions::OptionMap &Opts) override;
+ bool isLanguageVersionSupported(const LangOptions &LangOpts) const override {
+ return LangOpts.CPlusPlus;
+ }
+
+private:
+ const bool OnlyWarnInLoops;
+ const std::vector<StringRef> FlatContainers;
+};
+
+} // namespace performance
+} // namespace tidy
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_PERFORMANCE_EXPENSIVEFLATCONTAINEROPERATIONCHECK_H
Index: clang-tools-extra/clang-tidy/performance/ExpensiveFlatContainerOperationCheck.cpp
===================================================================
--- /dev/null
+++ clang-tools-extra/clang-tidy/performance/ExpensiveFlatContainerOperationCheck.cpp
@@ -0,0 +1,100 @@
+//===--- ExpensiveFlatContainerOperationCheck.cpp - clang-tidy ------------===//
+//
+// 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 "ExpensiveFlatContainerOperationCheck.h"
+
+#include "../utils/OptionsUtils.h"
+
+using namespace clang::ast_matchers;
+
+namespace {
+const auto DefaultFlatContainers =
+ "::folly::sorted_vector_set; ::folly::sorted_vector_map;"
+ "::boost::container::flat_set; ::boost::container::flat_map;";
+} // namespace
+
+namespace clang {
+namespace tidy {
+namespace performance {
+
+ExpensiveFlatContainerOperationCheck::ExpensiveFlatContainerOperationCheck(
+ StringRef Name, ClangTidyContext *Context)
+ : ClangTidyCheck(Name, Context),
+ OnlyWarnInLoops(Options.get("OnlyWarnInLoops", true)),
+ FlatContainers(utils::options::parseStringList(
+ Options.get("FlatContainers", DefaultFlatContainers))) {}
+
+void ExpensiveFlatContainerOperationCheck::registerMatchers(
+ MatchFinder *Finder) {
+ const auto SoughtContainerDecl = cxxRecordDecl(
+ hasAnyName(FlatContainers),
+ has(typedefNameDecl(
+ hasName("value_type"),
+ hasType(hasUnqualifiedDesugaredType(type().bind("value_type"))))));
+
+ const auto HasSoughtArrowMemberExpr = has(memberExpr(
+ isArrow(), hasObjectExpression(
+ hasType(pointerType(pointee(hasUnqualifiedDesugaredType(
+ recordType(hasDeclaration(SoughtContainerDecl)))))))));
+
+ // We don't need to make sure the MemberExpr is not an arrow call, if it was
+ // the code wouldn't compile anyway.
+ const auto HasSoughtPeriodMemberExpr =
+ has(memberExpr(hasObjectExpression(hasType(hasUnqualifiedDesugaredType(
+ recordType(hasDeclaration(SoughtContainerDecl)))))));
+
+ const auto HasEmplaceCall = callee(cxxMethodDecl(matchesName("emplace")));
+
+ const auto HasInsertCallWithValueTypeArgument =
+ cxxMemberCallExpr(callee(cxxMethodDecl(matchesName("insert"))),
+ hasAnyArgument(expr(hasType(hasUnqualifiedDesugaredType(
+ type(equalsBoundNode("value_type")))))));
+
+ const auto HasEraseCallWithOneArgument = cxxMemberCallExpr(
+ callee(cxxMethodDecl(matchesName("erase"))), argumentCountIs(1));
+
+ const auto SoughtFlatContainerOperation =
+ cxxMemberCallExpr(
+ anyOf(HasSoughtArrowMemberExpr, HasSoughtPeriodMemberExpr),
+ anyOf(HasEmplaceCall, HasInsertCallWithValueTypeArgument,
+ HasEraseCallWithOneArgument))
+ .bind("call");
+
+ if (OnlyWarnInLoops) {
+ const auto IsWithinLoop = cxxMemberCallExpr(
+ hasAncestor(stmt(anyOf(forStmt(), whileStmt(), doStmt())).bind("loop")),
+ // An easy false positive case: the variable is declared in the loop.
+ unless(onImplicitObjectArgument(declRefExpr(hasDeclaration(
+ decl(hasAncestor(stmt(equalsBoundNode("loop")))))))));
+
+ Finder->addMatcher(
+ cxxMemberCallExpr(SoughtFlatContainerOperation, IsWithinLoop), this);
+ } else {
+ Finder->addMatcher(SoughtFlatContainerOperation, this);
+ }
+}
+
+void ExpensiveFlatContainerOperationCheck::check(
+ const MatchFinder::MatchResult &Result) {
+ const auto *Call = Result.Nodes.getNodeAs<CXXMemberCallExpr>("call");
+
+ diag(Call->getExprLoc(),
+ "Single element operations are expensive for flat containers. "
+ "Consider using available bulk operations instead.");
+}
+
+void ExpensiveFlatContainerOperationCheck::storeOptions(
+ ClangTidyOptions::OptionMap &Opts) {
+ Options.store(Opts, "OnlyWarnInLoops", OnlyWarnInLoops);
+ Options.store(Opts, "FlatContainers",
+ utils::options::serializeStringList(FlatContainers));
+}
+
+} // namespace performance
+} // namespace tidy
+} // namespace clang
Index: clang-tools-extra/clang-tidy/performance/CMakeLists.txt
===================================================================
--- clang-tools-extra/clang-tidy/performance/CMakeLists.txt
+++ clang-tools-extra/clang-tidy/performance/CMakeLists.txt
@@ -4,6 +4,7 @@
)
add_clang_library(clangTidyPerformanceModule
+ ExpensiveFlatContainerOperationCheck.cpp
FasterStringFindCheck.cpp
ForRangeCopyCheck.cpp
ImplicitConversionInLoopCheck.cpp
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
