7 ms·
How can dereferencing the first character take longer when the string is longer?
- deleted 8y ago[deleted]
- stabbles 8y agoIn C++ with short string optimization short strings are on the stack while longer strings are on the heap. That's the difference between a cache hit and a cache miss.
- foota 8y agoThe article is about C, not C++.
- thisismyaccoun7 8y agoWhich is why s/he specified that the post was about c++ and not c in literally the first two words of the post :)
- paulmooreparks 8y agoThe article is about cache effects on performance, independent of language. The example code just happened to be in C.
- sigi45 8y agoHow does this make a difference? 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.
- Sharlin 8y agoA stack variable is almost always already in the cache.
- jonhohle 8y agoI’m assuming the OP meant that there is a higher likelihood of SSO strings (24 bytes)§ being in the same cache line (64 bytes)§ when they are stored in the same stack frame. 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
- sigi45 8y agoBut I don't create a string on the stack first. First allocation on the heap than probably a copy onto the stack.
- CyberDildonics 8y agoTwo string on the stack are far more likely to be cached at a low cache level and/or prefetched (but probably already cached). 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.
- bostonpete 8y agoHuh? I guess you mean short strings are stored in the string object rather than separately allocated. That memory will only be on the stack if the string itself is...
- austincheney 8y agoI 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. I suspect the speed differences between short and long strings is negligible and possibly not something most tools can detect in isolation. There are second and third order consequences that compound over other operations when executed in a loop though.
- scarface74 8y agoWhen you access an index of an array via a[x], it should only access the memory of: 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.
- 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 agoThe 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.
- 8y ago
- userbinator 8y agoThis is also why data alignment/structure padding can be slower than packing all the data together. Cache usage is very important in CPUs now, because in a lot of cases the bottleneck is the memory. Padding is effectively wasted memory.
- dpark 8y agoIs this true on even x86? On most platforms[1] misaligned access will simply crash your program and you definitely will not execute faster (but you’ll probably terminate faster). On x86 you’ll pay a hefty penalty for the misaligned access and I would expect that it likely costs more than the cache optimization saves (but maybe 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.
- herf 8y agoRemember it takes 100ns to get a value from main memory (after you miss all the caches). With random-access data structures the total size tells you the speed. Here's a test to see how your CPU does: https://github.com/emilk/ram_bench https://github.com/emilk/ram_bench
- scarface74 8y agoSlightly off topic and I feel a little hypocritical for saying this since I’m always railing against the need for every developer to know leetCode and algorithms, but some of the responses make me believe that every developer needs to have at least some understanding of lower level languages like C and/or assembly at some point.