15th-March

To-do List

  • [x] 算法

    • [ ]

  • [ ] 项目

    • [ ] cmu15445
    • [x] mit6.824
    • [ ] mit6.081

  • [ ] 八股

    • [ ] 操作系统
    • [ ] 计算机网络
    • [ ] 数据库
    • [ ] redis
  • [x] 日常总结

算法

今天没写。。。 心态有点小崩 等会随便找个题练个手吧

项目

6.824

完成了mapreduce

主要是coordinator mapworker和reduceworker的协调，感觉还是表达能力差了点

放点主要代码吧

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
63
64
65
66
67
68
69
70
71
72
73
74
75
func DoMap(mapf func(string, string) []KeyValue, task *Task) {
	//读入每个输入文件，将其传给map，累积中间Map输出。
	fmt.Println("Begin map function,task information(TaskType Filename NReduce TaskId Finished Start):", task)
	intermediate := []KeyValue{}
	filename := task.Filename
	file, err := os.Open(filename)
	if err != nil {
		log.Fatalf("cannot open %v", filename)
	}
	content, err := ioutil.ReadAll(file)
	if err != nil {
		log.Fatalf("cannot read %v", filename)
	}
	file.Close()
	kva := mapf(filename, string(content))
	//中间key
	intermediate = append(intermediate, kva...)
	fmt.Println("map生成的中间key:", intermediate)
	intermediateMap := make([][]KeyValue, task.NReduce)
	for _, tmp := range intermediate {
		intermediateMap[ihash(tmp.Key)%task.NReduce] = append(intermediateMap[ihash(tmp.Key)%task.NReduce], tmp)
	}
	sort.Sort(ByKey(intermediate))
	i := 0
	for i < task.NReduce {
		oname := "mr-" + strconv.Itoa(task.TaskId) + "-" + strconv.Itoa(i)
		ofile, _ := os.Create(oname)
		enc := json.NewEncoder(ofile)
		for _, kv := range intermediateMap[i] {
			enc.Encode(&kv)
		}
		i++
		ofile.Close()
	}
}

func DoReduce(reducef func(string, []string) string, task *Task) {
	i := 0
	intermediate := []KeyValue{}
	for i < task.NReduce {
		filepath := task.Filename + strconv.Itoa(i) + "-" + strconv.Itoa(task.TaskId)
		fmt.Println("Begin map function,task information(TaskType Filename NReduce TaskId Finished Start):", task, "\nfilepath:", filepath)
		file, _ := os.Open(filepath)
		dec := json.NewDecoder(file)
		//解码
		for {
			var kv KeyValue
			if err := dec.Decode(&kv); err != nil {
				break
			}
			intermediate = append(intermediate, kv)
		}
		file.Close()
		i++
	}
	sort.Sort(ByKey(intermediate))
	i = 0
	oname := "mr-out-" + strconv.Itoa(task.TaskId)
	ofile, _ := os.Create(oname)

	for i < len(intermediate) {
		j := i + 1
		for j < len(intermediate) && intermediate[j].Key == intermediate[i].Key {
			j++
		}
		values := []string{}
		//将相同的Key收集到一起
		for k := i; k < j; k++ {
			values = append(values, intermediate[k].Value)
		}
		output := reducef(intermediate[i].Key, values)
		fmt.Fprintf(ofile, "%v %v\n", intermediate[i].Key, output)
		i = j
	}
}

八股

Golang-切片的容量是怎样增长的

一般都是在向slice追加了元素之后，才会引起扩容，追加元素调用的是append函数

先来看看append函数的原型：

1
func append(slice []Type, elems ...Type) []Type

append函数的参数长度可变，因此可以追加多个值到slice中，还可以用…传入slice，直接追加一个切片

1
2
slice = append(slice, elem1, elem2)
slice = append(slice, anotherSlice...)

append函数返回值是一个新的slice，Go编译器不允许调用了append函数后不使用返回值。

使用 append 可以向 slice 追加元素，实际上是往底层数组添加元素。但是底层数组的长度是固定的，如果索引 len-1 所指向的元素已经是底层数组的最后一个元素，就没法再添加了。

这时，slice 会迁移到新的内存位置，新底层数组的长度也会增加，这样就可以放置新增的元素。同时，为了应对未来可能再次发生的 append 操作，新的底层数组的长度，也就是新 slice 的容量是留了一定的 buffer 的。否则，每次添加元素的时候，都会发生迁移，成本太高。

新 slice 预留的 buffer 大小是有一定规律的。在golang1.18版本更新之前网上大多数的文章都是这样描述slice的扩容策略的：

当原 slice 容量小于 1024 的时候，新 slice 容量变成原来的 2 倍；原 slice 容量超过 1024，新 slice 容量变成原来的1.25倍。

在1.18版本更新之后，slice的扩容策略变为了：

当原slice容量(oldcap)小于256的时候，新slice(newcap)容量为原来的2倍；原slice容量超过256，新slice容量newcap = oldcap+(oldcap+3*256)/4

举例：

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

import "fmt"

func main() {
	s := make([]int, 0)

	oldCap := cap(s)

	for i := 0; i < 2048; i++ {
		s = append(s, i)

		newCap := cap(s)

		if newCap != oldCap {
			fmt.Printf("[%d -> %4d] cap = %-4d  |  after append %-4d  cap = %-4d\n", 0, i-1, oldCap, i, newCap)
			oldCap = newCap
		}
	}
}

我先创建了一个空的 slice，然后，在一个循环里不断往里面 append 新的元素。然后记录容量的变化，并且每当容量发生变化的时候，记录下老的容量，以及添加完元素之后的容量，同时记下此时 slice 里的元素。这样，我就可以观察，新老 slice 的容量变化情况，从而找出规律。

运行结果(1.18版本之前)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
[0 ->   -1] cap = 0     |  after append 0     cap = 1   
[0 ->    0] cap = 1     |  after append 1     cap = 2   
[0 ->    1] cap = 2     |  after append 2     cap = 4   
[0 ->    3] cap = 4     |  after append 4     cap = 8   
[0 ->    7] cap = 8     |  after append 8     cap = 16  
[0 ->   15] cap = 16    |  after append 16    cap = 32  
[0 ->   31] cap = 32    |  after append 32    cap = 64  
[0 ->   63] cap = 64    |  after append 64    cap = 128 
[0 ->  127] cap = 128   |  after append 128   cap = 256 
[0 ->  255] cap = 256   |  after append 256   cap = 512 
[0 ->  511] cap = 512   |  after append 512   cap = 1024
[0 -> 1023] cap = 1024  |  after append 1024  cap = 1280
[0 -> 1279] cap = 1280  |  after append 1280  cap = 1696
[0 -> 1695] cap = 1696  |  after append 1696  cap = 2304

运行结果(1.18版本)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
[0 ->   -1] cap = 0     |  after append 0     cap = 1
[0 ->    0] cap = 1     |  after append 1     cap = 2   
[0 ->    1] cap = 2     |  after append 2     cap = 4   
[0 ->    3] cap = 4     |  after append 4     cap = 8   
[0 ->    7] cap = 8     |  after append 8     cap = 16  
[0 ->   15] cap = 16    |  after append 16    cap = 32  
[0 ->   31] cap = 32    |  after append 32    cap = 64  
[0 ->   63] cap = 64    |  after append 64    cap = 128 
[0 ->  127] cap = 128   |  after append 128   cap = 256 
[0 ->  255] cap = 256   |  after append 256   cap = 512 
[0 ->  511] cap = 512   |  after append 512   cap = 848 
[0 ->  847] cap = 848   |  after append 848   cap = 1280
[0 -> 1279] cap = 1280  |  after append 1280  cap = 1792
[0 -> 1791] cap = 1792  |  after append 1792  cap = 2560

根据上面的结果我们可以看出在1.18版本之前：

在原来的slice容量oldcap小于1024的时候，新 slice 的容量newcap的确是oldcap的2倍。

但是，当oldcap大于等于 1024 的时候，情况就有变化了。当向 slice 中添加元素 1280 的时候，原来的slice 的容量为 1280，之后newcap变成了 1696，两者并不是 1.25 倍的关系（1696/1280=1.325）。添加完 1696 后，新的容量 2304 当然也不是 1696 的 1.25 倍。

在1.18版本之后：

在原来的slice 容量oldcap小于256的时候，新 slice 的容量newcap的确是oldcap 的2倍。

但是，当oldcap容量大于等于 256 的时候，情况就有变化了。当向 slice 中添加元素 512 的时候，老 slice 的容量为 512，之后变成了 848，两者并没有符合newcap = oldcap+(oldcap+3*256)/4 的策略（512+（512+3*256）/4）=832。添加完 848 后，新的容量 1280 当然也不是 按照之前策略所计算出的的1252。

难道现在网上各种文章中的扩容策略并不是正确的吗。我们直接搬出源码：源码面前，了无秘密。

从前面汇编代码我们也看到了，向 slice 追加元素的时候，若容量不够，会调用 growslice 函数，所以我们直接看它的代码。

golang版本1.9.5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// go 1.9.5 src/runtime/slice.go:82
func growslice(et *_type, old slice, cap int) slice {
    // ……
    newcap := old.cap
	doublecap := newcap + newcap
	if cap > doublecap {
		newcap = cap
	} else {
		if old.len < 1024 {
			newcap = doublecap
		} else {
			for newcap < cap {
				newcap += newcap / 4
			}
		}
	}
	// ……
	
	capmem = roundupsize(uintptr(newcap) * ptrSize)
	newcap = int(capmem / ptrSize)
}

golang版本1.18

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
// go 1.18 src/runtime/slice.go:178
func growslice(et *_type, old slice, cap int) slice {
    // ……
    newcap := old.cap
	doublecap := newcap + newcap
	if cap > doublecap {
		newcap = cap
	} else {
		const threshold = 256
		if old.cap < threshold {
			newcap = doublecap
		} else {
			for 0 < newcap && newcap < cap {
                // Transition from growing 2x for small slices
				// to growing 1.25x for large slices. This formula
				// gives a smooth-ish transition between the two.
				newcap += (newcap + 3*threshold) / 4
			}
			if newcap <= 0 {
				newcap = cap
			}
		}
	}
	// ……
    
	capmem = roundupsize(uintptr(newcap) * ptrSize)
	newcap = int(capmem / ptrSize)
}

如果只看前半部分，现在网上各种文章里说的 newcap 的规律是对的。现实是，后半部分还对 newcap 作了一个内存对齐，这个和内存分配策略相关。进行内存对齐之后，新 slice 的容量是要 大于等于 按照前半部分生成的newcap。

之后，向 Go 内存管理器申请内存，将老 slice 中的数据复制过去，并且将 append 的元素添加到新的底层数组中。

最后，向 growslice 函数调用者返回一个新的 slice，这个 slice 的长度并没有变化，而容量却增大了。

总结

。。。失败 但是差不多能知道哪里不足了 可以尝试一下 明天笔试加油

diary
#diary #八股
15th-March
https://www.polarishaw.top/2024/03/15/15th-March/
作者
Polaris
发布于
2024年3月15日
许可协议