3 ms·

> I suspect that in order to access any character index of a given string you must access the entire string and then the specified index. The longer a string th

by dpark 8y ago

> I suspect that in order to access any character index of a given string you must access the entire string and then the specified index. The longer a string the more indexes there are from which to access. 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.

austincheney 8y ago
The locality effect only explains access via cache versus memory. Just a paragraph later the article mentions this: > 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.
- 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.

by dpark 8y ago

austincheney 8y ago

The locality effect only explains access via cache versus memory. Just a paragraph later the article mentions this: > 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.

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.