I am working on making sorting of strings faster. The progress so far is that I can sort strings of 8 bytes in size as fast as radixsort in R (which is the fastest algorithm to sort strings found in the R/Python/Julia-verse). The first set of demo code can be found in the README of FastGroupBy.jl w…

R’s Internals documentation discusses how R stores the strings and they do use some kind of “cache/look up” table for their strings; probably to save on RAM usage. So it’s not really fair to compare to the R implementation yet.

[image] xiaodai: discusses how R stores the strings and they do use some kind of “cache/look up” table for their strings; probably to save on RAM usage. Two potential advantages are lower RAM usage, and very fast comparison because strcmp becomes a pointer comparison rather than character-by-…

[image] xiaodai: By the way what’s the most efficient way to swap around the last 1-8 bits with the 9-16 bits so that the bit order is now 9-16, 1-8, instead of 1-8, 9-16 e.g. Use bswap(value), it usually ends up being a single instruction (rolw, bswapl, bswapq)

there is also ntoh for endiness conversion. i will test them out

Those are just synonyms for bswap, such that if you use hton, on a little-endian host, it will convert it to network order (i.e. bigendian), but on a big-endian host, it’s a no-op. You should use hton not ntoh though, just to keep the semantics correct, even though functions end up being the same o…

I have made some improvements to string sorting and have made a PR to SortingAlgorithms.jl See https://github.com/JuliaCollections/SortingAlgorithms.jl/pull/27

I will take a rest on string sorting now and focus on string-grouping instead.

First draft of the blog post about string sorting https://www.codementor.io/zhuojiadai/draft/f57tf9f8s

Great! My two cents: I’d mention the fact that R uses string interning directly when presenting the results. People may not read the full post, or may just skip it, in which case they will not understand the full story. Also, interning strings requires an additional computation step that is not acc…

WIP: faster string sort

Internals & Design

xiaodai December 29, 2017, 12:39am 51

It will be really good if I can get some help with the following posts. It will help me create a faster pure Julia string sorting algorithm

Assign values in user-defined primitive type

bswap_int for user-defined primitive type

Topic		Replies	Views
Progress towards faster `sortperm` for Strings Data performance , sortperm	16	4713	January 29, 2018
Request for comments: a roadmap to faster sort() for primitive types using RadixSort Internals & Design sort	32	3574	November 14, 2021
Ironic observation about `sort` and `sortperm` speed for "small integers" vs R Performance sort , sortperm , r	32	4841	February 4, 2018
[ANN]: WIP Strs.jl package ready for alpha review and testing Community	15	3344	April 3, 2018
Is `Vector{UInt8}(string)` the fastest way to convert String to bytes? Performance	19	4765	December 10, 2017

WIP: faster string sort

Related topics