Jump to content

  • Log In with Google      Sign In   
  • Create Account

FREE SOFTWARE GIVEAWAY

We have 4 x Pro Licences (valued at $59 each) for 2d modular animation software Spriter to give away in this Thursday's GDNet Direct email newsletter.


Read more in this forum topic or make sure you're signed up (from the right-hand sidebar on the homepage) and read Thursday's newsletter to get in the running!


SSE insertion sort?


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
2 replies to this topic

#1 trs79   Members   -  Reputation: 126

Like
0Likes
Like

Posted 04 January 2012 - 08:19 PM

Hey all,

I've looked all over the Internet but can't seem to find any examples of an SSE insertion sort. Maybe it doesn't lend itself well to SIMD? Anyone know of any good resources? Thanks

Sponsor:

#2 frob   Moderators   -  Reputation: 22779

Like
0Likes
Like

Posted 04 January 2012 - 09:11 PM

No, you aren't finding them because it doesn't really make sense to do.

There are some sorting methods that use SIMD operations, you can even achieve O (N log log N) performance on integer sorting with SIMD in limited cases. ... But not with an insertion sort.

Check out my book, Game Development with Unity, aimed at beginners who want to build fun games fast.

Also check out my personal website at bryanwagstaff.com, where I write about assorted stuff.


#3 trs79   Members   -  Reputation: 126

Like
0Likes
Like

Posted 04 January 2012 - 10:00 PM

Thanks, I was afraid of that. My data sets is almost always going to be mostly sorted so it seems like the insertion sort would be ideal, even vs another algorithm that is SIMD capable.

I'm not sure of any other algorithms that would give as good performance for mostly sorted data sets as the insertion sort.

#4 iMalc   Crossbones+   -  Reputation: 2314

Like
1Likes
Like

Posted 04 January 2012 - 11:42 PM

What type is the data (e.g. unsigned int, float, struct...) and what are typical and expected near maximum values on the number of items?
Is it in an array rather than a linked-list?
How often will the data actually be sorted already, and how often will it be nearly sorted?
It might help if you explain where the data comes from.
If I can get enough info from you then I can point you at the optimal sorting algorithm.

I doubt there's much to be gained by trying to do it using SSE though.
"In order to understand recursion, you must first understand recursion."
My website dedicated to sorting algorithms

#5 Antheus   Members   -  Reputation: 2397

Like
1Likes
Like

Posted 05 January 2012 - 08:06 AM

Derive sorting network for insertion sort and implement it as SSE.

Sorting networks get around the lack of branching, but tend to be less efficient.

For general parallelization, something like bitonic sort might be a better fit.

All of these work best on 2^n-sized sub-sections, other sizes may either require padding or differently sized subdivisions, if possible.

For SSE specifically, such methods tend to be best suited for sorting register-sized data (4xint SSE register, for example). Rather than general sorting, they tend to be used for selection or filtering, such as selecting smallest component of a vector, or as preparation pass for next stage. Biggest gain is ability to keep data in SSE registers instead of moving them back and forth for regular processing.

would give as good performance for mostly sorted data sets


Heap sort, merge sort or tim sort. Insertion sort has that painful n^2 common case. Quicksort found in various standard libraries may be implemented as introsort, which should avoid typical qsort problems.

#6 trs79   Members   -  Reputation: 126

Like
0Likes
Like

Posted 05 January 2012 - 11:31 AM

Thanks for the responses, to answer:

What type is the data (e.g. unsigned int, float, struct...) and what are typical and expected near maximum values on the number of items?
Is it in an array rather than a linked-list?
How often will the data actually be sorted already, and how often will it be nearly sorted?
It might help if you explain where the data comes from.
If I can get enough info from you then I can point you at the optimal sorting algorithm.

I doubt there's much to be gained by trying to do it using SSE though.


Basically I'm looking to sort SPH fluid particles. Most of the time, they will be at rest inside of a small round container, with only occasional disturbances. I plan on sorting them with Morton Z-order according to what 3D spatial grid cell they are in, so they'll be spatially sorted inside of memory. I'm currently storing them in an array, and the min and max values should be somewhere around 9 and 25 respectively.

Since the fluid will almost always be stable at rest, I'd say it's sorted probably 90% of the time.

Derive sorting network for insertion sort and implement it as SSE.

Sorting networks get around the lack of branching, but tend to be less efficient.

For general parallelization, something like bitonic sort might be a better fit.

All of these work best on 2^n-sized sub-sections, other sizes may either require padding or differently sized subdivisions, if possible.

For SSE specifically, such methods tend to be best suited for sorting register-sized data (4xint SSE register, for example). Rather than general sorting, they tend to be used for selection or filtering, such as selecting smallest component of a vector, or as preparation pass for next stage. Biggest gain is ability to keep data in SSE registers instead of moving them back and forth for regular processing.

would give as good performance for mostly sorted data sets


Heap sort, merge sort or tim sort. Insertion sort has that painful n^2 common case. Quicksort found in various standard libraries may be implemented as introsort, which should avoid typical qsort problems.


Thanks for the info, the Sorting network sounds interesting. Since the fluids will be 90% sorted I'm trying to optimize for the mostly sorted case, would the sorting network slow things down for that?




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