According to the standard, the swap method of unorder

Ok, it's my fault. I'm not noticed that you have a Table&amp

Hi <a class="user-mention notranslate" data-hovercard-type="user" data-hovercard-url="

Complexity of the swap method about robin-hood-hashing HOT 2 CLOSED

asbai commented on May 20, 2024

Complexity of the swap method

from robin-hood-hashing.

Comments (2)

asbai commented on May 20, 2024 1

Ok, it's my fault. I'm not noticed that you have a Table& operator=(Table&& o) method, sorry~

I've only seen the Table& operator=(Table const& o) one what is immediately above the swap method :-)

from robin-hood-hashing.

martinus commented on May 20, 2024

Hi @asbai, the swap already is O(1). I took your issue as an opportunity to demonstrate this with nanobench. I've added a benchmark that calculates complexity of swap:

robin-hood-hashing/src/test/unit/bench_swap.cpp

Lines 18 to 27 in f577ca9

 ankerl::nanobench::Bench bench; 

 for (size_t i = 0; i < 10; ++i) { 

 for (size_t j = 0; j < 10U * (1U << i); ++j) { 

 a[rng()]; 

 b[rng()]; 

 } 

 bench.complexityN(a.size()).run("swap " + type_string(a), [&] { std::swap(a, b); }); 

 } 

 ankerl::nanobench::doNotOptimizeAway(a, b); 

 std::cout << bench.complexityBigO() << std::endl;

This benchmarks swap() with differently sized maps. It can be clearly seen that swap performance is always constant at 11.27 ns/op:

complexityN	ns/op	op/s	err%	ins/op	cyc/op	IPC	benchmark
10	11.27	88,736,885.89	0.0%	63.01	35.98	1.751	`swap <robin_hood::unordered_flat_map<uint64_t, uint64_t>>`
30	11.27	88,728,648.87	0.0%	63.01	36.01	1.750	`swap <robin_hood::unordered_flat_map<uint64_t, uint64_t>>`
70	11.28	88,658,752.21	0.1%	63.01	36.02	1.749	`swap <robin_hood::unordered_flat_map<uint64_t, uint64_t>>`
150	11.29	88,580,392.83	0.1%	63.01	36.06	1.747	`swap <robin_hood::unordered_flat_map<uint64_t, uint64_t>>`
310	11.29	88,578,516.95	0.1%	63.01	36.05	1.748	`swap <robin_hood::unordered_flat_map<uint64_t, uint64_t>>`
630	11.27	88,723,132.79	0.0%	63.01	36.00	1.750	`swap <robin_hood::unordered_flat_map<uint64_t, uint64_t>>`
1,270	11.27	88,731,841.38	0.0%	63.01	36.00	1.750	`swap <robin_hood::unordered_flat_map<uint64_t, uint64_t>>`
2,550	11.27	88,734,786.30	0.0%	63.01	36.01	1.750	`swap <robin_hood::unordered_flat_map<uint64_t, uint64_t>>`
5,110	11.27	88,736,885.89	0.0%	63.01	35.99	1.751	`swap <robin_hood::unordered_flat_map<uint64_t, uint64_t>>`
10,230	11.27	88,735,566.10	0.0%	63.01	35.99	1.751	`swap <robin_hood::unordered_flat_map<uint64_t, uint64_t>>`

Additionally, this data can be used to fit different complexity curves to the data. Unsurprisingly, the best fitting curve with an error of only 0.1% is O(1):

coefficient	err%	complexity
1.12747e-08	0.1%	O(1)
1.15522e-09	33.8%	O(log n)
1.64601e-12	83.8%	O(n)
1.20108e-13	85.6%	O(n log n)
1.34512e-16	91.3%	O(n^2)
1.18374e-20	93.4%	O(n^3)

So no need to worry, swap already is O(1).

from robin-hood-hashing.

Recommend Projects

Complexity of the swap method about robin-hood-hashing HOT 2 CLOSED

Comments (2)

Related Issues (20)

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent

	ankerl::nanobench::Bench bench;
	for (size_t i = 0; i < 10; ++i) {
	for (size_t j = 0; j < 10U * (1U << i); ++j) {
	a[rng()];
	b[rng()];
	}
	bench.complexityN(a.size()).run("swap " + type_string(a), [&] { std::swap(a, b); });
	}
	ankerl::nanobench::doNotOptimizeAway(a, b);
	std::cout << bench.complexityBigO() << std::endl;