| // This can grow a Robin Hood linear probing hash table near word-at-a-time memcpy speeds. If you're confused why I use 'keys' | |
| // to describe the hash values, it's because my favorite perspective on Robin Hood (which I learned from Paul Khuong) | |
| // is that it's just a sorted gap array which is MSB bucketed and insertion sorted per chain: | |
| // https://pvk.ca/Blog/2019/09/29/a-couple-of-probabilistic-worst-case-bounds-for-robin-hood-linear-probing/ | |
| // The more widely known "max displacement" picture of Robin Hood hashing also has strengths since the max displacement | |
| // can be stored very compactly. You can see a micro-optimized example of that here for small tables where the max displacement | |
| // can fit in 4 bits: Sub-nanosecond Searches Using Vector Instructions, https://www.youtube.com/watch?v=paxIkKBzqBU | |
| void grow(Table *table) { | |
| u64 exp = 64 - table->shift; | |
| // We grow the table downward in place by a factor of 2 (not counting the overflow area at table->end). |
Background: I am moving away from GMail to my own Haskell-based
server (SMTP receiver/sender, web-based email client, spam filtering,
etc.). All email to @chrisdone.com goes through this server
(mx.chrisdone.com) as of today, and chrisdone@gmail.com forwards a
copy of everything to it.
This is a summary/tracking document of my efforts to simply parse email messages in Haskell for the SMTP receiver.
This is a short post that explains how to write a high-performance matrix multiplication program on modern processors. In this tutorial I will use a single core of the Skylake-client CPU with AVX2, but the principles in this post also apply to other processors with different instruction sets (such as AVX512).
Matrix multiplication is a mathematical operation that defines the product of
| import java.io.*; | |
| import java.util.logging.*; | |
| import javax.xml.bind.DatatypeConverter; | |
| /** | |
| * Hashing with SHA1 | |
| * | |
| * @param input String to hash | |
| * @return String hashed | |
| */ |
