理解 C++ Traits

C++ 是我学习的第一种编程语言,当时是 2007 年。现在 C++ 标准委员会已经在讨论 2020 年要发布的特性了,我连 2011 年发布的 Traits 都还不知道是啥。今天下定决心了解总结一下。

C++ 之父 Bjarne Stroustrup 说:

Think of a trait as a small object whose main purpose is to carry information used by another object or algorithm to determine “policy” or “implementation details”.

嗯,这段描述也比较抽象。我的理解是,trait 把不同类型的特定信息进行打包,用在算法或者其他对象中。这样算法或者其他对象的设计可以做到更加通用,通过 trait 打包的信息进行策略选择或者实现细节。

trait1

这段代码判断两个类型的关系。第 4 行的模板以两个类型作为参数,通过结构体 type_relation 的成员 relation 获取比较结果。当前代码输出:

1
2
type_relation<bool, int>: different
type_relation<int, int>: different

这段代码并未实现预期功能,因为比较 boolint,以及 intint 时,都输出 "different" 。下面继续完善这个 trait 实现。

trait2

第 11 行的类型参数种使用 <T, T> (即两个相同的类型)进行模式匹配。这段代码输出:

1
2
type_relation<bool, int>: different
type_relation<int, int>: equal

输出结果正确完成了类型比较的功能。


实现

trait 的实现基于 C++ 的模板引擎(template engine),能够在编译时期(compile time)将模板(基于最匹配的模式)展开。如果要在 Golang 或者 Java 种实现类似功能,可以使用反射或者 interface 之类的方法,而这些方法都是在运行时(runtime)进行判定,不可避免带来性能开销。


进阶

除了可以比较两个类型是否相等,还可以在类型参数上添加其他约束,例如:*[] 等。下面是一个稍微复杂一些的版本:

trait3

1
2
3
4
5
type_relation<bool, int>: different
type_relation<int, int>: equal
type_relation<int*, int>: is pointer of
type_relation<int[], int>: is array of
type_relation<int[4], int>: is array (length 4) of

当然这个“进阶”仅仅是比上面的例子复杂了一些,trait 还有更多能力。
C++ 的模板引擎为 C++ 提供了强大的元编程(meta programming)能力,也使得现代的 C++ 代码看上去比较奇怪。
事实上模板引擎是图灵完备的,如果使用好的话,能够将 C++ 的易用性和优雅性提升到一个高度(从那些看不到模板实现细节的用户的视角)。


感想

每次 C++ 标准更新的新闻我都看到了,从 C++0X、C++11、C++14 到 C++17,新出的特性一直在关注,可却从来没有真正编写一段程序去试试这些特性。这让我很伤感。

看到新的语言就想去尝试,OCaml、Clojure、Haskell …… 这些语言都很有特色,OCaml 让我体会到模式匹配的爽快,Clojure 让我体会到 S-表达式的自由和 Lisp 宏的强大,Haskell 让我体会到抽象的威力以及自己脑容量的有限。可是工作中用的最多的还是 Python、Java 和 C,当然还有 PHP (这个不能忘)。

想我和 C++ 的关系,最初的时候还是看的 Bjarne Stroustrup 的《The C++ Programming Language》。后来怎么就越走越远了呢?虽然现在工作中暂时依旧用不到,还是希望以此为契机,了解更多模板引擎可以做的事情。

追逐过的其他语言,各有各的契机,或许是缘分,或许是喜欢,或许是虚荣。现在都不敢说自己会 C++ 了。
如果当时能够更专注一些,自己目前的职业轨迹会不会有所区别?

想起最初自己理解 Haskell 里 Monad 概念的时候,一头雾水。后来懂了,就是懂了。为什么偏爱某一种语言呢?我也搞不清楚自己。

也许爱情也是如此,回忆当初做的不同结果是否能够更好?也许。记住过往,抗拒住回忆的诱惑,很难,但不得不做。喜欢的,就喜欢着吧。有些事情就是不行,正如有些事情莫名其妙地发生。

Just live with it.

2016 十一塞罕坝行动

这是很久之前应该出现的一篇日志,当时忙于处理照片、毕业论文之类的事情,加上强烈的携带情绪,一直没写。


2016 年暑假过后开学不久,政委喊大家出去骑车,这注定会很有趣。目的地是承德的塞罕坝,不是张家口的坝上草原。
主题是骑行、赏秋景。大家确认好时间后,大家定了火车票,提前去西直门北京北站托运了自行车。剩下的就是等待出行了。

塞罕坝国家森林公园位于承德北部,毗邻内蒙古(上面),是清代皇家猎苑一部分,集满蒙汉三民族文化。
景区内有七星湖、太阳湖、泰丰湖、白桦林、月亮湖等较大的景点和多个小景点,自然风光和人文遗迹于一体。
(注:这些湖我们一个也没去,人文遗迹也没看到)
另外,还珠格格就是在这个地方被他皇阿玛一箭射中的。

整体路线规划为:

  • 北京北 - 四合永镇 (火车)
  • 四合永镇 - 围场县 (骑车、住宿)
  • 围场县 - 机械林场 (骑车、住宿)
  • 机械林场 - 半截塔镇 (骑车、住宿)
  • 半截塔镇 - 隆化县 (骑车)
  • 隆化县 - 北京北 (火车)

Day 0

火车上的旅行总是欢快的,小帅哥 YL 拿了很多桌游,大家玩啊玩。
在玩阿瓦隆的时候,某个女博士一脸愁容,明显就是脑细胞不够用的表现。
路上路过了很多听过但是没去过的地方,比如古北口。

到了四合永镇,取车合影。

Gubeikou

到围场县很近,我们很快就骑到了,安顿好了住宿。肚子饿的呱呱叫,出去觅食,集体决定吃火锅(作为吃饭不挑剔的我当然也给不出什么建设性意见)。
一行人吃得热火朝天,风生水起,生龙活虎。最后算账,人均三十。

Hot Pot

然后去附近的超市准备接下来几天的食粮。水果、面包、零食、饮料,各种东西都来点。
逛超市比较有意思的是看到各种东西分门别类堆在一起,那么多,又都很光鲜。虽然不能都买了,但总有种莫名的愉悦感。

Supermarket

晚上还是玩玩玩,时刻压制住情绪,以免吵到其他人。

Day 1

第二天按时起床,旁边小店吃了早饭,准备出发。
说到这个出发,还是有些字面意义上的周折。小城在修路,大家凭着感觉和导航终于骑了出去。

骑车嘛,还是为了拍照。一路上大家各种互拍、自拍,对着天空、河流、群山拍。

骑车嘛,总会爆胎,尤其是漂亮的那种车,比如鲜红的挑战者 300。一路上补过胎的,没经验的,也基本都学会了。

scene1

scene2

scene4

这样的景色大家拍来拍去,怎么也拍不厌。骑在这样的路上,也感觉不累(假的,毕竟在爬大坡)。

接近傍晚,天空的颜色变得多彩,而眼前原野的景色淡下去了。

scene5

scene3

剩下的就是赶路了,还要走一段公路到机械林场。虽然路上的景色也很美,但是看不到,只能通过黑黢黢的树影摇曳想象了。路上发生了一起意外,美女 GY 摔车了。
简单处理了一下,也只能继续骑车。到了机械林场后买了创可贴和碘酒暂时顶一下。

together4

晚上十点多大家吃了羊腿饭,景区物价高,不过仍不及五道口。住宿的话,还停暖和的,三个大男生挤一挤了,另外的妹子们怎么睡都随意了,虽然大家都是在一间屋子里吧。

Day 2

together5

第二天早上在店家吃了早餐,馒头、稀饭、饼、鸡蛋、炒小菜,典型的住店组合套餐(甚至在西藏也是这种组合……)。
出去后,开始下小雪,然后是小雨。大家都披上了雨衣。不过这注定是狼狈的、凄惨的、励志的一天 ……
我不说别人了,就说我自己吧。首先我的鞋子是登山鞋,防水的那种,可以避免水从外面进来,也可以防止水从里面出去。于是我就相当于穿着一个便携泡脚盆在骑车。
总之就是一种说不清道不明的酸楚与傻乐呵在心中交织。

最大的收获是,雨中的山林颜色更加润了。眼前的雨虽然冷,但是远处的雾气很没啊,我们是不畏风雨的骑车人。

scene6

scene7

scene8

遇到一个便利店,大家进去买了各种包裹隔离物品(塑料袋),试图把自己的脚和腿保护起来。
中午在一个小饭馆吃了面,面对有点凶狠的狗去上了厕所。
吃完饭接着骑车,然后大家的车纷纷爆了胎,前面爆完后面爆胎。
忘记提的一点是,我带的补胎片失效了。
而备胎也用光了,于是各种打气筒接力打气艰难前行。
直到政委看到了一个给汽车补胎的地方,我们借用先进装备磨胎,强力胶水补胎,颇有种鸟枪换炮的感觉。

我最为先锋官,到了半截塔镇,发现了一个问题:有人办婚礼,没旅馆可以住了。
大家到了后,决定一拨人先买点东西吃饭,政委向来时方向去找住的地方,我向前面骑,去看看镇子里有没有住的地方。
我本来看到一家说可以的,但是后来店主说很抱歉,他现在在外地,只有自己孩子在家不放心。
幸好政委找到了一家汽车旅馆,住的地方有着落了,安心吃饭喽。

这天路上还遇到了交通事故,别人的。车堵了好几公里,我们骑车经过拥堵路段,骑在没车的路上,好爽啊。

这个汽车旅馆洗漱都要在屋子外面的,水冰凉。
睡之前大家把坏掉的车胎都换了。大家不停吐槽,车胎上面粘的泥里一股马粪味儿。
我和政委一屋,拿出了宝具 - 吹风机,开始吹白天被灌湿的登山鞋。
效果吗?还是超群的。累了,就睡得好了。

Day 3

因为今天要赶车,大家还是早起,吃了一点行动食品就出发了。
到了一个村子里,发现了卖包子的地方,于是纷纷买包子吃。
发现骑车的时候,怎么吃都吃不饱啊。
今天的天气,好极了,阳光灿烂。

scene9

scene10

大家嫌拍照片不过瘾,开始各种拍视频、拍延时,不亦乐乎。

我在前面骑,突然感觉内心迸发出无比力量,蹭蹭蹭。一路冲到了隆化县城火车站。
后来听闻某美女骑车走神,冲到了别人的电动三轮车车斗里面 ……

selfie1

[我一个人吃果粒爽,真是太好吃了 ……]

县城汇合后吃了羊蝎子,味道赞赞赞,食材很给力。让我的冲锋衣回去后携带的羊油气息经久不散 ……

吃完大家就去坐车了。火车上的时候我就开始傲娇了,伙伴们换了座位玩桌游,我却不想去,自己一个人坐在一个车厢里。
现在想想,很多时候情绪就不受自己控制了,当时有什么好的处理方法吗?

Day 4

回学校了。


一起骑车的小伙伴,有的还要继续在学校几年,有的已经要毕业了。想起你们,还是有些伤感的,在杭州有些孤单。

祝你们顺利。

‘How Does Monero Work?' 笔记

Monero 门罗币的一个介绍视频

我刚买到 1070Ti 显卡时曾经想要挖过这个币,后来放弃了,觉得没有意义。不过了解这个技术的一些原理还是有价值的。


Siraj Raval 的免责声明:


Monero 是一种不可追踪的加密货币,网络上很多非法买卖东西的人会使用它。他介绍这个技术的原因是:你应当对你的数据有控制权,而很多数据是交易数据(transactional data)。目前很多公司可以从中免费挖掘信息,用来预测你的购买行为,以便向你展示广告。理想情况下他们应当为你的数据付费,而他们付费的唯一可能是你控制着数据,而唯一控制数据的方式为数据是匿名的。为了查阅你的交易历史,

两个玻璃球(网上流传的面试题)

据说这是 Google 的一个面试题:

有一栋 100 层高的大楼,有两个完全相同的玻璃球。假设从某一层开始丢下玻璃球会摔碎,利用手中的两个玻璃球确定是第几层。最少扔几次玻璃球可以确定这个临界楼层(玻璃球在这一层以及更高的楼层扔下会摔碎)?

就如孔子说过的那句名言 “I Never Said All That Shit” 一样,这个题目出自哪里我也没有去考证。下面把我的思路整理一下。

如果只有一个玻璃球,能做的就是从 1 层开始尝试扔下玻璃球,然后尝试 2 层、3 层 ……,直到某一层扔下玻璃球后摔碎。而现在有两个玻璃球,我们可以用一个玻璃球从 1 层、11 层、21 层 …… 扔下去,确定一个较小的破碎范围,然后使用第二个玻璃球确定具体的楼层。

假如总共 N 层,我们从第 X 层扔下第一个玻璃球,有两种可能性:玻璃球摔碎或者没碎。如果玻璃球摔碎,说明临界楼层在 1~X 中;如果没摔碎,则临界楼层在 X+1~N 中。

如果临界楼层在 1~N 中是均匀分布的,那么 $N > 2$ 时确定临界楼层需要扔玻璃球的最少次数可以由以下公式表示:

$$
f(N)= \min_{X \in [1, N]} {1 + f(N-X)\frac{N-X}{N} + g(X)\frac{X}{N}}
$$

$f(N)$ 为使用两个玻璃球确定区间长度为 N 时的临界楼层所用次数,$g(X)$ 为使用一个玻璃球确定区间长度为 N 时的临界楼层所用次数。这个公式的三部分分别对应:

  • 一次扔玻璃球的尝试
  • 玻璃球未摔碎概率$\times$此时继续尝试需要的次数 $f(N-X)$(两个玻璃球)
  • 玻璃球摔碎概率$\times$此时继续尝试需要的次数 $g(X)$(一个玻璃球)。

显然有 $f(1)=0$,$g(N)=N-1$。可以用动态规划求解 $N=100$ 时需要的最少次数。

Golang 系统调用/Syscall

概述

很多和系统相关的函数都需要调用系统 API,例如读写文件的函数。Golang 对一些系统调用接口进行了封装,提供了 Golang 函数让用户调用,例如:

1
2
func Read(fd int, p []byte) (n int, err error)
func Write(fd int, p []byte) (n int, err error)

同时,Golang 也提供了对 Syscall 的直接调用支持:

1
2
3
4
5
func Syscall(trap, a1, a2, a3 uintptr) (r1, r2 uintptr, err Errno)
func Syscall6(trap, a1, a2, a3, a4, a5, a6 uintptr) (r1, r2 uintptr, err Errno)

func RawSyscall(trap, a1, a2, a3 uintptr) (r1, r2 uintptr, err Errno)
func RawSyscall6(trap, a1, a2, a3, a4, a5, a6 uintptr) (r1, r2 uintptr, err Errno)

RawSyscallRawSyscall6 是对操作系统 Syscall 的直接调用;SyscallSyscall6 会在调用操作系统 Syscall 前调用 runtime·entersyscall ,在操作系统 Syscall 返回后调用 runtime·exitsyscall

这四个函数都是使用汇编语言实现,代码和具体的硬件体系结构和操作系统有关。RawSyscallRawSyscall6 的行为和 C 语言中系统调用很类似,在这里不展开描述。而 SyscallSyscall6 的行为(在进行真正的系统调用前后插入额外操作)与 Golang 的调度器关系紧密,在下面会进行要点描述。

Syscall 的关键在于 runtime·entersyscallruntime·exitsyscall ,而 runtime·entersyscall 还有一个行为有部分差异的版本 runtime·entersyscallblock

runtime·entersyscall

1
2
3
func entersyscall(dummy int32) {
reentersyscall(getcallerpc(), getcallersp(unsafe.Pointer(&dummy)))
}
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
func reentersyscall(pc, sp uintptr) {
_g_ := getg()

// Disable preemption because during this function g is in Gsyscall status,
// but can have inconsistent g->sched, do not let GC observe it.
_g_.m.locks++

// Entersyscall must not call any function that might split/grow the stack.
// (See details in comment above.)
// Catch calls that might, by replacing the stack guard with something that
// will trip any stack check and leaving a flag to tell newstack to die.
_g_.stackguard0 = stackPreempt
_g_.throwsplit = true

// Leave SP around for GC and traceback.
save(pc, sp)
_g_.syscallsp = sp
_g_.syscallpc = pc
casgstatus(_g_, _Grunning, _Gsyscall)
if _g_.syscallsp < _g_.stack.lo || _g_.stack.hi < _g_.syscallsp {
systemstack(func() {
print("entersyscall inconsistent ", hex(_g_.syscallsp), " [", hex(_g_.stack.lo), ",", hex(_g_.stack.hi), "]\n")
throw("entersyscall")
})
}

if trace.enabled {
systemstack(traceGoSysCall)
// systemstack itself clobbers g.sched.{pc,sp} and we might
// need them later when the G is genuinely blocked in a
// syscall
save(pc, sp)
}

if atomic.Load(&sched.sysmonwait) != 0 {
systemstack(entersyscall_sysmon)
save(pc, sp)
}

if _g_.m.p.ptr().runSafePointFn != 0 {
// runSafePointFn may stack split if run on this stack
systemstack(runSafePointFn)
save(pc, sp)
}

_g_.m.syscalltick = _g_.m.p.ptr().syscalltick
_g_.sysblocktraced = true
_g_.m.mcache = nil
_g_.m.p.ptr().m = 0
atomic.Store(&_g_.m.p.ptr().status, _Psyscall)
if sched.gcwaiting != 0 {
systemstack(entersyscall_gcwait)
save(pc, sp)
}

// Goroutines must not split stacks in Gsyscall status (it would corrupt g->sched).
// We set _StackGuard to StackPreempt so that first split stack check calls morestack.
// Morestack detects this case and throws.
_g_.stackguard0 = stackPreempt
_g_.m.locks--
}

runtime·entersyscall 主要完成以下几件事:

  1. 声明函数为 NOSPLIT ,不触发栈扩展检查
  2. 禁止抢占
  3. 通过 dummy 参数获得调用者的 SPPC 的值,并保存到 goroutine 的 syscallspsyscallpc 字段。同时记录 syscallstacksyscallguard ,使得垃圾回收器只对系统调用前的栈进行 mark-sweep (cgo 机制也利用了 entersyscall 来使得 cgo 中运行的代码不受垃圾回收机制管理)。
  4. 将 goroutine 的状态切换到 Gsyscall 状态。
  5. 唤醒后台线程 sysmon (这个线程会监控执行 syscall 的线程,如果超过某个时间阈值,就会将 M 与对应的 P 解除绑定)。
  6. 置空 M 的 mcache 、将 P 的 m 字段,切换 P 的状态到 Psyscall
  7. 检查是否需要垃圾回收
  8. 通过 g->stackguard0 = StackPreempt 使得出现 split stack 时可以通过 morestack 捕获并抛出错误
  9. 恢复抢占

可以看到 reentersyscall 多次调用 save 保存 pcspsave 更新 getg().sched 中的 sppc ,使得调用 gogo 的时候可以恢复 pcspreentersyscallsave 的目的都是为 goroutine 跳回这个 syscall 调用者执行 syscall 时刻的 pcsp做准备。

需要继续深入:

  1. StackPreempt
  2. syscallstacksyscallguard 的具体作用时机

runtime·entersyscallblock

runtime·entersyscall 区别在于这个函数认为当前执行的 syscall 会运行较长时间,因此在函数中主动进行了 M 和 P 的解除绑定,无需等待 sysmon 处理。解除 M 和 P 绑定的逻辑由 entersyscallblock_handoff 实现。

1
2
3
4
5
6
7
func entersyscallblock_handoff() {
if trace.enabled {
traceGoSysCall()
traceGoSysBlock(getg().m.p.ptr())
}
handoffp(releasep())
}

runtime·exitsyscall

主要实现了从 syscall 状态中恢复的动作:

  1. 尝试调用 exitsyscallfast ,如果 M 与 P 没有完全解除绑定,那么该操作会将 M 和 P 重新绑定;否则获取一个空闲的 P 与当前 M 绑定。如果绑定成功,返回 True,否则返回 False 进行后续步骤处理。
  2. 如果 exitsyscallfast 返回 True ,函数就直接返回;返回 False,则进入 slow path 将当前 goroutine 放到任务队列中等待调度,具体实现由 mcall(exitsyscall0) 实现。

exitsyscall0 这个函数比较清晰,只是对其中 dropg() 的目的还没想清楚。

runtime·exitsyscall 的函数说明中提到的 // Write barriers are not allowed because our P may have been stolen. 也没有搞清楚,知道和 GC 有一定关系。

引用

  1. https://studygolang.com/articles/7005

Golang 中学到的新东西

数据类型

string 类型

string 类型使用 2 个 word(64 bit 系统为 8 byte * 2)表示:一个 word 是指针,指向字符串存储区域;一个 word 表示长度数据。

slice $\leftrightarrow$ unsafe.Pointer

1
2
s := make([]byte, 200)
ptr := unsafe.Pointer(&s[0])
1
2
var ptr unsafe.Pointer
s := ((*[1<<10]byte)(ptr))[:200]

or

1
2
3
4
5
6
7
8
var ptr unsafe.Pointer
var s1 = struct {
addr uintptr
len int
cap int
}{ptr, length, length}

s := *(*[]byte)(unsafe.Pointer(&s1))

or

1
2
3
4
5
var o []byte
sliceHeader := (*reflect.SliceHeader)((unsafe.Pointer(&o)))
sliceHeader.Cap = length
sliceHeader.Len = length
sliceHeader.Data = uintptr(ptr)

map 实现

整个页面的内容对我来说都是新的:https://tiancaiamao.gitbooks.io/go-internals/content/zh/02.3.html
不过这个页面描述的内容和最新的 Golang source 有一定差别。

HashMap 的实现,里面的一些核心关键词:bucketoverflow 让我理解起来有些困难。查询 HashMap 相关的一些资料后有了进一步了解。

  1. bucket 一般使用某种 array 管理,从 key 经过 hash-function 映射的 hash-value(可能截取一部分,也可以视作 sub-hash,我自己编的)作为 index 直接得到。一个 bucket 中可能包含多个不同的 hash-value ,它们截取那一部分得到的 index 相同。因此 bucket 会用一个数据结构管理这些冲突的值,可能是 linked-list 或者 tree-map 之类的。这些内部的数据结构中的 node 存储着真正对应 mapkey\value 对(pair)。
  2. 如果 bucket 太满了,比如元素的数量超过 bucket 数量一定倍数(load factor),则会进行扩容,所有元素都被 rehashed 到一个新的值。
  3. 采用这种方式实现 HashMapbucket 可以有两种选择:
    • Direct chaining 只存一个指向冲突元素集合的 header
    • Seperate Chainingbucket 存一部分(一个)元素集合(Golang HashMap 实现里放了 8 个),和一个指向剩下冲突元素集合的 header
  4. 上面 header 指向的元素集合叫 overflow list 或者 overflow some-other-data-structure

有了这些背景后,看代码应该会比较清晰了。

目前 Golang 中的 bucket 是为 insert 操作优化的,找到第一个空余位置就可以插入,但是删除的时候要把所有相同 key 的元素都删掉,要遍历 bucketoverflow 集合。

如果 key 或者 value 小于 128 字节,那么它们是直接在 bucket 存储值,否则存指向数据的指针。

nil 语义

按照 Golang 规范,任何类型在未初始化时都对应一个零值:

  • bool $\rightarrow$ true
  • integer $\rightarrow$ 0
  • string $\rightarrow$ ""
  • pointer/function/interface/slice/channel/map $\rightarrow$ nil

关于 interface{}

1
2
3
var v *T           // v == nil
var i interface{} // i == nil
i = v // i != nil

关于 channel

一些操作规则:

  • 读写一个 nilchannel 会立即阻塞
  • 读一个关闭的 channel 会立刻返回一个 channel 元素类型的零值,即 chan int 会返回 0
  • 写一个关闭的 channel 会导致 panic

函数调用

汇编

可以看一下这个 Golang 的官方介绍页面:https://golang.org/doc/asm

add.go

1
2
3
package add

func Add(a, b uint64) uint64

add_amd64.s 或使用其他平台后缀,和 add.go 在同一个目录

1
2
3
4
5
6
TEXT    ·Add+0(SB),$0-24
MOVQ a+0(FP),BX
MOVQ b+8(FP),BP
ADDQ BP,BX
MOVQ BX,res+16(FP)
RET ,

Golang 调用 C

add.c ,和 add.go 在同一个目录

1
2
3
4
void ·Add(uint64 a, uint64 b, uint64 ret) {
ret = a + b;
FLUSH(&ret);
}

编译这个包:go install add

C 文件中需要包含 runtime.h 头文件。因为 Golang 使用特殊寄存器存放像全局 struct Gstruct M ,包含这个文件可以让所有链接到 Go 的 C 文件感知这一点,避免编译器使用这些特定的寄存器做其他用途。

上面示例中返回值为空,使用 ret 作为返回值,FLUSHpkg/runtime/runtime.h 中定义为 USED() ,防止编译器优化掉对某个变量的赋值操作(因为看不到这个变量在后面其他地方使用了)。

函数调用时的内存布局

Golang 中使用的 C 编译器是 plan9 的 C 编译器,与 gcc 有一定差异。
这个页面中有部分基础介绍:
https://tiancaiamao.gitbooks.io/go-internals/content/zh/03.1.html

如果返回多个值,func f(a, b int) (d, e int) 内存布局如下所示:

1
2
3
4
5
slot for e
slot for d
b
a
<- SP

调用后为

1
2
3
4
5
6
slot for e
slot for d
b
a <- FP
PC <- SP
f's stack

plan9 的 C 汇编器对被调用函数的参数值的修改是会返回到调用函数中的。

1
2
3
MOVQ    BX,d+16(FP)
...
MOVQ BX,e+24(FP)

go 关键字

f(1, 2, 3) 的汇编:

1
2
3
4
MOVL    $1, 0(SP)
MOVL $2, 4(SP)
MOVL $3, 8(SP)
CALL f(SB)

go f(1, 2, 3) 的汇编:

1
2
3
4
5
6
7
8
MOVL    $1, 0(SP)
MOVL $2, 4(SP)
MOVL $3, 8(SP)
PUSHQ $f(SB)
PUSHQ $12
CALL runtime.newproc(SB)
POPQ AX
POPQ AX

12 是参数占用的大小,runtime.newproc 函数接受的参数为:参数大小、新的 goroutine 要运行的函数、函数的参数。runtime.newproc 会新建一个栈空间,将栈参数的 12 个字节复制到新的栈空间,并让栈指针指向参数。可以看做 runtime.newproc(size, f, args)

defer 关键字

return x 不是原子语句,函数执行顺序为:

  1. 给返回值赋值
  2. defer 调用
  3. return

defer 实现对应 runtime.deferproc,其出现的地方插入指令 call runtime.deferproc ,函数返回之前的地方,插入 call runtime.deferreturn 。 goroutine 的控制结构中有一张表记录 defer,表以栈行为运作。

Continuous Stack

我也基本理解了思路,具体细节可以看:https://tiancaiamao.gitbooks.io/go-internals/content/zh/03.5.html

最后的 runtime.lessstack 有些没看懂。

闭包

闭包中引用的变量不能在栈上分配,否则闭包函数返回的时候,栈上变量的地址就失效了。

逃逸分析(escape analyze)

Golang 有个特性,可以自动识别哪些变量在栈上分配,哪些在堆上分配。

1
2
3
4
5
6
func f() *Cursor {
var c Cursor
c.X = 500
noinline()
return &c
}
1
2
3
4
5
6
7
8
9
MOVQ      $type."".Cursor+0(SB),(SP)    // 取变量c的类型,也就是Cursor
PCDATA $0,$16
PCDATA $1,$0
CALL ,runtime.new(SB) // 调用new函数,相当于new(Cursor)
PCDATA $0,$-1
MOVQ 8(SP),AX // 取c.X的地址放到AX寄存器
MOVQ $500,(AX) // 将AX存放的内存地址的值赋为500
MOVQ AX,"".~r0+24(FP)
ADDQ $16,SP

在编译的过程中可以通过指令输出哪些变量逃逸了:go build --gcflags=-m main.go

闭包结构体

闭包将函数和它引用的环境表示为一个结构体:

1
2
3
4
type Closure struct {
F func()()
i *int
}

整体思路是返回闭包的时候,返回一个结构体,包含闭包返回函数的地址和引用的环境中的变量地址。

1
2
3
4
5
6
func f(i int) func() int {
return func() int {
i++
return i
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
MOVQ    $type.int+0(SB),(SP)
PCDATA $0,$16
PCDATA $1,$0
CALL ,runtime.new(SB) // 是不是很熟悉,这一段就是i = new(int)
...
MOVQ $type.struct { F uintptr; A0 *int }+0(SB),(SP) // 这个结构体就是闭包的类型
...
CALL ,runtime.new(SB) // 接下来相当于 new(Closure)
PCDATA $0,$-1
MOVQ 8(SP),AX
NOP ,
MOVQ $"".func·001+0(SB),BP
MOVQ BP,(AX) // 函数地址赋值给Closure的F部分
NOP ,
MOVQ "".&i+16(SP),BP // 将堆中new的变量i的地址赋值给Closure的值部分
MOVQ BP,8(AX)
MOVQ AX,"".~r1+40(FP)
ADDQ $24,SP
RET ,

引用

  1. https://tiancaiamao.gitbooks.io/go-internals
  2. http://gki.informatik.uni-freiburg.de/teaching/ss11/theoryI/07_Hashing_Chaining.pdf

使用 Nvidia 显卡加速机器学习算法的一些资料

Nnidia 显卡可以用来加速机器学习算法(特别是深度学习),但安装驱动过程中总会碰到这样或者那样的问题。
一个难点是安装库的时候没有下载链接,比如 Nvidia 的 Cuda/cuDNN 主页经常会出现这样的提示:

1
2
3
NVIDIA Developer Site is under going maintenance.
The site will be back by shortly.
We apologize for any inconvenience.

虽然不能按照官方路径进行下载,但经过搜索总能找到一些入口。下面是我收集的一些链接:

一些有趣的项目 Protocol Labs

最初在 3Blue1Brown 发布的一个介绍区块链原理的视频中看到了这个组织的连接。发现比较有意思,给大家分享一下~

项目的使命:

We believe the internet has become humanity’s most important technology. We build protocols, systems, and tools to improve how it works. Today, we are focused on how we store, locate, and move information.

我们相信互联网已成为人类最重要的技术。我们构建提升互联网工作能力的协议、系统和工具。当前我们集中在如何存储、定位和移动信息的工作上。

这段文字翻译得有点机器翻译风格。

项目地址:https://protocol.ai/projects/ ,目前上面有 5 个项目:

  1. Filecoin
    • 加密货币,Miners 通过向网络提供存储空间来获取 Filecoin ,使用者通过消耗 Filecoin 来在去中心化的网络中存储加密后的文件。
  2. IPFS (InterPlanetary File System)
    • 一种新型协议,用来使网络去中心化。IPFS 通过内容寻址和数字签名来创建完全去中心化和分布式的应用。IPFS 使得网络更快、更安全以及更加开放。
    • 这是一段 YouTube 上的介绍视频:https://www.youtube.com/watch?v=8CMxDNuuAiQ ,介绍了 IPFS 的一些基本使用方法。根据我的理解,这是通过 content-address(immutable hash) 访问的分布式加密文件系统,可以通过命令行、网页界面等多种方式进行访问,有点类似 Samba,不过是分布式的。Siraj Raval 制作的一个视频:https://www.youtube.com/watch?v=BA2rHlbB5i0 ,也对 IPFS 进行了介绍,主要对 Why 的部分进行阐述。
      • 带宽,多个客户端对中心节点访问
      • 延迟
      • 弹性 Resiliency,中心节点失效(网络断开或者数据删除)后无法进行数据访问
      • 中心化 Centralization,主流网站掌控所有数据,用户无从得知数据的使用方式,此外会受到政府或者其他势力的干扰。
    • 使用的技术:Chord、DHT、bit swap(bittorrent mechanism)、MerkleDAG
  3. Libp2p
    • 一个模块化的网络栈,把一系列传输协议和 peer-to-peer 协议整合在一起,方便开发者构建大型、健壮的 p2p 网络
  4. IPLD
    • 去中心化网络(content-addressable web)的数据模型,它通过加密哈希值的方式连接了所有数据,使得数据的遍历和彼此链接更加容易。网站的示意图中连接了 bitcoin、以太坊、IPFS、Git Repo 等。
  5. Multiformats
    • 这个项目是面向未来验证系统(future-proof systems)的协议集合, 自描述的格式可以让你的系统可以互操作和具有可升级性。

Bar

1
2
3
4
5
import "blog.formalscience.com/nothing"

func main() {
nothing.bar()
}

I dreamed about death this morning.

I dreamed about false dreams this morning.

I woke up tired.

I made some coffee with milk or without milk.

I saw some videos on Youtube and Bilibili.

I wrote this blog.

我一生的故事

我一生的故事
我终于去看了《降临》。最初知道 特德·姜/Ted Chiang 的《你一生的故事 /Story of Your Life》要被搬上银幕的时候,我内心很激动,因为这是我非常喜欢的一篇科幻小说。不过担忧也是有的,很多科幻小说以电影的形式展现时,感觉上总是有些残缺,或囿于电影技术,或囿于艺术表现形式,或者就是书的读者有不切实际的期望。

再次听说相关消息时,已经是在美国上映的消息了,影片名称是《降临》,相比原书的标题这个名称显得更加科幻一些。然后听说到的就是各种好评,我本来期待着北邮人上什么时候会有下载资源,因为感觉国内没可能上映了。后来知道的就是上映的消息,直到今天观影结束。

我相信关注一些电影公众号的人肯定已经被剧透了,在此我就不再描述剧情了。对于我来说,看过中文版的小说,又看了英文版的小说,然后看了电影。在已经知道了剧情的前提下看电影,和已经知道了未来的人生的前提下继续生活有些相似之处。不过我头脑仍然只能处理从过去向未来流动的线形时间,而不是书中/电影中的 没有方向的文字。

语言真的可以影响人的思考方式吗?

作为《你一生的故事》理论基石的是语言相对性原理(萨丕尔-沃夫假说)。这是一个关于人类语言的假说:

认为不同语言裡所包含的文化概念和分类会影响语言使用者对于现实世界的认知,也就是说不同的语言的使用者会因语言差异而产生思考方式,行为方式的不同。

七肢桶(书中外星人因其外形得到的称呼)的文字是非线形的文字,复杂的文字在简单的文字之上通过改变结构得到,它们在表达一个思想之前就获得了这个思想对应文字的全部形状。同样对于它们来说,复杂的物理学定律,特别是人类目前没有掌握的关于时间空间的部分,比基础的牛顿定律来说更容易理解。光为什么沿着时间最短路径行进?我们可能需要量子理论来计算光行进所有可能路径然后对每一条路径进行积分算出其概率。对于七肢桶来说,光沿着最短路径行进就是其目的。

每个文明的科技进展路线和其环境有很大关系,一个内陆国家是发展出强大航海科技的可能性是很小的。对于七肢桶来说谈论过去和未来是没有意义的,它们只是向着目的前进。(即使这个“目的”在“未来”发生)也许这是看待世界的两种方式,就像在在时域和频域对一个信号进行不同的观察。

女主角在和七肢桶接触以及学习了其文字 —— “七文” 后,逐渐领悟了自己的未来。电影或书中出现未来的地方就容易出现矛盾。特别集中在人知道了未来之后能否改变未来这一问题上。有一种观点认为预知未来和自由意志之间只能二择其一。女主角在学习文字语言的过程中,到底是获取了预知未来的能力,还是放弃了自由意志?

预知未来的人不会奢谈未来,读过岁月之书的人不会承认自己读过它。
—— 《你一生的故事 /Story of Your Life》 特德·姜/Ted Chiang

人们讴歌自由意志,然而又同时梦想可以预知未来。
—— 《我一生的故事》 乱说话的跳跳 / Bef0rewind

女主角在知道自己女儿将来会因为罕见病去世之后,依然(此处用选择或者决定都不合适)生下了她。后来她把自己对未来的预知告诉丈夫后,丈夫对她的行为感到愤怒,他们的婚姻也结束了。

对于电影中出现的一个小高潮,商将军告诉女主角自己的私人号码。有人质疑,女主角既然能够看见未来,为什么需要在未来的商将军告诉她这一信息。也许语言对她的影响是逐步产生的,未来的画面满满展开在了她面前,而在此刻她注定不知道这一信息。未来的商将军也受到了 “七文” 的影响,对女主角说:你应该(should)给我打电话。

书中最后没有提到七肢桶来到地球的目的,电影中给出了一个目的:三千年后七肢桶需要人类的帮助(它们在未来里看不到自己的目的了吗?)。电影中女主角对七肢桶的文字出版了教科书,讲授相关知识,也许会对地球人的思维产生影响吧。我也想过,七文会主导世界吗,地球人也会出现某种进化吧。好多语言会消失啊,对应的文明也消失了吧。

我讲过的两段话:

时间旅行故事中最美妙的因素就是时间。我在过去种下一颗种子,现在收获了一棵大树。

一个能够沿着时间轴前进后退的生命和一个只能单向前进的生命,哪个更有趣?前者已知所有,后者并不知道未来。如果前者眼中时间是一条线段(端点可能在无穷处),线段两端是其诞生和终结,可能还是对前面是否有尽头的未知有意思一点。

在英剧《奇异博士》五十周年特别篇 The Day Of The Doctor 中,三代博士使用的是同一个计算终端。当最老的博士在他的终端启动了计算,到了第三代博士手中的终端就处于计算了几百年之后的状态,得到了计算结果。

时间,只有时间。


我如果在书中,会是一个什么角色呢?我会有什么样的行为?作为一个希望与外星智慧生命接触的人,如果真有外星飞船降临,我得不到与它们见面的机会,毕竟我不是有特殊技能的人士。除非我是男主角,那外星生命可能出于某种目的同我接触。

有一点特别感动,父母会走到生命的尽头,孩子也会。我想到自己未来的孩子,我与你的故事,我会成为一个怎样的父亲,也许很久之前我就知道了呀。


一些相关的科幻小说

《与拉玛相会/Rendezvous with Rama》 阿瑟·克拉克/Arthur C. Clarke

一艘外星飞船从地球附近飞过,人类登陆上去后除了发现了高级自动机器人外,对于是否有智慧生命控制飞船以及其目的仍旧一无所知。最后随着飞船离地球远去,留给人类的只是一个谜。人是多么渴望自己有邻居,然而这个邻居确毫无回应地走了。

《海伯利安/Hyperion》丹·西蒙斯/Dan Simmons

这是一个背景宏大的故事,我们未来是否能够与人类的创造物(AI)和平共处?爆发战争的话,双方都要穿越时空传送回战力进行决斗。如果有更高级的生命,人类被其接纳的条件是什么?需要超越肉体形态,或者和 AI 进行合体产生新的生命吗?是否要保持人类的纯粹,还是对自身进行改造,适应地球之外的环境,在未来更广阔的世界中进化?

《永恒的终结/The End of Eternity》艾萨克·阿西莫夫 /Isaac Asimov

当人类获得了延时空旅行的能力,对历史(时空井建成之后)中的“错误”进行修正。未来的某段时间区间的人封闭了自己所在的区间,主角所在的永恒时空组织没有能力进入。当主角碰到了封闭时空区间段内的女主角时,对于爱情和永恒的领悟使他做出了最终的修正——毁掉时空井。通过修改过去对历史填补,也可能会把人类逼到死路——使人类生活于安逸的时代,错失向外太空进发的动力与机遇,而宇宙中不只有地球人。

《童年的终结/Childhood’s End》阿瑟·克拉克/Arthur C. Clarke

当更高级的文明降临地球,接管地球的管理,禁止战争,提升科技,人类对于国家的认识和生活方式也发生了改变。同时发生改变的还有地球上的孩子,他们不和父母交流,不接受地球的文明,并且拥有了控制物质的能力。当向往外星文明的扬回到地球后,发现十岁之下的还在都已经是这种状态了。原来高级文明是接受了更高级文明的委托,监督引导人类的进化过程。最后所有孩子分解了地球,一起融入了更高级的文明。人类文明是别人的猎物吗?还是获得了进化?无论怎样,这都是人类文明的终结。而监督地球的高级文明没有融入更高级文明的可能性,他们被困住了。这是一种幸运还是悲哀呢?他们不会有理解

《时间回旋/Spin》罗伯特· 查尔斯·威尔森/Robert Charles Wilson

这是一部在技术和人文上都独具匠心的作品。末世的希望,末世的绝望。超级生命帮助人类制造了时间膜,地球一年,外面一亿年。太阳四十二亿年后是会毁灭的,人类的希望是利用进化的力量向火星运送生命,期待时间带来的科技进步能够拯救人类自身。而火星的同胞最终发展的生物科技到底给人类带来了什么?当太空中百万年才产生下一代的机械生命和人类哪个更 “高级”(生存下来才是王道)?机械生命之间的吞并战争更加残酷。更高级的文明拯救低级文明的目的是什么?融入更广阔的智慧是一种选择,哪怕失去了 “我” 的意识。时间,只要有了时间,一切都有可能。

《宇宙尽头的餐馆/The Restaurant at the End of the Universe》道格拉斯·亚当斯 /Douglas Adams

如果你想在欢乐中感受科幻的魅力,这部充满英式幽默的小说绝对不能错过。在时间尽头来回游荡,发生的趣事一桩接一桩。此外如果对宇宙中一切问题的终极答案感兴趣,《银河系搭车客指南》不容错过。不过我也可以告诉你答案,是 42 哦。

还有很多小说,我想不起来了。

We write to taste life twice in the moment and in retrospect.
— Anaïs Nin