Add: darray, cow_darray, cow_iterator; Adjust cow_vector to cow_darray findings (deprecated); Performance enhancements

cow_darray, cow_vector design changes / notes:
- Aligned all typedef's names etc between both implementations for easier review

- Removed direct element access, as this would be only valid if Value_type is a std:share_ptr,
  assuming the underlying shared storage has been pulled.
  Use iterator!

- Introducing immutable const_iterator (a jau::cow_ro_iterator) and mutable iterator (a jau::cow_rw_iterator).
  Both types hold the underling's iterator and also either the lock-free shared snapshot (const_iterator)
  or hold the lock and a copy of the storage (iterator).
  This guarantees an efficient std API aligned operation, keeping alove std::shared_ptr references.

- Removed for_each_cow: Use std::for_each with our new const_iterator or iterator etc...

Performance changes / notes:
- cow_darray: Use fixed golden-ratio for grow-factor in push_back(), reducing too many copies.

- cow_darray::push_back(..): No copy on size < capacity, just push_back into underling,
  dramatically reducing copies.
  Guaranteed correct using cow_darray + darray, as darray increments end_ iterator
  after the new element has been added.

- Always use pre-increment/decrement, avoiding copy with post-* variant.

cow_vector fixes (learned from working with cow_darray)
- reserve(): Only is new_capacity > capacity, then need copy_ctor storage
- operator=(cow_vector&& x): Hold both cow_vector's write-mutex
- pop_back(): Only if not empty
-

+++

Performance seems to fluctuate on the allocator
and we might want resolve this with a custom pooled alloctor.
This is obvious when comparing the 'empty' samples with 'reserved',
the latter reserve whole memory of the std::vector and jau::darray upfront.

Performance on arm64-raspi4 jau::cow_vector vs jau::cow_darray:
- sequential fill and list O(1): cow_vector is ~30 times slower
  (starting empty)
  (delta due to cow_darray capacity usage, less copies)

- unique fill and list O(n*n): cow_vector is 2-3 times slower
  (starting empty)
  (most time used for equal time dereferencing)

Performance on arm64-raspi4 std::vector vs jau::darray:
- sequential fill and list iterator O(1): jau::darray is ~0% - 40% slower (50 .. 1000)
  (starting empty)
  (we may call this almost equal, probably allocator related)

- unique fill and list iterator O(n*n): std::vector is ~0% - 23% slower (50 .. 1000)
  (starting empty)
  (almost equal, most time used for equal time dereferencing)

+++

Performance on amd64 jau::cow_vector vs jau::cow_darray:
- sequential fill and list O(1): cow_vector is ~38 times slower
  (starting empty)
  (delta due to cow_darray capacity usage, less copies)

- unique fill and list O(n*n): cow_vector is ~2 times slower
  (starting empty)
  (most time used for equal time dereferencing)

Performance on amd64 std::vector vs jau::darray:
- sequential fill and list iterator O(1): jau::darray is ~0% - 20% slower (50 .. 1000)
  (starting empty)
  (we may call this almost equal, probably allocator related)

- unique fill and list iterator O(n*n): std::vector is ~0% - 30% slower (50 .. 1000)
  (starting empty)
  (almost equal, most time used for equal time dereferencing)

+++

Memory ratio allocation/size jau::cow_vector vs jau::cow_darray having size:
-   50: 2 vs 1.1
-  100: 2 vs 1.44
- 1000: 2 vs 1.6
- Hence cow_darray golden-ratio growth factor is more efficient on size + perf.

Memory ratio allocation/size std::vector vs jau::darray having size:
-   50: 1.28 vs 1.10
-  100: 1.28 vs 1.44
- 1000: 1.03 vs 1.60
- Hence cow_darray golden-ratio growth factor is less efficient on big sizes
  (but configurable)

1 files changed, 254 insertions, 0 deletions

diff --git a/include/jau/cow_iterator.hpp b/include/jau/cow_iterator.hpp
new file mode 100644
index 0000000..8ebd9c1
--- /dev/null
+++ b/include/jau/cow_iterator.hpp
@@ -0,0 +1,254 @@
+/*
+ * Author: Sven Gothel <[email protected]>
+ * Copyright (c) 2020 Gothel Software e.K.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining
+ * a copy of this software and associated documentation files (the
+ * "Software"), to deal in the Software without restriction, including
+ * without limitation the rights to use, copy, modify, merge, publish,
+ * distribute, sublicense, and/or sell copies of the Software, and to
+ * permit persons to whom the Software is furnished to do so, subject to
+ * the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
+ * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+ * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
+ * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ */
+
+#ifndef JAU_COW_ITERATOR_HPP_
+#define JAU_COW_ITERATOR_HPP_
+
+#include <cstddef>
+#include <mutex>
+
+namespace jau {
+
+    /**
+     * Implementation of a Copy-On-Write (CoW) read-only iterator for immutable Value_type,
+     * holding the shared Value_type& of the current CoW storage until destruction.
+     */
+    template <typename Value_type, typename Storage_type, typename Storage_ref_type>
+    class cow_ro_iterator {
+
+        private:
+            Storage_ref_type store_holder_;
+            typename Storage_type::const_iterator iterator_;
+
+        public:
+            constexpr cow_ro_iterator(Storage_ref_type store, typename Storage_type::const_iterator iter)
+            : store_holder_(store), iterator_(iter) {}
+
+            constexpr explicit cow_ro_iterator(const cow_ro_iterator& o) noexcept
+            : store_holder_(o.store_holder_), iterator_(o.iterator_) {}
+
+            /**
+             * Returns a copy of the underlying storage const_iterator.
+             */
+            typename Storage_type::const_iterator underling() const noexcept { return iterator_; };
+
+            // Multipass guarantee equality
+
+            constexpr bool operator==(const cow_ro_iterator& rhs) const noexcept {
+                if( this == &rhs ) {
+                    return true;
+                }
+                // only testing identity of pointer, OK for Multipass guarantee
+                return store_holder_ == rhs.store_holder_ &&
+                       iterator_ == rhs.iterator_;
+            }
+            constexpr bool operator!=(const cow_ro_iterator& rhs) const noexcept
+            { return !(*this == rhs); }
+
+            // Forward iterator requirements
+
+            constexpr const Value_type& operator*() const noexcept
+            { return *iterator_; }
+
+            constexpr const Value_type* operator->() const noexcept
+            { return iterator_; }
+
+            /** Pre-increment; Well performing, return *this.  */
+            constexpr cow_ro_iterator& operator++() noexcept {
+                ++iterator_;
+                return *this;
+            }
+
+            /** Post-increment; Try to avoid: Low performance due to returning copy-ctor. */
+            constexpr cow_ro_iterator& operator++(int) noexcept
+            { return cow_ro_iterator(store_holder_, iterator_++); }
+
+            // Bidirectional iterator requirements
+
+            /** Pre-decrement; Well performing, return *this.  */
+            constexpr cow_ro_iterator& operator--() noexcept {
+                --iterator_;
+                return *this;
+            }
+
+            /** Post-decrement; Try to avoid: Low performance due to returning copy-ctor. */
+            constexpr cow_ro_iterator& operator--(int) noexcept
+            { return cow_iterator(store_holder_, iterator_--); }
+
+            // Random access iterator requirements
+
+            /** Subscript of 'element_index', returning immutable Value_type reference. */
+            constexpr const Value_type& operator[](std::ptrdiff_t i) const noexcept
+            { return iterator_[i]; }
+
+            /** Addition-assignment of 'element_count'; Well performing, return *this.  */
+            constexpr cow_ro_iterator& operator+=(std::ptrdiff_t i) noexcept
+            { iterator_ += i; return *this; }
+
+            /** Binary 'iterator + element_count'; Try to avoid: Low performance due to returning copy-ctor. */
+            constexpr cow_ro_iterator operator+(std::ptrdiff_t rhs) const noexcept
+            { return cow_iterator(store_holder_, iterator_ + rhs); }
+
+            /** Subtraction-assignment of 'element_count'; Well performing, return *this.  */
+            constexpr cow_ro_iterator& operator-=(std::ptrdiff_t i) noexcept
+            { iterator_ -= i; return *this; }
+
+            /** Binary 'iterator - element_count'; Try to avoid: Low performance due to returning copy-ctor. */
+            constexpr cow_ro_iterator operator-(std::ptrdiff_t rhs) const noexcept
+            { return cow_iterator(store_holder_, iterator_ - rhs); }
+
+            // Distance or element count, binary subtraction of two iterator.
+
+            /** Binary 'iterator - iterator -> element_count'; Well performing, return element_count of type std::ptrdiff_t. */
+            constexpr std::ptrdiff_t operator-(const cow_ro_iterator& rhs) const noexcept
+            { return iterator_ - rhs.iterator_; }
+    };
+
+    /**
+     * Implementation of a Copy-On-Write (CoW) read-write iterator for mutable Value_type,
+     * holding the write lock, a new copy of the CoW storage and a Value_type& of the CoW container itself.
+     * <p>
+     * At destruction, the mutated local storage will replace the
+     * storage in the CoW container and the lock will be released.
+     * </p>
+     */
+    template <typename Value_type, typename Storage_type, typename Storage_ref_type, typename CoW_container>
+    class cow_rw_iterator {
+
+        private:
+            CoW_container& cow_parent_;
+            const std::lock_guard<std::recursive_mutex> lock_;
+            Storage_ref_type new_store_;
+            typename Storage_type::iterator iterator_;
+
+            constexpr explicit cow_rw_iterator(CoW_container& cow_parent, Storage_ref_type& store, typename Storage_type::iterator iter) noexcept
+            : cow_parent_(cow_parent), lock_(cow_parent.get_write_mutex()), new_store_(store), iterator_(iter) {}
+
+        public:
+            constexpr cow_rw_iterator(CoW_container& cow_parent, typename Storage_type::iterator (*get_iterator)(Storage_ref_type&))
+            : cow_parent_(cow_parent), lock_(cow_parent.get_write_mutex()), new_store_(cow_parent.copy_store()), iterator_(get_iterator(new_store_)) {}
+
+#if __cplusplus > 201703L
+            constexpr ~cow_rw_iterator() noexcept
+#else
+            ~cow_rw_iterator() noexcept
+#endif
+            {
+                cow_parent_.set_store(std::move(new_store_));
+            }
+
+            /**
+             * Returns a copy of the underlying storage iterator.
+             */
+            typename Storage_type::iterator underling() const noexcept { return iterator_; };
+
+            // Multipass guarantee equality
+
+            constexpr bool operator==(const cow_rw_iterator& rhs) const noexcept {
+                if( this == &rhs ) {
+                    return true;
+                }
+                // only testing identity of pointer, OK for Multipass guarantee
+                return &cow_parent_ == &rhs.cow_parent_ &&
+                       new_store_ == rhs.new_store_ &&
+                       iterator_ == rhs.iterator_;
+            }
+            constexpr bool operator!=(const cow_rw_iterator& rhs) const noexcept
+            { return !(*this == rhs); }
+
+            // Forward iterator requirements
+
+            constexpr const Value_type& operator*() const noexcept
+            { return *iterator_; }
+
+            constexpr const Value_type* operator->() const noexcept
+            { return iterator_; }
+
+            constexpr Value_type& operator*() noexcept
+            { return *iterator_; }
+
+            constexpr Value_type* operator->() noexcept
+            { return iterator_; }
+
+            /** Pre-increment; Well performing, return *this.  */
+            constexpr cow_rw_iterator& operator++() noexcept {
+                ++iterator_;
+                return *this;
+            }
+
+            /** Post-increment; Try to avoid: Low performance due to returning copy-ctor. */
+            constexpr cow_rw_iterator& operator++(int) noexcept
+            { return cow_rw_iterator(cow_parent_, new_store_, iterator_++); }
+
+            // Bidirectional iterator requirements
+
+            /** Pre-decrement; Well performing, return *this.  */
+            constexpr cow_rw_iterator& operator--() noexcept {
+                --iterator_;
+                return *this;
+            }
+
+            /** Post-decrement; Try to avoid: Low performance due to returning copy-ctor. */
+            constexpr cow_rw_iterator& operator--(int) noexcept
+            { return cow_rw_iterator(cow_parent_, new_store_, iterator_--); }
+
+            // Random access iterator requirements
+
+            /** Subscript of 'element_index', returning immutable Value_type reference. */
+            constexpr const Value_type& operator[](std::ptrdiff_t i) const noexcept
+            { return iterator_[i]; }
+
+            /** Subscript of 'element_index', returning mutable Value_type reference. */
+            constexpr Value_type& operator[](std::ptrdiff_t i) noexcept
+            { return iterator_[i]; }
+
+            /** Addition-assignment of 'element_count'; Well performing, return *this.  */
+            constexpr cow_rw_iterator& operator+=(std::ptrdiff_t i) noexcept
+            { iterator_ += i; return *this; }
+
+            /** Binary 'iterator + element_count'; Try to avoid: Low performance due to returning copy-ctor. */
+            constexpr cow_rw_iterator operator+(std::ptrdiff_t rhs) const noexcept
+            { return cow_rw_iterator(cow_parent_, new_store_, iterator_ + rhs); }
+
+            /** Subtraction-assignment of 'element_count'; Well performing, return *this.  */
+            constexpr cow_rw_iterator& operator-=(std::ptrdiff_t i) noexcept
+            { iterator_ -= i; return *this; }
+
+            /** Binary 'iterator - element_count'; Try to avoid: Low performance due to returning copy-ctor. */
+            constexpr cow_rw_iterator operator-(std::ptrdiff_t rhs) const noexcept
+            { return cow_rw_iterator(cow_parent_, new_store_, iterator_ - rhs); }
+
+            // constexpr const cow_rw_iterator& base() const noexcept
+            // { return iterator_; }
+
+            // Distance or element count, binary subtraction of two iterator.
+
+            /** Binary 'iterator - iterator -> element_count'; Well performing, return element_count of type std::ptrdiff_t. */
+            constexpr std::ptrdiff_t operator-(const cow_rw_iterator& rhs) const noexcept
+            { return iterator_ - rhs.iterator_; }
+    };
+
+} /* namespace jau */
+
+#endif /* JAU_COW_ITERATOR_HPP_ */