Any Tips On Writing More Efficient Code?

[rapidcoder]

ConcurrentHashMap is a typical data structure used in lock-free/wait-free programming and it exposes an API typical for lockfree structures (CAS-like). Lock-free programming doesn't mean you're not allowed to use locks anywhere *at all*. Actually most of the time you can't. Atomic operations like CAS are special kinds of locks, too. CHM uses locks only on writes but no locking on reads (volatile reads). I guess they didn't make it fully lock-free, because it is just not needed. How often will you have collisions on a single bucket?

BTW: I'm arguing more on the general approach, than one particular implementation. Protecting shared resources by locks is generally less scalable than not-using-locks. But this is not black and white - there are many shades of gray inbetween.

BTW2: Regardless of how you call it - avoiding locks (especially contended) is a good thing. Therefore avoiding mutexes and shared_ptr is a good general advice if you care about performance.

[N36fSL3A]

Is it necessary to use vectors for every array?

People always tell me to use vectors and I wonder why I should use them when they're not needed.

[BHX]

That is your job as the programmer. You have to know when and where to use each tool you have in your bag. You really only need vectors if you plan to be doing things that require the array to adjust size (vector), otherwise static arrays will work.

[N36fSL3A]

That's what I originally thought, but people told me otherwise...

Anyway, what if I want to allocate a an array with a pointer, would I have to use a vector?

[BHX]

Well depends on what you mean by that.

int *array[];

or

int *array;
array = new int[];

delete [] array;

or The ever fun dynamic memory allocation multidimensional array:

int **array;
array = new int *[ARRAY_SIZE];
for(int i = 0; i < ARRAY_SIZE; i++)
{
      array[i] = new int[ARRAY_SIZE];
}

// same as calling array [ARRAY_SIZE][ARRAY_SIZE]; 

[N36fSL3A]

The first, I will never use multidimensional arrays.

[BHX]

Well you will eventually. Tilemaps require multidimensional arrays. Here is an array from a tilemap test I was doing a few years back on my laptop.

int map[MAP_X_SIZE][MAP_Y_SIZE] = {
    {0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4},
    {8, 3, 3, 3, 3, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 8},
    {8, 3, 3, 3, 3, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 8},
    {8, 3, 3, 3, 3, 7, 5, 5, 7, 3, 3, 3, 3, 3, 3, 3, 9, 9, 3, 3, 3, 3, 3, 3, 9, 9, 3, 3, 3, 8},
    {8, 3, 3, 3, 3, 7, 5, 5, 7, 3, 3, 3, 3, 3, 3, 3, 9, 9, 3, 3, 3, 3, 3, 3, 9, 9, 3, 3, 3, 8},
    {8, 3, 3, 3, 3, 7, 5, 5, 7, 3, 3, 3, 3, 3, 3, 3, 9, 9, 3, 3, 3, 3, 3, 3, 9, 9, 3, 3, 3, 8},
    {8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 8},
    {8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 8},
    {8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 8},
    {8, 3, 3, 3, 3, 7, 5, 5, 7, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 8},
    {8, 3, 3, 3, 3, 7, 5, 5, 7, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 7, 7, 7, 3, 8},
    {8, 3, 3, 3, 3, 3, 5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 5, 5, 5, 3, 3, 3, 3, 8},
    {8, 3, 3, 3, 3, 3, 5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 5, 5, 5, 3, 3, 3, 3, 8},
    {8, 3, 3, 3, 3, 3, 5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 5, 3, 5, 3, 3, 3, 3, 8},
    {8, 3, 3, 3, 3, 3, 5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 5, 3, 5, 3, 3, 3, 3, 8},
    {8, 3, 3, 3, 3, 3, 5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 5, 5, 5, 3, 3, 3, 3, 8},
    {8, 3, 3, 3, 3, 3, 5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 5, 5, 5, 3, 3, 3, 3, 8},
    {8, 3, 3, 3, 3, 3, 5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 5, 3, 3, 3, 3, 3, 8},
    {8, 3, 3, 3, 3, 3, 3, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 8},
    {8, 3, 3, 3, 3, 3, 3, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 8},
    {8, 3, 3, 3, 3, 3, 3, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 8},
    {8, 3, 3, 3, 3, 3, 3, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 8},
    {8, 3, 3, 3, 3, 3, 5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 7, 3, 7, 7, 7, 3, 3, 3, 3, 3, 3, 8},
    {8, 3, 3, 3, 3, 3, 5, 5, 3, 7, 3, 3, 3, 3, 3, 3, 3, 3, 3, 7, 3, 3, 3, 7, 3, 3, 3, 3, 3, 8},
    {8, 3, 3, 3, 3, 3, 5, 3, 7, 7, 3, 3, 3, 3, 3, 3, 3, 3, 3, 7, 7, 7, 7, 7, 3, 3, 3, 3, 3, 8},
    {8, 3, 3, 3, 3, 3, 5, 3, 7, 7, 3, 3, 3, 3, 3, 7, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 8},
    {8, 3, 3, 3, 3, 5, 5, 3, 7, 7, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 8},
    {8, 3, 3, 3, 3, 5, 5, 3, 7, 7, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 8},
    {8, 3, 3, 3, 3, 5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 8},
    {6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2}
};

I could have used multidimensional vectors if I wanted to make it resizable per level. vector< vector<int> > a;

http://prntscr.com/20g50z <= screenshot of my tilemap test running.

[Lachlan Easton]

Well since the original topic was efficient code, it would be a much better idea (in regards to efficiency) to store rectangles of the same type of tile (with tiled uvs). That way there will only be one draw call for sections that would take upwards of a hundred if each tile were separate.

[BHX]

I used Allegro for that code.

@Lachlan Easton
What? Not sure what you are saying (not good with the terms). UV I'm only familiar with in 3D and know it means the 2D XY coordinates as 3D uses XYZ for its coordinates. That is why I'm confused about you saying to use tile UVs.

That is my hard coded array, as I didn't want to mess with file i/o at the time (mainly because I was learning tilemapping still). I have a tilesheet of those images that I read into a vector that holds each tile.

sprite = al_load_bitmap("tilesheet.png");
    int tileOffset = 0;

    // load chunks (32x32) chunks into individual tile
    for(int i = 0; i < 10; i++)
    {
        for(int j = 0; j < 2; j++)
        {
            tiles.push_back(al_create_sub_bitmap(sprite, i * TILE_SIZE, j * TILE_SIZE, TILE_SIZE, TILE_SIZE));
            tileOffset = tileOffset + TILE_SIZE;
        }
    }

Drawing code:

for (int i = 0; i < MAP_X_SIZE; i++)
            {
                for(int j = 0; j < MAP_Y_SIZE; j++)
                {
                    al_draw_bitmap(tiles[map[j][i]], i * TILE_SIZE, j * TILE_SIZE, 0);
                }
            }

Again that was just a test so it wasn't designed to be efficient, it was designed to familiarize me with tilemapping.

[Lachlan Easton]

UVs (generally) refer to a mesh's coordinates on a texture map http://en.wikipedia.org/wiki/UV_mapping
This is applicable to both 2D and 3D. In a way it turns 2D into 4D and 3D into 5D, but it's probably not a great idea to think of it that way. Having UV coordinates >1 or <0 can let you tile a texture. I don't know if Allegro supports this.

In regards to the rectangle, the screenshot you posted would create rects like this:
https://www.dropbox.com/s/sdr4ubc7pc4vueu/tilesss.png
each rect would only need one draw call (as apposed to the ~140 for each tile individually).
Finding the most efficient arrangement of rectangles is nontrivial.

[BHX]

That doesn't even 'almost' make sense to me. The wikipedia page just adds to the confusion for me because the texture it shows is just a single image that is then applied to the unwrapped 2D image of the 3D object that you then put the jpg/png onto so that it is wrapped back onto the 3d model.Even the wiki says:

This process projects a texture map onto a 3D object. The letters "U" and "V" denote the axes of the 2D texture because "X", "Y" and "Z" are already used to denote the axes of the 3D object in model space.

You say it is both 2D and 3D, but the wikipedia link is talking about unwrapping a 3D object to get the 2D UV Map to put the image on. So your talking about rectangles and UVs is just completely confusing me right now. I'll have to look into it more when I have time.

[Lachlan Easton]

I've never been the best of teachers :P
Okay, 2D essentially is 3D, except everything has its third coordinate locked to zero. Each rectangle is a 3D mesh made of one quad (4 verts), each quad has its coordinates in games space and can be unwrapped onto a texture.
Actually, this is how sprite-sheets for characters et al. work.

[BHX]

Oh, okay, now that made sense to me :).

[rapidcoder]

You should not use raw arrays for the same reasons you should not use naked pointers. Also vectors are easier to use, because they track vector size for you, while arrays don't expose their size to the programmer and you need to store it separately (which is pretty funny because in every single implementation I know of, internally they *do* store their size so they can be delete[]d so you end up storing the array size *twice*, unless it is completely constant).

[N36fSL3A]

BHXSpecter wrote:

Well you will eventually. Tilemaps require multidimensional arrays. Here is an array from a tilemap test I was doing a few years back on my laptop.

No... I was working on a 2D RPG a while ago, I never used them, ever.

My map looked like:

std::vector<Tile*> tiles;
unsigned int w;
unsigned int h;

Much faster that 2D arrays, and much simpler aswell.

I suppose theoretically a 2 dimensional vector would be able to hold more than a 1D vector, due to the size limits of an unsigned integer. But I seriously doubt someones going to use 4 billion tiles in a map.

...Nice game btw.

rapidcoder wrote:

You should not use raw arrays for the same reasons you should not use naked pointers. Also vectors are easier to use, because they track vector size for you, while arrays don't expose their size to the programmer and you need to store it separately (which is pretty funny because in every single implementation I know of, internally they *do* store their size so they can be delete[]d so you end up storing the array size *twice*, unless it is completely constant).

I really don't need what vectors give to me. I usually just need to allocate memory real quick then read some data from a file, after that, directly plug it into OpenGL. All that vector nonsense just makes my job HARDER.

EDIT: Yes, the size is constant in a way, it allocates memory once then reads data. It's deleted straight after that

[3qX21hU5]

Remember there is std::array now that gives you the benefits of STL containers while still giving you a static array. Personally I say if you know you won't need to resize the container ever or you know the max amount that would be needed then a static array is probably your best bet (Preferably std::array). If there is a possibility you might need to resize it then a dynamic array is probably the best bet.

I personally don't get the argument or vector is better then array or vice versa. They are two different containers which server different purposes. In my mind it's like comparing oranges to apples. There is no one size is a perfect fit container out there. Choose whatever one works best for your situation it's as simple as that.

If you don't know which container to use for that situation then you better go back to the basics and learn your containers pros and cons again.


Now performance wise vectors and arrays are really no different in performance as long as you size the vector correctly. If you are constantly resizing the vector then yes you will have a performance hit but that is your own fault not the containers.

[chrisname]

If you have a compiler that supports C++11 then you don't have to use stack arrays at all, you can just use std::array<T, N>, although their size is fixed at compile-time. If you need resizable arrays then you can use std::vector or std::deque in most cases.

[N36fSL3A]

But I don't know the size of the array.

The code I have works just fine, but I have a .bmp loader, and I get the size of the array from the file.

[chrisname]

If you don't know the size of the array until runtime, then use std::vector.

[N36fSL3A]

But it just makes everything more difficult. I have to add in for loops, etc.