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

Fast String sorting #6

Open
VS-ux opened this issue Sep 5, 2020 · 1 comment
Open

Fast String sorting #6

VS-ux opened this issue Sep 5, 2020 · 1 comment

Comments

@VS-ux
Copy link

VS-ux commented Sep 5, 2020

I am trying to find the fastest way to sort strings (actually an array of ascii byte*), and have came across https://www.codeproject.com/articles/146086/fast-string-sort-in-c-and-f. It works very well for me. However, it only utilizes a single thread (it uses multikey-quicksort). I tried to use HPCsharps parallel merge sort with the same data, however, on a 24-thread system, it was only slightly faster than the codeproject article mentioned. I was wondering if there was an even faster way to sort an array of byte* pointing to ASCII text, preferably parallel.

Sorry if this is a bad place to put it.
Thanks

@DragonSpit
Copy link
Owner

DragonSpit commented Sep 25, 2020

Would you mind posting your benchmark? There are a couple of thresholds that have been optimized for sorting arrays of integers, which most likely need changed for sorting an array of strings (array of ascii byte pointers).
Another idea is to place all string (byte*'s) in an array and hand these to a sorting algorithm. This reduces random memory accesses, due to strings being scattered randomly in system memory, which slows performance down significantly. You could then provide an array of strings to the sort algorithm, and an array of starting addresses and lengths.
Let me know if you can sponsor this further work.

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

2 participants