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 <algorithm> 21 #include <vector> 22 23 // A vector-based set::set-like container. 24 // It's more cache friendly than std::*set and performs for cases where: 25 // 1. A high number of dupes is expected (e.g. pid tracking in ftrace). 26 // 2. The working set is small (hundreds of elements). 27 28 // Performance characteristics (for uniformly random insertion order): 29 // - For smaller insertions (up to ~500), it outperforms both std::set<int> and 30 // std::unordered_set<int> by ~3x. 31 // - Up until 4k insertions, it is always faster than std::set<int>. 32 // - unordered_set<int> is faster with more than 2k insertions. 33 // - unordered_set, however, it's less memory efficient and has more caveats 34 // (see chromium's base/containers/README.md). 35 // 36 // See flat_set_benchmark.cc and the charts in go/perfetto-int-set-benchmark. 37 38 namespace perfetto { 39 namespace base { 40 41 template <typename T> 42 class FlatSet { 43 public: 44 using value_type = T; 45 using const_pointer = const T*; 46 using iterator = typename std::vector<T>::iterator; 47 using const_iterator = typename std::vector<T>::const_iterator; 48 49 FlatSet() = default; 50 51 // Mainly for tests. Deliberately not marked as "expicit". FlatSet(std::initializer_list<T> initial)52 FlatSet(std::initializer_list<T> initial) : entries_(initial) { 53 std::sort(entries_.begin(), entries_.end()); 54 entries_.erase(std::unique(entries_.begin(), entries_.end()), 55 entries_.end()); 56 } 57 find(T value)58 const_iterator find(T value) const { 59 auto entries_end = entries_.end(); 60 auto it = std::lower_bound(entries_.begin(), entries_end, value); 61 return (it != entries_end && *it == value) ? it : entries_end; 62 } 63 count(T value)64 size_t count(T value) const { return find(value) == entries_.end() ? 0 : 1; } 65 insert(T value)66 std::pair<iterator, bool> insert(T value) { 67 auto entries_end = entries_.end(); 68 auto it = std::lower_bound(entries_.begin(), entries_end, value); 69 if (it != entries_end && *it == value) 70 return std::make_pair(it, false); 71 // If the value is not found |it| is either end() or the next item strictly 72 // greater than |value|. In both cases we want to insert just before that. 73 it = entries_.insert(it, std::move(value)); 74 return std::make_pair(it, true); 75 } 76 erase(T value)77 size_t erase(T value) { 78 auto it = find(value); 79 if (it == entries_.end()) 80 return 0; 81 entries_.erase(it); 82 return 1; 83 } 84 clear()85 void clear() { entries_.clear(); } 86 empty()87 bool empty() const { return entries_.empty(); } reserve(size_t n)88 void reserve(size_t n) { entries_.reserve(n); } size()89 size_t size() const { return entries_.size(); } begin()90 const_iterator begin() const { return entries_.begin(); } end()91 const_iterator end() const { return entries_.end(); } 92 93 private: 94 std::vector<T> entries_; 95 }; 96 97 } // namespace base 98 } // namespace perfetto 99 100 #endif // INCLUDE_PERFETTO_BASE_FLAT_SET_H_ 101