Merge pull request #4538 from vespa-engine/balder/fast-for_each

Balder/fast for each

8 files changed, 52 insertions, 8 deletions

diff --git a/document/src/test/resources/tensor/multi_cell_tensor__cpp b/document/src/test/resources/tensor/multi_cell_tensor__cpp
index c0b2b3a165a..d4c7c5fbbe5 100644
--- a/document/src/test/resources/tensor/multi_cell_tensor__cpp
+++ b/document/src/test/resources/tensor/multi_cell_tensor__cpp
diff --git a/eval/src/vespa/eval/tensor/sparse/sparse_tensor.cpp b/eval/src/vespa/eval/tensor/sparse/sparse_tensor.cpp
index 1aa05bf4f61..b69b1cdab05 100644
--- a/eval/src/vespa/eval/tensor/sparse/sparse_tensor.cpp
+++ b/eval/src/vespa/eval/tensor/sparse/sparse_tensor.cpp
@@ -82,9 +82,7 @@ double
 SparseTensor::as_double() const
 {
     double result = 0.0;
-    for (const auto &cell : _cells) {
-        result += cell.second;
-    }
+    _cells.for_each([&result](const auto & v) { result += v.second; });
     return result;
 }
 
diff --git a/eval/src/vespa/eval/tensor/sparse/sparse_tensor_address_combiner.cpp b/eval/src/vespa/eval/tensor/sparse/sparse_tensor_address_combiner.cpp
index e0de63b90d2..aafb87c9d67 100644
--- a/eval/src/vespa/eval/tensor/sparse/sparse_tensor_address_combiner.cpp
+++ b/eval/src/vespa/eval/tensor/sparse/sparse_tensor_address_combiner.cpp
@@ -3,7 +3,6 @@
 #include "sparse_tensor_address_combiner.h"
 #include "sparse_tensor_address_decoder.h"
 #include <vespa/eval/eval/value_type.h>
-#include <cassert>
 
 namespace vespalib::tensor::sparse {
 
diff --git a/vespalib/src/tests/stllike/hash_test.cpp b/vespalib/src/tests/stllike/hash_test.cpp
index b405ac84797..af889754530 100644
--- a/vespalib/src/tests/stllike/hash_test.cpp
+++ b/vespalib/src/tests/stllike/hash_test.cpp
@@ -402,8 +402,7 @@ TEST("test hash set iterators stl compatible")
     EXPECT_TRUE((equal_types<iter_traits::value_type, int>::value));
     EXPECT_TRUE((equal_types<iter_traits::reference, int&>::value));
     EXPECT_TRUE((equal_types<iter_traits::pointer, int*>::value));
-    EXPECT_TRUE((equal_types<iter_traits::iterator_category,
-                             std::forward_iterator_tag>::value));
+    EXPECT_TRUE((equal_types<iter_traits::iterator_category, std::forward_iterator_tag>::value));
 
     typedef set_type::const_iterator const_iter_type;
     typedef std::iterator_traits<const_iter_type> const_iter_traits;
@@ -411,8 +410,28 @@ TEST("test hash set iterators stl compatible")
     EXPECT_TRUE((equal_types<const_iter_traits::value_type, const int>::value));
     EXPECT_TRUE((equal_types<const_iter_traits::reference, const int&>::value));
     EXPECT_TRUE((equal_types<const_iter_traits::pointer, const int*>::value));
-    EXPECT_TRUE((equal_types<const_iter_traits::iterator_category,
-                             std::forward_iterator_tag>::value));
+    EXPECT_TRUE((equal_types<const_iter_traits::iterator_category, std::forward_iterator_tag>::value));
+}
+
+void
+verify_sum(const hash_map<size_t, size_t> & m, size_t expexted_sum) {
+    size_t computed_sum = 0;
+    std::for_each(m.begin(), m.end(), [&computed_sum](const auto & v) { computed_sum += v.second; });
+    EXPECT_EQUAL(expexted_sum, computed_sum);
+    computed_sum = 0;
+    m.for_each([&computed_sum](const auto & v) { computed_sum += v.second; });
+    EXPECT_EQUAL(expexted_sum, computed_sum);
+}
+
+TEST("test that for_each member works as std::for_each") {
+    hash_map<size_t, size_t> m;
+    size_t expected_sum(0);
+    for (size_t i(0); i < 1000; i++) {
+        TEST_DO(verify_sum(m, expected_sum));
+        m[i] = i;
+        expected_sum += i;
+    }
+    TEST_DO(verify_sum(m, expected_sum));
 }
 
 using IntHashSet = hash_set<int>;
diff --git a/vespalib/src/vespa/vespalib/stllike/hash_map.h b/vespalib/src/vespa/vespalib/stllike/hash_map.h
index 023594d3018..f2431a73f28 100644
--- a/vespalib/src/vespa/vespalib/stllike/hash_map.h
+++ b/vespalib/src/vespa/vespalib/stllike/hash_map.h
@@ -38,6 +38,10 @@ public:
     insert_result insert(const value_type & value) { return _ht.insert(value); }
     template <typename InputIt>
     void insert(InputIt first, InputIt last);
+
+    /// This gives faster iteration than can be achieved by the iterators.
+    template <typename Func>
+    void for_each(Func func) const { _ht.for_each(func); }
     const V & operator [] (const K & key) const { return _ht.find(key)->second; }
     V & operator [] (const K & key)             { return _ht.insert(value_type(key, V())).first->second; }
     void erase(const K & key);
diff --git a/vespalib/src/vespa/vespalib/stllike/hash_set.h b/vespalib/src/vespa/vespalib/stllike/hash_set.h
index bde2a62c37b..bb16932a990 100644
--- a/vespalib/src/vespa/vespalib/stllike/hash_set.h
+++ b/vespalib/src/vespa/vespalib/stllike/hash_set.h
@@ -43,6 +43,10 @@ public:
     iterator find(const K & key)             { return _ht.find(key); }
     const_iterator find(const K & key) const { return _ht.find(key); }
 
+    /// This gives faster iteration than can be achieved by the iterators.
+    template <typename Func>
+    void for_each(Func func) const { _ht.for_each(func); }
+
     template< typename AltKey, typename AltExtract, typename AltHash, typename AltEqual >
     const_iterator find(const AltKey & key) const { return _ht.template find<AltKey, AltExtract, AltHash, AltEqual>(key); }
 
diff --git a/vespalib/src/vespa/vespalib/stllike/hashtable.h b/vespalib/src/vespa/vespalib/stllike/hashtable.h
index 15949067a60..16d9cde1f78 100644
--- a/vespalib/src/vespa/vespalib/stllike/hashtable.h
+++ b/vespalib/src/vespa/vespalib/stllike/hashtable.h
@@ -249,6 +249,11 @@ public:
     insert_result insert(V && node) {
         return insertInternal(std::forward<V>(node));
     }
+    
+    /// This gives faster iteration than can be achieved by the iterators.
+    template <typename Func>
+    void for_each(Func func) const;
+
     void erase(const Key & key);
     void reserve(size_t sz) {
         if (sz > _nodes.capacity()) {
diff --git a/vespalib/src/vespa/vespalib/stllike/hashtable.hpp b/vespalib/src/vespa/vespalib/stllike/hashtable.hpp
index f499ba35f3f..2fbe83eb226 100644
--- a/vespalib/src/vespa/vespalib/stllike/hashtable.hpp
+++ b/vespalib/src/vespa/vespalib/stllike/hashtable.hpp
@@ -201,6 +201,21 @@ 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 Func>
+void hashtable<Key, Value, Hash, Equal, KeyExtract, Modulator>::for_each(Func func) const
+{
+    uint32_t i(0);
+    for (; i < _modulator.getTableSize(); i++) {
+        if (_nodes[i].valid()) {
+            func(_nodes[i].getValue());
+        }
+    }
+    for (; i < _nodes.size(); i++) {
+        func(_nodes[i].getValue());
+    }
+}
+
+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, next_t h, const const_iterator & it)