3 ms·

Hello, the author here. It feels great to see my blog on HN! It was quite a journey, at first I thought I invented a novel concurrency schema. However, it turn

Hello, the author here. It feels great to see my blog on HN! It was quite a journey, at first I thought I invented a novel concurrency schema. However, it turns out that it was simply a mix of my ignorance and hubris! :-) Still, I had a lot of fun while designing this data structure and I believe it made a nice story. Ask me anything!

impish9208 3y ago
How do you learn stuff like this? Especially the JNI and off-heap memory parts.
nextaccountic 3y ago
If the keys are strings and you can use Rust, have you considered fst [0]? If the keys have prefixes in common, it is very compact. There's a blog post about it [1] [0] https://github.com/BurntSushi/fst https://github.com/BurntSushi/fst [1] https://blog.burntsushi.net/transducers/ https://blog.burntsushi.net/transducers/ The main limitation of it is that it doesn't support removal, but if removals are infrequent you can workaround that with another fst with removed items (and periodically rebuild the whole thing)
- porridgeandrice 3y ago
  Isn't this. this? https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html
  - nextaccountic 3y ago
    Yes the state machine data structure are also used in regex engines. The author of the fst crate also created Rust's regex crate and the ripgrep [0] CLI tool. The regex crate has multiple implementations of regex matching algorithms, which is exposed as a library [1]. The implementations are selected at runtime based on which is faster and works right for a given regex. See also [2] [0] https://blog.burntsushi.net/ripgrep/ https://blog.burntsushi.net/ripgrep/ [1] https://blog.burntsushi.net/regex-internals/ https://blog.burntsushi.net/regex-internals/ [2] https://docs.rs/regex-automata/latest/regex_automata/#available-regex-engines https://docs.rs/regex-automata/latest/regex_automata/#availa...
  - burntsushi 3y ago
    Author of fst and regex crates here. No, it isn't. The only similarity between them is finite state machines. Cox's article is about regexes. The fst crate is a data structure for storing keys and optional values. Two completely different things.

impish9208 3y ago

How do you learn stuff like this? Especially the JNI and off-heap memory parts.

nextaccountic 3y ago

If the keys are strings and you can use Rust, have you considered fst [0]? If the keys have prefixes in common, it is very compact. There's a blog post about it [1] [0] https://github.com/BurntSushi/fst https://github.com/BurntSushi/fst [1] https://blog.burntsushi.net/transducers/ https://blog.burntsushi.net/transducers/ The main limitation of it is that it doesn't support removal, but if removals are infrequent you can workaround that with another fst with removed items (and periodically rebuild the whole thing)

porridgeandrice 3y ago
Isn't this. this? https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html
- nextaccountic 3y ago
  Yes the state machine data structure are also used in regex engines. The author of the fst crate also created Rust's regex crate and the ripgrep [0] CLI tool. The regex crate has multiple implementations of regex matching algorithms, which is exposed as a library [1]. The implementations are selected at runtime based on which is faster and works right for a given regex. See also [2] [0] https://blog.burntsushi.net/ripgrep/ https://blog.burntsushi.net/ripgrep/ [1] https://blog.burntsushi.net/regex-internals/ https://blog.burntsushi.net/regex-internals/ [2] https://docs.rs/regex-automata/latest/regex_automata/#available-regex-engines https://docs.rs/regex-automata/latest/regex_automata/#availa...
- burntsushi 3y ago
  Author of fst and regex crates here. No, it isn't. The only similarity between them is finite state machines. Cox's article is about regexes. The fst crate is a data structure for storing keys and optional values. Two completely different things.