3 ms·

It seems to me the gobblydok is more a problem with your chosen language than the data structure. In c it is perfectly straight forward. Also we are long in a

by nn3 9y ago

It seems to me the gobblydok is more a problem with your chosen language than the data structure. In c it is perfectly straight forward. Also we are long in a world where computers are needed to program computers. Or when did you last type in a program in raw machine language?

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 ago
  You 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).

by nn3 9y ago

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 ago
You 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).