Would be beneficial Tail Heapsort for SPARK

I just saw the heaposort algorithm in SPARK, by arrangin few variables I was able to speed it up, then I realized that it is still recursive, would be beneficial make it TAIL RECURSIVE?

(to make it tail recursive is just sufficient that the function call itself exactly once and that the call is the last instruction)

current fastest code I have in place of SPARK's heapsort:

("array" is a variable just declared in the CPP file)

Code:

//slightly changed version
void Sorter::innerSortPoints(index start, index end)
    {
        index i = start - 1;
        index j = end + 1;

        const Point pivot = array[(start + end) >> 1];
        while (true)
        {
            do ++i;
            while (array[i] > pivot); //point have overloaded ">"
            do --j;
            while (array[j] < pivot); //point have overloaded "<"
            if (i < j)
            {
                const Point a = array[i];
                array[i] = array[j];
                array[j] = a;
            }
            else break;
        }
     
        if(start < j)
            innerSortPoints(start,j);

        j++;
        if(j<end)
            innerSortPoints(j,end);
    }


void Sorter::sortPoints( index start, index end, Point * _array)
    {
        array= _array;
        if(start>end)
        {
            index temp = start;
            start = end;
            end = temp;
        }

        innerSortPoints(end,start);

        array= 0;
    }

the tail recursive alternative (compiler will automatically convert the function from recursive call to loop, and optionally can unroll it, etc.. many reasons why loop perform better than recursive call)

Code:

//tail recursive version
        index i = start - 1;
        index j = end + 1;

        const Point pivot = array[(start + end) >> 1];
        while (true)
        {
            do ++i;
            while (array[i] > pivot);
            do --j;
            while (array[j] < pivot);
            if (i < j)
            {
                const Point a = array[i];
                array[i] = array[j];
                array[j] = a;
            }
            else break;
        }
        //only last part change, variables rearranged so that InnerSort is called just once.
        i = j;                 
        bool quit=false;
        if(start>=j)
        {
            i=end;
            start=j++;
            quit =( j>=end );
        }
       
        if(quit)
            return;
           
        innerSortPoints(start,i);

I'm trying to write a loop that can also be automatically be vectorized without explicit usage of SIMD instructions. Hope you like it actually GCC can't still vectorize the loop

Hi yes of course having a method being tail recursive is always beneficial in term of performance (and stack size).
No optimization effort were made on the sort algorithm so far... I ll take a look on what you made ! Thanks a lot.
Moreover if you want to use simd instructions explicitely, use intrinsics with a define (as not all platform may support that).

thanks hope it works correctly for spark too for intrinsics I don't know. I prefer let the compiler deal with them by autovectorization. I dislike having strange instructions in the code since most people don't understand them

Apart from that, it is a quicksort not a heap sort in spark I think. However the quick sort (and the heap sort as well) algorithm does not take advantage of the fact the particles are likely to be nearly sorted from frame to frame (in a usage with not that much particles spawning each frame and the camera moving smoothly). Maybe using a smoothsort or something like that may improve performance as well...

I m not sure compilers perform well at autovectorization. I made some tests some time ago and it was not that good.

Ah I didn't looked at algorithm, I just saved it as "quik_heapsort_from_spark.cpp" probably wrong name, anyway the optimization was not in the algorithm but just in variables, so is fine anyway..

well if you are looking for different algorithms you should look at

INSERTION SORT => O(N) for nearly sorted items (like particles between frames) even wehen quicksort was taking several milliseconds with insertion sort I had very few milliseconds or no measurable time with conventional clocks.


I think that 1 QUICK_SORT every second and INSERTION SORT every frame would be much better


(insertion sort can be easily limited in complexity so that there are no troubles if camera is fast moving through particles or particles are fast moving themselves).


Much better then I will not lose time with autovectoriazion anymore (just started few days ago) XD

Yep another possibility is a quicksort on the whole array backed to an simpler sort when the range become small (insertion or selection). I think this is what is used in most implementation of the STL sort. Using only an insertion sort will be too situational as even if it will perform well for nearly sorted data it will be terrible for arbitrary one (O(n²)).

says that Partial ordering of particles can be measured (entropy). You can exactly know when you must use quicksort or then you can use insertion sort.

At first frame you assume max entropy because you don't know its value.

When quicksort is used, => entropy = 0.


Then while particles system evolves you add entropy (every modifier can add its own entropy, mainly based on CAmera/PARTICLE speed,).

Insertion sort worst case is N^2, but you can easily limit the number of iterations to say.. 3*N.

if insertion sort ends withtin 3*N cycles then you set entropy to 0.

If it does not end you set entropy to maximum.


In certain situations you can already add a great amount of entropy,

for example if you know average particle system density and average distance travelled by each particle you know how likely particles are to become RANDOMLY (not necessary known every particle, just need to know modifiers) sorted and so you can add an exact amount of entropy based on statistical evidence


And this is not DIVIDE ET IMPERA algorithm, is just matter of deciding wich one of two very simple algorithms to use, so is far more maintenable than a STL solution like

I love those kind of heuristics !

However, even if it can work quite well to derive the best sort algorithm, good results will depend mainly on how well the entropy can be estimated.

And estimating this entropy well can add a lot of overhead and complexity. I dont want the entropy computation to leak everywhere in the code, it must remain local.

One thing that can be made is to take into account only inserted particles and compare this to the total of particles, assuming an inserted particle will not be correctly sorted. This ratio serves to estimate the entropy. This can be easily performed into Group class with no overhead. Camera position can also be taken into account to weight this ratio. But taking the particles speed into account may be more difficult...

Another possibility is to get info from the sorts at previous frames but it may lead to incorrect results.

Anyway this is an interesting discussion. I know the sort in spark is not optimized and we can do better.
If you re interested I can make you a commiter on svn.

oh dear ... I have to reinstall SVN tortoise, but I'd be honored to join the crew


edit:

the tail-recursive version code I posted does not work, by the way I'm sure quicksort can be implemented without recursion.