Use a faster and simpler iteration for speed and simplicity.

2 files changed, 54 insertions, 61 deletions

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..ada3f455017 100644
--- a/vespalib/src/vespa/vespalib/stllike/hashtable.hpp
+++ b/vespalib/src/vespa/vespalib/stllike/hashtable.hpp
@@ -68,10 +68,9 @@ hashtable<Key, Value, Hash, Equal, KeyExtract, Modulator>::find(const Key & key)
 {
     next_t h = hash(key);
     if (_nodes[h].valid()) {
-        next_t start(h);
         do {
             if (_equal(_keyExtractor(_nodes[h].getValue()), key)) {
-                return iterator(this, start, h);
+                return iterator(this, h);
             }
             h = _nodes[h].getNext();
         } while (h != Node::npos);
@@ -85,10 +84,9 @@ hashtable<Key, Value, Hash, Equal, KeyExtract, Modulator>::find(const Key & key)
 {
     next_t h = hash(key);
     if (_nodes[h].valid()) {
-        next_t start(h);
         do {
             if (_equal(_keyExtractor(_nodes[h].getValue()), key)) {
-                return const_iterator(this, start, h);
+                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()) {