steeven
- 浏览: 313809 次
- 性别:
- 来自: 上海
-
最新评论
-
steeven：
后记，网上一搜，这个算法有人贴过。再仔细看看其他算法，这就是统 ...
瞎掰一个效率最高的整数排序算法，bitmap排序，时间复杂度O(n) -
steeven：
skip list其它有点，不用锁，并发性好，不需要维护B树的 ...
2-3树的C实现 -
steeven：
chenguo962332430 写道请问sudo targe ...
P4 behavioral-model: BMv2 -
chenguo962332430：
请问sudo targets/simple_router/si ...
P4 behavioral-model: BMv2 -
steeven：
提交了一个patch刚被接受，Broadcom的网卡也能支持了 ...
MoonGen - 灵活又高性能的收发包工具
文章列表
0. Create C Makefile project
1. Project property: c/c++ general -> Paths & Symbols -> Includes -> GNU C -> Add:
/usr/src/linux-headers-3.19.0-25/arch/x86/include
/usr/src/linux-headers-3.19.0-25/include
2. Project property: C/C++ general -> Preprocessor -> Entries -> ...
Some tips to install and setup Ubuntu
How to install Chrome & Flash plugin
1. sudo apt install chromium-browser
2. Open "Software & UPdate" Panel -> "Other Software" Tab -> check "Canonical Partners".
Close Panel dialog and choose update the sources.
3. s ...
闲着无聊在微信上看到一个皮裤子面试算法的问题，面试者Paul后来用皮裤子的算法赢得了Google的职位。题目如下：
假设这有一个各种字母组成的字符串，假设这还有另外一个字符串，而且这个字符串里的字母数相对少一些。从 ...
从来没想过枯燥的算法居然也能上瘾。 字符串匹配是不是可以这么做，类似于hash， 但是更快
1. hash算法简化，比如取每个字符相加，
2. key长度len, 从0开始，取前len个字符hash
3. while (hash不一致 || 逐个字符比较不一致） && 没到字符串末尾
5. hash减掉当前字符，加上len+1位置字符
---------------------
3/20/2017
又想了一下，还可以改进:
相加的方法比较粗糙，基本上只有一个有效byte, 对于ab, ba很容易误判
我们可以利用寄存器长度多放几个字符，比如64位cpu, 一次可以放8个字 ...
先上结果，速度上秒掉各种排序：
1e4 Straight Insertion: 0.109916 Sec
1e4 Bitmap sorting : 0.000214 Sec
1e8 Bitmap sorting : 6.568575 Sec
前提条件是一般测试数据偏差不大，因此可以用bitmap来标记数据，标记完了自然就排序完成。比堆排序还要快一两个数量级。
缺点也很明显：占内存，只能使用不是特别多的数据排序。
内存评估：一字节8bit, 1M内存是8M bitmap, 1G内存可以排序偏差为8e9的数据，所以一般开发时如果内存够用可以快速出结果。上面1e8个随机数，生成的时候取值 ...
B树一个Node可以有N个key, N+1个下级Node， 二叉树就是简化版，一个key两个下级node
2-3树和2-3-4树的区不大，2-3树在插入时先找到叶子节点（没有子节点），然后插入，过程中如果已经是3Node(2 key）就分裂，向上冒泡，一直可能冒泡到顶上。
2-3-4树则在向下找叶子节点时就做调整，把4Node(3 key)提前分裂掉，为下级节点腾出空间，所以叶子节点插入后不会不停向上冒泡。
2-3-4树冗余更大，如果不提前分裂就是2-3树
红黑树是2-3-4树的2节点表示，采用左倾和旋转来简化和冒泡，Rober Segwick的ppt很经典
B+树感觉都是数据库中数据和索引 ...
`define N_LED 4
`define LEDS_OFF {`N_LED{1'b1}}
`define LEDS_ON {`N_LED{1'b0}}
`define RIGHT_ON {{`N_LED-1{1'b1}}, 1'b0}
`define LEFT_ON { 1'b0, {`N_LED-1{1'b1}}}
module LedFsm (
input clk, input rst_n,
output [`N_LED-1:0] leds); //0:on, 1:off
parameter N_MODE = 4;
parameter ...
MoonGen是一个高性能的基于CPU的收发包工具
DPDK保证其性能强大，用单核x86 CPU可以收发64B 10G
Lua是比较流行的小巧灵活的脚本语言，收发包逻辑修改后不用编译，直接运行，因为是脚本。
LuaJit是Lua的x86即时编译工具。
这三兄弟组合就是灵活的MoonGen引擎，运行Lua脚本用来执行收发包逻辑，很容易写出比专业测试仪还复杂的逻辑。
编译步骤：
安装cmake
git clone https://github.com/emmericp/MoonGen.git
./build.sh
如果DPDK KNI模块编译出错, 打开libmoon/deps/dpdk/x8 ...
ODP/DPDK代码级性能优化总结Tips
以下过程基于ARM 64位CPU, 仅供参考
ODP是Linaro基金下面的开源框架，类似于DPDK。最近用ODP程序DEMO公司SOC性能，性能不理想，优化了一圈又一圈，发现驱动水分很大，包括ODP框架本身。中间不听Architec ...
10/30/2016 P4资源搜集：
看了杨帅的slides发现ONOS 1.6已经有实验性的P4支持，并且可以demo:
https://wiki.onosproject.org/display/ONOS/P4+Experimental+Support+via+BMv2
ONOS是Java的Controller, 通过BMv2的Thrift远程接口调用，Controller本身也需要编译并且映射才能认识P4的表。通过mininet可以创建一些很好看的demo. 注意这个demo并非走的openflow, 是thrift。 ONOS还扩展了thrift接口通过控制器下发P4.
http:/ ...
10/16/2016 发现CI/travis目录下面有依赖工具的安装脚本，供参考
switch是个参考的switch例子，很多表可以参考，并且生成了SAI等API供调用。
============================================
首先要参照前面两篇文章安装BMv2(p4-behavioral-model)和p4c-bmv2(p4c-bm)
安装PTF：
git clone https://github.com/p4lang/ptf.git
cd ptf; sudo python setup.py install
安装switch：
git clone h ...
今天是10/15/2016，如果时间太久请移步https://github.com/p4lang/behavioral-model参考最新信息。
BMv2是一个交换机模拟引擎，和p4-factory不同，不依靠代码生成，而是根据p4c-bm编译生成的JSON动态生效。
安装：
===================================================
因为之前安装了p4-factory，所以相关软件可能已经安装好，如果缺东西，请参考github
还是ubuntu1404:
git clone https://github.com/p4lang/behavioral ...
本文时间10/15/2016，如果时间久远请参考网站 以免被旧信息误导
p4-hlir项目解析p4，可以看成p4语言的python解析器，生成对应的python对象。
基于这个解析结果可以再加上模板输出json或者c, 或者RTL，或者DPDK，或者NP的微码。。
BMv2 ...
注意：BMv2是最新的模型，请参考后面文章，这个仅供参考10/16/2016
==============================
p4lang官网p4.org上的视频比较老，不能简单执行成功，下面是根据p4factory的guide安装过程，运行成功，仅供参考：
#虚拟机安装ubuntu1404版本，升级到最新
#克隆p4factory mast分支
git clone https://github.com/p4lang/p4factory.git
cd p4factory
git submodule update --init --recursive
引用 # 用github ...