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);