Krdytkyu

I was trying to optimize the Radix Sort code, because I never found a code that was simple and easy to understand yet wasn't any slower. I have seen codes on web and in some books that implement arbitrary radices such as 10 and others and also do modulo operation rather than bit-shifting. Those codes however have always been slower that their comparison based counterparts in the same language.

Since Radix Sort runs in $O(n)$ time, I built up my version of Radix Sort which is coded below in C. I choose C language because of speed, however please correct me if I'm going wrong. The code also works for negative numbers too.

I have optimized the code as far as I could go, and maybe I might have missed some more optimization techniques.

Any ideas with which I can increase the execution speed ?

Motivation for optimization:
http://codercorner.com/RadixSortRevisited.htm
http://stereopsis.com/radix.html

I was unable to implement all the optimizations in the articles, as it was beyond my skills and understanding mostly and somewhat lack of sufficient time. Other techniques not included in them or out of the box would definitely help a lot.

This is the pointer optimized version, "long" on my system is 32 bits.

long* Radix_Sort(long *A, size_t N, long *Temp)

{

    long Z1[256] ;

    long Z2[256] ;

    long Z3[256] ;

    long Z4[256] ;

    long T = 0 ;

    while(T != 256)

    {

        *(Z1+T) = 0 ;

        *(Z2+T) = 0 ;

        *(Z3+T) = 0 ;

        *(Z4+T) = 0 ;

        ++T;

    }

    size_t Jump, Jump2, Jump3, Jump4;



    // Sort-circuit set-up

    Jump = *A & 255 ;

    Z1[Jump] = 1;

    Jump2 = (*A >> 8) & 255 ;

    Z2[Jump2] = 1;

    Jump3 = (*A >> 16) & 255 ;

    Z3[Jump3] = 1;

    Jump4 = (*A >> 24) & 255 ;

    Z4[Jump4] = 1;



    // Histograms creation

    long *swp = A + N;

    long *i = A + 1;

    for( ; i != swp ; ++i)

    {

        ++Z1[*i & 255];

        ++Z2[(*i >> 8) & 255];

        ++Z3[(*i >> 16) & 255];

        ++Z4[(*i >> 24) & 255];

    }



    // 1st LSB byte sort

    if( Z1[Jump] == N );

    else

    {

        swp = Z1+256 ;

        for( i = Z1+1 ; i != swp ; ++i )

        {

            *i = *(i-1) + *i;

        }

        swp = A-1;

        for( i = A+N-1 ; i != swp ; --i )

        {

            *(--Z1[*i & 255] + Temp) = *i;

        }

        swp = A;

        A = Temp;

        Temp = swp;

    }



    // 2nd LSB byte sort

    if( Z2[Jump2] == N );

    else

    {

        swp = Z2+256 ;

        for( i = Z2+1 ; i != swp ; ++i )

        {

            *i = *(i-1) + *i;

        }

        swp = A-1;

        for( i = A+N-1 ; i != swp ; --i )

        {

            *(--Z2[(*i >> 8) & 255] + Temp) = *i;

        }

        swp = A;

        A = Temp;

        Temp = swp;

    }



    // 3rd LSB byte sort

    if( Z3[Jump3] == N );

    else

    {

        swp = Z3 + 256 ;

        for( i = Z3+1 ; i != swp ; ++i )

        {

            *i = *(i-1) + *i;

        }

        swp = A-1;

        for( i = A+N-1 ; i != swp ; --i )

        {

            *(--Z3[(*i >> 16) & 255] + Temp) = *i;

        }

        swp = A;

        A = Temp;

        Temp = swp;

    }



    // 4th LSB byte sort and negative numbers sort

    if( Z4[Jump4] == N );

    else

    {

        swp = Z4 + 256 ;

        for( i = Z4+129 ; i != swp ; ++i )

        {

            *i = *(i-1) + *i;

        }

        *Z4 = *Z4 + *(Z4+255) ;

        swp = Z4 + 128 ;

        for( i = Z4+1 ; i != swp ; ++i )

        {

            *i = *(i-1) + *i;

        }

        swp = A - 1;

        for( i = A+N-1 ; i != swp ; --i )

        {

            *(--Z4[(*i >> 24) & 255] + Temp) = *i;

        }

        return Temp;

    }

    return A;

}

I never found a code that was simple and easy to understand yet wasn't any slower

Note the order. Start readable.

Start with What shall this be good for?: (doc)comment your code.

No slower than what? A "well known implementation" for reference and as a base-line would be useful.

Things I liked:

• "non-obvious" code blocks are commented
  
  (short-circuit set-up, negative numbers sort)


• trying to keep the number of passes low


• handling of negative numbers via histogram instead of value manipulation

Dislikes (beyond missing doc comments):

• not declaring the size parameter const N
  
  this would at least hint that the memory pointed to by A and Temp may be modified


• naming
  
  while I like i for index without further significance, I prefer p for a pointer
  
  What is the significance of Z in Z1…4?
  
  case:
  
  assuming capital case OK for arrays: why N, T, Jump1…4?


• naked literals (beyond 0±1)


• repetition
  
  starting with types: have a value type, a histogram type
  
  with "the rearrangement blocks", I'd prefer benchmark/machine code comparisons between


• zeroing memory with open code - use memset(destination, 0, count)
  


• "empty then" instead of inverting the condition


• 
  *(p+e) instead of p[e] (let alone *(e+p)) - without revisiting the standard, I would have denied this was well defined.)


• updating a counter using increment/decrement
  
  I think of those operations as next/previous and use += 1(-= 1) for numerical adjustment


• not using an explicit variable (histogram handling, mostly)


• re. speed: not special-casing "small" arrays

Things I don't want to presume warranted:

• bit operations preferred to ldiv_t ldiv()
  


• bit operations using compile time constants over using parameters (would allow factoring out)


• "walking memory backwards" as fast as "forwards"