Þ   briarpig  » thorn  » demos  » primes

     While prime numbers are seldom important in many tasks Wil undertakes, primes are useful in sizing hashmaps using keys that might otherwise collide in buckets too often because map keys have patterns. Wil takes particular care to use prime numbers to size hashmaps whose keys are pointer addresses with strong alignments like pages. It helps prevent collisions.

     Sample code below trivially shows the value of relatively prime hashmap sizes and hashes for table keys. You might infer the value of prime hashmap sizes from the result shown — seeing can help you believe. A hashmap size of 127 is chosen because 127 is prime. Then Wil writes code to add 127 integers with increasing values separated by the same step increment.

     This is meant to simulate an effect of adding keys all sharing a numerical relationship, like all being multiples of a common factor. When hashmap size is relatively prime to step size, an interesting pattern emerges: there are no collisions. The result is independent of step size; each hashmap bucket has a single hit.

     The loop above zeroes both arrays. Array hit[i] counts the number of times a value is written into vec[i] below.

     This new loop adds 127 integers — increasing by step each time — to array vec[n] where index n is just j mod the prime hashmap size. We count the number of times a value is stored at the same index n by bumping hit[n], and the highest hit count seen is stored in max. The following loop prints all:

     Output from this code appears below. The value of max is one: no collisions were observed. The loop prints any slot with more than one hit in a different format, but that case doesn't appear in the output. Each key lands in a unique slot.

     Of course, a random increase between keys added would show collisions. This demonstration only intends to show value in keeping hashmap size relatively prime to some common factor in keys added. A prime hashmap size will always be relatively prime when the common factor is not the hashmap size itself.

     thorn: todo, names, fd, iovec, assert, log, run, hex, crc, buf, in, out, quote, escape, compare, file, deck, cow, arc, blob, tree, slice, rand, time, stat, hash, heap, node, primes « Þ, page, book, pile, stack, atomic, lock, mutex, thread, map, meter, list, iter, ctype

     (mu: toy, peg, imm, tag, box, symbol, token, number, bigint, class, method, reader, writer, eval, env, vm, gc, world, pcode, compiler, asm, lathe, lisp, smalltalk, design, weight, jar, card, harp, debug, profile)

     Some demos are stubs: todo is a demo guide. See toy for mu updates on language pages; names introduces naming schemes.

     Wil usually collects lists of primes in sizes convenient for progressively larger space allocation schemes. In particular, Wil almost always wants a list of the largest primes less than powers of two, within ranges of plausible hashmap sizes.

     "Do you always use a prime for hashmap size?" Stu asked.

     "No," Wil replied. "Actually, I don't use primes often at all. Usually I have something more important to worry about, like choosing a hash function with good collision resistance."

     "Well, when would you use one of the primes above?" Stu asked. "Is there any pattern? A minimal hash function?"

     "Sometimes I carefully manage heap space to avoid fragmentation," Wil explained. "And I use a variety of block sizes aligned to powers of two. For example, the future page and book demos are about page and super page allocation."

     "Do you put hashmaps inside those?" Stu guessed.

     "Yes, exactly," Wil confirmed. "When I put a hashmap in a block containing a power of two bytes, I'm afraid of address alignment related patterns in bucket collisions."

     "For example, a 4K page contains 1024 32-bit pointers," Stu explored. "If each is a hashmap bucket, you prefer to use only 1021 of them — 1021 is the largest prime under 1024?"

     "Bingo. I couldn't say it better myself," Wil nodded.

     "It sounds weirdly static," Stu complained. "Like you don't plan to dynamically resize hashmaps."

     "In some cases that's right," Wil agreed. "In some first drafts of programming language elements, some hashmaps don't resize. But often they're already much bigger than they need to be."

     "But if each block is uniform in size like pages and books," Stu considered, "then you'd have no fragmentation?"

     "Yes, that's basically the reason," Wil confirmed. "Especially when I allocate temporary space for operations, there's no reason to allocate less than a 4K page. It will just go back in the free pool after, with zero fragmentation. Same for books on a bigger scale."

     Stu squinted. "It sounds like you're simplifying somewhere. Do you really get away with just two sizes: large and small?"

     Wil was nodding. "Yes, having sizes in only two granularities is a simplfication. In real life things get more complex and involve more sizes. But such tuning can always wait."

     "Do you use hashmaps for the page and book allocator, too?" Stu guessed. "Ooh, I just had an idea. Do you use pages and books for space managing allocation of pages and books?"

     "Yeeees," Wil drawled. "You can see how it poses a self referential problem unless care is taken. It's one of the reasons for statically sized hashmaps using primes from the list above. I don't want feedback in map resizing when objects represent their own free lists."

     "Thinking about it gives me a headache already," Stu winced.

     "The code might give you a headache too," Wil warned.