The articel states that it becomes slower when two strings don't fit together in one cache line anymore. That is independend on using heap or stack.

Two small strings allocated on the heap at different times have a lower likelihood of being in the same cache line. Even within consecutive mallocs the addresses might not fall within the same line. Unless the memory is allocated exlipicitly for locality, there’s a higher likelihood (>=0) that memory fragmentation causes the allocations to be split on different lines.

Ultimately, this can be controlled on either the heap or stack, SSO seems to be optimizing for the stack case, which probably works pretty well for most cases (especially for oblivious developers).

§ on recent x86-64 processors

First allocation on the heap than probably a copy onto the stack.

A noticeable difference is much more likely to be because a string is too big and moved to the heap, which is in a different part of memory and thus not cached. Also there is the translation look aside buffer which caches the virtual memory to real memory address lookup. This also needs to be done on cold pages of memory and be expensive since it requires looking up in to the virtual memory table.

a + sizeof({type of a}) * x.

The compiler has no concept of a “string” in this context. A string is just a null terminated character array.

Are you saying that you believe accessing a single character (index) requires reading the entire string? This is incorrect. In C, you might have to read the first N characters in order to read the N+1th character, but that’s a bounds-checking cost due to null-terminated strings(and is avoided if the length is known). And in any case, you need not access anything past the character you wish to read.

The article answers the question. It’s a well-known locality effect.

> Reading the first character from the string adds another memory access, and the characteristics of that memory access vary depending on the length of the string.

Provided access were always to memory, such that strings in an array of strings exceed cache size, it would not be a locality issue and string length would still result in a performance variance.

> Provided access were always to memory, such that strings in an array of strings exceed cache size, it would not be a locality issue and string length would still result in a performance variance

If you always miss the cache, then performance will no longer vary with string length.

Locality only applies in a third middle state when some strings are short enough to fit in the cache and when others are not. In this case the degrading performance is predictable to the number of memory look ups. If the string is in cache there are no memory look ups. If it is in memory there are two look ups: one of the string and a second for the index upon that string. Finally the article mentions the second look up varies according to the length of the string, which suggests different performances for strings of different length even if both reside in memory.

Its not that I disagree with the article, but rather the finality of assumptions drawn from the article. Logically you cannot access a specified index on a string without first accessing the string and then navigating to the given index. There is instruction time in all of that and it isn't solely confined to locality.

Raymond Chen didn't post this because he had trouble understanding the behavior. He posted this as an exercise for his readers. There is zero chance that Raymond Chen doesn't fully understand this behavior.

Also, the strings being short doesn't mean they're all in the cache. If your strings are 4 chars each but you're storing a billion of them, you won't have them all in cache, but cache effects will still matter.

> Locality only applies in a third middle state when some strings are short enough to fit in the cache and when others are not. In this case the degrading performance is predictable to the number of memory look ups. If the string is in cache there are no memory look ups. If it is in memory there are two look ups: one of the string and a second for the index upon that string. Finally the article mentions the second look up varies according to the length of the string, which suggests different performances for strings of different length even if both reside in memory.

Look at the code again. All the strings have the same length for a given execution. There is no case here where "some strings are short enough to fit in the cache and when others are not".

I think your mental model of cache behavior and why it's relevant here is wrong. The question isn't whether all the strings fit into cache. Nor whether individual strings are "too large" to fit into the cache. The former is uninteresting and the latter is irrelevant because we aren't looking at the entire string, only the first character, which will most certainly fit in the cache.

Modern CPUs will pull in an entire cache line at a time. If you access the first character of a string, you'll pull in the surrounding N bytes as well. If your string is long, you'll only pull in bytes from that string. (You will also pull in the bytes preceding your string if your string doesn't begin on the start of the cache line.) If it's short and other strings are adjacent, you'll pull in bytes from the next string (or strings) as well. This is where the data locality bit matters. If your strings are very short and your layout is sequential, the cache is extremely efficient at minimizing main memory lookups, and your comparison of one string will pull several following strings into the cache "for free".

> Logically you cannot access a specified index on a string without first accessing the string and then navigating to the given index.

I don't understand what your mental model of string access looks like, but accessing a character within a string in C is literally a single pointer addition and a dereference. There is no "navigating" nor is there any meaningful notion of "accessing the string". You access characters individually by offsetting a pointer and dereferencing.

They key thing I realized after I wrote my last comment is that you've (probably) been thinking in terms of an object cache. Your comments make a lot of sense if the cache is something like a key/value store that you shove an address and an object into. If you can't fit the string in the cache, it won't be in the cache at all. If you want to access a character in the string, you need to access the string first (pull it from the cache) and then access the character you want.

CPU caches don't map very well to that model. CPU caches make a lot more sense if you think about the system memory as one enormous array of contiguous bytes. The CPU doesn't know anything about objects. It just knows about different-sized chunks of bytes (pages, cache lines) that it can read from the array (system memory). The cache doesn't hold objects (and cannot, because the CPU has no concept of an object). The cache just holds a bit of memory pulled from the array. The benefits of CPU caches come from recency (you'll probably touch the same memory again very soon) and data locality (the CPU will already read in an entire chunk, which is awesome if you're going to touch nearby memory). Your strings are embedded in this enormous array. The "chunking" behavior means that adjacent strings will be loaded together if they're short enough. The shorter, the better, as observed here.

From a quick look, this appears to be one of the better explanations of CPU caches online:

https://courses.cs.washington.edu/courses/cse378/09wi/lectur...

With the usual malloc you have to subtract 8 from 63, as malloc reserves a word at the front. With _independent_comalloc for efficient array storage not.

Of course you can probably optimize your struct packing anyway. Shuffling members around can get a lot of benefit without a bunch of internal padding, though you might still have some trailing padding.

[1] I guess these days the platforms are essentially just x86 and ARM.

Alignment matter much more when using atomics. X64 can do unaligned atomic access although (I think) there is a penalty for crossing the cache line boundary with atomics. Also there is an issue of 'false sharing' - two threads needing to sync cache lines even though the bytes they are accessing don't overlap.

128 bit (16 byte) atomic operations need to be aligned on 128 bit boundaries or they will crash.

(if anyone sees something inaccurate here feel free to correct me)

Someone should make a lockless library and call it, "Family." Most people will think it is a reference to the Fast and the Furious, but it would actually be a reference to Dune.

Also, isn't it a pretty strong signal that there's so much talk of cache oblivious algorithms and cache usage? As in an olfactory signal. If we are warping our algorithms and coding so much around it, isn't this a sign that the memory abstraction with the current caching scheme is an overly leaky abstraction?

This, and the abuse of memory as a means of communicating between threads running on different CPU cores are two areas that seem very much like a signal that a paradigm shift of some kind is due on the level of the abstract model of the hardware.

No, because we don't code our programs in the 'language of performance'. Performance of algorithms is always exterior to our abstractions. There's no way to talk about performance without talking about all the things that 'leak'.

Conversely, if you design your algorithms with no consideration for performance, you will not care what the cache does. If you design your algorithms to maximize something they don't literally encode, then you're escaping the abstraction by definition, and side channels become relevant.

In other words, the abstractions don't leak, they are just not up to the task of modeling optimal performance, so you have to use your human brain to do it on the side.

From a certain point of view.

In other words, the abstractions don't leak, they are just not up to the task of modeling optimal performance

If the performance becomes pathological, to the point where the app or system is unusable, then from the point of view of the users, the abstraction is leaking.

Let me put it this way. Maybe a flat Random Access Machine isn't the best mental model for certain coding tasks? Maybe there's a way we could have a cleaner abstract model that makes the pathologies visible, yet is a bit more abstract than just thinking about the actual cache?

Here's a test to see how your CPU does: https://github.com/emilk/ram_bench