Colors Game Redux

Two days ago I posted a simple implementation of a game of colors. Though it was intended only as an exercise, someone has criticizes the use of an int** to hold the grid information, mainly for two reasons:

  • the footprint on 64-bit platforms can get nasty
  • the explicitly allocated memory, instead of using a std::vector

So this is the code:

Let’s see how much memory it takes. The total size should be:

On 32-bit platforms, the size of a pointer is the same with the size of int and is 4 bytes. For the maximum size allowed for my grid, which is 50, the total size in bytes for the grid is: 4 + 4*50 + 50*50*4 = 10204.

On 64-bit platforms, the size of a pointer is 8 bytes, but the size of int is still 4 bytes. So for a grid with 50 rows and columns it needs: 8 + 8*50 + 50*50*4 = 10408 bytes. That’s a 2% increase of required memory.

The memory footprint was the last thing I had in mind when I wrote this simple exercise. Well, of course there is a way to require only 4 more bytes on 64-bit platforms. And that is using an int* allocating m_nSize*m_nSize elements.

With this implementation, when you need to access the element at row i and column j, you have to use m_pCells[i * m_nSize + j].

As for the second argument, that explicitly using operator new[] to allocate memory instead of using a vector of vectors, well, what could I say? Sure, why not. Different people use different programming styles. As long as all implementation are correct and achieve the same goal with similar performance, I guess everyone is entitle to code as he/she wants. But if we go back to the memory footprint, I would also guess that the use of vectors would take more memory than pointers to int, because the size of a vector is several times the size of a pointer. But I wouldn’t say that’s an important issue here.

Anyway, these arguments remember me the joke (or maybe it’s serious) about the rules of optimization:

  1. Don’t optimize.
  2. Don’t optimize yet (for experts only).

(Of course there are super experts that can ignore these rules.)

8 Replies to “Colors Game Redux”

  1. Permite-mi te rog sa repet partea esentiala a criticii:

    “da’ chiar imi scapa de ce ai scrie atita cod in plus, ca la sfirsit sa mearga si prost”.

    Cu alte cuvinte:
    – merge mai prost din cauza de alocari in plus si pointer chasing
    – e mai mult cod de scris (for-ul ala care aloca array-urile plus for-ul corespunzator din Destroy())
    – e “bad style” ca sa zic asa
    – nu obtii nimic

    Chiar am vrut sa mentionez ca sper sa nu vina vreun destept cu zicatori despre optimizarea prematura, da’ am crezut ca se intelege din “acum nu ca in cazul de fata ar conta”. Aici nu e vorba de optimizari. E vorba sa nu faci string-uri goale cu sprintf(a, “”) in loc de a[0] = 0, daca ma intelegi. E o chestie de igiena.

  2. Pai alocari interne fac si toate containerele pe care le-as folosi in loc de new[]. Asa ca nu stiu exact ce ar merte mai prost, dar as fi curios sa aflu. Faptul ca e “bad style” cred ca e discutabil. Nu vad de ce mi-ar fi frica sa folosesc new[], mai ales ca in cazul de fata nu folosesc prea multe facilitati din containere ca vector. Ca nu obtin nimic, eventual nu obtin nimic in plus. Da, asa e, nu obtin nimic in plus, cu un container din STL as fi avut diferse functionalitati la dispozitie. Si da, sunt de acord cu tine, in general e bine sa folosesti containerele standard, dar asta nu inseamna ca trebuie sa ne punem ochelarii de cal in privinta asta. In rest, hai sa fim seriosi, critica ta e doar de dragul criticii.

  3. Tot nu ne intelegem. Eu n-am suflat nici un cuvintel despre containere standard (am zis “vectori” la un moment dat, dar ma refeream la array-uri unidimensionale, nu la std::vector). Eu am comparat asta:

    int** cells = new int*[size];
    for(int i = 0; i < size; ++i)
    cells[i] = new int[size];
    // …
    for(int i = 0; i < size; ++i)
    delete[] cells[i];
    delete[] cells;

    cu asta:

    int* cells = new int[size*size];
    // …
    delete[] cells;

    O alocare vs. size+1 alocari, adica "alocari in plus". Mai mult cod, mai incet, nici o diferenta de lizibilitate, 0 avantaje – adica definitia lui "bad style". De la aia se ajunge usor la asta:

    float** points = new float*[numPoints];
    for(int i = 0; i < numPoints; ++i)
    points[i] = new float[2];

    Cum ziceam, igiena mentala, ca si i++ vs. ++i.

  4. O alocare vs. size+1 alocari, adica “alocari in plus”. Mai mult cod, mai incet, nici o diferenta de lizibilitate, 0 avantaje – adica definitia lui “bad style”.

    Era mai simplu daca explicai ce vrei sa spui de fapt de la bun inceput. Da, OK, ai avantajele de care ziceai, desi in privinta lizibilitatii am unele dubii.

  5. Am explicat cu liniute. Nu-i vina mea ca tu ai inteles ca vorbesc despre STL, desi eu n-am zis nimic de STL.

  6. Singurile comentarii acceptate sunt cele la obiect. Cele care fac referire la lucruri care nu au nici o legatura cu topicul, mai ales la lucruri discutate pe alte situri nu-si au locul aici si imi rezerv dreptul de a le sterge, chiar daca acest lucru displace.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.