Radix Sort speed improvement

Question

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;
}

• chux: Note: Why is Radix Sort O(n)? goes into some details about the O() for radix sort.
• ytoamn: @chux Radix Sort takes O( d(n+k) ) where "d" is number of digits as per the base "k" in the maximum value in the list, typically "d" is 4 for 32 bit numbers as 4 passes are performed ( if K is 256 ), clever implementations will skip passes if all nth LSBs are same, "d" depends on K, in order to fit the histogram in L1 cache K is often taken 256, so if n is >= 200 then only Radix Sort will run in O(n) time. For arrays of small sizes, it will run in O(nlogn) or even worse O(n2). The "K" has to be chosen carefully. This is only for 32-bit numbers. You can extend the same analysis to 64-bits too.
• chux: Note: sort fails with long as 64-bit. Good code get ported to other platforms than the ones used today.
• ytoamn: @chux You say today's code aren't good enough ? Why ? and it would fail for 64 bits ? How ? Instead of making claims without backed up proofs, at least contribute to the knowledge, share such codes if you know them, otherwise whats the use of hankering all that knowledge ? Post relevant comments that would help get an answer, otherwise no need for you to review.
• chux: Post requests an increase in the execution speed (assuming 32-bit) and not a portability review. Given that viewers of this code may not see that code fails with a 64-bit long with long *A with only 4 Z arrays, I felt a small note to high-light that ancillary concern was sufficient. Should a portability review be desired, recommended that post is amended to include that goal.

Answer 1

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"

• greybeard: (Dang. Wanted to have looked up how to check "overlap between A and Temp" - one should at least check for NULL/&equality.)