1 /** Optimized prime modulo calculations. 2 * 3 * Used for fast prime modulo calculations when using simple hash-functions to 4 * index in hash tables (associative arrays). 5 * 6 * See_Also: https://www.reddit.com/r/cpp/comments/anbmol/robin_hoodunordered_map_is_now_the_fastest_hashmap/ 7 * See_Also: https://github.com/martinus/robin-hood-hashing 8 * See_Also: https://probablydance.com/2017/02/26/i-wrote-the-fastest-hashtable/ 9 */ 10 module nxt.prime_modulo; 11 12 pure nothrow @safe @nogc: 13 14 static assert(size_t.sizeof == 8, "This module currently only supports 64-bit platforms"); 15 16 /** Type-safe index into prime number constants `primeConstants`. 17 */ 18 struct PrimeIndex 19 { 20 private ubyte _ix; ///< The index. 21 alias _ix this; ///< PrimeIndex becomes type-safe wrapper to `_ix`. 22 } 23 24 /** Returns: first prime in `primeConstants` >= `value`, where the linear search 25 * in `primeConstants` starts at `primeIndex`. 26 * 27 * Increases `primeIndex` so that `primeConstants[primeIndex]` equals returned 28 * value. 29 */ 30 size_t ceilingPrime(in size_t value, 31 scope ref PrimeIndex primeIndex) 32 { 33 foreach (const nextPrimeIndex; primeIndex .. PrimeIndex(primeConstants.length)) 34 { 35 immutable prime = primeConstants[nextPrimeIndex]; 36 if (value <= prime) 37 { 38 primeIndex = nextPrimeIndex; 39 return prime; 40 } 41 } 42 assert(0, "Parameter value is too large"); 43 } 44 45 /// verify for small modulos 46 unittest { 47 size_t value = 0; // to be adjusted to nearest prime in `primeConstants` 48 auto i = PrimeIndex(0); 49 50 value = 0; 51 value = ceilingPrime(value, i); 52 assert(primeConstants[i] == 0); 53 54 value = 1; 55 value = ceilingPrime(value, i); 56 assert(primeConstants[i] == 2); 57 assert(value == 2); 58 59 value = 2; 60 value = ceilingPrime(value, i); 61 assert(primeConstants[i] == 2); 62 assert(value == 2); 63 64 value = 3; 65 value = ceilingPrime(value, i); 66 assert(primeConstants[i] == 3); 67 assert(value == 3); 68 69 value = 4; 70 value = ceilingPrime(value, i); 71 assert(primeConstants[i] == 5); 72 assert(value == 5); 73 74 value = 5; 75 value = ceilingPrime(value, i); 76 assert(primeConstants[i] == 5); 77 assert(value == 5); 78 79 value = 6; 80 value = ceilingPrime(value, i); 81 assert(primeConstants[i] == 7); 82 assert(value == 7); 83 84 value = 7; 85 value = ceilingPrime(value, i); 86 assert(primeConstants[i] == 7); 87 88 foreach (const ix; 8 .. 11 + 1) 89 { 90 value = ix; 91 value = ceilingPrime(value, i); 92 assert(value == 11); 93 assert(primeConstants[i] == 11); 94 } 95 96 foreach (const ix; 12 .. 13 + 1) 97 { 98 value = ix; 99 value = ceilingPrime(value, i); 100 assert(value == 13); 101 assert(primeConstants[i] == 13); 102 } 103 104 foreach (const ix; 14 .. 17 + 1) 105 { 106 value = ix; 107 value = ceilingPrime(value, i); 108 assert(value == 17); 109 assert(primeConstants[i] == 17); 110 } 111 112 foreach (const ix; 18 .. 23 + 1) 113 { 114 value = ix; 115 value = ceilingPrime(value, i); 116 assert(value == 23); 117 assert(primeConstants[i] == 23); 118 } 119 } 120 121 /// remaining modulos 122 unittest { 123 foreach (const prime; primeConstants[3 .. $]) 124 { 125 size_t value = prime - 1; 126 PrimeIndex primeIndex; 127 value = ceilingPrime(value, primeIndex); 128 assert(value == prime); 129 assert(moduloPrimeIndex(value, primeIndex) == 0); 130 } 131 } 132 133 size_t moduloPrimeIndex(in size_t value, 134 in PrimeIndex primeIndex) 135 { 136 final switch (primeIndex) 137 { 138 static foreach (const index, const primeConstant; primeConstants) 139 { 140 case index: 141 return value % primeConstants[index]; 142 } 143 } 144 } 145 146 /// 147 unittest { 148 static assert(primeConstants.length == 187); 149 assert(moduloPrimeIndex(8, PrimeIndex(3)) == 3); // modulo 5 150 assert(moduloPrimeIndex(9, PrimeIndex(4)) == 2); // modulo 7 151 } 152 153 /// verify `moduloPrimeIndex` 154 unittest { 155 static assert(primeConstants.length <= PrimeIndex._ix.max); 156 foreach (const primeIndex, const prime; primeConstants) 157 { 158 if (prime != 0) 159 { 160 assert(moduloPrimeIndex(prime + 0, PrimeIndex(cast(typeof(PrimeIndex._ix))primeIndex)) == 0); 161 assert(moduloPrimeIndex(prime + 1, PrimeIndex(cast(typeof(PrimeIndex._ix))primeIndex)) == 1); 162 } 163 } 164 } 165 166 private static: 167 168 /** Subset of prime constants in the exclusive range `[0 .. size_t.max]`. 169 * 170 * Suitable for use as lengths of a growing hash table. 171 */ 172 static immutable size_t[] primeConstants = 173 [ 174 0UL, 2UL, 3UL, 5UL, 7UL, 11UL, 13UL, 17UL, 23UL, 29UL, 37UL, 47UL, 175 59UL, 73UL, 97UL, 127UL, 151UL, 197UL, 251UL, 313UL, 397UL, 176 499UL, 631UL, 797UL, 1009UL, 1259UL, 1597UL, 2011UL, 2539UL, 177 3203UL, 4027UL, 5087UL, 6421UL, 8089UL, 10193UL, 12853UL, 16193UL, 178 20399UL, 25717UL, 32401UL, 40823UL, 51437UL, 64811UL, 81649UL, 179 102877UL, 129607UL, 163307UL, 205759UL, 259229UL, 326617UL, 180 411527UL, 518509UL, 653267UL, 823117UL, 1037059UL, 1306601UL, 181 1646237UL, 2074129UL, 2613229UL, 3292489UL, 4148279UL, 5226491UL, 182 6584983UL, 8296553UL, 10453007UL, 13169977UL, 16593127UL, 20906033UL, 183 26339969UL, 33186281UL, 41812097UL, 52679969UL, 66372617UL, 184 83624237UL, 105359939UL, 132745199UL, 167248483UL, 210719881UL, 185 265490441UL, 334496971UL, 421439783UL, 530980861UL, 668993977UL, 186 842879579UL, 1061961721UL, 1337987929UL, 1685759167UL, 2123923447UL, 187 2675975881UL, 3371518343UL, 4247846927UL, 5351951779UL, 6743036717UL, 188 8495693897UL, 10703903591UL, 13486073473UL, 16991387857UL, 189 21407807219UL, 26972146961UL, 33982775741UL, 42815614441UL, 190 53944293929UL, 67965551447UL, 85631228929UL, 107888587883UL, 191 135931102921UL, 171262457903UL, 215777175787UL, 271862205833UL, 192 342524915839UL, 431554351609UL, 543724411781UL, 685049831731UL, 193 863108703229UL, 1087448823553UL, 1370099663459UL, 1726217406467UL, 194 2174897647073UL, 2740199326961UL, 3452434812973UL, 4349795294267UL, 195 5480398654009UL, 6904869625999UL, 8699590588571UL, 10960797308051UL, 196 13809739252051UL, 17399181177241UL, 21921594616111UL, 27619478504183UL, 197 34798362354533UL, 43843189232363UL, 55238957008387UL, 69596724709081UL, 198 87686378464759UL, 110477914016779UL, 139193449418173UL, 199 175372756929481UL, 220955828033581UL, 278386898836457UL, 200 350745513859007UL, 441911656067171UL, 556773797672909UL, 201 701491027718027UL, 883823312134381UL, 1113547595345903UL, 202 1402982055436147UL, 1767646624268779UL, 2227095190691797UL, 203 2805964110872297UL, 3535293248537579UL, 4454190381383713UL, 204 5611928221744609UL, 7070586497075177UL, 8908380762767489UL, 205 11223856443489329UL, 14141172994150357UL, 17816761525534927UL, 206 22447712886978529UL, 28282345988300791UL, 35633523051069991UL, 207 44895425773957261UL, 56564691976601587UL, 71267046102139967UL, 208 89790851547914507UL, 113129383953203213UL, 142534092204280003UL, 209 179581703095829107UL, 226258767906406483UL, 285068184408560057UL, 210 359163406191658253UL, 452517535812813007UL, 570136368817120201UL, 211 718326812383316683UL, 905035071625626043UL, 1140272737634240411UL, 212 1436653624766633509UL, 1810070143251252131UL, 2280545475268481167UL, 213 2873307249533267101UL, 3620140286502504283UL, 4561090950536962147UL, 214 5746614499066534157UL, 7240280573005008577UL, 9122181901073924329UL, 215 11493228998133068689UL, 14480561146010017169UL, 18446744073709551557UL, 216 ]; 217 218 version (none) // deprecated by `switch` over `static foreach` in `moduloPrimeIndex` 219 { 220 static foreach (primeConstant; primeConstants) 221 { 222 static if (primeConstant == 0) 223 { 224 mixin(`size_t mod` ~ primeConstant.stringof[0 .. $-2] ~ `(const size_t) { return ` ~ primeConstant.stringof ~ `; }`); 225 } 226 else 227 { 228 mixin(`size_t mod` ~ primeConstant.stringof[0 .. $-2] ~ `(const size_t value) { return value % ` ~ primeConstant.stringof ~ `; }`); 229 } 230 } 231 static immutable moduloPrimeFns = [ 232 &mod0, &mod2, &mod3, &mod5, &mod7, &mod11, &mod13, &mod17, &mod23, &mod29, &mod37, 233 &mod47, &mod59, &mod73, &mod97, &mod127, &mod151, &mod197, &mod251, &mod313, &mod397, 234 &mod499, &mod631, &mod797, &mod1009, &mod1259, &mod1597, &mod2011, &mod2539, &mod3203, 235 &mod4027, &mod5087, &mod6421, &mod8089, &mod10193, &mod12853, &mod16193, &mod20399, 236 &mod25717, &mod32401, &mod40823, &mod51437, &mod64811, &mod81649, &mod102877, 237 &mod129607, &mod163307, &mod205759, &mod259229, &mod326617, &mod411527, &mod518509, 238 &mod653267, &mod823117, &mod1037059, &mod1306601, &mod1646237, &mod2074129, 239 &mod2613229, &mod3292489, &mod4148279, &mod5226491, &mod6584983, &mod8296553, 240 &mod10453007, &mod13169977, &mod16593127, &mod20906033, &mod26339969, &mod33186281, 241 &mod41812097, &mod52679969, &mod66372617, &mod83624237, &mod105359939, &mod132745199, 242 &mod167248483, &mod210719881, &mod265490441, &mod334496971, &mod421439783, 243 &mod530980861, &mod668993977, &mod842879579, &mod1061961721, &mod1337987929, 244 &mod1685759167, &mod2123923447, &mod2675975881, &mod3371518343, &mod4247846927, 245 &mod5351951779, &mod6743036717, &mod8495693897, &mod10703903591, &mod13486073473, 246 &mod16991387857, &mod21407807219, &mod26972146961, &mod33982775741, &mod42815614441, 247 &mod53944293929, &mod67965551447, &mod85631228929, &mod107888587883, &mod135931102921, 248 &mod171262457903, &mod215777175787, &mod271862205833, &mod342524915839, 249 &mod431554351609, &mod543724411781, &mod685049831731, &mod863108703229, 250 &mod1087448823553, &mod1370099663459, &mod1726217406467, &mod2174897647073, 251 &mod2740199326961, &mod3452434812973, &mod4349795294267, &mod5480398654009, 252 &mod6904869625999, &mod8699590588571, &mod10960797308051, &mod13809739252051, 253 &mod17399181177241, &mod21921594616111, &mod27619478504183, &mod34798362354533, 254 &mod43843189232363, &mod55238957008387, &mod69596724709081, &mod87686378464759, 255 &mod110477914016779, &mod139193449418173, &mod175372756929481, &mod220955828033581, 256 &mod278386898836457, &mod350745513859007, &mod441911656067171, &mod556773797672909, 257 &mod701491027718027, &mod883823312134381, &mod1113547595345903, &mod1402982055436147, 258 &mod1767646624268779, &mod2227095190691797, &mod2805964110872297, &mod3535293248537579, 259 &mod4454190381383713, &mod5611928221744609, &mod7070586497075177, &mod8908380762767489, 260 &mod11223856443489329, &mod14141172994150357, &mod17816761525534927, 261 &mod22447712886978529, &mod28282345988300791, &mod35633523051069991, 262 &mod44895425773957261, &mod56564691976601587, &mod71267046102139967, 263 &mod89790851547914507, &mod113129383953203213, &mod142534092204280003, 264 &mod179581703095829107, &mod226258767906406483, &mod285068184408560057, 265 &mod359163406191658253, &mod452517535812813007, &mod570136368817120201, 266 &mod718326812383316683, &mod905035071625626043, &mod1140272737634240411, 267 &mod1436653624766633509, &mod1810070143251252131, &mod2280545475268481167, 268 &mod2873307249533267101, &mod3620140286502504283, &mod4561090950536962147, 269 &mod5746614499066534157, &mod7240280573005008577, &mod9122181901073924329, 270 &mod11493228998133068689, &mod14480561146010017169, &mod18446744073709551557, 271 ]; 272 }