3 ms·
I made one of those in C, using skip lists instead of trees so it wouldn't need rebalancing: https://github.com/josephg/librope https://github.com/josephg/libr
by josephg 9y ago
I made one of those in C, using skip lists instead of trees so it wouldn't need rebalancing:
https://github.com/josephg/librope https://github.com/josephg/librope
It could happily do 5M random single character edits / second on my old laptop. Its wild what you can pull off with C. Much more memory efficient too (it uses about 4 pointers of overhead per 180 characters).
I'd love to see a version which supported traversal using more methods though - that library needs to support searching by line as well as character count.
I tried porting it to Rust a few times but unfortunately couldn't figure out how to port it without introducing indirection everywhere. Modern 'C replacement' languages don't let you do the same funky memory management tricks. (Like using a dynamically sized array at the end of a struct allocated in the same block.)
- smaddox 9y agoImplementing efficient datastructures in Rust often requires `unsafe` code. Unlike in C, though, you can use Traits (which provide both static and dynamic dispatch, depending on usage) to provide a safe, zero-cost interface.
- Ar-Curunir 9y agoJust to nitpick, Traits aren't (just) what make Rust fast. There's a lot of help from the compiler and the type system that allows the final compiled code to remove bounds checks in a safe manner.
- josephg 9y agoEven using unsafe I couldn't figure out how to pull it off in rust without doubling my heap allocations. Each item in the skip list has an associated randomly sized list of next pointers. In C I store that list at the end of the node data structure, and dynamically allocate the struct based on how much memory I need (basically, size of static array of characters + size of dynamic nexts array). In Rust in theory I can make my struct unsized to do the same thing. (Well, it pushes the nexts height out into the pointer but that's not too bad). But there doesn't seem to be any syntax to initialise the values in my unsized struct array itself once I've allocated it - even in unsafe. If you can figure out simply how to initialize a custom heap-allocated unsized struct I'll happily keep working on it. My conclusion at the time (and, still, after trying out tokio) is that rust isn't mature enough to replace C yet.