4 ms·

> Non-trivial data structures are often just a bunch of arrays/maps with additional semantics This might be fine for code which consumes data structures implem

> Non-trivial data structures are often just a bunch of arrays/maps with additional semantics This might be fine for code which consumes data structures implemented by other people. The approach is not good when you actually need to implement data structures in your program. In modern world this is especially bad for a low-level language (marketed as high performance, BTW) because the gap between memory latency and compute performance is now huge. You do need efficient data structures, which often implies developing custom ones for specific use cases. This is required to saturate CPU cores as opposed to stalling on RAM latency while chasing pointers, or on cache coherency protocol while incrementing/decrementing reference counters from multiple CPU cores. Interestingly, neither C++ nor C# has that boundary, for different reasons: C++ is completely unsafe, and safe C# supports almost all data structures (except really weird ones like XOR linked lists) because GC.

jltsiren 2y ago
I used to think like that. Then C++11 arrived, and I realized I could get effectively the same performance with containers and move semantics, while spending less effort on writing and debugging the code. If you need an array for your custom data structure, a standard library vector is almost always good enough. Associative arrays are a bit more tricky, but you should be able to find a handful of map implementations that cover most of your needs. And when you need a custom one, you can often implement it on top of the standard library vector.
- ryandrake 2y ago
  The C++ Standard Library containers are very good and generic, and almost always the right tool to reach for. People are finally giving up on that notion that their own custom linked list is so much better than <list>. My estimate is that out of all the C++ programmers, 1% of them think that the C++ standard containers are not appropriate for their application, and only 1% of that 1% is right, due to their extremely specialized application needs.
- Const-me 2y ago
  > I could get effectively the same performance with containers and move semantics When I’m happy with the level of performance delivered by idiomatic C++ and standard collections, I tend to avoid C++ all together because I also proficient with C# which is even faster to write and debug. But sometimes I want more performance. An example from my day job is a multi-step numerical simulation which needs to handle grids of 200M nodes. When processing that amount of data, standard collections are suboptimal. I’m not using std::vector because I don’t need them to grow and I want to allocate these huge buffers bypassing C heap i.e. page-aligned blocks of memory zero initialized by the OS.
  - almostgotcaught 2y ago
    > proficient with C# which is even faster to write and debug. I don't get it - why are we ignoring the fact that C# necessarily implies distributing CLR? NativeAOT doesn't work for everything.
    - Const-me 2y ago
      On AMD64 Windows, .NET 8.0 runtime takes 31.7 MB to download, and 70.7 MB on disk. On ARM64 Linux, the numbers are 28.4 MB and 75.0 MB, respectively. For that amount of data, both internet bandwidth and disk space are rather cheap these days?
    - pjmlp 2y ago
      As usual the typical argument that if it doesn't cover 100% of everything it isn't good enough. There are plenty of use cases where NativeAOT works perfectly fine, and is getting better with each .NET release.
      - almostgotcaught 2y ago
        > As usual the typical argument that if it doesn't cover 100% of everything it isn't good enough. This text > When I’m happy with the level of performance delivered by idiomatic C++ and standard collections, I tend to avoid C++ all together because I also proficient with C# which is even faster to write and debug. very strongly implies that they're completely interchangeable. They're not. It's as simple as that. Sometimes it's hard to keep track of whether I work in software or politics.
SkiFire13 2y ago
> You do need efficient data structures, which often implies developing custom ones for specific use cases. You are assuming you can't do this with those vecs/maps. But you can! That's what the "additional semantics" are. They will be slightly slower due to often using indexes instead of raw pointer, which requires a bound check and an addition to get the pointer, and sometimes a reallocation, but they won't be that slow. Surely they will be faster than C#, which you claim can implement those same data structures efficiently. You also often get the benefit of better cache locality due to packing everything together, meaning it could even be faster.
- estebank 2y ago
  > They will be slightly slower due to often using indexes instead of raw pointer, which requires a bound check and an addition to get the pointer, and sometimes a reallocation, but they won't be that slow. This is not a fundamental requirement, though. Assuming arena-like behavior, the index will be constructed/provided by the arena itself, so the bounds check can be safely ellided by-construction. Reallocation cost of the entire arena could be expensive, but if that is a cost you'd want to ammortize down to a new allocation, the arena could be implemented as an extensible list of non-growable arenas: every time an arena is full, you append another. This can be an issue if you don't keep track of deletions/tombstones or can't afford a compaction step to keep memory usage down, but in practice having all of these requirements at once is not as common.

jltsiren 2y ago

I used to think like that. Then C++11 arrived, and I realized I could get effectively the same performance with containers and move semantics, while spending less effort on writing and debugging the code. If you need an array for your custom data structure, a standard library vector is almost always good enough. Associative arrays are a bit more tricky, but you should be able to find a handful of map implementations that cover most of your needs. And when you need a custom one, you can often implement it on top of the standard library vector.

ryandrake 2y ago
The C++ Standard Library containers are very good and generic, and almost always the right tool to reach for. People are finally giving up on that notion that their own custom linked list is so much better than <list>. My estimate is that out of all the C++ programmers, 1% of them think that the C++ standard containers are not appropriate for their application, and only 1% of that 1% is right, due to their extremely specialized application needs.
Const-me 2y ago
> I could get effectively the same performance with containers and move semantics When I’m happy with the level of performance delivered by idiomatic C++ and standard collections, I tend to avoid C++ all together because I also proficient with C# which is even faster to write and debug. But sometimes I want more performance. An example from my day job is a multi-step numerical simulation which needs to handle grids of 200M nodes. When processing that amount of data, standard collections are suboptimal. I’m not using std::vector because I don’t need them to grow and I want to allocate these huge buffers bypassing C heap i.e. page-aligned blocks of memory zero initialized by the OS.
- almostgotcaught 2y ago
  > proficient with C# which is even faster to write and debug. I don't get it - why are we ignoring the fact that C# necessarily implies distributing CLR? NativeAOT doesn't work for everything.
  - Const-me 2y ago
    On AMD64 Windows, .NET 8.0 runtime takes 31.7 MB to download, and 70.7 MB on disk. On ARM64 Linux, the numbers are 28.4 MB and 75.0 MB, respectively. For that amount of data, both internet bandwidth and disk space are rather cheap these days?
  - pjmlp 2y ago
    As usual the typical argument that if it doesn't cover 100% of everything it isn't good enough. There are plenty of use cases where NativeAOT works perfectly fine, and is getting better with each .NET release.
    - almostgotcaught 2y ago
      > As usual the typical argument that if it doesn't cover 100% of everything it isn't good enough. This text > When I’m happy with the level of performance delivered by idiomatic C++ and standard collections, I tend to avoid C++ all together because I also proficient with C# which is even faster to write and debug. very strongly implies that they're completely interchangeable. They're not. It's as simple as that. Sometimes it's hard to keep track of whether I work in software or politics.

SkiFire13 2y ago

> You do need efficient data structures, which often implies developing custom ones for specific use cases. You are assuming you can't do this with those vecs/maps. But you can! That's what the "additional semantics" are. They will be slightly slower due to often using indexes instead of raw pointer, which requires a bound check and an addition to get the pointer, and sometimes a reallocation, but they won't be that slow. Surely they will be faster than C#, which you claim can implement those same data structures efficiently. You also often get the benefit of better cache locality due to packing everything together, meaning it could even be faster.

estebank 2y ago
> They will be slightly slower due to often using indexes instead of raw pointer, which requires a bound check and an addition to get the pointer, and sometimes a reallocation, but they won't be that slow. This is not a fundamental requirement, though. Assuming arena-like behavior, the index will be constructed/provided by the arena itself, so the bounds check can be safely ellided by-construction. Reallocation cost of the entire arena could be expensive, but if that is a cost you'd want to ammortize down to a new allocation, the arena could be implemented as an extensible list of non-growable arenas: every time an arena is full, you append another. This can be an issue if you don't keep track of deletions/tombstones or can't afford a compaction step to keep memory usage down, but in practice having all of these requirements at once is not as common.