Hacker News Reader

Comment by Dzugaru | Hacker News Reader

I come from C# and Rust absolutely drives me bonkers. I try to reference all the things all the time, cause its ingrained in my brain as more efficient than copying stuff around or/and requesting things from hashmaps. The first thing I've tried to implement was a string interning module and I was stuck on it for three days (I still don't know how to do it without duplicating each string twice). Rust is completely orthogonal to the concept of a nice garbage collected graph of objects.

View on HN

On this very specific point, for this specific problem, I think that `Rc<str>` is criminally underused. It's a great type if you need a heap allocated string, but want to hold on to copies of it in various places; and it derefs to `&str`, so you can use it transparently with most of `std`.

Maybe check out one of the existing string interning modules? There are some good ones. I believe it's common to internally use indexes instead of references to get around the borrow checker in these kind of situations.

That's my impression with Rust for now - you use indexes instead and borrow as needed. Long lived borrows are a no go, I was shocked to figure out you cannot return a new thing and a reference to it from a function.

I have a similar experience. I initially naively thought that implementing data structures would be a good exercise in grasping syntax and ownership. It's usually one of the earlier exercises I do in learning a new language.

However data structures in Rust are not at all straightforward. Especially implementing traits, such as an Iterator for a Hashmap. And std implementations use loads of unsafe so beginner me became increasingly confused as to whether these things were not expressible in safe rust.

> I try to reference all the things all the time, cause its ingrained in my brain as more efficient than copying stuff around or/and requesting things from hashmaps.

Many people don't realize that actually referencing all the things all the time is LESS efficient than copying stuff around on modern architectures, unless you copy really big things. This is because the majority of improvement of memory access in the recent years is seen in sequential speeds but not latency.

I’ve never tried that so i don’t know the challenge but my first thought was that it doesn’t seem incompatible with rust’s ownership model - assuming an interned string has static lifetime and then hand out immutable references?

I wanted to drop strings which are not used anymore, you do need Rc for that (no way around it I think), but my problem was that I also needed that strings as a key to HashMap<String, Weak<String>>. So I use that HashMap to check if the string is interned and give a new counted reference as needed and also periodically check any weak refs that should be dropped. This works, but the key better be immutable (I think?) so you cant do HashMap<Weak<String>, Weak<String>> (HashSet?) and hence need second copy as a key.

That's an interesting case. This won't solve your whole problem, but you should be able to make the key the hash of the string and then have a HashMap<u64, Weak<String>>. I feel like there's a pretty solution where you stick the whole map in a Rc and stick that in every interned string. Then strings can remove/lookup themselves. To make that work you'll want some sort of concurrent hash map.

But how would you handle hash collisions if the value is just a Weak<String> rather than some kind of nested container type?

I started thinking along the lines of an arena allocator, that would allow a shorter lifetime than static so you could remove unused references by dropping the arena and moving over still live references to a new arena. I guess arenas the wrong term with that behaviour, maybe generational mark and sweep garbage collector is closer to describing this approach.

It a avoids the double reference though of the Rc<> model.

What about using a HashSet<Rc<str>>. And returning a type that implements Drop. The drop method can remove the string from the cache when the last reference is dropped. Since the cache must be accessed by the interning function and drop, I used interior mutability. By putting the cache behind a Rc<RefCell<>>.

https://play.rust-lang.org/?version=stable&mode=debug&editio...

With the same principle, we can use a static, arc and mutex to use a the cache as a global variable. And implement thread-safe string interning. Here, locking the cache at the wrong time during the drop can lead to a race condition.

https://play.rust-lang.org/?version=stable&mode=debug&editio...

To make the InternedStr behaves a bit more like &str or an immutable String, I implemented Clone, Display, Pointer, conversion from &Interned to &str. Ideally it should probably resemble how String de-references to &str for everything (Deref<Target = str>).

You'd need to pick a hash that won't have collisions within your expected use.

Edit: this might be interesting to you: https://docs.rs/crossbeam-epoch/0.9.4/crossbeam_epoch/

Reply on news.ycombinator.com