Jump to content

  • Log In with Google      Sign In   
  • Create Account


Sorting a std::vector efficiently


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
29 replies to this topic

#1 cozzie   Members   -  Reputation: 1586

Like
0Likes
Like

Posted 08 March 2014 - 06:01 PM

Hi,

 

I would like to know how/ what possibilities I have to rearrange a std::vector, assuming that I know in which order I want the elements to be rearranged. The sorting/ finding out the new order I've already covered and saved in a 'newIndex' int vector.The only possibility I thought of is making a copy of the original vector and then copy it back in the right order, but that feels like a waste of memory/ performance.

 

Can someone give me some directions?

bool CRenderQueue::SortBucketBlended()
{
	if(mEffectDataCreated)
	{
		size_t bucketSize = mRenderBucketBlended.size();

		std::vector<int>	indexTemp;	
		std::vector<int>	orderTemp;	
		std::vector<float>	distToCam;	
		
		indexTemp.resize(bucketSize);
		orderTemp.resize(bucketSize);
		distToCam.resize(bucketSize);

		for(size_t init=0;init<bucketSize;++init) orderTemp[init] = init;
		
		for(size_t renderable=0;renderable<mRenderBucketBlended.size();++renderable)
		{
			indexTemp[renderable] = renderable;
			distToCam[renderable] = mRenderBucketBlended[renderable].DistToCam;
		}

		sort(orderTemp.begin(), orderTemp.end(), [&](int a, int b)
			{ return distToCam[a] > distToCam[b]; });

		std::vector<int> newIndex;
		newIndex.resize(bucketSize);

		for(size_t results=0;results<bucketSize;++results)
			newIndex[results] = indexTemp[orderTemp[results]];

		// re-arrange the blended bucket based on newIndex?

		return true;
	}
	else return false;
}


Edited by cozzie, 08 March 2014 - 06:01 PM.


Sponsor:

#2 phantom   Moderators   -  Reputation: 7113

Like
9Likes
Like

Posted 08 March 2014 - 06:54 PM

Just sort the renderables in place?
It'll probably be faster than 4 memory allocations, an initialisation of 3 arrays, a sort and 'newindex' setup (which will be horrible because you could end up jumping all over memory to find your indices as it's a double indirection).

or, when you add them, use an insertion sort to pre-position them in the correct place in the vector. (A vector which should be pre-sized to 'max number of entities' before you even try to do this loop).

#3 L. Spiro   Crossbones+   -  Reputation: 13318

Like
6Likes
Like

Posted 08 March 2014 - 07:45 PM

The only possibility I thought of is making a copy of the original vector and then copy it back in the right order, but that feels like a waste of memory/ performance.

You are making a render queue.
Why not just run over the items in the order specified by the sorted indices you said you have?


This allows to take advantage of temporal coherence across frames.


#1: Add render-queue items to a render queue.
- #a: If the total number of items is the same as in the last frame, continue.
- #b: If the total number of items is less than before, recreate the index list from 0 to total items, in order.
- #c: If the total number of items is greater than before, just add the new indices in order at the end of the list, not modifying the indices from the previous frame.
#2: Use insertion sort on the indices of the items. Since it should be the same or similar to the previous frame, insertion sort will be fastest.
#3: Run over the list and use the array of sorted indices to draw each item specified by the render queue items.


L. Spiro
It is amazing how often people try to be unique, and yet they are always trying to make others be like them. - L. Spiro 2011
I spent most of my life learning the courage it takes to go out and get what I want. Now that I have it, I am not sure exactly what it is that I want. - L. Spiro 2013
I went to my local Subway once to find some guy yelling at the staff. When someone finally came to take my order and asked, “May I help you?”, I replied, “Yeah, I’ll have one asshole to go.”
L. Spiro Engine: http://lspiroengine.com
L. Spiro Engine Forums: http://lspiroengine.com/forums

#4 Ryan_001   Prime Members   -  Reputation: 1348

Like
3Likes
Like

Posted 08 March 2014 - 11:22 PM

I'm confused.  Why not just store pointers to the renderables in a vector?

std::vector<Renderable*> queue;
queue.clear();
FillQueue(queue);
std::sort(queue.begin(),queue.end(),SomeSortFunction);
for (auto i = queue.begin(); i != queue.end(); ++i) (*i)->Render();

Edited by Ryan_001, 09 March 2014 - 12:02 AM.


#5 L. Spiro   Crossbones+   -  Reputation: 13318

Like
1Likes
Like

Posted 09 March 2014 - 02:00 AM

  1. Store what needs to be sorted and nothing more.  Certainly not an entire “renderable”.  What is that anyway?  An entire mesh?  A part of a mesh?
  2. Single-responsibility principle.  A render-queue item is specifically designed to be a contextless collection of just the information needed to sort and determine the order of rendering of mesh parts.  It doesn’t know what a texture is, or a shader, mesh, vertex buffer, index buffer, etc.
  3. Never sort a render queue with std::sort().  It is neither stable (most important factor) nor fast enough thanks to pointer function calls on each compare.  Create a templated base class that uses < and == operators within its code and add these as inlined overridden operators to the render-queue item class/structure.
  4. Adding things to the render queue locally and sorting indices between them within that linear section of memory should always outperform a sort that needs to dereference 2 pointers on each compare, especially when what gets swapped is actually a 4-byte integer (no need to swap 64-bit integers just because you promote to 64-bit machines).

 

 

L. Spiro


It is amazing how often people try to be unique, and yet they are always trying to make others be like them. - L. Spiro 2011
I spent most of my life learning the courage it takes to go out and get what I want. Now that I have it, I am not sure exactly what it is that I want. - L. Spiro 2013
I went to my local Subway once to find some guy yelling at the staff. When someone finally came to take my order and asked, “May I help you?”, I replied, “Yeah, I’ll have one asshole to go.”
L. Spiro Engine: http://lspiroengine.com
L. Spiro Engine Forums: http://lspiroengine.com/forums

#6 Ryan_001   Prime Members   -  Reputation: 1348

Like
0Likes
Like

Posted 09 March 2014 - 03:04 AM

 

  1. Store what needs to be sorted and nothing more.  Certainly not an entire “renderable”.  What is that anyway?  An entire mesh?  A part of a mesh?
  2. Single-responsibility principle.  A render-queue item is specifically designed to be a contextless collection of just the information needed to sort and determine the order of rendering of mesh parts.  It doesn’t know what a texture is, or a shader, mesh, vertex buffer, index buffer, etc.
  3. Never sort a render queue with std::sort().  It is neither stable (most important factor) nor fast enough thanks to pointer function calls on each compare.  Create a templated base class that uses < and == operators within its code and add these as inlined overridden operators to the render-queue item class/structure.
  4. Adding things to the render queue locally and sorting indices between them within that linear section of memory should always outperform a sort that needs to dereference 2 pointers on each compare, especially when what gets swapped is actually a 4-byte integer (no need to swap 64-bit integers just because you promote to 64-bit machines).

 

 

L. Spiro

 

 

1) I don't know what the int's mean.  I assumed they were identifiers to renderable objects of some sort.  Its not like it matters...  If we're storing only what needs to be stored, then a unique id (aka a pointer) is sufficient.

 

2) That doesn't really apply here.  If I store id's to items, how is that different from storing pointers (and yes, I know a very complex Component Entity system might require id's, the OPs clearly not working with one...)?

 

3) I don't see why you would need a stable sort, but if you feel it is necessary std::stable_sort can be dropped in just as easily.

 

4) Whether you are storing int's or pointers, its the same thing performance-wise.  If you're sorting on data stored in an object (distance, shader usage, whatever) then you have to look that up somehow in the sort function.  Looking it up through a pointer is at least as fast, if not faster, than any other method.  If you didn't need object data in the sort, then using pointers is no slower.  Granted 64-bit pointers could be slightly slower to sort than pure 32-bit ints... perhaps... but the difference is negligible at best; and again if you have to look up data to do any compare, pointers are your best option.



#7 L. Spiro   Crossbones+   -  Reputation: 13318

Like
0Likes
Like

Posted 09 March 2014 - 04:16 AM

#1 and #2 are similar. “Store what you need.”
They are typically ID values, yes, but to shaders, textures, etc. Since a reasonable limit to the number of valid shader ID’s or texture ID’s is 65,535 concurrently, it is reasonable to use only 2-byte ID’s for these, half the bandwidth of a 32-bit pointer. This means on 32-bit systems you can put the ID’s next to each other in RAM and compare 2 at once, increasing the speed of the sort potentially dramatically.

And once again it performs the sort with as little knowledge about any graphics interfaces as possible; it uses the bare minimum of knowledge it needs to access, which is just a set of integral values for this purpose. Pointers would indeed be suitable too, but then you waste at least 16 bits and can compare only 1 structure member at once.

 

3) I don't see why you would need a stable sort, but if you feel it is necessary std::stable_sort can be dropped in just as easily.

  • So that things on top of each other don’t flicker, especially windshields or translucent objects with the same bounding box.
  • I said std::sort() is too slow.  If std::sort() is too slow, of course std::stable_sort() is too slow.  It would be better not to even use a render queue.

4) Whether you are storing int's or pointers, its the same thing performance-wise.

One word refutes this handily: Cache. Read my reply more carefully; I didn’t say talking about storing, I talked about accessing during a sort.
 

Granted 64-bit pointers could be slightly slower to sort than pure 32-bit ints... perhaps... but the difference is negligible at best

You know there is no such thing as negligible slowdown on a render queue right? Its whole purpose is performance.


#5: Render-queue items, which are tiny structures that hold all these ID’s and depth needed for sorting, also has another important feature that makes it necessary to use a separate structure rather than just a pointer to some modularity-breaking class: Pass number.
On multi-pass renders you should submit each pass to the render queue as a separate render-queue item structure, each with the correct shader ID and textures for that pass.
The object will be drawn once for each pass but the shaders will be properly sorted throughout (no behind-the-scenes changes between what should have been 2 objects drawn with the same shader) and overdraw on following passes will be minimized by having those passes delayed until their proper place in the queue.


L. Spiro
It is amazing how often people try to be unique, and yet they are always trying to make others be like them. - L. Spiro 2011
I spent most of my life learning the courage it takes to go out and get what I want. Now that I have it, I am not sure exactly what it is that I want. - L. Spiro 2013
I went to my local Subway once to find some guy yelling at the staff. When someone finally came to take my order and asked, “May I help you?”, I replied, “Yeah, I’ll have one asshole to go.”
L. Spiro Engine: http://lspiroengine.com
L. Spiro Engine Forums: http://lspiroengine.com/forums

#8 Ryan_001   Prime Members   -  Reputation: 1348

Like
4Likes
Like

Posted 09 March 2014 - 05:29 AM

I understand how the cache works.  If you're sorting less than 65k items, use a bubble sort if you want, any modern processor will blast through it in mirco-seconds.  You also seem to be implying that the id's themselves are sufficient for sorting.  This isn't the case in the OPs example.  He's using the indices to index into distToCam.  And of course storing the sorted value along side the id's would be faster than accessing them.  But again, that's not what the OP is doing.
 
Now you are correct, in the sense that if you were only sorting a small number of items, and they were only sorted on one criteria, that packing them into a tight data structure would yield better cache access.  But you suggest std::sort being too slow, and suggest using insertion sort instead?  That's VERY engine/game specific.  If on average more than log(n) items change place then an insertion sort would be slower.  Also there are much better ways to approach flickering (z-offsets, multi-pass, ect...), though if you don't plan on using better methods a stable_sort is a crude alternative.
 
As far as multipass, its easier to just use separate vector's for each pass.
 
Also pointers are no more 'modularity breaking' than ids.  Either way you have some numbers (pointers or ids, still both numbers) and a sort predicate.  How more or less modular you want the system is up to you.
 
I'm not trying to argue, and clearly we differ in opinion here.  I prefer the easy solution unless profiling suggests otherwise.  Given the OPs code I'm of the opinion that what you are suggesting is over-engineered for his purposes, and that the performance gains you claim are very usage dependent.  To be honest if I needed to sort millions of items at the speed you're suggesting is required, I'd probably either go with a bucket/radix sort or some sort of spatial hash; but it would really depend on the application then.  Or perhaps just dump it all to the GPU and let it sort it out smile.png

Edited by Ryan_001, 09 March 2014 - 05:30 AM.


#9 cozzie   Members   -  Reputation: 1586

Like
1Likes
Like

Posted 09 March 2014 - 06:54 AM

Thanks all, for the valuable feedback.

For context, here's the Q_RENDERABLE struct (basically just some indices):

typedef struct Q_RENDERABLE			// renderable level; for filling render buckets
{
	int	Effect;
	int	Material;
	int	Mesh;
	int	Instance;
	int	Id;		
	float DistToCam;
} Q_RENDERABLE;

I really like the suggestion (LSpiro) to save the 'newIndex' with the sorted order of renderables and use that for rendering. I will simply not only pass the reference to the renderables vector to my draw function, but also the vector containing just the indices. That way there's no copying, sorting etc. needed within the vector of renderables. This also gives me flexibility when later on I'm sorting buckets on other criteria (For example opaque, from near to far to prevent overdraw etc.).

 

Besides this I read a lot of opinion on the way I'm currently 'generating' the newIndex / sorting based on the distToCam.

A few questions on this:

- what's a stable sort? (it has the exact same parameters and syntax and seems perfectly interchangable)

- would it really be worthwhile to create my own sort (like bubble sort or something)

- any other suggestions on how to improve coming to the newIndex?

(I can 'save' a bit my making the 3 vector's members instead of on the stack and do the initial filling just once, don't think that will bring much though)

(I believe using pointers directly to the dists to cam per renderable instead of copying them, doesn't bring much either)


Edited by cozzie, 09 March 2014 - 06:56 AM.


#10 L. Spiro   Crossbones+   -  Reputation: 13318

Like
2Likes
Like

Posted 09 March 2014 - 07:05 AM

This isn't the case in the OPs example.  He's using the indices to index into distToCam.

Based likely on one of my past posts and my first reply in which I suggested to sort indices rather than structures or pointers. All of my replies have assumed sorting of indices rather than pointers or objects.
 

But you suggest std::sort being too slow, and suggest using insertion sort instead?  That's VERY engine/game specific.

No actually it’s an all-encompassing fact. std::sort() (and friends) using a function callback cannot be faster than a templated inlined sort designed to call < and == operators (I said this already), and a stable sort is required to address temporal coherency.
An insertion sort that takes advantage of temporal coherency and uses inlined sorting comparison operators always beats std::sort() and friends; it’s only a matter by how much in a per-game or per-hardware basis. In my case it was 2.34 times faster in a large scene with about 100 sortable objects, each sorted 3 times for the different passes for shadows and normal rendering.

 

How more or less modular you want the system is up to you.

Except the render queue now knows what a “renderable” is instead of just what a 16-bit integer and a float is.

 

I prefer the easy solution unless profiling suggests otherwise.

Have you actually implemented my suggestions and profiled? The problem with your plan is that you have to have your profiler actually say to you, “By the way doc, this render queue could be faster.”
I’ve actually profiled various render queues quite a lot and made huge gains in performance over my first implementation, which may have been worse than having none at all (because I used std::sort()).

Nothing I have said until now is “opinion”. I implemented 5 more render queues after the first naive one and I am telling you from experience what I observed providing the most gains in performance. I also tried things I haven’t even mentioned here, such as a merge sort, because they ultimately provided no gains.

 

- what's a stable sort?

A sort that does not modify the orders of 2 objects that have the same sort value. If sorting by distance and 2 objects are exactly 25.0f units away, they will not be swapped inside of a stable sort.
 

- would it really be worthwhile to create my own sort

Combined with taking advantage of temporal coherence it gained me over 2.34 times the performance. Use an insertion sort.
 

(I can 'save' a bit my making the 3 vector's members instead of on the stack and do the initial filling just once, don't think that will bring much though)

Putting them on the stack means you are not taking advantage of temporal coherence, and not only that but you will allocate and deallocate memory every time the method is called. They should not be on the stack, for starters, even if they are fully cleared every call. Allocation is not just a “bit” of overhead.


L. Spiro


Edited by L. Spiro, 09 March 2014 - 06:41 PM.

It is amazing how often people try to be unique, and yet they are always trying to make others be like them. - L. Spiro 2011
I spent most of my life learning the courage it takes to go out and get what I want. Now that I have it, I am not sure exactly what it is that I want. - L. Spiro 2013
I went to my local Subway once to find some guy yelling at the staff. When someone finally came to take my order and asked, “May I help you?”, I replied, “Yeah, I’ll have one asshole to go.”
L. Spiro Engine: http://lspiroengine.com
L. Spiro Engine Forums: http://lspiroengine.com/forums

#11 Adam_42   Crossbones+   -  Reputation: 2462

Like
7Likes
Like

Posted 09 March 2014 - 07:16 AM


Never sort a render queue with std::sort(). It is neither stable (most important factor) nor fast enough thanks to pointer function calls on each compare. Create a templated base class that uses < and == operators within its code and add these as inlined overridden operators to the render-queue item class/structure.

 

std::sort (and presumably std::stable_sort, but I've not tried it) can and does inline the comparison. That will happen both when using the default < operator, and when specifying a functor to compare with like std::greater<T>(). Other cases do not inline so well in my experience.

 

Of course in general no inlining is guaranteed by the compiler, so if you care about such things double check the disassembly in an optimized build.



#12 samoth   Crossbones+   -  Reputation: 4684

Like
6Likes
Like

Posted 09 March 2014 - 07:45 AM

 


Never sort a render queue with std::sort(). It is neither stable (most important factor) nor fast enough thanks to pointer function calls on each compare. Create a templated base class that uses < and == operators within its code and add these as inlined overridden operators to the render-queue item class/structure.

 

std::sort (and presumably std::stable_sort, but I've not tried it) can and does inline the comparison. That will happen both when using the default < operator, and when specifying a functor to compare with like std::greater<T>(). Other cases do not inline so well in my experience.

Fully agree. std::sort being slow is a statement I can't understand. Default operators inline just fine, and with lambdas, it seems to inline pretty much everything else too (at least for me). I've never bothered about the speed of function pointer comparators since they've never been an issue, but I would concede that these likely won't inline, but who knows. While it is certainly possible to write some specialized sort that is faster, but as an a-priori strategy, I deem this a premature optimization in Hoare's sense. You can still resort to trying to write a better implementation if it turns out that sorting is really bottlenecking you.

 

As for the sort needing to be stable, I don't get the argument either. The point of a stable sort is that if for example you have a database of people who have a name ("John Smith") and an age ("45 years"), you first sort by name, and then later sort by age. If the sort is stable, this will give a list of people sorted by age, and within each group of people with the same age, names will be sorted alphabetically. That's not what you do in a render queue.

 

Following the above description, stable sorting is necessary to avoid flickering when objects have the same z distance. For that one would use Z buffering anyway. Stable sorting, or even perfect sorting at all, isn't necessary for that. Indeed, when you only care about Z, the common idiom is to run a single pass of bubble sort over all objects, which eventually puts them into kind-of-order (never 100% correctly, but good enough) and amortizes the cost for sorting over several frames (with an exactly predictable, constant cost per frame). Bubble sort as such is an ultra poor algorithm, but in this case, it turns out being one of the best solutions.

 

A fully fledged render queue has a few more things to worry about than just depth (such as grouping by shaders etc), but since you don't normally sort these independently, it shouldn't matter whether your sort is stable or not (at least I couldn't imagine how... feel free to explain where it matters). If you do for example something like in Lengyel's 6-7 year old blog post (basically, encode that stuff into a 64 bit sort key) you run just one single sort over the whole thing, and it doesn't matter at all whether it's stable or not.

 

EDIT:

 

Consider a very minimal render queue with very poor z resolution and a very minimal overall sort key:

1 bit:  layer (HUD or scene)
1 bit:  transparent or solid
2 bits: material (shader + texture + whatever)
4 bits: depth

No matter how you sort this 8-bit key (stable or not), renderables in the scene layer will always sort after the ones in the HUD, transparent objects (which test but don't write Z) will always draw after the solid ones (which test and write Z), and within each group, they'll also be sorted by material (shader/texture/whatever), and lastly depth.
Sure, if two objects have exactly identical sort keys, it is possible that they end up being rendered in alternating order between different frames, but who cares.


Edited by samoth, 09 March 2014 - 08:04 AM.


#13 Bregma   Crossbones+   -  Reputation: 5017

Like
8Likes
Like

Posted 09 March 2014 - 10:29 AM

std::sort() (and friends) using a function callback cannot be faster than a templated inlined sort designed to call < and == operators (I said this already), and a stable sort is required to address temporal coherency.

Both std::sort and std::stable_sort are templated inlined sorts designed to call operator<.  What was your point again?


Stephen M. Webb
Professional Free Software Developer

#14 L. Spiro   Crossbones+   -  Reputation: 13318

Like
2Likes
Like

Posted 09 March 2014 - 03:11 PM

std::sort() (and friends) using a function callback cannot be faster than a templated inlined sort designed to call < and == operators (I said this already), and a stable sort is required to address temporal coherency.

Both std::sort and std::stable_sort are templated inlined sorts designed to call operator<.  What was your point again?

  • Only when it is a function object.  Function pointers can’t be inlined, and it does work with function pointers: http://www.cplusplus.com/reference/algorithm/sort/

  • Other cases do not inline so well in my experience.

    My case did not inline.
  • It doesn’t matter anyway since you should be sorting indices, which requires you to make your own sort anyway.

As for the sort needing to be stable, I don't get the argument either. The point of a stable sort is that if for example you have a database of people who have a name ("John Smith") and an age ("45 years"), you first sort by name, and then later sort by age. If the sort is stable, this will give a list of people sorted by age, and within each group of people with the same age, names will be sorted alphabetically. That's not what you do in a render queue.

I gave a more applicable description already. Does no one understand temporal coherence as it pertains to the sorted objects in a render queue across frames? I really get tired of repeating myself.
 
 
 
 

If you do for example something like in Lengyel's 6-7 year old blog post

You mean Christer Ericson’s?
 
 
 
 

Sure, if two objects have exactly identical sort keys, it is possible that they end up being rendered in alternating order between different frames, but who cares.

I sure did when one of the model cars I was using had a back windshield with 2 parts with identical bounding boxes (because they aligned exactly with each other all around the borders), making it flicker like mad until I changed to a temporal-coherence-friendly stable sort.
 
 

Bubble sort as such is an ultra poor algorithm, but in this case, it turns out being one of the best solutions.

A bubble sort requires at least twice as many writes as insertion sort, twice as many cache misses, and asymptotically more branch mispredictions.
 
 
Is it this difficult to understand that you can reuse the results of the previous frame to improve the performance of a render queue dramatically?  One of the most important things you can do, in fact.
 
 
L. Spiro

Edited by L. Spiro, 09 March 2014 - 03:51 PM.

It is amazing how often people try to be unique, and yet they are always trying to make others be like them. - L. Spiro 2011
I spent most of my life learning the courage it takes to go out and get what I want. Now that I have it, I am not sure exactly what it is that I want. - L. Spiro 2013
I went to my local Subway once to find some guy yelling at the staff. When someone finally came to take my order and asked, “May I help you?”, I replied, “Yeah, I’ll have one asshole to go.”
L. Spiro Engine: http://lspiroengine.com
L. Spiro Engine Forums: http://lspiroengine.com/forums

#15 King Mir   Members   -  Reputation: 1956

Like
3Likes
Like

Posted 09 March 2014 - 03:23 PM

Since writing an insertion sort is more work anyway, you'll want to use std::sort or std::stable_sort as a first pass. Later, if there's a performance problem, you can replace it with your own tailored sorting function, and see if it helps. The opinion here is divided here on if it would.

#16 King Mir   Members   -  Reputation: 1956

Like
3Likes
Like

Posted 09 March 2014 - 03:42 PM

  • Only when it is a function object.  Function pointers can’t be inlined, and it does work with function pointers: http://www.cplusplus.com/reference/algorithm/sort/
  • My case did not inline.
  • It doesn’t matter anyway since you should be sorting indices, which requires you to make your own sort anyway.
You can sort a vector of indices as easily as a vector of pointers with standard algorithms.

if a function object inlines better, pass a function object.

Compiler technology is also moving forward, so what a compiler failed to inline before isn't necessarily the same today.

I'd be tempted to trust you with your experience in working with render queues if it weren't for the fact that you seem to have little experience working with the STL.

#17 Pink Horror   Members   -  Reputation: 1149

Like
1Likes
Like

Posted 09 March 2014 - 03:51 PM

Never sort a render queue with std::sort().  It is neither stable (most important factor) nor fast enough thanks to pointer function calls on each compare.  Create a templated base class that uses < and == operators within its code and add these as inlined overridden operators to the render-queue item class/structure.


First you were saying std::sort was guaranteed to be too slow because it had to use a function pointer.

Only when it is a function object.  Function pointers can’t be inlined, and it does work with function pointers: http://www.cplusplus.com/reference/algorithm/sort/


Now you're saying that, because std::sort has the option to use a function pointer, even though you don't have to, it's still too slow. Well, ok, I have the option of creating an insertion sort that calls new for every temp variable to go up against your function pointer std::sort. We'll see who can make the slowest straw-man sort.

In my case it was 2.34 times faster in a large scene with about 100 sortable objects, each sorted 3 times for the different passes for shadows and normal rendering.


Without knowing many details about the OP's code, there's no way I would ever come into an argument saying that something is definitely too slow, just because there's some other version that's 2.34 times faster. Maybe his program has 2.34 times as much as yours did to sort. Maybe it has ten times as much time. Maybe it has one tenth. Generally, I'd expect many more situations where either has plenty of time or neither is fast enough, compared to situations where one fits and the other doesn't.

#18 L. Spiro   Crossbones+   -  Reputation: 13318

Like
1Likes
Like

Posted 09 March 2014 - 03:56 PM

I'd be tempted to trust you with your experience in working with render queues if it weren't for the fact that you seem to have little experience working with the STL.

Perhaps it is time to write an in-depth article with downloadable source for users to test on their own then, eh?
I’ve already been through all of these render-queue variants on multiple devices and platforms (multiple x86, multiple x64, and various iOS devices).


L. Spiro
It is amazing how often people try to be unique, and yet they are always trying to make others be like them. - L. Spiro 2011
I spent most of my life learning the courage it takes to go out and get what I want. Now that I have it, I am not sure exactly what it is that I want. - L. Spiro 2013
I went to my local Subway once to find some guy yelling at the staff. When someone finally came to take my order and asked, “May I help you?”, I replied, “Yeah, I’ll have one asshole to go.”
L. Spiro Engine: http://lspiroengine.com
L. Spiro Engine Forums: http://lspiroengine.com/forums

#19 Bregma   Crossbones+   -  Reputation: 5017

Like
0Likes
Like

Posted 09 March 2014 - 07:23 PM


The point of a stable sort is that if for example you have a database of people who have a name ("John Smith") and an age ("45 years"), you first sort by name, and then later sort by age. If the sort is stable, this will give a list of people sorted by age, and within each group of people with the same age, names will be sorted alphabetically.

That's not a stable sort: that's a secondary sort.  A stable sort will preserve the relative order of two items with the same primary sort key.

 

Just, you know, to be pedantic.


Stephen M. Webb
Professional Free Software Developer

#20 samoth   Crossbones+   -  Reputation: 4684

Like
0Likes
Like

Posted 09 March 2014 - 07:32 PM

Only when it is a function object.  Function pointers can’t be inlined, and it does work with function pointers: http://www.cplusplus.com/reference/algorithm/sort/

You seem to be using a different standard library than the rest of us (or at least one that's different from mine...), since mine either uses operator< or a comparison function object.

 

But don't mind me, I'm probably using the wrong one.

 

(problem with car windows)
nobody understands stuff

Yup, sorry. Two different, distinct objects occupying the same space in the same time... I already didn't get that one when watching Timecop.

 

My car has a distinct window in the front, and one in the back. No matter how hard I try, I can't get one to move into the other. From a purely practical point of view, I'm not getting the problem.
 

A bubble sort requires at least twice as many writes as insertion sort, twice as many cache misses, and asymptotically more branch mispredictions.

One pass of bubble sort has exactly two cache misses since it traverses the data set exactly once, and strictly linearly. At the second cache miss, the hardware prefetcher kicks in.

For random input, it has on the average n/2 branch mispredictions if the compiler doesn't optimize properly, and zero with a compiler that uses CMOV.
In any case, its amortized runtime is constant. You can call it "temporal coherence", if you think that sounds more intelligent, but it's the same thing.






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS