benchmark iterating over set bits in a uint32_t

gistfile1.cpp

#include <cinttypes>
#include <cstdlib>
#include <ctime>
#include <iostream>


int main(int argc, char** args) {
	
	srand(time(NULL));
	const int NUM_LOOPS = rand() & 0xffff;
	std::cout << "testing with " << NUM_LOOPS << " loops" << std::endl;
	
	// make some test data
	uint32_t test_data[1000];
	for(auto &mask: test_data)
		mask = rand();

	// test simple loop
	auto start_time = clock();
	uint32_t check = 0;
	for(auto loop=NUM_LOOPS; loop-- > 0; ) {
		for(auto mask: test_data) {
			for(auto i=0; i<32; i++) {
				if(mask & (1U << i)) {
					// payload
					check += i;
				}
			}
		}
	}
	std::cout << check << " loop (simple) took " << ((float)(clock() - start_time) / CLOCKS_PER_SEC) << "s" << std::endl;

	// test early-out loop
	start_time = clock();
	check = 0;
	for(auto loop=NUM_LOOPS; loop-- > 0; ) {
		for(auto mask: test_data) {
			for(uint32_t i=0, m=mask; m; i++, m>>=1) {
				if(m & 1) {
					// payload
					check += i;
				}
			}
		}
	}
	std::cout << check << " loop (early out) took " << ((float)(clock() - start_time) / CLOCKS_PER_SEC) << "s" << std::endl;

	// test ffs
	start_time = clock();
	check = 0;
	for(auto loop=NUM_LOOPS; loop-- > 0; ) {
		for(auto mask: test_data) {
			for(uint32_t m = mask, i = ~0U; m; ) {
				auto shift = __builtin_ffs(m);
				m >>= shift;
				i += shift;
				// payload
				check += i;
			}
		}
	}
	std::cout << check << " ffs took " << ((float)(clock() - start_time) / CLOCKS_PER_SEC) << "s" << std::endl;
	
	return 0;
}