Btrfs: compression heuristic: replace heap sort with radix sort
authorTimofey Titovets <nefelim4ag@gmail.com>
Sun, 3 Dec 2017 21:30:33 +0000 (00:30 +0300)
committerDavid Sterba <dsterba@suse.com>
Mon, 22 Jan 2018 15:08:15 +0000 (16:08 +0100)
commit440c840cb49f7de91e68a4cc7bca79a75cd298ae
treeb7ce078a94d53fedc0ea25d77f1345457c0dac61
parent1c3063b6dbfa03e469a53371fae149a022a41bfd
Btrfs: compression heuristic: replace heap sort with radix sort

Slowest part of heuristic for now is kernel heap sort()
It's can take up to 55% of runtime on sorting bucket items.

As sorting will always call on most data sets to get correctly
byte_core_set_size, the only way to speed up heuristic, is to
speed up sort on bucket.

Add a general radix_sort function.
Radix sort require 2 buffers, one full size of input array
and one for store counters (jump addresses).

That increase usage per heuristic workspace +1KiB
8KiB + 1KiB -> 8KiB + 2KiB

That is LSD Radix, i use 4 bit as a base for calculating,
to make counters array acceptable small (16 elements * 8 byte).

That Radix sort implementation have several points to adjust,
I added him to make radix sort general usable in kernel,
like heap sort, if needed.

Performance tested in userspace copy of heuristic code,
throughput:
    - average <-> random data: ~3500 MiB/s - heap  sort
    - average <-> random data: ~6000 MiB/s - radix sort

Signed-off-by: Timofey Titovets <nefelim4ag@gmail.com>
[ coding style fixes ]
Signed-off-by: David Sterba <dsterba@suse.com>
fs/btrfs/compression.c