News for hackers. Stuff that matters.
Re:Data Structures Part 3: Arrays of Arrays by bullen on Tuesday October 01, 2019 @03:16AM (#21122782)
What is the difference between this "small" vector and a vector?
Re:Data Structures Part 3: Arrays of Arrays by PixelOfDeath on Tuesday October 01, 2019 @05:08AM (#21123428)
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.
Re:Data Structures Part 3: Arrays of Arrays by bullen on Tuesday October 01, 2019 @08:05AM (#21124371)
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?

Re:Data Structures Part 3: Arrays of Arrays by Vogtinator on Tuesday October 01, 2019 @07:15AM (#21124101)
Sounds like small string optimization (SSO), which is common in C++.
Re:Data Structures Part 3: Arrays of Arrays by QuadDamaged on Tuesday October 01, 2019 @04:51AM (#21123345)
`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.