使用一个使用16字节4v4单字节矩阵的程序:
unsigned char matrix[4][4];
和一些256字节16v16一个字节矩阵:
unsigned char bigMatrix[16][16];
通常由于数据操作,我被迫在程序中逐列循环,从而导致缓存未命中。
如果我使用数组,性能会提高,即
unsigned char matrix[16]; unsigned char matrix[256];
并通过使用一些变量来检索元素来访问元素,即
matrix[variableA*variableB + i];
每次我想访问一个元素时,需要重新计算variableA * variableB + i。
我只想要速度优化和内存没问题。 这会有什么帮助,比如给出一些性能上的打击或损失,还是差异太小甚至无法照顾?
没什么区别。 在任何一种情况下,数据都以完全相同的方式布局,并且也以相同的方式访问。 如果它甚至没有产生完全相同的assembly,我会感到惊讶。
但是,对于256字节的表,在任何情况下都不可能获得缓存未命中。 CPU的L1缓存通常在32到128KB之间,所以我怀疑你在任何情况下都会遇到很多缓存未命中。
贾尔夫大多是对的。 L1高速缓存被分成块,块的大小取决于处理器但是大约32个字节。 所以,如果你一次一个字节地通过内存,你会得到每32个字节的缓存未命中(或任何块大小)。 现在,英特尔芯片非常聪明,可以检测顺序读取和预取数据,减少高速缓存未命中的影响。
4×4矩阵很可能驻留在单个L1块(或缓存行)中,因此按行或按列访问它几乎没有区别。 当然,您不希望将矩阵拆分为两个缓存行,因此良好对齐的内存非常重要。
但是,16×16矩阵不适合缓存行。 因此,如果您正在跳过数组处理列,那么您将获得大量缓存未命中。 正如jalf所说,索引的计算没有什么区别,因为CPU和内存之间的比率很高(即你可以为每个缓存未命中做很多CPU工作)。
现在,如果您主要以列为导向处理矩阵,那么您最好的选择是转置所有矩阵(使用列交换行),因此您的内存访问将更加顺序,并且缓存未命中的数量将减少, CPU将能够更好地预取数据。 所以,而不是像这样组织矩阵:
0 1 2 .... 15 16 17 18 .... 31 .... 240 241 242 .... 255
其中数字是从矩阵开始的内存偏移量,因此组织:
0 16 32 ... 240 1 17 33 ... 241 ... 15 31 47 ... 255
虽然编译后的代码行为同样快,但存在一些设计问题:索引代码的重用可以最大化。
这样做的最好方法是imho,它将它包装在一个知道如何以最快的方式遍历它的元素的容器中。 他们得到了一个免费精选名字大全:一个’内部迭代器’,如GoF设计模式“迭代器”模式中所提到的。
一个简短的例子:
template< int N > struct CNxN { typedef int t_row[N]; typedef t_row t_matrix[N]; t_matrix m_Contents; template< typename Functor > void each( Functor & f ) { for( int col = 0; col != N; ++col ) for( int row = 0; row != N; ++row ) f( m_Contents[row][col] ); } }; // client code CNxN<3> matrix = { { {1,1,1},{1,1,1},{1,1,1} } }; struct sum { long result; sum():result(0){} void operator()( int i ){ result +=i; } }; matrix.each( sum ); assert(sum.result==0); assert(has_performed_in_the_fastest_possible_way);//;)
你说每次访问一个元素时都需要重新计算variableA*variableB+i
,这种情况在任何情况下都会发生,即使使用多维数组也是如此。 唯一的区别是,在多维数组中,编译器会发出此代码,因此您看不到它,而在一维数组中,您会看到源代码中的代码。
如果对数组进行顺序访问,则大线性数组可以稍快一些,因为您在每个索引处都保存了乘法运算。 如果您按列循环,那么您将按顺序访问; 至少在[row] [col]表示法中,与我曾与之交谈的每个人都是“标准”。
我怀疑你的256元素arrays会在现代硬件上导致缓存未命中,但我愿意被certificate是错误的。 cachegrind告诉你什么?
当我在学校时,我的一位CS老师坚持认为,如果你为singledimension制作arrays,它会更快。 那天我很生气……
通常由于数据操作,我被迫循环列[…]
你不可能两种方式:如果矩阵“足够大”,则行式或列式循环将导致缓存未命中(请参阅Skizz的回答 )。 针对更频繁执行的循环类型进行优化。
如果内存消耗不是问题,您还可以考虑保存矩阵及其转置。
以上就是c/c++开发分享C / C ++优化数据结构,数组数组或只是数组相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/562552.html