2

I have a list of structs that I am sorting by one of the members. I am using std::sort with my own comparison function, that part is fine. However, I notice a (very) large performance gap when I change the struct from:

struct square
{
    float x;
    float y;
    float z;

    float scale;
    float angle;

    GLuint texture;
};

to

struct square
{
    float x;
    float y;
    float z;

    float scale;
    float angle;

    GLuint texture;
    std::vector <float> color;
};

I have since used an entirely different method, and I realize that using a vector like this is a bad idea (I know the size of array - rgb) but I was wondering why I got the performance hit. I was comparing the z values to sort.

Here is my sorting function and struct list:

std::vector <square> square_list;
//Then add a bunch of squares

bool sort (square a,square b)
{
   return a.z < b.z;
}

//Here is the sort that is slow
std::sort (square_list.begin(),square_list.end(),sort);

I wonder if it has anything to do with re-ordering the list of structs as their size is significantly bigger in the second case?

Thanks for any responses.

Miicck
  • 182
  • 10
  • Does the difference in perfomance remain, if you change the sorting function to `bool sort (square& a,square& b)`? – mikhail Aug 08 '14 at 13:22
  • It would probably go quicker if you wrote move constructor/assignment operator for your structure. This way memory allocated for `color` (outside the struct) doesn't need to be re-allocated and copied, but the pointers are just moved from one vector to another. Should be at least a bit quicker. – j_kubik Aug 08 '14 at 13:36
  • @j_kubik I disagree. This would mean moving the struct into the sort function would damage the original struct. – Neil Kirk Aug 08 '14 at 13:38
  • @j_kubik Are you suggesting something like "shallow copying"? Seems to me that would be quite bad for the occasion: this way after the `square` object (say, A) if copied in `sort` function (say, begin now called B), A and B share the same pointer to `vector`. B's destructor will be called when exiting `sort`, thus destroying the memory allocated for `A.color`. Now A has a non-valid pointer `A.color`. You could, probably, redefine the destructor not to delete `color`, but that would lead to tremendous memory leaks. – mikhail Aug 08 '14 at 13:43
  • 1
    @NeilKirk @mikhail I didn't mean moving objects into sort function, this would be pointless - I don't even see how this could have worked at all, not to mention quicker. Move operator would make it quicker because of what happens after comparison - structure is being moved within array (usually exchanged with another structure, but we don't have an operator for that, and well optimized move will do just the same), so that array becomes sorted in the end. I assume c++11 implementations would use move semantics to move/exchange elements in `std::sort`. – j_kubik Aug 08 '14 at 13:55
  • @j_kubik OK I understand now, sorry. I don't know if C++11 can generate its own move operators like it can the assignment operator. – Neil Kirk Aug 08 '14 at 14:00
  • 1
    @NeilKirk http://stackoverflow.com/questions/8283589/are-move-constructors-produced-automatically – j_kubik Aug 10 '14 at 07:30
  • @j_kubik Thanks, that is informative! – Neil Kirk Aug 10 '14 at 07:32

4 Answers4

7
bool sort (square a,square b)

This copies the structs each time, including the vectors. Vectors are slower to copy than normal arrays. You should use this instead.

bool sort (const square& a, const square& b)

If you are using C++11, you can replace the vector with std::array as the size is constant.

Neil Kirk
  • 21,327
  • 9
  • 53
  • 91
  • On the other hand, `vector` could be faster to move that `array`, so it is worth trying it out with both. – juanchopanza Aug 08 '14 at 13:27
  • 1
    @juanchopanza You are correct in general. However, I think from the question the array size is only 3 :) – Neil Kirk Aug 08 '14 at 13:32
  • The problem was indeed as you pointed out. Thanks very much for the input. Also, juanchopanza, why might vector be faster to move? – Miicck Aug 08 '14 at 13:32
  • @Miicck Vectors can copy only their pointers to the data, whereas the array must copy all of its data. This is because of how the data is stored by the two data structures. – Neil Kirk Aug 08 '14 at 13:33
  • +1 Also, if the `square` sequence itself doesn't *have* to be sorted and only a one-time sorted view is the usage requirement, a temporary sorted pointer bed may also be beneficial. Regardless, if you know your ceiling on your `square` count using `.reserve()` is also considerable. – WhozCraig Aug 08 '14 at 13:34
0

In addition to take parameters as const ref you could use a functor for comparison. That is often faster because functors are more easy to inline.

std::vector <square> square_list;
//Then add a bunch of squares

struct sort
{
  bool operator() (const square& a, const square& b) const {
    return a.z < b.z;
  }
}

std::sort (square_list.begin(),square_list.end(),sort);
TNA
  • 2,595
  • 1
  • 14
  • 19
  • Functors aren't easier or harder to inline than the equivalent function. As the function doesn't depend on any state, I would not use a functor here. – Neil Kirk Aug 08 '14 at 13:34
  • @Neil Kirk I don't know any compiler that can inline a function call through a function pointer https://stackoverflow.com/questions/356950/c-functors-and-their-uses – TNA Aug 08 '14 at 13:37
-1

sort copy your values every time and std::vector preallocate a bunch of memory. The amount of copy time is bigger

Matyro
  • 151
  • 1
  • 9
-3

Did you try storing pointers instead of the whole struct in your vector?

std::vector <square*> square_list;
//Then add a bunch of squares

bool sort (square* a,square* b)
{
   return a->z < b->z;
}

//Here is the sort that is slow
std::sort (square_list.begin(),square_list.end(),sort);
glezmen
  • 554
  • 2
  • 5