3 ms·
I think it's mainly cache effects; things in heap memory tend to be more spread out, and that hurts spatial locality which is the basis of caching. The indirect
by unwind 10y ago
I think it's mainly cache effects; things in heap memory tend to be more spread out, and that hurts spatial locality which is the basis of caching. The indirection is part of this too, since "jumping around" following pointers can pollute the cache which in turn can make subsequent accesses slower.
Sure, the allocator itself can be expensive, and that's certainly important if you're doing "too many" allocations, but in general I think it's worse caching that matters the most.
- twoodfin 10y agoThis is important to keep in mind when looking at profiling reports: The cost of cache effects (both I and D!) can be spread throughout the critical path. Even if your profile shows your allocator being executed only in (say) 2% of the samples, if what it's doing during that time is pushing lots of useful instructions or data out of the fastest caches into which they otherwise would fit, the total cost of that allocation is likely much greater, but hard to pinpoint.
- ronjouch 10y agoThanks unwind/twoodfin! @twoodfin, can you precise what you mean by "cache effects (both I and D!)" ? (Indirect and Direct? By Indirect you mean Associative and by Direct you mean Direct Mapped as defined in http://www.ecs.umass.edu/ece/koren/architecture/Cache/tutorial.html http://www.ecs.umass.edu/ece/koren/architecture/Cache/tutori... ?). Also, googling "direct indirect cache" yielded the hilarious http://onlinelibrary.wiley.com/doi/10.1046/j.1439-0310.2003.00897.x/abstract http://onlinelibrary.wiley.com/doi/10.1046/j.1439-0310.2003.... To other programmers not so familiar with CPU caching, resharing two blurbs that helped me get a start of a grasp on it: - Why do CPUs have multiple cache levels? https://news.ycombinator.com/item?id=12245458 https://news.ycombinator.com/item?id=12245458 , https://fgiesen.wordpress.com/2016/08/07/why-do-cpus-have-multiple-cache-levels/ https://fgiesen.wordpress.com/2016/08/07/why-do-cpus-have-mu... - CppCon 2014 - Mike Acton: Data-oriented design and C++ , https://www.youtube.com/watch?v=rX0ItVEVjHc https://www.youtube.com/watch?v=rX0ItVEVjHc
- hrydgard 10y agoI-cache and D-cache means instruction cache and data cache.
- kibwen 10y agoI believe by "I and D" the parent is referring to instruction cache and data cache: http://stackoverflow.com/questions/22394750/what-is-meant-by-data-cache-and-instruction-cache http://stackoverflow.com/questions/22394750/what-is-meant-by...
- vvanders 10y agoWe used to call that a "flat profile" where everything looks slow due to cache thrashing but there's no inner loop that's a smoking gun. It's really a shame more platforms don't show cache/icache misses in an easy to access manner.