Hacker News Reader

Comment by dcsommer | Hacker News Reader

There are some good thoughts concerning when to use a linked list here: https://rust-unofficial.github.io/too-many-lists/

View on HN

Your link talks about the general case. For better or worse, (most) Lisps give linked-list operations a special status as a fundamental primitive. For example, getting the tail of a list over and over is commonly used for iterating through its elements. If you try and do this with a Vec you'll be copying and re-allocating almost the whole thing on every loop iteration.

Nothing about Lisp requires that you write code this way of course, but it's the epitome of what could be called "Lispy" (literally: "list processing language"), and any preexisting code or habits will hit a brick wall if those lists are implemented as Vecs

To add, Clojure uses a sequence interface that is typically backed by a vector. Conj (instead of cons) is used to derive a new sequence with the thing added in front for lists (which are rarely used) and at the back for vectors.

It supports both, as it should; Lists are still first-class citizens, it's just that vectors are too.

Though also in Clojure's case vectors aren't really vectors, they're immutable persistent data structures that share memory as much as possible, which I think would actually solve most of the performance problem here. But the same is not true of Rust's Vec<>

https://github.com/bodil/im-rs

I'm solely commenting on the implementation in the OP, which uses a regular Vec<>

Both are supported, but people rarely use lists in normal code IME - just in macros or other syntax representations (eg Datalog).

> you'll be copying and re-allocating almost the whole thing on every loop iteration.

This is true if the list is writeable, but, if so surely a Lisp has to also keep duplicating the list or else it will get into trouble?

For reading the list why shouldn't Rust use a slice of the vector? The slice can't own anything, but that's OK, we aren't changing anything. The slice is very cheap, it's basically a pointer into the vector plus a length count.

> surely a Lisp has to also keep duplicating the list or else it will get into trouble?

Nope, it doesn't traditionally duplicate the list. It certainly is possible to get into trouble in your logic, but those are the presented semantics, and debating their virtue is out of scope

> why shouldn't Rust use a slice of the vector?

You're gonna get into ownership-hell if you can't give a separate Rc to each list tail, because those can get passed around wherever

That's what Cow is for, surely?

For the ownership thing? No, I don't think so. I haven't done much with Cow but my understanding is it doesn't do anything to help with cases where you have "multiple owners" of a value. It might allow you to use a slice up until it needs to be cloned, but you'll still have to clone it at that point.

Unlike the slice, a Cow made from that slice can be Owned. Unlike reference counting the underlying Vector, the Cow won't duplicate the slice until you modify it.

This forces you to confront the reality you'd been dodging. Either you actually mutate this list in your program, and the "magic" of linked lists dissolves when it consumes all your memory, or as seems far more likely you get good performance from the better underlying data structure anyway and the "magic" of linked lists dissolves that way.

You only get good performance from linked lists today on the rare occasion when their lack of data locality is outweighed by some other factor. Sprinkling the Lisp idiom over things doesn't change that.

Here's an example where it's worth it: In highly concurrent systems you can't afford to use any sort of locking to protect data structures, the contention for the locks hurts too much, and you can't afford to reference count everything in those structures because even the contention on the reference counts also costs too much (everything looking at an item is storing to the reference count). So you use Hazard Pointers to avoid prematurely dropping anything. But any type of locking for your Hazard Pointers structure would have too much contention also, so you store the Hazard Pointers in a linked list, new ones can be slotted into place at the start of the list with an atomic compare-exchange. Each CPU core is writing to the Hazard Pointers it "owns" a lot, but they're deliberately too big to share with another CPU's cache, and any CPU cores that need to check the Hazard Pointers read from them all but never write so modern caches cope admirably.

You're getting really into the weeds. All I'm saying is the OP will behave unexpectedly for people expecting "just a lisp" (a Scheme-like and/or CL-like lisp). It is not some kind of contract-preserving optimization over a naive linked-list (though those exist!).

The way those languages chose to handle this stuff has well-trod advantages and disadvantages. I don't love it personally, but I get it. Certainly it's worked well enough for a whole lot of software!

But I'm not commentating on it here. I'm just stating the divergence with the OP. Critiquing Lisp's 40+ year history and what parts of it should or shouldn't have been different is out of scope as far as I'm concerned. You're arguing against something that isn't being stated.

> All I'm saying is the OP will behave unexpectedly for people expecting "just a lisp" (a Scheme-like and/or CL-like lisp)

What sort of expectations do you think will be defeated? Beyond the fact that it's only a toy and not, in fact, a Common Lisp or Scheme? Almost everything is missing, but it's a toy. You noticed the Vec but apparently didn't notice the toy language still doesn't even have Cons at the end.

The bytes[0] crate is a popular library in the Rust ecosystem for taking reference-counted slices of a shared byte buffer.

[0]: https://docs.rs/bytes/1.0.1/bytes/struct.Bytes.html

Reply on news.ycombinator.com