5 ms·

> an array of strings is now stored in contiguous memory, which is great for memory cache hitrates, which often delivers whole factors of speedup. How do they

> an array of strings is now stored in contiguous memory, which is great for memory cache hitrates, which often delivers whole factors of speedup. How do they do that? As string lengths can vary. One way might be to store the continuous strings in memory and then maintain an array of pointers to those strings. But then we are back to pointers. Searched google. Didn't find anything.

zabzonk 5y ago
This is not an article written by someone that knows what they are talking about.
- exdsq 5y ago
  This is written by Bert Hupert, the founder of PowerDNS among other things. That's at least 20 years of solid C++ engineering work.
bla3 5y ago
It's called the "short string optimization".
kjksf 5y ago
What he meant that if you have an array of strings that implement Small String Optimization AND those strings are short (i.e. below the threshold for Small String Optimization) THEN they'll be contiguous in memory. But you can be smarter than that. As it happens, I just implemented "vector of strings" where all strings are contiguous in memory. The code: https://github.com/sumatrapdfreader/sumatrapdf/commit/bc83112ff0b9607f1155e6b923001f2ea0e0286c#diff-35f8652bb542c1e449b60087a004e5b479a92f3a1f70f748da1fbada6813148eR2704 https://github.com/sumatrapdfreader/sumatrapdf/commit/bc8311... The basic idea is like you said: you keep strings contiguously in memory and maintain a separate array of pointers to each string. Except it's not a pointer but u32 index into that block of memory. Even if those were pointers, not the u32 indexes, it would still be cache friendly. The point is that strings are close together. If each string was allocated with malloc() then you don't control where they are allocated. In the worst case each string could end up in a separate cache line, which would be much slower if you were to iterate over all strings.
moth-fuzz 5y ago
Pointers are not slow because they are pointers. Pointers are slow because (usually) they point to random locations in memory, incurring cache misses. Pointers that point to contiguous memory can be just as fast as that same memory being accessed via an array directly, as long as the data stays contiguous.
- habibur 5y ago
  > as long as the data stays contiguous The data will stay contiguous as long as it's constant/read only. But as soon as you start to use it and change it for doing some real work, it will get scattered.

zabzonk 5y ago

This is not an article written by someone that knows what they are talking about.

exdsq 5y ago
This is written by Bert Hupert, the founder of PowerDNS among other things. That's at least 20 years of solid C++ engineering work.

bla3 5y ago

It's called the "short string optimization".

kjksf 5y ago

What he meant that if you have an array of strings that implement Small String Optimization AND those strings are short (i.e. below the threshold for Small String Optimization) THEN they'll be contiguous in memory. But you can be smarter than that. As it happens, I just implemented "vector of strings" where all strings are contiguous in memory. The code: https://github.com/sumatrapdfreader/sumatrapdf/commit/bc83112ff0b9607f1155e6b923001f2ea0e0286c#diff-35f8652bb542c1e449b60087a004e5b479a92f3a1f70f748da1fbada6813148eR2704 https://github.com/sumatrapdfreader/sumatrapdf/commit/bc8311... The basic idea is like you said: you keep strings contiguously in memory and maintain a separate array of pointers to each string. Except it's not a pointer but u32 index into that block of memory. Even if those were pointers, not the u32 indexes, it would still be cache friendly. The point is that strings are close together. If each string was allocated with malloc() then you don't control where they are allocated. In the worst case each string could end up in a separate cache line, which would be much slower if you were to iterate over all strings.

moth-fuzz 5y ago

Pointers are not slow because they are pointers. Pointers are slow because (usually) they point to random locations in memory, incurring cache misses. Pointers that point to contiguous memory can be just as fast as that same memory being accessed via an array directly, as long as the data stays contiguous.

habibur 5y ago
> as long as the data stays contiguous The data will stay contiguous as long as it's constant/read only. But as soon as you start to use it and change it for doing some real work, it will get scattered.