【分享帖】使用查表优化指令解析
用查表法优化并解耦解析程序
Tips: 阅读前请自动 #include <stdint.h>
Tips2: 本文写自某老灯,希望能为 RM 的发展做出一点微薄的贡献,让大家不要再为一些底层的琐事困扰。
Tips3: 本人水平有限,能力不强,仅作为抛砖引玉,提出一种可能的方案,大佬轻喷。
一、背景
查表在很多场景中都能遇到。例如上位机控制下位机时,下位机可能需要根据不同的指令码解析信息;又或者是通讯过程中根据信息的地址做出不同的判断。此时我们肯定需要查表。这里的查表可以是遍历某个命令列表,找出对应的做法;也可以是通过各种 if else 或 switch 组合成一种“广义的表”。然而这些做法有个问题:效率不高、且代码耦合严重。
何谓效率不高?无论是遍历列表,或是条件判断,本质上都是:带着我的某个特征值,从已有列表中从头走到尾,一个个比对是否有契合值。那么最坏的情况就是:我要带着我的值一直找到队尾,才能够找到对应值,也就是时间复杂度为列表长度,即常说的 O(n)。
何为代码耦合严重?遍历列表还算好,可以建立一个数组,其中存储的是待比较值+函数指针,查到某个对应值立刻跳转到解析函数里;if else switch 就麻烦了,每次新增一些比较值都要重新修改原来判断逻辑中的代码,不可谓不麻烦。
二、提出
如何查表才能加快速度?我们很容易就能想到“哈哈表”。例如我现在需要响应指令码“0x0B”,怎么才能够快呢?我们可以考虑创建一个如下格式的数组:
// 指定 LUT 长度
#define APP_LUT_MAXIMUM_LENGTH 114514
// 新建函数指针,用于放到结构体里
typedef int8_t (*AppLut_pRespondMethod_t)(uint8_t* pData, uint16_t size)
// 创建 LUT 元素(LUT,Look-Up-Table,即查找表)
typedef struct
{ uint8_t cmdId; AppLut_pRespondMethod_t pRespondMethod;
} AppLut_lutElement_t;
// 创建某个 LUT
AppLut_lutElement_t blablaLut[APP_LUT_MAXIMUM_LENGTH];
这样,当我们每解析到某个指令码时,我们就可以像下面这样使用
// 假设这是串口数据解包结果的结构体,用来提取指令码、数据等
typedef struct
{
uint8_t cmdIdField;
uint8_t* pDataField;
uint16_t dataFieldSize;
} depacked;
// 下面是示例通讯的 weak 中断函数,以串口为例吧
void HAL_UARTEx_RxEventCallback(UART_HandleTypeDef *huart, uint16_t Size)
{
// 假设这里可以通过某种解析函数,从原有的接收缓存中取出对应指令码和数据的区段
depacked = ExampleDepack(huart, Size);
// 查表解析
blablaLut[depacked.cmdIdField].pRespondMethod(depacked.pDataField, depacked.dataFieldSize);
return; // 退出
}
```
可以看到,我们的解析直接根据解包后的指令码,立刻调用了对应的函数。时间复杂度?直接查出来了还谈什么复杂度(好吧认真点,其实是 O(1))。结果非常的 Amazing 啊,我们通过一个数组列表,直接让解析速度起飞了!当我们需要匹配的指令码越复杂,这个表能够为我们节省的时间就越可观!
三、改进与优化
很显然,为了维护这么一个“哈哈表”,我们需要占用一片内存空间(也就是开了一个数组),从而换取时间上的速度,也就是常说的“空间换时间”。你或许已经蠢蠢欲动了,那么代价呢?
最大的问题就是:如果我需要解析的指令码是 uint16_t 格式,而我的指令码好巧不巧,正好有个 0x1233,那我这个表不得大到离谱啊?而且如果我这个表又偏偏只需要处理 0x0000 和 0x1233 这俩指令,这不是搞笑吗?
没错,这种表的问题就是占用空间过于离谱,因而就要想办法进行改进和优化。因而引入“哈希表”
哈希表的总体思想和上面是类似的,但查表和制表的方法改进了。
以我们刚刚举的例子为例,某个表只需要处理 0x0000 和 0x1233 这俩指令,这个表理论上最小可以有多小呢?当然就是只包含这两个指令对应的元素啦!那如果是只有两个元素的表,数组应该只有`Lut[0]` 和`Lut[1]` 两个元素,我们要怎么处理呢?
显然,如果我们能够设计某种函数,让 0x0000 输入以后,变成 0;让 0x1233 输入以后变成 1。我们假设这个函数叫 “hash”,那么这个表就可以这样用了:`Lut[hash(0x0000)]` 或`Lut[hash(0x1233)]` 。通过这么一个简单的映射函数,我们就实现了整个表的简化。例如用一个除2取余函数就可以实现了。
通过这么一个映射加查表,我们就基本实现了哈希表的功能。当然实际使用中,我们还会遇到大量的问题。例如:上面这个映射函数怎么设计?怎么确定我的哈希表能不能压缩到理论上的最小数值?如果不能怎么办?强烈建议各位搜索相关知识自行学习。本文只作为引子,不做过多原理的介绍。
为了实践,这里只需要知道
- 哈希表不可能开得很大(例如有几个指令码就开几个元素),因为内存会受不了。这时候我们会允许元素重叠,并适当降低一些时间复杂度以平衡内存的耗用。
四、实践
我们使用的哈希表基于如下开源:
https://github.com/tidwall/hashmap.c
此开源使用非常简单(可见其readme);同时使用 MIT 许可证,非常宽松,可以放心使用。使用此开源,最主要的是需要你完成:1. 哈希表多大?
首先要确保表的大小是一个素数。当除以一个素数时,会产生最分散的余数。这能保证我们放进去的元素尽可能分散。此外开源中定义了
“#define GROW_AT 0.60 /* 60% */”,
建议据此设计合适的大小。不过开源的哈希表也可以自己扩充,所以或许无所谓?2. 哈希表制表与元素
我们放进表中的是一个元素(大概率是结构体),比如结构体如下:
typedef struct{
uint16_t cmdId;
cmdIdParsedCb_t cmdIdCb;
} AppUpParser_cmdIdLutElement_t;
需要告诉哈希表,我们用 cmdId 来确定新元素放置的位置。也就是上面提到的用映射函数放到数组(内存)中某个位置的操作。因此我们根据元素实际内容编写代码,让哈希表能够读取制表标志、比较元素是否相等等(阅读开源的实例即可,非常清晰)。例如如下代码
uint64_t GetHash(const void *pElement, uint64_t seed0, uint64_t seed1){
void* pItem = lut->pGetIndexItemAddFunc(pElement);
size_t size = lut->pGetIndexItemSizeFunc(pElement);
return hashmap_sip(pItem, size, seed0, seed1);
}
seed0 seed1 可以为空,但推荐用随机数生成,这样可以在调用 GetHash 时通过 hashmap 的 seed 来判断是哪个表触发的 gethash 函数,从而方便调用不同的获取 Index 函数
3.一个奇怪的bug
在完成了基于哈希表的lut后,我们就可以把代码解耦了,例如我自己写的解析函数parser可以实现注册解析回调:
// 初始化 parser
upParser = AppUpParser_HandleRegister(&upParserCfg);
// 注册函数 0x0001
AppUpParser_cmdIdLutElement_t parsedElement;
parsedElement.cmdId = 0x0001;
parsedElement.cmdIdCb = cmdId_0001_cb;
AppUpParser_ParsedCbRegister(upParser, &parsedElement);
// 下略
这样再配合宏定义CONCA甚至还能实现批量注册。更多玩法可以发挥想象力。
Tips: 阅读前请自动 #include <stdint.h>
Tips2: 本文写自某老灯,希望能为 RM 的发展做出一点微薄的贡献,让大家不要再为一些底层的琐事困扰。
Tips3: 本人水平有限,能力不强,仅作为抛砖引玉,提出一种可能的方案,大佬轻喷。
一、背景
查表在很多场景中都能遇到。例如上位机控制下位机时,下位机可能需要根据不同的指令码解析信息;又或者是通讯过程中根据信息的地址做出不同的判断。此时我们肯定需要查表。这里的查表可以是遍历某个命令列表,找出对应的做法;也可以是通过各种 if else 或 switch 组合成一种“广义的表”。然而这些做法有个问题:效率不高、且代码耦合严重。
何谓效率不高?无论是遍历列表,或是条件判断,本质上都是:带着我的某个特征值,从已有列表中从头走到尾,一个个比对是否有契合值。那么最坏的情况就是:我要带着我的值一直找到队尾,才能够找到对应值,也就是时间复杂度为列表长度,即常说的 O(n)。
何为代码耦合严重?遍历列表还算好,可以建立一个数组,其中存储的是待比较值+函数指针,查到某个对应值立刻跳转到解析函数里;if else switch 就麻烦了,每次新增一些比较值都要重新修改原来判断逻辑中的代码,不可谓不麻烦。
二、提出
如何查表才能加快速度?我们很容易就能想到“哈哈表”。例如我现在需要响应指令码“0x0B”,怎么才能够快呢?我们可以考虑创建一个如下格式的数组:
// 指定 LUT 长度
#define APP_LUT_MAXIMUM_LENGTH 114514
// 新建函数指针,用于放到结构体里
typedef int8_t (*AppLut_pRespondMethod_t)(uint8_t* pData, uint16_t size)
// 创建 LUT 元素(LUT,Look-Up-Table,即查找表)
typedef struct
{ uint8_t cmdId; AppLut_pRespondMethod_t pRespondMethod;
} AppLut_lutElement_t;
// 创建某个 LUT
AppLut_lutElement_t blablaLut[APP_LUT_MAXIMUM_LENGTH];
这样,当我们每解析到某个指令码时,我们就可以像下面这样使用
// 假设这是串口数据解包结果的结构体,用来提取指令码、数据等
typedef struct
{
uint8_t cmdIdField;
uint8_t* pDataField;
uint16_t dataFieldSize;
} depacked;
// 下面是示例通讯的 weak 中断函数,以串口为例吧
void HAL_UARTEx_RxEventCallback(UART_HandleTypeDef *huart, uint16_t Size)
{
// 假设这里可以通过某种解析函数,从原有的接收缓存中取出对应指令码和数据的区段
depacked = ExampleDepack(huart, Size);
// 查表解析
blablaLut[depacked.cmdIdField].pRespondMethod(depacked.pDataField, depacked.dataFieldSize);
return; // 退出
}
```
可以看到,我们的解析直接根据解包后的指令码,立刻调用了对应的函数。时间复杂度?直接查出来了还谈什么复杂度(好吧认真点,其实是 O(1))。结果非常的 Amazing 啊,我们通过一个数组列表,直接让解析速度起飞了!当我们需要匹配的指令码越复杂,这个表能够为我们节省的时间就越可观!
三、改进与优化
很显然,为了维护这么一个“哈哈表”,我们需要占用一片内存空间(也就是开了一个数组),从而换取时间上的速度,也就是常说的“空间换时间”。你或许已经蠢蠢欲动了,那么代价呢?
最大的问题就是:如果我需要解析的指令码是 uint16_t 格式,而我的指令码好巧不巧,正好有个 0x1233,那我这个表不得大到离谱啊?而且如果我这个表又偏偏只需要处理 0x0000 和 0x1233 这俩指令,这不是搞笑吗?
没错,这种表的问题就是占用空间过于离谱,因而就要想办法进行改进和优化。因而引入“哈希表”
哈希表的总体思想和上面是类似的,但查表和制表的方法改进了。
以我们刚刚举的例子为例,某个表只需要处理 0x0000 和 0x1233 这俩指令,这个表理论上最小可以有多小呢?当然就是只包含这两个指令对应的元素啦!那如果是只有两个元素的表,数组应该只有`Lut[0]` 和`Lut[1]` 两个元素,我们要怎么处理呢?
显然,如果我们能够设计某种函数,让 0x0000 输入以后,变成 0;让 0x1233 输入以后变成 1。我们假设这个函数叫 “hash”,那么这个表就可以这样用了:`Lut[hash(0x0000)]` 或`Lut[hash(0x1233)]` 。通过这么一个简单的映射函数,我们就实现了整个表的简化。例如用一个除2取余函数就可以实现了。
通过这么一个映射加查表,我们就基本实现了哈希表的功能。当然实际使用中,我们还会遇到大量的问题。例如:上面这个映射函数怎么设计?怎么确定我的哈希表能不能压缩到理论上的最小数值?如果不能怎么办?强烈建议各位搜索相关知识自行学习。本文只作为引子,不做过多原理的介绍。
为了实践,这里只需要知道
- 哈希表不可能开得很大(例如有几个指令码就开几个元素),因为内存会受不了。这时候我们会允许元素重叠,并适当降低一些时间复杂度以平衡内存的耗用。
四、实践
我们使用的哈希表基于如下开源:
https://github.com/tidwall/hashmap.c
此开源使用非常简单(可见其readme);同时使用 MIT 许可证,非常宽松,可以放心使用。使用此开源,最主要的是需要你完成:1. 哈希表多大?
首先要确保表的大小是一个素数。当除以一个素数时,会产生最分散的余数。这能保证我们放进去的元素尽可能分散。此外开源中定义了
“#define GROW_AT 0.60 /* 60% */”,
建议据此设计合适的大小。不过开源的哈希表也可以自己扩充,所以或许无所谓?2. 哈希表制表与元素
我们放进表中的是一个元素(大概率是结构体),比如结构体如下:
typedef struct{
uint16_t cmdId;
cmdIdParsedCb_t cmdIdCb;
} AppUpParser_cmdIdLutElement_t;
需要告诉哈希表,我们用 cmdId 来确定新元素放置的位置。也就是上面提到的用映射函数放到数组(内存)中某个位置的操作。因此我们根据元素实际内容编写代码,让哈希表能够读取制表标志、比较元素是否相等等(阅读开源的实例即可,非常清晰)。例如如下代码
uint64_t GetHash(const void *pElement, uint64_t seed0, uint64_t seed1){
void* pItem = lut->pGetIndexItemAddFunc(pElement);
size_t size = lut->pGetIndexItemSizeFunc(pElement);
return hashmap_sip(pItem, size, seed0, seed1);
}
seed0 seed1 可以为空,但推荐用随机数生成,这样可以在调用 GetHash 时通过 hashmap 的 seed 来判断是哪个表触发的 gethash 函数,从而方便调用不同的获取 Index 函数
3.一个奇怪的bug
此哈希表允许用户使用自己的malloc fre等内存管理函数。我在使用时不知道为啥<stdlb.h>里没有free,只有cfree替换,虽然不影响使用,但要是有大佬知道原因烦请不吝赐
4. 解析解耦在完成了基于哈希表的lut后,我们就可以把代码解耦了,例如我自己写的解析函数parser可以实现注册解析回调:
// 初始化 parser
upParser = AppUpParser_HandleRegister(&upParserCfg);
// 注册函数 0x0001
AppUpParser_cmdIdLutElement_t parsedElement;
parsedElement.cmdId = 0x0001;
parsedElement.cmdIdCb = cmdId_0001_cb;
AppUpParser_ParsedCbRegister(upParser, &parsedElement);
// 下略
这样再配合宏定义CONCA甚至还能实现批量注册。更多玩法可以发挥想象力。
请问这篇文章对你有用吗?
【分享帖】使用查表优化指令解析