使用forwarding指针的深度优先GC算法 #

复制 GC 算法，最核心的就是如何实现复制。我们自己就可以很容易地写出一个基于深度优先搜索的算法，它的伪代码如下所示：

void copy_gc() {
    for (obj in roots) {
        *obj = copy(obj);
    }
}
obj * copy(obj) {
    new_obj = to_space.allocate(obj.size);
    copy_data(new_obj, obj, size);
    for (child in obj) {
        *child = copy(child);
    }
    return new_obj;
}

上面的代码中缺少了对重复访问对象的判断。考虑到有两个对象 A 和 B，它们都引用了对象 C，而且它们都是活跃对象，现在我们对这个图进行深度优先遍历。 在遍历过程中，A 先拷到 to space，然后 C 又拷过去，这时候，空间里的引用是这种状态： A 和 C 都拷到新的空间里了，原来的引用关系还是正确的。但我们的算法在拷贝 B 对象的时候，先完成 B 的拷贝，然后你就会发现，此时我们还会把 C 再拷贝一次。这样，在 To 空间里就会有两个 C 对象了，这显然是错的。我们必须要想办法解决这个问题。

通常来说，在一般的深度优先搜索算法中，我们只需要为每个结点增加一个标志位 visited，以表示这个结点是否被访问过。但这只能解决重复访问的问题，还有一件事情我们没有做到：新空间中 B 对象对 C 对象的引用没有修改。这是因为我们在对 B 进行拷贝的时候，并不知道它所引用的对象在新空间中的地址。

Content #

l_k范数 布尔环中的加法逆元(Additive Inverse)

Links #

Content #

包含n个元素的向量 \(\bm{v}\) 的 \(\ell_k\) 范数是如何定义的？范数指标k的大小对范数有何影响？

\begin{displaymath}\|\bm{v}\|_k=\left(|v_0|^k+|v_1|^k+\cdots +|v_n|^k\right)^{1/k}\end{displaymath}

范数指标越高，它越关注大值而忽略小值。

From #

Links #

获取者在对待上级和下级时，有何明显的特点？ #

向上谄媚的时候，获取者通常是优秀的伪装者。1998年，华尔街的分析师造访安然公司，莱雇用了70个人，让他们假扮成忙碌的交易员，希望让分析师相信，公司正在从事高产的能源生意。莱诱导着这些分析师，一步步踏入陷阱，让他的雇员将个人照片带到不同的楼层，好像他们在那里工作一样，由此上演了一场大戏。他们假装打着电话，好像正在忙着买进和卖出能源和汽油。这是莱作为获取者的另一种表现：他沉迷于给上面的人留下好印象，却很少担心下面的人怎么看他。塞缪尔·约翰逊（Samuel Johnson）曾写道：“衡量一个人的真正标准，是看他如何对待那些完全不能给自己带来好处的人。”

Viewpoint #

From #

Links #

为了鉴别出获取者，我们都可以怎么做？ #

在网上，我们可以通过访问公开的数据库，找到共享的关系联结，以此来追踪一个人的声望信息。我们也不再需要一份公司年报，才能逮住获取者，因为社交网络里充斥着各种形式和强度的炫耀行为。只言片语或照片这样微小的线索，就可以为我们提供丰富的信息，有研究表明，一般人仅仅通过浏览Facebook页面，就能鉴别出获取者。在一项研究中，心理学家让人们填写问卷，衡量自己是不是获取者。然后，研究者要求一些陌生人访问这些人的Facebook页面，陌生人能够以令人震惊的准确性，找出那些获取者。获取者发布的信息被认为更加自我鼓吹、以自我为中心和自我拔高。他们的发言被评定为是自吹自擂和狂妄自大的。获取者也有更多的Facebook好友，以此来积攒肤浅的社会关系，从而宣传自己的成就，并保持联系以获得帮助。此外，他们还更愿意张贴虚荣的、自我奉承的照片。

Viewpoint #

From #

Links #

什么是回归测试（regression test）？ #

一种系统测试可保证之前的Bug不会重现。回归测试可以被理解为曾经发生过的，导致系统故障或产生错误信息的Bug列表。通过将这些Bug记录为系统测试或者集成测试，重构代码的工程师可以保证他们不会偶然间将他们曾经辛苦调查和修复的Bug又带回来。

Viewpoint #

From #

Links #

Content #

固定资产（Fixed Assets）需要满足哪两个特征？固定资产指同时具有下列特征的有形资产：

1. 为生产商品、提供劳务、出租或经营管理而持有；
2. 使用寿命超过一个会计年度。

Viewpoint #

From #

Links #

碰撞指针(Bump-pointer) #

分配新的对象都是在 From 空间中，所以 From 空间也被称为分配空间（Allocation Space），而 To 空间则相应地被称为幸存者空间（Survivor Sapce）。在 JVM 代码中，这两套命名方式都会出现，所以搞清楚这点比较有好处。

最基础的 copy 算法，就是把程序运行的堆分成大小相同的两半，一半称为 From 空间，一半称为 To 空间。当创建新的对象时，都是在 From 空间里进行内存的分配。等 From 空间满了以后，垃圾回收器就会把活跃对象复制到 To 空间，把原来的 From 空间全部清空。然后再把这两个空间交换，也就是说 To 空间变成下一轮的 From 空间，现在的 From 空间变成 To 空间。具体过程如图所示： 可以看到，上图中的 from 空间已经满了，这时候，如果想再创建一个新的对象是无法满足的。此时就会执行 GC 算法将活跃对象都拷贝到新的空间中去。

在 From 空间里，所有的对象都是从头向后紧密排列的，也就是说对象与对象之间是没有空隙的。而所有的可用内存全部在 From 空间的尾部，也就是上图中 top 指针所指向的位置之后。

那么，当我们需要在堆里创建一个新的对象时，就非常容易了，只需要将 top 指针向后移动即可。top 指针始终指向最后分配的对象的末尾。每当新分配一个新对象时，只需要移动一次指针即可，这种分配效率非常高。

如果按这种方式进行新对象的创建，那么对象与对象之间可以保证没有任何空隙，因为后一个对象是顶着前一个对象分配的，所以，这种方式也叫做碰撞指针（Bump-pointer）。

Viewpoint #

From #

20 | Scavenge：基于copy的垃圾回收算法

Links #

数组的切片化 #

采用 array[low : high : max]语法基于一个已存在的数组创建切片。这种方式被称为数组的切片化，比如下面代码：

arr := [10]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
sl := arr[3:7:9]

我们基于数组 arr 创建了一个切片 sl，这个切片 sl 在运行时中的表示是这样： 我们看到，基于数组创建的切片，它的起始元素从 low 所标识的下标值开始，切片的长度（len）是 high - low，它的容量是 max - low。而且，由于切片 sl 的底层数组就是数组 arr，对切片 sl 中元素的修改将直接影响数组 arr 变量。比如，如果我们将切片的第一个元素加 10，那么数组 arr 的第四个元素将变为 14：

sl[0] += 10
fmt.Println("arr[3] =", arr[3]) // 14

这样看来，切片好比打开了一个访问与修改数组的“窗口”，通过这个窗口，我们可以直接操作底层数组中的部分元素。这有些类似于我们操作文件之前打开的“文件描述符”（Windows 上称为句柄），通过文件描述符我们可以对底层的真实文件进行相关操作。可以说，切片之于数组就像是文件描述符之于文件。

在 Go 语言中，数组更多是“退居幕后”，承担的是底层存储空间的角色。切片就是数组的“描述符”，也正是因为这一特性，切片才能在函数参数传递时避免较大性能开销。因为我们传递的并不是数组本身，而是数组的“描述符”，而这个描述符的大小是固定的（见上面的三元组结构），无论底层的数组有多大，切片打开的“窗口”长度有多长，它都是不变的。此外，我们在进行数组切片化的时候，通常省略 max，而 max 的默认值为数组的长度。

Viewpoint #

From #

15｜同构复合类型：从定长数组到变长切片

Links #

切片的内部结构 #

Go 切片在运行时其实是一个三元组结构，它在 Go 运行时中的表示如下：

type slice struct {
    array unsafe.Pointer
    len   int
    cap   int
}

我们可以看到，每个切片包含三个字段：

• array: 是指向底层数组的指针；
• len: 是切片的长度，即切片中当前元素的个数；
• cap: 是底层数组的长度，也是切片的最大容量，cap 值永远大于等于 len 值。

如果我们用这个三元组结构表示切片类型变量 nums，会是这样： 我们看到，Go 编译器会自动为每个新创建的切片，建立一个底层数组，默认底层数组的长度与切片初始元素个数相同。

Viewpoint #

From #

15｜同构复合类型：从定长数组到变长切片

Links #