4 ms·
I disagree that its straightforward in C. C is built around pointers, but the bitmasked array uses a completely different kind of pointer. IE you can't just do
by cdoxsey 9y ago
I disagree that its straightforward in C. C is built around pointers, but the bitmasked array uses a completely different kind of pointer. IE you can't just do
n->n.num_children++;
n->children[c] = (art_node*)child;
You have to do:
__m128i cmp;
// Compare the key to all 16 stored keys
cmp = _mm_cmplt_epi8(_mm_set1_epi8(c),
_mm_loadu_si128((__m128i*)n->keys));
// Use a mask to ignore children that don't exist
unsigned bitfield = _mm_movemask_epi8(cmp) & mask;
And that's all CPU-specific.
I'm not saying it can't be done, but rather the tools are a poor fit for the problem. Have you tried to build this data structure? Can you link to the code? I'd love to see what a clean, high-level, understandable example would look like.
> Also we are long in a world where computers are needed to program computers.
Yes you're correct about this. I just think its headed even further in this direction. Languages like C++ and Rust are designed to give the programmer control, but the platforms we're programming for seemed to designed to be impossible to understand.
If I were tasked with building data structures like this I would really want some tools to help me feel confident the code was correct.
- fanf2 9y agoYou might like my “qp trie” code. https://dotat.at/prog/qp/README.html https://dotat.at/prog/qp/README.html It is in a rather experimental proof-of-concept state, but it has been adapted for production use in the Knot-DNS server. The main correctness tool I used was a custom data structure fuzzer, with various sanity checks including a reference implementation in perl that produces the same results as the real implementation under test (when it works).