diff options
author | Henning Baldersheim <balder@yahoo-inc.com> | 2023-01-20 16:13:19 +0100 |
---|---|---|
committer | GitHub <noreply@github.com> | 2023-01-20 16:13:19 +0100 |
commit | effe4b34bb8a8740d9bf7ede11d24e2eaa0f8c15 (patch) | |
tree | 027cfa2e161d772d627e1a45f291e08fd0668136 | |
parent | 8abd0fca095b98e6c76fac50ea544d39608c0e07 (diff) | |
parent | 6528ac5d970e52c361121d02f1d76226c3be1728 (diff) |
Merge pull request #25657 from vespa-engine/balder/insert_intenal-hot-cold
Split insert_internal into hot and cold part.
4 files changed, 31 insertions, 22 deletions
diff --git a/vespalib/src/vespa/vespalib/stllike/hash_map.hpp b/vespalib/src/vespa/vespalib/stllike/hash_map.hpp index 5a843d6774c..872847a4e45 100644 --- a/vespalib/src/vespa/vespalib/stllike/hash_map.hpp +++ b/vespalib/src/vespa/vespalib/stllike/hash_map.hpp @@ -78,7 +78,7 @@ hash_map<K, V, H, EQ, M>::getMemoryUsed() const template vespalib::hashtable<K, std::pair<K,V>, H, E, vespalib::Select1st<std::pair<K,V>>, M>::insert_result \ vespalib::hashtable<K, std::pair<K,V>, H, E, vespalib::Select1st<std::pair<K,V>>, M>::insert(std::pair<K,V> &&); \ template vespalib::hashtable<K, std::pair<K,V>, H, E, vespalib::Select1st<std::pair<K,V>>, M>::insert_result \ - vespalib::hashtable<K, std::pair<K,V>, H, E, vespalib::Select1st<std::pair<K,V>>, M>::insertInternal(std::pair<K,V> &&); + vespalib::hashtable<K, std::pair<K,V>, H, E, vespalib::Select1st<std::pair<K,V>>, M>::insert_internal(std::pair<K,V> &&); #define VESPALIB_HASH_MAP_INSTANTIATE_H_E(K, V, H, E) \ VESPALIB_HASH_MAP_INSTANTIATE_H_E_M(K, V, H, E, vespalib::hashtable_base::prime_modulator) \ diff --git a/vespalib/src/vespa/vespalib/stllike/hashtable.h b/vespalib/src/vespa/vespalib/stllike/hashtable.h index 553cda1e6c0..7b688f1e27d 100644 --- a/vespalib/src/vespa/vespalib/stllike/hashtable.h +++ b/vespalib/src/vespa/vespalib/stllike/hashtable.h @@ -301,7 +301,7 @@ public: const_iterator find(const Key & key) const; template <typename V> insert_result insert(V && node) { - return insertInternal(std::forward<V>(node)); + return insert_internal(std::forward<V>(node)); } // This will insert unconditionally, without checking presence, and might cause duplicates. // Use at you own risk. @@ -335,7 +335,7 @@ public: protected: template <typename V> - insert_result insertInternal(V && node) __attribute__((noinline)); + insert_result insert_internal(V && node) __attribute__((noinline)); /// These two methods are only for the ones that know what they are doing. /// valid input here are stuff returned from iterator.getInternalIndex. Value & getByInternalIndex(size_t index) { return _nodes[index].getValue(); } @@ -364,6 +364,8 @@ private: template <typename MoveHandler> VESPA_DLL_LOCAL void reclaim(MoveHandler & moveHandler, next_t node); VESPA_DLL_LOCAL void force_insert_cold(Value && value, next_t node) __attribute__((noinline)); + template <typename V> + VESPA_DLL_LOCAL insert_result insert_internal_cold(V && node, next_t) __attribute__((noinline)); }; } diff --git a/vespalib/src/vespa/vespalib/stllike/hashtable.hpp b/vespalib/src/vespa/vespalib/stllike/hashtable.hpp index 1b12bfba427..772d1bbae9b 100644 --- a/vespalib/src/vespa/vespalib/stllike/hashtable.hpp +++ b/vespalib/src/vespa/vespalib/stllike/hashtable.hpp @@ -155,31 +155,38 @@ hashtable<Key, Value, Hash, Equal, KeyExtract, Modulator>::clear() { template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > template< typename V > typename hashtable<Key, Value, Hash, Equal, KeyExtract, Modulator>::insert_result -hashtable<Key, Value, Hash, Equal, KeyExtract, Modulator>::insertInternal(V && node) +hashtable<Key, Value, Hash, Equal, KeyExtract, Modulator>::insert_internal(V && node) { const next_t h = hash(_keyExtractor(node)); - if ( ! _nodes[h].valid() ) { + if ( ! _nodes[h].valid() ) [[likely]] { _nodes[h] = std::forward<V>(node); _count++; return insert_result(iterator(this, h), true); - } else { - for (next_t c(h); c != Node::npos; c = _nodes[c].getNext()) { - if (_equal(_keyExtractor(_nodes[c].getValue()), _keyExtractor(node))) { - return insert_result(iterator(this, c), false); - } - } - if (_nodes.size() < _nodes.capacity()) { - const next_t p(_nodes[h].getNext()); - const next_t newIdx(_nodes.size()); - _nodes[h].setNext(newIdx); - _nodes.template emplace_back(std::forward<V>(node), p); - _count++; - return insert_result(iterator(this, newIdx), true); - } else { - resize(_nodes.capacity()*2); - return insertInternal(std::forward<V>(node)); + } + return insert_internal_cold(std::move(node), h); +} + +template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > +template< typename V > +typename hashtable<Key, Value, Hash, Equal, KeyExtract, Modulator>::insert_result +hashtable<Key, Value, Hash, Equal, KeyExtract, Modulator>::insert_internal_cold(V && node, next_t h) +{ + for (next_t c(h); c != Node::npos; c = _nodes[c].getNext()) { + if (_equal(_keyExtractor(_nodes[c].getValue()), _keyExtractor(node))) { + return insert_result(iterator(this, c), false); } } + if (_nodes.size() < _nodes.capacity()) { + const next_t p(_nodes[h].getNext()); + const next_t newIdx(_nodes.size()); + _nodes[h].setNext(newIdx); + _nodes.template emplace_back(std::forward<V>(node), p); + _count++; + return insert_result(iterator(this, newIdx), true); + } else { + resize(_nodes.capacity()*2); + return insert_internal(std::forward<V>(node)); + } } diff --git a/vespalib/src/vespa/vespalib/stllike/lrucache_map.hpp b/vespalib/src/vespa/vespalib/stllike/lrucache_map.hpp index 73e9956ffdf..ccaae52469e 100644 --- a/vespalib/src/vespa/vespalib/stllike/lrucache_map.hpp +++ b/vespalib/src/vespa/vespalib/stllike/lrucache_map.hpp @@ -237,7 +237,7 @@ lrucache_map<P>::ref(const internal_iterator & it) { template< typename P > typename lrucache_map<P>::insert_result lrucache_map<P>::insert(value_type && value) { - insert_result res = HashTable::insertInternal(std::forward<value_type>(value)); + insert_result res = HashTable::insert_internal(std::forward<value_type>(value)); uint32_t next(_head); if ( ! res.second) { ref(res.first); |