【嵌入式开发学习】__改了一行代码,数组遍历耗时从10.3秒降到了0.5秒!

本文主要是介绍【嵌入式开发学习】__改了一行代码,数组遍历耗时从10.3秒降到了0.5秒!,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

前言

两个简单的测试程序

1. array1.c 对数组按行进行访问

2. array2.c 对数组按列进行访问

​编辑 3. 编译运行,并用 time 命令统计一下运行时间:

重要说明

存储金字塔

局部性原理

1. 时间局部性

2. 空间局部性

 高速缓存 - Cache

Cache Line

Cache Line 实例讲解

按行、列访问的真正差异 - Cache

用perf观测性能指标

小结

(* ̄︶ ̄)创作不易!期待你们的 点赞、收藏和评论喔。


前言

本专题除讲解常见性能问题以及分析、调优手段外,还会重点讲解一些对系统性能至关重要,却又经常被忽视的高级话题,如Cache、指令流水线、Superscala、SIMD、分支预测、内存屏障等。此外,还会涉及到编译器、操作系统等话题。

两个简单的测试程序

定义一个同样大小的二维数组,然后循环遍历,对数组元素赋值。

1. array1.c 对数组按行进行访问

2. array2.c 对数组按列进行访问

 3. 编译运行,并用 time 命令统计一下运行时间:

array1用时0.528秒,array2用时10.310秒。array2耗时居然是array1的将近20倍

有没有被这个结果震惊到?为什么会有如此之大的性能差异呢?

重要说明

要想真正理解这个问题,必须要先补充一些关于现代计算机存储系统相关的背景知识,这也是理解这个问题的关键所在。为方便大家理解,我会尽量以白话的形式进行讲解,尽可能避免枯燥无味的纯理论描述。

存储金字塔

相信不少人都听过“存储金字塔”这个词,或者至少见过类似下面这张图:

这张图很直观地描述了现代计算机系统的分级存储模型

可以认为CPU就位于金字塔的顶点上,越靠近塔顶,离CPU越近,访问速度越快,但生产成本越高,相应的容量也就越小。在所有存储器中,寄存器直接内嵌在CPU中,访问速度最快,容量也最小,一般CPU上也就最多几十个通用寄存器供应用程序使用。

反之,越往下靠近塔底,访问速度越慢,生产成本越低,相应的容量也就越大。比如图中最底部的网络存储设备,相对其他存储设备而言是访问速度最慢的,但其容量却几乎可以认为是无限制的。

那么,这种金字塔式结构中,不同层级的存储设备之间究竟是如何协调工作的呢?

用一句话概括

高一级的存储设备,往往是作为低一级存储设备的缓存来使用的。

简单来说,系统运行时,为了提升数据访问效率,把程序中最近最经常访问的数据,尽可能放到访问速度更快的高一级存储器中。这样一来,每次访问数据时,从金字塔的顶端开始,都先尝试在高一级存储器中查找,如果被访问的数据存在且有效,则直接访问,否则,就逐级到更低级的存储器中去查找。

这种金字塔式的分级存储模型之所以能够以近乎完美的方式运行,实际上都是建立在现代计算机科学中的一个非常重要的理论基础之上:程序的局部性原理

 

局部性原理

一个程序的局部性,包含两个维度:时间局部性空间局部性

1. 时间局部性

如果一个数据在某个时间点被CPU访问了,那么在接下来很短的一段时间内,这个数据很有可能会再次被CPU访问到。

2. 空间局部性

如果一个数据在某个时间点被CPU访问了,那么与这个数据临近的其他数据,很有可能也会很快被CPU访问到

 高速缓存 - Cache

根据常识,我们知道,程序要想被CPU正常执行,必须要先被加载到内存中

但是,内存的访问速度与CPU运行速度相比,要慢好几个数量级,可以想象一下,如果CPU每次都直接从内存中存取数据,会造成大量的计算资源浪费,程序性能严重受损,假如真是这样的话,你还能像现在这样愉快的吃鸡吗?

为了解决CPU和内存之间速度严重不匹配的问题,在CPU和内存之间设计了高速缓存,即Cache。

目前,主流CPU一般都有三级(或更多级)的Cache,依次是L1 Cache、L2 Cache、L3 Cache。其中L1 Cache速度最快,几乎可以和内嵌在CPU中的寄存器媲美,容量也最小,而L3 Cache速度最慢(但仍然比内存快很多),但容量最大。

CPU读取数据时,会在L1、L2、L3Cache中逐级查找,如果找到,就从Cache直接读取,找不到再从内存读取,并且把数据存放到Cache中,以便提高下次访问的效率。

在这个过程中,如果在Cache中找到所需数据,称为Cache命中(Cache Hit), 找不到称为Cache未命中(Cache Miss)

不难看出,L1 Cache命中的时候,读取数据最快,性能最好,而当L1、L2、L3 Cache全部未命中时,就必须要直接从内存中读取数据,性能最差!

Cache Line

Cache Line 是 Cache和内存之间进行数据传输的最小单位。

根据上文讲解的程序的局部性原理,如果一个数据被CPU访问了,那么这个数据相邻的其他数据也很快会被访问到。因此,为了提高内存数据的读取效率,并且最大化利用CPU资源,数据在Cache和内存之间传输时,不是一个字节一个字节进行传输的,而是以缓存行(Cache Line)为单位进行传输的。

不同CPU的Cache line大小可能不同,典型的CPU Cache line大小是64个字节。

我们通过下面一个简单的例子,加深一下理解。

Cache Line 实例讲解

在一个Cache Line大小为64字节的机器上,定义个数组:

int a[16] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};

我们假设数组a的起始地址是Cache Line对齐的,可以简单理解为a的地址能被64整除。假设,数组a还从来没有被访问过,如果此时需要访问a中的一个元素a[5],如:

int x = a[5];

由于在此之前数组a没有被访问过,所以理论上讲,数组a应该只存在于内存中,并未被加载到Cache中。因此,此时CPU在Cache中找不到a[5],触发Cache Miss,然后需要从内存中读取数据,并更加载到Cache中。前面提到,Cache和内存之间是以Cache Line为单位进行数据传输的,因此,这里会把一个Cache line大小(64字节)的数据从内存读取出来加载到Cache中。由于a的起始地址恰巧是Cache line对齐的,所以CPU会把整个数组(64个字节,刚好一个Cache Line)都加载到Cache中。

紧接着,如果再访问数组a的元素,如:

int y = a[10];

此时,整个数组都在Cache中,所以CPU在访问时,触发Cache Hit,直接从Cache读取数据即可,不需要再从内存中读取。

了解了Cache的背景知识,现在来分析下array1.c和array2.c为什么会存在这么巨大的性能差异。

按行、列访问的真正差异 - Cache

首先,必须要知道一点:C语言的数组,所有元素是存放在地址连续的内存中的,此外,C语言的多维数组,是按行进行存储的

array1.c按行对数组进行访问,也就是从数组起始地址开始,一直连续访问到数组的最后一个元素的地址处。第一次访问一个Cache Line的首个元素时,触发Cache Miss,与该元素临近的几个元素会组成一个Cache Line,被一起加载到Cache中。如此,在访问下一个元素的时候,就会Cache Hit,直接从Cache读取数据即可。

而array2.c按列对数组进行访问,因此并不是按照连续地址进行访问的,而是每次间隔10240 * 4个字节进行访问。第一次访问一个Cache Line的首个元素时,假设地址为x,尽管该元素临近的一个Cache Line大小的元素也会被一起加载进Cache中,但是程序接下来访问的并不是临近的元素,而是地址为x + 10240 * 4处的元素,因此会再次触发Cache Miss。而当程序回过头来访问x + 4地址处的元素时,这个Cache Line可能已经被其他数据冲刷掉了。因为,尽管Cache会尽量缓存最近访问过的数据,但毕竟大小有限,当Cache被占满时,一些旧的数据就会被冲刷替换掉。

可以看出,无论是时间局部性还是空间局部性,array1.c都要比array2.c好很多!相比array1.c,array2.c会触发大量的Cache Miss,这也是为什么array2的性能会如此之差!

下面我们用perf来对比下这两个程序的性能指标。

用perf观测性能指标

perf是Linux提供的一个功能强大的实用性能调优工具,它可以用来观测几乎所有CPU相关的性能指标,但perf工具本身,不是本文重点,以后会有专门文章详细介绍perf的使用。

1. 先获取array1.c的性能指标:

2. 再看下array2.c的性能指标:

这里,我们只关注一个最重要的性能指标:L1 Data Cache的Miss率。

对比一下,array1.c的L1-dcache-load-misses率只有3.10%, 而按列访问的array2.c,则达到了惊人的93.03%!这就是两者性能差异如此巨大的真相!

小结

Cache是CPU内部最为重要的部件之一,也是影响程序性能的最重要因素之一,但由于各种原因,经常被程序员忽视。在进行性能调优时,除了系统架构、算法等方面的考量之外,不妨也从CPU的角度去思考一下,比如Cache,有时会对程序性能产生决定性影响。


(* ̄︶ ̄)创作不易!期待你们的 点赞收藏评论喔。

本文来源网络,免费分享知识,版权归原作者所有。如涉及作品版权问题,请联系我进行删除!

这篇关于【嵌入式开发学习】__改了一行代码,数组遍历耗时从10.3秒降到了0.5秒!的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/324420

相关文章

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

这15个Vue指令,让你的项目开发爽到爆

1. V-Hotkey 仓库地址: github.com/Dafrok/v-ho… Demo: 戳这里 https://dafrok.github.io/v-hotkey 安装: npm install --save v-hotkey 这个指令可以给组件绑定一个或多个快捷键。你想要通过按下 Escape 键后隐藏某个组件,按住 Control 和回车键再显示它吗?小菜一碟: <template

Hadoop企业开发案例调优场景

需求 (1)需求:从1G数据中,统计每个单词出现次数。服务器3台,每台配置4G内存,4核CPU,4线程。 (2)需求分析: 1G / 128m = 8个MapTask;1个ReduceTask;1个mrAppMaster 平均每个节点运行10个 / 3台 ≈ 3个任务(4    3    3) HDFS参数调优 (1)修改:hadoop-env.sh export HDFS_NAMENOD

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

学习hash总结

2014/1/29/   最近刚开始学hash,名字很陌生,但是hash的思想却很熟悉,以前早就做过此类的题,但是不知道这就是hash思想而已,说白了hash就是一个映射,往往灵活利用数组的下标来实现算法,hash的作用:1、判重;2、统计次数;

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

嵌入式QT开发:构建高效智能的嵌入式系统

摘要: 本文深入探讨了嵌入式 QT 相关的各个方面。从 QT 框架的基础架构和核心概念出发,详细阐述了其在嵌入式环境中的优势与特点。文中分析了嵌入式 QT 的开发环境搭建过程,包括交叉编译工具链的配置等关键步骤。进一步探讨了嵌入式 QT 的界面设计与开发,涵盖了从基本控件的使用到复杂界面布局的构建。同时也深入研究了信号与槽机制在嵌入式系统中的应用,以及嵌入式 QT 与硬件设备的交互,包括输入输出设

OpenHarmony鸿蒙开发( Beta5.0)无感配网详解

1、简介 无感配网是指在设备联网过程中无需输入热点相关账号信息,即可快速实现设备配网,是一种兼顾高效性、可靠性和安全性的配网方式。 2、配网原理 2.1 通信原理 手机和智能设备之间的信息传递,利用特有的NAN协议实现。利用手机和智能设备之间的WiFi 感知订阅、发布能力,实现了数字管家应用和设备之间的发现。在完成设备间的认证和响应后,即可发送相关配网数据。同时还支持与常规Sof

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来