For rsdict, the main idea is to use `pshufb` to implement querying a lookup table on a vector of integers and then use `psadbw` to horizontally sum the vector.
The arbolito code is a lot less fleshed out, but the main idea is to take a small trie and encode it into SIMD vectors. Laying out the nodes into a linear order, we'd have one vector that maintains a parent pointer (4 bits for 16 node trees in 128-bit vectors) and another vector with the incoming edge label.
Then, following the Teddy algorithm[3] (very similar to the Hillis/Stele state transition ideas too!), we can implement traversing the tree as a state machine, where each node in the trie has a bitmask, and the state transition is a parallel bitshift + shuffle of parent state to children states + bitwise AND. We can even reduce the circuit depth of this algorithm to `O(log depth)` by using successive squaring of the transition, like Hillis/Steele describe too.
I've put it on the backburner, but my main goal for arbolito would be to find a way to stitch together these "tiny tries" into a general purpose trie adaptively and get query performance competitive with a hashmap for integer keys. The ART paper[4] does similar stuff but without the SIMD tricks.
[1] https://github.com/sujayakar/rsdict
[2] https://github.com/sujayakar/arbolito