Performance Differences from Page Faults vs. Prefetching

Just how large can the performance difference caused by page faults be? Let’s write a benchmark to find out.

Simulating Page Fault Behavior

To build this benchmark, we need to understand two low-level Linux syscalls for memory management: mmap and madvise. For memory allocation, mmap can be called with the anonymous and private mapping flags MAP_ANON and MAP_PRIVATE. Memory allocated this way is in a page-fault state — any access to the allocated region will trigger a page fault. We can exploit this to measure the cost of accessing memory through page faults. Meanwhile, madvise can advise the kernel to prefetch memory in advance. By applying prefetching to mmap-allocated memory, we can then measure the cost of accessing already-prefetched memory:

 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


package main_test

import (
	"fmt"
	"syscall"
	"testing"
)

var pageSize = syscall.Getpagesize()

func BenchmarkPrefetch(b *testing.B) {
	for i := 1; i <= 1024; i *= 2 {
		benchMem(b, i, true)
	}
}

func BenchmarkPageFault(b *testing.B) {
	for i := 1; i <= 1024; i *= 2 {
		benchMem(b, i, false)
	}
}

func benchMem(b *testing.B, allocMB int, prefetch bool) {
	b.Run(fmt.Sprintf("%dMiB", allocMB), func(b *testing.B) {
		for j := 0; j < b.N; j++ {
			b.StopTimer()
			anonMB := allocMB << 20 // MiB
			m, err := syscall.Mmap(-1, 0, anonMB,
				syscall.PROT_READ|syscall.PROT_WRITE,
				syscall.MAP_ANON|syscall.MAP_PRIVATE)
			if err != nil {
				panic(err)
			}
			if prefetch {
				err = syscall.Madvise(m, syscall.MADV_HUGEPAGE)
				if err != nil {
					panic(err)
				}
			}
			b.StartTimer()
			// 逐页访问，用来测量写入成本
			for i := 0; i < len(m); i += pageSize {
				m[i] = 42
			}
			b.StopTimer()
			err = syscall.Madvise(m, syscall.MADV_DONTNEED)
			if err != nil {
				panic(err)
			}
		}
	})
}

Using the bench tool, we can run and obtain the following results:

 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


$ uname -a
Linux changkun-perflock 5.8.0-34-generic #37~20.04.2-Ubuntu SMP Thu Dec 17 14:53:00 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux

$ bench
name                  time/op
Prefetch/1MiB-16        156µs ±0%
Prefetch/2MiB-16        315µs ±1%
Prefetch/4MiB-16        403µs ±1%
Prefetch/8MiB-16        581µs ±2%
Prefetch/16MiB-16      1000µs ±2%
Prefetch/32MiB-16      2170µs ±3%
Prefetch/64MiB-16      4450µs ±3%
Prefetch/128MiB-16     8920µs ±3%
Prefetch/256MiB-16    18200µs ±1%
Prefetch/512MiB-16    36600µs ±1%
Prefetch/1024MiB-16   72200µs ±4%
PageFault/1MiB-16       157µs ±1%
PageFault/2MiB-16       315µs ±1%
PageFault/4MiB-16       638µs ±1%
PageFault/8MiB-16      1310µs ±1%
PageFault/16MiB-16     2760µs ±1%
PageFault/32MiB-16     5940µs ±1%
PageFault/64MiB-16    12100µs ±0%
PageFault/128MiB-16   23900µs ±1%
PageFault/256MiB-16   47400µs ±1%
PageFault/512MiB-16   94100µs ±0%
PageFault/1024MiB-16 187000µs ±1%

As allocation size grows, the performance gain from prefetching becomes very significant:

`MADV_DONTNEED` v.s. `MADV_FREE`

Worth noting is that we used the MADV_DONTNEED flag to release memory. For the other release mode, MADV_FREE, its lazy-release semantics mean that memory marked for release does not immediately enter a page-fault state, which could affect subsequent memory operations and should in principle yield some performance improvement. We can verify the effect of switching to MADV_FREE with a simple test:

 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
76
77
78
79
80
81


// main.go
package main

/*
#include <sys/mman.h>
*/
import "C"

var MADV_FREE = C.MADV_FREE // 获得 MADV_FREE 参数

func main() {}

// main_test.go
package main

import (
	"fmt"
	"syscall"
	"testing"
)

var pageSize = syscall.Getpagesize()

func BenchmarkPrefetch(b *testing.B) {
	for i := 1; i <= 1024; i *= 2 {
		benchMem(b, i, true, true)
	}
	for i := 1; i <= 1024; i *= 2 {
		benchMem(b, i, true, false)
	}
}

func BenchmarkPageFault(b *testing.B) {
	for i := 1; i <= 1024; i *= 2 {
		benchMem(b, i, false, true)
	}
	for i := 1; i <= 1024; i *= 2 {
		benchMem(b, i, false, false)
	}
}

func benchMem(b *testing.B, allocMB int, prefetch bool, dontneed bool) {
	var s string
	if dontneed {
		s = fmt.Sprintf("MADV-DONTNEED-%dMiB", allocMB)
	} else {
		s = fmt.Sprintf("MADV-FREE-%dMiB", allocMB)
	}
	b.Run(s, func(b *testing.B) {
		for j := 0; j < b.N; j++ {
			b.StopTimer()
			anonMB := allocMB << 20 // MiB
			m, err := syscall.Mmap(-1, 0, anonMB, syscall.PROT_READ|syscall.PROT_WRITE, syscall.MAP_ANON|syscall.MAP_PRIVATE)
			if err != nil {
				panic(err)
			}
			if prefetch {
				err = syscall.Madvise(m, syscall.MADV_HUGEPAGE)
				if err != nil {
					panic(err)
				}
			}
			b.StartTimer()
			for i := 0; i < len(m); i += pageSize {
				m[i] = 42
			}
			b.StopTimer()
			if dontneed {
				err = syscall.Madvise(m, syscall.MADV_DONTNEED)
				if err != nil {
					panic(err)
				}
			} else {
				err = syscall.Madvise(m, MADV_FREE)
				if err != nil {
					panic(err)
				}
			}
		}
	})
}

We can obtain the following results:

 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


name                                time/op
Prefetch/MADV-DONTNEED-1MiB-16        157µs ±1%
Prefetch/MADV-DONTNEED-2MiB-16       180µs ±77%
Prefetch/MADV-DONTNEED-4MiB-16        172µs ±1%
Prefetch/MADV-DONTNEED-8MiB-16        351µs ±5%
Prefetch/MADV-DONTNEED-16MiB-16       753µs ±4%
Prefetch/MADV-DONTNEED-32MiB-16      1.91ms ±3%
Prefetch/MADV-DONTNEED-64MiB-16      4.22ms ±3%
Prefetch/MADV-DONTNEED-128MiB-16     8.65ms ±4%
Prefetch/MADV-DONTNEED-256MiB-16     17.7ms ±3%
Prefetch/MADV-DONTNEED-512MiB-16     35.7ms ±2%
Prefetch/MADV-FREE-1MiB-16            189µs ±4%
Prefetch/MADV-FREE-2MiB-16            391µs ±4%
Prefetch/MADV-FREE-4MiB-16          1.64ms ±19%
Prefetch/MADV-FREE-8MiB-16          2.84ms ±31%
Prefetch/MADV-FREE-16MiB-16          3.32ms ±8%
Prefetch/MADV-FREE-32MiB-16          6.30ms ±1%
Prefetch/MADV-FREE-64MiB-16          12.7ms ±1%
Prefetch/MADV-FREE-128MiB-16         25.1ms ±2%
Prefetch/MADV-FREE-256MiB-16         50.7ms ±2%
Prefetch/MADV-FREE-512MiB-16          101ms ±1%
PageFault/MADV-DONTNEED-1MiB-16       157µs ±0%
PageFault/MADV-DONTNEED-2MiB-16       317µs ±1%
PageFault/MADV-DONTNEED-4MiB-16       645µs ±1%
PageFault/MADV-DONTNEED-8MiB-16      1.31ms ±1%
PageFault/MADV-DONTNEED-16MiB-16     2.77ms ±1%
PageFault/MADV-DONTNEED-32MiB-16     5.92ms ±0%
PageFault/MADV-DONTNEED-64MiB-16     12.4ms ±0%
PageFault/MADV-DONTNEED-128MiB-16    25.2ms ±0%
PageFault/MADV-DONTNEED-256MiB-16    50.7ms ±1%
PageFault/MADV-DONTNEED-512MiB-16     102ms ±0%
PageFault/MADV-FREE-1MiB-16           191µs ±2%
PageFault/MADV-FREE-2MiB-16           389µs ±3%
PageFault/MADV-FREE-4MiB-16           770µs ±1%
PageFault/MADV-FREE-8MiB-16          1.54ms ±1%
PageFault/MADV-FREE-16MiB-16         3.08ms ±1%
PageFault/MADV-FREE-32MiB-16         6.17ms ±2%
PageFault/MADV-FREE-64MiB-16         12.3ms ±2%
PageFault/MADV-FREE-128MiB-16        25.0ms ±2%
PageFault/MADV-FREE-256MiB-16        50.1ms ±3%
PageFault/MADV-FREE-512MiB-16         101ms ±1%

We can see that using MADV_FREE in the page-fault scenario brings little change:

1
2


PageFault/MADV-DONTNEED-512MiB-16     102ms ±0%
PageFault/MADV-FREE-512MiB-16         101ms ±1%

Conversely, in the prefetch scenario, MADV_FREE does not deliver the better performance it claims — instead it introduces more overhead:

1
2


Prefetch/MADV-DONTNEED-512MiB-16     35.7ms ±2%
Prefetch/MADV-FREE-512MiB-16          101ms ±1%

This is rather interesting. Why does this happen? When kernel support for MADV_FREE was added, there was a mailing list discussion about it:

1
2
3
4
5
6
7
8
9


...
MADV_FREE is about 2 time faster than MADV_DONTNEED but
it starts slow down as memory pressure is heavy compared to
DONTNEED. It's natural because MADV_FREE needs more steps to
free pages so one thing I have a mind to overcome is just
purge them if memory pressure is severe(ex, kswapd active)
rather than giving a chance to promote freeing page
from inactive LRU when madvise_free is called.
...

Further verifying these claims would likely require digging into the kernel source, but the explanation is theoretically plausible. Since MADV_FREE merely defers the release of memory, it still needs to release memory when pressure is high. Our benchmark repeatedly allocates large blocks of memory, which easily creates the appearance of heavy memory pressure — this is an extreme simulation, and actual behavior may more closely resemble the earlier page-fault test where memory pressure had not yet built up. In most cases MADV_FREE is slightly better than MADV_DONTNEED, but under high pressure MADV_FREE can be worse than MADV_DONTNEED.

模拟缺页行为

想要实现这样的基准测试，需要了解 Linux 下对内存管理的两个底层的系统调用：mmap 和 madvise。对于内存分配场景，mmap 可以使用匿名、私有映射两个参数 MAP_ANON 和 MAP_PRIVATE，这时候创建的内存实际上属于缺页状态，任何对其申请到内存区域的访问行为都将导致缺页，利用这一原理，便可以用来测量缺页时访问内存的成本；而 madvise 能够用来给内核提供建议，提前对内存进行预取，于是可以利用这一点，对 mmap 的来的内存执行预取操作，进而测量预取后访问内存的成本：

 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


package main_test

import (
	"fmt"
	"syscall"
	"testing"
)

var pageSize = syscall.Getpagesize()

func BenchmarkPrefetch(b *testing.B) {
	for i := 1; i <= 1024; i *= 2 {
		benchMem(b, i, true)
	}
}

func BenchmarkPageFault(b *testing.B) {
	for i := 1; i <= 1024; i *= 2 {
		benchMem(b, i, false)
	}
}

func benchMem(b *testing.B, allocMB int, prefetch bool) {
	b.Run(fmt.Sprintf("%dMiB", allocMB), func(b *testing.B) {
		for j := 0; j < b.N; j++ {
			b.StopTimer()
			anonMB := allocMB << 20 // MiB
			m, err := syscall.Mmap(-1, 0, anonMB,
				syscall.PROT_READ|syscall.PROT_WRITE,
				syscall.MAP_ANON|syscall.MAP_PRIVATE)
			if err != nil {
				panic(err)
			}
			if prefetch {
				err = syscall.Madvise(m, syscall.MADV_HUGEPAGE)
				if err != nil {
					panic(err)
				}
			}
			b.StartTimer()
			// 逐页访问，用来测量写入成本
			for i := 0; i < len(m); i += pageSize {
				m[i] = 42
			}
			b.StopTimer()
			err = syscall.Madvise(m, syscall.MADV_DONTNEED)
			if err != nil {
				panic(err)
			}
		}
	})
}

使用 bench 工具，可以运行得到下面的结果：

 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


$ uname -a
Linux changkun-perflock 5.8.0-34-generic #37~20.04.2-Ubuntu SMP Thu Dec 17 14:53:00 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux

$ bench
name                  time/op
Prefetch/1MiB-16        156µs ±0%
Prefetch/2MiB-16        315µs ±1%
Prefetch/4MiB-16        403µs ±1%
Prefetch/8MiB-16        581µs ±2%
Prefetch/16MiB-16      1000µs ±2%
Prefetch/32MiB-16      2170µs ±3%
Prefetch/64MiB-16      4450µs ±3%
Prefetch/128MiB-16     8920µs ±3%
Prefetch/256MiB-16    18200µs ±1%
Prefetch/512MiB-16    36600µs ±1%
Prefetch/1024MiB-16   72200µs ±4%
PageFault/1MiB-16       157µs ±1%
PageFault/2MiB-16       315µs ±1%
PageFault/4MiB-16       638µs ±1%
PageFault/8MiB-16      1310µs ±1%
PageFault/16MiB-16     2760µs ±1%
PageFault/32MiB-16     5940µs ±1%
PageFault/64MiB-16    12100µs ±0%
PageFault/128MiB-16   23900µs ±1%
PageFault/256MiB-16   47400µs ±1%
PageFault/512MiB-16   94100µs ±0%
PageFault/1024MiB-16 187000µs ±1%

可以看到随着分配内存的增大，预取带来的性能提升是非常可观的：

`MADV_DONTNEED` v.s. `MADV_FREE`

值得一提的是这里使用的是 MADV_DONTNEED 参数来释放内存。对于另一种释放模式 MADV_FREE 而言，因为其本质是懒惰释放，使用这个参数宣告释放的内存不会立刻进入缺页状态，进而对后续的内存操作可能带来影响，原则上应该会带来一定的性能提升。那么，但根据同样可以简单的验证换用 MADV_FREE 参数后带来的影响：

 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
76
77
78
79
80
81


// main.go
package main

/*
#include <sys/mman.h>
*/
import "C"

var MADV_FREE = C.MADV_FREE // 获得 MADV_FREE 参数

func main() {}

// main_test.go
package main

import (
	"fmt"
	"syscall"
	"testing"
)

var pageSize = syscall.Getpagesize()

func BenchmarkPrefetch(b *testing.B) {
	for i := 1; i <= 1024; i *= 2 {
		benchMem(b, i, true, true)
	}
	for i := 1; i <= 1024; i *= 2 {
		benchMem(b, i, true, false)
	}
}

func BenchmarkPageFault(b *testing.B) {
	for i := 1; i <= 1024; i *= 2 {
		benchMem(b, i, false, true)
	}
	for i := 1; i <= 1024; i *= 2 {
		benchMem(b, i, false, false)
	}
}

func benchMem(b *testing.B, allocMB int, prefetch bool, dontneed bool) {
	var s string
	if dontneed {
		s = fmt.Sprintf("MADV-DONTNEED-%dMiB", allocMB)
	} else {
		s = fmt.Sprintf("MADV-FREE-%dMiB", allocMB)
	}
	b.Run(s, func(b *testing.B) {
		for j := 0; j < b.N; j++ {
			b.StopTimer()
			anonMB := allocMB << 20 // MiB
			m, err := syscall.Mmap(-1, 0, anonMB, syscall.PROT_READ|syscall.PROT_WRITE, syscall.MAP_ANON|syscall.MAP_PRIVATE)
			if err != nil {
				panic(err)
			}
			if prefetch {
				err = syscall.Madvise(m, syscall.MADV_HUGEPAGE)
				if err != nil {
					panic(err)
				}
			}
			b.StartTimer()
			for i := 0; i < len(m); i += pageSize {
				m[i] = 42
			}
			b.StopTimer()
			if dontneed {
				err = syscall.Madvise(m, syscall.MADV_DONTNEED)
				if err != nil {
					panic(err)
				}
			} else {
				err = syscall.Madvise(m, MADV_FREE)
				if err != nil {
					panic(err)
				}
			}
		}
	})
}

同样的可以得到下面的结果：

 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


name                                time/op
Prefetch/MADV-DONTNEED-1MiB-16        157µs ±1%
Prefetch/MADV-DONTNEED-2MiB-16       180µs ±77%
Prefetch/MADV-DONTNEED-4MiB-16        172µs ±1%
Prefetch/MADV-DONTNEED-8MiB-16        351µs ±5%
Prefetch/MADV-DONTNEED-16MiB-16       753µs ±4%
Prefetch/MADV-DONTNEED-32MiB-16      1.91ms ±3%
Prefetch/MADV-DONTNEED-64MiB-16      4.22ms ±3%
Prefetch/MADV-DONTNEED-128MiB-16     8.65ms ±4%
Prefetch/MADV-DONTNEED-256MiB-16     17.7ms ±3%
Prefetch/MADV-DONTNEED-512MiB-16     35.7ms ±2%
Prefetch/MADV-FREE-1MiB-16            189µs ±4%
Prefetch/MADV-FREE-2MiB-16            391µs ±4%
Prefetch/MADV-FREE-4MiB-16          1.64ms ±19%
Prefetch/MADV-FREE-8MiB-16          2.84ms ±31%
Prefetch/MADV-FREE-16MiB-16          3.32ms ±8%
Prefetch/MADV-FREE-32MiB-16          6.30ms ±1%
Prefetch/MADV-FREE-64MiB-16          12.7ms ±1%
Prefetch/MADV-FREE-128MiB-16         25.1ms ±2%
Prefetch/MADV-FREE-256MiB-16         50.7ms ±2%
Prefetch/MADV-FREE-512MiB-16          101ms ±1%
PageFault/MADV-DONTNEED-1MiB-16       157µs ±0%
PageFault/MADV-DONTNEED-2MiB-16       317µs ±1%
PageFault/MADV-DONTNEED-4MiB-16       645µs ±1%
PageFault/MADV-DONTNEED-8MiB-16      1.31ms ±1%
PageFault/MADV-DONTNEED-16MiB-16     2.77ms ±1%
PageFault/MADV-DONTNEED-32MiB-16     5.92ms ±0%
PageFault/MADV-DONTNEED-64MiB-16     12.4ms ±0%
PageFault/MADV-DONTNEED-128MiB-16    25.2ms ±0%
PageFault/MADV-DONTNEED-256MiB-16    50.7ms ±1%
PageFault/MADV-DONTNEED-512MiB-16     102ms ±0%
PageFault/MADV-FREE-1MiB-16           191µs ±2%
PageFault/MADV-FREE-2MiB-16           389µs ±3%
PageFault/MADV-FREE-4MiB-16           770µs ±1%
PageFault/MADV-FREE-8MiB-16          1.54ms ±1%
PageFault/MADV-FREE-16MiB-16         3.08ms ±1%
PageFault/MADV-FREE-32MiB-16         6.17ms ±2%
PageFault/MADV-FREE-64MiB-16         12.3ms ±2%
PageFault/MADV-FREE-128MiB-16        25.0ms ±2%
PageFault/MADV-FREE-256MiB-16        50.1ms ±3%
PageFault/MADV-FREE-512MiB-16         101ms ±1%

可以看到使用 MADV_FREE 缺页场景下并没有带来多大变化：

1
2


PageFault/MADV-DONTNEED-512MiB-16     102ms ±0%
PageFault/MADV-FREE-512MiB-16         101ms ±1%

相反，对于已经预取的情况下并没有 MADV_FREE 宣称的那样具有更好的性能，反而带来了更多的性能损耗：

1
2


Prefetch/MADV-DONTNEED-512MiB-16     35.7ms ±2%
Prefetch/MADV-FREE-512MiB-16          101ms ±1%

这就比较有有趣了。为什么会这样呢？在内核增加 MADV_FREE 支持的时候有这样一个邮件列表讨论：

1
2
3
4
5
6
7
8
9


...
MADV_FREE is about 2 time faster than MADV_DONTNEED but
it starts slow down as memory pressure is heavy compared to
DONTNEED. It's natural because MADV_FREE needs more steps to
free pages so one thing I have a mind to overcome is just
purge them if memory pressure is severe(ex, kswapd active)
rather than giving a chance to promote freeing page
from inactive LRU when madvise_free is called.
...

至于如何进一步验证这些说法可能需要把内核代码拿出来溜了，不过这个解释读起来从理论上分析是比较可信的。由于从 MADV_FREE 的行为来看只是延缓了释放的行为，实际上当内存紧张时还是需要释放的。我们上面的基准测试反复申请内存，很容易造成内存紧张的假象，某种程度上属于极端的模拟情况，实际状态下可能跟此前的 PageFault 测试中还未造成内存高压相似。即大部分情况下 MADV_FREE 略好于 MADV_DONTNEED，在面临高压时 MADV_FREE 反逊于 MADV_DONTNEED。

Performance Differences from Page Faults vs. Prefetching缺页与预取带来的性能差异

Simulating Page Fault Behavior

`MADV_DONTNEED` v.s. `MADV_FREE`

Further Reading

模拟缺页行为

`MADV_DONTNEED` v.s. `MADV_FREE`

进一步阅读的参考

Simulating Page Fault Behavior

MADV_DONTNEED v.s. MADV_FREE

Further Reading

模拟缺页行为

MADV_DONTNEED v.s. MADV_FREE

进一步阅读的参考

`MADV_DONTNEED` v.s. `MADV_FREE`

`MADV_DONTNEED` v.s. `MADV_FREE`