数组的重复赋值
赋值一个数组的每一位,可以使用 3 种方法:
memset
std::fill
- 手写
for
循环
本文将比较三者的优劣,并给出相应的示范 C++ 代码以及汇编代码。
结论
方法 |
实现原理 |
无优化赋值为字节值 |
O2 优化赋值为字节值 |
赋值为其他值 |
memset |
将内存块的每个字节设置为特定的值 |
常数 |
常数 |
无法完成 |
std::fill |
循环遍历每个元素赋值 |
线性 |
常数 |
线性 |
手写 for 循环 |
循环遍历每个元素赋值 |
线性 |
常数 |
线性 |
开启 O2 优化后,std::fill
或手写 for
循环,将数组赋值为字节值,都会被优化为 memset
,因此是常数时间复杂度。
对于 int
型数组,字节值只有 \(0\) 和 \(-1\)。
具体代码
memset
示范 C++ 代码
| #include <string.h>
int d[(int)1e6];
int main() {
memset(d, -1, sizeof(d));
return 0;
}
|
汇编代码
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 | main:
.LFB17:
1: call __fentry__
subq $40, %rsp #,
.seh_stackalloc 40
.seh_endprologue
# line 4: int main() {
call _monstartup #
call __main #
# line 5: memset(d, -1, sizeof(d));
movl $4000000, %r8d #,
movl $-1, %edx #,
leaq d(%rip), %rcx #, tmp84
call memset #
# line 7: }
xorl %eax, %eax #
addq $40, %rsp #,
ret
.seh_endproc
.globl d
.bss
.align 32
d:
.space 4000000
.def memset; .scl 2; .type 32; .endef
|
std::fill
示范 C++ 代码
| #include <bits/stl_algobase.h>
int d[(int)1e6];
int main() {
std::fill(d, d + (int)1e6, -1);
return 0;
}
|
赋值字节值汇编代码
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 | main:
.LFB505:
1: call __fentry__
subq $40, %rsp #,
.seh_stackalloc 40
.seh_endprologue
# line 4: int main() {
call _monstartup #
call __main #
# .../MinGW64/lib/gcc/x86_64-w64-mingw32/11.2.0/include/c++/bits/stl_algobase.h:924: *__first = __tmp;
movl $4000000, %r8d #,
movl $255, %edx #,
leaq d(%rip), %rcx #, tmp84
call memset #
# line 7: }
xorl %eax, %eax #
addq $40, %rsp #,
ret
.seh_endproc
.globl d
.bss
.align 32
d:
.space 4000000
.def memset; .scl 2; .type 32; .endef
|
赋值非字节值汇编代码
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 | main:
.LFB505:
1: call __fentry__
subq $40, %rsp #,
.seh_stackalloc 40
.seh_endprologue
# line 4: int main() {
call _monstartup #
call __main #
leaq d(%rip), %rax #, __first
leaq 4000000(%rax), %rdx #, tmp86
.p2align 4,,10
.p2align 3
.L2:
# .../MinGW64/lib/gcc/x86_64-w64-mingw32/11.2.0/include/c++/bits/stl_algobase.h:924: *__first = __tmp;
movl $1234, (%rax) #, MEM[(int *)__first_10]
# .../MinGW64/lib/gcc/x86_64-w64-mingw32/11.2.0/include/c++/bits/stl_algobase.h:923: for (; __first != __last; ++__first)
addq $4, %rax #, __first
# .../MinGW64/lib/gcc/x86_64-w64-mingw32/11.2.0/include/c++/bits/stl_algobase.h:923: for (; __first != __last; ++__first)
cmpq %rdx, %rax # tmp86, __first
jne .L2 #,
# line 7: }
xorl %eax, %eax #
addq $40, %rsp #,
ret
.seh_endproc
.globl d
.bss
.align 32
d:
.space 4000000
|
手写 for 循环
示范 C++ 代码
| int d[(int)1e6];
int main() {
for(int i = 0; i < (int)1e6; i ++)
d[i] = -1;
return 0;
}
|
赋值字节值汇编代码
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 | main:
.LFB0:
1: call __fentry__
subq $40, %rsp #,
.seh_stackalloc 40
.seh_endprologue
# line 3: int main() {
call _monstartup #
call __main #
# line 5: d[i] = -1;
movl $4000000, %r8d #,
movl $255, %edx #,
leaq d(%rip), %rcx #, tmp84
call memset #
# line 7: }
xorl %eax, %eax #
addq $40, %rsp #,
ret
.seh_endproc
.globl d
.bss
.align 32
d:
.space 4000000
.def memset; .scl 2; .type 32; .endef
|
赋值非字节值汇编代码
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 | main:
.LFB0:
1: call __fentry__
subq $40, %rsp #,
.seh_stackalloc 40
.seh_endprologue
# line 3: int main() {
call _monstartup #
call __main #
leaq d(%rip), %rax #, ivtmp.9
leaq 4000000(%rax), %rdx #, _13
.p2align 4,,10
.p2align 3
.L2:
# line 5: d[i] = 1234;
movl $1234, (%rax) #, MEM[(int *)_11]
# line 4: for(int i = 0; i < (int)1e6; i ++)
addq $4, %rax #, ivtmp.9
cmpq %rdx, %rax # _13, ivtmp.9
jne .L2 #,
# line 7: }
xorl %eax, %eax #
addq $40, %rsp #,
ret
.seh_endproc
.globl d
.bss
.align 32
d:
.space 4000000
|
汇编代码生成环境
| GNU C++23 (x86_64-posix-seh-rev1, Built by MinGW-W64 project) version 11.2.0 (x86_64-w64-mingw32)
compiled by GNU C version 11.2.0, GMP version 6.2.1, MPFR version 4.1.0, MPC version 1.2.1, isl version isl-0.24-GMP
GGC heuristics: --param ggc-min-expand=100 --param ggc-min-heapsize=131072
options passed: -m64 -mtune=core2 -march=nocona -O2 -std=c++23 -p
|
注:上述汇编代码只是摘取了部分主要的代码。