3 ms·

I'm confused by your response. You quote the article, but you seem to disagree with it. The author explicitly states that this is a data locality effect. The

by dpark 8y ago

I'm confused by your response. You quote the article, but you seem to disagree with it. The author explicitly states that this is a data locality effect. The access characteristics vary because of cache effects, as the article explicitly states: "When the strings are short...they are more likely to occupy the same cache line.... As the strings get longer...fewer strings will fit inside a cache line. Eventually...you don't gain any significant benefit from locality." > 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.

austincheney 8y ago
If the strings are short and everything always lived in the cache I don't think the author would have posted this in the first place. If the strings are always long and never fit in the cache the performance cannot be related to cache or anything related to cache vs memory access. In this case I don't think the author would have posted about variable performance when accessing the strings from memory if it were something they had not observed. 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.
- dpark 8y ago
  > If the strings are short and everything always lived in the cache I don't think the author would have posted this in the first place. 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.
  - austincheney 8y ago
    Excellent. As somebody who does not write C this is the answer I needed.
    - dpark 8y ago
      Glad to help. 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/lectures/lec15.pdf https://courses.cs.washington.edu/courses/cse378/09wi/lectur...

by dpark 8y ago

austincheney 8y ago

If the strings are short and everything always lived in the cache I don't think the author would have posted this in the first place. If the strings are always long and never fit in the cache the performance cannot be related to cache or anything related to cache vs memory access. In this case I don't think the author would have posted about variable performance when accessing the strings from memory if it were something they had not observed. 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.

dpark 8y ago
> If the strings are short and everything always lived in the cache I don't think the author would have posted this in the first place. 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.
- austincheney 8y ago
  Excellent. As somebody who does not write C this is the answer I needed.
  - dpark 8y ago
    Glad to help. 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/lectures/lec15.pdf https://courses.cs.washington.edu/courses/cse378/09wi/lectur...