1 /**************************************************************************
3 * Copyright 2013-2014 RAD Game Tools and Valve Software
4 * Copyright 2010-2014 Rich Geldreich and Tenacious Software LLC
7 * Permission is hereby granted, free of charge, to any person obtaining a copy
8 * of this software and associated documentation files (the "Software"), to deal
9 * in the Software without restriction, including without limitation the rights
10 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
11 * copies of the Software, and to permit persons to whom the Software is
12 * furnished to do so, subject to the following conditions:
14 * The above copyright notice and this permission notice shall be included in
15 * all copies or substantial portions of the Software.
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
20 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
21 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
22 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
25 **************************************************************************/
28 #include "vogl_core.h"
31 #define VOGL_MAP_COMPARATIVE_PERF_TESTING
33 #ifdef VOGL_MAP_COMPARATIVE_PERF_TESTING
35 #include "vogl_hash_map.h"
36 //#include "vogl_treap.h"
37 //#include "vogl_avltree.h"
44 typedef vogl::map<int, vogl::vector<dynamic_string> > int_to_string_vec_map;
45 int_to_string_vec_map blah;
48 for (uint i = 0; i < 100; i++)
50 vogl::vector<dynamic_string> v;
51 v.push_back(dynamic_string(cVarArg, "hello %u", i));
52 v.push_back(dynamic_string(cVarArg, "blah %u", i));
56 if (blah.contains(cINT32_MAX))
59 for (int_to_string_vec_map::const_iterator it = blah.begin(); it != blah.end(); ++it)
61 if (!blah.contains(it->first))
64 printf("%u:\n", it->first);
65 for (uint i = 0; i < it->second.size(); i++)
67 printf("%s\n", it->second[i].get_ptr());
71 int_to_string_vec_map blah2(blah);
75 if (!blah2.debug_check())
80 if (!blah.debug_check())
82 blah.print_debug_info();
84 if (!blah.debug_check())
86 blah.print_debug_info();
91 typedef vogl::map<int> int_map;
95 for (uint i = 0; i < 10000; i++)
96 z.insert_multi(frm.irand(0, 5000));
100 for (uint i = 0; i < 10000; i++)
101 z.insert_multi(frm.irand(0, 5000));
116 if (!z2.debug_check())
120 int x = z2.begin()->first;
122 z2.erase_all(z2.begin()->first);
126 if (z2.begin()->first == x)
130 if (!z2.debug_check())
136 for (uint i = 0; i < 1000; i++)
138 int l = frm.irand(0, 5000);
139 int h = frm.irand(0, 5000);
143 printf("%i %i\n", l, h);
145 std::pair<int_map::iterator, int_map::iterator> p(z.equal_range(l));
146 uint cnt = z.count(l);
149 if ((p.first != z.end()) || (p.second != z.end()))
155 int_map::const_iterator it(p.first);
156 while (it != p.second)
165 vogl::vector<int> uk;
166 z.get_unique_keys(uk);
169 for (uint i = 0; i < uk.size(); i++)
171 if (!tst.insert(uk[i]).second)
174 if (!tst.debug_check())
177 int_map::iterator nl_it(z.lower_bound(l));
178 VOGL_NOTE_UNUSED(nl_it);
179 int_map::iterator nh_it(z.upper_bound(h));
180 VOGL_NOTE_UNUSED(nh_it);
182 int_map::const_iterator l_it(z.lower_bound(l));
183 int_map::const_iterator h_it(z.upper_bound(h));
186 for (int_map::const_iterator it = l_it; it != h_it; it++)
188 if ((it->first < l) || (it->first > h))
194 for (int_map::const_iterator it = z.begin(); it != z.end(); ++it)
195 if ((it->first >= l) && (it->first <= h))
204 for (uint i = 0; i < 1000; i++)
205 set_test.insert_multi(frm.irand(0, 100));
207 for (int_map::const_iterator it = set_test.begin(); it != set_test.end(); it++)
208 printf("%i ", it->first);
211 if (!set_test.debug_check())
213 int_map set_test2(set_test);
215 if (set_test2 != set_test)
218 if (!set_test2.debug_check())
221 for (int_map::const_iterator it = set_test2.begin(); it != set_test2.end(); it++)
222 printf("%i ", it->first);
225 for (int_map::iterator it = set_test2.begin(); it != set_test2.end();)
229 int_map::iterator next_it = it;
240 for (int_map::const_iterator it = set_test2.begin(); it != set_test2.end(); it++)
241 printf("%i ", it->first);
244 if (!set_test2.debug_check())
246 set_test2.print_debug_info();
248 typedef vogl::map<int, int> int_to_int_map;
251 int_to_int_map blah(10);
253 int_to_int_map::const_iterator it0;
254 int_to_int_map::const_iterator it1(blah.begin());
255 int_to_int_map::iterator it2(blah.begin());
260 bool ignored = it1 != it1;
261 VOGL_NOTE_UNUSED(ignored);
262 ignored = it2 != it2;
263 ignored = it1 == it1;
264 ignored = it2 == it2;
266 ignored = it1 != it2;
267 ignored = it2 != it1;
269 int_to_int_map::const_iterator it3(it1);
270 VOGL_NOTE_UNUSED(it3);
271 int_to_int_map::const_iterator it4(it2);
272 VOGL_NOTE_UNUSED(it4);
274 blah.insert_multi(0, 100);
275 blah.insert_multi(0, 101);
276 blah.insert_multi(1, 200);
278 if (blah.count(0) != 2)
281 vogl::vector<int> iv;
282 blah.get_values(0, iv);
285 if ((iv[0] != 101) || (iv[1] != 100))
289 for (int_to_int_map::const_iterator it = blah.begin(); it != blah.end(); ++it)
290 printf("%i %i\n", it->first, it->second);
294 for (int_to_int_map::iterator it = blah.begin(); it != blah.end(); ++it)
295 printf("%i %i\n", it->first, it->second);
298 bool status = blah.debug_check();
303 blah.erase(blah.begin());
307 for (int_to_int_map::const_iterator it = blah.begin(); it != blah.end(); ++it)
308 printf("%i %i\n", it->first, it->second);
311 status = blah.debug_check();
315 int_to_int_map blah2(blah);
317 status = blah2.debug_check();
322 status = blah2.debug_check();
327 status = blah2.debug_check();
331 blah2.print_debug_info();
335 typedef map<dynamic_string, dynamic_string> string_to_string_map;
336 string_to_string_map s2s(5);
337 s2s.insert_multi("Hello", "World");
338 s2s.insert_multi("Hello", "2");
339 s2s.insert_multi("Hello", "3");
340 s2s.insert_multi("Hello", "4");
341 s2s.insert_multi("Blah", "x");
343 for (string_to_string_map::const_iterator it = s2s.begin(); it != s2s.end(); it++)
345 printf("%s %s\n", it->first.get_ptr(), it->second.get_ptr());
350 if (!s2s.erase("Hello"))
352 if (!s2s.erase("Blah"))
354 if (s2s.erase("ssss"))
357 for (string_to_string_map::const_iterator it = s2s.end(); it != s2s.begin();)
360 printf("%s %s\n", it->first.get_ptr(), it->second.get_ptr());
363 if (!s2s.debug_check())
366 s2s.print_debug_info();
370 if (!s2s.debug_check())
375 typedef map<dynamic_string, vogl::vector<uint> > string_to_vec_map;
376 vogl::vector<uint> k;
380 string_to_vec_map s2v(0);
381 s2v.set_fixed_map_level(0);
382 s2v.insert_multi("Hello", k);
386 s2v.insert_multi("X", k);
390 s2v.insert_multi("Y", k);
392 for (string_to_vec_map::const_iterator it = s2v.begin(); it != s2v.end(); it++)
394 printf("%s %u\n", it->first.get_ptr(), it->second.size());
400 for (string_to_vec_map::const_iterator it = s2v.end(); it != s2v.begin();)
403 printf("%s %u\n", it->first.get_ptr(), it->second.size());
406 if (!s2v.debug_check())
409 s2v.print_debug_info();
412 s2v.insert_multi("Hello", k);
413 for (string_to_vec_map::const_iterator it = s2v.begin(); it != s2v.end(); it++)
415 printf("%s %u\n", it->first.get_ptr(), it->second.size());
418 if (!s2v.debug_check())
425 for (uint t = 0; t < 100; t++)
427 uint n = rm.irand(1, 5000000);
428 uint k = rm.irand(1, n);
433 uint max_level = (n < 512) ? rm.irand(0, 5) : rm.irand(5, 20);
434 m.set_fixed_map_level(max_level);
435 printf("Using fixed max level of %u\n", max_level);
438 printf("Auto max level\n");
442 vogl::vector<int> keys(n);
443 for (uint i = 0; i < n; i++)
445 uint c = rm.irand_inclusive(0, k);
447 m.insert_multi(c, i);
449 printf("max level: %u, max used level: %u, bytes allocated: %" PRIi64 ", avg per node: %f\n",
450 m.get_cur_max_level(), m.get_cur_list_level(), m.get_total_bytes_allocated(), m.get_total_bytes_allocated() / (double)n);
452 bool success = m.debug_check();
456 m.print_debug_info();
458 for (int i = 0; i < static_cast<int>(n); i++)
460 const int c = keys[i];
461 int_to_int_map::const_iterator it = m.find(c);
463 VOGL_VERIFY(it != m.end());
464 VOGL_VERIFY(it->first == keys[i]);
467 // duplicate, the iterator should always point at the beginning of the dup key run
468 int_to_int_map::const_iterator xit(it);
470 if (xit != m.begin())
479 VOGL_VERIFY(xit->first < c);
497 if (xit->second == i)
503 success = m.debug_check();
507 for (uint j = 0; j < keys.size() / 2; j++)
509 if (j == keys.size() / 4)
511 success = m.debug_check();
516 int i = rm.irand(0, keys.size());
522 int_to_int_map::iterator it = m.find(c);
524 VOGL_VERIFY(it != m.end());
525 VOGL_VERIFY(it->first == c);
528 // duplicate, the iterator should always point at the beginning of the dup key run
529 int_to_int_map::iterator xit(it);
531 if (xit != m.begin())
540 VOGL_VERIFY(xit->first < c);
558 if (xit->second == i)
570 success = m.debug_check();
574 while (!m.is_empty())
579 m.erase(m.begin()->first);
582 success = m.debug_check();
586 m.print_debug_info();
588 printf("------------------\n");
594 #define VOGL_MAP_INSERT_ONLY_SPEED_TEST 0
596 void map_perf_test(uint Q)
598 printf("--------------------------------------------------\n");
599 printf("map_perf_test int->int Q: %u\n", Q);
601 vogl::vector<uint> rand_indices(Q);
602 for (uint i = 0; i < Q; i++)
606 rand_indices.shuffle(rm);
608 for (uint i = 0; i < 2; i++)
610 printf("---------------------------- Run %u\n", i);
612 #ifdef VOGL_MAP_COMPARATIVE_PERF_TESTING
613 typedef std::map<int, int> int_to_int_map;
616 printf("forwards std::map:\n");
620 for (uint t = 0; t < Q; t++)
621 m.insert(std::make_pair(t, t * 2));
623 for (uint t = 0; t < Q; t++)
631 printf("backwards std::map:\n");
635 for (uint t = 0; t < Q; t++)
636 m.insert(std::make_pair(Q - 1 - t, t * 2));
638 #if !VOGL_MAP_INSERT_ONLY_SPEED_TEST
639 for (uint t = 0; t < Q; t++)
648 printf("random std::map:\n");
652 for (uint t = 0; t < Q; t++)
653 m.insert(std::make_pair(rand_indices[t], t * 2));
655 #if !VOGL_MAP_INSERT_ONLY_SPEED_TEST
656 for (uint t = 0; t < Q; t++)
658 m.find(rand_indices[t]);
659 m.erase(rand_indices[t]);
664 printf("-----------------------\n");
666 printf("vogl::hash_map:\n");
669 typedef vogl::hash_map<int, int> int_to_int_hash_map;
670 int_to_int_hash_map m;
672 for (uint t = 0; t < Q; t++)
675 #if !VOGL_MAP_INSERT_ONLY_SPEED_TEST
676 for (uint t = 0; t < Q; t++)
685 printf("vogl::hash_map reserved:\n");
688 typedef vogl::hash_map<int, int> int_to_int_hash_map;
689 int_to_int_hash_map m;
693 for (uint t = 0; t < Q; t++)
696 #if !VOGL_MAP_INSERT_ONLY_SPEED_TEST
697 for (uint t = 0; t < Q; t++)
706 printf("-----------------------\n");
708 typedef Treap<int, int> int_to_int_treap;
711 printf("forwards Treap:\n");
715 for (uint t = 0; t < Q; t++)
718 for (uint t = 0; t < Q; t++)
726 printf("backwards Treap:\n");
730 for (uint t = 0; t < Q; t++)
731 m.insert(Q - 1 - t, t * 2);
733 #if !VOGL_MAP_INSERT_ONLY_SPEED_TEST
734 for (uint t = 0; t < Q; t++)
743 printf("random Treap:\n");
747 for (uint t = 0; t < Q; t++)
748 m.insert(rand_indices[t], t * 2);
750 #if !VOGL_MAP_INSERT_ONLY_SPEED_TEST
751 for (uint t = 0; t < Q; t++)
753 m.find(rand_indices[t]);
754 m.erase(rand_indices[t]);
761 printf("-----------------------\n");
763 typedef AVLTree<int, int> int_to_int_avl_tree;
766 printf("forwards AVLTree:\n");
769 int_to_int_avl_tree m;
770 for (uint t = 0; t < Q; t++)
773 for (uint t = 0; t < Q; t++)
781 printf("backwards AVLTree:\n");
784 int_to_int_avl_tree m;
785 for (uint t = 0; t < Q; t++)
786 m.insert(Q - 1 - t, t * 2);
788 #if !VOGL_MAP_INSERT_ONLY_SPEED_TEST
789 for (uint t = 0; t < Q; t++)
798 printf("random AVLTree:\n");
801 int_to_int_avl_tree m;
802 for (uint t = 0; t < Q; t++)
803 m.insert(rand_indices[t], t * 2);
805 #if !VOGL_MAP_INSERT_ONLY_SPEED_TEST
806 for (uint t = 0; t < Q; t++)
808 m.find(rand_indices[t]);
809 m.erase(rand_indices[t]);
817 // Skip testing fixed max levels 0-4, they are just too slow
818 const int skip_level = 5;
820 printf("-----------------------\n");
821 for (int l = -1; l <= 11; l++)
823 if ((l >= 0) && (l < skip_level))
826 printf("forwards vogl::map max_level: %i\n", l);
830 typedef vogl::map<int, int> int_to_int_map;
831 int_to_int_map m((l < 0) ? int_to_int_map::cDefaultMaxLevel : l);
833 m.set_fixed_map_level(l);
835 for (uint t = 0; t < Q; t++)
838 #if !VOGL_MAP_INSERT_ONLY_SPEED_TEST
839 for (uint t = 0; t < Q; t++)
847 printf("-----------------------\n");
848 for (int l = -1; l <= 11; l++)
850 if ((l >= 0) && (l < skip_level))
853 printf("backwards vogl::map max_level: %i\n", l);
857 typedef vogl::map<int, int> int_to_int_map;
858 int_to_int_map m((l < 0) ? int_to_int_map::cDefaultMaxLevel : l);
860 m.set_fixed_map_level(l);
862 for (uint t = 0; t < Q; t++)
863 m.insert(Q - 1 - t, t * 2);
865 #if !VOGL_MAP_INSERT_ONLY_SPEED_TEST
866 for (uint t = 0; t < Q; t++)
874 printf("-----------------------\n");
875 for (int l = -1; l <= 11; l++)
877 if ((l >= 0) && (l < skip_level))
880 printf("random vogl::map max_level: %i\n", l);
884 typedef vogl::map<int, int> int_to_int_map;
885 int_to_int_map m((l < 0) ? int_to_int_map::cDefaultMaxLevel : l);
887 m.set_fixed_map_level(l);
889 for (uint t = 0; t < Q; t++)
890 m.insert(rand_indices[t], t * 2);
892 #if !VOGL_MAP_INSERT_ONLY_SPEED_TEST
893 for (uint t = 0; t < Q; t++)
895 m.find(rand_indices[t]);
896 m.erase(rand_indices[t]);