Hi John,
I played the radix sort again during the weekend.
First, I changed my direction and implemented the in-place switching in the other way, where I did a way like
chained-switching.Say starting from item0, for example, switching item0 to item5, then check where item5 should be
switchedto, and makes the switch, till an item is switch to position 0. See my implementation in other-implemation.diff
ifyou are interested in it. This time, I eyeball checked the sort result and confirmed the correction. But my
implementationis slightly slower than your implementation, based on the same test procedure I described in my previous
email,my implementation is roughly ~3% slower your implementation. So I think that at least proves your current
implementationin v5 has been perfectly fine tuned.
Then I went back to read your implementation again, I found a tiny optimization, where we can move “count sorted
partitions”to before the “for” loop, which avoid sorted partition to go through the “for” loop, and my test shows that
themovement may lead to ~1% improvement. See the change in radixsort_tiny_optimizeation.diff.
I also noticed that, there could be cases where target element is already in the right partition, so that switching
couldbe unnecessary. However if we want to avoid such unnecessary switches, then we will need to add a “if” check.
Giventhe total number of such cases is tiny, the “if” check would be more expensive than performing blindly switching.
Itried to add such a check like:
```
if (offset == (size_t) (st - begin))
continue; /* already in correct position */
```
With my test, it just makes the query ~3% slower.
So, now I think I can wrap up this round of playing. My only suggestion is radixsort_tiny_optimizeation.diff. I may
revisitthis patch again once you make the entire patch set ready for review.
Best regards,
--
Chao Li (Evan)
HighGo Software Co., Ltd.
https://www.highgo.com/
