HomeFreeBSD

10809 Performance optimization of AVL tree comparator functions

Description

10809 Performance optimization of AVL tree comparator functions

illumos/illumos-gate@c4ab0d3f46036e85ad0700125c5a83cc139f55a3
https://github.com/illumos/illumos-gate/commit/c4ab0d3f46036e85ad0700125c5a83cc139f55a3

https://www.illumos.org/issues/10809

Port ZoL ee36c709c3d Performance optimization of AVL tree comparator functions
From the ZoL commit msg:
    perf: 2.75x faster ddt_entry_compare()
    First 256bits of ddt_key_t is a block checksum, which are expected
    to be close to random data. Hence, on average, comparison only needs to
    look at first few bytes of the keys. To reduce number of conditional
    jump instructions, the result is computed as: sign(memcmp(k1, k2)).

    Sign of an integer 'a' can be obtained as: `(0 < a) - (a < 0)` := {-1, 0, 1},
    which is computed efficiently.  Synthetic performance evaluation
    of original and new algorithm over 1G random keys on 2.6GHz
    Intel(R) Xeon(R) CPU E5-2660 v3:
    old     6.85789 s
    new     2.49089 s

    perf: 2.8x faster vdev_queue_offset_compare() and vdev_queue_timestamp_compare()
        Compute the result directly instead of using conditionals

    perf: zfs_range_compare()
        Speedup between 1.1x - 2.5x, depending on compiler version and
        optimization level.

    perf: spa_error_entry_compare()
        `bcmp()` is not suitable for comparator use. Use `memcmp()` instead.

    perf: 2.8x faster metaslab_compare() and metaslab_rangesize_compare()
    perf: 2.8x faster zil_bp_compare()

Portions contributed by: Jerry Jelinek <jerry.jelinek@joyent.com>
Author: Gvozden Neskovic <neskovic@gmail.com>

Details

Provenance
avgAuthored on Oct 16 2019, 8:01 AM
Parents
rG74032c5f3b4b: 10842 Mutex leak in dsl_dataset_hold_obj()
Branches
Unknown
Tags
Unknown

Event Timeline