1 /* 2 * Copyright (C) 2019 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef INCLUDE_PERFETTO_BASE_FLAT_SET_H_ 18 #define INCLUDE_PERFETTO_BASE_FLAT_SET_H_ 19 20 #include <stddef.h> 21 22 #include <algorithm> 23 #include <utility> 24 #include <vector> 25 26 // A vector-based set::set-like container. 27 // It's more cache friendly than std::*set and performs for cases where: 28 // 1. A high number of dupes is expected (e.g. pid tracking in ftrace). 29 // 2. The working set is small (hundreds of elements). 30 31 // Performance characteristics (for uniformly random insertion order): 32 // - For smaller insertions (up to ~500), it outperforms both std::set<int> and 33 // std::unordered_set<int> by ~3x. 34 // - Up until 4k insertions, it is always faster than std::set<int>. 35 // - unordered_set<int> is faster with more than 2k insertions. 36 // - unordered_set, however, it's less memory efficient and has more caveats 37 // (see chromium's base/containers/README.md). 38 // 39 // See flat_set_benchmark.cc and the charts in go/perfetto-int-set-benchmark. 40 41 namespace perfetto { 42 namespace base { 43 44 template <typename T> 45 class FlatSet { 46 public: 47 using value_type = T; 48 using const_pointer = const T*; 49 using iterator = typename std::vector<T>::iterator; 50 using const_iterator = typename std::vector<T>::const_iterator; 51 52 FlatSet() = default; 53 54 // Mainly for tests. Deliberately not marked as "explicit". FlatSet(std::initializer_list<T> initial)55 FlatSet(std::initializer_list<T> initial) : entries_(initial) { 56 std::sort(entries_.begin(), entries_.end()); 57 entries_.erase(std::unique(entries_.begin(), entries_.end()), 58 entries_.end()); 59 } 60 find(T value)61 const_iterator find(T value) const { 62 auto entries_end = entries_.end(); 63 auto it = std::lower_bound(entries_.begin(), entries_end, value); 64 return (it != entries_end && *it == value) ? it : entries_end; 65 } 66 count(T value)67 size_t count(T value) const { return find(value) == entries_.end() ? 0 : 1; } 68 insert(T value)69 std::pair<iterator, bool> insert(T value) { 70 auto entries_end = entries_.end(); 71 auto it = std::lower_bound(entries_.begin(), entries_end, value); 72 if (it != entries_end && *it == value) 73 return std::make_pair(it, false); 74 // If the value is not found |it| is either end() or the next item strictly 75 // greater than |value|. In both cases we want to insert just before that. 76 it = entries_.insert(it, std::move(value)); 77 return std::make_pair(it, true); 78 } 79 erase(T value)80 size_t erase(T value) { 81 auto it = find(value); 82 if (it == entries_.end()) 83 return 0; 84 entries_.erase(it); 85 return 1; 86 } 87 clear()88 void clear() { entries_.clear(); } 89 empty()90 bool empty() const { return entries_.empty(); } reserve(size_t n)91 void reserve(size_t n) { entries_.reserve(n); } size()92 size_t size() const { return entries_.size(); } begin()93 const_iterator begin() const { return entries_.begin(); } end()94 const_iterator end() const { return entries_.end(); } 95 96 private: 97 std::vector<T> entries_; 98 }; 99 100 } // namespace base 101 } // namespace perfetto 102 103 #endif // INCLUDE_PERFETTO_BASE_FLAT_SET_H_ 104