Advanced array sorting

[Alesk]

Hi,

I have a big array of classes to sort. I would like to split this sorting across multiple execution cycles and limit it to a portion of my array.

Say I have 10000 instances of my class in the array, and I would like to sort only the first 4000 instances upon a given attribute of the class, in 5 cycles.

What would be the fastest approach to do that ?

[Marrrk]

Iam as far from beeing a algorithm pro, but I implemented some time ago sorting on the GPU, which, as you want it, sorts in multiple cycles. Maybe thats something you might be interested in:

http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter46.html

Everything is doable outside of the GPU. But wouldnt you be better off with some multithreaded solution or do you need the results before its completely sorted? (The methods in my link are not good for intermediate results).

[Alesk]

I’m quite new to Unity and I didn’t know it has multithreading ^^ (is it a cross-platform solution ?)

I’m interested in both solutions (gpu and multithreading)
Intermediate results might be useful too, but are not my priority.

So, if you have any piece of code to share, I’m really interested

EDIT : ha, no, after reading your link, I’m really interested by intermediate results, since I’m working on particles depth sorting !

[tomvds]

For the best advice, it would help if you would explain a bit more about your array. For example, how is it constructed? Is it a list of objects that has objects added and removed over time? If that’s the case, you probably don’t need to sort the entire array, but could use a sorted list or similar sorted data structure. Or is it a brand new array of objects you receive every time? Will you use the partially sorted array and if you do, are there requirements for it (for instance, do those 4k sorted instances from your example need to be the first 4k of the final result)?

[Alesk]

I’m sorting billboard particles.

here is a sample of my current code :

private void DepthSort(){
	if(pVisibleCount>0){
		SortedParticles = new sortIndex[pVisibleCount];
		pSortedCount = 0;
		
		for(int i = 0; i < pCount; i++) {
			if(CustomParticlesArray[i].render){
				SortedParticles[pSortedCount] = new sortIndex(i,CustomParticlesArray[i].depth);
				pSortedCount++;
			}
		}
		System.Array.Sort(SortedParticles, new DepthComparison());
	}
}

public class sortIndex{
	public int index = 0;
	public float order = 0f;
	
	public sortIndex(int i, float o){
		index = i;
		order = o;
	}
}

public class DepthComparison: System.Collections.IComparer{
	public DepthComparison(){}

	public int Compare(object Object1, object Object2) { 
		if (((sortIndex) Object2).order<((sortIndex) Object1).order){
			return -1;
		}
		return 1; 
	}
}

I would like to not have to recreate the SortedParticles array each time, but since the count of visible particles may vary from a render to another, I have to recreate it.
Before sorting the particles, I have a first pass wich eliminates all the particles out of camera view, to have less stuff to sort…

[EDIT] details :

For the best advice, it would help if you would explain a bit more about your array. For example, how is it constructed?

private CustomParticle[ ] CustomParticlesArray;

Is it a list of objects that has objects added and removed over time?

for now it’s a static count array

If that’s the case, you probably don’t need to sort the entire array, but could use a sorted list or similar sorted data structure.

I’m not sure how to get a sorted list working with classes

Or is it a brand new array of objects you receive every time?

Since the depth of each particle may vary from frame to frame, then yes… it can be a brand new array

Will you use the partially sorted array and if you do, are there requirements for it (for instance, do those 4k sorted instances from your example need to be the first 4k of the final result)?

My current idea is like that :

1. define the maximum count of particle in the array
   → CustomParticlesArray[10000]

2. set the same maximum count for the sorting array
   → SortedParticles[10000]

3. tag particles in CustomParticlesArray as visible or not (with camera frutsum test)

4. update SortedParticles entries with only the N visible particles informations (index in CustomParticlesArray and depth)
   (3 and 4 could be done in a single loop)

5. sort SortedParticles only on the first N entries representing visible particles
   (and if possible spread this sorting across multiple cycles)

EDIT2 : by not recreating the SortedParticles array each time, I’m sparing a costly garbage collector pass

[tomvds]

First of all, I would probably move away from using built-in arrays for this. Creating a new array so often will be very taxing on the garbage collector. Try using a List<> instead. You could define this list as a member variable and Clear() it instead of creating a new one all the time. You could then also use an IComparer, which would save some casting during the sorting.

Also I can’t help but wonder why you need this in the first place. Is the built-in particle system not good enough for your needs? If it isn’t, are you certain you can’t obtain that same functionality using the Unity particle renderer with a custom animator?

[Alesk]

@tomvds

First of all, I would probably move away from using built-in arrays for this. Creating a new array so often will be very taxing on the garbage collector. Try using a List<> instead. You could define this list as a member variable and Clear() it instead of creating a new one all the time. You could then also use an IComparer, which would save some casting during the sorting.

Ok, I was unsure about this, but then clearing and refilling the list will not be also heaving stuff for the garbage collector ?
EDIT : Could you please give me a sample code of this being done with Lists ? I’m not sure of the syntax…

@tomvds

Also I can’t help but wonder why you need this in the first place. Is the built-in particle system not good enough for your needs? If it isn’t, are you certain you can’t obtain that same functionality using the Unity particle renderer with a custom animator?

I’m doing some more special processing on the particles that cannot be done easily with the built-in particle system.

[anon_19585093]

	List<Particle> particles = new List<Particle>();
	particles.Add(new Particle());
	ParticleComparer pComparer = new ParticleComparer();
	particles.Sort(pComparer);
	

	public class ParticleComparer : IComparer<Particle>
	{
		public int Compare(Particle a, Particle b)
		{
			return a.size.CompareTo(b.size);
		}
	}

I just used the built in Particle class so I could verify that my syntax was correct… There’s no reason why you couldn’t do this on 10000 objects every frame without any problem as far as I can tell.

Sorting them shouldn’t be the problem really, but calculating their “depth” is probably what will hurt you if you need to be exact. If you are calculating distance from the camera or something make sure to use sqrMagnitude and not magnitude as your depth value.

[Alesk]

@anon_19585093

I just used the built in Particle class so I could verify that my syntax was correct… There’s no reason why you couldn’t do this on 10000 objects every frame without any problem as far as I can tell.

Thanks for this example, but since I’m using a custom class instead of Particles, I got an error message on that line :

public class OrderComparer : IComparer<sortIndex>

Error message = error CS0308: The non-generic type `System.Collections.IComparer’ cannot be used with the type arguments
What changes should I do to my sortIndex class to fix this problem ?

@anon_19585093

Sorting them shouldn’t be the problem really, but calculating their “depth” is probably what will hurt you if you need to be exact. If you are calculating distance from the camera or something make sure to use sqrMagnitude and not magnitude as your depth value.

I used the profiler to detect the heavier task, and sorting was way beyond the depth calculation (where I’m already using the sqrMagnitude value ;))

[tomvds]

You will need to add the generic namespace to your script:
using System.Collections.Generic;

Or use System.Collections.Generic.List<> and System.Collections.Generic.IComparer<>.

[Alesk]

@tomvds

You will need to add the generic namespace to your script:
using System.Collections.Generic;

ouch, I’m such a noob >_<

So, it’s working like a charm now, and the sorting stuff dropped from 27ms to around 10ms (for 10000 particles) Thanks !

But that’s still too slow (for me), since I’ll have of course many more things than only particles in my game

FYI, here is a bench on the time consumed for each step of the sort processing (for 10000 particles)

With builin array :
Depth computing : 0.45 ms
Array filling : 1.68 ms
Array sorting : 25 ms

With List :
Depth computing : 0.45 ms
List filling : 1.77 ms
List sorting : 9 ms

I’ve got something in mind to split this over more than one cycle, I’ll let you know if that’s working soon ^^

[tomvds]

Reading back your code, I would also change SortIndex to a struct instead of a class, that could also save you a lot of memory (and possibly performance). Structs, unlike classes, are not allocated in main memory, but instead kept on the stack and behave like built-in types like int and float, copying by value instead of reference.

[Alesk]

@tomvds

Reading back your code, I would also change SortIndex to a struct instead of a class, that could also save you a lot of memory (and possibly performance). Structs, unlike classes, are not allocated in main memory, but instead kept on the stack and behave like built-in types like int and float, copying by value instead of reference.

Example please ? (sorry)

[tomvds]

public [B]struct[/B] sortIndex
{
	public int index = 0;
	public float order = 0f;
	
	public sortIndex(int i, float o)
        {
		index = i;
		order = o;
	}
}

If you don’t rely on comparing references, that’s all that you need to make it work.

[andeeeee]

OK, a few things spring to mind here…

There are algorithms, most notably Heapsort, that generate the sorted array one item at a time in the correct order. Consequently, you can just stop execution wherever you want and be sure that the items already returned are the first n items of the final sorted order. It is also possible to use a modified version of Quicksort that does less work when you don’t need to sort the whole array. If the portion on the right side of the pivot element is completely within the section of array that you don’t need to sort then you can just ignore it rather than running Quicksort recursively on it.

Another useful thing to know is that merging lists that are already sorted is much faster than dumping all the elements into one array and sorting again from scratch. You could use System.Array.Sort on several sections of the list (over a few frames) then merge the sections together quite efficiently.

[Alesk]

Thanks ^^

In fact I had to simplify it a bit more to get it working :

public struct sortIndex{
	public int index;
	public float order;
}

I’m now down to 6ms for 10000 particles on the depth sorting stuff ^^

[Alesk]

@andeeeee

OK, a few things spring to mind here…

There are algorithms, most notably Heapsort, that generate the sorted array one item at a time in the correct order. Consequently, you can just stop execution wherever you want and be sure that the items already returned are the first n items of the final sorted order. It is also possible to use a modified version of Quicksort that does less work when you don’t need to sort the whole array. If the portion on the right side of the pivot element is completely within the section of array that you don’t need to sort then you can just ignore it rather than running Quicksort recursively on it.

Thank you, I’ll have a look at this stuff

@andeeeee

Another useful thing to know is that merging lists that are already sorted is much faster than dumping all the elements into one array and sorting again from scratch. You could use System.Array.Sort on several sections of the list (over a few frames) then merge the sections together quite efficiently.

This is exactly what I had in mind to split the processing over multiple frames.
But how would you merge the the sections ? Does exists a built-in function, or should I do this myself ?

[andeeeee]

I don’t think there is a suitable merge function in the Mono library but it is quite straightforward to implement yourself. You need an integer for each sublist to mark the “top” element from each. Then, you just repeatedly look through all the top elements and take the highest in the sort order each time to add to the main list.

[Alesk]

ok, I was thinking to something like that
thanks ^^

[Alesk]

Hi

The sort split is working pretty well, and I’ve even found a solution here http://forum.unity3d.com/threads/90128-Unity-Threading-Helper to get it work over a single frame update instead of spreading it over time.

With 3 threads, I get around of 3ms of sorting time for an array with 16000 entries, instead of 8 or 9ms when sorting the full array in one row.