4 ms·

A lot of the trade-offs in picking a fixed size array versus a heap allocated array can be solved with a container that supports small vector optimization! You

A lot of the trade-offs in picking a fixed size array versus a heap allocated array can be solved with a container that supports small vector optimization! You see this in C++'s std::string type, which leads some people to use it for storing binary data. [1] I'm not sure what common STL-ish implementations of the idea exist. In Rust, there's SmallVec, which has configurable storage backing and spills onto the heap when there are too many elements. [2] [1] https://stackoverflow.com/a/21710033/802794 https://stackoverflow.com/a/21710033/802794 [2] https://docs.rs/smallvec/0.6.10/smallvec/struct.SmallVec.html https://docs.rs/smallvec/0.6.10/smallvec/struct.SmallVec.htm...

deleted 7y ago
[deleted]
bullen 7y ago
What is the difference between this "small" vector and a vector?
- QuadDamaged 7y ago
  `SmallVec` allocates a contiguous array in the struct holding the vector itself (so it can be located on the stack), then if the capacity is insufficent, fallbacks to a heap-allocated `Vec` equivalent. The `Vec` struct contains the capacity and used length integers, as well as a pointer to the heap-allocated storage.
- PixelOfDeath 7y ago
  The small vector class contains a static array of a few bytes. And as long as your data fits in it, no extra heap allocation is needed. A vector always does heap allocation, even if you only use a few bytes.
  - Vogtinator 7y ago
    Sounds like small string optimization (SSO), which is common in C++.
  - bullen 7y ago
    Ok, thx! If I use the trick Niklas calls “array with holes” in part 1, will each hole larger than the cache frame result in a cache miss?
martincmartin 7y ago
There's folly's small_vector. https://github.com/facebook/folly/blob/master/folly/docs/small_vector.md https://github.com/facebook/folly/blob/master/folly/docs/sma... High quality, and widely used inside Facebook. It's a shame folly isn't more widely used outside.
- chillee 7y ago
  People are reluctant to use Folly for the same reason people are reluctant to use Boost - except that using Folly also implies a dependency on Boost.
chrisseaton 7y ago
Why doesn't the compiler do this optimisation for small vectors automatically for you?
- corysama 7y ago
  Compilers are extremely limited in how they are allowed to change data layout on your behalf. In C/C++ there’s: per-platform integer sizes (which are easily and usually forced to be consistent), padding between members of structs, alignment of objects, anything else? I think that’s about it. Compilers are definitely not allowed to insert a small buffer into an object. Nor even repurpose an int that’s not being utilized completely. Messing with your data under the hood is blasphemous. Unfortunately data issues have been the top cause of performance problems for a long time and it’s only going to get worse. A cache miss is much, much more expensive than operations people are taught are slow, like divisions, square roots and branches. Meanwhile, in my dozens of interviews with junior programmers I’ve found that the vast majority are only vaguely aware that cache exists at all :(
  - chrisseaton 7y ago
    I don't know if you have more experience than me in C and C++ compiler implementation, but I think you have a lot of options for how you layout memory. The C++ specification doesn't say anything about how objects are laid out does it? ABIs do, but not C++. I've worked with a conforming C implementation that uses Java objects for structs, for example. As long as you match the intended semantics, you can inline a malloc call into an object if you want to.
    - corysama 7y ago
      Well, I know it requires elements to be laid out in the order they are declared, but it is allowed to put gaps between items for alignment. I guess a compiler could insert a 16-byte gap and do whatever it wants in there. I don't expect a great reception for that feature from the community... Then there's the issue of writing a compiler that is smart enough to recognize that you allocate small arrays frequently enough that it's worth it to insert an "alignment wink-wink" buffer into your object :P I do believe there is some work to elide allocations that are short-lived enough that the compiler can strongly guarantee their entire lifetime. For example: inside a small std::vector that lives on the stack (but it's internal buffer would normally be malloced). There's even work on getting this to work in constexpr so that you could have constexpr algorithms allocate temporary memory that does not live past the end of the compile-time algo. However, I was knee-jerking against a wider complaint I've seen frequently along the lines of "Why can't the compiler just optimize my data structures for me to make it go more good?" in terms of AOS to SOA transformations, separating hot-cold data into different arrays, somehow magically getting rid of pointer indirections and other major re-writes. That's a research topic for some libraries and special-purpose languages. But, it's outside of the scope of the C++ compiler.

deleted 7y ago

[deleted]

bullen 7y ago

What is the difference between this "small" vector and a vector?

QuadDamaged 7y ago
`SmallVec` allocates a contiguous array in the struct holding the vector itself (so it can be located on the stack), then if the capacity is insufficent, fallbacks to a heap-allocated `Vec` equivalent. The `Vec` struct contains the capacity and used length integers, as well as a pointer to the heap-allocated storage.
PixelOfDeath 7y ago
The small vector class contains a static array of a few bytes. And as long as your data fits in it, no extra heap allocation is needed. A vector always does heap allocation, even if you only use a few bytes.
- Vogtinator 7y ago
  Sounds like small string optimization (SSO), which is common in C++.
- bullen 7y ago
  Ok, thx! If I use the trick Niklas calls “array with holes” in part 1, will each hole larger than the cache frame result in a cache miss?

martincmartin 7y ago

There's folly's small_vector. https://github.com/facebook/folly/blob/master/folly/docs/small_vector.md https://github.com/facebook/folly/blob/master/folly/docs/sma... High quality, and widely used inside Facebook. It's a shame folly isn't more widely used outside.

chillee 7y ago
People are reluctant to use Folly for the same reason people are reluctant to use Boost - except that using Folly also implies a dependency on Boost.

chrisseaton 7y ago

Why doesn't the compiler do this optimisation for small vectors automatically for you?

corysama 7y ago
Compilers are extremely limited in how they are allowed to change data layout on your behalf. In C/C++ there’s: per-platform integer sizes (which are easily and usually forced to be consistent), padding between members of structs, alignment of objects, anything else? I think that’s about it. Compilers are definitely not allowed to insert a small buffer into an object. Nor even repurpose an int that’s not being utilized completely. Messing with your data under the hood is blasphemous. Unfortunately data issues have been the top cause of performance problems for a long time and it’s only going to get worse. A cache miss is much, much more expensive than operations people are taught are slow, like divisions, square roots and branches. Meanwhile, in my dozens of interviews with junior programmers I’ve found that the vast majority are only vaguely aware that cache exists at all :(
- chrisseaton 7y ago
  I don't know if you have more experience than me in C and C++ compiler implementation, but I think you have a lot of options for how you layout memory. The C++ specification doesn't say anything about how objects are laid out does it? ABIs do, but not C++. I've worked with a conforming C implementation that uses Java objects for structs, for example. As long as you match the intended semantics, you can inline a malloc call into an object if you want to.
  - corysama 7y ago
    Well, I know it requires elements to be laid out in the order they are declared, but it is allowed to put gaps between items for alignment. I guess a compiler could insert a 16-byte gap and do whatever it wants in there. I don't expect a great reception for that feature from the community... Then there's the issue of writing a compiler that is smart enough to recognize that you allocate small arrays frequently enough that it's worth it to insert an "alignment wink-wink" buffer into your object :P I do believe there is some work to elide allocations that are short-lived enough that the compiler can strongly guarantee their entire lifetime. For example: inside a small std::vector that lives on the stack (but it's internal buffer would normally be malloced). There's even work on getting this to work in constexpr so that you could have constexpr algorithms allocate temporary memory that does not live past the end of the compile-time algo. However, I was knee-jerking against a wider complaint I've seen frequently along the lines of "Why can't the compiler just optimize my data structures for me to make it go more good?" in terms of AOS to SOA transformations, separating hot-cold data into different arrays, somehow magically getting rid of pointer indirections and other major re-writes. That's a research topic for some libraries and special-purpose languages. But, it's outside of the scope of the C++ compiler.