四年前写过一篇小内存拷贝优化：https://www.skywind.me/blog/archives/143
纠结了一下还是把全尺寸拷贝优化代码发布出来吧，没啥好保密的，
如今总结一下全尺寸内存拷贝优化的要点：
1. 策略区别：64字节以内用小内存方案，64K以内用中尺寸方案，大于64K用大内存拷贝方案。
2. 查表跳转：拷贝不同小尺寸内存，直接跳转到相应地址解除循环。
3. 目标对齐：64字节以上拷贝的先用普通方法拷贝几个字节让目标地址对齐，好做后面的事情。
4. 矢量拷贝：并行一次性读入N个矢量到 sse2 寄存器，再并行写出。
5. 缓存预取：使用 prefetchnta ，提前预取数据，等到真的要用时数据已经到位。
6. 内存直写：使用 movntdq 来直写内存，避免缓存污染。
部分理论，见论文：《Using Block Prefetch for Optimized Memory Performance 》
但论文考虑问题比较单一，所以实际代码写的比论文复杂不少，目前在各个尺寸上基本平均能够加速 40%，比较GCC 4.9, VS2012的 memcpy，不排除未来的 libc, crt库继续完善以后，能够达到下面代码的速度。但我看libc和crt的 memcpy代码已经很久没人更新了，不知道他们还愿意继续优化下去么？
行了，具体实现各位读代码吧，需要 SSE2 指令集支持，gcc编译时需要 –msse2 一下，点击（more）展开代码，测试结果附在源文件最后注释部分：
Read more…
要彻底理解视频编码原理，看书都是虚的，需要实际动手，实现一个简单的视频编码器：
知识准备：基本图像处理知识，信号的时域和频域问题，熟练掌握傅立叶正反变换，一维、二维傅立叶变换，以及其变种，dct变换，快速dct变换。
来自知乎问题：http://www.zhihu.com/question/22567173/answer/73610451
第一步：实现有损图像压缩和解压
参考 JPEG原理，将 RGB->YUV，然后 Y/U/V 看成三张不同的图片，将其中一张图片分为 8×8的 block进行 dct变换（可以直接进行二维 dct变换，或者按一定顺序将 8×8的二维数组整理成一个64字节的一维数组），还是得到一个 8×8的整数频率数据。于是表示图像大轮廓的低频信号（人眼敏感的信号）集中在 8×8的左上角；表示图像细节的高频信号集中在右下角。
接着将其量化，所谓量化，就是信号采样的步长，8×8的整数频率数据块，每个数据都要除以对应位置的步长，左上角相对重要的低频信号步长是 1，也就是说 0-255，是多少就是多少。而右下角是不太重要的高频信号，比如步长取 10，那么这些位置的数据都要 /10，实际解码的时候再将他们 x10恢复出来，这样经过编码的时候 /10 和解码的时候 x10，那么步长为 10的信号1, 13, 25, 37就会变成规矩的：0, 10, 20, 30, 对小于步长 10的部分我们直接丢弃了，因为高频不太重要。
经过量化以后，8×8 的数据块左上角的数据由于步长小，都是比较离散的，而靠近右下角的高频数据，都比较统一，或者是一串0，因此图像大量的细节被我们丢弃了，这时候，我们用无损压缩方式，比如 lzma2算法（jpeg是 rle + huffman）将这 64个 byte压缩起来，由于后面高频数据步长大，做了除法以后，这些值都比较小，而且比较靠近，甚至右下部分都是一串0，十分便于压缩。
JPEG 图像有个问题就是低码率时 block边界比较严重，现代图片压缩技术往往要配合一些 de-block算法，比如最简单的就是边界部分几个像素点和周围插值模糊一下。
做到这里我们实现了一个同 jpeg类似的静态图片有损压缩算法。在视频里面用来保存I帧数据。
第二步：实现宏块误差计算
视频由连续的若干图像帧组成，分为 I帧，P帧，所谓I帧，就是不依赖就可以独立解码的视频图像帧，而 P帧则需要依赖前面已解码的视频帧，配合一定数据才能生成出来。所以视频中 I帧往往都比较大，而P帧比较小，如果播放器一开始收到了 P帧那么是无法播放的，只有收到下一个I帧才能开始播放。I帧多了视频就变大，I帧少了，数据量是小了，但视频受到丢包或者数据错误的影响却又会更严重。
Read more…
同范畴类似的东西中，虚拟机开发比操作系统和编译器都有意思：
操作系统能玩的好玩的不多，做完进程管理和内存管理，其他就是脏活累活了，要得到一个成型可用的东西，没有一个团队弄不了，个人玩不转。以前调侃过这个话题：
关于LMOS自主操作系统的发展，大家有什么建议？ – 韦易笑的回答
而编译器方面，优化和代码生成有llvm，用不着自己开发，其他部分基本上是一个固定套路，照着文档照着书，按固定套路来即可。
以 Lua为例，最精巧的部分就是 Lua虚拟机的实现，整个 Lua-5.3 代码中，编译部分只占2000行，剩下两万行全在实现虚拟机。大家津津乐道的各种 lua 奇技淫巧全都在它的虚拟机实现部分中。
Ruby更是如此，整个ruby代码除去库实现外，基本在实现ruby的虚拟机，编译器部分作者都懒得怎么写，直接一个的 .y文件搞定，精力都在ruby虚拟机实现上。
虚拟机难是难在开头的设计，怎样最精巧，怎样没有逻辑漏洞，别写着写着发现前后逻辑矛盾了，设计好以后就要开始架构了，先从最简单的 switch case opcode实现起来，很快你就能得到反馈看到自己的工作成果，接下来给虚拟机实现符号表，object，实现 gc，实现各种容器，优化性能，在内存中翻译成本地指令码，然后实现多线程，再给你的虚拟机实现一门汇编语言，每走一步都很有意思。且虚拟机相关的技术目前还在日新月异的发展着，光一个gc，每年都能看到很多新方法出现，大有需要继续改进迭代的地方。
实现虚拟机需要覆盖很多知识面，虚拟机设计的好，还可以嫁接很多其他语言，让这些新语言来这个虚拟机上运行。
大家夸 v8 都是说它虚拟机运行速度快，内存少，没人说 v8 的编译部分如何如何，以至于很多新语言都以v8虚拟机为运行环境。
同样，每年都有很多人尝试重新实现 lua vm，引入更灵巧的机制或者使用更新的 JIT方法。来pk官方runtime, 以及 luajit，好多人或多或少在某些方面都能并发出很多奇思妙想。
相反，从来没人碰 lua 的编译部分，为啥啊？就那样了，还碰它干嘛，没意思了啊。
用不同测试用例具体测试 softfp, armv7-a, cortax 等优化选项，看选项不同性能差别多大。首先设计下面几个测试用例，包含字符串处理、复杂逻辑、整数运算、浮点运算几个方面：
compress：进行 LZO/LZW 大规模压缩，测试搜索，字符串匹配，复杂分支等性能
resample：进行一系列整数 DSP 运算，包括 resample 和 fir low pass
int add：一亿次整数加法
int mul：一亿次整数乘法
int div：一亿次整数除法
float add：一亿次浮点加法
float mul：一亿次浮点乘法
float div：一亿次浮点除法
const div：一亿次整数除以常数255
matrix：若干次矩阵乘法运算，同时考察浮点数乘法加法
normalize：若干次矢量归一化运算，同时考察浮点数乘法，除法，加法，sqrt
其次对安卓的几个 gcc 的编译选项进行分别测试：
-mfloat-abi=softfp，如果有硬件浮点处理器将会使用硬件，如果没有会转移到软件模拟
-march=armv7-a，生成适合 armv7a 架构的代码
-mtune=cortex-9，代码生成按照 cortex-9 进行调优
–mfpu=neon，使用 neon 进行硬件浮点运算，决定 softfp 的硬件方式到底用这个
-mfpu=vfp，使用 vfp 进行硬件浮点运算，决定 softfp 的硬件方式用这个
测试硬件：
桌面电脑：Intel® Core™ i5-2520M CPU @ 2.50GHz
安卓手机：三星，双核 CPU 1.73GHz armv7-a cortex-9
结果如下：
Read more…
传统方式调试 NDK 开发的程序比较麻烦，先要编译成 JNI，又要导出 java接口，还要再写一个 java 工程，改一个地方又要连续改几处，这样效率是很低的。最频繁使用的关键工作路径（编译/调试环节）如果能极致简化，那么可以带来开发效率的成倍提升。其实安卓官方是提供了命令行调试方法的，将你需要调试的 C代码用 NDK直接编译成可执行，然后到设备上执行：
使用 NDK 导出独立工具链，方便以后使用，在 cygwin 下面，将 $NDK 环境变量代表的路径设置好，然后：
cd $NDK
这样就导出了一套针对 API9 的独立工具链（包含 gcc, ld, ndk必要文件），以后方便使用，比如导出到 d:\android-9下面，那么以后可以跳过 cygwin，直接编译我们的 Hello World：
d:\android-9\bin\arm-linux-androideabi-gcc.exe hello.c –o hello
于是你可以在命令行下直接开发 Android 的非 GUI 应用程序了。
调试也很简单，用 adb push 上传到 /data/local/tmp 下面，并且设置可执行模式为 755：
adb push hello /data/local/tmp/hello
运行就是直接：
adb shell /data/local/tmp/hello
不要传到其他目录，比如 /sdcard，这些目录 mount时有 NOEXEC 权限，不能给文件增加可执行权限，而 /data/local/tmp 就是留给大家调试命令行用的，并且不需要 root 权限。
可以编写一些脚本，每次编译好自动上传，配置到你的 Editplus/Vim/Npp 中，一键编译上传，一键运行。比起以前调试下 C代码还需要写一大堆 jni 和 java 的方式，效率高极了。
实现个简单的固定渲染管线软渲染器不算复杂，差不多700行代码就可以搞定了。之所以很多人用 D3D用的很熟，写软渲染却坑坑洼洼，主要是现在大部分讲图形的书，讲到透视投影时就是分析一下透视变换矩阵如何生成，顶点如何计算就跳到其他讲模型或者光照的部分了。
因为今天基本上是直接用 D3D 或者 OGL，真正光栅化的部分不了解也不影响使用，所以大部分教材都直接跳过了一大段，摄像机坐标系如何转换？三角形如何生成？CVV边缘如何检测？四维坐标如何裁剪？边缘及步长如何计算？扫描线该如何绘制？透视纹理映射具体代码该怎么写？framebuffer zbuffer 到底该怎么用？z-test 到底是该 test z 还是 w 还是 1/z 还是 1/w ？这些都没讲。
早年培训学生时候，我花两天时间写的一个 DEMO，今天拿出来重新调整注释一下，性能和功能当然比不过高大上的软件渲染器。但一般来讲，工程类项目代码不容易阅读，太多边界情况和太多细节优化容易让初学者迷失，这个 mini3d 的项目不做任何优化，主要目的就是为了突出主干：
源代码：skywind3000/mini3d · GitHub http://www.skywind.me/mw/images/c/c8/Mini3d.7z
操作方式：左右键旋转，前后键前进后退，空格键切换模式，ESC退出。
特性介绍：
单个文件：源代码只有一个 mini3d.c，单个文件实现所有内容，阅读容易。
独立编译：没有任何第三方库依赖，没有复杂的工程目录。
模型标准：标准 D3D 坐标模型，左手系 + WORLD/VIEW/PROJECTION 三矩阵
实现裁剪：简单 CVV 裁剪
纹理支持：最大支持 1024 x 1024 的纹理
深度缓存：使用深度缓存判断图像前后
边缘计算：精确的多边形边缘覆盖计算
透视贴图：透视纹理映射以及透视色彩填充
实现精简：渲染部分只有 700行， 模块清晰，主干突出。
详细注释：主要代码详细注释
截图效果
颜色填充
透视纹理映射
Read more…
通常工程里不推荐自己写内存分配器，因为你费力写一个出来99%可能性没有内置的好，且内存出bug难调试
1. 实现教科书上的内存分配器：
做一个链表指向空闲内存，分配就是取出一块来，改写链表，返回，释放就是放回到链表里面，并做好归并。注意做好标记和保护，避免二次释放，还可以花点力气在如何查找最适合大小的内存快的搜索上，减少内存碎片，有空你了还可以把链表换成伙伴算法，写着玩嘛。
2. 实现固定内存分配器：
即实现一个 FreeList，每个 FreeList 用于分配固定大小的内存块，比如用于分配 32字节对象的固定内存分配器，之类的。每个固定内存分配器里面有两个链表，OpenList 用于存储未分配的空闲对象，CloseList用于存储已分配的内存对象，那么所谓的分配就是从 OpenList 中取出一个对象放到 CloseList 里并且返回给用户，释放又是从 CloseList 移回到 OpenList。分配时如果不够，那么就需要增长 OpenList：申请一个大一点的内存块，切割成比如 64 个相同大小的对象添加到 OpenList中。这个固定内存分配器回收的时候，统一把先前向系统申请的内存块全部还给系统。
3. 实现 FreeList 池：
在你实现了 FreeList的基础上，按照不同对象大小（8字节，16字节，32，64，128，256，512，1K。。。64K），构造十多个固定内存分配器，分配内存时根据内存大小查表，决定到底由哪个分配器负责，分配后要在头部的 header 处（ptr[-sizeof(char*)]处）写上 cookie，表示又哪个分配器分配的，这样释放时候你才能正确归还。如果大于64K，则直接用系统的 malloc作为分配，如此以浪费内存为代价你得到了一个分配时间近似O（1）的内存分配器，差不多实现了一个 memcached 的 slab 内存管理器了，但是先别得意。此 slab 非彼 slab（sunos/solaris/linux kernel 的 slab）。这说白了还是一个弱智的 freelist 无法归还内存给操作系统，某个 FreeList 如果高峰期占用了大量内存即使后面不用，也无法支援到其他内存不够的 FreeList，所以我们做的这个和 memcached 类似的分配器其实是比较残缺的，你还需要往下继续优化。
Read more…
通常来讲，就是利用 select 的空余时间，来进行时钟检查，不管是 select / poll / epoll/ kevent，以下统称 select，它有一个等待时间作为参数，即没有事件时，最多 wait 多少时间，我们把这个作为网络库的基准频率，比如 10MS，或者 20MS, 25MS, 50MS，都是常用的几个值。
就是说网络库调用 select 等待事件时如果没有事件，那么最长等待 10MS 就返回了，这时再处理完所有网络事件后，就可以来处理时钟数据了。事件处理函数就是这样：
def update_events(milisec = 10):
while 1:
关键就是这个两次 select 中间 update_timer 的任务：集合中检查需要唤醒的时钟，并且调用它们的回调函数，来驱动整个服务器的时钟运行，以最简单的扫描法为例：
def update_timer (current):
available_timers 记录着当前可用的所有 timer 的集合，expires 是他们需要被触发的时间，如果当前时间大于等于这个 expires，认为该 timer 需要被触发到。注意 timer.expires 更新的时候是 += 周期，而不是 = current + 周期，后者会导致误差积累，长时间运行后偏差越来越大。同时这里需要 while，因为可能跨越两个以上周期，当然只运行一次的 timer 就不需要了，这里只是简化下。
比如 libevent 里面的主循环 event_base_loop 每次 select 完毕后就调用一次 timeout_process。
这就是 Timer 调度的基本原理。
可能你会发现每次 select 结束都要扫描整个 available_timers 集合，是一个非常费时间的事情，那么首先想到的就是优先队列了：将 Timer 节点按照 expires 的先后顺序，将最快要发生的超时节点放在前面，每次检测队列头就可以判断是否超时了。
Read more…
Recent Comments