librope

the difference is small in practice. Good rust often does look a lot like C - with plain structs everywhere and lots of global-ish scoped functions. But I don't agree about unsafe. I've spent some time porting well optimised code from C to rust. I generally find I need far less unsafe code than I expected. I ported a ~500 line skip list implementation from C to rust a few years ago. I think my rust code ended up using just 2 unsafe functions. The rest of the code didn't need any unsafe at all. My skip list was a monster to debug in C because most logic bugs ended up corrupting memory. As a result, a bug in one function caused crashes in far away code. In rust, debugging was much easier. There wasn't any "spooky action at a distance". And that let me reason about the code much more easily. As a result, once I got it working I ended up adding a few more optimisations in rust that I was too overwhelmed to write in C. The rust code is now ~2-3x faster. If you're interested: https://github.com/josephg/jumprope-rs#benchmarks C code is here: https://github.com/josephg/librope

og n) insert & delete, at arbitrary positions. I wrote my library in pure C, implemented on top of a skip list. The code is very subtle - like, there's a lot of very careful logic. A single incorrect line of code will often cause silent data corruption or memory errors that don't show up until much later. It took about as long to properly test & debug the library as it took to write it in the first place. Debugging it was exhausting - there were a myriad of obscure edge cases that I needed fuzzing to track down. When the fuzzer found problems, going from a failing fuzzer trace to a code fix was a big job. Before I started, I had a bunch of optimisations in mind that I wanted to add to the library. But it was so exhausting getting it working at all that I never got around to most of them. Eg I wanted to make each node in the skip list into a gap buffer to reduce memcopies. But implementing that would have required significant code changes - which in turn would have meant a new round of memory bugs and debugging. I never brought myself to do it. At some point I rewrote the library in rust, with liberal use of raw pointers. I made just as many mistakes in the implementation - though the compiler caught a lot of them. The first time I ran it it segfaulted. And I thought "here we go again". But despite using raw pointers, there were only 2 unsafe functions in the whole program. A segfault in rust can only happen from unsafe code. So I took a read of that code - and lo and behold, there was my bug, plain as day. Time to fix: 2 minutes. The library never segfaulted again in all my testing. The first time I benchmarked it it was ~10% faster than the C version. I still have no idea why. It was so much easier to write that a little while later, I put the gap buffer optimisation in. Now the rust library is 2-3x faster than C. In this case, memory safety made my program easier to write. And that resulted in better performance. If anyone is curious, C / rust code is here: https://github.com/josephg/librope https://github.com/josephg/jumprope-rs > BUT. the cultural characteristics of the programmers are only one-quarter of the story. The bigger part is about company culture, and more specifically the availability of programmers. Yeah absolutely. I think this is the biggest downside of rust. Rust is really hard - and painful - to learn. It front loads all the pain. In C, you suffer while debugging. In rust, all that suffering happens while learning the language in the first place. I spent months fighting the borrow checker. And its very demotivating not being able to compile your program at all. Once you understand it, it makes sense. But I think there will always be a limited pool of programmers willing to struggle through. Even chatgpt is bad at rust. It makes all sorts of classic beginner mistakes with lifetimes, and the resulting code often won't compile. Even after pointing out the problem, chatgpt is often unable to correct lifetime bugs.

ryday-sized files. this laptop can do about 20 gigabytes a second to main memory, 10 gigabytes of memmove(), so in 16.7 milliseconds (a 60-hertz frame) it can memmove() 167 megabytes. it isn't until you get into things like search-and-replace jobs on big logfiles that you start to feel the pain the complexity of ropes is also being oversold here. as i pointed out in a comment in a subthread, you can make ropes quite complex, but https://github.com/ivanbgd/Rope-Data-Structure-C is 339 lines of code. it's probably not a real-world rope, though; it has far too much memory overhead probably the most widely used implementation of ropes is the one from the sgi stl, which is in gcc as libstdc++/ext/rope https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USER... and libstdc++/ext/ropeimpl.h https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USER..., which total 1485 lines of code, about five times larger. c++'s verbose syntax isn't doing brevity any favors here in a garbage-collected language, like the cedar language where ropes originated, most of that complexity goes away, and production-quality ropes can be only a few hundred lines of code http://www.bitsavers.org/pdf/xerox/parc/cedar/Cedar_7.0/09_C... another somewhat popular rope implementation is librope, in c https://github.com/josephg/librope which is 684 lines of code and looks to be production-quality there's an unrelated librope-ocaml in debian (and opam); it's 1029 lines of code but nothing in debian depends on it. it looks quite full-featured; the documentation says it 'has all non-deprecated operations of String' http://chris00.github.io/ocaml-rope/doc/rope/Rope/ in ur-scheme i used the simplest, dumbest kind of rope for building up output text (input was parsed into s-expressions character by character): an output text was either a string, a pair (representing the concatenation of its arguments), or nil (representing the empty string). this is very similar to erlang's io lists. the only operations supported were (constant-time) concatenation (implemented as cons) and (linear-time) flattening into a string; this took 27 lines of scheme because the subset of scheme i implemented it in was quite limited. http://canonical.org/~kragen/sw/urscheme/ finseth's book is worth reading https://www.finseth.com/craft/, tatham's notes on b-tree ropes https://www.chiark.greenend.org.uk/~sgtatham/tweak/btree.htm... are worth reading, and raph levien's notes on xi and ropes https://xi-editor.io/docs/rope_science_00.html are worth reading. chris wellons's post about gap buffers https://nullprogram.com/blog/2017/09/07/ is a little bit silly but has animations

your program. If my experience is anything to go by, naively porting C programs to rust would result in faster code a lot of the time. And I find it easier to optimize rust code compared to C code, thanks to generics and the (excellent) crates ecosystem. If I was optimizing for runtime speed, I'd pick rust over C every time. [1] https://github.com/josephg/librope [2] https://github.com/josephg/jumprope-rs

C, but it would have been really awkward to weave in. Possible, but awkward in an already very complex bit of C. In rust it was much easier because of the language's ergonomics. In C I'm using lots of complex memory management and I don't want to add complexity in case I add memory corruption bugs. In rust, well, the optimization was entirely safe code. And as for other languages - I challenge anyone to even approach this level of performance in a non-native language. I'm processing ~30M text edit operations per second. A few years ago I tried something similar in JS and got about 100k edits per second. (300x slower) But these sort of performance results probably won't scale for a broader group of programmers. I've seen rust code run slower than equivalent javascript code because the programmers, used to having a GC, just Box<>'ed everything. And all the heap allocations killed performance. If you naively port python line-by-line to rust, you can't expect to magically get 100x the performance. Its like, if you give a top of the line Porsche to an expert driver, they can absolutely drive faster. But I'm not an expert driver, so I'll probably crash the darn thing. I'd take a simple toyota or something any day. I feel like rust is the porsche, and python is the toyota.

up in a tree with just 88 internal nodes and a depth of 3. It goes fast like this. But if you think an array based solution would work better, I'd love to see it! It would certainly need a lot less code. [1] https://github.com/josephg/librope

more cache misses. A large number will be linearly slower because of all the time spent in memmove. Benchmarking shows the ideal number is in the ballpark of 100-200, depending on CPU and some specifics of the benchmark itself. Cache misses are extremely expensive. Storing only a single character at each node (like the SGI C++ rope structure does) makes it run several times slower. (!!) Code: https://github.com/josephg/librope This is the constant to change if you want to experiment yourself: https://github.com/josephg/librope/blob/81e1938e45561b0856d4... In my opinion, hash tables, btrees and the like in the standard library should probably swap to flat lists internally when the number of items in the collection is small. I'm surprised more libraries don't do that.

/character positions and offset positions. I can't just hardcode a lot of those translations into the data type because the bookkeeping is expensive and it kills cache coherence. Its a cost you only want to pay when you need it. I'm curious to try porting the skip list code to unsafe rust to see if I can add that abstraction capacity in while maintaining the current performance profile. Data structures are fun!