std::vector making struct sort slow? c++

Question

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.

Does the difference in perfomance remain, if you change the sorting function to bool sort (square& a,square& b)? — mikhail
– mikhail, Commented Aug 8, 2014 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
– j_kubik, Commented Aug 8, 2014 at 13:36
@j_kubik I disagree. This would mean moving the struct into the sort function would damage the original struct. — Neil Kirk
– Neil Kirk, Commented Aug 8, 2014 at 13:38
@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
– j_kubik, Commented Aug 8, 2014 at 13:55

Neil Kirk · Accepted Answer · 2014-08-08 13:23:01Z

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.

answered Aug 8, 2014 at 13:23

Neil Kirk

22k9 gold badges57 silver badges96 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

juanchopanza Over a year ago

On the other hand, vector could be faster to move that array, so it is worth trying it out with both.

Neil Kirk Over a year ago

@juanchopanza You are correct in general. However, I think from the question the array size is only 3 :)

Miicck Over a year ago

The problem was indeed as you pointed out. Thanks very much for the input. Also, juanchopanza, why might vector be faster to move?

Neil Kirk Over a year ago

@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.

WhozCraig Over a year ago

+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.

TNA · Accepted Answer · 2014-08-08 13:30:27Z

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);

answered Aug 8, 2014 at 13:30

TNA

2,7551 gold badge17 silver badges20 bronze badges

2 Comments

Neil Kirk Over a year ago

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.

TNA Over a year ago

@Neil Kirk I don't know any compiler that can inline a function call through a function pointer stackoverflow.com/questions/356950/c-functors-and-their-uses

Matyro · Accepted Answer · 2014-08-08 13:23:07Z

-1

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

answered Aug 8, 2014 at 13:23

Matyro

1411 silver badge9 bronze badges

1 Comment

Neil Kirk Over a year ago

It has nothing to do with preallocating.

glezmen · Accepted Answer · 2014-08-08 13:25:36Z

-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);

answered Aug 8, 2014 at 13:25

glezmen

5542 silver badges5 bronze badges

2 Comments

mikhail Over a year ago

Why change the processing code if you can just use references?

user2672165 Over a year ago

Then it should be const ptr.

Collectives™ on Stack Overflow

std::vector making struct sort slow? c++

4 Answers 4

5 Comments

2 Comments

1 Comment

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

5 Comments

2 Comments

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related