Comment by ekidd | Hacker News Reader

Comment by ekidd | Hacker News Reader

In my programming experience, there are two kinds of code:

1. Code where my objects form a tree. Rust's ownership model is great for this. 95% of my code looks this way naturally, and maybe another 3% can be rewritten to look like this.

2. Code where my objects form a complex graph. At this point, I need to make a choice between manual pointer management (C++, unsafe Rust) and a garbage collector (lots of languages). Happily, Rust does have regular pointers and 'unsafe'.

If most your code looks like (1), and only a small amount looks like (2), then Rust can be a big win. Personally. I really like the combination of low-level control, performance and safety.

But if I encounter a problem with a lot of (2), my first instinct is to reach for crates.io and look up an appropriate library. I do know how to use pointers in Rust and work with 'unsafe', but it's easier to let somebody else do it for me.

If you're really curious, then "Learning Rust with too many lists" (http://cglab.ca/~abeinges/blah/too-many-lists/book/) is a great introduction to more advanced techniques.

(2) is why I'm so happy for Gc<T>.

Also, if my graph is going to be short-lived, I've had success just allocing up an Arena<T>, making as many cycles as I want, and then collecting the whole thing at once after my computation is done.

https://github.com/Manishearth/rust-gc

A common approach to 2) is the database approach ("data-oriented design") where you basically have tables and replace pointers by offsets into these tables.

That might not work if the situation is very uncontrolled and objects live and die very quickly. But in most cases you can just let die a few objects, and every once in a while do "garbage collection" manually by renumbering the still-alive objects to be consecutively indexed.

Usually the result is very clean, performant and modular code.

It's clean and modular for all the reasons that E.F. Codd preached all his life.

It's performant because the tables approach is not micro-managing allocations - each table is only one allocation. You will be hard pressed to detect a difference of (single array + relative index) to raw pointers (= absolute index). There's even machine level support for relative addressing.

You also write most of your code to operate on slices (tables or contiguous subsets of tables) instead of only one row per function call. Mike Acton rightfully says "where there's one, there's many". This approach is obviously great for performance because it avoids function-call overhead and because it's cache-friendly.

By the way, what's Rust's story to avoid referencing dead items in these tables?

> By the way, what's Rust's story to avoid referencing dead items in these tables?

One option is Option<T>.

I've thought about this issue quite a bit because I had a use case (using scala) with lots of graphical data structures and GC mark phases were totally killing my performance, and I thought about using rust until I found out my graph shenanigans wouldn't work there either.

One of those hairbrained research-y ideas I have bouncing around in the back of my head is to fix this. The thing about graphical structures is that there is a huge body of work in graph theory that could be used to provably and deterministically cover >90% (ballpark) of these data structure use cases, but likely at the cost of compiler performance. And if I were even remotely competent with rust macros, I would totally hook up some annotation macro that would call out to Z3/CVC4 to determine satisfiability and then rewrite the code safely (even if it uses unsafe blocks under the covers) or throw an error. But thats for another time :)

The off-the-shelf standard library solutions to #2 are Rc<RefCell<T>> (single threaded) and Arc<Mutex<T>> (multi-threaded). Those aren't super high performance, and they're a little verbose, but they usually satisfy the borrow checker.

Reply on news.ycombinator.com