第三次寒假作业_快一点的简陋路由

内容概要

前言

跪了。没有完成规定的任务，还是朴素算法。

这里是本次作业的 Github 仓库

?? 不足

这版程序和第二次程序的思路是一样的（线性表搜索），先说说不足的地方。

• Hicuts 算法

  论文看是看懂了。基本框架也搭了。算法的启发规则 \(np()\) 和 \(dim()\) 写不清楚。建树不能收敛，就死循环卡住。

• C++ 类的继承

  作用域的权限搞得我好乱。最后还是直接吧类独立开了。

• 内存泄露

  new 出来的对象全部没有 delete 掉。

• 代码冗余

  有很多代码可以复用和优化。

? 优化

然后讲讲这版程序相对于第二次作业做出的改进。

• 使用 C++ 重构代码

  实现把路由抽象成一个类。使用面向对象的思想（可能是）重构了代码。

• 更友好的用户交互

  使用了一个开源库 cmdline](https://github.com/tanakh/cmdline)。解析命令行参数。

  将路由封装成类。

• 更好的性能

  就是莫名其妙的提升，我基本没有做什么工作。就是简单的重构了一下代码。

  结果路由速度出乎意料地提升了 20-30% 左右

• Benchmark 模式

  通过指定一个列表文件，程序可以按照顺序匹配多个数据包文件。

  一键 run。

HiCut 算法简介

Hicut 算法通过预处理规则数据，构建决策树的方法大幅减少分类数据包时的性能开销。其构建的决策树的决策节点（Internal node）存储用以判断下一步决策的信息，叶节点（Leaf node）存放一个规则子集（规则数小于 binth（bin-threshold))。当输入一个数据包，Hicuts 算法会遍历决策树，按照决策节点的指导搜索匹配的规则。直到遇到叶节点， 然后在叶节点中线性查找，匹配最佳规则。

性能测试

以下测试程序均开启 -O3 选项编译，运行于 Ryzen R7-5800H + Windows 11 环境。

如果使用第二次作业的数据集进行测试，单个数据集平均需要 20ms 匹配。

第二次作业

如果打开编译器的 O3 优化 再进行编译，程序性能还能够有一定的提升。

PS D:\Projects\simple-router-repo\build> .\simple-router-O3.exe .\debug-rule .\debug-data
INFO: Start to read rule. 
INFO: Start to match.
INFO: Read 9191 data in total, matched 9191/9191
=================
TIME (in cpu clock):
Read rule: 4
Match data: 26

程序性能提升了 25%，使用测试集文件可以做到 30ms 完成。

本次作业

INFO || Open "out" as output file.
INFO || Start to build tree 
INFO || Open "rule" as rule file.
INFO || Open "packet" as data file.
INFO || Exiting the router, show info now...
---------------------
Time: 0.023
Rule: 918
Memory: 51.4KB

其实也没差多少。

开启 Benchmark 模式运行本次作业的 dataset1 结果如下。

PS  .\simple-router.exe -i --benchmark packetlist
INFO || Benchmark started! Parsing assigned ...
INFO || Open "output" as output file.
INFO || Start to build tree 
INFO || Open "rule" as rule file.
INFO || Open "packet1.txt" as data file.
INFO || packet1.txt Matching finished!
INFO || Open "output" as output file.
INFO || Start to build tree 
INFO || Open "rule" as rule file.
INFO || Open "packet2.txt" as data file.
INFO || packet2.txt Matching finished!
INFO || Open "output" as output file.
INFO || Start to build tree 
INFO || Open "rule" as rule file.
INFO || Open "packet3.txt" as data file.
INFO || packet3.txt Matching finished!
INFO || Benchmark ended.
---------------------
Totoal Time: 2.96

平均一秒左右一个 packet。