alcinnz
Now that we have a mid-level (stack-based) language to use, & DX-tested it via Tetris, its time to get to actually implementing our high-level language: Lua!
Starting with its datamodel, for which Lua has a single collection type called "records". These are best thought of as hashmaps, though they also perform well as arrays or hashsets. And with a bit of syntactic sugar, structures & in turn modules!
Though I will later add byteslices, so Lua can serve as a system language!
1/3?
alcinnz
When the keys of a record are other records, they obey pointer-equality. Integers I'll take care to leave unhashed so it performs well as an array, & strings I'll prehash. There's other datatypes I'll need to consider, but those are the main ones!
From this key or hash-thereof I'd compute an index into a power-of-2-sized array, by bitshifting the upper bits to XOR with the lower bits thereby ensuring all bits of the key of a say on the index. Without hurting performance as an array.
2/4?
alcinnz
I'd maintain a "header" object tracking the underlying array's size & how many entries it holds in addition to the pointer to said array where it can readily be resized. Each entry of the array would hold the key, value, & a byte for both their types. The type would also flag empty slots.
Once the array reaches 2/3s full I'd have it reallocate the array and move entry into its new place. If we enlarged the array in-place, check if a value's already there to rehash.
3/4?
alcinnz
If upon looking up an entry I find another value in that slot (bound to happen) I'd check the next slot (which our CPU has probably prefetched already) until we reach a slot which has never held a value. I'd have the type field distinguish always-was empty vs "tombstoned" slots.
To set a value in the record under a given key, I'd locate the slot for that key or the first empty slot after where it should be.
As for handling strings...
4/5!
alcinnz
I'd hash strings using FNV-hashing, that is XORing the hash by each byte/char of the key & multiplying by a carefully chosen prime.
None of my research states in great detail why these particular primes are chosen but for a 32bit hash 2^24 + 2^8 + 147 = 16,777,619 is IETF-recommended!
For small strings I'd use an internal record mapping from hashes to deduplicated strings, so we can use the string's pointer as it's hash. These strings would be length-prefixed.
As for longer strings...
5/6!!
alcinnz
Longer strings would represented using a record (so I can self-host most of it), & cache the hash in that record. Or if its not there yet I'd iterate over keys >= 1 to hash the concatenation of them.
Beyond long-strings would be entirely implemented in Lua!
5.5/5.5 Fin for today!
GNU social JP is a social network, courtesy of GNU social JP管理人. It runs on GNU social, version 2.0.2-dev, available under the GNU Affero General Public License.
All GNU social JP content and data are available under the Creative Commons Attribution 3.0 license.