定点数优化:性能成倍提升

定点数这玩意儿并不是什么新东西,早年 CPU 浮点性能不够,定点数技巧大量活跃于各类图形图像处理的热点路径中。今天 CPU 浮点上来了,但很多情况下整数仍然快于浮点,因此比如:libcario (gnome/quartz 后端)及 pixman 之类的很多库里你仍然找得到定点数的身影。那么今天我们就来看看使用定点数到底能快多少。

简单用一下的话,下面这几行宏就够了:

#define cfixed_from_int(i)      (((cfixed)(i)) << 16)
#define cfixed_from_float(x)    ((cfixed)((x) * 65536.0f))
#define cfixed_from_double(d)   ((cfixed)((d) * 65536.0))
#define cfixed_to_int(f)        ((f) >> 16)
#define cfixed_to_float(x)      ((float)((x) / 65536.0f))
#define cfixed_to_double(f)     ((double)((f) / 65536.0))
#define cfixed_const_1          (cfixed_from_int(1))
#define cfixed_const_half       (cfixed_const_1 >> 1)
#define cfixed_const_e          ((cfixed)(1))
#define cfixed_const_1_m_e      (cfixed_const_1 - cfixed_const_e)
#define cfixed_frac(f)          ((f) & cfixed_const_1_m_e)
#define cfixed_floor(f)         ((f) & (~cfixed_const_1_m_e))
#define cfixed_ceil(f)          (cfixed_floor((f) + 0xffff))
#define cfixed_mul(x, y)        ((cfixed)((((int64_t)(x)) * (y)) >> 16))
#define cfixed_div(x, y)        ((cfixed)((((int64_t)(x)) << 16) / (y)))
#define cfixed_const_max        ((int64_t)0x7fffffff)
#define cfixed_const_min        (-((((int64_t)1) << 31)))
typedef int32_t cfixed;

类型狂可以写成 inline 函数,封装狂可以封装成一系列 operator xx,如果需要更高的精度,可以将上面用 int32_t 表示的 16.16 定点数改为用 int64_t 表示的 32.32 定点数。

那么我们找个浮点数的例子优化一下吧,比如 libyuv 中的 ARGBAffineRow_C 函数:

void ARGBAffineRow_C(const uint8_t* src_argb,
                     int src_argb_stride,
                     uint8_t* dst_argb,
                     const float* uv_dudv,
                     int width) {
  int i;
  // Render a row of pixels from source into a buffer.
  float uv[2];
  uv[0] = uv_dudv[0];
  uv[1] = uv_dudv[1];
  for (i = 0; i < width; ++i) {
    int x = (int)(uv[0]);
    int y = (int)(uv[1]);
    *(uint32_t*)(dst_argb) = *(const uint32_t*)(src_argb + y * src_argb_stride + x * 4);
    dst_argb += 4;
    uv[0] += uv_dudv[2];
    uv[1] += uv_dudv[3];
  }
}

这个函数是干什么用的呢?给图像做 仿射变换(affine transformation) 用的,比如 2D 图像库或者 ActionScript 中可以给 Bitmap 设置一个 3×3 的矩阵,然后让 Bitmap 按照该矩阵进行变换绘制:

基本上二维图像所有:缩放,旋转,扭曲都是通过仿射变换完成,这个函数就是从图像的起点(u, v)开始按照步长(du, dv)进行采样,放入临时缓存中,方便下一步一次性整行写入 frame buffer。

这个采样函数有几个特点:

  • 运算简单:没有复杂的运算,计算无越界,不需要求什么 log/exp 之类的复杂函数。
  • 范围可控:大部分图像长宽尺寸都在 32768 范围内,用 16.16 的定点数即可。
  • 转换频繁:每个点的坐标都需要从浮点转换成整数,这个操作很费事。

适合用定点数简单重写一下:(点击 Read more 展开)

Continue reading

Loading

Posted in 编程技术 | Tagged | Leave a comment

快除 255:到底能有多快?

真金不怕火炼,我先前在《C 语言有什么奇技淫巧?》中给出的整数快速除以 255 的公式:

#define div_255_fast(x)    (((x) + (((x) + 257) >> 8)) >> 8)

有人觉得并没有快多少,还给出了测试

红色为 255 快除法的消耗时间,看他的测试好像也只快了那么一点,是这样的么?

并非如此,我们只要把测试用例中的 long long j 改成 int j 就有比较大的性能提升了:

链接:http://quick-bench.com/t3Y2-b4isYIwnKwMaPQi3n9dmtQ

这才是真实的快除法性能。

原评测的作者其他地方都是用 int ,这里故意改成 64 位去和原始的 / 255 对齐,引入一个干扰项,得到一个比较慢的结果,到底是为了黑而黑呢?还是别的什么原因?

编译器生成的 / 255 方法是把 x / 255 换成定点数的 x * (1/255):

(点击 Read more 展开)

Continue reading

Loading

Posted in 编程技术 | Tagged | Leave a comment

快速范围判断:再来一种新写法

C 语言的魔法数不胜数,我在《C 语言有什么奇技淫巧?》中过给快速范围判断的公式,将:

if (x >= minx && x <= maxx) ...

改做:

if (((x - minx) | (maxx - x)) >= 0) ...

能有一倍的性能提升,我也提到,如果你的数据 99% 都是超出范围的那继续用 && 最快。今天再给大家介绍另外一种新写法,它有更均衡的性能,并且在最坏的情况下,任然表现良好:

if ((unsigned)(x - minx) <= (unsigned)(maxx - minx)) ...

该公式在各种测试数据中能有更均衡的表现,类型安全狂们可以写作:

if (((unsigned)x - (unsigned)minx) <= ((unsigned)maxx - (unsigned)minx)) ...

利用单次无符号整数溢出来减少指令和分支,普通情况,这个公式性能照样快接近一倍:

链接:http://quick-bench.com/EbCR9psA3lUEhpn8bYLwVtJ-FWk

为什么说它综合性能最好呢?是不是只实用于某些特殊情况呢?普通情况如何?汇编指令有啥区别?理论依据是啥?是不是只有 x86 可以用,换个平台就不行呢?下面依次回答:

(点击 Read more 展开)

Continue reading

Loading

Posted in 编程技术 | Tagged | Leave a comment

C 语言有什么奇技淫巧?

C 语言的技巧有很多,列一些和性能有关的:

快速范围判断

经常要批量判断某些值在不在范围内,如果 int 检测是 [0, N) 的话:

if (x >= 0 && x < N) ...

众所周知,现代 CPU 优化,减分支是重要手段,上述两次判断可以简写为:

if (((unsigned int)x) < N) ...

减少判断次数。如果 int 检测范围是 [minx, maxx] 这种更常见的形式的话,怎么办呢?

if (x >= minx && x <= maxx) ...

可以继续用比特或操作继续减少判断次数:

if (( (x - minx) | (maxx - x) ) >= 0) ...

如果语言警察们担心有符号整数回环是未定义行为的话,可以写成这样:

if ((int32_t)(((uint32_t)x - (uint32_t)minx) | ((uint32_t)maxx - (uint32_t)x)) > = 0) ...

性能相同,但避开了有符号整数回环,改为无符号回环,合并后转为有符号判断最高位。

第一个 (x – minx) 如果 x < minx 的话,得到的结果 < 0 ,即高位为 1,第二个判断同理,如果超过范围,高位也为 1,两个条件进行比特或运算以后,只有两个高位都是 0 ,最终才为真,同理,多个变量范围判断整合:

if (( (x - minx) | (maxx - x) | (y - miny) | (maxy - y) ) >= 0) ...

这样本来需要对 [x, y] 进行四次判断的,可以完全归并为一次判断,减少分支。

补充:加了个性能评测

性能提升 37%。快速范围判断还有第二个性能更均衡的版本:

if ((unsigned)(x - minx) <= (unsigned)(maxx - minx)) ...

快速范围判断的原理和评测详细见:《快速范围判断:再来一种新写法》。

更好的循环展开

很多人提了 duff’s device ,按照 gcc 和标委会丧心病狂的程度,你们用这些 just works 的代码,不怕哪天变成未定义行为给一股脑优化掉了么?其实对于循环展开,可以有更优雅的写法:

#define CPU_LOOP_UNROLL_4X(actionx1, actionx2, actionx4, width) do { \
    unsigned long __width = (unsigned long)(width);    \
    unsigned long __increment = __width >> 2; \
    for (; __increment > 0; __increment--) { actionx4; }    \
    if (__width & 2) { actionx2; } \
    if (__width & 1) { actionx1; } \
}   while (0)

送大家个代替品,CPU_LOOP_UNROLL_4X,用于四次循环展开,用法是:

(点击 Read more 展开)

Continue reading

Loading

Posted in 编程技术 | Tagged | Leave a comment

支持 Win10 的网络环境模拟(丢包,延迟,带宽)

升级 Windows 10 以后,原来各种网络模拟软件都挂掉了,目前能用的就是只有 clumsy

唯一问题是不支持模拟带宽,那么平时要模拟一些糟糕的网络情况的话,是不太方便的,而开虚拟机用 Linux tc 或者设置个远程 linux 网关又很蛋疼,于是我顺便给他加了个带宽模拟功能:

注意最下面的 “Bandwidth” 选项,打上勾的话,就能顺利限速了,注意上面的 Filtering 需要填写正确的 WinDivert 规则。

注意,统计包大小时用的是整个 IP 包的大小(包括各种协议头),所以你设置成 500 KB/s 的话,实际按 tcp 计算的下载速率会略小。

二进制下载:

想自己检查自己编译的话:

欢迎 PR。

Loading

Posted in 网络编程 | Tagged | Leave a comment

Vim 8 中的 C/C++ 编译运行:类 vscode 的任务系统

谦卑的向大家介绍我的新插件:asynctasks.vim,一套类似 vscode 的 tasks 系统,用于解决 vim 下长期没法轻松优雅的编译/运行 C/C++ 程序的问题。这个插件我去年酝酿了很长时间了,今年打算给他做一点宣传。

最近两年 Vim/NeoVim 发展非常迅速,各种:异步补全/LSP/查错,DAP 等项目相继出现,就连 vimspector 这样以前只能奢望 emacs 的项目如今都出现了。

然而 Vim 任然缺少一套优雅的通用的任务系统来加速你的内部开发循环(编辑,编译,测试)。很多人在处理这些 编译/测试/部署 类任务时,任然还在使用一些比较原始的方法,所以我创建了这个插件,将 vscode 的任务系统引入 Vim。

vscode 为每个项目的根目录下新建了一个 .vscode 目录,里面保存了一个 tasks.json 配置文件来描述针对该项目的各类:编译/运行任务。而 asynctasks.vim 采用类似的机制,在每个项目的根文件夹下面放一个 .tasks 配置文件来描述针对该项目的任务,同时维护一份 ~/.vim/tasks.ini 的全局配置,适配一些通用性很强的项目,避免每个项目重复写 tasks 配置。

说起来好像很简单?其实这是概念简单,很多好的设计从概念上来讲往往非常简单,但是用起来却十分灵活强大,这不是我设计的好,而是 vscode 的 tasks 系统设计的好,我只是大自然的搬运工,这应该是目前 Vim 下最强的构建工具,下面就试用一下:

Continue reading

Loading

Posted in 随笔 | Tagged | Leave a comment

用好你的瑞士军刀/netcat

Netcat 号称 TCP/IP 的瑞士军刀并非浪得虚名,以体积小(可执行 200KB)功能灵活而著称,在各大发行版中都默认安装,你可以用它来做很多网络相关的工作,熟练使用它可以不依靠其他工具做一些很有用的事情。

最初作者是叫做“霍比特人”的网友 Hobbit hobbit@avian.org 于 1995 年在 UNIX 上以源代码的形式发布,Posix 版本的 netcat 主要有 GNU 版本的 netcat 和 OpenBSD 的 netcat 两者都可以在 debian/ubuntu 下面安装,但是 Windows 下面只有 GNU 版本的 port。

不管是程序员还是运维,熟悉这个命令都可以让很多工作事半功倍,然而网上基本 90% 的 netcat 文章说的都是老版本的 OpenBSD 的 netcat,已经没法在主流 linux 上使用了,所以我们先要检查版本:

在 debian/ubuntu 下面:

readlink -f $(which nc)

看看,结果会有两种:

  • /bin/nc.traditional: 默认 GNU 基础版本,一般系统自带。
  • /bin/nc.openbsd: openbsd 版本,强大很多。

都可以用 apt-get install nc-traditional 或者 apt-get install nc-openbsd 来选择安装。不管是 gnu 版本还是 openbsd 版本,都有新老的区别,主要是传送文件时 stdin 发生 EOF 了,老版本会自动断开,而新的 gnu/openbsd 还会一直连着,两年前 debian jessie 时统一升过级,导致网上的所有教程几乎同时失效。

下面主要以最新的 GNU 版本为主同时对照更强大的 openbsd 版本进行说明。

端口测试

你在服务器 A主机(192.168.1.2) 上面 8080 端口启动了一个服务,有没有通用的方法检测服务的 TCP 端口是否启动成功?或者在 B 主机上能不能正常访问该端口?

进一步,如果而 A 主机上用 netstat -an 发现端口成功监听了,你在 B 主机上的客户端却无法访问,那么到底是服务错误还是网络无法到达呢?我们当然可以在 B 主机上用 telnet 探测一下:

telnet 192.168.1.2 8080

但 telnet 并不是专门做这事情的,还需要额外安装,所以我们在 B 主机上用 netcat:

nc -vz 192.168.1.2 8080

即可,v 的意思是显示多点信息(verbose),z 代表不发送数据。那么如果 B 主机连不上 A 主机的 8080 端口,此时你就该检查网络和安全设置了,如果连的上那么再去查服务日志去。

nc 命令后面的 8080 可以写成一个范围进行扫描:

nc -v -v -w3 -z 192.168.1.2 8080-8083

两次 -v 是让它报告更详细的内容,-w3 是设置扫描超时时间为 3 秒。

传输测试

你在配置 iptable 或者安全组策略,禁止了所有端口,但是仅仅开放了 8080 端口,你想测试一下该设置成功与否怎么测试?安装个 nginx 改下端口,外面再用 chrome 访问下或者 telnet/curl 测试下??还是 python -m 启动简单 http 服务 ?其实不用那么麻烦,在需要测试的 A 主机上:

nc -l -p 8080

这样就监听了 8080 端口,然后在 B 主机上连接过去:

nc 192.168.1.2 8080

两边就可以会话了,随便输入点什么按回车,另外一边应该会显示出来,注意,openbsd 版本 netcat 用了 -l 以后可以省略 -p 参数,写做:nc -l 8080 ,但在 GNU netcat 下面无法运行,所以既然推荐写法是加上 -p 参数,两个版本都通用。

老版本的 nc 只要 CTRL+D 发送 EOF 就会断开,新版本一律要 CTRL+C 结束,不管是服务端还是客户端只要任意一边断开了,另一端也就结束了,但是 openbsd 版本的 nc 可以加一个 -k 参数让服务端持续工作。

那么你就可以先用 nc 监听 8080 端口,再远端检查可用,然后又再次随便监听个 8081 端口,远端检测不可用,说明你的安全策略配置成功了,完全不用安装任何累赘的服务。

(点击 Read more 展开)

Continue reading

Loading

Posted in 网络编程 | Tagged , | Leave a comment

最近都流行实现 Coroutine 么 ?

这两天看着大家都在实现无栈的 coroutine 都挺好玩的,但无栈协程限制太多,工程实践上很少用,所以昨天手痒写了个有栈的 coroutine ,接口反照 ucontext 的接口,不比无栈的复杂多少:

int main(void)
{
    ctx_context_t r;
    int hr;
    volatile int mode = 0;

    hr = ctx_getcontext(&r);
    printf("ctx_getcontext() -> %d\n", hr);

    if (mode == 0) {
        mode++;
        printf("first run\n");
        ctx_setcontext(&r);
    }
    else {
        printf("second run\n");
    }
    printf("endup\n");

    return 0;
}

使用 ctx_getcontext / ctx_setcontext 可以实现保存现场,恢复现场的功能,该程序输出:

ctx_getcontext() -> 0
first run
ctx_getcontext() -> 6356604
second run
endup

继续使用 ctx_makecontext / ctx_swapcontext 可以实现初始化协程和切换上下文的功能:

char temp_stack[32768];
ctx_context_t mc, cc;

int raw_thread(void*p) {
    printf("remote: hello %s\n", (char*)p);
    ctx_swapcontext(&cc, &mc);

    printf("remote: back again\n");
    ctx_swapcontext(&cc, &mc);

    printf("remote: return\n");
    return 1024;
}

int main(void)
{
    cc.stack = temp_stack;
    cc.stack_size = sizeof(temp_stack);
    cc.link = &mc;

    ctx_getcontext(&cc);
    ctx_makecontext(&cc, raw_thread, (char*)"girl");

    printf("before switch: %d\n", cc.stack_size);
    ctx_swapcontext(&mc, &cc);

    printf("local: here\n");
    ctx_swapcontext(&mc, &cc);

    printf("local: again\n");
    ctx_swapcontext(&mc, &cc);

    printf("local: end\n");
    return 0;
}

这里创建了一个协程,接着主程序和协程互相切换,程序输出:

before switch: 32768
remote: hello girl
local: here
remote: back again
local: again
remote: return
local: end

关于实现

核心代码其实很简单,就 60 多行,没啥复杂的:

(点击 Read more 展开)

Continue reading

Loading

Posted in 编程技术 | Tagged | Leave a comment