• Timofey Titovets's avatar
    Btrfs: compression heuristic: replace heap sort with radix sort · 440c840c
    Timofey Titovets authored
    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: default avatarTimofey Titovets <nefelim4ag@gmail.com>
    [ coding style fixes ]
    Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
    440c840c
compression.c 42.1 KB