4 ms·

> You can, but not without introducing runtime overhead relative to C and C++, e.g., by forcing reference-counting where none would be necessary in C. The runt

> You can, but not without introducing runtime overhead relative to C and C++, e.g., by forcing reference-counting where none would be necessary in C. The runtime overhead is minimal. 96% of it comes from the pointer indirection in the linked list, and this you have either way. Last time I benchmarked, the checks made the list 4% slower, which is acceptable for many, since doubly-linked lists are already very slow. This 4% is buying you a correctness proof that your list API cannot introduce undefined behavior. If you write this doubly-linked list abstraction in safe Rust, and make a mistake, the resulting code will still not have undefined behavior. C and C++, even paying this 4% performance cost, do not provide this guarantee, which is valuable to many. Unsafe code that removes this 4% runtime overhead is an optimization. The fact that you can remove this overhead by providing a safe wrapper over unsafe code is a selling point of Rust, but learning how to write such optimized code without learning first what it takes to make it correct IMO completely misses the point of Rust. It is very easy to write broken safe Rust abstractions over broken unsafe code. At that point, you are in a worse place than C or C++, since you are paying many costs for introducing Rust in a project, but leaving the most valuable feature off the table (correctness, lack of segfaults, lack of data-races, etc.).

gpderetta 5y ago
Reference counting also adds per-element space overhead. Also linked lists are often [1] used in C and C++ for intrusive chaining of nodes otherwise owned by other data structures and the reference counting would either impose overhead to those other datastrucutres or be pointless. [1] In fact I would say this is very common at least in C++ as linked lists make otherwise very poor datastructures by themselves.
- volta83 5y ago
  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.
Jensson 5y ago
> learning how to write such optimized code without learning first what it takes to make it correct IMO completely misses the point of Rust. This culture is why rust will never replace C++ and why C++ will never replace C. You can write the same computations in C++ as in C, and in Rust as in C++, but it isn't "idiomatic" so people are really afraid to do it because it will get harshly rejected by the community.
- volta83 5y ago
  The premise that Rust does not intend to replace C and C++ is not true. Rust is designed to mesh with existing C and C++ code bases well, which is why many large projects support writing code in Rust (Chrome, Firefox, Linux, Windows, etc.). Your claim that you need to learn all low level details first is also not true. There are ~20 million programmers in the world, and about ~16 million of those are Javascript programmers. Many of them don't know and don't need to know the difference between the stack and the heap. Many of them regularly optimize their Javascript hotspots by re-writing them in Rust and compiling it to webassembly. And almost all of them benefit from Javascript libraries that do this internally. Rust is for many of them the ramp up into lower-level systems programming, and this is one of the reasons the Rust project has so many contributors. Rust enables Javascript programmers to actually hack on the Rust compiler, Firefox, etc. This is something that C and C++ never achieved, and one of the main reasons for the Linux kernel to want to use Rust (they want to attract more junior developers to increase the developer base and make the project more accessible). Your tone that the large majority of programmers in the world are somehow "doing programming wrong" by learning higher-level and safe languages first, and delving into low-level details as they need to, sounds very elitist and I personally find it disgusting.
  - Jensson 5y ago
    > The premise that Rust does not intend to replace C and C++ is not true. My point was that Rust wont replace C and C++ as long as the Rust community is as it is now. And from your comments it seems like Rust isn't intended to replace C or C++, but act as a low level language for people who don't know how to write low level code, like javascript programmers. > Your tone that the large majority of programmers in the world are somehow "doing programming wrong" by learning higher-level and safe languages first, and delving into low-level details as they need to, sounds very elitist and I personally find it disgusting. I didn't say that everyone has to learn rust by learning how to write the low level parts. I am saying that if someone wants to learn how to write low level parts of rust rather than the safe parts because they are used to writing performance critical bits of code in C or C++ then you shouldn't discourage them from doing that. Please don't put words in my mouth.

gpderetta 5y ago

Reference counting also adds per-element space overhead. Also linked lists are often [1] used in C and C++ for intrusive chaining of nodes otherwise owned by other data structures and the reference counting would either impose overhead to those other datastrucutres or be pointless. [1] In fact I would say this is very common at least in C++ as linked lists make otherwise very poor datastructures by themselves.

volta83 5y ago
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.

Jensson 5y ago

> learning how to write such optimized code without learning first what it takes to make it correct IMO completely misses the point of Rust. This culture is why rust will never replace C++ and why C++ will never replace C. You can write the same computations in C++ as in C, and in Rust as in C++, but it isn't "idiomatic" so people are really afraid to do it because it will get harshly rejected by the community.

volta83 5y ago
The premise that Rust does not intend to replace C and C++ is not true. Rust is designed to mesh with existing C and C++ code bases well, which is why many large projects support writing code in Rust (Chrome, Firefox, Linux, Windows, etc.). Your claim that you need to learn all low level details first is also not true. There are ~20 million programmers in the world, and about ~16 million of those are Javascript programmers. Many of them don't know and don't need to know the difference between the stack and the heap. Many of them regularly optimize their Javascript hotspots by re-writing them in Rust and compiling it to webassembly. And almost all of them benefit from Javascript libraries that do this internally. Rust is for many of them the ramp up into lower-level systems programming, and this is one of the reasons the Rust project has so many contributors. Rust enables Javascript programmers to actually hack on the Rust compiler, Firefox, etc. This is something that C and C++ never achieved, and one of the main reasons for the Linux kernel to want to use Rust (they want to attract more junior developers to increase the developer base and make the project more accessible). Your tone that the large majority of programmers in the world are somehow "doing programming wrong" by learning higher-level and safe languages first, and delving into low-level details as they need to, sounds very elitist and I personally find it disgusting.
- Jensson 5y ago
  > The premise that Rust does not intend to replace C and C++ is not true. My point was that Rust wont replace C and C++ as long as the Rust community is as it is now. And from your comments it seems like Rust isn't intended to replace C or C++, but act as a low level language for people who don't know how to write low level code, like javascript programmers. > Your tone that the large majority of programmers in the world are somehow "doing programming wrong" by learning higher-level and safe languages first, and delving into low-level details as they need to, sounds very elitist and I personally find it disgusting. I didn't say that everyone has to learn rust by learning how to write the low level parts. I am saying that if someone wants to learn how to write low level parts of rust rather than the safe parts because they are used to writing performance critical bits of code in C or C++ then you shouldn't discourage them from doing that. Please don't put words in my mouth.