4 ms·

Has there been any responses to this by some rust guru's? I don't follow rust too closely but am curious about the ownership model

steveklabnik 8y ago
Yes, there's been lots of writing about this. I've been implementing linked lists in various ways over the last week (including right now), so this is very top of mind for me. The core of it is two things: mindset, and how programmers think about learning languages. Mindset: there's two things at play here. The first is that C programmers tend to reach for linked lists by default. It's a CS 101 data structure. Not super hard. A Rust programmer, however, would reach for a vector (or a deque) by default. For many use-cases, these structures are better, thanks to amortized allocations + cache reasons. As always, depends on exactly what you're doing. The second mindset issue is write vs use; C programmers tend to write their data structures themselves. Rust programmers tend to use packages. If you've determined that you need a linked list in Rust, you don't start writing one: you "use std::collections::LinkedList;". It's a doubly-linked one, so maybe that's not what you need. In that case, you go on crates.io and see if someone has already written what you need. (225 hits incidentally: https://crates.io/search?q=linked%20list https://crates.io/search?q=linked%20list) Only if that fails do you write it yourself. As the ecosystem has filled out, this happens increasingly infrequently. So "a linked list is painful to write" just doesn't apply to the vast, vast majority of Rust programmers who are simply getting work done. Learning: because linked lists are a CS 101 data structure, they're something people reach for when learning Rust. But different languages are different, and Rust is not C. Writing a good data structure isn't a beginner Rust topic, it's an intermediate to expert one. There's stuff Rust makes easy that C makes hard as well. You can't assume that topics are equally difficult across the languages. Even then, there's http://cglab.ca/~abeinges/blah/too-many-lists/book/ http://cglab.ca/~abeinges/blah/too-many-lists/book/. TL;DR: linked lists being painful to implement is sorta true, but also not really relevant, other than people who try to learn Rust by building them and having a bad time. (Which is unfortunate, but many people don't as well, or have at least heard that they're hard and so have the right expectations going in.) Now, I've gotta get back to my benchmarks: std::collections::LinkedList is twice as fast as my straightforward C linked list, and I gotta figure out where I messed up. I'll check back later for replies. (If you're interested in this benchmark I'm working on, https://godbolt.org/z/lF1D85 https://godbolt.org/z/lF1D85 is the disassembly. They look so close, I have no idea why 100,000 pushes, the Rust impl is taking 7.9038 ms on average, whereas the C impl is taking 15.413 ms. That seems very wrong...)
- xfer 8y ago
  > C programmers tend to write their data structures themselves. Rust programmers tend to use packages. If you've determined that you need a linked list in Rust, you don't start writing one: you "use std::collections::LinkedList;". It's a doubly-linked one, so maybe that's not what you need. In that case, you go on crates.io and see if someone has already written what you need. (225 hits incidentally: https://crates.io/search?q=linked%20list https://crates.io/search?q=linked%20list) Not sure why you bring this up, since sooner/later people are going to need to implement their own data-structures(and this ownership problem will surface) and being it harder to implement is not relevant to package management(after all somebody did just implement that and made it available).
  - djur 8y ago
    It's very relevant in the context of whether Rust is a 'get things done' language. Implementing a linked list is not a characteristic task of 'getting things done' in Rust, just like implementing a hash table isn't a characteristic task of 'getting things done' in Python. And when you do need to do it, implementing a data structure isn't any harder in unsafe Rust than in C++.
- Cocalus 8y ago
  Have you checked the allocator, that may cause cache differences.
  - steveklabnik 8y ago
    Since I’m on Windows, the Rust is using the system allocator, just like the C.

steveklabnik 8y ago

Yes, there's been lots of writing about this. I've been implementing linked lists in various ways over the last week (including right now), so this is very top of mind for me. The core of it is two things: mindset, and how programmers think about learning languages. Mindset: there's two things at play here. The first is that C programmers tend to reach for linked lists by default. It's a CS 101 data structure. Not super hard. A Rust programmer, however, would reach for a vector (or a deque) by default. For many use-cases, these structures are better, thanks to amortized allocations + cache reasons. As always, depends on exactly what you're doing. The second mindset issue is write vs use; C programmers tend to write their data structures themselves. Rust programmers tend to use packages. If you've determined that you need a linked list in Rust, you don't start writing one: you "use std::collections::LinkedList;". It's a doubly-linked one, so maybe that's not what you need. In that case, you go on crates.io and see if someone has already written what you need. (225 hits incidentally: https://crates.io/search?q=linked%20list https://crates.io/search?q=linked%20list) Only if that fails do you write it yourself. As the ecosystem has filled out, this happens increasingly infrequently. So "a linked list is painful to write" just doesn't apply to the vast, vast majority of Rust programmers who are simply getting work done. Learning: because linked lists are a CS 101 data structure, they're something people reach for when learning Rust. But different languages are different, and Rust is not C. Writing a good data structure isn't a beginner Rust topic, it's an intermediate to expert one. There's stuff Rust makes easy that C makes hard as well. You can't assume that topics are equally difficult across the languages. Even then, there's http://cglab.ca/~abeinges/blah/too-many-lists/book/ http://cglab.ca/~abeinges/blah/too-many-lists/book/. TL;DR: linked lists being painful to implement is sorta true, but also not really relevant, other than people who try to learn Rust by building them and having a bad time. (Which is unfortunate, but many people don't as well, or have at least heard that they're hard and so have the right expectations going in.) Now, I've gotta get back to my benchmarks: std::collections::LinkedList is twice as fast as my straightforward C linked list, and I gotta figure out where I messed up. I'll check back later for replies. (If you're interested in this benchmark I'm working on, https://godbolt.org/z/lF1D85 https://godbolt.org/z/lF1D85 is the disassembly. They look so close, I have no idea why 100,000 pushes, the Rust impl is taking 7.9038 ms on average, whereas the C impl is taking 15.413 ms. That seems very wrong...)

xfer 8y ago
> C programmers tend to write their data structures themselves. Rust programmers tend to use packages. If you've determined that you need a linked list in Rust, you don't start writing one: you "use std::collections::LinkedList;". It's a doubly-linked one, so maybe that's not what you need. In that case, you go on crates.io and see if someone has already written what you need. (225 hits incidentally: https://crates.io/search?q=linked%20list https://crates.io/search?q=linked%20list) Not sure why you bring this up, since sooner/later people are going to need to implement their own data-structures(and this ownership problem will surface) and being it harder to implement is not relevant to package management(after all somebody did just implement that and made it available).
- djur 8y ago
  It's very relevant in the context of whether Rust is a 'get things done' language. Implementing a linked list is not a characteristic task of 'getting things done' in Rust, just like implementing a hash table isn't a characteristic task of 'getting things done' in Python. And when you do need to do it, implementing a data structure isn't any harder in unsafe Rust than in C++.
Cocalus 8y ago
Have you checked the allocator, that may cause cache differences.
- steveklabnik 8y ago
  Since I’m on Windows, the Rust is using the system allocator, just like the C.