Bytes and bytesarrays can be sorted with a much faster count sort.

[rhpvorderman]

BPO	45902
Nosy	@malemburg, @tim-one, @rhettinger, @gpshead, @mdickinson, @vstinner, @ericvsmith, @markshannon, @serhiy-storchaka, @1st1, @rhpvorderman

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2021-11-28.02:10:28.051>
created_at = <Date 2021-11-26.09:36:30.590>
labels = ['expert-C-API', 'type-feature', '3.11']
title = 'Bytes and bytesarrays can be sorted with a much faster count sort.'
updated_at = <Date 2021-11-29.14:05:45.629>
user = 'https://github.com/rhpvorderman'

bugs.python.org fields:

activity = <Date 2021-11-29.14:05:45.629>
actor = 'lemburg'
assignee = 'none'
closed = True
closed_date = <Date 2021-11-28.02:10:28.051>
closer = 'gregory.p.smith'
components = ['C API']
creation = <Date 2021-11-26.09:36:30.590>
creator = 'rhpvorderman'
dependencies = []
files = []
hgrepos = []
issue_num = 45902
keywords = []
message_count = 15.0
messages = ['407032', '407033', '407034', '407040', '407041', '407042', '407043', '407059', '407073', '407075', '407150', '407170', '407181', '407244', '407275']
nosy_count = 11.0
nosy_names = ['lemburg', 'tim.peters', 'rhettinger', 'gregory.p.smith', 'mark.dickinson', 'vstinner', 'eric.smith', 'Mark.Shannon', 'serhiy.storchaka', 'yselivanov', 'rhpvorderman']
pr_nums = []
priority = 'normal'
resolution = 'rejected'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue45902'
versions = ['Python 3.11']

[rhpvorderman]

Python now uses the excellent timsort for most (all?) of its sorting. But this is not the fastest sort available for one particular use case.

If the number of possible values in the array is limited, it is possible to perform a counting sort: https://en.wikipedia.org/wiki/Counting_sort. In a counting sort each value maps to an integer corresponding to its relative value. The values are then counted by using key = map_to_key(value); count_array[key]. Then from this count_array a new array of sorted values can be constructed. (See the wikipedia article for a more detailed explanation).

For the python bytes and bytesarray types this is extremely simple to implement. All 256 possible values are can be directly used as keys.

Rough implementation:

• Use buffer protocol to get pointer to bytes/bytesarray internal c-string
• Declare a count_array: Py_ssize_t[256] count_array . (use memset to set it to 0)
• Iterate over the c-string and add each value to the countarray. count_array[buffer[i]] += 1
• Allocate a new bytes(array) object, or in the case of bytesarray the sorting can be performed inplace when bytesarray.sort() is used.
• Iterate over the count_array. Get the number of values for each key and use memset to insert the sequences of keys into position.

The most obvious way to implement this algorithm will be as bytesarray.sort() where it is sorted inplace and as bytes.sort() which returns a new sorted bytes object. This is much much faster than using bytes(sorted(bytes)).

I made a quick cython implementation for speed testing here: https://github.com/rhpvorderman/bytes_sort/blob/main/bytes_sort.pyx

Currently to get a sorted bytestring one has to do bytes(sorted(my_bytes)).

Test results:

# First make sure there is no regression when sorting an empty string
$ python -m timeit -c "from bytes_sort import bytes_sort" "bytes(sorted(b''))"
500000 loops, best of 5: 560 nsec per loop
$ python -m timeit -c "from bytes_sort import bytes_sort" "bytes_sort(b'')"
500000 loops, best of 5: 565 nsec per loop

# Test result for very small strings
$ python -m timeit -c "from bytes_sort import bytes_sort" "bytes(sorted(b'abc'))"
500000 loops, best of 5: 628 nsec per loop
$ python -m timeit -c "from bytes_sort import bytes_sort" "bytes_sort(b'abc')"
500000 loops, best of 5: 578 nsec per loop

# Even on a very small already sorted string, a counting sort is faster.

# Test with a proper string
$ python -m timeit -c "from bytes_sort import bytes_sort" "bytes(sorted(b'Let\'s test a proper string now. One that has some value to be sorted.'))"
100000 loops, best of 5: 2.32 usec per loop
$ python -m timeit -c "from bytes_sort import bytes_sort" "bytes_sort(b'Let\'s test a proper string now. One that has some value to be sorted.')"
500000 loops, best of 5: 674 nsec per loop

More than three times faster!

[rhpvorderman]

Also I didn't know if this should be in Component C-API or Interpreter Core. But I guess this will be implemented as C-API calls PyBytes_Sort and PyByteArray_SortInplace so I figured C-API is the correct component here.

[rhpvorderman]

I changed the cython script a bit to use a more naive implementation without memset.
Now it is always significantly faster than bytes(sorted(my_bytes)).

$ python -m timeit -c "from bytes_sort import bytes_sort" "bytes_sort(b'')"
500000 loops, best of 5: 495 nsec per loop
$ python -m timeit -c "from bytes_sort import bytes_sort" "bytes_sort(b'abc')"
500000 loops, best of 5: 519 nsec per loop
$ python -m timeit -c "from bytes_sort import bytes_sort" "bytes_sort(b'Let\'s test a proper string now. One that has some value to be sorted.')"
500000 loops, best of 5: 594 nsec per loop

[rhpvorderman]

Sorry for the spam. I see I made a typo in the timeit script. Next time I will be more dilligent when making these kinds of reports and triple checking it before hand, and sending it once. I used -c instead of -s and now all the setup time is also included. This confounds the results.

The proper test commands should be:

python -m timeit -s "from bytes_sort import bytes_sort, bytearray_sort_inplace" "bytes_sort(b'My string here')"

python -m timeit "bytes(sorted(b'My string here'))"

Using just sorted, to purely compare the sorting algorithms without the overhead of creating a new bytes object.
python -m timeit "sorted(b'My string here')"

Correct comparison results
# String = b''
using bytes(sorted: 188 nsec
using sorted: 108 nsec
using byte_sort: 125 nsec # Some overhead here, setting up the countarray
# String = b'abc'
using bytes(sorted: 252 nsec
using sorted: 145 nsec
using byte_sort: 136 nsec # Overhead compared to sorted already negated when sorting 3 items(!)
# String = b'Let\'s test a proper string now. One that has some value to be sorted.'
using bytes(sorted: 1830 nsec (reported as 1.83 usec)
using sorted: 1550 nsec (reported as 1.55 usec)
using byte_sort: 220 nsec

[mdickinson]

Can you give example use-cases for sorting a bytes or bytearray object? I see value in the intermediate object - the frequency table, but the reconstructed sorted bytes object just seems like an inefficient representation of the frequency table, and I'm not sure how it would be useful.

As the wikipedia page for counting sort says, the real value is in sorting items by keys that are small integers, and the special case where the item is identical to the key isn't all that useful:

In some descriptions of counting sort, the input to be sorted is assumed to be more simply a sequence of integers itself, but this simplification does not accommodate many applications of counting sort.

[mdickinson]

(Changing the issue type: as I understand it, this is a proposal for a new feature, namely new methods bytes.sort and bytearray.sort, rather than a performance improvement to an existing feature.)