Integrate Hashtable into Multicaster, where @mwarning found heaviest std::map() overhead.

5 files changed, 117 insertions, 57 deletions

diff --git a/node/Hashtable.hpp b/node/Hashtable.hpp
index bba1fa2b..c997d54f 100644
--- a/node/Hashtable.hpp
+++ b/node/Hashtable.hpp
@@ -19,7 +19,6 @@
  *
  * ZeroTier may be used and distributed under the terms of the GPLv3, which
  * are available at: http://www.gnu.org/licenses/gpl-3.0.html
- *
  */
 
 #ifndef ZT_HASHTABLE_HPP
@@ -39,9 +38,6 @@ namespace ZeroTier {
  * This is not a drop-in replacement for STL containers, and has several
  * limitations. It's designed to be small and fast for use in the
  * ZeroTier core.
- *
- * Pairs of values can also be used as a key. In this case the first and
- * second element of the pair's hash codes are XORed.
  */
 template<typename K,typename V>
 class Hashtable
@@ -49,12 +45,11 @@ class Hashtable
 private:
 	struct _Bucket
 	{
-		_Bucket(const K &k,const V &v) :
-			k(k),
-			v(v) {}
-		_Bucket *next;
+		_Bucket(const K &k,const V &v) : k(k),v(v) {}
+		_Bucket(const K &k) : k(k),v() {}
 		K k;
 		V v;
+		_Bucket *next;
 	};
 
 public:
@@ -188,35 +183,56 @@ public:
 	/**
 	 * @param k Key
 	 * @param v Value
+	 * @return Reference to value in table
 	 */
-	inline void set(const K &k,const V &v)
+	inline V &set(const K &k,const V &v)
 	{
-		if (_s >= _bc) {
-			const unsigned long nc = _bc * 2;
-			_Bucket **nt = reinterpret_cast<_Bucket **>(::malloc(sizeof(_Bucket *) * nc));
-			if (nt) {
-				for(unsigned long i=0;i<nc;++i)
-					nt[i] = (_Bucket *)0;
-				for(unsigned long i=0;i<_bc;++i) {
-					_Bucket *b = _t[i];
-					while (b) {
-						_Bucket *const nb = b->next;
-						const unsigned long nidx = _hc(b->k) % nc;
-						b->next = nt[nidx];
-						nt[nidx] = b;
-						b = nb;
-					}
-				}
-				::free(_t);
-				_t = nt;
-				_bc = nc;
+		const unsigned long bidx = _hc(k) % _bc;
+
+		_Bucket *b = _t[bidx];
+		while (b) {
+			if (b->k == k) {
+				b->v = v;
+				return b->v;
 			}
+			b = b->next;
 		}
+
+		if (_s >= _bc)
+			_grow();
+
+		b = new _Bucket(k,v);
+		b->next = _t[bidx];
+		_t[bidx] = b;
+		++_s;
+
+		return b->v;
+	}
+
+	/**
+	 * @param k Key
+	 * @return Value, possibly newly created
+	 */
+	inline V &operator[](const K &k)
+	{
 		const unsigned long bidx = _hc(k) % _bc;
-		_Bucket *const b = new _Bucket(k,v);
+
+		_Bucket *b = _t[bidx];
+		while (b) {
+			if (b->k == k)
+				return b->v;
+			b = b->next;
+		}
+
+		if (_s >= _bc)
+			_grow();
+
+		b = new _Bucket(k);
 		b->next = _t[bidx];
 		_t[bidx] = b;
 		++_s;
+
+		return b->v;
 	}
 
 	/**
@@ -242,6 +258,29 @@ private:
 		return (unsigned long)((i ^ (i >> 32)) * 2654435761ULL);
 	}
 
+	inline void _grow()
+	{
+		const unsigned long nc = _bc * 2;
+		_Bucket **nt = reinterpret_cast<_Bucket **>(::malloc(sizeof(_Bucket *) * nc));
+		if (nt) {
+			for(unsigned long i=0;i<nc;++i)
+				nt[i] = (_Bucket *)0;
+			for(unsigned long i=0;i<_bc;++i) {
+				_Bucket *b = _t[i];
+				while (b) {
+					_Bucket *const nb = b->next;
+					const unsigned long nidx = _hc(b->k) % nc;
+					b->next = nt[nidx];
+					nt[nidx] = b;
+					b = nb;
+				}
+			}
+			::free(_t);
+			_t = nt;
+			_bc = nc;
+		}
+	}
+
 	_Bucket **_t;
 	unsigned long _bc;
 	unsigned long _s;
diff --git a/node/MAC.hpp b/node/MAC.hpp
index 442a7a2e..619b7195 100644
--- a/node/MAC.hpp
+++ b/node/MAC.hpp
@@ -242,6 +242,8 @@ public:
 	 */
 	inline unsigned int size() const throw() { return 6; }
 
+	inline unsigned long hashCode() const throw() { return (unsigned long)_m; }
+
 	inline MAC &operator=(const MAC &m)
 		throw()
 	{
diff --git a/node/MulticastGroup.hpp b/node/MulticastGroup.hpp
index 61fb55f2..fad433b5 100644
--- a/node/MulticastGroup.hpp
+++ b/node/MulticastGroup.hpp
@@ -141,6 +141,8 @@ public:
 	 */
 	inline uint32_t adi() const throw() { return _adi; }
 
+	inline unsigned long hashCode() const throw() { return (_mac.hashCode() ^ (unsigned long)_adi); }
+
 	inline bool operator==(const MulticastGroup &g) const throw() { return ((_mac == g._mac)&&(_adi == g._adi)); }
 	inline bool operator!=(const MulticastGroup &g) const throw() { return ((_mac != g._mac)||(_adi != g._adi)); }
 	inline bool operator<(const MulticastGroup &g) const throw()
diff --git a/node/Multicaster.cpp b/node/Multicaster.cpp
index 489c170b..07792737 100644
--- a/node/Multicaster.cpp
+++ b/node/Multicaster.cpp
@@ -41,7 +41,9 @@
 namespace ZeroTier {
 
 Multicaster::Multicaster(const RuntimeEnvironment *renv) :
-	RR(renv)
+	RR(renv),
+	_groups(1024),
+	_groups_m()
 {
 }
 
@@ -54,7 +56,7 @@ void Multicaster::addMultiple(uint64_t now,uint64_t nwid,const MulticastGroup &m
 	const unsigned char *p = (const unsigned char *)addresses;
 	const unsigned char *e = p + (5 * count);
 	Mutex::Lock _l(_groups_m);
-	MulticastGroupStatus &gs = _groups[std::pair<uint64_t,MulticastGroup>(nwid,mg)];
+	MulticastGroupStatus &gs = _groups[Multicaster::Key(nwid,mg)];
 	while (p != e) {
 		_add(now,nwid,mg,gs,Address(p,5));
 		p += 5;
@@ -64,11 +66,11 @@ void Multicaster::addMultiple(uint64_t now,uint64_t nwid,const MulticastGroup &m
 void Multicaster::remove(uint64_t nwid,const MulticastGroup &mg,const Address &member)
 {
 	Mutex::Lock _l(_groups_m);
-	std::map< std::pair<uint64_t,MulticastGroup>,MulticastGroupStatus >::iterator g(_groups.find(std::pair<uint64_t,MulticastGroup>(nwid,mg)));
-	if (g != _groups.end()) {
-		for(std::vector<MulticastGroupMember>::iterator m(g->second.members.begin());m!=g->second.members.end();++m) {
+	MulticastGroupStatus *s = _groups.get(Multicaster::Key(nwid,mg));
+	if (s) {
+		for(std::vector<MulticastGroupMember>::iterator m(s->members.begin());m!=s->members.end();++m) {
 			if (m->address == member) {
-				g->second.members.erase(m);
+				s->members.erase(m);
 				break;
 			}
 		}
@@ -102,18 +104,18 @@ unsigned int Multicaster::gather(const Address &queryingPeer,uint64_t nwid,const
 
 	Mutex::Lock _l(_groups_m);
 
-	std::map< std::pair<uint64_t,MulticastGroup>,MulticastGroupStatus >::const_iterator gs(_groups.find(std::pair<uint64_t,MulticastGroup>(nwid,mg)));
-	if ((gs != _groups.end())&&(!gs->second.members.empty())) {
-		totalKnown += (unsigned int)gs->second.members.size();
+	const MulticastGroupStatus *s = _groups.get(Multicaster::Key(nwid,mg));
+	if ((s)&&(!s->members.empty())) {
+		totalKnown += (unsigned int)s->members.size();
 
 		// Members are returned in random order so that repeated gather queries
 		// will return different subsets of a large multicast group.
 		k = 0;
-		while ((added < limit)&&(k < gs->second.members.size())&&((appendTo.size() + ZT_ADDRESS_LENGTH) <= ZT_UDP_DEFAULT_PAYLOAD_MTU)) {
+		while ((added < limit)&&(k < s->members.size())&&((appendTo.size() + ZT_ADDRESS_LENGTH) <= ZT_UDP_DEFAULT_PAYLOAD_MTU)) {
 			rptr = (unsigned int)RR->node->prng();
 
 restart_member_scan:
-			a = gs->second.members[rptr % (unsigned int)gs->second.members.size()].address.toInt();
+			a = s->members[rptr % (unsigned int)s->members.size()].address.toInt();
 			for(i=0;i<k;++i) {
 				if (picked[i] == a) {
 					++rptr;
@@ -146,10 +148,10 @@ std::vector<Address> Multicaster::getMembers(uint64_t nwid,const MulticastGroup
 {
 	std::vector<Address> ls;
 	Mutex::Lock _l(_groups_m);
-	std::map< std::pair<uint64_t,MulticastGroup>,MulticastGroupStatus >::const_iterator gs(_groups.find(std::pair<uint64_t,MulticastGroup>(nwid,mg)));
-	if (gs == _groups.end())
+	const MulticastGroupStatus *s = _groups.get(Multicaster::Key(nwid,mg));
+	if (!s)
 		return ls;
-	for(std::vector<MulticastGroupMember>::const_reverse_iterator m(gs->second.members.rbegin());m!=gs->second.members.rend();++m) {
+	for(std::vector<MulticastGroupMember>::const_reverse_iterator m(s->members.rbegin());m!=s->members.rend();++m) {
 		ls.push_back(m->address);
 		if (ls.size() >= limit)
 			break;
@@ -173,7 +175,7 @@ void Multicaster::send(
 	unsigned long *indexes = idxbuf;
 
 	Mutex::Lock _l(_groups_m);
-	MulticastGroupStatus &gs = _groups[std::pair<uint64_t,MulticastGroup>(nwid,mg)];
+	MulticastGroupStatus &gs = _groups[Multicaster::Key(nwid,mg)];
 
 	if (!gs.members.empty()) {
 		// Allocate a memory buffer if group is monstrous
@@ -291,18 +293,22 @@ void Multicaster::send(
 void Multicaster::clean(uint64_t now)
 {
 	Mutex::Lock _l(_groups_m);
-	for(std::map< std::pair<uint64_t,MulticastGroup>,MulticastGroupStatus >::iterator mm(_groups.begin());mm!=_groups.end();) {
-		for(std::list<OutboundMulticast>::iterator tx(mm->second.txQueue.begin());tx!=mm->second.txQueue.end();) {
+
+	Multicaster::Key *k = (Multicaster::Key *)0;
+	MulticastGroupStatus *s = (MulticastGroupStatus *)0;
+	Hashtable<Multicaster::Key,MulticastGroupStatus>::Iterator mm(_groups);
+	while (mm.next(k,s)) {
+		for(std::list<OutboundMulticast>::iterator tx(s->txQueue.begin());tx!=s->txQueue.end();) {
 			if ((tx->expired(now))||(tx->atLimit()))
-				mm->second.txQueue.erase(tx++);
+				s->txQueue.erase(tx++);
 			else ++tx;
 		}
 
 		unsigned long count = 0;
 		{
-			std::vector<MulticastGroupMember>::iterator reader(mm->second.members.begin());
+			std::vector<MulticastGroupMember>::iterator reader(s->members.begin());
 			std::vector<MulticastGroupMember>::iterator writer(reader);
-			while (reader != mm->second.members.end()) {
+			while (reader != s->members.end()) {
 				if ((now - reader->timestamp) < ZT_MULTICAST_LIKE_EXPIRE) {
 					*writer = *reader;
 					++writer;
@@ -313,13 +319,11 @@ void Multicaster::clean(uint64_t now)
 		}
 
 		if (count) {
-			mm->second.members.resize(count);
-			++mm;
-		} else if (mm->second.txQueue.empty()) {
-			_groups.erase(mm++);
+			s->members.resize(count);
+		} else if (s->txQueue.empty()) {
+			_groups.erase(*k);
 		} else {
-			mm->second.members.clear();
-			++mm;
+			s->members.clear();
 		}
 	}
 }
diff --git a/node/Multicaster.hpp b/node/Multicaster.hpp
index 0dd199f9..898c4db7 100644
--- a/node/Multicaster.hpp
+++ b/node/Multicaster.hpp
@@ -36,6 +36,7 @@
 #include <list>
 
 #include "Constants.hpp"
+#include "Hashtable.hpp"
 #include "Address.hpp"
 #include "MAC.hpp"
 #include "MulticastGroup.hpp"
@@ -56,6 +57,18 @@ class Packet;
 class Multicaster : NonCopyable
 {
 private:
+	struct Key
+	{
+		Key() : nwid(0),mg() {}
+		Key(uint64_t n,const MulticastGroup &g) : nwid(n),mg(g) {}
+
+		uint64_t nwid;
+		MulticastGroup mg;
+
+		inline bool operator==(const Key &k) const throw() { return ((nwid == k.nwid)&&(mg == k.mg)); }
+		inline unsigned long hashCode() const throw() { return (mg.hashCode() ^ (unsigned long)(nwid ^ (nwid >> 32))); }
+	};
+
 	struct MulticastGroupMember
 	{
 		MulticastGroupMember() {}
@@ -89,7 +102,7 @@ public:
 	inline void add(uint64_t now,uint64_t nwid,const MulticastGroup &mg,const Address &member)
 	{
 		Mutex::Lock _l(_groups_m);
-		_add(now,nwid,mg,_groups[std::pair<uint64_t,MulticastGroup>(nwid,mg)],member);
+		_add(now,nwid,mg,_groups[Multicaster::Key(nwid,mg)],member);
 	}
 
 	/**
@@ -181,7 +194,7 @@ private:
 	void _add(uint64_t now,uint64_t nwid,const MulticastGroup &mg,MulticastGroupStatus &gs,const Address &member);
 
 	const RuntimeEnvironment *RR;
-	std::map< std::pair<uint64_t,MulticastGroup>,MulticastGroupStatus > _groups;
+	Hashtable<Multicaster::Key,MulticastGroupStatus> _groups;
 	Mutex _groups_m;
 };