More hashtable finetuning

4 files changed, 34 insertions, 12 deletions

diff --git a/kernel/hashmap.h b/kernel/hashmap.h
index 91df68a71..729b4916c 100644
--- a/kernel/hashmap.h
+++ b/kernel/hashmap.h
@@ -23,6 +23,8 @@
 #include <string>
 #include <vector>
 
+#define YOSYS_HASHTABLE_SIZE_FACTOR 3
+
 inline unsigned int mkhash(unsigned int a, unsigned int b) {
 	return ((a << 5) + a) ^ b;
 }
@@ -81,8 +83,19 @@ struct hash_ptr_ops {
 	}
 };
 
+struct hash_obj_ops {
+	bool cmp(const void *a, const void *b) const {
+		return a == b;
+	}
+	template<typename T>
+	unsigned int hash(const T *a) const {
+		return a->name.hash();
+	}
+};
+
 inline int hashtable_size(int old_size)
 {
+	// prime numbers, approx. in powers of two
 	if (old_size <         53) return         53;
 	if (old_size <        113) return        113;
 	if (old_size <        251) return        251;
@@ -144,7 +157,9 @@ class dict
 		entries.clear();
 
 		counter = other.size();
-		int new_size = hashtable_size(counter);
+		int new_size = hashtable_size(YOSYS_HASHTABLE_SIZE_FACTOR * counter);
+		hashtable.resize(new_size);
+		new_size = new_size / YOSYS_HASHTABLE_SIZE_FACTOR + 1;
 		entries.reserve(new_size);
 
 		for (auto &it : other)
@@ -165,7 +180,6 @@ class dict
 	{
 		free_list = -1;
 
-		hashtable.resize(entries.size());
 		for (auto &h : hashtable)
 			h = -1;
 
@@ -221,7 +235,9 @@ class dict
 		if (free_list < 0)
 		{
 			int i = entries.size();
-			entries.resize(hashtable_size(i));
+			int new_size = hashtable_size(YOSYS_HASHTABLE_SIZE_FACTOR * entries.size());
+			hashtable.resize(new_size);
+			entries.resize(new_size / YOSYS_HASHTABLE_SIZE_FACTOR + 1);
 			entries[i].udata = value;
 			entries[i].set_next_used(0);
 			counter++;
@@ -473,7 +489,9 @@ class pool
 		entries.clear();
 
 		counter = other.size();
-		int new_size = hashtable_size(counter);
+		int new_size = hashtable_size(YOSYS_HASHTABLE_SIZE_FACTOR * counter);
+		hashtable.resize(new_size);
+		new_size = new_size / YOSYS_HASHTABLE_SIZE_FACTOR + 1;
 		entries.reserve(new_size);
 
 		for (auto &it : other)
@@ -494,7 +512,6 @@ class pool
 	{
 		free_list = -1;
 
-		hashtable.resize(entries.size());
 		for (auto &h : hashtable)
 			h = -1;
 
@@ -550,7 +567,9 @@ class pool
 		if (free_list < 0)
 		{
 			int i = entries.size();
-			entries.resize(hashtable_size(i));
+			int new_size = hashtable_size(YOSYS_HASHTABLE_SIZE_FACTOR * entries.size());
+			hashtable.resize(new_size);
+			entries.resize(new_size / YOSYS_HASHTABLE_SIZE_FACTOR + 1);
 			entries[i].key = key;
 			entries[i].set_next_used(0);
 			counter++;
diff --git a/kernel/rtlil.cc b/kernel/rtlil.cc
index 8f65f5273..0114cbd60 100644
--- a/kernel/rtlil.cc
+++ b/kernel/rtlil.cc
@@ -1132,7 +1132,7 @@ namespace {
 	struct DeleteWireWorker
 	{
 		RTLIL::Module *module;
-		const pool<RTLIL::Wire*, hash_ptr_ops> *wires_p;
+		const pool<RTLIL::Wire*, hash_obj_ops> *wires_p;
 
 		void operator()(RTLIL::SigSpec &sig) {
 			std::vector<RTLIL::SigChunk> chunks = sig;
@@ -1146,7 +1146,7 @@ namespace {
 	};
 }
 
-void RTLIL::Module::remove(const pool<RTLIL::Wire*, hash_ptr_ops> &wires)
+void RTLIL::Module::remove(const pool<RTLIL::Wire*, hash_obj_ops> &wires)
 {
 	log_assert(refcount_wires_ == 0);
 
diff --git a/kernel/rtlil.h b/kernel/rtlil.h
index ae37c350c..c50a58619 100644
--- a/kernel/rtlil.h
+++ b/kernel/rtlil.h
@@ -708,6 +708,8 @@ struct RTLIL::Selection
 
 struct RTLIL::Monitor
 {
+	RTLIL::IdString name;
+	Monitor() { name = stringf("$%d", autoidx++); }
 	virtual ~Monitor() { }
 	virtual void notify_module_add(RTLIL::Module*) { }
 	virtual void notify_module_del(RTLIL::Module*) { }
@@ -719,7 +721,7 @@ struct RTLIL::Monitor
 
 struct RTLIL::Design
 {
-	pool<RTLIL::Monitor*, hash_ptr_ops> monitors;
+	pool<RTLIL::Monitor*, hash_obj_ops> monitors;
 	dict<std::string, std::string> scratchpad;
 
 	int refcount_modules_;
@@ -806,7 +808,7 @@ protected:
 
 public:
 	RTLIL::Design *design;
-	pool<RTLIL::Monitor*, hash_ptr_ops> monitors;
+	pool<RTLIL::Monitor*, hash_obj_ops> monitors;
 
 	int refcount_wires_;
 	int refcount_cells_;
@@ -860,7 +862,7 @@ public:
 	RTLIL::ObjRange<RTLIL::Cell*> cells() { return RTLIL::ObjRange<RTLIL::Cell*>(&cells_, &refcount_cells_); }
 
 	// Removing wires is expensive. If you have to remove wires, remove them all at once.
-	void remove(const pool<RTLIL::Wire*, hash_ptr_ops> &wires);
+	void remove(const pool<RTLIL::Wire*, hash_obj_ops> &wires);
 	void remove(RTLIL::Cell *cell);
 
 	void rename(RTLIL::Wire *wire, RTLIL::IdString new_name);
diff --git a/kernel/yosys.h b/kernel/yosys.h
index 012b40c1f..d47f3a958 100644
--- a/kernel/yosys.h
+++ b/kernel/yosys.h
@@ -149,6 +149,8 @@ void remove_directory(std::string dirname);
 template<typename T> int GetSize(const T &obj) { return obj.size(); }
 int GetSize(RTLIL::Wire *wire);
 
+extern int autoidx;
+
 YOSYS_NAMESPACE_END
 
 #include "kernel/log.h"
@@ -164,7 +166,6 @@ void yosys_shutdown();
 Tcl_Interp *yosys_get_tcl_interp();
 #endif
 
-extern int autoidx;
 extern RTLIL::Design *yosys_design;
 
 RTLIL::IdString new_id(std::string file, int line, std::string func);