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
}

Feb 12, 2018 - 在 C++ 中使用 GLPK 求解线性规划

最近,参加了一个提交答案类的编程比赛,有一道题可用线性规划解决。搜索发现,GLPK (GNU Linear Programming Kit) 是一个免费的线性规划计算库,可以方便地被 C/C++ 代码调用。现将基本使用方法整理如下:

准备工作

安装 GLPK

多数的发行版都应该提供了 GLPK 的包。在 Fedora 下,只需运行
sudo dnf install glpk glpk-devel

编译 GLPK

Fedora 将 glpk.h 存在了 /usr/include/glpk.h,因此,不需添加指令即可找到头文件。如果你是手动编译安装的 GLPK,那可能需要使用 -I 指定头文件目录。链接的指令为 -lglpk。如果使用的是 C++ 的话,在调用头文件时,记得声明 extern。你可以试着使用 g++ -lglpk test.cpp 编译如下代码

#include <iostream>
extern "C"{
#include "glpk.h"
}
int main()
{
    std::cout << glp_version() << std::endl;
    return 0;
}

在我撰写本文时(2018年2月初),GLPK 的版本应当为 4.61。

实战演练

GLPK 官方手册上的例子有点让人混淆。在这里,我将采用更精简的例子。
Maximize \[z=10x_1+6x_2\] Subject to \[x_1+x_2\leqslant200\] \[x_1+2x_2\geqslant10\] \[3x_1+x_2\leqslant275.5\] where all variables are non-negative \[x_1\geqslant 0, x_2\geqslant 0\]

对于三个约束条件,我们可以创建三个辅助变量(auxiliary variables),将问题转化为如下形式:
Maximize \[z=10x_1+6x_2\] Subject to \[p=x_1+x_2\] \[q=x_1+2x_2\] \[r=3x_1+x_2\] where all variables are non-negative \[x_1\geqslant 0, x_2\geqslant 0\] \[0\leqslant p\leqslant200,q\geqslant10,0\leqslant r\leqslant275.5\]

现在,可以将我们的问题输入程序了。GLPK 将各辅助变量看作行(row),将原有的变量看作列(column),用一个矩阵表示辅助变量和原有变量的关系。

#include <cstdio>
extern "C"{
#include "glpk.h"
}

int main() {
initialize:
    glp_prob *lp;
    lp = glp_create_prob();
    glp_set_obj_dir(lp, GLP_MAX);
auxiliary_variables_rows:
    glp_add_rows(lp, 3);
    glp_set_row_name(lp, 1, "p");
    glp_set_row_bnds(lp, 1, GLP_DB, 0.0, 200.0);
    glp_set_row_name(lp, 2, "q");
    glp_set_row_bnds(lp, 2, GLP_LO, 10.0, 0.0);
    glp_set_row_name(lp, 3, "r");
    glp_set_row_bnds(lp, 3, GLP_DB, 0.0, 275.5);

variables_columns:
    glp_add_cols(lp, 2);
    glp_set_col_name(lp, 1, "x1");
    glp_set_col_bnds(lp, 1, GLP_LO, 0.0, 0.0);
    glp_set_col_name(lp, 2, "x2");
    glp_set_col_bnds(lp, 2, GLP_LO, 0.0, 0.0);
to_maximize:
    glp_set_obj_coef(lp, 1, 10.0);
    glp_set_obj_coef(lp, 2, 6.0);

constrant_matrix:
    int ia[7], ja[7];
    double ar[7];
    ia[1] = 1, ja[1] = 1, ar[1] = 1;
    ia[2] = 1, ja[2] = 2, ar[2] = 1; // p = x1 + x2
    ia[3] = 2, ja[3] = 1, ar[3] = 1;
    ia[4] = 2, ja[4] = 2, ar[4] = 2; // q = x1 + 2x2
    ia[5] = 3, ja[5] = 1, ar[5] = 3;
    ia[6] = 3, ja[6] = 2, ar[6] = 1; // r = 3x1 + x2
    glp_load_matrix(lp, 6, ia, ja, ar);

calculate:
    glp_simplex(lp, NULL);

output:
    double z, x1, x2;
    z = glp_get_obj_val(lp);
    x1 = glp_get_col_prim(lp, 1);
    x2 = glp_get_col_prim(lp, 2);
    printf("z = %lf, x1 = %lf, x2 = %lf\n", z, x1, x2);

cleanup:
    glp_delete_prob(lp);
    return 0;
}
/*
GLPK Simplex Optimizer, v4.61
3 rows, 2 columns, 6 non-zeros
      0: obj =  -0.000000000e+00 inf =   1.000e+01 (1)
      1: obj =   3.000000000e+01 inf =   0.000e+00 (0)
*     4: obj =   1.351000000e+03 inf =   0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND
z = 1351.000000, x1 = 37.750000, x2 = 162.250000
*/

第一次看到示例代码,对于 constrant_matrix 部分可能会比较费解。在这里,ia 表示行号(第几个辅助变量),ja 表示列号(第几个变量),而 ar 的类型是 double,表示 constrant matrix 中的系数。将这些条件成功导入后,使用 glp_simplex 就可以求解了。

一个常见的需求是,需要求出对应的整数解。使用 glpk,这一问题也很好解决。

set_variables_to_integer:
    glp_set_col_kind(lp, 1, GLP_IV);
    glp_set_col_kind(lp, 2, GLP_IV);
calculate:
    glp_simplex(lp, NULL);
    glp_intopt(lp, NULL);
output:
    double z, x1, x2;
    z = glp_mip_obj_val(lp);
    x1 = glp_mip_col_val(lp, 1);
    x2 = glp_mip_col_val(lp, 2);
    printf("z = %lf, x1 = %lf, x2 = %lf\n", z, x1, x2);
/*
GLPK Simplex Optimizer, v4.61
3 rows, 2 columns, 6 non-zeros
      0: obj =  -0.000000000e+00 inf =   1.000e+01 (1)
      1: obj =   3.000000000e+01 inf =   0.000e+00 (0)
*     4: obj =   1.351000000e+03 inf =   0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND
GLPK Integer Optimizer, v4.61
3 rows, 2 columns, 6 non-zeros
2 integer variables, none of which are binary
Integer optimization begins...
+     4: mip =     not found yet <=              +inf        (1; 0)
Solution found by heuristic: 1346
+     6: >>>>>   1.348000000e+03 <=   1.348000000e+03   0.0% (1; 1)
+     6: mip =   1.348000000e+03 <=     tree is empty   0.0% (0; 3)
INTEGER OPTIMAL SOLUTION FOUND
z = 1348.000000, x1 = 37.000000, x2 = 163.000000
*/

在运行过glp_simplex后,再运行glp_intopt即可得到整数解。但要注意的是,提取整数解的命令是 glp_mip_obj_val / glp_mip_col_val

PS 写这篇 blog 时,我第一次使用了 mathjax。只能说,写作体验超乎想象地好。

讲一个逸闻吧。之前我曾把线性规划和高斯消元的时间复杂度弄混了,以至于我成功将大量NP问题转化为了线性规划问题后得到了“多项式”的解。

Sep 20, 2015 - 用牛刀 LaTeX 完成简单的排版任务

假期里,我们被布置了一篇报告作为作业。排版要求如下:

正文为宋体、小四号、1.25倍行距。标题号第一层用一、二……第二层用1、2……第三层用(1)、(2)……。

同时,我们的报告要求写在特定纸张上。换句话说,是要用特定的页眉页脚。如图: Example

在布置作业时,我们也得到了一个Word 模板。刚刚读完 《LaTex 入门》,就想着用 LaTeX 来完成这项工作。

自定义纸张

自定义纸张可以用 wallpaper 宏包 来处理。这个包的功能很简单,刚好符合本例的需求。将原有的模板导出成 pdf,然后使用该宏包加载即可。

\CenterWallPaper{1}{background.pdf}

自定义章节标题格式

新的 CTeX 套件 已经能完善地支持标题格式。本例中,可以使用

\ctexset {
	section = {
		name = {,、},
		number = \chinese{section}
	},
	subsection = {
		name = {,、},
		number = \arabic{subsection},
	},
	subsubsection = {
		name = {(,)、},
		numbering = true,
		number = \arabic{subsubsection}
	}
}

不过,这一功能比较新。如果使用的是较旧的套件,可能就无法正确编译。因此,建议首先升级至 texlive 2015.

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.