3 ms·

The other major downside being the extra level of indirection, which could potentially cause an extra cache miss per method call. A drop in the park bucket comp

The other major downside being the extra level of indirection, which could potentially cause an extra cache miss per method call. A drop in the park bucket compared to most other languages, but a serious consideration for many of the areas that C and C++ dominate.

haberman 12y ago
Extra indirection? There is less indirection. With the C++ approach the data is one pointer away but the vtable is two pointers away. With the Rust approach both data and vtable are just one pointer away.
- fgsfdsfgsfds 12y ago
  That's assuming that a "full pointer" (i.e. an unpredictable address to an arbitrary point in heap memory) is the only way to get a reference to an object. What about if you want to stick a bunch of objects in a vector, and iterate over them linearly? In the C++ approach, the data will have a nice linear cache access pattern. In the Rust approach (unless I'm missing something) you'd be storing a vector of (double sized) pointers, to god knows where in heap memory... suffering a cache miss on every access, on average.
  - robinei 12y ago
    Since you are talking about a heterogeneous [edit: homogeneous] array, you would store the concrete structs continously in Rust as well. Rust would also not waste space in the vector for storing a vtable-pointer, and would instead construct fat pointers dynamically when needed (since it knows the type, it knows which vtable to inject in the fat pointer).
    - fgsfdsfgsfds 12y ago
      > you would store the concrete structs continously in Rust as well. Rust would also not waste space in the vector for storing a vtable-pointer, and would instead construct fat pointers dynamically when needed (since it knows the type, it knows which vtable to inject in the fat pointer). Uh, what? How is the compiler just supposed to magically know which of the structures in the array are of what type, without any additional identifying information? I'm assuming that in this optimized case, there's a hidden type field in each struct, that it would use to index into a table of vtable pointers? If so, there you go, that's yet another level of indirection.
      - robinei 12y ago
        I meant to say homogenous array, which I assume you were talking about.
        fgsfdsfgsfds 12y ago
        No, I was talking about iterating over an array of objects calling their virtual functions (or either of the additional cases listed above). Of course it's easy to "do the right thing" with homogeneous arrays, either in the compiler or by hand if need be. But if you're iterating over a homogeneous array, calling the same virtual function on every single one, and your compiler somehow manages to notice this before you do, you probably screwed up in your design somewhere, so that's not the kind of problem I'm talking about. It usually is smarter for performance to do the "data oriented design" thing and break the heterogeneous arrays into separate homogeneous arrays, so that you can potentially avoid a few levels of indirection, hoist loop invariants out, and maybe even make use of SIMD. But the whole point of the conversation was to talk about a nontrivial abstraction that (supposedly) trades performance for clarity. So I gave a scenario that would exercise that overhead.
  - GolDDranks 12y ago
    How would you put or index objects in a vector in C++ if they are virtual / dynamically sized? I'm in impression that unless you have the dynamically sized object behind a pointer, you get object slicing.
    - fgsfdsfgsfds 12y ago
      I didn't say they were dynamically sized. You could either have objects of the same type, but with virtual functions, or you could make a union of all applicable objects (thus guaranteed to be constant sized, at the size of the largest object) and store those in the array/vector, switching on a type enum or calling a function from an inherited base class.
      - haberman 12y ago
        > You could either have objects of the same type, but with virtual functions If objects have the same type, which is statically known, there is no need for virtual functions because the compiler can resolve the specific method implementation at compile-time. > or you could make a union of all applicable objects (thus guaranteed to be constant sized, at the size of the largest object) and store those in the array/vector, switching on a type enum You can do this in both C++ and Rust easily, with equivalent efficiency in both. In Rust you would just use an enum type. This design is generally highly discouraged though, because it requires callers to be aware of all possible "derived classes". My comments were only about the case where you are using true language-level polymorphism.
  - haberman 12y ago
    > That's assuming that a "full pointer" (i.e. an unpredictable address to an arbitrary point in heap memory) is the only way to get a reference to an object. No, it's assuming that a "full pointer" is the only way to get a reference to a polymorphic object. This is true in both C++ and Rust. > What about if you want to stick a bunch of objects in a vector, and iterate over them linearly? You can do this in both C++ and Rust. But you can only put a bunch of objects in a vector if they have a statically-known type. The point of dynamic dispatch is calling methods of an object where you don't statically know its type.

haberman 12y ago

Extra indirection? There is less indirection. With the C++ approach the data is one pointer away but the vtable is two pointers away. With the Rust approach both data and vtable are just one pointer away.

fgsfdsfgsfds 12y ago
That's assuming that a "full pointer" (i.e. an unpredictable address to an arbitrary point in heap memory) is the only way to get a reference to an object. What about if you want to stick a bunch of objects in a vector, and iterate over them linearly? In the C++ approach, the data will have a nice linear cache access pattern. In the Rust approach (unless I'm missing something) you'd be storing a vector of (double sized) pointers, to god knows where in heap memory... suffering a cache miss on every access, on average.
- robinei 12y ago
  Since you are talking about a heterogeneous [edit: homogeneous] array, you would store the concrete structs continously in Rust as well. Rust would also not waste space in the vector for storing a vtable-pointer, and would instead construct fat pointers dynamically when needed (since it knows the type, it knows which vtable to inject in the fat pointer).
  - fgsfdsfgsfds 12y ago
    > you would store the concrete structs continously in Rust as well. Rust would also not waste space in the vector for storing a vtable-pointer, and would instead construct fat pointers dynamically when needed (since it knows the type, it knows which vtable to inject in the fat pointer). Uh, what? How is the compiler just supposed to magically know which of the structures in the array are of what type, without any additional identifying information? I'm assuming that in this optimized case, there's a hidden type field in each struct, that it would use to index into a table of vtable pointers? If so, there you go, that's yet another level of indirection.
    - robinei 12y ago
      I meant to say homogenous array, which I assume you were talking about.
      - fgsfdsfgsfds 12y ago
        No, I was talking about iterating over an array of objects calling their virtual functions (or either of the additional cases listed above). Of course it's easy to "do the right thing" with homogeneous arrays, either in the compiler or by hand if need be. But if you're iterating over a homogeneous array, calling the same virtual function on every single one, and your compiler somehow manages to notice this before you do, you probably screwed up in your design somewhere, so that's not the kind of problem I'm talking about. It usually is smarter for performance to do the "data oriented design" thing and break the heterogeneous arrays into separate homogeneous arrays, so that you can potentially avoid a few levels of indirection, hoist loop invariants out, and maybe even make use of SIMD. But the whole point of the conversation was to talk about a nontrivial abstraction that (supposedly) trades performance for clarity. So I gave a scenario that would exercise that overhead.
- GolDDranks 12y ago
  How would you put or index objects in a vector in C++ if they are virtual / dynamically sized? I'm in impression that unless you have the dynamically sized object behind a pointer, you get object slicing.
  - fgsfdsfgsfds 12y ago
    I didn't say they were dynamically sized. You could either have objects of the same type, but with virtual functions, or you could make a union of all applicable objects (thus guaranteed to be constant sized, at the size of the largest object) and store those in the array/vector, switching on a type enum or calling a function from an inherited base class.
    - haberman 12y ago
      > You could either have objects of the same type, but with virtual functions If objects have the same type, which is statically known, there is no need for virtual functions because the compiler can resolve the specific method implementation at compile-time. > or you could make a union of all applicable objects (thus guaranteed to be constant sized, at the size of the largest object) and store those in the array/vector, switching on a type enum You can do this in both C++ and Rust easily, with equivalent efficiency in both. In Rust you would just use an enum type. This design is generally highly discouraged though, because it requires callers to be aware of all possible "derived classes". My comments were only about the case where you are using true language-level polymorphism.
- haberman 12y ago
  > That's assuming that a "full pointer" (i.e. an unpredictable address to an arbitrary point in heap memory) is the only way to get a reference to an object. No, it's assuming that a "full pointer" is the only way to get a reference to a polymorphic object. This is true in both C++ and Rust. > What about if you want to stick a bunch of objects in a vector, and iterate over them linearly? You can do this in both C++ and Rust. But you can only put a bunch of objects in a vector if they have a statically-known type. The point of dynamic dispatch is calling methods of an object where you don't statically know its type.