[Bf-blender-cvs] [0f1b4d7c38e] functions: Use actual hash tables instead of linear search

Jacques Lucke noreply at git.blender.org
Sun Apr 7 17:02:53 CEST 2019


Commit: 0f1b4d7c38e6dd0225c9c5fe72fb844e63bb49aa
Author: Jacques Lucke
Date:   Sun Apr 7 17:01:31 2019 +0200
Branches: functions
https://developer.blender.org/rB0f1b4d7c38e6dd0225c9c5fe72fb844e63bb49aa

Use actual hash tables instead of linear search

The hash functions themselves are not optimized yet.

===================================================================

A	source/blender/blenlib/BLI_array_lookup.hpp
M	source/blender/blenlib/BLI_shared.hpp
M	source/blender/blenlib/BLI_small_map.hpp
M	source/blender/blenlib/BLI_small_set.hpp
M	source/blender/blenlib/BLI_small_set_vector.hpp
M	source/blender/blenlib/BLI_small_vector.hpp
M	source/blender/blenlib/CMakeLists.txt
M	source/blender/functions/core/data_flow_graph.hpp
M	source/blender/functions/core/type.hpp
M	source/blender/functions/frontends/data_flow_nodes/inserters.cpp
A	tests/gtests/blenlib/BLI_array_lookup_test.cc
M	tests/gtests/blenlib/BLI_small_map_test.cc
M	tests/gtests/blenlib/BLI_small_set_vector_test.cc
M	tests/gtests/blenlib/CMakeLists.txt

===================================================================

diff --git a/source/blender/blenlib/BLI_array_lookup.hpp b/source/blender/blenlib/BLI_array_lookup.hpp
new file mode 100644
index 00000000000..08741f9ff96
--- /dev/null
+++ b/source/blender/blenlib/BLI_array_lookup.hpp
@@ -0,0 +1,181 @@
+#pragma once
+
+#include "BLI_utildefines.h"
+#include "BLI_small_vector.hpp"
+#include "BLI_math_bits.h"
+
+#define SLOT_EMPTY -1
+#define SLOT_DUMMY -2
+#define LOAD_FACTOR 0.6f
+#define PERTURB_SHIFT 5
+
+#define ITER_SLOTS(KEY, SLOT, STATE) \
+	uint32_t SLOT, SLOT##_perturb; \
+	State STATE; \
+	for (this->first_slot(KEY, &SLOT, &SLOT##_perturb), STATE = m_map[SLOT];; \
+		 this->next_slot(&SLOT, &SLOT##_perturb), STATE = m_map[SLOT])
+
+namespace BLI {
+
+	template<typename T>
+	inline const T &get_key_from_item(const T &item)
+	{
+		return item;
+	}
+
+	template<
+		typename Key,
+		typename Item = Key,
+		const Key &GetKey(const Item &entry) = get_key_from_item,
+		uint N_EXP = 3,
+		typename Hash = std::hash<Key>,
+		typename Index = uint32_t>
+	class ArrayLookup {
+	private:
+		using State = typename std::make_signed<Index>::type;
+		using Mapping = SmallVector<State, (1 << N_EXP)>;
+		Mapping m_map;
+		uint m_usable_slots;
+		uint m_length;
+		uint32_t m_slot_mask;
+
+	public:
+		ArrayLookup()
+		{
+			this->reset_map(1 << N_EXP);
+			m_length = 0;
+		}
+
+		void ensure_can_add(Item *array, uint amount = 1)
+		{
+			if (LIKELY(m_usable_slots >= amount)) {
+				return;
+			}
+
+			this->reset_map(m_map.size() * 2);
+			for (uint i = 0; i < m_length; i++) {
+				const Key &key = GetKey(array[i]);
+				this->insert_index(key, i);
+			}
+			m_usable_slots -= m_length;
+		}
+
+		bool contains(Item *array, const Key &key) const
+		{
+			ITER_SLOTS(key, slot, state) {
+				if (state == SLOT_EMPTY) {
+					return false;
+				}
+				else if (state == SLOT_DUMMY) {
+					continue;
+				}
+				else if (GetKey(array[state]) == key) {
+					return true;
+				}
+			}
+		}
+
+		void add_new(Item *array, Index index)
+		{
+			this->ensure_can_add(array);
+			const Key &key = GetKey(array[index]);
+			this->add_new__fast(key, index);
+			m_usable_slots--;
+			m_length++;
+		}
+
+		void add_new_range(Item *array, Index start, Index end)
+		{
+			BLI_assert(start <= end);
+			uint amount = end - start;
+			this->ensure_can_add(array, amount);
+			for (Index i = start; i < end; i++) {
+				const Key &key = GetKey(array[index]);
+				this->add_new__fast(key, i);
+			}
+			m_usable_slots -= amount;
+			m_length += amount;
+		}
+
+		void add_new__fast(const Key &key, Index index)
+		{
+			ITER_SLOTS(key, slot, state) {
+				if (state == SLOT_EMPTY) {
+					m_map[slot] = (State)index;
+					break;
+				}
+			}
+		}
+
+		void remove(const Key &key, Index index)
+		{
+			ITER_SLOTS(key, slot, state) {
+				if (state == index) {
+					m_map[slot] = SLOT_DUMMY;
+					m_length--;
+					break;
+				}
+			}
+		}
+
+		typename std::make_signed<Index>::type find(
+			Item *array, const Key &key) const
+		{
+			ITER_SLOTS(key, slot, state) {
+				if (state == SLOT_EMPTY) {
+					return -1;
+				}
+				else if (state == SLOT_DUMMY) {
+					continue;
+				}
+				else if (GetKey(array[state]) == key) {
+					return state;
+				}
+			}
+		}
+
+	private:
+		inline void reset_map(uint size)
+		{
+			BLI_assert(count_bits_i(size) == 1);
+			m_map = Mapping(size);
+			m_map.fill(SLOT_EMPTY);
+			m_usable_slots = m_map.size() * LOAD_FACTOR;
+			m_slot_mask = size - 1;
+		}
+
+		inline void insert_index(const Key &key, Index index)
+		{
+			ITER_SLOTS(key, slot, state) {
+				if (state == SLOT_EMPTY) {
+					m_map[slot] = index;
+					break;
+				}
+			}
+		}
+
+		inline void first_slot(
+			const Key &key,
+			uint32_t *slot,
+			uint32_t *perturb) const
+		{
+			uint32_t hash_value = Hash{}(key);
+			*slot = hash_value & m_slot_mask;
+			*perturb = hash_value;
+		}
+
+		inline void next_slot(
+			uint32_t *slot,
+			uint32_t *perturb) const
+		{
+			*slot = m_slot_mask & ((5 + *slot) + 1 + *perturb);
+			*perturb >>= PERTURB_SHIFT;
+		}
+	};
+
+} /* namespace BLI */
+
+#undef SLOT_EMPTY
+#undef SLOT_DUMMY
+#undef LOAD_FACTOR
+#undef PERTURB_SHIFT
\ No newline at end of file
diff --git a/source/blender/blenlib/BLI_shared.hpp b/source/blender/blenlib/BLI_shared.hpp
index 5fb62635aa1..dc608eb75ca 100644
--- a/source/blender/blenlib/BLI_shared.hpp
+++ b/source/blender/blenlib/BLI_shared.hpp
@@ -143,7 +143,7 @@ namespace BLI {
 
 		friend bool operator==(const AutoRefCount &a, const AutoRefCount &b)
 		{
-			return a.m_object == b.m_object;
+			return *a.ptr() == *b.ptr();
 		}
 
 		friend bool operator!=(const AutoRefCount &a, const AutoRefCount &b)
@@ -152,4 +152,19 @@ namespace BLI {
 		}
 	};
 
-} /* namespace BLI */
\ No newline at end of file
+} /* namespace BLI */
+
+namespace std
+{
+	template<typename T>
+	struct hash<BLI::AutoRefCount<T>>
+	{
+		typedef BLI::AutoRefCount<T> argument_type;
+		typedef size_t result_type;
+
+		result_type operator()(argument_type const &v) const noexcept
+		{
+			return std::hash<T>{}(*v.ptr());
+		}
+	};
+}
\ No newline at end of file
diff --git a/source/blender/blenlib/BLI_small_map.hpp b/source/blender/blenlib/BLI_small_map.hpp
index cddf82edd26..bea14230212 100644
--- a/source/blender/blenlib/BLI_small_map.hpp
+++ b/source/blender/blenlib/BLI_small_map.hpp
@@ -1,6 +1,7 @@
 #pragma once
 
 #include "BLI_small_vector.hpp"
+#include "BLI_array_lookup.hpp"
 
 namespace BLI {
 
@@ -16,27 +17,31 @@ namespace BLI {
 				: key(key), value(value) {}
 		};
 
+		static const K &get_key_from_entry(const Entry &entry)
+		{
+			return entry.key;
+		}
+
 		SmallVector<Entry> m_entries;
+		ArrayLookup<K, Entry, get_key_from_entry> m_lookup;
 
 	public:
 		class ValueIterator;
 
 		SmallMap() = default;
 
-		void add(K key, V value)
+		void add(const K &key, const V &value)
 		{
 			BLI_assert(!this->contains(key));
-			m_entries.append(Entry(key, value));
+			uint index = m_entries.size();
+			Entry entry(key, value);
+			m_entries.append(entry);
+			m_lookup.add_new(m_entries.begin(), index);
 		}
 
-		bool contains(K key) const
+		bool contains(const K &key) const
 		{
-			for (Entry entry : m_entries) {
-				if (entry.key == key) {
-					return true;
-				}
-			}
-			return false;
+			return m_lookup.contains(m_entries.begin(), key);
 		}
 
 		V lookup(const K &key) const
@@ -63,12 +68,13 @@ namespace BLI {
 
 		V *lookup_ptr(const K &key) const
 		{
-			for (Entry &entry : m_entries) {
-				if (entry.key == key) {
-					return &entry.value;
-				}
+			int index = m_lookup.find(m_entries.begin(), key);
+			if (index >= 0) {
+				return &m_entries[index].value;
+			}
+			else {
+				return nullptr;
 			}
-			return nullptr;
 		}
 
 		uint size() const
diff --git a/source/blender/blenlib/BLI_small_set.hpp b/source/blender/blenlib/BLI_small_set.hpp
index d01d5a6f0c2..3b9a85e64e2 100644
--- a/source/blender/blenlib/BLI_small_set.hpp
+++ b/source/blender/blenlib/BLI_small_set.hpp
@@ -1,86 +1,80 @@
 #pragma once
 
 #include "BLI_small_vector.hpp"
+#include "BLI_array_lookup.hpp"
 
 namespace BLI {
 
-	template<typename T, uint N = 4>
+	template<
+		typename T,
+		uint N = 4,
+		typename Hash = std::hash<T>>
 	class SmallSet {
 	protected:
-		SmallVector<T> m_entries;
+		SmallVector<T> m_elements;
+		ArrayLookup<T> m_lookup;
 
 	public:
 		SmallSet() = default;
 
-		SmallSet(const std::initializer_list<T> &values)
+		SmallSet(const SmallVector<T> &values)
 		{
-			for (T value : values) {
+			for (const T &value : values) {
 				this->add(value);
 			}
 		}
 
-		SmallSet(const SmallVector<T> &values)
+		SmallSet (const std::initializer_list<T> &values)
 		{
-			for (T value : values) {
+			for (const T &value : values) {
 				this->add(value);
 			}
 		}
 
-		void add(T value)
+		uint size() const
 		{
-			if (!this->contains(value)) {
-				m_entries.append(value);
-			}
+			return m_elements.size();
 		}
 
-		bool contains(T value) const
+		bool contains(const T &value) const
 		{
-			for (T entry : m_entries) {
-				if (entry == value) {
-					return true;
-				}
-			}
-			return false;
+			return m_lookup.contains(m_elements.begin(), value);
 		}
 
-		uint size() const
+		void add(const T &value)
 		{
-			return m_entries.size();
+			if (!this->contains(value)) {
+				uint index = m_elements.size();
+				m_elements.append(value);
+				m_lookup.add_new(m_elements.begin(), index);
+			}
 		}
 
-		T any() const
+		T pop()
 		{
 			BLI_assert(this->size() > 0);
-			return m_entries[0];
+			T value = m_elements.pop_last();
+			uint index = m_elements.size();
+			m_lookup.remove(value, index);
+			return value;
 		}
 
-		T pop()
+		T any() const
 		{
-			return m_entries.pop_last();
+			BLI_assert(this->size() > 0);
+			return m_elements[0];
 		}
 
-
-		/* Iterators */
-
 		T *begin() const
 		{
-			return m_entries.begin();
+			return m_elements.begin();
 		}
 
 		T *end() const
 		{
-			return m_entries.end();
+			return m_elements.end();
 		}
 
-		const T *cbegin() const
-		{
-			return m_entries.cbegin();
-		}
-
-		const T *cend() const
-		{
-			return m_entries.cend();
-		}
 	};
 
 } /* namespace BLI */
\ No newline at end of file
diff --git a/source/blender/blenlib/BLI_small_set_vector.hpp b/source/blender/blenlib/BLI_small_set_vector.hpp
index 8c18c53234f..3e25e603a3f 100644
--- a/source/blender/blenlib/BLI_small_set_vector.hpp
+++ b/source/blender/blenlib/BLI_small_set_vector.hpp
@@ -19,7 +19,7 @@ namespace BLI {
 		int index(const T &value) const
 		{
 			for (uint i = 0; i < this->size(); i++) {
-				if (this->m_entries[i] == value) {
+				if (this->m_elements[i] == value) {
 					return i;
 				}
 			}
@@ -29,7 +29,7 @@ namespace BLI {
 		T operator[](const int index) const
 		{
 			BLI_assert(index >= 0 && index < this->size());
-			return this->m_entries[index];
+			return this->m_elements[index];
 		}
 	};
 
diff --git a/source/blender/blenlib/BLI_small_vector.hpp b/source/blender/blenlib/BLI_small_vector.hpp
index c5ffee5dc7a..e34cb8c4d73 100644
--- a/source/blender/blenlib/BLI_small_vector.hpp
+++ b/source/blender/blenlib/BLI_small_vector.hpp
@@ -56,9 +56,7 @@ namespace BLI {
 
 		~SmallVector()
 		{
-			if (m_elements != nullptr) {
-				this->destruct_elements_and_free_memory();
-			}
+			this->destruct_eleme

@@ Diff output truncated at 10240 characters. @@



More information about the Bf-blender-cvs mailing list