diff options
author | Henning Baldersheim <balder@yahoo-inc.com> | 2017-12-29 13:01:37 +0100 |
---|---|---|
committer | GitHub <noreply@github.com> | 2017-12-29 13:01:37 +0100 |
commit | 91d0b8518a1b9bbff2675d4ff1541e7d35583f9b (patch) | |
tree | ca59a2a9405b75a6cde056887f241a8b9347c8e6 | |
parent | ded136ba6f1ac0cbe5a91600a24b70f3ff4e9cc6 (diff) | |
parent | f62d3547d3b0d1f13dcd1e805f3c965d6678b997 (diff) |
Merge pull request #4526 from vespa-engine/balder/use-faster-iteration
Balder/use faster iteration
12 files changed, 71 insertions, 76 deletions
diff --git a/persistence/src/vespa/persistence/conformancetest/conformancetest.cpp b/persistence/src/vespa/persistence/conformancetest/conformancetest.cpp index 885d3e9aad7..7f4ea9dcc2e 100644 --- a/persistence/src/vespa/persistence/conformancetest/conformancetest.cpp +++ b/persistence/src/vespa/persistence/conformancetest/conformancetest.cpp @@ -8,6 +8,7 @@ #include <vespa/document/update/documentupdate.h> #include <vespa/document/update/assignvalueupdate.h> #include <vespa/document/test/make_bucket_space.h> +#include <vespa/metrics/loadmetric.h> #include <vespa/vdslib/state/state.h> #include <vespa/vdslib/state/node.h> #include <vespa/vdslib/state/nodestate.h> diff --git a/persistence/src/vespa/persistence/spi/context.h b/persistence/src/vespa/persistence/spi/context.h index 75d3eac4538..ca4c79e3005 100644 --- a/persistence/src/vespa/persistence/spi/context.h +++ b/persistence/src/vespa/persistence/spi/context.h @@ -29,7 +29,6 @@ #pragma once -#include <vespa/metrics/loadmetric.h> #include <persistence/spi/types.h> #include <vespa/persistence/spi/read_consistency.h> #include <vespa/vespalib/trace/trace.h> @@ -38,8 +37,7 @@ namespace metrics { class LoadType; } -namespace storage { -namespace spi { +namespace storage::spi { using LoadType = metrics::LoadType; @@ -93,6 +91,4 @@ public: { _trace.trace(level, msg, addTime); } }; -} // spi -} // storage - +} diff --git a/searchcore/src/tests/proton/persistenceengine/persistenceengine_test.cpp b/searchcore/src/tests/proton/persistenceengine/persistenceengine_test.cpp index bd274093f87..4b73e4ca115 100644 --- a/searchcore/src/tests/proton/persistenceengine/persistenceengine_test.cpp +++ b/searchcore/src/tests/proton/persistenceengine/persistenceengine_test.cpp @@ -13,6 +13,7 @@ #include <vespa/searchcore/proton/persistenceengine/persistenceengine.h> #include <vespa/vdslib/distribution/distribution.h> #include <vespa/vdslib/state/clusterstate.h> +#include <vespa/metrics/loadmetric.h> #include <vespa/vespalib/testkit/testapp.h> #include <algorithm> #include <set> diff --git a/searchcore/src/vespa/searchcore/proton/persistenceengine/persistenceengine.cpp b/searchcore/src/vespa/searchcore/proton/persistenceengine/persistenceengine.cpp index 390f8241b1d..e2b389fb898 100644 --- a/searchcore/src/vespa/searchcore/proton/persistenceengine/persistenceengine.cpp +++ b/searchcore/src/vespa/searchcore/proton/persistenceengine/persistenceengine.cpp @@ -3,6 +3,7 @@ #include "persistenceengine.h" #include "ipersistenceengineowner.h" #include "transport_latch.h" +#include <vespa/metrics/loadmetric.h> #include <vespa/vespalib/stllike/hash_set.h> #include <vespa/log/log.h> diff --git a/searchlib/src/vespa/searchlib/docstore/visitcache.cpp b/searchlib/src/vespa/searchlib/docstore/visitcache.cpp index 8f73c9862ae..7e881d8de76 100644 --- a/searchlib/src/vespa/searchlib/docstore/visitcache.cpp +++ b/searchlib/src/vespa/searchlib/docstore/visitcache.cpp @@ -209,8 +209,7 @@ VisitCache::Cache::locateAndInvalidateOtherSubsets(const LockGuard & cacheGuard, CompressedBlobSet VisitCache::read(const IDocumentStore::LidVector & lids) const { - KeySet key(lids); - return _cache->readSet(lids); + return _cache->readSet(KeySet(lids)); } void diff --git a/searchlib/src/vespa/searchlib/docstore/visitcache.h b/searchlib/src/vespa/searchlib/docstore/visitcache.h index 1bf867c5580..effc6c19a21 100644 --- a/searchlib/src/vespa/searchlib/docstore/visitcache.h +++ b/searchlib/src/vespa/searchlib/docstore/visitcache.h @@ -20,7 +20,7 @@ class KeySet { public: KeySet() : _keys() { } KeySet(uint32_t key); - KeySet(const IDocumentStore::LidVector &keys); + explicit KeySet(const IDocumentStore::LidVector &keys); uint32_t hash() const { return _keys.empty() ? 0 : _keys[0]; } bool operator==(const KeySet &rhs) const { return _keys == rhs._keys; } bool operator<(const KeySet &rhs) const { return _keys < rhs._keys; } diff --git a/staging_vespalib/src/vespa/vespalib/stllike/lrucache_map.hpp b/staging_vespalib/src/vespa/vespalib/stllike/lrucache_map.hpp index fe57de093dd..61147229497 100644 --- a/staging_vespalib/src/vespa/vespalib/stllike/lrucache_map.hpp +++ b/staging_vespalib/src/vespa/vespalib/stllike/lrucache_map.hpp @@ -110,6 +110,7 @@ void lrucache_map<P>::erase(const K & key) { internal_iterator it = HashTable::find(key); if (it != HashTable::end()) { + next_t h = HashTable::hash(key); onRemove(key); LV & v = it->second; if (v._prev != LinkedValueBase::npos) { @@ -122,7 +123,7 @@ lrucache_map<P>::erase(const K & key) { } else { _tail = v._prev; } - HashTable::erase(*this, it); + HashTable::erase(*this, h, it); } } @@ -202,7 +203,7 @@ lrucache_map<P>::removeOld() { { _tail = last->second._prev; HashTable::getByInternalIndex(_tail).second._next = LinkedValueBase::npos; - HashTable::erase(*this, HashTable::find(last->first)); + HashTable::erase(*this, HashTable::hash(last->first), HashTable::find(last->first)); } } } diff --git a/storage/src/tests/persistence/splitbitdetectortest.cpp b/storage/src/tests/persistence/splitbitdetectortest.cpp index c20aae373ec..01baa8f4e98 100644 --- a/storage/src/tests/persistence/splitbitdetectortest.cpp +++ b/storage/src/tests/persistence/splitbitdetectortest.cpp @@ -8,6 +8,7 @@ #include <vespa/persistence/spi/test.h> #include <vespa/document/base/testdocman.h> #include <vespa/document/bucket/bucketidfactory.h> +#include <vespa/metrics/loadmetric.h> #include <algorithm> using storage::spi::test::makeSpiBucket; diff --git a/storage/src/vespa/storage/common/bucketmessages.cpp b/storage/src/vespa/storage/common/bucketmessages.cpp index 3157bad49e5..e92e2d4c3bf 100644 --- a/storage/src/vespa/storage/common/bucketmessages.cpp +++ b/storage/src/vespa/storage/common/bucketmessages.cpp @@ -2,6 +2,7 @@ #include "bucketmessages.h" #include <vespa/vespalib/stllike/asciistream.h> +#include <ostream> using document::BucketSpace; diff --git a/storage/src/vespa/storage/persistence/splitbitdetector.h b/storage/src/vespa/storage/persistence/splitbitdetector.h index b3fc5bea566..6f1af6c5970 100644 --- a/storage/src/vespa/storage/persistence/splitbitdetector.h +++ b/storage/src/vespa/storage/persistence/splitbitdetector.h @@ -18,6 +18,7 @@ #pragma once #include <vespa/persistence/spi/persistenceprovider.h> +#include <vespa/vespalib/util/printable.h> namespace storage { diff --git a/vespalib/src/vespa/vespalib/stllike/hashtable.h b/vespalib/src/vespa/vespalib/stllike/hashtable.h index 263ee952c2e..55db2f6d384 100644 --- a/vespalib/src/vespa/vespalib/stllike/hashtable.h +++ b/vespalib/src/vespa/vespalib/stllike/hashtable.h @@ -141,19 +141,18 @@ public: typedef Value* pointer; typedef std::forward_iterator_tag iterator_category; - iterator(hashtable * hash, next_t start) : _hash(start), _subNode(start), _hashTable(hash) { - advanceToNextValidHash(); - } - iterator(hashtable * hash, next_t start, next_t subNode) : _hash(start), _subNode(subNode), _hashTable(hash) { } - Value & operator * () const { return _hashTable->get(_subNode); } - Value * operator -> () const { return & _hashTable->get(_subNode); } - iterator & operator ++ () { - if (_hashTable->_nodes[_subNode].hasNext()) { - _subNode = _hashTable->_nodes[_subNode].getNext(); - } else { - _hash++; + iterator(hashtable * hash) : _current(0), _hashTable(hash) { + if ((_current < _hashTable->initializedSize()) && ! _hashTable->_nodes[_current].valid()) { advanceToNextValidHash(); } + } + iterator(hashtable * hash, next_t pos) : _current(pos), _hashTable(hash) { } + static iterator end(hashtable *hash) { return iterator(hash, Node::npos); } + + Value & operator * () const { return _hashTable->get(_current); } + Value * operator -> () const { return & _hashTable->get(_current); } + iterator & operator ++ () { + advanceToNextValidHash(); return *this; } iterator operator ++ (int) { @@ -161,19 +160,19 @@ public: ++(*this); return prev; } - bool operator==(const iterator& rhs) const { return (_subNode == rhs._subNode); } - bool operator!=(const iterator& rhs) const { return (_subNode != rhs._subNode); } + bool operator==(const iterator& rhs) const { return (_current == rhs._current); } + bool operator!=(const iterator& rhs) const { return (_current != rhs._current); } /// Carefull about this one. Only used by lrucache. - next_t getInternalIndex() const { return _subNode; } - void setInternalIndex(next_t n) { _subNode = n; } - next_t getHash() const { return _hash; } + next_t getInternalIndex() const { return _current; } + void setInternalIndex(next_t n) { _current = n; } private: void advanceToNextValidHash() { - for (;(_hash < _hashTable->getTableSize()) && ! _hashTable->_nodes[_hash].valid(); _hash++) { } - _subNode = (_hash < _hashTable->getTableSize()) ? _hash : Node::npos; + for (_current++;(_current < _hashTable->initializedSize()) && ! _hashTable->_nodes[_current].valid(); _current++) { } + if (_current >= _hashTable->initializedSize()) { + _current = Node::npos; + } } - next_t _hash; - next_t _subNode; + next_t _current; hashtable * _hashTable; friend class hashtable::const_iterator; @@ -186,21 +185,19 @@ public: typedef const Value* pointer; typedef std::forward_iterator_tag iterator_category; - const_iterator(const hashtable * hash, next_t start) : _hash(start), _subNode(start), _hashTable(hash) { - advanceToNextValidHash(); - } - const_iterator(const hashtable * hash, next_t start, next_t subNode) : _hash(start), _subNode(subNode), _hashTable(hash) { } - const_iterator(const iterator &i) - : _hash(i._hash), _subNode(i._subNode), _hashTable(i._hashTable) {} - const Value & operator * () const { return _hashTable->get(_subNode); } - const Value * operator -> () const { return & _hashTable->get(_subNode); } - const_iterator & operator ++ () { - if (_hashTable->_nodes[_subNode].hasNext()) { - _subNode = _hashTable->_nodes[_subNode].getNext(); - } else { - _hash++; + const_iterator(const hashtable * hash) : _current(0), _hashTable(hash) { + if ((_current < _hashTable->initializedSize()) && ! _hashTable->_nodes[_current].valid()) { advanceToNextValidHash(); } + } + const_iterator(const hashtable * hash, next_t pos) : _current(pos), _hashTable(hash) { } + const_iterator(const iterator &i) : _current(i._current), _hashTable(i._hashTable) {} + static const_iterator end(const hashtable *hash) { return const_iterator(hash, Node::npos); } + + const Value & operator * () const { return _hashTable->get(_current); } + const Value * operator -> () const { return & _hashTable->get(_current); } + const_iterator & operator ++ () { + advanceToNextValidHash(); return *this; } const_iterator operator ++ (int) { @@ -208,17 +205,17 @@ public: ++(*this); return prev; } - bool operator==(const const_iterator& rhs) const { return (_subNode == rhs._subNode); } - bool operator!=(const const_iterator& rhs) const { return (_subNode != rhs._subNode); } - next_t getInternalIndex() const { return _subNode; } - next_t getHash() const { return _hash; } + bool operator==(const const_iterator& rhs) const { return (_current == rhs._current); } + bool operator!=(const const_iterator& rhs) const { return (_current != rhs._current); } + next_t getInternalIndex() const { return _current; } private: void advanceToNextValidHash() { - for (;(_hash < _hashTable->getTableSize()) && ! _hashTable->_nodes[_hash].valid(); _hash++) { } - _subNode = (_hash < _hashTable->getTableSize()) ? _hash : Node::npos; + for (_current++;(_current < _hashTable->initializedSize()) && ! _hashTable->_nodes[_current].valid(); _current++) { } + if (_current >= _hashTable->initializedSize()) { + _current = Node::npos; + } } - next_t _hash; - next_t _subNode; + next_t _current; const hashtable * _hashTable; }; typedef std::pair<iterator, bool> insert_result; @@ -231,10 +228,10 @@ public: hashtable(size_t reservedSpace); hashtable(size_t reservedSpace, const Hash & hasher, const Equal & equal); virtual ~hashtable(); - iterator begin() { return iterator(this, 0); } - iterator end() { return iterator(this, Node::npos); } - const_iterator begin() const { return const_iterator(this, 0); } - const_iterator end() const { return const_iterator(this, Node::npos); } + iterator begin() { return iterator(this); } + iterator end() { return iterator::end(this); } + const_iterator begin() const { return const_iterator(this); } + const_iterator end() const { return const_iterator::end(this); } size_t capacity() const { return _nodes.capacity(); } size_t size() const { return _count; } bool empty() const { return _count == 0; } @@ -280,7 +277,8 @@ protected: Value & getByInternalIndex(size_t index) { return _nodes[index].getValue(); } const Value & getByInternalIndex(size_t index) const { return _nodes[index].getValue(); } template <typename MoveHandler> - void erase(MoveHandler & moveHandler, const const_iterator & key); + void erase(MoveHandler & moveHandler, next_t h, const const_iterator & key); + next_t hash(const Key & key) const { return modulator(_hasher(key)); } private: Modulator _modulator; size_t _count; @@ -292,7 +290,7 @@ private: const Value & get(size_t index) const { return _nodes[index].getValue(); } next_t modulator(next_t key) const { return _modulator.modulo(key); } next_t getTableSize() const { return _modulator.getTableSize(); } - next_t hash(const Key & key) const { return modulator(_hasher(key)); } + size_t initializedSize() const { return _nodes.size(); } template <typename MoveHandler> void move(MoveHandler & moveHandler, next_t from, next_t to) { _nodes[to] = std::move(_nodes[from]); diff --git a/vespalib/src/vespa/vespalib/stllike/hashtable.hpp b/vespalib/src/vespa/vespalib/stllike/hashtable.hpp index 359e71aa0d2..57e8dcc4b03 100644 --- a/vespalib/src/vespa/vespalib/stllike/hashtable.hpp +++ b/vespalib/src/vespa/vespalib/stllike/hashtable.hpp @@ -67,11 +67,10 @@ typename hashtable<Key, Value, Hash, Equal, KeyExtract, Modulator>::iterator hashtable<Key, Value, Hash, Equal, KeyExtract, Modulator>::find(const Key & key) { next_t h = hash(key); - if (_nodes[h].valid()) { - next_t start(h); + if (__builtin_expect(_nodes[h].valid(), true)) { do { - if (_equal(_keyExtractor(_nodes[h].getValue()), key)) { - return iterator(this, start, h); + if (__builtin_expect(_equal(_keyExtractor(_nodes[h].getValue()), key), true)) { + return iterator(this, h); } h = _nodes[h].getNext(); } while (h != Node::npos); @@ -84,11 +83,10 @@ typename hashtable<Key, Value, Hash, Equal, KeyExtract, Modulator>::const_iterat hashtable<Key, Value, Hash, Equal, KeyExtract, Modulator>::find(const Key & key) const { next_t h = hash(key); - if (_nodes[h].valid()) { - next_t start(h); + if (__builtin_expect(_nodes[h].valid(), true)) { do { - if (_equal(_keyExtractor(_nodes[h].getValue()), key)) { - return const_iterator(this, start, h); + if (__builtin_expect(_equal(_keyExtractor(_nodes[h].getValue()), key), true)) { + return const_iterator(this, h); } h = _nodes[h].getNext(); } while (h != Node::npos); @@ -104,11 +102,10 @@ hashtable<Key, Value, Hash, Equal, KeyExtract, Modulator>::find(const AltKey & k AltHash altHasher; next_t h = modulator(altHasher(key)); if (_nodes[h].valid()) { - next_t start(h); AltEqual altEqual; do { if (altEqual(altExtract(_keyExtractor(_nodes[h].getValue())), key)) { - return const_iterator(this, start, h); + return const_iterator(this, h); } h = _nodes[h].getNext(); } while (h != Node::npos); @@ -124,11 +121,10 @@ hashtable<Key, Value, Hash, Equal, KeyExtract, Modulator>::find(const AltKey & k AltHash altHasher; next_t h = modulator(altHasher(key)); if (_nodes[h].valid()) { - next_t start(h); AltEqual altEqual; do { if (altEqual(altExtract(_keyExtractor(_nodes[h].getValue())), key)) { - return iterator(this, start, h); + return iterator(this, h); } h = _nodes[h].getNext(); } while (h != Node::npos); @@ -149,7 +145,7 @@ hashtable<Key, Value, Hash, Equal, KeyExtract, Modulator>::erase(const Key & key const_iterator found(find(key)); if (found != end()) { DefaultMoveHandler moveHandler; - erase(moveHandler, found); + erase(moveHandler, hash(key), found); } } @@ -169,11 +165,11 @@ hashtable<Key, Value, Hash, Equal, KeyExtract, Modulator>::insertInternal(V && n if ( ! _nodes[h].valid() ) { _nodes[h] = std::forward<V>(node); _count++; - return insert_result(iterator(this, h, h), true); + return insert_result(iterator(this, h), true); } else if (_nodes.size() <= _nodes.capacity()) { 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, h, c), false); + return insert_result(iterator(this, c), false); } } if (_nodes.size() < _nodes.capacity()) { @@ -182,7 +178,7 @@ hashtable<Key, Value, Hash, Equal, KeyExtract, Modulator>::insertInternal(V && n _nodes[h].setNext(newIdx); new (_nodes.push_back_fast()) Node(std::forward<V>(node), p); _count++; - return insert_result(iterator(this, h, newIdx), true); + return insert_result(iterator(this, newIdx), true); } else { resize(_nodes.capacity()*2); return insertInternal(std::forward<V>(node)); @@ -214,9 +210,8 @@ void hashtable<Key, Value, Hash, Equal, KeyExtract, Modulator>::reclaim(MoveHand template< typename Key, typename Value, typename Hash, typename Equal, typename KeyExtract, typename Modulator > template <typename MoveHandler> void -hashtable<Key, Value, Hash, Equal, KeyExtract, Modulator>::erase(MoveHandler & moveHandler, const const_iterator & it) +hashtable<Key, Value, Hash, Equal, KeyExtract, Modulator>::erase(MoveHandler & moveHandler, next_t h, const const_iterator & it) { - next_t h = it.getHash(); next_t prev = Node::npos; do { if (h == it.getInternalIndex()) { |