Chen Guo wrote: > Hi all, Hi Chen,
Thanks for following up. It's been frustrating all around. > I'm looking for some group input/guidance. Is there a kind of > performance goal we want for a threaded sort implementation? Something I > can work towards? Perhaps over-optimistically, I've been hoping for results that indicate higher efficiency. > I submitted a patch earlier, but obviously it had its problems: > copious amounts of copying, worst case n^2, high variance in results, > and in the end it was only slightly faster than the previous threaded > sort patch, and only at 8 threads and up. I've optimized the code further, > but obviously the copying, O(n^2), and variance issues still exist. ... Have you considered writing a program like the one suggested here? http://thread.gmane.org/gmane.comp.gnu.coreutils.bugs/15789/focus=15790 Given a seekable input file, INPUT, you might do this on a quad-core system: sort -m \ <(sort <(dice -k1,4 INPUT)) \ <(sort <(dice -k2,4 INPUT)) \ <(sort <(dice -k3,4 INPUT)) \ <(sort <(dice -k4,4 INPUT)) \ > out Timing that should give us a useful point of reference with which to compare the performance of your multi-threaded sort. Maybe the inefficiency we're seeing is simply unavoidable, given the current algorithms, and we should view the resulting speed-up as a lot better than no speed-up.
