From d8678e02ecec9375bec1dcf1388c6fc8b4ce3ad2 Mon Sep 17 00:00:00 2001 From: Jacques Lucke Date: Tue, 9 Jun 2020 10:10:56 +0200 Subject: BLI: generally improve C++ data structures The main focus here was to improve the docs significantly. Furthermore, I reimplemented `Set`, `Map` and `VectorSet`. They are now (usually) faster, simpler and more customizable. I also rewrote `Stack` to make it more efficient by avoiding unnecessary copies. Thanks to everyone who helped with constructive feedback. Approved by brecht and sybren. Differential Revision: https://developer.blender.org/D7931 --- tests/gtests/blenlib/BLI_map_test.cc | 261 ++++++++++++++++++++++++++++++----- 1 file changed, 224 insertions(+), 37 deletions(-) (limited to 'tests/gtests/blenlib/BLI_map_test.cc') diff --git a/tests/gtests/blenlib/BLI_map_test.cc b/tests/gtests/blenlib/BLI_map_test.cc index 5a19216fa7c..990683dcfc5 100644 --- a/tests/gtests/blenlib/BLI_map_test.cc +++ b/tests/gtests/blenlib/BLI_map_test.cc @@ -1,20 +1,23 @@ #include "BLI_map.hh" +#include "BLI_rand.h" #include "BLI_set.hh" +#include "BLI_strict_flags.h" +#include "BLI_timeit.hh" +#include "BLI_vector.hh" #include "testing/testing.h" -using BLI::Map; -using IntFloatMap = Map; +using namespace BLI; TEST(map, DefaultConstructor) { - IntFloatMap map; + Map map; EXPECT_EQ(map.size(), 0); EXPECT_TRUE(map.is_empty()); } TEST(map, AddIncreasesSize) { - IntFloatMap map; + Map map; EXPECT_EQ(map.size(), 0); EXPECT_TRUE(map.is_empty()); map.add(2, 5.0f); @@ -27,7 +30,7 @@ TEST(map, AddIncreasesSize) TEST(map, Contains) { - IntFloatMap map; + Map map; EXPECT_FALSE(map.contains(4)); map.add(5, 6.0f); EXPECT_FALSE(map.contains(4)); @@ -37,7 +40,7 @@ TEST(map, Contains) TEST(map, LookupExisting) { - IntFloatMap map; + Map map; map.add(2, 6.0f); map.add(4, 1.0f); EXPECT_EQ(map.lookup(2), 6.0f); @@ -46,7 +49,7 @@ TEST(map, LookupExisting) TEST(map, LookupNotExisting) { - IntFloatMap map; + Map map; map.add(2, 4.0f); map.add(1, 1.0f); EXPECT_EQ(map.lookup_ptr(0), nullptr); @@ -55,15 +58,16 @@ TEST(map, LookupNotExisting) TEST(map, AddMany) { - IntFloatMap map; + Map map; for (int i = 0; i < 100; i++) { - map.add(i, i); + map.add(i * 30, i); + map.add(i * 31, i); } } TEST(map, PopItem) { - IntFloatMap map; + Map map; map.add(2, 3.0f); map.add(1, 9.0f); EXPECT_TRUE(map.contains(2)); @@ -80,21 +84,21 @@ TEST(map, PopItem) TEST(map, PopItemMany) { - IntFloatMap map; - for (uint i = 0; i < 100; i++) { + Map map; + for (int i = 0; i < 100; i++) { map.add_new(i, i); } - for (uint i = 25; i < 80; i++) { + for (int i = 25; i < 80; i++) { EXPECT_EQ(map.pop(i), i); } - for (uint i = 0; i < 100; i++) { + for (int i = 0; i < 100; i++) { EXPECT_EQ(map.contains(i), i < 25 || i >= 80); } } TEST(map, ValueIterator) { - IntFloatMap map; + Map map; map.add(3, 5.0f); map.add(1, 2.0f); map.add(7, -2.0f); @@ -115,7 +119,7 @@ TEST(map, ValueIterator) TEST(map, KeyIterator) { - IntFloatMap map; + Map map; map.add(6, 3.0f); map.add(2, 4.0f); map.add(1, 3.0f); @@ -136,7 +140,7 @@ TEST(map, KeyIterator) TEST(map, ItemIterator) { - IntFloatMap map; + Map map; map.add(5, 3.0f); map.add(2, 9.0f); map.add(1, 0.0f); @@ -160,6 +164,34 @@ TEST(map, ItemIterator) EXPECT_TRUE(values.contains(0.0f)); } +TEST(map, MutableValueIterator) +{ + Map map; + map.add(3, 6); + map.add(2, 1); + + for (int &value : map.values()) { + value += 10; + } + + EXPECT_EQ(map.lookup(3), 16); + EXPECT_EQ(map.lookup(2), 11); +} + +TEST(map, MutableItemIterator) +{ + Map map; + map.add(3, 6); + map.add(2, 1); + + for (auto item : map.items()) { + item.value += item.key; + } + + EXPECT_EQ(map.lookup(3), 9.0f); + EXPECT_EQ(map.lookup(2), 3.0f); +} + static float return_42() { return 42.0f; @@ -167,14 +199,16 @@ static float return_42() TEST(map, LookupOrAdd_SeparateFunction) { - IntFloatMap map; + Map map; EXPECT_EQ(map.lookup_or_add(0, return_42), 42.0f); EXPECT_EQ(map.lookup(0), 42); + + map.keys(); } TEST(map, LookupOrAdd_Lambdas) { - IntFloatMap map; + Map map; auto lambda1 = []() { return 11.0f; }; EXPECT_EQ(map.lookup_or_add(0, lambda1), 11.0f); auto lambda2 = []() { return 20.0f; }; @@ -186,7 +220,7 @@ TEST(map, LookupOrAdd_Lambdas) TEST(map, AddOrModify) { - IntFloatMap map; + Map map; auto create_func = [](float *value) { *value = 10.0f; return true; @@ -201,13 +235,13 @@ TEST(map, AddOrModify) EXPECT_EQ(map.lookup(1), 15.0f); } -TEST(map, AddOverride) +TEST(map, AddOverwrite) { - IntFloatMap map; + Map map; EXPECT_FALSE(map.contains(3)); - EXPECT_TRUE(map.add_override(3, 6.0f)); + EXPECT_TRUE(map.add_overwrite(3, 6.0f)); EXPECT_EQ(map.lookup(3), 6.0f); - EXPECT_FALSE(map.add_override(3, 7.0f)); + EXPECT_FALSE(map.add_overwrite(3, 7.0f)); EXPECT_EQ(map.lookup(3), 7.0f); EXPECT_FALSE(map.add(3, 8.0f)); EXPECT_EQ(map.lookup(3), 7.0f); @@ -215,7 +249,7 @@ TEST(map, AddOverride) TEST(map, LookupOrAddDefault) { - IntFloatMap map; + Map map; map.lookup_or_add_default(3) = 6; EXPECT_EQ(map.lookup(3), 6); map.lookup_or_add_default(5) = 2; @@ -226,10 +260,10 @@ TEST(map, LookupOrAddDefault) TEST(map, MoveConstructorSmall) { - IntFloatMap map1; + Map map1; map1.add(1, 2.0f); map1.add(4, 1.0f); - IntFloatMap map2(std::move(map1)); + Map map2(std::move(map1)); EXPECT_EQ(map2.size(), 2); EXPECT_EQ(map2.lookup(1), 2.0f); EXPECT_EQ(map2.lookup(4), 1.0f); @@ -239,24 +273,25 @@ TEST(map, MoveConstructorSmall) TEST(map, MoveConstructorLarge) { - IntFloatMap map1; - for (uint i = 0; i < 100; i++) { + Map map1; + for (int i = 0; i < 100; i++) { map1.add_new(i, i); } - IntFloatMap map2(std::move(map1)); + Map map2(std::move(map1)); EXPECT_EQ(map2.size(), 100); - EXPECT_EQ(map2.lookup(1), 1.0f); - EXPECT_EQ(map2.lookup(4), 4.0f); + EXPECT_EQ(map2.lookup(1), 1); + EXPECT_EQ(map2.lookup(4), 4); EXPECT_EQ(map1.size(), 0); EXPECT_EQ(map1.lookup_ptr(4), nullptr); } TEST(map, MoveAssignment) { - IntFloatMap map1; + Map map1; map1.add(1, 2.0f); map1.add(4, 1.0f); - IntFloatMap map2 = std::move(map1); + Map map2; + map2 = std::move(map1); EXPECT_EQ(map2.size(), 2); EXPECT_EQ(map2.lookup(1), 2.0f); EXPECT_EQ(map2.lookup(4), 1.0f); @@ -264,9 +299,23 @@ TEST(map, MoveAssignment) EXPECT_EQ(map1.lookup_ptr(4), nullptr); } +TEST(map, CopyAssignment) +{ + Map map1; + map1.add(1, 2.0f); + map1.add(4, 1.0f); + Map map2; + map2 = map1; + EXPECT_EQ(map2.size(), 2); + EXPECT_EQ(map2.lookup(1), 2.0f); + EXPECT_EQ(map2.lookup(4), 1.0f); + EXPECT_EQ(map1.size(), 2); + EXPECT_EQ(*map1.lookup_ptr(4), 1.0f); +} + TEST(map, Clear) { - IntFloatMap map; + Map map; map.add(1, 1.0f); map.add(2, 5.0f); @@ -292,12 +341,150 @@ TEST(map, UniquePtrValue) Map> map; map.add_new(1, std::move(value1)); map.add(2, std::move(value2)); - map.add_override(3, std::move(value3)); + map.add_overwrite(3, std::move(value3)); map.lookup_or_add(4, []() { return std::unique_ptr(new int()); }); map.add_new(5, std::unique_ptr(new int())); map.add(6, std::unique_ptr(new int())); - map.add_override(7, std::unique_ptr(new int())); + map.add_overwrite(7, std::unique_ptr(new int())); EXPECT_EQ(map.lookup(1).get(), value1_ptr); EXPECT_EQ(map.lookup_ptr(100), nullptr); } + +TEST(map, Remove) +{ + Map map; + map.add(2, 4); + EXPECT_EQ(map.size(), 1); + EXPECT_FALSE(map.remove(3)); + EXPECT_EQ(map.size(), 1); + EXPECT_TRUE(map.remove(2)); + EXPECT_EQ(map.size(), 0); +} + +TEST(map, PointerKeys) +{ + char a, b, c, d; + + Map map; + EXPECT_TRUE(map.add(&a, 5)); + EXPECT_FALSE(map.add(&a, 4)); + map.add_new(&b, 1); + map.add_new(&c, 1); + EXPECT_EQ(map.size(), 3); + EXPECT_TRUE(map.remove(&b)); + EXPECT_TRUE(map.add(&b, 8)); + EXPECT_FALSE(map.remove(&d)); + EXPECT_TRUE(map.remove(&a)); + EXPECT_TRUE(map.remove(&b)); + EXPECT_TRUE(map.remove(&c)); + EXPECT_TRUE(map.is_empty()); +} + +/** + * Set this to 1 to activate the benchmark. It is disabled by default, because it prints a lot. + */ +#if 0 +template +BLI_NOINLINE void benchmark_random_ints(StringRef name, uint amount, uint factor) +{ + RNG *rng = BLI_rng_new(0); + Vector values; + for (uint i = 0; i < amount; i++) { + values.append(BLI_rng_get_int(rng) * factor); + } + BLI_rng_free(rng); + + MapT map; + { + SCOPED_TIMER(name + " Add"); + for (int value : values) { + map.add(value, value); + } + } + int count = 0; + { + SCOPED_TIMER(name + " Contains"); + for (int value : values) { + count += map.contains(value); + } + } + { + SCOPED_TIMER(name + " Remove"); + for (int value : values) { + count += map.remove(value); + } + } + + /* Print the value for simple error checking and to avoid some compiler optimizations. */ + std::cout << "Count: " << count << "\n"; +} + +TEST(map, Benchmark) +{ + for (uint i = 0; i < 3; i++) { + benchmark_random_ints>("BLI::Map ", 1000000, 1); + benchmark_random_ints>("std::unordered_map", 1000000, 1); + } + std::cout << "\n"; + for (uint i = 0; i < 3; i++) { + uint32_t factor = (3 << 10); + benchmark_random_ints>("BLI::Map ", 1000000, factor); + benchmark_random_ints>( + "std::unordered_map", 1000000, factor); + } +} + +/** + * Timer 'BLI::Map Add' took 61.7616 ms + * Timer 'BLI::Map Contains' took 18.4989 ms + * Timer 'BLI::Map Remove' took 20.5864 ms + * Count: 1999755 + * Timer 'std::unordered_map Add' took 188.674 ms + * Timer 'std::unordered_map Contains' took 44.3741 ms + * Timer 'std::unordered_map Remove' took 169.52 ms + * Count: 1999755 + * Timer 'BLI::Map Add' took 37.9196 ms + * Timer 'BLI::Map Contains' took 16.7361 ms + * Timer 'BLI::Map Remove' took 20.9568 ms + * Count: 1999755 + * Timer 'std::unordered_map Add' took 166.09 ms + * Timer 'std::unordered_map Contains' took 40.6133 ms + * Timer 'std::unordered_map Remove' took 142.85 ms + * Count: 1999755 + * Timer 'BLI::Map Add' took 37.3053 ms + * Timer 'BLI::Map Contains' took 16.6731 ms + * Timer 'BLI::Map Remove' took 18.8304 ms + * Count: 1999755 + * Timer 'std::unordered_map Add' took 170.964 ms + * Timer 'std::unordered_map Contains' took 38.1824 ms + * Timer 'std::unordered_map Remove' took 140.263 ms + * Count: 1999755 + * + * Timer 'BLI::Map Add' took 50.1131 ms + * Timer 'BLI::Map Contains' took 25.0491 ms + * Timer 'BLI::Map Remove' took 32.4225 ms + * Count: 1889920 + * Timer 'std::unordered_map Add' took 150.129 ms + * Timer 'std::unordered_map Contains' took 34.6999 ms + * Timer 'std::unordered_map Remove' took 120.907 ms + * Count: 1889920 + * Timer 'BLI::Map Add' took 50.4438 ms + * Timer 'BLI::Map Contains' took 25.2677 ms + * Timer 'BLI::Map Remove' took 32.3047 ms + * Count: 1889920 + * Timer 'std::unordered_map Add' took 144.015 ms + * Timer 'std::unordered_map Contains' took 36.3387 ms + * Timer 'std::unordered_map Remove' took 119.109 ms + * Count: 1889920 + * Timer 'BLI::Map Add' took 48.6995 ms + * Timer 'BLI::Map Contains' took 25.1846 ms + * Timer 'BLI::Map Remove' took 33.0283 ms + * Count: 1889920 + * Timer 'std::unordered_map Add' took 143.494 ms + * Timer 'std::unordered_map Contains' took 34.8905 ms + * Timer 'std::unordered_map Remove' took 122.739 ms + * Count: 1889920 + */ + +#endif /* Benchmark */ -- cgit v1.2.3