test.cpp

#include <boost/intrusive/unordered_set.hpp>
#include <chrono>
#include <random>
#include <vector>
#include <iostream>

namespace bi = boost::intrusive;

struct Billboard : public bi::unordered_set_base_hook<>
{
	bi::unordered_set_member_hook<> member_hook;

	Billboard(unsigned int tag) : tag(tag) {}

	unsigned int tag = 0;
	float x = 0.0f;
	float y = 0.0f;

	// The rest of this is boost::intrusive::unordered_set plumbing.

	friend bool operator==(const Billboard& a, const Billboard& b) {
		return a.tag == b.tag;
	}

	friend std::size_t hash_value(const Billboard& a) {
		std::hash<unsigned int> h;
		return h(a.tag);
	}

	/**
	 * A functor to find billboards by tag without constructing a billboard.
	 */
	struct Finder {
		bool operator()(unsigned int tag, const Billboard& b) const {
			return tag == b.tag;
		}

		bool operator()(const Billboard& b, unsigned int tag) const {
			return b.tag == tag;
		}
	};
};

typedef bi::unordered_set<Billboard> Billboards;
typedef Billboards::bucket_type     bucket_type;
typedef Billboards::bucket_traits   bucket_traits;

int main(int argc, char** argv)
{
	constexpr unsigned int billboardCount = 100;
	constexpr unsigned int iterationCount = 100000;
	unsigned int i;

	// Construct billboards and set tags.
	std::vector<Billboard> bs;

	for (i = 0; i < billboardCount; ++i) {
		bs.emplace_back(i);
	}

	// Build the map.  We use 100 hash buckets because that's in the
	// boost::intrusive documentation.
	bucket_type buckets[100];
	Billboards bmap(bucket_traits(buckets, 100));

	for (auto& b : bs) {
		bmap.insert(b);
	}

	// Access a random billboard and write a position to it.  Do this
	// iterationCount times.
	std::minstd_rand rand;

	// Seed value shouldn't matter for this, I hope.
	rand.seed(0);

	std::hash<unsigned int> hasher;
	std::chrono::high_resolution_clock clock;

	auto start = clock.now();

	for (i = 0; i < iterationCount; ++i) {
		auto it = bmap.find(rand() % billboardCount, hasher, Billboard::Finder());

		if (it != bmap.end()) {
			it->x = static_cast<float>(rand());
			it->y = static_cast<float>(i);
		}
	}

	auto end = clock.now();

	float total = std::accumulate(bmap.begin(), bmap.end(), 0.0f,
			[](float acc, Billboard& b) { acc += b.x; acc += b.y; return acc; });

	std::cerr << total << std::endl;
	std::cerr << "(map) " << iterationCount << " iterations: ";
	std::cerr << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count() << " us";
	std::cerr << std::endl;
	
	// ------------------------------------------------------------------
	
	// Do the same pick-one-and-write-to-it thing, but this time skip the map.
	
	start = clock.now();

	for (i = 0; i < iterationCount; ++i) {
		auto& billboard = bs[rand() % billboardCount];

		billboard.x = static_cast<float>(rand());
		billboard.y = static_cast<float>(i);
	}

	end = clock.now();

	total = std::accumulate(bmap.begin(), bmap.end(), 0.0f,
			[](float acc, Billboard& b) { acc += b.x; acc += b.y; return acc; });

	std::cerr << total << std::endl;
	std::cerr << "(vector) " << iterationCount << " iterations: ";
	std::cerr << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count() << " us";
	std::cerr << std::endl;

	return 0;
}

So if you throw 10000 elements into a hash table with 100 buckets, performance goes to hell at all optimization levels. This makes sense, and makes boost::intrusive::unordered_set slightly less attractive of an option because if I use it I'll have to handle rehashing myself.