Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Make LSD radix sort faster with software write-combining #12

Open
Bulat-Ziganshin opened this issue Jul 2, 2018 · 0 comments
Open

Make LSD radix sort faster with software write-combining #12

Bulat-Ziganshin opened this issue Jul 2, 2018 · 0 comments

Comments

@Bulat-Ziganshin
Copy link

Bulat-Ziganshin commented Jul 2, 2018

Naive code: https://github.com/Bulat-Ziganshin/MT-LZ/blob/master/RadixSort.cpp#L38
Speed - 19 MKeys/s: https://github.com/Bulat-Ziganshin/MT-LZ/blob/master/results.txt#L377

Optimized code: https://github.com/Bulat-Ziganshin/MT-LZ/blob/master/RadixSort.cpp#L51
Speed - 94 MKeys/s: https://github.com/Bulat-Ziganshin/MT-LZ/blob/master/results.txt#L329

Speed measured on 100M 32-bit uniform keys, sorted by 4 passes of 256-bucket sort, using single core of i7-4770: https://github.com/Bulat-Ziganshin/MT-LZ/blob/master/TestRadixSort.cpp

The optimized code combines data into 64-byte packets stored in temporary buffer, and then writes whole packet into output bucket. This improves TLB usage efficiency and avoids hardware write-combining, thus improving resulting speed (for my code and my computer) 5 times!

@Bulat-Ziganshin Bulat-Ziganshin changed the title Make LSD radix sort faster by employing write-combining trick Make LSD radix sort faster with software write-combining Jul 2, 2018
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant