5 ms·

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

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.

Jensson 5y ago
> Why would you want to use a non-intrusive doubly-linked list? Or you have a list of objects with many references to parts inside the list and you want to rearrange those parts from those references at O(1) speed. Lets say I have pointers two elements A and B in the list. I now want to say that B should come after A, I can do this easily in O(1) time with this with no overhead and all references sees this update instantly. Lets say I put integers in these so the data is embedded in the list. You have many other places referring to elements inside the list and you want those references to track the objects position. How would you solve this using a Rust compatible data structure? > The question is fair. No it is not. Experienced people almost surely knows their use case better than you do. > there exists no hardware you can buy for which you can measure a performance difference between ref-counting and not ref-counting. Are you kidding me? Seriously, I don't see how you could believe this unless you never tried to use ref counting to replace other code and compare the performance difference.
- volta83 5y ago
  > Lets say I have pointers two elements A and B in the list. I now want to say that B should come after A, I can do this easily in O(1) time with this with no overhead and all references sees this update instantly. You can do this with a vector of pointers as well, at lower space complexity cost (1 pointer per element instead of two), and a lower runtime cost (1 swap of two pointers instead of swapping 4 pointers). Such a data-structure has also other advantages, like higher cache efficiency, etc.
  - Jensson 5y ago
    You can't move an element in a vector in O(1) time. Swapping isn't the same as moving, you'd have to move n elements to make room for the new one.
    - volta83 5y ago
      You mentioned changing the order of two elements in a list, such that one comes after the other. With a vector of pointers to the elements (C++ std::vector<T*>) this can be easily done in O(1) as I explained above. If now that I've proven you wrong, you want to change the problem to something else, feel free to state your new problem, and I'll proceed to prove you wrong again.
      - Jensson 5y ago
        > You mentioned changing the order of two elements in a list, such that one comes after the other. Putting B after A is not swapping them, it is putting the element B so it is right after A. You could technically interpret it as you did, but only a contrarian would do that. If you want more people to support rust then you should stop being a contrarian. If you want me and others to assume that the Rust community is full of hard to work with people then please continue, but that wont make people more likely to pick up rust. If instead of behaving like you do here people would just say "Sure thing, in order to get that performance in rust you just do X and Y!" I bet people would be way more supportive of rust. But if working in the language means that people like you will come and argue like this then why not just write a C library, and then someone will write a Rust wrapper and people are happy? While if they'd write it in unsafe Rust people would come and complain like hell.
PaulDavisThe1st 5y ago
The objects don't have to be big. They have to be expensive to copy. These are related but not always identical. Objects that refer to things in the real world (or in a complex model) can be either actually non-copyable or just hard to copy.

Jensson 5y ago

> Why would you want to use a non-intrusive doubly-linked list? Or you have a list of objects with many references to parts inside the list and you want to rearrange those parts from those references at O(1) speed. Lets say I have pointers two elements A and B in the list. I now want to say that B should come after A, I can do this easily in O(1) time with this with no overhead and all references sees this update instantly. Lets say I put integers in these so the data is embedded in the list. You have many other places referring to elements inside the list and you want those references to track the objects position. How would you solve this using a Rust compatible data structure? > The question is fair. No it is not. Experienced people almost surely knows their use case better than you do. > there exists no hardware you can buy for which you can measure a performance difference between ref-counting and not ref-counting. Are you kidding me? Seriously, I don't see how you could believe this unless you never tried to use ref counting to replace other code and compare the performance difference.

volta83 5y ago
> Lets say I have pointers two elements A and B in the list. I now want to say that B should come after A, I can do this easily in O(1) time with this with no overhead and all references sees this update instantly. You can do this with a vector of pointers as well, at lower space complexity cost (1 pointer per element instead of two), and a lower runtime cost (1 swap of two pointers instead of swapping 4 pointers). Such a data-structure has also other advantages, like higher cache efficiency, etc.
- Jensson 5y ago
  You can't move an element in a vector in O(1) time. Swapping isn't the same as moving, you'd have to move n elements to make room for the new one.
  - volta83 5y ago
    You mentioned changing the order of two elements in a list, such that one comes after the other. With a vector of pointers to the elements (C++ std::vector<T*>) this can be easily done in O(1) as I explained above. If now that I've proven you wrong, you want to change the problem to something else, feel free to state your new problem, and I'll proceed to prove you wrong again.
    - Jensson 5y ago
      > You mentioned changing the order of two elements in a list, such that one comes after the other. Putting B after A is not swapping them, it is putting the element B so it is right after A. You could technically interpret it as you did, but only a contrarian would do that. If you want more people to support rust then you should stop being a contrarian. If you want me and others to assume that the Rust community is full of hard to work with people then please continue, but that wont make people more likely to pick up rust. If instead of behaving like you do here people would just say "Sure thing, in order to get that performance in rust you just do X and Y!" I bet people would be way more supportive of rust. But if working in the language means that people like you will come and argue like this then why not just write a C library, and then someone will write a Rust wrapper and people are happy? While if they'd write it in unsafe Rust people would come and complain like hell.

PaulDavisThe1st 5y ago

The objects don't have to be big. They have to be expensive to copy. These are related but not always identical. Objects that refer to things in the real world (or in a complex model) can be either actually non-copyable or just hard to copy.