C++ dynamic_bitset 구현

게임 엔진에서 기존에 사용하던 boost::dynamic_bitset을 직접 구현해보기로 했다.
인터페이스를 기존의 것을 그대로 사용했다.

최대한 std::bitset을 활용하는 방향으로 생각했고, +1 사이즈씩 증가하는 동적배열과 정해진 offset만큼을 늘려나가는 std::vector 중 고민을 하다가 std::vector를 통한 구현을 생각했다.

class dynamic_bitset
{
public:
	static constexpr std::size_t bit_size = 64;
	static constexpr std::size_t npos = SIZE_MAX;

	using bitset = std::bitset<bit_size>;
		 
	dynamic_bitset();
	~dynamic_bitset() = default;
	dynamic_bitset(const dynamic_bitset&) = default;
	dynamic_bitset& operator=(const dynamic_bitset&) = default;
	bool operator==(const dynamic_bitset&) const;

	void set(std::size_t pos);
	void reset(std::size_t pos);
	bool get(std::size_t pos) const;
	std::size_t size() const noexcept;
	void clear();
	void resize(std::size_t size);
	bool empty() const noexcept;
	std::string to_string() const noexcept;

	bool is_proper_subset_of(const dynamic_bitset& bitset) const;
	std::size_t find_first() const noexcept;
	std::size_t find_next(std::size_t pos) const noexcept;

private:
	std::size_t numbits;
	std::vector<bitset> bitArray;
	std::size_t find_from(std::size_t pos) const noexcept;
};

엔진 내부적으로 Component ID가 비트셋의 인덱스로 처리되는데 is_subset_of을 통해 포함관계인지 아닌지를 구별한다.

bitset A :      0010 0101 1111
bitset B : 0000 0010 0101 1111
B.is_subset_of(A) // true!!

위와 같은 상황에서도 B는 A에 포함된다. 그래서 어떤 방식으로 처리할 수 있을까 고민하다가 만약 호출하는 비트셋이 비교 대상보다 사이즈가 클 경우에 큰 부분에 1이 하나라도 있다면 false를 리턴하도록 했다.

bool se::dynamic_bitset::is_subset_of(const dynamic_bitset& other) const
{
	if (bitArray.size() > other.bitArray.size())
	{
		for (int i = other.bitArray.size(); i < bitArray.size(); i++)
		{
			if (bitArray[i].any())
			{
				return false;
			}
		}
	}
	else
	{
		for (int i = 0; i < bitArray.size(); i++)
		{
        		//비트연산을 통해 다른 부분이 있으면 return false
			if ((bitArray[i] & other.bitArray[i]) != bitArray[i])
			{
				return false;
			}
		}
	}
	return true;
}

boost에서는 is_proper_subset_of 라는 진부분집합을 검사하는 함수도 제공하고 있어 is_same함수를 만들어 is_proper_subset_of와 ==연산자에 활용했다.

bool se::dynamic_bitset::is_same(const dynamic_bitset& other) const
{
	const auto& big = (bitArray.size() <= other.bitArray.size()) ? other.bitArray : bitArray;
	const auto& small = (bitArray.size() > other.bitArray.size()) ? other.bitArray : bitArray;

	for (int i = small.size(); i < big.size(); i++)
	{
		if (big[i].any())
			return false;
	}

	if (std::equal(small.cbegin(), small.cend(), big.cbegin()))
	{
		return true;
	}
	else
	{
		return false;
	}
}

bool se::dynamic_bitset::is_proper_subset_of(const dynamic_bitset& other) const
{
	//같은 경우는 false
	if (is_same(other))
		return false;

	return is_subset_of(other);
}

bool se::dynamic_bitset::operator==(const dynamic_bitset& other) const
{
	return is_same(other);
}

엔진 0.1 버전, 엔티티 1000만개 기준 벤치마크에서 각각 10번씩 돌려보았다.
시간측정 결과
boost::dynamic_bitset : 0.0385~0.0391 초
se::dynamic_bitset :: 0.385~0.0394 초
boost의 dynamic_bitset이 성능 이슈가 있다고 들어 구현했는데 거의 똑같은 성능을 보인다.
아직 최적화가 잘 이루어지지 않은 부분이 있나 생각이 들어 추후 개선할 예정이다.