diff options
author | Alexander Gavrilov <angavrilov@gmail.com> | 2018-11-05 19:14:40 +0300 |
---|---|---|
committer | Alexander Gavrilov <angavrilov@gmail.com> | 2018-11-05 20:49:17 +0300 |
commit | fee6ab18e7e9a38203bf8eb95d114ac837578aa7 (patch) | |
tree | 8dc1830ce6dabf781e8d0c2d709db76fab1fd1b9 /tests/gtests | |
parent | a120b120ce380017324e982c2277cb8fca52f39d (diff) |
BLI_heap: implement a limited but faster version of heap.
If the user only needs insertion and removal from top, there is
no need to allocate and manage separate HeapNode objects: the
data can be stored directly in the main tree array.
This measured a 24% FPS increase on a ~50% heap-heavy workload.
Reviewers: brecht
Differential Revision: https://developer.blender.org/D3898
Diffstat (limited to 'tests/gtests')
-rw-r--r-- | tests/gtests/blenlib/BLI_heap_test.cc | 91 |
1 files changed, 91 insertions, 0 deletions
diff --git a/tests/gtests/blenlib/BLI_heap_test.cc b/tests/gtests/blenlib/BLI_heap_test.cc index 26f3aa19b9f..c8026ffa775 100644 --- a/tests/gtests/blenlib/BLI_heap_test.cc +++ b/tests/gtests/blenlib/BLI_heap_test.cc @@ -34,6 +34,16 @@ TEST(heap, Empty) BLI_heap_free(heap, NULL); } +TEST(heap, FastEmpty) +{ + FastHeap *heap; + + heap = BLI_fastheap_new(); + EXPECT_TRUE(BLI_fastheap_is_empty(heap)); + EXPECT_EQ(BLI_fastheap_len(heap), 0); + BLI_fastheap_free(heap, NULL); +} + TEST(heap, One) { Heap *heap; @@ -50,6 +60,22 @@ TEST(heap, One) BLI_heap_free(heap, NULL); } +TEST(heap, FastOne) +{ + FastHeap *heap; + const char *in = "test"; + + heap = BLI_fastheap_new(); + + BLI_fastheap_insert(heap, 0.0f, (void *)in); + EXPECT_FALSE(BLI_fastheap_is_empty(heap)); + EXPECT_EQ(BLI_fastheap_len(heap), 1); + EXPECT_EQ(in, BLI_fastheap_pop_min(heap)); + EXPECT_TRUE(BLI_fastheap_is_empty(heap)); + EXPECT_EQ(BLI_fastheap_len(heap), 0); + BLI_fastheap_free(heap, NULL); +} + TEST(heap, Range) { const int items_total = SIZE; @@ -65,6 +91,21 @@ TEST(heap, Range) BLI_heap_free(heap, NULL); } +TEST(heap, FastRange) +{ + const int items_total = SIZE; + FastHeap *heap = BLI_fastheap_new(); + for (int in = 0; in < items_total; in++) { + BLI_fastheap_insert(heap, (float)in, POINTER_FROM_INT(in)); + } + for (int out_test = 0; out_test < items_total; out_test++) { + EXPECT_EQ(out_test, POINTER_AS_INT(BLI_fastheap_pop_min(heap))); + + } + EXPECT_TRUE(BLI_fastheap_is_empty(heap)); + BLI_fastheap_free(heap, NULL); +} + TEST(heap, RangeReverse) { const int items_total = SIZE; @@ -79,6 +120,20 @@ TEST(heap, RangeReverse) BLI_heap_free(heap, NULL); } +TEST(heap, FastRangeReverse) +{ + const int items_total = SIZE; + FastHeap *heap = BLI_fastheap_new(); + for (int in = 0; in < items_total; in++) { + BLI_fastheap_insert(heap, (float)-in, POINTER_FROM_INT(-in)); + } + for (int out_test = items_total - 1; out_test >= 0; out_test--) { + EXPECT_EQ(-out_test, POINTER_AS_INT(BLI_fastheap_pop_min(heap))); + } + EXPECT_TRUE(BLI_fastheap_is_empty(heap)); + BLI_fastheap_free(heap, NULL); +} + TEST(heap, RangeRemove) { const int items_total = SIZE; @@ -113,6 +168,20 @@ TEST(heap, Duplicates) BLI_heap_free(heap, NULL); } +TEST(heap, FastDuplicates) +{ + const int items_total = SIZE; + FastHeap *heap = BLI_fastheap_new(); + for (int in = 0; in < items_total; in++) { + BLI_fastheap_insert(heap, 1.0f, 0); + } + for (int out_test = 0; out_test < items_total; out_test++) { + EXPECT_EQ(0, POINTER_AS_INT(BLI_fastheap_pop_min(heap))); + } + EXPECT_TRUE(BLI_fastheap_is_empty(heap)); + BLI_fastheap_free(heap, NULL); +} + static void random_heap_helper( const int items_total, const int random_seed) @@ -136,6 +205,28 @@ TEST(heap, Rand1) { random_heap_helper(1, 1234); } TEST(heap, Rand2) { random_heap_helper(2, 1234); } TEST(heap, Rand100) { random_heap_helper(100, 4321); } +static void random_fastheap_helper( + const int items_total, + const int random_seed) +{ + FastHeap *heap = BLI_fastheap_new(); + float *values = (float *)MEM_mallocN(sizeof(float) * items_total, __func__); + range_fl(values, items_total); + BLI_array_randomize(values, sizeof(float), items_total, random_seed); + for (int i = 0; i < items_total; i++) { + BLI_fastheap_insert(heap, values[i], POINTER_FROM_INT((int)values[i])); + } + for (int out_test = 0; out_test < items_total; out_test++) { + EXPECT_EQ(out_test, POINTER_AS_INT(BLI_fastheap_pop_min(heap))); + } + EXPECT_TRUE(BLI_fastheap_is_empty(heap)); + BLI_fastheap_free(heap, NULL); + MEM_freeN(values); +} + +TEST(heap, FastRand1) { random_fastheap_helper(1, 1234); } +TEST(heap, FastRand2) { random_fastheap_helper(2, 1234); } +TEST(heap, FastRand100) { random_fastheap_helper(100, 4321); } TEST(heap, ReInsertSimple) { |