Dragomir Ioan (ftsl) Atat la concursuri si olimpiade cat si in aplicatii practice, de multe ori se intalneste problema eficientei spatiului, cel mai grav caz al acesteia fiind stocarea unui tablou care contine valori de tip bool. Toate seturile de instructiuni moderne (x86, x64, ARM) pot adresa memorie doar la nivel de octet. Din aceasta cauza, aplicatii care necesita granularitate mai mare pentru elemente ce nu necesita ocuparea unui intreg octet trebuie ori sa sacrifice timp de executie pentru a combina mai multe elemente intr-un singur octet, ori sa sacrifice memorie, punand un singur element per octet si ignorand spatiul ramas neutilizat.
Exista un zvon ca tablourile din C sunt optimizate automat de compilator pe sisteme Linux in cadrul Olimpiadei de Informatica.
Deoarece mediul incurajat in cadrul Olimpiadei este Code::Blocks cu compilatoarele gcc/g++ MinGW, e natural ca si comisia de evaluare sa foloseasca aceleasi compilatoare pe Windows si variantele lor de linux pentru evaluarea pe linux. De aceea, acestea sunt compilatoarele folosite in demonstratiile urmatoare.
Pe langa tablourile simple mostenite din C, standardul C++ ofera doua metode principale pentru stocarea eficienta a tablourilor de booleeni: std::vector<bool> si std::bitset.
Scopul acestui articol este studierea diverselor tipuri de tablouri de booleeni, analizand atat codul assembler produs de compilator cat si comportamentul programului compilat.
Vector global (.bss)
volatile bool v[8 * 1024 * 1024];
int main() {
v[0] = true;
v[1] = false;
v[123] = true;
return v[123];
}
Codul de mai sus a fost compilat cu gcc la diferite nivele de optimizare (neoptimizat, optimizat pentru viteza cu -O2, optimizat pentru viteza si memorie cu -Os care implica -O2):
$ gcc --version
gcc (Ubuntu 5.4.0-6ubuntu1~16.04.5) 5.4.0 20160609
$ gcc global.c -o global-neoptimizat
$ gcc global.c -O2 -o global-o2
$ gcc global.c -Os -o global-os
La toate cele 3 binare sectiunea .bss (cea in care stocate variabilele globale) are dimensiunea 0x800020 = 8MiB si un pic. Considerand ca nu se irosesc 7/8 din sectiune, se poate spune ca vectorul ocupa aproape tot spatiul acesta, deci elementele ocupa un octet fiecare.
Pentru redundanta se poate analiza si codul compilat:
Neoptimizat
00000000004004d6 <main>:
4004d6: 55 push rbp
4004d7: 48 89 e5 mov rbp,rsp
4004da: c6 05 7f 0b 20 00 01 mov BYTE PTR [rip+0x200b7f],0x1 # 601060 <v>
4004e1: c6 05 79 0b 20 00 00 mov BYTE PTR [rip+0x200b79],0x0 # 601061 <v+0x1>
4004e8: c6 05 ec 0b 20 00 01 mov BYTE PTR [rip+0x200bec],0x1 # 6010db <v+0x7b>
4004ef: 0f b6 05 e5 0b 20 00 movzx eax,BYTE PTR [rip+0x200be5] # 6010db <v+0x7b>
4004f6: 0f b6 c0 movzx eax,al
4004f9: 5d pop rbp
4004fa: c3 ret
Primele doua instructiuni pregatesc stiva pentru functia main. Acestea sunt, in general, prezente in toate functiile si se numesc “preambulul”.
Urmatoarele 3 mov-uri seteaza valori din vector. Se poate observa ca se adreseaza la nivel de octet, nu de bit.
Primul movzx copiaza valoarea v[123] in registrul eax, iar a doua sterge tot in afara de ultimii 4 biti ai registrului, in caz ca ar fi fost altceva in afara de 0 si 1.
pop rbp se intoarce la stiva functiei precedente, marcand sfarsitul lui main, iar ret returneaza valoarea din registrul eax.
-O2
00000000004003e0 <main>:
4003e0: c6 05 79 0c 20 00 01 mov BYTE PTR [rip+0x200c79],0x1 # 601060 <v>
4003e7: c6 05 73 0c 20 00 00 mov BYTE PTR [rip+0x200c73],0x0 # 601061 <v+0x1>
4003ee: c6 05 e6 0c 20 00 01 mov BYTE PTR [rip+0x200ce6],0x1 # 6010db <v+0x7b>
4003f5: 0f b6 05 df 0c 20 00 movzx eax,BYTE PTR [rip+0x200cdf] # 6010db <v+0x7b>
4003fc: c3 ret
A disparut preambulul deoarece nu se declara nimic pe stiva. Registrul eax nu mai este redus la ultimii 4 biti, operatie care oricum nu era necesara deoarece doar ultimul bit era folosit. In rest, elementele tot ocupa un octet.
-Os
00000000004003e0 <main>:
4003e0: c6 05 79 0c 20 00 01 mov BYTE PTR [rip+0x200c79],0x1 # 601060 <v>
4003e7: c6 05 73 0c 20 00 00 mov BYTE PTR [rip+0x200c73],0x0 # 601061 <v+0x1>
4003ee: c6 05 e6 0c 20 00 01 mov BYTE PTR [rip+0x200ce6],0x1 # 6010db <v+0x7b>
4003f5: 0f b6 05 df 0c 20 00 movzx eax,BYTE PTR [rip+0x200cdf] # 6010db <v+0x7b>
4003fc: c3 ret
Ma asteptam ca macar aici sa cedeze timp pentru memorie si sa foloseasca instructiuni pe biti, dar nu e cazul. Codul rezultat e identic cu cel de la -O2.
Vector pe stiva
int main() {
volatile bool v[8 * 1024 * 1024];
v[0] = true;
v[1] = false;
v[123] = true;
return v[123];
}
Compilarea a fost facuta exact ca mai devreme:
$ gcc --version
gcc (Ubuntu 5.4.0-6ubuntu1~16.04.5) 5.4.0 20160609
$ gcc stiva.c -o stiva-neoptimizat
$ gcc stiva.c -O2 -o stiva-o2
$ gcc stiva.c -Os -o stiva-os
Deoarece dimensiunea stivei nu e specificata in headerele executabilului, marimea vectorului poate fi determinata prin analiza dinamica cu un debugger sau prin analiza statica a codului compilat.
Neoptimizat
0000000000400546 <main>:
400546: 55 push rbp
400547: 48 89 e5 mov rbp,rsp
40054a: 48 81 ec 10 00 80 00 sub rsp,0x800010
400551: 64 48 8b 04 25 28 00 mov rax,QWORD PTR fs:0x28
400558: 00 00
40055a: 48 89 45 f8 mov QWORD PTR [rbp-0x8],rax
40055e: 31 c0 xor eax,eax
400560: c6 85 f0 ff 7f ff 01 mov BYTE PTR [rbp-0x800010],0x1
400567: c6 85 f1 ff 7f ff 00 mov BYTE PTR [rbp-0x80000f],0x0
40056e: c6 85 6b 00 80 ff 01 mov BYTE PTR [rbp-0x7fff95],0x1
400575: 0f b6 85 6b 00 80 ff movzx eax,BYTE PTR [rbp-0x7fff95]
40057c: 0f b6 c0 movzx eax,al
40057f: 48 8b 55 f8 mov rdx,QWORD PTR [rbp-0x8]
400583: 64 48 33 14 25 28 00 xor rdx,QWORD PTR fs:0x28
40058a: 00 00
40058c: 74 05 je 400593 <main+0x4d>
40058e: e8 8d fe ff ff call 400420 <__stack_chk_fail [at] plt>
400593: c9 leave
400594: c3 ret
Un lucru nou fata de varianta cu vectorul global este aparitia detectarii de stack smashing. Dupa primele 3 instructiuni care constituie preambulul urmeaza 2 instructiuni care pun o valoare secreta imediat dupa sfarsitul vectorului. Registrul rax e folosit ca valoare intermediara, asa ca trebuie resetat la 0 cu xor eax,eax. La sfarsit se verifica daca valoarea secreta a ramas neschimbata. Daca nu mai e aceiasi se considera ca programul nu a functionat corect si se apeleaza __stack_chk_fail.
In rest, instructiunile de la 400560 la 40057c sunt foarte similare cu cele de la global-neoptimizat.
-O2
0000000000400450 <main>:
400450: 48 81 ec 18 00 80 00 sub rsp,0x800018
400457: 64 48 8b 04 25 28 00 mov rax,QWORD PTR fs:0x28
40045e: 00 00
400460: 48 89 84 24 08 00 80 mov QWORD PTR [rsp+0x800008],rax
400467: 00
400468: 31 c0 xor eax,eax
40046a: c6 04 24 01 mov BYTE PTR [rsp],0x1
40046e: c6 44 24 01 00 mov BYTE PTR [rsp+0x1],0x0
400473: c6 44 24 7b 01 mov BYTE PTR [rsp+0x7b],0x1
400478: 0f b6 44 24 7b movzx eax,BYTE PTR [rsp+0x7b]
40047d: 48 8b 94 24 08 00 80 mov rdx,QWORD PTR [rsp+0x800008]
400484: 00
400485: 64 48 33 14 25 28 00 xor rdx,QWORD PTR fs:0x28
40048c: 00 00
40048e: 75 08 jne 400498 <main+0x48>
400490: 48 81 c4 18 00 80 00 add rsp,0x800018
400497: c3 ret
400498: e8 83 ff ff ff call 400420 <__stack_chk_fail [at] plt>
Varianta aceasta foloseste un preambul dubios, ne mai salvand rbp si rsp. Stack smash detection arata la fel. Asemenea optimizarii la varianta globala, a disparut a doua instructiune movzx.
-Os
0000000000400450 <main>:
400450: 48 81 ec 18 00 80 00 sub rsp,0x800018
400457: 64 48 8b 04 25 28 00 mov rax,QWORD PTR fs:0x28
40045e: 00 00
400460: 48 89 84 24 08 00 80 mov QWORD PTR [rsp+0x800008],rax
400467: 00
400468: 31 c0 xor eax,eax
40046a: c6 44 24 08 01 mov BYTE PTR [rsp+0x8],0x1
40046f: c6 44 24 09 00 mov BYTE PTR [rsp+0x9],0x0
400474: c6 84 24 83 00 00 00 mov BYTE PTR [rsp+0x83],0x1
40047b: 01
40047c: 0f b6 84 24 83 00 00 movzx eax,BYTE PTR [rsp+0x83]
400483: 00
400484: 48 8b 94 24 08 00 80 mov rdx,QWORD PTR [rsp+0x800008]
40048b: 00
40048c: 64 48 33 14 25 28 00 xor rdx,QWORD PTR fs:0x28
400493: 00 00
400495: 74 05 je 40049c <main+0x4c>
400497: e8 84 ff ff ff call 400420 <__stack_chk_fail [at] plt>
40049c: 48 81 c4 18 00 80 00 add rsp,0x800018
4004a3: c3 ret
Codul arata foarte similar cu cel de la -O2, singura diferenta fiind ca vectorul nu e in acelasi loc relativ cu rsp (banuiesc ca pentru aliniere).
Analiza dinamica
Deoarece rezultatele celor 3 executabile sunt similare, voi demonstra doar pe cel neoptimizat.
Initial deschid programul cu gdb, afisez instructiunile din main si pun un breakpoint undeva in mijlocul functiei.
$ gdb stiva-neoptimizat
(gdb) set disassembly-flavor intel
(gdb) disassemble main
Dump of assembler code for function main:
0x0000000000400546 <+0>: push rbp
0x0000000000400547 <+1>: mov rbp,rsp
0x000000000040054a <+4>: sub rsp,0x800010
0x0000000000400551 <+11>: mov rax,QWORD PTR fs:0x28
0x000000000040055a <+20>: mov QWORD PTR [rbp-0x8],rax
0x000000000040055e <+24>: xor eax,eax
0x0000000000400560 <+26>: mov BYTE PTR [rbp-0x800010],0x1
0x0000000000400567 <+33>: mov BYTE PTR [rbp-0x80000f],0x0
0x000000000040056e <+40>: mov BYTE PTR [rbp-0x7fff95],0x1
0x0000000000400575 <+47>: movzx eax,BYTE PTR [rbp-0x7fff95]
0x000000000040057c <+54>: movzx eax,al
0x000000000040057f <+57>: mov rdx,QWORD PTR [rbp-0x8]
0x0000000000400583 <+61>: xor rdx,QWORD PTR fs:0x28
0x000000000040058c <+70>: je 0x400593 <main+77>
0x000000000040058e <+72>: call 0x400420 <__stack_chk_fail [at] plt>
0x0000000000400593 <+77>: leave
0x0000000000400594 <+78>: ret
End of assembler dump.
(gdb) break *main+26
Breakpoint 1 at 0x400560
(gdb) run
Starting program: /home/trupples/test-bool/stiva-neoptimizat
Breakpoint 1, 0x0000000000400560 in main ()
(gdb) p/ux $ebp
$6 = 0xffffe4c0
(gdb) p/ux $esp
$7 = 0xff7fe4b0
Registrii ebp si esp delimiteaza zona functiei curente de pe stiva. Diferenta dintre ei e de 0xffffe4c0 - 0xff7fe4b0 = 0x800010 = 8MiB si un pic.
std::vector<bool>
Documentatia c++ mentioneaza ca depinzand de implementarea bibliotecii, std::vector<bool> poate fi optimizat pentru spatiu. Deoarece containerele stdlib sunt declarate in heap, nu conteaza daca referinta la vector e pe stiva sau globala, asa ca am compilat un singur program. Functia malloc_stats va afisa informatii despre heap, inclusiv cata memorie a fost alocata. E posibil ca vectorul sa nu fie singurul lucru de pe heap, dar cu siguranta va ocupa majoritatea spatiului, alte obiecte fiind neglijabile.
#include<vector>
#include<malloc.h>
#include<stdio.h>
int main() {
fprintf(stderr, "Inainte de declararea vectorului:\n");
malloc_stats();
std::vector<bool> v(8*1024*1024);
v[0] = true;
v[1] = false;
v[123] = true;
fprintf(stderr, "\n\nDupa declararea vectorului:\n");
malloc_stats();
return v[123];
}
$ g++ stdvector.cpp -o stdvector
$ ./stdvector
Inainte de declararea vectorului:
Arena 0:
system bytes = 204800
in use bytes = 72720
Total (incl. mmap):
system bytes = 204800
in use bytes = 72720
max mmap regions = 0
max mmap bytes = 0
Dupa declararea vectorului:
Arena 0:
system bytes = 204800
in use bytes = 72720
Total (incl. mmap):
system bytes = 1257472
in use bytes = 1125392
max mmap regions = 1
max mmap bytes = 1052672
E de asteptat ca dimensiunea vectorului sa fie de 8 ori mai mica fata de ce am vazut anterior, deci in jur de 1024 * 1024 = 1048576 octeti. Se observa faptul ca intre primul malloc_stats() si al doilea declararea vectorului a alocat 1125392 - 72720 = 1052672 octeti, deci intr-adevar std::vector<bool> foloseste memoria eficient.
std::bitset
Bitset trebuie sa fie eficient din punctul de vedere al memoriei deoarece acesta este principalul lui scop. In cazul acesta nu se foloseste alocare dinamica, bitsetul rezervandu-si loc pe stiva. Dimensiunea bitsetului se poate calcula in ambele moduri folosite la sectiunea cu un vector simplu de bool-uri pe stiva.
#include<bitset>
int main() {
std::bitset<8*1024*1024> v;
v[0] = true;
v[1] = false;
v[123] = true;
return v[123];
}
$ g++ bitset.cpp -o bitset
$ gdb ./bitset
(gdb) break *main+27
Breakpoint 1 at 0x400721
(gdb) run
Starting program: /home/trupples/test-bool/bitset
Breakpoint 1, 0x0000000000400721 in main ()
(gdb) p/ux $esp
$1 = 0xffefe4a0
(gdb) p/ux $ebp
$2 = 0xffffe4d0
Am folosit analiza dinamica, punand un breakpoint dupa preambul, astfel incat stiva sa fie pregatita intre adresa ebp si esp. Diferenta intre cei doi registri arata ca bitset-ul ocupa aproximativ 1MiB, dupa cum era de asteptat.
Concluzie
In concluzie, compilatorul gcc nu va optimiza pentru spatiu un tablou simplu de bool-uri, nici cu nivel de optimizare -O2, insa daca e nevoie de un tablou de bool-uri care ar depasi in mod normal limita de memorie exista doua alternative:
std::bitset, in cazul in care e destul spatiu pe stiva
std::vector<bool>, in cazul in care trebuie folosit heap-ul.
Merita mentionat faptul ca std::bitset poate fi mai incet decat std::vector<bool>: https://stackoverflow.com/a/4159130