C/C++遍历二维数组,列优先(column-major)比行优先(row-major)慢,why?

简介: C/C++遍历二维数组,列优先(column-major)比行优先(row-major)慢,why?简单粗暴的答案:存在Cache机制!稍微啰嗦一点:CPU访问内存(读/写,遍历数组的话主要是读),不是每次都直接从内存上操作,而是先看Cache里是否有所指定地址的值!这个问题,stackoverflow上有人问过的,结论是:CPU读取内存某地址处的值,并不是每次都去内存中取出来,有时候会从cache里读取。

C/C++遍历二维数组,列优先(column-major)比行优先(row-major)慢,why?

简单粗暴的答案:存在Cache机制!

稍微啰嗦一点:CPU访问内存(读/写,遍历数组的话主要是读),不是每次都直接从内存上操作,而是先看Cache里是否有所指定地址的值!

这个问题,stackoverflow上有人问过的,结论是:CPU读取内存某地址处的值,并不是每次都去内存中取出来,有时候会从cache里读取。当初次访问数组的时候,会把连续一块(chunk)内存地址上的值都读到cache里(比如,64字节),后续CPU接受到一个内存地址要读取数据时,先看cache里有没有,没有的话再去内存上取。

原文:
https://stackoverflow.com/questions/33722520/why-is-iterating-2d-array-row-major-faster-than-column-major

关键句:The important factor is that the cache doesn't contain individual bytes or words, it holds chunks of adjacent memory, known as a cache-line, typically 64-bytes in size. So when address X is in the cache the CPU probably doesn't need to pre-emptively fetch X+1 because it has probably already got it (except in the case where X is the last byte in a cache-line, in which case it probably will have pre-fetched the next cache-line).

目录
相关文章
|
8月前
|
C++ 容器
【C++之迭代器】遍历容器
【C++之迭代器】遍历容器
|
11天前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
36 2
|
11天前
|
数据采集 存储 算法
【C++数据结构——图】图的遍历(头歌教学实验平台习题) 【合集】
本文介绍了图的遍历算法,包括深度优先遍历(DFS)和广度优先遍历(BFS)。深度优先遍历通过递归方式从起始节点深入探索图,适用于寻找路径、拓扑排序等场景;广度优先遍历则按层次逐层访问节点,适合无权图最短路径和网络爬虫等应用。文中提供了C++代码示例,演示了如何实现这两种遍历方法,并附有测试用例及结果,帮助读者理解和实践图的遍历算法。
26 0
|
6月前
|
存储 算法 搜索推荐
|
7月前
|
算法 搜索推荐 C++
C++之STL常用算法(遍历、查找、排序、拷贝、替换、算数生成、集合)
C++之STL常用算法(遍历、查找、排序、拷贝、替换、算数生成、集合)
|
7月前
|
算法 C++ 容器
C++之vector容器操作(构造、赋值、扩容、插入、删除、交换、预留空间、遍历)
C++之vector容器操作(构造、赋值、扩容、插入、删除、交换、预留空间、遍历)
347 0
|
7月前
|
C++
C++数组(定义、遍历、长度、地址、最大值、逆置、冒泡排序)
C++数组(定义、遍历、长度、地址、最大值、逆置、冒泡排序)
111 0
|
8月前
|
存储 C++ 计算机视觉
C++程序二维数组:深入理解与实践
C++程序二维数组:深入理解与实践
106 1
|
7月前
|
计算机视觉 C++
【见微知著】OpenCV中C++11 lambda方式急速像素遍历
【见微知著】OpenCV中C++11 lambda方式急速像素遍历
75 0
|
7月前
|
C++ 安全
高效遍历:C++中分隔字符串单词的3种方法详解与实例
拷贝并交换(Copy-and-Swap)是C++中实现赋值操作符和异常安全拷贝构造函数的技巧。它涉及创建临时对象,使用拷贝构造函数,然后交换数据以确保安全。C++11之前的策略在此后及C++11引入的移动语义和右值引用下仍有效,但后者提供了更高效的实现方式。