Is an array of arrays cache local?

If an array

[1,2,3,4,5,6]

exists in a contiguous block of memory, does an array of arrays

[[1,2,3],[4,5,6]]

necessarily have the same cache locality?

---

In the array of arrays case, the arrays themselves will have the same locality properties that an array of elements has because this case is no different - the "elements" here are arrays. However, whether or not the elements of each sub-array are contiguous in memory to the elements of another sub-array depends on the implementation of the sub-arrays.

Since you didn't specify a language, I'll use C++ syntax to demonstrate, but this is fundamentally language agnostic, as it deals with aspects of the hardware. If your array-of-arrays is equivalent to the C++ std::vector<std::vector<int>> - which is a flexible container of containers that can grow/shrink as needed, each std::vector will be contiguous in memory with respect to the others, but a std::vector doesn't contain the elements directly. Rather, its a wrapper around a dynamically allocated array, typically holding a few pointers to the underlying data. What this means is that each wrapper will be contiguous, but the elements won't necessarily be. Here's a live demo demonstrating this.

However, consider the case where your array-of-arrays is a std::array<std::array<int,3>,2> instead - which is simply an array of 2 elements, where each element is an array of the fixed size ,3, int s. A std::array is a wrapper around a fixed-size C array which is not dynamically allocated, in contrast to its std::vector counterpart. In this case, you get the same locality property as you did for the std::vector case - each std::array is contiguous with respet to the others, but here you also get something more. Since a std::array actually contains the underlying data rather than just a few pointers to it, the elements of each sub-array are also contiguous with respect to each other. This, too can be seen here.

What this boils down to from a hardware perspective is simply how your objects are laid down in memory. In the former case, each wrapper is contiguous, but the data isn't, because the wrappers simply hold pointers to the data. In the latter case, each wrapper is contiguous, and so is the data, because each wrapper actually contains the data.

Perhaps if you specify which language you're referring to, I could help you with your specific case.

链接地址: http://www.djcxy.com/p/36364.html

上一篇: Numpy数组访问优化

下一篇: 数组是否缓存本地数组？