跳转至

数组的重复赋值

赋值一个数组的每一位，可以使用 3 种方法：

  • memset
  • std::fill
  • 手写 for 循环

本文将比较三者的优劣，并给出相应的示范 C++ 代码以及汇编代码。

结论

方法 实现原理 无优化赋值为字节值 O2 优化赋值为字节值 赋值为其他值
memset 将内存块的每个字节设置为特定的值 常数 常数 无法完成
std::fill 循环遍历每个元素赋值 线性 常数 线性
手写 for 循环 循环遍历每个元素赋值 线性 常数 线性

开启 O2 优化后，std::fill 或手写 for 循环，将数组赋值为字节值，都会被优化为 memset，因此是常数时间复杂度。

对于 int 型数组，字节值只有 \(0\) 和 \(-1\)。

具体代码

memset

示范 C++ 代码

1
2
3
4
5
6
7
#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++ 代码

1
2
3
4
5
6
7
#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++ 代码

1
2
3
4
5
6
7
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

汇编代码生成环境

1
2
3
4
5
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

注：上述汇编代码只是摘取了部分主要的代码。