1 /******************************************************************************* 2 3 copyright: Copyright (c) 2008 Kris Bell. All rights reserved 4 5 license: BSD style: $(LICENSE) 6 7 version: Apr 2008: Initial release 8 9 authors: Kris 10 11 Since: 0.99.7 12 13 Based upon Doug Lea's Java collection package 14 15 *******************************************************************************/ 16 17 module tango.util.container.HashMap; 18 19 private import tango.util.container.Slink; 20 21 public import tango.util.container.Container; 22 23 private import tango.util.container.model.IContainer; 24 25 private import tango.core.Exception : NoSuchElementException; 26 27 /******************************************************************************* 28 29 Hash table implementation of a Map 30 31 --- 32 Iterator iterator () 33 int opApply (scope int delegate(ref V value) dg) 34 int opApply (scope int delegate(ref K key, ref V value) dg) 35 36 bool get (K key, ref V element) 37 bool keyOf (V value, ref K key) 38 bool contains (V element) 39 bool containsPair (K key, V element) 40 41 bool removeKey (K key) 42 bool take (ref V element) 43 bool take (K key, ref V element) 44 size_t remove (V element, bool all) 45 size_t remove (IContainer!(V) e, bool all) 46 size_t replace (V oldElement, V newElement, bool all) 47 bool replacePair (K key, V oldElement, V newElement) 48 49 bool add (K key, V element) 50 bool opIndexAssign (V element, K key) 51 V opIndex (K key) 52 V* opIn_r (K key) 53 54 size_t size () 55 bool isEmpty () 56 V[] toArray (V[] dst) 57 HashMap dup () 58 HashMap clear () 59 HashMap reset () 60 size_t buckets () 61 float threshold () 62 void buckets (size_t cap) 63 void threshold (float desired) 64 --- 65 66 *******************************************************************************/ 67 68 class HashMap (K, V, alias Hash = Container.hash, 69 alias Reap = Container.reap, 70 alias Heap = Container.DefaultCollect) 71 : IContainer!(V) 72 { 73 // bucket types 74 version (HashCache) 75 private alias Slink!(V, K, false, true) Type; 76 else 77 private alias Slink!(V, K) Type; 78 79 private alias Type *Ref; 80 81 // allocator type 82 private alias Heap!(Type) Alloc; 83 84 // each table entry is a linked list, or null 85 private Ref[] table; 86 87 // number of elements contained 88 private size_t count; 89 90 // the threshold load factor 91 private float loadFactor; 92 93 // configured heap manager 94 private Alloc heap; 95 96 // mutation tag updates on each change 97 private size_t mutation; 98 99 /*********************************************************************** 100 101 Construct a HashMap instance 102 103 ***********************************************************************/ 104 105 this (float f = Container.defaultLoadFactor) 106 { 107 loadFactor = f; 108 } 109 110 /*********************************************************************** 111 112 Clean up when deleted 113 114 ***********************************************************************/ 115 116 ~this () 117 { 118 reset; 119 } 120 121 /*********************************************************************** 122 123 Return a generic iterator for contained elements 124 125 ***********************************************************************/ 126 127 final Iterator iterator () 128 { 129 Iterator i = void; 130 i.mutation = mutation; 131 i.table = table; 132 i.owner = this; 133 i.cell = null; 134 i.row = 0; 135 return i; 136 } 137 138 /*********************************************************************** 139 140 141 ***********************************************************************/ 142 143 final int opApply (scope int delegate(ref K key, ref V value) dg) 144 { 145 return iterator.opApply (dg); 146 } 147 148 /*********************************************************************** 149 150 151 ***********************************************************************/ 152 153 final int opApply (scope int delegate(ref V value) dg) 154 { 155 return iterator.opApply ((ref K k, ref V v) {return dg(v);}); 156 } 157 158 /*********************************************************************** 159 160 Return the number of elements contained 161 162 ***********************************************************************/ 163 164 @property final const size_t size () 165 { 166 return count; 167 } 168 169 /*********************************************************************** 170 171 Add a new element to the set. Does not add if there is an 172 equivalent already present. Returns true where an element 173 is added, false where it already exists (and was possibly 174 updated). 175 176 Time complexity: O(1) average; O(n) worst. 177 178 ***********************************************************************/ 179 180 final bool add (K key, V element) 181 { 182 if (table is null) 183 resize (Container.defaultInitialBuckets); 184 185 auto hd = &table [Hash (key, table.length)]; 186 auto node = *hd; 187 188 if (node is null) 189 { 190 *hd = heap.allocate.set (key, element, null); 191 increment; 192 } 193 else 194 { 195 auto p = node.findKey (key); 196 if (p) 197 { 198 if (element != p.value) 199 { 200 p.value = element; 201 mutate; 202 } 203 return false; 204 } 205 else 206 { 207 *hd = heap.allocate.set (key, element, node); 208 increment; 209 210 // we only check load factor on add to nonempty bin 211 checkLoad; 212 } 213 } 214 return true; 215 } 216 217 /*********************************************************************** 218 219 Add a new element to the set. Does not add if there is an 220 equivalent already present. Returns true where an element 221 is added, false where it already exists (and was possibly 222 updated). This variation invokes the given retain function 223 when the key does not already exist. You would typically 224 use that to duplicate a char[], or whatever is required. 225 226 Time complexity: O(1) average; O(n) worst. 227 228 ***********************************************************************/ 229 230 final bool add (K key, V element, K function(K) retain) 231 { 232 if (table is null) 233 resize (Container.defaultInitialBuckets); 234 235 auto hd = &table [Hash (key, table.length)]; 236 auto node = *hd; 237 238 if (node is null) 239 { 240 *hd = heap.allocate.set (retain(key), element, null); 241 increment; 242 } 243 else 244 { 245 auto p = node.findKey (key); 246 if (p) 247 { 248 if (element != p.value) 249 { 250 p.value = element; 251 mutate; 252 } 253 return false; 254 } 255 else 256 { 257 *hd = heap.allocate.set (retain(key), element, node); 258 increment; 259 260 // we only check load factor on add to nonempty bin 261 checkLoad; 262 } 263 } 264 return true; 265 } 266 267 /*********************************************************************** 268 269 Return the element associated with key 270 271 param: a key 272 param: a value reference (where returned value will reside) 273 Returns: whether the key is contained or not 274 275 ************************************************************************/ 276 277 final bool get (K key, ref V element) 278 { 279 if (count) 280 { 281 auto p = table [Hash (key, table.length)]; 282 if (p && (p = p.findKey(key)) !is null) 283 { 284 element = p.value; 285 return true; 286 } 287 } 288 return false; 289 } 290 291 /*********************************************************************** 292 293 Return the element associated with key 294 295 param: a key 296 Returns: a pointer to the located value, or null if not found 297 298 ************************************************************************/ 299 300 final V* opIn_r (K key) 301 { 302 if (count) 303 { 304 auto p = table [Hash (key, table.length)]; 305 if (p && (p = p.findKey(key)) !is null) 306 return &p.value; 307 } 308 return null; 309 } 310 311 /*********************************************************************** 312 313 Does this set contain the given element? 314 315 Time complexity: O(1) average; O(n) worst 316 317 ***********************************************************************/ 318 319 final bool contains (V element) 320 { 321 return instances (element) > 0; 322 } 323 324 /*********************************************************************** 325 326 Time complexity: O(n). 327 328 ************************************************************************/ 329 330 final bool keyOf (V value, ref K key) 331 { 332 if (count) 333 foreach (list; table) 334 if (list) 335 { 336 auto p = list.find (value); 337 if (p) 338 { 339 key = p.key; 340 return true; 341 } 342 } 343 return false; 344 } 345 346 /*********************************************************************** 347 348 Time complexity: O(1) average; O(n) worst. 349 350 ***********************************************************************/ 351 352 final bool containsKey (K key) 353 { 354 if (count) 355 { 356 auto p = table[Hash (key, table.length)]; 357 if (p && p.findKey(key)) 358 return true; 359 } 360 return false; 361 } 362 363 /*********************************************************************** 364 365 Time complexity: O(1) average; O(n) worst. 366 367 ***********************************************************************/ 368 369 final bool containsPair (K key, V element) 370 { 371 if (count) 372 { 373 auto p = table[Hash (key, table.length)]; 374 if (p && p.findPair (key, element)) 375 return true; 376 } 377 return false; 378 } 379 380 /*********************************************************************** 381 382 Make an independent copy of the container. Does not clone 383 elements 384 385 Time complexity: O(n) 386 387 ***********************************************************************/ 388 389 @property final HashMap dup () 390 { 391 auto clone = new HashMap!(K, V, Hash, Reap, Heap) (loadFactor); 392 393 if (count) 394 { 395 clone.buckets (buckets); 396 397 foreach (key, value; iterator) 398 clone.add (key, value); 399 } 400 return clone; 401 } 402 403 /*********************************************************************** 404 405 Time complexity: O(1) average; O(n) worst. 406 407 ***********************************************************************/ 408 409 final bool removeKey (K key) 410 { 411 V value; 412 413 return take (key, value); 414 } 415 416 /*********************************************************************** 417 418 Time complexity: O(1) average; O(n) worst. 419 420 ***********************************************************************/ 421 422 final bool replaceKey (K key, K replace) 423 { 424 if (count) 425 { 426 auto h = Hash (key, table.length); 427 auto hd = table[h]; 428 auto trail = hd; 429 auto p = hd; 430 431 while (p) 432 { 433 auto n = p.next; 434 if (key == p.key) 435 { 436 if (p is hd) 437 table[h] = n; 438 else 439 trail.detachNext; 440 441 // inject into new location 442 h = Hash (replace, table.length); 443 table[h] = p.set (replace, p.value, table[h]); 444 return true; 445 } 446 else 447 { 448 trail = p; 449 p = n; 450 } 451 } 452 } 453 return false; 454 } 455 456 /*********************************************************************** 457 458 Time complexity: O(1) average; O(n) worst. 459 460 ***********************************************************************/ 461 462 final bool replacePair (K key, V oldElement, V newElement) 463 { 464 if (count) 465 { 466 auto p = table [Hash (key, table.length)]; 467 if (p) 468 { 469 auto c = p.findPair (key, oldElement); 470 if (c) 471 { 472 c.value = newElement; 473 mutate; 474 return true; 475 } 476 } 477 } 478 return false; 479 } 480 481 /*********************************************************************** 482 483 Remove and expose the first element. Returns false when no 484 more elements are contained 485 486 Time complexity: O(n) 487 488 ***********************************************************************/ 489 490 final bool take (ref V element) 491 { 492 if (count) 493 foreach (ref list; table) 494 if (list) 495 { 496 auto p = list; 497 element = p.value; 498 list = p.next; 499 decrement (p); 500 return true; 501 } 502 return false; 503 } 504 505 /*********************************************************************** 506 507 Remove and expose the element associated with key 508 509 param: a key 510 param: a value reference (where returned value will reside) 511 Returns: whether the key is contained or not 512 513 Time complexity: O(1) average, O(n) worst 514 515 ***********************************************************************/ 516 517 final bool take (K key, ref V value) 518 { 519 if (count) 520 { 521 auto p = &table [Hash (key, table.length)]; 522 auto n = *p; 523 524 while ((n = *p) !is null) 525 if (key == n.key) 526 { 527 *p = n.next; 528 value = n.value; 529 decrement (n); 530 return true; 531 } 532 else 533 p = &n.next; 534 } 535 return false; 536 } 537 538 /*********************************************************************** 539 540 Operator shortcut for assignment 541 542 ***********************************************************************/ 543 544 final bool opIndexAssign (V element, K key) 545 { 546 return add (key, element); 547 } 548 549 /*********************************************************************** 550 551 Operator retreival function 552 553 Throws NoSuchElementException where key is missing 554 555 ***********************************************************************/ 556 557 final V opIndex (K key) 558 { 559 auto p = opIn_r (key); 560 if (p) 561 return *p; 562 throw new NoSuchElementException ("missing or invalid key"); 563 } 564 565 /*********************************************************************** 566 567 Remove a set of values 568 569 ************************************************************************/ 570 571 final size_t remove (IContainer!(V) e, bool all = false) 572 { 573 auto i = count; 574 foreach (value; e) 575 remove (value, all); 576 return i - count; 577 } 578 579 /*********************************************************************** 580 581 Removes element instances, and returns the number of elements 582 removed 583 584 Time complexity: O(1) average; O(n) worst 585 586 ************************************************************************/ 587 588 final size_t remove (V element, bool all = false) 589 { 590 auto i = count; 591 592 if (i) 593 foreach (ref node; table) 594 { 595 auto p = node; 596 auto trail = node; 597 598 while (p) 599 { 600 auto n = p.next; 601 if (element == p.value) 602 { 603 decrement (p); 604 if (p is node) 605 { 606 node = n; 607 trail = n; 608 } 609 else 610 trail.next = n; 611 612 if (! all) 613 return i - count; 614 else 615 p = n; 616 } 617 else 618 { 619 trail = p; 620 p = n; 621 } 622 } 623 } 624 625 return i - count; 626 } 627 628 /*********************************************************************** 629 630 Replace instances of oldElement with newElement, and returns 631 the number of replacements 632 633 Time complexity: O(n). 634 635 ************************************************************************/ 636 637 final size_t replace (V oldElement, V newElement, bool all = false) 638 { 639 size_t i; 640 641 if (count && oldElement != newElement) 642 foreach (node; table) 643 while (node && (node = node.find(oldElement)) !is null) 644 { 645 ++i; 646 mutate; 647 node.value = newElement; 648 if (! all) 649 return i; 650 } 651 return i; 652 } 653 654 /*********************************************************************** 655 656 Clears the HashMap contents. Various attributes are 657 retained, such as the internal table itself. Invoke 658 reset() to drop everything. 659 660 Time complexity: O(n) 661 662 ***********************************************************************/ 663 664 final HashMap clear () 665 { 666 return clear (false); 667 } 668 669 /*********************************************************************** 670 671 Reset the HashMap contents. This releases more memory 672 than clear() does 673 674 Time complexity: O(n) 675 676 ***********************************************************************/ 677 678 final HashMap reset () 679 { 680 clear (true); 681 heap.collect (table); 682 table = null; 683 return this; 684 } 685 686 /*********************************************************************** 687 688 Return the number of buckets 689 690 Time complexity: O(1) 691 692 ***********************************************************************/ 693 694 final size_t buckets () 695 { 696 return table ? table.length : 0; 697 } 698 699 /*********************************************************************** 700 701 Set the desired number of buckets in the hash table. Any 702 value greater than or equal to one is OK. 703 704 If different than current buckets, causes a version change 705 706 Time complexity: O(n) 707 708 ***********************************************************************/ 709 710 final HashMap buckets (size_t cap) 711 { 712 if (cap < Container.defaultInitialBuckets) 713 cap = Container.defaultInitialBuckets; 714 715 if (cap !is buckets) 716 resize (cap); 717 return this; 718 } 719 720 /*********************************************************************** 721 722 Set the number of buckets for the given threshold 723 and resize as required 724 725 Time complexity: O(n) 726 727 ***********************************************************************/ 728 729 final HashMap buckets (size_t cap, float threshold) 730 { 731 loadFactor = threshold; 732 return buckets (cast(size_t)(cap / threshold) + 1); 733 } 734 735 /*********************************************************************** 736 737 Configure the assigned allocator with the size of each 738 allocation block (number of nodes allocated at one time) 739 and the number of nodes to pre-populate the cache with. 740 741 Time complexity: O(n) 742 743 ***********************************************************************/ 744 745 final HashMap cache (size_t chunk, size_t count=0) 746 { 747 heap.config (chunk, count); 748 return this; 749 } 750 751 /*********************************************************************** 752 753 Return the current load factor threshold 754 755 The Hash table occasionally checka against the load factor 756 resizes itself if it has gone past it. 757 758 Time complexity: O(1) 759 760 ***********************************************************************/ 761 762 final const float threshold () 763 { 764 return loadFactor; 765 } 766 767 /*********************************************************************** 768 769 Set the resize threshold, and resize as required 770 Set the current desired load factor. Any value greater 771 than 0 is OK. The current load is checked against it, 772 possibly causing a resize. 773 774 Time complexity: O(n) 775 776 ***********************************************************************/ 777 778 final void threshold (float desired) 779 { 780 assert (desired > 0.0); 781 loadFactor = desired; 782 if (table) 783 checkLoad; 784 } 785 786 /*********************************************************************** 787 788 Copy and return the contained set of values in an array, 789 using the optional dst as a recipient (which is resized 790 as necessary). 791 792 Returns a slice of dst representing the container values. 793 794 Time complexity: O(n) 795 796 ***********************************************************************/ 797 798 final V[] toArray (V[] dst = null) 799 { 800 if (dst.length < count) 801 dst.length = count; 802 803 size_t i = 0; 804 foreach (k, v; this) 805 dst[i++] = v; 806 return dst [0 .. count]; 807 } 808 809 /*********************************************************************** 810 811 Is this container empty? 812 813 Time complexity: O(1) 814 815 ***********************************************************************/ 816 817 final const bool isEmpty () 818 { 819 return count is 0; 820 } 821 822 /*********************************************************************** 823 824 Sanity check 825 826 ***********************************************************************/ 827 828 final HashMap check () 829 { 830 assert(!(table is null && count !is 0)); 831 assert((table is null || table.length > 0)); 832 assert(loadFactor > 0.0f); 833 834 if (table) 835 { 836 size_t c = 0; 837 for (size_t i=0; i < table.length; ++i) 838 for (auto p = table[i]; p; p = p.next) 839 { 840 ++c; 841 assert(contains(p.value)); 842 assert(containsKey(p.key)); 843 assert(instances(p.value) >= 1); 844 assert(containsPair(p.key, p.value)); 845 assert(Hash (p.key, table.length) is i); 846 } 847 assert(c is count); 848 } 849 return this; 850 } 851 852 /*********************************************************************** 853 854 Count the element instances in the set (there can only be 855 0 or 1 instances in a Set). 856 857 Time complexity: O(n) 858 859 ***********************************************************************/ 860 861 private size_t instances (V element) 862 { 863 size_t c = 0; 864 foreach (node; table) 865 if (node) 866 c += node.count (element); 867 return c; 868 } 869 870 /*********************************************************************** 871 872 Check to see if we are past load factor threshold. If so, 873 resize so that we are at half of the desired threshold. 874 875 ***********************************************************************/ 876 877 private HashMap checkLoad () 878 { 879 float fc = count; 880 float ft = table.length; 881 if (fc / ft > loadFactor) 882 resize (2 * cast(size_t)(fc / loadFactor) + 1); 883 return this; 884 } 885 886 /*********************************************************************** 887 888 resize table to new capacity, rehashing all elements 889 890 ***********************************************************************/ 891 892 private void resize (size_t newCap) 893 { 894 // Stdout.formatln ("resize {}", newCap); 895 auto newtab = heap.allocate (newCap); 896 mutate; 897 898 foreach (bucket; table) 899 while (bucket) 900 { 901 auto n = bucket.next; 902 version (HashCache) 903 auto h = n.cache; 904 else 905 auto h = Hash (bucket.key, newCap); 906 bucket.next = newtab[h]; 907 newtab[h] = bucket; 908 bucket = n; 909 } 910 911 // release the prior table and assign new one 912 heap.collect (table); 913 table = newtab; 914 } 915 916 /*********************************************************************** 917 918 Remove the indicated node. We need to traverse buckets 919 for this, since we're singly-linked only. Better to save 920 the per-node memory than to gain a little on each remove 921 922 Used by iterators only 923 924 ***********************************************************************/ 925 926 private bool removeNode (Ref node, Ref* list) 927 { 928 auto p = list; 929 auto n = *p; 930 931 while ((n = *p) !is null) 932 if (n is node) 933 { 934 *p = n.next; 935 decrement (n); 936 return true; 937 } 938 else 939 p = &n.next; 940 return false; 941 } 942 943 /*********************************************************************** 944 945 Clears the HashMap contents. Various attributes are 946 retained, such as the internal table itself. Invoke 947 reset() to drop everything. 948 949 Time complexity: O(n) 950 951 ***********************************************************************/ 952 953 private final HashMap clear (bool all) 954 { 955 mutate; 956 957 // collect each node if we can't collect all at once 958 if (heap.collect(all) is false) 959 foreach (v; table) 960 while (v) 961 { 962 auto n = v.next; 963 decrement (v); 964 v = n; 965 } 966 967 // retain table, but remove bucket chains 968 foreach (ref v; table) 969 v = null; 970 971 count = 0; 972 return this; 973 } 974 975 /*********************************************************************** 976 977 new element was added 978 979 ***********************************************************************/ 980 981 private void increment () 982 { 983 ++mutation; 984 ++count; 985 } 986 987 /*********************************************************************** 988 989 element was removed 990 991 ***********************************************************************/ 992 993 private void decrement (Ref p) 994 { 995 Reap (p.key, p.value); 996 heap.collect (p); 997 ++mutation; 998 --count; 999 } 1000 1001 /*********************************************************************** 1002 1003 set was changed 1004 1005 ***********************************************************************/ 1006 1007 private void mutate () 1008 { 1009 ++mutation; 1010 } 1011 1012 /*********************************************************************** 1013 1014 Iterator with no filtering 1015 1016 ***********************************************************************/ 1017 1018 private struct Iterator 1019 { 1020 size_t row; 1021 Ref cell, 1022 prior; 1023 Ref[] table; 1024 HashMap owner; 1025 size_t mutation; 1026 1027 /*************************************************************** 1028 1029 Did the container change underneath us? 1030 1031 ***************************************************************/ 1032 1033 bool valid () 1034 { 1035 return owner.mutation is mutation; 1036 } 1037 1038 /*************************************************************** 1039 1040 Accesses the next value, and returns false when 1041 there are no further values to traverse 1042 1043 ***************************************************************/ 1044 1045 bool next (ref K k, ref V v) 1046 { 1047 auto n = next (k); 1048 return (n) ? v = *n, true : false; 1049 } 1050 1051 /*************************************************************** 1052 1053 Return a pointer to the next value, or null when 1054 there are no further values to traverse 1055 1056 ***************************************************************/ 1057 1058 V* next (ref K k) 1059 { 1060 while (cell is null) 1061 if (row < table.length) 1062 cell = table [row++]; 1063 else 1064 return null; 1065 1066 prior = cell; 1067 k = cell.key; 1068 cell = cell.next; 1069 return &prior.value; 1070 1071 } 1072 1073 /*************************************************************** 1074 1075 Foreach support 1076 1077 ***************************************************************/ 1078 1079 int opApply (scope int delegate(ref K key, ref V value) dg) 1080 { 1081 int result; 1082 1083 auto c = cell; 1084 loop: while (true) 1085 { 1086 while (c is null) 1087 if (row < table.length) 1088 c = table [row++]; 1089 else 1090 break loop; 1091 1092 prior = c; 1093 c = c.next; 1094 if ((result = dg(prior.key, prior.value)) != 0) 1095 break loop; 1096 } 1097 1098 cell = c; 1099 return result; 1100 } 1101 1102 /*************************************************************** 1103 1104 Remove value at the current iterator location 1105 1106 ***************************************************************/ 1107 1108 bool remove () 1109 { 1110 if (prior) 1111 if (owner.removeNode (prior, &table[row-1])) 1112 { 1113 // ignore this change 1114 ++mutation; 1115 return true; 1116 } 1117 1118 prior = null; 1119 return false; 1120 } 1121 } 1122 } 1123 1124 1125 /******************************************************************************* 1126 1127 *******************************************************************************/ 1128 1129 debug (HashMap) 1130 { 1131 import tango.io.Stdout; 1132 import tango.core.Memory; 1133 import tango.time.StopWatch; 1134 1135 void main() 1136 { 1137 // usage examples ... 1138 auto map = new HashMap!(char[], int); 1139 map.add ("foo", 1); 1140 map.add ("bar", 2); 1141 map.add ("wumpus", 3); 1142 1143 // implicit generic iteration 1144 foreach (key, value; map) 1145 Stdout.formatln ("{}:{}", key, value); 1146 1147 // explicit generic iteration 1148 foreach (key, value; map.iterator) 1149 Stdout.formatln ("{}:{}", key, value); 1150 1151 // generic iteration with optional remove 1152 auto s = map.iterator; 1153 foreach (key, value; s) 1154 {} // s.remove; 1155 1156 // incremental iteration, with optional remove 1157 char[] k; 1158 int v; 1159 auto iterator = map.iterator; 1160 while (iterator.next(k, v)) 1161 {} //iterator.remove; 1162 1163 // incremental iteration, with optional failfast 1164 auto it = map.iterator; 1165 while (it.valid && it.next(k, v)) 1166 {} 1167 1168 // remove specific element 1169 map.removeKey ("wumpus"); 1170 1171 // remove first element ... 1172 while (map.take(v)) 1173 Stdout.formatln ("taking {}, {} left", v, map.size); 1174 1175 // setup for benchmark, with a set of integers. We 1176 // use a chunk allocator, and presize the bucket[] 1177 auto test = new HashMap!(int, int);//, Container.hash, Container.reap, Container.ChunkGC); 1178 test.buckets(1_500_000);//.cache(8000, 1000000); 1179 const count = 1_000_000; 1180 StopWatch w; 1181 1182 GC.collect; 1183 test.check; 1184 1185 // benchmark adding 1186 w.start; 1187 for (int i=count; i--;) 1188 test.add(i, i); 1189 Stdout.formatln ("{} adds: {}/s", test.size, test.size/w.stop); 1190 1191 // benchmark reading 1192 w.start; 1193 for (int i=count; i--;) 1194 test.get(i, v); 1195 Stdout.formatln ("{} lookups: {}/s", test.size, test.size/w.stop); 1196 1197 // benchmark adding without allocation overhead 1198 test.clear; 1199 w.start; 1200 for (int i=count; i--;) 1201 test.add(i, i); 1202 Stdout.formatln ("{} adds (after clear): {}/s", test.size, test.size/w.stop); 1203 1204 // benchmark duplication 1205 w.start; 1206 auto dup = test.dup; 1207 Stdout.formatln ("{} element dup: {}/s", dup.size, dup.size/w.stop); 1208 1209 // benchmark iteration 1210 w.start; 1211 foreach (key, value; test) {} 1212 Stdout.formatln ("{} element iteration: {}/s", test.size, test.size/w.stop); 1213 1214 GC.collect; 1215 test.check; 1216 /+ 1217 auto aa = new HashMap!(long, int, Container.hash, Container.reap, Container.Chunk); 1218 aa.buckets(7_500_000).cache(100000, 5_000_000); 1219 w.start; 1220 for (int i=5_000_000; i--;) 1221 aa.add (i, 0); 1222 Stdout.formatln ("{} test iteration: {}/s", aa.size, aa.size/w.stop); 1223 +/ 1224 } 1225 }