Oct 26, 2018 - 跟着 clang 的 libcxx 学习二分查找

哪个算法简单到初学编程的人都能轻松实现,但有多年编程经验的人也可能会写出严重的 bug 呢?没错,正是二分查找。既然普通人的二分查找容易写错,那专业人士会如何实现二分查找呢?不妨参考一下 clang 7.0 的实现。

lower_bound 是指在区间 [first, last) 中,对于任意 i < j,若 comp(A[i]) 为真,则 comp(A[j]) 必为真。如下图

lower_bound

让我们看一看 lower_bound 的实现

__lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
{
    typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
    difference_type __len = _VSTD::distance(__first, __last);
    while (__len != 0)
    {
        difference_type __l2 = __len / 2;
        _ForwardIterator __m = __first;
        _VSTD::advance(__m, __l2);
        if (__comp(*__m, __value_))
        {
            __first = ++__m;
            __len -= __l2 + 1;
        }
        else
            __len = __l2;
    }
    return __first;
}
// This file is dual licensed under the MIT and the UIUC license.

代码很精简,不到十行,注意几个关键点就不会写错

  1. 定义:first 是第一个有可能为真的元素
  2. 迭代:l2 < len 恒成立,因此 first+l2 就不会越界。同时,每次迭代时 len 严格递减
  3. 迭代结束:l2 == 0 当且仅当 len == 1。这是我们最后一次进行迭代
  4. 特殊情况:如果所有的元素都为假,那最后一次迭代时, ++m 的结果正是 last

相比我之前写的不时丢弃真值、出现死循环的二分查找,clang 的代码可是高到不知道哪里去了。

upper_bound 的实现 看起来是相反的,不过从布尔值的角度看,与 lower_bound 是一样的,我就不复制代码了。

上文中的示意图使用 R 语言绘制,参考了 Stack Overflow 上画棋盘的讨论。代码如下

b <- matrix(nrow=1,ncol=6)            
colorindex <- c(rep(0, 4), rep(1, 2))
# for each square
colors <- c("red", "green")[colorindex+1] # choose colors
side <- 1/8                               # side of one square
ux <- col(b)*side                         # upper x values
lx <- ux-side                             # lower x values
uy <- row(b)*side                         # upper y
ly <- uy-side                             # upper y
plot.new()                                # initialize R graphics
rect(lx, ly, ux, uy, col=colors, asp=1)   # draw the board

最后,按照惯例推荐一本书 Effective C++:改善程序与设计的55个具体做法(第3版)

Sep 15, 2018 - 用 distcc 加快编译 续篇-clang

上一篇文章 简单介绍了使用 distcc 编译 wine 代码。有人在朋友圈里问我,能不能用 clang 编译。我当时的回答是,为什么不能呢?这周在摸鱼的时候,我完成了测试。

理论分析

我看了一下 distcc 的代码,发现其机制还是比较简单的。distcc 后的一个参数会被当成编译器名称。理论上,不管是 gcc 还是 clang,都应该可以用类似的机制在多台电脑间分发。

实战演练

因为这里仅仅是为了测试,而不是实际运行,我就不用麻烦地在 32-bit 和 64-bit下编译 wine 两次了。workflow如下

function mkwine_clang()
{
    export CC="clang-6.0"
    export CXX="clang-6.0"
    export CFLAGS="-O0"
    export JOBS=8
    mkdir -p ~/src/wine_n_extras/wine-clang
    cd ~/src/wine_n_extras/wine-clang
    ../wine/configure --enable-win64
    make -j$JOBS
}

wine 项目组对 clang 投入的精力 是有回报的。我没有做任何额外的设置,就在本机成功编译了 wine

在 Ubuntu 上安装 clang 非常简单。很有趣的是,在我的 Ubuntu 14 工作站上,clang 默认是指向 clang-3.3clang-3.5 的软链接。不过,在工作站和笔记本上,/usr/bin/clang-6.0 都是可用的。因此,我们可以对编译的 workflow 稍加修改

function mkwine_clang()
{
    export CC="distcc clang-6.0"
    export CXX="distcc clang-6.0"
    export CFLAGS="-O0"
    export JOBS=8
    export DISTCC_HOSTS="@beddp,lzo"
    mkdir -p ~/src/wine_n_extras/wine-clang
    cd ~/src/wine_n_extras/wine-clang
    ../wine/configure --enable-win64
    make -j$JOBS
}

在我的电脑上,这一流程非常的顺利。理论分析和实践演练同时成功的情景真是太少了。

In theory, theory and practice are the same. In practice, they are not. -Anonymous

不仅仅是C

上文提到,distcc 判断编译器的方法很简单。那么,能不能用它来分发其他语言呢?很抱歉,这可能不行。dcc_scan_args 函数会尝试解析编译选项。如果要使用其他的编译器,个人猜测,必要条件包括使用与 gccclang 相同的编译选项。[Rust 社区在 2017 年年末进行了讨论](https://users.rust-lang.org/t/contract-opportunity-mozilla-distributed-compilation-cache-written-in-rust/13898),但好像并没有得出太好的解决方案。
不过,这也称不上太大的损失。人生苦短,在 C/C++/Rust 以外,我们也不再需要一门编译超慢的语言了,不是吗?

Sep 10, 2018 - 用 distcc 加快编译

我的卧室迎来了新成员 - 拥有双 Xeon E5649 的工作站。在安顿好后,我就第一时间开始研究用 distcc 来加快编译速度了。毕竟,与其让我的 XPS 15 被折磨,不如把这个工作交给局域网内的工作站。官网提供了一份 60-second instructions ,不妨一试。如果你是在60秒内完成了配置的幸运儿,那请关掉本页面。如果你遇到了阻碍,那么请看下一节。

Server / Slaves / 工作站设置

为了方便地调试,我选择在工作站上运行 distccd --no-detach --daemon --allow 192.168.1.0/24 --log-stderr --verbose -j 1
在新版本的 distcc 里,--allow参数已经是必选项了。在完成了调试后,我在生产环境中设置成了 -j 10,避免将 12 核都跑满后,ssh访问工作站会有一定延迟。另一种解决方法是,通过设置 nice 避免吃光资源。

本地设置

支线任务 - SSH name

通过~/.ssh/config 可以给自己局域网中的电脑分配一个简单易记的名字。我将我的工作站命名为了 beddp。不设置不影响使用。如果第一次接触这一概念,可以阅读 https://serverfault.com/a/215027

主线任务

首先要设置环境变量 export DISTCC_HOSTS="@beddp,lzo,cpp"
@beddp 的意思是,通过 ssh 连接到名为 beddp 的主机。,lzo,cpp 这两个设置是为了开启 pump模式。详情可以阅读 Arch Wiki

测试代码选择

#include <stdio.h>
int main(){
    puts(__VERSION__); return 0;
}

在本地运行 gcc k.c -o local.out && ./local.out 的结果是 8.1.1 20180712 (Red Hat 8.1.1-5)
在服务器运行 gcc k.c -o server.out && ./server.out 的结果是 4.8.4

gcc 版本的差异可能会导致各类潜在的问题。但现阶段,可以以此测试 distcc 是否正常工作

在本机运行 DISTCC_VERBOSE=1 pump distcc gcc -c k.c -o k.o && gcc k.o -o server.out && ./server.out 结果是 4.8.4。简单来说,添加了 pump 指令,意味着测试文件和涉及到的头文件会被发送到了工作站上,进行预处理以及编译,并在本地完成了最终的链接。我们也可以运行 distcc gcc -c k.c -o k.o && gcc k.o -o server_nopump.out && ./server_nopump.out 结果就变为了 8.1.1 20180712 (Red Hat 8.1.1-5)。 可以看到,没有了 pump 指令,预处理工作是在本地处理的

在本机也可以运行 distccmon-text 2。这会启动一个两秒钟刷新一次的监视器,显示任务的分配状态。

项目实战

让我们开一瓶香槟,选一个项目实战一下。按照教程,我们只需要把运行 make -j8 CC=distcc即可。不过,很遗憾,我在 wine 项目上的测试失败了。即便 Wine Wiki 显示 gcc 4.8.4 应当可以成功编译 wine,distcc 也没有顺利地接过工作。相反,它不停地显示 (dcc_build_somewhere) Warning: failed to distribute, running locally instead
我在工作站上编译安装了 gcc 8。distccd命令支持指定 PATH,但我选择了笨办法:在本机和工作站上,都设置了一个软链接 /usr/local/bin/gcc-8。在编译前,设置 export CC="ccache distcc gcc-8"。在 ccache 缓存失败时,distcc 会将任务转交给工作站进行处理。我并没有统计具体的编译耗时,但个人体验是有断崖式提升的:在配置前,如果代码变化量大,编译代码时我的 XPS 机身会变得滚烫,同时风扇狂转。而配置好 distcc 后,即便在 ccache 缓存清空的情况下编译,自己的笔记本依旧凉爽安静。

最后附上我用 distcc 编译 wine 的 workflow,比较复杂,个别地方的写法也有待商榷。欢迎大家在评论区,或是向我发送邮件进行讨论。

function cfgwine64()
{
    cd ~/src/wine_n_extras/wine64-build && ../wine/configure --enable-win64
}
function cfgwine32()
{
    cd ~/src/wine_n_extras/wine32-build &&\
    PKG_CONFIG_PATH=/usr/lib/pkgconfig \
    ../wine/configure --with-wine64=../wine64-build
}
function mkwine()
{
    export DISTCC_HOSTS="@beddp,lzo,cpp"
    export CC="ccache distcc gcc-8"
    export CFLAGS="-O0"
    export JOBS=16
    export DISTCC_HOSTS="@beddp,lzo"
    cdwine
    cfgwine64
    make -j$JOBS
    cfgwine32
    make -j$JOBS
}