std::vector<bool> perormance penalty

I have created a test for various vector<T> types (T in int, bool, char, int_fast8_t, uint_fast8_t).

Summary

I have found that a vector of int is 4 times faster than bool, but char (and *_fast8_t types) can be even faster: 20 times when writing and 50 times when reading

Vector size is 400 million (8 long pattern used 50 million times). First we populate a vector (write), then ve copy the vector to another (read+write). We approximate the read by subtracting the two (read = read+write - write).

type	write [ms]	read+write [ms]	read [ms]
int	92	129	37
bool	419	892	473
char	23	32	9
int_fast8_t	23	32	9
uint_fast8_t	23	31	8

• CPU: AMD EPYC 7B12
• OS: Linux version 6.6.15 amd64
• Compiler: gcc version 13.2.0
• Compliation: g++ -std=c++17 -O3 -W -Wall -Wextra -pedantic -flto vector_bool.cpp -o vector_bool
• Source: pastebin.com

Background

In the standard library of C++ vector<bool> is specialized for space. This is a very old legacy from a time where generally speaking RAMs were very small. In this container the bool type ‐ which uses 1 or even more bytes to store a true/false ‐ is not used for storage: rather a larger integer type is used as underlying array element to store multiple bits. In this case writing a bit requires reading the corresponding integer, altering it with bitwise operations, then writing it back to the container.

Search the Internet if you would like to find other disadvantages of this specialization. This post is only about the magnitude of the performance penalty this decision have caused.

Recommended workarounds

Some alternatives

• Use *_fast8_t as T.
• Use boost::container::vector<bool> instead.
• Create a class Bool that stores a bool and use it as T. This seems to be much more like a school/learning project rather than a production solution. But who knows: there might be circumstances where this is the way.

Kormos Anett írása Andy Vajna halálának online fogadtatásáról

Idézet:

Egy barátom azt tanácsolta, ne írjak erről a témáról, mert túlságosan vékony jég. Nekem pedig az jutott eszembe magamba fojtott riposztként, hogy ha vékony jég azzal kapcsolatban véleményt nyilvánítani: hogyan kéne reagálnunk arra, ha valaki meghal, akkor üsse bassza, szakadjon be alattam, mert ez a jég számomra nem megfelelő élőhely.

Ma reggel meghalt Andy Vajna.

Az internetet pedig rögtön elárasztották a haláláról, és a felesége anyagi fellendüléséről szóló mémek, amelyek belőlem valahogy nem tudták előcsalni az önfeledt kacagás ingerét.

Nem Andy Vajna vagy az özvegye miatt, nem a gyász vagy a mélységes együttérzés miatt.

Hanem azért, mert a derű helyett riadalom költözött belém. Riaszt, hogy mennyire elfogadottá, sőt lájkolandóvá vált az, hogy sokan egy jó poén kedvéért könnyedén levetik magukról emberarcukat …márha egyáltalán szokták még hordani.

Ti is tudjátok, messze vagyok a tapintatoskodástól, nem jellemző, hogy eltartott kisujjal fogom meg a poént. Azt vallom, bármiből lehet viccet csinálni: buzikból, zsidókból, cigányokból, nőkből, férfiakból, anyósokból, apósokból, gyerekekből és… igen, akár a halálból is. Feltéve, hogy képesek vagyunk olyan szellemesen kiforgatni azt a sarkából, hogy felülírjuk magának a HALÁL tényének a drámáját. Ha ezt a lécet nem sikerül megugrani, kár is neki futni, biztos bukás a vége.

Ugyanakkor azt is gondolom, hogy nyitott koporsó felett szotyihéjat köpködve az elhúnyton élcelődni, minimum nem elegáns, de inkább állati nagy parasztság. A szellemeskedésre meg kell várni a megfelelő időt, alkalmat, formát, helyet és közönséget. Ez most nem sikerült.

Itt azonban még kerestem a mentségeket: hogy a virtuális világ már teljesen leradírozta a valóság kontúrját, a mémgyárosok pedig nyilván röpke poéngyártási kényszerük hatása alá kerülve felejtették el, hogy meghalt valaki. De hát tudjuk: a virtuális világ vérszomjas csecsemő, a bölcsőjét pedig mi magunk ringatjuk.

Ezzel a keserű summázattal túl is libbentem volna a témán, amikor kiderült, hogy nagyobb a baj. Andy Vajna halálának napján rengetegen érezték úgy, hogy itt az idő, hogy indulataik és gyűlöletük rövidláncon tartott vérebeit végre ráuszítsák Vajna Tímeára.

És ez sokkolt igazán.

Mert ennek a virtuális vandalizmusnak én nem akarom kutatni az okait, és nem akarom felmenteni az elkövetőit.

Mert ettől valóban belém költözött a szomorúság és a részvét.

A gyász.

Csak az én gyászom nem Andy Vajnának szól, hanem azoknak, akikből az emberség úgy halt ki, hogy nekik talán fel sem tűnt.

Hogy miért osztom meg más posztját, mint másolatot?

Magyar Hang: A gyűlölködés ellen szólalt fel Kormos Anett, a Facebook törölte a posztját

undefined reference to `vtable for C'

This post intends to be a quick help for anyone who struggles with this error. This error came to me when I tried to compile a larger source code which was already compiling on Windows. It took me more than an hour to figure it out. Here is what I've found, from solution to details.

Possible reasons

• C.cpp was not compiled.
• C.o was not added to inputs.
• There is a virtual method in the C class that is not defined (body of method not present).

Minimalistic reproduction

vtrep.cpp

class C
{
public:
  virtual ~C()
  { }
public:
  virtual int id();
};

int main()
{
  C c;
  return 0;
}

Compilation

$ g++ -c vtrep.cpp -o vtrep.o
$ g++ -o vtrep vtrep.o
vtrep.o: In function `C::~C()':
vtrep.cpp:(.text._ZN1CD2Ev[_ZN1CD5Ev]+0x13): undefined reference to `vtable for C'
vtrep.o: In function `C::C()':
vtrep.cpp:(.text._ZN1CC2Ev[_ZN1CC5Ev]+0xf): undefined reference to `vtable for C'
collect2: error: ld returned 1 exit status

Note that the error messages tell nothing about the id() method.

Java ArrayList resize

Once I had an array:

    static final Apple[] apples = new Apple[4];

Then circumstances changed so, Apple became generic, so my code changed to

    static final Apple<T>[] apples = new Apple<T>[4];

which produced compile errors as Cannot create a generic array of Apple<T>, so I was forced to switch to ArrayList like:

    static final ArrayList<Apple<T>> apples = new ArrayList<>(4);
    // 4 means capacity here not size.

I have some code in a static initializer block that fills apples using calculated indexes, so it is not a sequence of add(e) calls and it is not desirable for me to rearrange it that way.

I would like to resize the array to have 4 elements, all of them null. A manual way to achieve it is this:

    static {
      for(int i=0; i<4; ++i)
        apples.add(null);
      // ORIGINAL index-magic based code here.
    }

Which is super effective but not so elegant.

Unfortunately all my search efforts on the Internet were derailed because of posts that suggest ensuring capacity and then adding elements with add(e). None of them addressed the original question of resizing an ArrayList using a filler element. The OPs of those questions were satisfied with those answers, but I really would like to have the answer to the original question.

Until then this will go:

  /**
   * Resizes and returns an {@code ArrayList}.
   * Capacity is not freed upon shrinking. At most one allocation happens.
   * 
   * @param list
   *          Input to be altered, return value.
   * @param size
   *          Desired size
   * @param filler
   *          Additional elements - if any - will be set to this.
   * @return Altered list.
   */
  public static <T> ArrayList<T> resize( ArrayList<T> list, int size, T filler ) {
    for( int i = list.size(); i > size; --i )
      list.remove( i - 1 );
    list.ensureCapacity( size );
    for( int i = list.size(); i < size; ++i )
      list.add( filler );
    return list;
  }

  /**
   * Resizes and returns an {@code ArrayList}.
   * Capacity is not freed upon shrinking. At most one allocation happens.
   * Additional elements - if any - will be set to null.
   * 
   * @param list
   *          Input to be altered, return value.
   * @param size
   *          Desired size
   * @return Altered list.
   */
  public static <T> ArrayList<T> resize( ArrayList<T> list, int size ) {
    return resize( list, size, null );
  }

It is slower than the original for based ad-hoc solution, but it is quicker to read at the place of usage, and resizing of arrays do not (should not) happen that often, as I would seriously doubt the general quality of a code where an array resizing takes place at a hot-spot.

Senior developer / Tapasztalt fejlesztő

Senior Developer explaining how to use his library

A tapasztalt fejlesztő elmeséli, hogy hogyan kell a programját használni

↠ @ DevOps reactions

Prizma napló #2

A két szemem fókuszpontjainak távolsága kb ötöde szemüvegben, mint szemüveg nélkül. A mérési nehézségekhez képest egész jóra sikerültek a lencsék.

A kilincset egyszer-egyszer még mindig eltévesztem, de már csak pár centivel.

Az autók mozgásával kapcsolatban nincsen a korábban tapasztalt bizonytalanság (amit rögtön nem is írtam le).

A szivárvány effektet már csak nagyon ritka fényviszonyok mellett látom. Cserébe minden egy picit olyan, mintha finoman meg lenne rajzolva a kontúrja.

Eddig még egyszer sem sikerült elfelejtenem, hogy rajtam van, azaz még nem szoktam meg.

Prizma napló #1

Minden kontúr szivárványos. A szemész hölgy ezen nem lepődött meg. Azt mondta, hogy meg fogom tanulni a szivárvány nem látását.

Vélt vagy valós térélmény javulás

Emlékezetből pontosan fogom a kilincset, látás alapján 10 centit tévedtem elsőre.

Bizonytalan voltam elsőre egy-két tárgy darabszámát illetően.

A szemüveg felvétele és levétele után nem tapasztalom a megjósolt lehetséges tüneteket (több perces átszokási idő, kettős látás, bizonytalan távolság érzékelés)

Szemüveg nélkül a bal szemem a domináns, szemüvegben a jobb.

Prizma napló #0

Körülbelül egy hónapja volt a melóhelyemen egy szemészeti szűrés, amelyen kiderült (csodák csodája), hogy szemtengely ferdülésem van. Nem volt meg a helyszínen minden műszerük ami a paraméterek pontos kiméréséhez szükségesek lettek volna, ezért elhívtak a székesfehérvári bázisukra további vizsgálatokra, amelyre el is mentem.

A színpad úgy néz ki, hogy egy szemésztáblára felfestenek egy szálkeresztet úgy, hogy a függőleges és a vízszintes szár más-más polarizációval látszott, nekem pedig egy olyan szemüveget (szemészeti lencseállványt) adtak amely elé polár-szűrőket helyeztek. Így a bal szememmel csak a függőleges szárat láttam a jobb szememmel csak a vízszinteset.

Ilyenkor jött a belépő mutatvány. Képes vagyok-e az agyammal mindkét szem képét egyszerre látni. Némi játék után a mutatvány sikerült. A körülbelül 5 méterre lévő falon egymástól fél méter távolságra megláttam az ábra két komponensét. Függőleges irányban is volt némi elcsúszás, az eltérés nagyja vízszintesen volt.

Ekkor következett a prizma típusú lencsék cserélgetése, amelyek a szemeimből kiinduló nézést megpróbálták párhuzamosra téríteni (értjük). A függőleges irányú igazítás tökéletessé vált, a vízszintes nem nagyon akart összejönni. Az agyam elutasította azt az ötletet, hogy a bal és a jobb szemem által látott tárgy megegyezik. Amikor a két komponensnek elvileg egymáson kellett volna lennie, akkor a vízszintes komponens el kezdett gyors tempóban ugrálni a függőleges komponens két oldala között.

Az így kimért közelítő értékeket elfogadtuk és felvéstük az adatlapra. Ez alapján elkészíthették számomra azt a szemüveget, amihez ha jól hozzászokom, akkor újabb mérések következhetnek. Ha az agyam tényleg megtanulja a normál emberek látását és sikerül pontosan kimérni a szemtengely ferdülést, akkor az egy műtéttel drasztikusan csökkenthető. Szerencsés esetben meg is szűnhet.

A szemüveget ma vettem át és el is kezdtem hordani. A viccesebb vizuális élményeimet pedig meg is fogom osztani itt a blogon. Meg amúgy is, diagnosztikai szempontból esetleg hasznos lehet, ha naplózva vannak.