Howard Cheung修改

2023-03-12 22:01:49

memory ballast 的概念这里不再赘述，相信在使用 Golang 的读者应该都知道。确实不了解的话可以阅读提出这个概念的文章，里面有详细的描述。这几年，ballast 被大量运用，在大家的认知里，ballast 是降低 GC 频率的一个简单、实用的方法，我也一直没有看到过关于它的负面报道 —— 直到这次之前。

在 golang-nuts 邮件列表中，也有一个关于这个问题的讨论，但对 golang 了解不多，或者英文不太好的读者可能会一头雾水。本文会对这个问题的来龙去脉做一个简单易懂的概述。如果有错误，欢迎指正。

背景

最近遇到，总有一小部分实例，内存（RSS）占用比其他实例大。而且和正常的实例相比，经过反复排查也没有看出它们的环境有明显的差异。

后面发现，这些实例的 ballast 都整个地被分配了物理内存，并且是启动、创建 ballast 时就这样。

原因

OS（熟悉者可跳过）

众所周知，现代操作系统，尤其是类 Unix 系统中，虚拟内存机制被广泛使用。用户进程对内存的申请、访问等都是在虚拟地址空间内进行的，当进程访问内存时，才会通过“缺页异常”中断，调入对应的内存分页。

比如，当 Go runtime 申请了一块大小为 1GB 的连续内存时，会在虚拟地址空间中得到一段长度为 1GB 的地址，但在它被访问之前，OS 并不会调入对应的物理内存分页，此时也不会占用 1GB 的物理内存。这是 ballast 的理论基础。

ballast 通常的实现是，申请一个大切片，并设置它 KeepAlive（防止 Go 帮倒忙把它优化掉），然后保持它存在但永不访问它，这样结果就不会占用物理内存，同时会占着堆内存，使得 GC 的触发频率降低。

而事实上却出现了 ballast 占用物理内存的情况，最容易想到的原因是 Go runtime 在创建 ballast 大切片时访问了它。

Go runtime

在 Go 的内存分配机制中，大于 32KB 的内存属于大内存，是通过 mheap 分配的。Go 语言原本对应章节中有提到一个“清零”操作。如果在分配 ballast 的内存时，发生了这个清零操作，结果似乎就是会发生 ballast 吃内存的情况。Go 语言原本里没有介绍如何判断是否需要清零。

关于清零，在开头提到的邮件列表里，Golang 团队的开发者，也是下文将提到的 go1.19 GC 相关新特性的提出者，Michael Knyszek 进行了一段回复（译文）：

runtime 有一个简单的启发式方法来避免清零操作，但它远非完美。 因此，ballast 本质上总是会有一点风险。 在某些平台上尤其如此，例如 Windows，因为无法避免将内存标记为已提交（Windows 可以自由地对范围内的内存使用按需分页，因此整体系统内存压力可能会增加，但您不能避免将其计为特定进程的已提交）。

判断的具体逻辑（Github 地址）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

// allocNeedsZero checks if the region of address space [base, base+npage*pageSize),
// assumed to be allocated, needs to be zeroed, updating heap arena metadata for
// future allocations.
//
// This must be called each time pages are allocated from the heap, even if the page
// allocator can otherwise prove the memory it's allocating is already zero because
// they're fresh from the operating system. It updates heapArena metadata that is
// critical for future page allocations.
//
// There are no locking constraints on this method.
func (h *mheap) allocNeedsZero(base, npage uintptr) (needZero bool) {
	for npage > 0 {
		ai := arenaIndex(base)
		ha := h.arenas[ai.l1()][ai.l2()]

		zeroedBase := atomic.Loaduintptr(&ha.zeroedBase)
		arenaBase := base % heapArenaBytes
		if arenaBase < zeroedBase {
			// We extended into the non-zeroed part of the
			// arena, so this region needs to be zeroed before use.
			//
			// zeroedBase is monotonically increasing, so if we see this now then
			// we can be sure we need to zero this memory region.
			//
			// We still need to update zeroedBase for this arena, and
			// potentially more arenas.
			needZero = true
		}
		// We may observe arenaBase > zeroedBase if we're racing with one or more
		// allocations which are acquiring memory directly before us in the address
		// space. But, because we know no one else is acquiring *this* memory, it's
		// still safe to not zero.

		// Compute how far into the arena we extend into, capped
		// at heapArenaBytes.
		arenaLimit := arenaBase + npage*pageSize
		if arenaLimit > heapArenaBytes {
			arenaLimit = heapArenaBytes
		}
		// Increase ha.zeroedBase so it's >= arenaLimit.
		// We may be racing with other updates.
		for arenaLimit > zeroedBase {
			if atomic.Casuintptr(&ha.zeroedBase, zeroedBase, arenaLimit) {
				break
			}
			zeroedBase = atomic.Loaduintptr(&ha.zeroedBase)
			// Double check basic conditions of zeroedBase.
			if zeroedBase <= arenaLimit && zeroedBase > arenaBase {
				// The zeroedBase moved into the space we were trying to
				// claim. That's very bad, and indicates someone allocated
				// the same region we did.
				throw("potentially overlapping in-use allocations detected")
			}
		}

		// Move base forward and subtract from npage to move into
		// the next arena, or finish.
		base += arenaLimit - arenaBase
		npage -= (arenaLimit - arenaBase) / pageSize
	}
	return
}

注：原子操作 Casuintptr 的作用是，如果 p1 == p2，则 p1 = p3 并 return 1；否则无操作，return 0。

它会去遍历此次分配内存将涉及到的各个 arena（Go 内存分配中的一类大对象，详见 Go 语言原本），分别检查它们的 zeroedBase（值越大说明无需清零的内存越少），判断是否需要清零，并会增大 zeroedBase 的值。即，它的值可以理解为已被分配过、需要清零的值。需要注意的是，只要有一个 arena 符合 arenaBase < zeroedBase，都是整体地返回 true。

可以看出，arena 里已经被分配过又回收的内存，再次分配给 ballast 时，这次分配就会被判断为需要清零，进而出现开头描述的问题。因为 ballast 通常都是在启动早期创建的，在它之前分配的内存很少，所以这是个概率较小的事件，但确实存在。

建议

对于仍在继续使用 ballast 的读者，为了预防此问题，建议考虑以下方案替代它。

memory target

这是 1.19 的新功能，可以设置一个固定数值的，GC 触发的目标堆大小。有两种方法：

• 环境变量 GOMEMLIMIT。设置为数字，单位 byte；也可以用数字加单位如 1MiB，1GiB。
• debug.SetMemoryTarget(limit int64)，单位也是 byte

这个功能是为了替代 ballast 设计的，当它被设置后，runtime 会通过多种方法，包括调整 GC 触发频率、返还内存给操作系统的频率等，尽量使内存不超过它。它测量内存是否达到限制的指标是 go runtime 管理的所有内存，相当于 memStats 中 Sys - HeapReleased 的值。它的效果理论上类似且优于 ballast。

使用它限制内存时，可以关闭按比例的 GC（GOGC=off），或将其比例调大。

不过，它和 ballast 一样，不是硬限制，不要把它的值设置为环境允许的内存占用极限。

gc tuner

对于旧版本的 golang，还有一个方案是由 uber 提出的的。思路是动态地调整 GC 触发的比例。有两个开源实现：cch123/gogctuner、bytedance/gopkg/util/gctuner。

仍然使用 ballast

如果想继续使用 ballast ，我想以下两点可能有助于降低该问题发生的概率：

• 尽量早创建 ballast
• 在创建 ballast 前关闭 GC

2022-07-21 17:20:00

在 2020 年底，ICPC 济南站获得第一块金牌之后，由于队友们在学业等其他方向上各有安排，加上里下一场比赛的时间稍远（当时还不确定会去打省赛），我们一起训练的时间相对减少。虽然自己也会做一些练习，但效果一般。后面的省赛中，我校选手都拿了金，其中也包括我们队。

而后则是一直拖到2021年7月的沈阳区域赛，这也是我唯一一次飞到现场参加的比赛。沈阳的气候和南方不同，尽管七月的沈阳不至于寒冷，但第一次到北方的我还是不太适应。在比赛现场上，我出现了较大的失误，整体上我们队伍的优势也没有发挥出来，最后只拿到了铜牌。

最后一年，先后有秋招、毕设等比较重要的事。我们除了赛前会集合训练一下以外，大部分时候都是自己练习。我们先后参加了 CCPC 哈尔滨站和 ICPC 济南站，都取得了银牌。2022 年初，一名队友因为保研夏令营退出队伍，我们直到三月初才最终确定了新队员，是一名大一的学弟，高中时是 OI 选手，实力很强。四月我们便参加了今年的第二场 ICPC 区域赛——昆明站，由于我们俩在搞毕设，学弟课程也很多，一起训练的时间仍然有限。尽管如此，我们最后还是拿到了金牌，这也是我们俩的第二块金牌。

拿了金牌之后，我们也获得了 ICPC EC Final 的参赛名额。西安主办方为了线下比赛，把时间一直拖到了7月19-20日，且在七月初，西安出现了疫情，包括数个高风险区。这个时间段已经毕业在家，赛后不久就是我入职时间。综合考虑可能出现的各种风险、主办方允许部分更换队员的情况（按照往年的要求，除了奖励名额外，其余名额是要在今年区域赛中排名靠前的整支队伍参赛的，但今年似乎放宽了要求，可能和疫情有关），我最后选择了退出比赛，更换为一名学弟。可惜的是，最后他们只拿了铜牌。

现在我已没有机会参加 ICPC 区域赛，是时候和 ICPC 说 Goobye 了。回想这几年，经过了大一大二的高度热情和大量训练，我在大三时终于获得了第一块金牌，而后拿了 ICPC 与 CCPC 的数块银牌和第二块金，在此中间也夹杂着省赛、CCCC 等比赛。这些是我大学期间，最重要的经历与回忆，其中既有成功的喜悦，也有失败的遗憾，但无论如何，都不可能再重来。

在 ICPC 生涯结束后，我很快将会成为一名普通的开发。我会在工作上多多努力，不断提升自己。

2020-12-29 17:26:00

在上次 CCPC 打铜之后，我们打了一次很失败的校赛二等奖。济南报名之后，正式比赛之前，我感觉自己的状态和心态都并不是很好。准备这次比赛时想着拿铜有点小亏，拿银就比较正常了。

在赛场上，签到四题的部分共 WA 一发，还算比较稳，但并不快，排名在银区。

然后自然是跟榜看 A、L，但是都没有想出做法，尤其是 A 涉及的矩阵变换等是我最弱的方向。

后来发现有人过 J 题之后，我也开始看，一开始想在反图（原图不存在的所有边组成新图）里找强连通分量来构造，后面发现似乎并不可行。然后我想起了树上可以相邻点异色染色之类的操作，就发现它可以染两种色，同色点之间无边，这样这题一下子就豁然开朗了。很快地过了 J，排名一下子到了 9。

然后就进入了罚坐模式，期间我甚至想提前放弃🌚。A 题过的队越来越多，我们却迟迟找不到做法。由于我矩阵、代数等方面不太行，帮不上忙，便把所有没过的题都看了，然后也没发现有思路的，心态有点炸。A 题队友找到了把等式变形，矩阵按列拆开之后每列算自由度的做法，继而想到高斯消元和线性基。因为高斯消元算各列，总的复杂度是 $O(n^4)$，即 $1.6 \times 10^9$，感觉过不了，然后线性基连板子都没人看得懂，又开始卡。直到最后没办法才尝试用高斯消元去做，结果直接过了。赛后大佬们都说高斯消元本来复杂度就卡不满🌚，另外这题也可以 bitset 优化，不过没优化也过了。

A 题过了之后金牌应该是稳了，我一下子心态好了非常多，然后我们再一起看 L，想到了枚举后面几位的方法，但是只有不到半小时，来不及过了。不过金牌已经有了，这题过了也离出线差一题，所以也没太大影响。

这场我前中期发挥还可以，但在 A 卡题过程中不仅没帮上什么忙，反而因为自己心态不好，对队友心态也有些影响。很感谢他们并没有一起心态爆炸，并且最终过了这题，让我们第一次打 ICPC 就获得了金牌的好成绩。

A Matrix Equation

题意：已知相同大小的 0-1 方阵 $A$ 和 $B$，定义运算 $\times$ 是普通的矩阵乘，所有元素对 2 取模。定义 $\odot$ 为对应位置元素相乘（也就是相与），求使等式 $A \times C = B \odot C$ 成立的 $C$ 的个数，对 998244353 取模。

很显然，$C$ 的一个元素只会影响它所在的那一列，所以可以以列为单位分开考虑。

好像是只考虑一列之后，就可以得出方程组，然后用高斯消元算自由度。这题队友过的，我先溜了🌚。

C Stone Game

题意：有若干堆石头，每堆有最多三个石头，MianKing 想把它们合并为一堆。他每次可以把任意两堆合并为一堆，如果合并前两堆石头各有 $x$、$y$ 个，则代价为 $(x \mod 3) (y \mod 3)$，求最小总代价。

首先，石堆的个数只有模 3 后的部分有意义。模 3 为 0 的石堆，它与任何石堆合并代价为 0，也不会影响其个数模 3 的值，故可以无视。

然后，1 与 2 都有时，把它们两两合并为 0 是最优解，因为如果不这样做，两个 1 变成 2 代价 1，两个 2 变成 1 代价 4，怎么想都是亏的。因此，优先合并为 0，耗尽 1 和 2 中较少的那种。

对于多出的 1 或 2，显然只能合并，然后得到 2 或 1，然后按照上面的结论，优先合并 0。也就是三个 1 或 2 合并得 0，代价是 3 或 6，直至剩下不到三个为止。

上一步如果刚好够或者剩一个，都没有额外代价。剩两个时则还有一次额外的合并。

D Fight against involution

题意：期末论文有一个奇怪的打分规则：一个人的成绩等于全班总人数减去论文字数比他多的人数，不含相等。每个人能写的字数都有一个区间 $[L, R]$ 作为限制。为了拿高分，卷王们自然都会写最多的字数。但是，如果大家都不那么卷，适当减少字数，或许可以让所有人的成绩都不降低。这题要求找到一个这样的方案，在所有人成绩不降低的前提下，让所有人写的字数总和最小。只输出最小总和的值即可。

这个成绩实际上就是排名，并列往高算。

所有人排名不降，也就是排序不能变。因为并列算高，原本不并列的可以变并列，反之则不能。

显然可以贪心，按原字数排序，原字数最少的尽量减（到 $L$），后面的在不比前面的少的情况下尽量减。并列的只能一起减到它们的 $L$ 中的最大值。

具体做法可以把 $R$ map 到对应的最大 $L$，也可以对 $R$ 并列的按 $L$ 从大到小排，等等。

G Xor Transformation

题意：通过最多五次操作把 $x$ 变成 $y$，每次操作是任选满足 $0 \le a < x$ 的 $a$，令 $x = x \oplus a$。保证 $y < x$。

第一次可以把 $x$ 补满成 $2^k-1$ 的形式，第二次则直接变成 $y$。由于允许 $a = 0$，这种做法无需任何特判。

J Tree Constructer

题意：已知一棵无向树，要求为每个点赋值（$[0,2^{60})$），使有连边的两点所赋值按位或结果等于 $2^{60}-1$，无连边的两点所赋值按位或不等于 $2^{60}-1$。输出一种方案即可。

这题一开始往反图方向考虑去了，后面发现这样做位数应该不够。

按染色思路，相邻边异色，染成两色，设较少的颜色为 0，多的为 1，这样显然可以构造互补关系。

先对每个颜色为 0 的点，分配一位，置 0，其它位置 1。再为了防止同色互连，把一个标记位置 0。

这样颜色为 1 的与它互补，标记位置 1，分配给与它相邻的各点的位置 1，其它置 0。

最多 51 位，加上颜色为 1 的各点共同的零（剩下 9 位都是，需要 1 位），共需 52 位。

M Cook Pancakes!

题意：经典问题，平底锅煎煎饼，两面都要煎，3 个饼能同时煎 2 个，最少 3 次可以煎完。求 $n$ 个饼能同时煎 $k$ 个，最少几次能煎完，$n,k > 0$。

现在我们应该很容易想到，$2n/k$ 向上取整的方案肯定是存在的。

然后，当 $n < k$ 时需要煎 2 次，而上面的式子可能会得到 1 的错误答案。

因此，$\max(2, (2n+k-1)/k)$ 即为答案。

2020-10-20 17:53:00

第一次参加 CCPC，开局不到一小时愉快地签完了 A、G、F，rank 银区偏高，然后就开始了三小时多的自闭调试，队友我分别开了 C 和 E 两题，都在出问题。最后两题调完还剩二十多分钟，K 这种傻逼题都搞不出来，最后耻辱地打铜了（之前敲错成银了🌚）。

由于第一次打比较正式的比赛，之前没有对 codeblocks 等 IDE 进行适应也是一个问题（我日常 Emacs + 大量插件，一个队友日常 VS），感觉时间上面多少吃了些亏。

A A Greeting from Qinhuangdao

签到题，取两个，都是红色，$\frac{C_r^2}{C_{r+b}^2}$ 即可，注意约分，红球少于两个则为 $0$。

C Cameraman

题意：Bob 的房间为矩形，长宽已知；里面有若干私人物品，Bob 自身和私人物品均视为点，位置已知固定。Alex 给 Bob 拍照，位置自选，角度范围自定（可超过 180°）。要求拍到 Bob，不拍到私人物品，求可以拍到的最大墙壁总长度。如下图绿色部分。

这题大清再次背锅，只能靠样例来猜测 Alex 和 Bob 在同一个位置时最优，否则似乎不可做。

然后，利用极角排序，找到一个方向，让直线和它两边的点紧贴，计算出结果。

由于队伍内计算几何比较薄弱，这题虽然不算难但还是在细节上出了不少问题，再加上平台上 C 题的自测是坏的（估计是因为自测没有 spj），导致比赛期间怀疑评测机有问题，浪费了大量时间。

E Exam Results

题意：有若干学生考试，每人有可能获得一高一低两个成绩（可能相等），且无法预测。本次考试的及格线为 $最高分 \times ratio$，求所有情况中，可能的最多及格人数。

对于一个人的成绩 $x$，在最高分不高于 $x/ratio$ 时，他可以及格。当然，最高分不可能低于 $x$，否则他自己的成绩将成为最高分，又因为他可能有两种成绩 $a, b$，所以当最高分位于 $[a,a/ratio]\cup[b,b/ratio]$ 时，他可以及格。

然后，我们把所有人的可能的较低分数取一个最大值，最高分至少等于它，而比它高的每个成绩也都可能作为最高分。然后枚举这个最高分，判断它在多少个人的可及格区间内，找出最大值即为答案。

数区间数量可以用线段树或者树状数组，区间更新+单点查询解决。

由于输入是百分比整数，且所有人成绩是整数，可以成绩乘 $100$（int 溢出警告）再除，向下取整作为右端点。区间范围太大，需要离散化。

本人由于在开始写代码时忘记，“所有人的可能的较低分数取一个最大值，最高分最小时就等于它”的性质，导致耗费大量时间。

F Friendly Group

题意：组内的若干学生参加学术会议。全组的友好值初始为 $0$。组内有若干对朋友，如果一对朋友同时参加，则友好值加 $1$，如果有且仅有其中一人参加，则减 $1$。最后，每个参加的人都会让友好值减 $1$。从中选择任意一部分人（可能一个都不选）参加，求可能的最高友好值。

把学生看作点，关系看作边，则友好值等于 $内部边数-跨内外边数-内部点数$。假如对于一个联通块，我们选了一部分人，那么连通块的其他部分的 $内部点数-内部点数$ 最少为 $-1$，加上它与已选部分之间的边，把整个连通块选进来结果一定不会比只选当前部分差。

因此，可以把整个连通块视为整体，用上面的公式计算，然后根据其值正负决定是否选择，最后对所有正结果取和即可得出最终结果。

G Good Number

题意：不大于 $n$ 的正整数中，有多少个可以被它的 $k$ 次方根（向下取整）整除。

对于每一个数 $i$，$[i^k,(i+1)^k)$ 开根向下取整均为 $i$，所以可以用该区间长度除以 $i$ 即可得到可被 $i$ 整除的个数。由于区间的第一个数就可被整除，所以有余数时向上取整。

由于 $n \leq 10^9$，当 $k \geq 30$ 时，所有数开根都是 $1$。

I Interstellar Hunter

题意：在一个无限制的二维空间内，Alex 一开始在原点，他会不断获得按照一个二维向量进行移动的能力，利用每个能力可以正向或反向移动无限次。询问是否可以到达特定的位置。存在多次询问，获得能力和询问可交替出现，每次询问附带价值，最后输出可到达的询问的价值之和。

对于二维向量 $\boldsymbol a$ 和 $\boldsymbol b$，利用它们能走到的位置，也就是它们的线性组合。进行变换 $\boldsymbol a = \boldsymbol a - \boldsymbol b$，它们的线性组合并不会改变。因此我们可以对它们进行辗转相除。如 $\boldsymbol a = (x_0,y_0), \boldsymbol b = (x_1,y_1)$，对其 $x$ 进行辗转相除，计算（加减乘）时使用整个向量。这样就会得到 $\boldsymbol a = (gcd(x_0,y_0), y_0’), \boldsymbol b = (0,y_1’)$ 。这样我们就可以利用询问的 $x$ 坐标轻易得出 $\boldsymbol a$ 的系数，或是不能整除直接得出不可达，然后再判断 $y$。然后出现新的向量的话，我们先将它与 $\boldsymbol a$ 进行辗转相除，使其 $x$ 为 $0$，再与 $\boldsymbol b$ 对 $y$ 辗转相除，这样它就变成无用的零向量了。

为了使当 $a$ 与新的向量进行辗转相除时在 $y$ 方向上最优，需要在 $y_0’ \geq y_1’$ 时对其相减，也就是取模。另外本题部分写法需要对 $0$ 进行特殊考虑。

K Kingdom’s Power

题意：在一个战略游戏中，地图为树形，国王在根部（点 $1$），有无限的士兵，开始全部在点 $1$。每周可以让一个军队移动到一个相邻点。求他们走一遍所有地区（可重复）至少需要的周数。

首先，对于每个非叶子节点，它都在从根节点到它对应子树的各点的必经之路上。因此只需考虑遍历所有叶子节点。

一个必然可行的方案是，对每个叶子节点，由一支军队从根部走过去。所需时间是所有叶子节点深度之和，以此作为基准值，考虑如何节省时间。

如果对某个有多个子节点的节点 $X$，如果 $X$ 的某个军队在走到了某个叶子节点 $A$ 后回来，再进入 $X$ 下面的另一个子树，则对另一个子树的某一个叶子节点来说，从根（记作 $R$，下同）到 $X$ 的路径 $d_{RX}$ 被替换为了 $d_{AX}$，节省的时间为 $d_{AX} - d_{RX}$。

对于某个节点 $X$，如果它下面的某个子树下有两个叶子节点 $A,B$，有两个军队分别从根部走到 $A,B$ 再回到 $X$，则可节省的时间为 $d_{RX} - d_{AX} + d_{RX} - d_{BX}$。此时，设 $A,B$ 的 LCA 为 $Y$，则改用如下方案：一个士兵走到 $A$ 后回到 $Y$，再进入 $B$，然后回到 $X$，则可节省的时间是 $d_{RY} - d_{AY} + d_{RX} - d_{BX}$。而 $Y$ 在 $X$ 和 $A$ 之间，$d_{AY} < d_{AX}$，$d_{RY} > d_{RX}$，后者节省的时间更多。该情况可类推到更多叶子节点的情况，从而可得到性质：对于每个子树，最多只会有一个军队从它返回到它的根节点的父节点。

然后，对于刚刚的情况，假如都要返回 $X$，则交换 $A,B$ 的位置，总的结果不变。但如果最后不返回 $X$，那么设最后的点为 $B$，设返回 $X$ 的情况下总共节省的时间为 $T$，则不返回的情况就要减去那一部分，则为 $T + d_{BX} - d_{RX}$（$B$ 越深，该值越大），如果它优于 $T$，则不用返回。因此，我们在考虑子树时，把最深的放到最后，在返回父节点的情况下不影响结果，在不返回父节点的情况下结果优于其他顺序。因此，我们应在子树内计算时优先考虑较浅节点，最后把最深节点的深度用于父节点判断是否需要该子树返回。

这样我们可以对整个树进行一次 dfs，dfs 过程中判断军队是否要从当前点下面的各个子树返回到当前点。根据上一段的分析，用各子树的最深节点判断，则在 dfs 过程中获取子节点的高度（叶子为 $1$，记作 height）即可。同时传一个参数表示遍历深度（根为 $0$，记作 dep）。则对于每个子树，如果要返回，节省的时间为 $dep - height$，该值大于 $0$ 则返回，把结果减去该值。

最后，如果某节点下的所有子树都选择返回，则意味着不存在最后进入的叶子节点，这样得到的结果显然是不合理的，需要让某一个不返回。很显然，让减少的时间最少（深度最大）的一个不返回即为最优。

核心部分代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

int dfs(int pos = 1, int dep = 0) {
  if (ch[pos].empty()) {
    ans += dep;
    return 1;
  }
  int height = 0;
  bool flag = 1;
  for (auto p : ch[pos]) {
    auto tmp = dfs(p, dep + 1);
    height = max(height, tmp);
    if (tmp < dep)
      ans -= dep - tmp;
    else
      flag = 0;
  }
  if (flag) ans += dep - height;
  return height + 1;
}

2020-07-28 23:57:27

前言

平铺窗口管理器是否好用这个问题就不说了，不喜欢它的用户可能永远用不惯，但喜欢它的用户则很容易对它形成依赖。在 Linux 的各个桌面环境中，KDE 可以说是最受欢迎的一款，无论是外观、功能还是易用性都很出色，全局菜单等功能也做得很好。

但是，KDE 的窗口管理器没有原生的平铺模式。虽然它提供脚本扩展的能力，也有不少实现平铺的脚本可以使用，但效果远远不如一个原生的平铺窗口管理器。经常会有一些情况没有被脚本控制到的情况，且它们的可定制性也远不如其他的 Tiling WM。

本文将介绍我尝试过一些缝合 KDE 和 Tiling WM 的方案，并在最后给出目前使用的 patched i3。

原版 i3 或 i3-gaps

存在问题

说起平铺窗口管理器，最著名的无疑是 i3，在关于 KDE 搭配平铺窗口管理器这个讨论量并不大的话题中，i3 占了大部分。我也曾经使用 KDE + i3 近一年的时间，但存在大量的问题。

KDE 的大量组件在 i3 上不会自动被设置为 floating，需要自己写规则。而部分组建即使 floating 也不行，比如桌面，只能 kill 掉然后用独立的壁纸设置工具（如 feh）代替，再比如往 panel 添加部件的侧边窗口会全屏（除 panel 区域）显示，并有一定几率崩掉，需要 kill plasmashell 再重新运行，等等。

通知窗口的问题最让人头疼，KDE 的通知窗口会被直接显示在屏幕的正中心。通常推荐的方法是设置规则向右上方移动固定的像素，这样做效果可想而知，不同尺寸的通知窗口移动后间距显然不同，特别长的还会超出屏幕，再加上多个窗口有时会叠在一起的问题。而自己写一个脚本处理这些问题的话，对于多个通知窗口的处理也很麻烦。

如果更换通知 daemon，首先目前没有太多独立的通知 daemon，很多都是要么太简陋，要么和桌面环境耦合。好看一点的界面 + 桌面托盘图标 + 少量的自定义都很难满足。一般 i3 常用的是 dunst，它的通知按钮、历史通知等功能都只能通过快捷键。linux_notification_center 看起来不错，但如果尝试在 KDE 上使用的话，由于 KDE 的通知 daemon 无法关闭，只能让其他的通知 daemon 抢占 dbus。而这个工具我试过很多种方法都不能抢占到（dunst 用 systemd user unit 可以）。

bspwm

优缺点

最近我也考虑其他窗口管理器，由于不想去搞我不熟悉的 lua、haskell 等，尝试了配置简单的 bspwm，发现它有以下几个优点：

• 会自动 floating 部分窗口，且对 KDE 的各种窗口有很好的兼容性，无需额外规则，即可正常显示所有窗口，上面提到的几个兼容问题都没有出现
• 有独立的键绑定工具，而且所有操作通过命令实现，你甚至完全可以用别的快捷键工具代替

不过它还是有一些美中不足的地方：

• 全屏后，其他窗口会出现在该窗口之下，桌面之上，影响透明效果。由于我比较喜欢全局透明的效果，所以这个问题对我影响很大
• 调度器中会显示所有虚拟桌面，即使其中没有窗口，导致 panel 中的虚拟桌面控件过长

另外，bspwm 本身很多地方个人觉得是不如 i3 顺手的。不过，如果你不常使用透明，bspwm 也是一个比较可用的方案。下面是具体的使用方法

如何使用 bspwm

基本配置

更换窗口管理器的方法同 i3，把环境变量中 i3 改为 bspwm 即可

bspwm 本身并不需要太多的配置，唯一必要的一条就是根据你的 KDE panel 设置边距。比如用了 28px 的 top panel，那么就需要加入规则 bspc config top_padding 28。值得注意的是，bspwm 的配置全部是命令，它的配置文件就是一个 bash 脚本，因此你可以动态地添加各种规则，经测试之后再加入 bspwmrc。

快捷键

bspwm 的快捷键程序是一个独立的二进制程序 sxhkd。bspwm 的各种功能调用基于命令，你可以不用 sxhkd，改用 KDE 自带的快捷键工具。不过，把这些快捷键一条一跳加到 KDE 的快捷键中工作量很大（不知道有没有方便的方法），所以还是建议 sxhkd，注意把冲突排除掉，否则 sxhkd 可能不生效。

sxhkdrc 的格式非常简洁，基本上看一眼就会知道怎么写。

混成器

推荐使用 picom，具体介绍看 patched i3 部分。

搭配 bspwm 使用时如果出现设置透明后，部分窗口失去焦点就不透明的情况，可设置 mark-ovredir-focused = false。

patched i3

介绍

这是我目前使用的方案，本部分也是本文的最主要部分。

KDE + i3 的主要问题 i3 是不能很好地 handle KDE 的一些窗口，针对这个问题，存在一些 fork，不过没有进入主线（连 gaps 都进不了主线你还想进？），热度也不高。

目前还处于活跃维护状态的分支是 PJK136/i3，它和它之前的 fork 的 kde-master 分支是基于原版 i3 的，PJK136 自己搞了一个合并了 i3-windows-icons 分支（标题栏显示图标等）的分支。

我喜欢无窗口边框的设计，因此间距肯定是必要的。我尝试了合并它和 i3-gaps，目前使用没有发现大问题，使用效果非常好。后面我会尽量维护更新这个分支（绝对不咕.jpg）。

项目地址 h0cheung/i3-gaps-kde，AUR 已打包：i3-gaps-kde-git。当然你也可以使用 PJK136 的版本，他的 kde-wm-icons-master 分支 repo 中提供了 PKGBUILD。

下面是一个简单的使用方法

如何使用 patched i3

基本配置

首先安装 KDE 和 i3，i3 的 patched 版本上面已介绍。

KDE 提供了一个环境变量 KDEWM 来指定窗口管理器，当然默认是 kwin。我们只需在 KDE 桌面启动前设置它为 i3 即可。最简单的方法（per user），写一个设置环境变量的脚本，比如用 sh 就像这样：

1
2

#!/bin/sh
export KDEWM=/usr/bin/i3

给予执行权限，然后在 KDE 的设置 → 开机与关机 → 自动启动中加入该脚本，并设置为在会话启动之前即可。 从 5.20 版本开始，该功能似乎已经被移除，可以根据使用 pam、dm、xinit 等方法设置该环境变量，详见各发行版或相关工具的文档。当然你也可以写一个 session，这样可以在 dm 里面选择是否用 i3。

经过 patch 的 i3 可以直接用于 KDE，不再需要各种 wiki、论坛上推荐的那堆配置，KDE 的桌面壁纸也可正常使用。对于通知等窗口偷焦点等小问题，简单地加入少量配置即可，比如：

1
2
3
4
5
6
7
8

# disable focus
no_focus [class="plasmashell"]
no_focus [window_role="pop-up"]
no_focus [window_type="notification"]

focus_on_window_activation none
focus_follows_mouse no
mouse_warping none

快捷键

i3 的快捷键是直接由 i3 主程序控制的，建议用 i3 设置快捷键，不在 KDE 中设置。

i3 默认的快捷键基本都是比较好用的，像我就只改了 dmenu 为 krunner，方向键设置为 hjkl，再把冲突的 h 处理了一下。

具体可见我的 dotfiles。

混成器

首先，KDE 自带的混成器是集成在 kwin 中的，不用 kwin 就别考虑了。i3 和 bspwm，以及绝大多数 Xorg 下的窗口管理器也都没有自带混成器。（Wayland 下 WM 必须带混成功能）

Linux 下独立的混成器其实并不多，主流的就一个多次被 fork 改名的，它最新最主流的版本叫 picom，这个混成器主要的优势就是自定义较为强大。

个人的设置主要是关闭 shadow，backend 用 glx，设置了一些透明效果的规则（除了一小部分单独设置，其余窗口都 15% 透明），等等。

当然这部分配置个人喜好不同，可以自行找相关资料（关于 compton 的资料也能参考，大部分兼容）并编写自己的配置。

后记

虽然我做了很多折腾，本文中也提到了多种方法，但是最希望出现的情况还是 kwin 可以支持 Tiling 模式。

另外，StumpWM 等窗口管理器据说也可以较好地配合 KDE，可以考虑尝试。

2020-04-29 16:03:25

简单介绍

其实 fcitx5 已经被偷偷开发了很久了，但是进度比较缓慢。不过，现在的 fcitx5 也已经基本可用。cn 源里的 fcitx5-config-qt-git 包和官方源里的 kcm-fcitx5 都解决了对 KDE 过度依赖的问题（自己编译的话依赖还是很多）。日常使用也没有太大的问题，有兴趣的可以尝试。

安装使用

Arch Linux 用户可以使用 cn 源里的版本（-git 结尾），或官方源里的版本，前者更新打包极其频繁，后者则相对少一些。另外，后者没有 qt4 模块，cn 源和 AUR 也没有可以和它一起使用的 qt4 模块，或许可以自己改 fcitx5-qt4-git 的依赖试试（那干嘛不直接用前者）。

需要安装的包基本上和 fcitx 的类似，我自己安装了的有 fcitx5-chinese-addons-git，fcitx5-git，fcitx5-gtk-git，fcitx5-qt4-git，fcitx5-qt5-git，fcitx5-rime-git，kcm-fcitx5-git。

主要区别就配置工具换成了 kcm-fcitx5（git 版本非 KDE 用户用 fcitx5-config-qt-git）。

其他发行版用户先看源里有没有，没有的话可以尝试找第三方源，或者自己编译/解包后打包并安装。

装上之后用你喜欢的方式设置如下环境变量（由于漏洞的原因，.pam_environment 将不再默认读取，可以根据你的情况考虑 .xprofile、.profile、.zshenv 等）：

1
2
3

GTK_IM_MODULE=fcitx
QT_IM_MODULE=fcitx
XMODIFIERS=@im=fcitx

拼音输入

fcitx5 的自带拼音有一定改进，同时也提供了 rime。rime 仍然不能使用云拼音。至于想使用搜狗输入法的，建议点击右上角的$\times$。

对于两个拼音输入的比较，个人认为新的自带拼音好于 rime 明月拼音简化字的默认配置，并且也提供了不少常用的自定义选项。如果你不怎么在乎隐私，或者对云拼音提供商（目前支持咕果/咕果CN/百毒）很信任的话，使用云拼音会有不错的体验。不过重度折腾下还是 rime 可定制性最好，并且跨平台同步折腾好之后效果也不错。

拼音推荐设置：

• 启用预测
• 启用颜文字
• 云拼音看自己需要
• Show preedit within application（单行显示）
• 快捷键自己设置
• 词典：可适当导入搜狗词库

rime 的话 fcitx5 提供的额外设置就一个单行显示，建议打开。

主题美化

fcitx5 的主题有一定变化，fcitx 的主题不能直接使用，而 fcitx5 的主题很少。

一种选择是使用 kimpanel，不使用的话，推荐 hosxy/Fcitx5-Material-Color，比较简洁，风格类似微软拼音，配色为 Material，建议配合单行模式，建议打开“按屏幕 DPI 使用”，然后把字体调小到合适的程度。

fcitx5-remote

fcitx5-remote 的行为与 fcitx-remote 没有明显区别，使用此功能的工具只需修改调用的命令即可。如果命令是硬编码的，不想改源码可以直接 ln -s。