`StringBackend`: ensure `ends` precedes `buffer` in memory

[Caellian]

As ends and buffer are separately stored, their relative positions can significantly drift away when a lot of strings are interned.

To fix this, their memory should be manually managed as a single growable allocation with two sections (for ends and contents).

This requires a rewrite and likely unsafe code but it would also fix this issue and remove the need to read from both pointers (instead it would be just one).

[Robbepop]

In order to understand you correctly: Do you mean to instead of storing an ends: Vec<usize> and buffer: Vec<u8> separately, you'd store a single raw-byte data: Vec<u8> that contains both, ends and buffer, data?

E.g., buffer data would grow starting from 0 ascending [0...n) and ends data would grow from N descending towards 0? So that the combined buffer would looks roughly like this: [ buffer | ... <nothing> ... | ends ]. And once buffer and ends are about to touch each other we'd regrow the combined buffer? 🤔

While I think this would work and is implementable, I also think that this would significantly increase complexity of the code and won't affect performance at all or too much. Modern CPU caches are very effective at dealing with more than just one buffer. But probably I misunderstood you entirely. So please feel free to explain again.

Also: what exactly is the problem that this is fixing? Potential bugs? Performance?

[Caellian]

That's basically it. It's an improvement suggestion.

While being a tiny bit more complicated, it would remove the need to manage two separate chunks of memory and move them around as more strings get interned. How well it will behave in CPU cache depends on a bunch of things, but a single buffer would certainly behave better from both cache and paging perspective than having two (possibly distant) allocations that are always accessed at the same time.

I feel the current implementation is too simplistic and doesn't really provide any benefit over the other two interning mechanisms. The comparison table says iteration performance is good for this one and bad for buffer backend, but this implementation needs to dereference two pointers from the stack and buffer only has one (and much better cache locality). If BufferBackend didn't have dynamic interned string lengths (which... why not just use u32? who will ever need to intern more than 4 GB of characters for a single string) it would certainly perform faster than StringBackend.

[Robbepop]

The current StringBackend is very simple indeed but in my honest opinion that's usually a good thing. Although, I agree that implementations should not be simple for the sake of simplicity.

Concerning your idea I feel that it won't actually improve the situation with respect to uncached memory accesses. The reason being that this single big buffer still divides ends from string data and thus the distance in memory between the two is still large enough to not fit into a single cache line and thus might cause multiple cache misses. So from a performance perspective I highly doubt that this would actually be an improvement. It might even degrade performance, since the large buffer needs to be resized more often and includes more data, meaning more data that needs to be copied during a vector growth.

Furthermore, I do not think that this is just "a tiny bit more complicated". At least in comparison to the very simple implementation we have today for the StringBackend this would add a lot of complexity.

I think the only way forward is, that you start an experiment and try it out. If it fails we know better. If it is a success and performs better than today's StringBackend and does not add too much complexity, we also know better. I won't guarantee merging it, even if it minimally improves performance in some cases, since complexity is a maintenance fee and should never be added lightly to a codebase. Obviously, if the performance benefits are significant, there is no question that we want to buy this complexity.

If BufferBackend didn't have dynamic interned string lengths (which... why not just use u32? who will ever need to intern more than 4 GB of characters for a single string) it would certainly perform faster than StringBackend.

This is slightly off-topic but I want to still answer it here. The main reason you'd want to use the BufferBackend is that is very efficiently stores strings with near minimal wasted space. Performance is 2nd class for the BufferBackend. While encoding lengths as u32 might yield slightly better performance, most strings have string lengths of less than 256 bytes and thus fit in a single u8 so we are probably better off optimizing this happy path at the cost of a slow unhappy path for huge strings.

The string-interner crate allows you to come up and implement your own backends. So I want to encourage you to try it out and implement your own or modify existing ones and see how they perform. Experiment and let the rest of us know about your results! :)