5 ms·

I know. So? How does that change anything? A doubly-linked list is already space inefficient, it adds 2 pointers per element. Using Rc + Weak adds one extra w

I know. So? How does that change anything? A doubly-linked list is already space inefficient, it adds 2 pointers per element. Using Rc + Weak adds one extra word per element to store the two (strong and weak) refcounts. So for a 64-bit type, a Vec takes 1x space 1xN, a list takes 3xN, and a ref-counted list 4xN. Performance wise, the extra space doesn't change anything, since that word is allocated with the element in the same cache line and would have been read anyways (even if you don't access it, the hardware does access it). If you are using a doubly-linked list, you really don't care that much about any of this, and the only thing that makes a real difference, is the guarantee that your list implementation is correct.

gpderetta 5y ago
The additional refcount takes space that could be used for the payload that now either needs to spill into the next cacheline or needs to be compressed further. You can still use double linked lists in high performance code, as long as the list traversal doesn't happen on the critical path (or at all).
- estebank 5y ago
  If you are concerned about high performance/space overhead/cache awareness you wouldn't want to use a linked list in the first place, instead you'd use an arena.
  - Jensson 5y ago
    An arena is not a replacement for linked lists. In some cases you can use it as a replacement, but in many cases you can't. So can the idiomatic rust apologists please stop with this? I know you love it the language and wants more people to use it, but these sort of statements doesn't help your case. "Performance is almost the same in real world cases" "You don't really need that data structure anyway" "You can learn how to optimize code later" People come and want to use Rust for some fast code. They know what they want the code to do and want it to be as fast as the code they wrote before, and see how Rust would help them achieve that. The above statements are then wrong or patronizing or completely misses the point.
    - estebank 5y ago
      Linked lists are not good for cache locality, it has nothing to do with the language. It'd be my advice over linked lists even if you were doing it in C. Rust does make doubly linked lists in safe code without reference counting impossible, but I don't the argument that you'd use one due to performance or memory overhead.
      - Jensson 5y ago
        > Linked lists are not good for cache locality That doesn't matter if a solution with good cache locality doesn't exist for your problem.
      - deleted 5y ago
        [deleted]
      - gpderetta 5y ago
        They are not, that's why you would use a flat layout for your primary iteration order. But for any secondary ordering/indexing you might need, if you also need fast insert/removal, chaining in a list can be an option.
    - volta83 5y ago
      The question is fair. Why would you want to use a non-intrusive doubly-linked list? AFAIK there is only one answer: you have very big objects and you need O(1) splice. If you don't have very big objects, or you don't need O(1), pretty much any other data-structure in existence is going to give you much much better performance than a doubly-linked list. For the only use case for which non-intrusive doubly-linked lists are good at, however, there exists no hardware you can buy for which you can measure a performance difference between ref-counting and not ref-counting. This has nothing to do with Rust. The same applies to C++, or Java, or Python, or even C. You can do ref counting on any language, and all these languages run pretty much everywhere. The only thing that Rust gives you over Java, Python, or C here is the possibility to implement a doubly-linked list in safe Rust that will perform the same but that the compiler will prove for you to be memory and thread safe. Sure, Rust also allows you to use unsafe code, and then prove that safe and create a safe wrapper. It even does this for you and provides this in std::List. But what value does this add? It's more work, and it doesn't perform better, and why a significant number of people have argued in the past that adding std::List was a mistake in one form or another.
- volta83 5y ago
  > The additional refcount takes space that could be used for the payload that now either needs to spill into the next cacheline or needs to be compressed further. It could, but since the cachelines are adjacents the prefetcher will pull subsequent cache lines anyways, and since the objects typically used in doubly-linked lists are very large (much larger than 64-bit), then this doesn't matter on any practical application that I am aware of. Our results of 4% performance increase is for the worst-case that we found. Usually is 1% or less. If you have a real-world benchmark that shows otherwise, can you please share it? AFAIK there does not exist any hardware for which the performance model for: - non-intrusive doubly-linked lists, - typical object sizes used on these lists (>> 64-bit) - typical operations done on these lists (splice, etc.) would predict a performance difference, and in our case, having replaced unsafe lists with safe list in many large applications, we never were able to measure a difference in application performance, only in the synthetic worst-case micro-benchmarks. So I am truly interested to learn about your use case.
  - quotemstr 5y ago
    You're ignoring the case of a list being densely packed and embedded inside another data structure. If you bloat a data structure with a useless machine word, there are all sorts of ways for that machine word to hurt the resulting program, and you can't just handwave that away. The Linux kernel is made by people who spend weeks to shave one bit off the size of a data structure. Do you really think they'd respond positively to your saying they don't need to do that? You really need to stop assuming what kind of computers other people are programming The larger point here is you don't get to decide whether other people's use cases are legitimate. Either Rust gives you complete control of the machine or it does not. It does not, not in safe mode, but Rust people keep doing this annoying motte and bailey thing about it.
    - volta83 5y ago
      > You're ignoring the case of a list being densely packed and embedded inside another data structure. No, I am not. This conversation is exclusively about non-intrusive doubly-linked lists. If you want to have a conversation about intrusive doubly-linked lists we can have it, but it is a very different data-structure. > You really need to stop assuming what kind of computers other people are programming Every week I touch x86, arm, ppc64, riscv and gpu assembly. I write code for apps daily that run from 16-bit micro controllers to the largest super computers in the world, going through phones, desktops, cloud, etc. I am not assuming what others are programming, but rather talking about what I program for, which include most hardware that anyone can buy today, and quite a bit of hardware that almost no one can even buy, as well as hardware that's not for sale.
jhgb 5y ago
> A doubly-linked list is already space inefficient, it adds 2 pointers per element. ...unless you use the XOR trick to store two pointers in one field?

gpderetta 5y ago

The additional refcount takes space that could be used for the payload that now either needs to spill into the next cacheline or needs to be compressed further. You can still use double linked lists in high performance code, as long as the list traversal doesn't happen on the critical path (or at all).

estebank 5y ago
If you are concerned about high performance/space overhead/cache awareness you wouldn't want to use a linked list in the first place, instead you'd use an arena.
- Jensson 5y ago
  An arena is not a replacement for linked lists. In some cases you can use it as a replacement, but in many cases you can't. So can the idiomatic rust apologists please stop with this? I know you love it the language and wants more people to use it, but these sort of statements doesn't help your case. "Performance is almost the same in real world cases" "You don't really need that data structure anyway" "You can learn how to optimize code later" People come and want to use Rust for some fast code. They know what they want the code to do and want it to be as fast as the code they wrote before, and see how Rust would help them achieve that. The above statements are then wrong or patronizing or completely misses the point.
  - estebank 5y ago
    Linked lists are not good for cache locality, it has nothing to do with the language. It'd be my advice over linked lists even if you were doing it in C. Rust does make doubly linked lists in safe code without reference counting impossible, but I don't the argument that you'd use one due to performance or memory overhead.
    - Jensson 5y ago
      > Linked lists are not good for cache locality That doesn't matter if a solution with good cache locality doesn't exist for your problem.
    - deleted 5y ago
      [deleted]
    - gpderetta 5y ago
      They are not, that's why you would use a flat layout for your primary iteration order. But for any secondary ordering/indexing you might need, if you also need fast insert/removal, chaining in a list can be an option.
  - volta83 5y ago
    The question is fair. Why would you want to use a non-intrusive doubly-linked list? AFAIK there is only one answer: you have very big objects and you need O(1) splice. If you don't have very big objects, or you don't need O(1), pretty much any other data-structure in existence is going to give you much much better performance than a doubly-linked list. For the only use case for which non-intrusive doubly-linked lists are good at, however, there exists no hardware you can buy for which you can measure a performance difference between ref-counting and not ref-counting. This has nothing to do with Rust. The same applies to C++, or Java, or Python, or even C. You can do ref counting on any language, and all these languages run pretty much everywhere. The only thing that Rust gives you over Java, Python, or C here is the possibility to implement a doubly-linked list in safe Rust that will perform the same but that the compiler will prove for you to be memory and thread safe. Sure, Rust also allows you to use unsafe code, and then prove that safe and create a safe wrapper. It even does this for you and provides this in std::List. But what value does this add? It's more work, and it doesn't perform better, and why a significant number of people have argued in the past that adding std::List was a mistake in one form or another.
volta83 5y ago
> The additional refcount takes space that could be used for the payload that now either needs to spill into the next cacheline or needs to be compressed further. It could, but since the cachelines are adjacents the prefetcher will pull subsequent cache lines anyways, and since the objects typically used in doubly-linked lists are very large (much larger than 64-bit), then this doesn't matter on any practical application that I am aware of. Our results of 4% performance increase is for the worst-case that we found. Usually is 1% or less. If you have a real-world benchmark that shows otherwise, can you please share it? AFAIK there does not exist any hardware for which the performance model for: - non-intrusive doubly-linked lists, - typical object sizes used on these lists (>> 64-bit) - typical operations done on these lists (splice, etc.) would predict a performance difference, and in our case, having replaced unsafe lists with safe list in many large applications, we never were able to measure a difference in application performance, only in the synthetic worst-case micro-benchmarks. So I am truly interested to learn about your use case.
- quotemstr 5y ago
  You're ignoring the case of a list being densely packed and embedded inside another data structure. If you bloat a data structure with a useless machine word, there are all sorts of ways for that machine word to hurt the resulting program, and you can't just handwave that away. The Linux kernel is made by people who spend weeks to shave one bit off the size of a data structure. Do you really think they'd respond positively to your saying they don't need to do that? You really need to stop assuming what kind of computers other people are programming The larger point here is you don't get to decide whether other people's use cases are legitimate. Either Rust gives you complete control of the machine or it does not. It does not, not in safe mode, but Rust people keep doing this annoying motte and bailey thing about it.
  - volta83 5y ago
    > You're ignoring the case of a list being densely packed and embedded inside another data structure. No, I am not. This conversation is exclusively about non-intrusive doubly-linked lists. If you want to have a conversation about intrusive doubly-linked lists we can have it, but it is a very different data-structure. > You really need to stop assuming what kind of computers other people are programming Every week I touch x86, arm, ppc64, riscv and gpu assembly. I write code for apps daily that run from 16-bit micro controllers to the largest super computers in the world, going through phones, desktops, cloud, etc. I am not assuming what others are programming, but rather talking about what I program for, which include most hardware that anyone can buy today, and quite a bit of hardware that almost no one can even buy, as well as hardware that's not for sale.

jhgb 5y ago

> A doubly-linked list is already space inefficient, it adds 2 pointers per element. ...unless you use the XOR trick to store two pointers in one field?