Ydeevnesammenligning af boolean[] vs BitSet
1. Oversigt
I denne artikel skal vi sammenligne BitSet s og boolesk[] med hensyn til ydeevne i forskellige scenarier.
Vi bruger normalt udtrykket performance meget løst med forskellige betydninger i tankerne. Derfor vil vi starte med at se på forskellige definitioner af begrebet "performance".
Derefter vil vi bruge to forskellige præstationsmålinger til benchmarks:hukommelsesfodaftryk og gennemløb. For at benchmarke gennemløbet, vil vi sammenligne nogle få almindelige operationer på bitvektorer.
2. Definition af ydeevne
Ydeevne er en meget generel betegnelse, der refererer til en lang række "performance"-relaterede begreber!
Nogle gange bruger vi dette udtryk til at tale om opstartshastigheden for en bestemt applikation; det vil sige, hvor lang tid det tager, applikationen er i stand til at svare på dens første anmodning.
Ud over opstartshastighed kan vi tænke på hukommelsesbrug, når vi taler om ydeevne . Så hukommelsesfodaftrykket er et andet aspekt af dette udtryk.
Det er muligt at fortolke "ydelsen" som, hvor "hurtigt" vores kode fungerer . Så latensen er endnu et ydeevneaspekt.
For nogle applikationer er det meget vigtigt at kende systemets kapacitet i form af operationer pr. sekund. Så gennemløbet kan være et andet aspekt af ydeevnen .
Nogle applikationer kan kun fungere på deres højeste præstationsniveau efter at have svaret på nogle få anmodninger og blevet "varmet op" teknisk set. Derfor t tid til maksimal ydeevne er et andet aspekt .
Listen over mulige definitioner bliver ved og ved! Igennem denne artikel vil vi dog kun fokusere på to præstationsmålinger:m hukommelsesfodaftryk og gennemløb .
3. Memory Footprint
Selvom vi måske forventer booleans at forbruge kun en smule, hver boolsk på et boolsk[] bruger en byte hukommelse . Dette er primært for at undgå ordrivning og tilgængelighedsproblemer. Derfor, hvis vi har brug for en vektor af bit, boolean[] vil have et ret betydeligt hukommelsesfodaftryk.
For at gøre tingene mere konkrete kan vi bruge Java Object Layout (JOL) til at inspicere hukommelseslayoutet for en boolesk[] med f.eks. 10.000 elementer:
boolean[] ba = new boolean[10_000];
System.out.println(ClassLayout.parseInstance(ba).toPrintable());Dette vil udskrive hukommelseslayoutet:
[Z object internals:
OFFSET SIZE TYPE DESCRIPTION VALUE
0 4 (object header) 01 00 00 00 (1)
4 4 (object header) 00 00 00 00 (0)
8 4 (object header) 05 00 00 f8 (-134217723)
12 4 (object header) 10 27 00 00 (10000)
16 10000 boolean [Z. N/A
Instance size: 10016 bytesSom vist ovenfor er denne boolean[] bruger omkring 10 KB hukommelse.
På den anden side BitSet bruger en kombination af primitive datatyper (specifikt lange ) og bitvise operationer for at opnå en bit pr. flag footprint . Så et BitSet med 10.000 bit vil forbruge meget mindre hukommelse sammenlignet med en boolesk[] med samme størrelse:
BitSet bitSet = new BitSet(10_000);
System.out.println(GraphLayout.parseInstance(bitSet).toPrintable());På samme måde vil dette udskrive hukommelseslayoutet for BitSet :
[email protected] object externals:
ADDRESS SIZE TYPE PATH
76beb8190 24 java.util.BitSet
76beb81a8 1272 [J .words Som forventet er BitSet med det samme antal bit bruger omkring 1 KB, hvilket er langt mindre end boolsk[] .
Vi kan også sammenligne hukommelsesfodaftrykket for de forskellige antal bits:
Path path = Paths.get("footprint.csv");
try (BufferedWriter stream = Files.newBufferedWriter(path, StandardOpenOption.CREATE)) {
stream.write("bits,bool,bitset\n");
for (int i = 0; i <= 10_000_000; i += 500) {
System.out.println("Number of bits => " + i);
boolean[] ba = new boolean[i];
BitSet bitSet = new BitSet(i);
long baSize = ClassLayout.parseInstance(ba).instanceSize();
long bitSetSize = GraphLayout.parseInstance(bitSet).totalSize();
stream.write((i + "," + baSize + "," + bitSetSize + "\n"));
if (i % 10_000 == 0) {
stream.flush();
}
}
}Ovenstående kode vil beregne objektstørrelsen for begge typer bit-vektorer med forskellige længder. Derefter skriver den og fjerner størrelsessammenligningerne til en CSV-fil.
Hvis vi nu plotter denne CSV-fil, vil vi se, at den absolutte forskel i hukommelsesfodaftryk vokser med antallet af bits :
Det vigtigste her er BitSet slår boolsk[] med hensyn til hukommelsesfodaftrykket, bortset fra et minimalt antal bits.
4. Gennemløb
For at sammenligne gennemløbet af BitSet og boolesk[] med hinanden vil vi udføre tre benchmarks baseret på tre forskellige og alligevel dagligdags operationer på bit-vektorer:
- Hent værdien af en bestemt bit
- Indstilling eller sletning af værdien af en bestemt bit
- Tæller antallet af sæt bits
Dette er den almindelige opsætning, vi skal bruge til sammenligning af gennemstrømning af bitvektorer med forskellige længder:
@State(Scope.Benchmark)
@BenchmarkMode(Mode.Throughput)
public class VectorOfBitsBenchmark {
private boolean[] array;
private BitSet bitSet;
@Param({"100", "1000", "5000", "50000", "100000", "1000000", "2000000", "3000000",
"5000000", "7000000", "10000000", "20000000", "30000000", "50000000", "70000000", "1000000000"})
public int size;
@Setup(Level.Trial)
public void setUp() {
array = new boolean[size];
for (int i = 0; i < array.length; i++) {
array[i] = ThreadLocalRandom.current().nextBoolean();
}
bitSet = new BitSet(size);
for (int i = 0; i < size; i++) {
bitSet.set(i, ThreadLocalRandom.current().nextBoolean());
}
}
// omitted benchmarks
}Som vist ovenfor opretter vi boolesk[] s og BitSet s med længder i intervallet 100-1.000.000.000. Efter at have indstillet et par bits i opsætningsprocessen, udfører vi også forskellige handlinger på både boolesk[] og BitSet s.
4.1. Få en smule
Ved første øjekast er den direkte hukommelsesadgang i boolesk[] synes at være mere effektivt end at udføre to bitvise operationer pr. get i BitSet s (venstre-skift plus et og operation). På den anden side er hukommelseskompaktheden af BitSet s kan tillade dem at passe flere værdier inde i en cache-linje.
Lad os se, hvem der vinder! Her er de benchmarks, som JMH vil køre med en anden værdi af størrelsen angiv hver gang:
@Benchmark
public boolean getBoolArray() {
return array[ThreadLocalRandom.current().nextInt(size)];
}
@Benchmark
public boolean getBitSet() {
return bitSet.get(ThreadLocalRandom.current().nextInt(size));
}4.2. Få en smule:Gennemløb
Vi skal køre benchmarks ved hjælp af følgende kommando:
$ java -jar jmh-1.0-SNAPSHOT.jar -f2 -t4 -prof perfnorm -rff get.csv getBitSet getBoolArrayDette vil køre de get-relaterede benchmarks ved hjælp af fire tråde og to gafler, profilere deres eksekveringsstatistik ved hjælp af perf-værktøjet på Linux og udlæse resultatet i bench- get.csv fil . “-prof-perfnormen” vil profilere benchmark ved hjælp af perf-værktøjet på Linux og normalisere ydeevnetællerne baseret på antallet af operationer.
Da kommandoresultatet er så omfattende, vil vi kun plotte dem her. Før det, lad os se den grundlæggende struktur for hvert benchmarkresultat:
"Benchmark","Mode","Threads","Samples","Score","Score Error (99.9%)","Unit","Param: size"
"getBitSet","thrpt",4,40,184790139.562014,2667066.521846,"ops/s",100
"getBitSet:L1-dcache-load-misses","thrpt",4,2,0.002467,NaN,"#/op",100
"getBitSet:L1-dcache-loads","thrpt",4,2,19.050243,NaN,"#/op",100
"getBitSet:L1-dcache-stores","thrpt",4,2,6.042285,NaN,"#/op",100
"getBitSet:L1-icache-load-misses","thrpt",4,2,0.002206,NaN,"#/op",100
"getBitSet:branch-misses","thrpt",4,2,0.000451,NaN,"#/op",100
"getBitSet:branches","thrpt",4,2,12.985709,NaN,"#/op",100
"getBitSet:dTLB-load-misses","thrpt",4,2,0.000194,NaN,"#/op",100
"getBitSet:dTLB-loads","thrpt",4,2,19.132320,NaN,"#/op",100
"getBitSet:dTLB-store-misses","thrpt",4,2,0.000034,NaN,"#/op",100
"getBitSet:dTLB-stores","thrpt",4,2,6.035930,NaN,"#/op",100
"getBitSet:iTLB-load-misses","thrpt",4,2,0.000246,NaN,"#/op",100
"getBitSet:iTLB-loads","thrpt",4,2,0.000417,NaN,"#/op",100
"getBitSet:instructions","thrpt",4,2,90.781944,NaN,"#/op",100Som vist ovenfor er resultatet en kommasepareret liste over felter, der hver repræsenterer en metrik. For eksempel “thrpt” repræsenterer gennemløbet, “L1-dcache-load-misses” er antallet af cache-misser for niveau 1-datacachen, “L1-icache-load-misses” er antallet af cache-misser for niveau 1-instruktionscachen og “instruktioner” repræsenterer antallet af CPU-instruktioner for hvert benchmark. Det sidste felt repræsenterer også antallet af bit, og det første repræsenterer benchmarkmetodens navn.
Sådan ser benchmarkresultaterne ud for gennemløb på en typisk digital havdråbe med en 4-kernet Intel(R) Xeon(R) CPU 2,20 GHz:
Som vist ovenfor, det boolske[] har en bedre gennemstrømning på mindre størrelser. Når antallet af bit stiger, BitSet overgår boolesk[] med hensyn til gennemstrømning . For at være mere specifik, efter 100.000 bit, er BitSet viser overlegen ydeevne.
4.3. Få lidt:Instruktioner pr. betjening
Som vi forventede, get-operationen på en boolesk[] har færre instruktioner pr. operation :
4.4. Få en smule:Datacache mangler
Lad os nu se, hvordan datacache-misser leder efter disse bit-vektorer:
Som vist ovenfor mangler antallet af datacache for boolean[] stiger, efterhånden som antallet af bit stiger.
Så cache-misser er meget dyrere end at udføre flere instruktioner her . Derfor BitSet API overgår boolean[] i dette scenarie det meste af tiden.
4.5. Indstilling af en smule
For at sammenligne gennemstrømningen af indstillede operationer vil vi bruge disse benchmarks:
@Benchmark
public void setBoolArray() {
int index = ThreadLocalRandom.current().nextInt(size);
array[index] = true;
}
@Benchmark
public void setBitSet() {
int index = ThreadLocalRandom.current().nextInt(size);
bitSet.set(index);
}Grundlæggende vælger vi et tilfældigt bitindeks og indstiller det til sandt . På samme måde kan vi køre disse benchmarks ved hjælp af følgende kommando:
$ java -jar jmh-1.0-SNAPSHOT.jar -f2 -t4 -prof perfnorm -rff set.csv setBitSet setBoolArrayLad os se, hvordan benchmark-resultaterne ser ud for disse operationer med hensyn til gennemløb:
Denne gang den boolske[] udkonkurrerer BitSet det meste af tiden bortset fra de helt store størrelser . Da vi kan have flere BitSet bits inde i en cachelinje, kan effekten af cache-misser og falsk deling være mere signifikant i BitSet forekomster.
Her er datacache-miss-sammenligningen:
Som vist ovenfor mangler datacachen for boolean[] er ret lav for et lavt til et moderat antal bits. Igen, når antallet af bit stiger, boolean[] støder på flere cache-misser.
På samme måde er instruktionerne pr. handling for boolean[] er rimeligt mindre end BitSet :
4.6. Kardinalitet
En af de andre almindelige operationer i sådanne bit-vektorer er at tælle antallet af sæt-bits. Denne gang skal vi køre disse benchmarks:
@Benchmark
public int cardinalityBoolArray() {
int sum = 0;
for (boolean b : array) {
if (b) sum++;
}
return sum;
}
@Benchmark
public int cardinalityBitSet() {
return bitSet.cardinality();
}Igen kan vi køre disse benchmarks med følgende kommando:
$ java -jar jmh-1.0-SNAPSHOT.jar -f2 -t4 -prof perfnorm -rff cardinal.csv cardinalityBitSet cardinalityBoolArraySådan ser gennemløbet ud for disse benchmarks:
Med hensyn til kardinalitetsgennemstrømning er BitSet API overgår boolean[] næsten hele tiden, fordi den har meget færre gentagelser . For at være mere specifik, BitSet skal kun gentage sin interne lange[] som har meget mindre antal elementer sammenlignet med den tilsvarende boolean[] .
Også på grund af denne linje og tilfældig fordeling af sæt-bits i vores bit-vektorer:
if (b) {
sum++;
}Omkostningerne ved fejlforudsigelse af brancher kan også være afgørende:
Som vist ovenfor, når antallet af bit stiger, vil antallet af fejlforudsigelser for boolsk[] går markant op.
5. Konklusion
I denne artikel sammenlignede vi gennemløbet af BitSet og boolesk[] i form af tre almindelige operationer:få en smule, sætte en bit og beregne kardinalitet. Ud over gennemstrømningen så vi, at BitSet bruger meget mindre hukommelse sammenlignet med en boolesk[] med samme størrelse.
For at opsummere, i enkelt-bit læsetunge scenarier, boolsk[] udkonkurrerer BitSet i mindre størrelser. Men når antallet af bit stiger, vil BitSet har overlegen gennemstrømning.
I enkelt-bit skrivetunge scenarier er boolsk[] desuden udviser en overlegen gennemstrømning næsten hele tiden bortset fra et meget stort antal bits. I batchlæse scenarierne er også BitSet API dominerer fuldstændigt boolean[] tilgang.
Vi brugte JMH-perf-integrationen til at fange CPU-målinger på lavt niveau, såsom L1 Data Cache Misses eller Missed Branch Predictions. Fra Linux 2.6.31 er perf standard Linux-profiler, der er i stand til at afsløre nyttige Performance Monitoring Counters eller PMC'er. Det er også muligt at bruge dette værktøj separat. For at se nogle eksempler på denne selvstændige brug, anbefales det stærkt at læse Branden Gregs blog.
Som sædvanlig er alle eksemplerne tilgængelige på GitHub. Desuden er CSV-resultaterne for alle udførte benchmarks også tilgængelige på GitHub.
