Project

General

Profile

Bug #10809

Performance optimization of AVL tree comparator functions

Added by Jerry Jelinek 8 months ago. Updated 7 months ago.

Status:
Closed
Priority:
Normal
Assignee:
Category:
zfs - Zettabyte File System
Start date:
2019-03-19
Due date:
% Done:

100%

Estimated time:
Difficulty:
Medium
Tags:

Description

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()
    perf: 2.8x faster mze_compare()
    perf: faster dbuf_compare()
    perf: faster compares in spa_misc
    perf: 2.8x faster layout_hash_compare()
    perf: 2.8x faster space_reftree_compare()
    perf: libzfs: faster avl tree comparators
    perf: guid_compare()
    perf: dsl_deadlist_compare()
    perf: perm_set_compare()
    perf: 2x faster range_tree_seg_compare()
    perf: faster unique_compare()
    perf: faster vdev_cache _compare()
    perf: faster vdev_uberblock_compare()
    perf: faster fuid _compare()
    perf: faster zfs_znode_hold_compare()


Related issues

Blocks illumos gate - Bug #10566: Multiple DVA Scrubbing FixIn Progress2019-03-19

Actions

History

#1

Updated by Electric Monk 7 months ago

git commit c4ab0d3f46036e85ad0700125c5a83cc139f55a3

commit  c4ab0d3f46036e85ad0700125c5a83cc139f55a3
Author: Gvozden Neskovic <neskovic@gmail.com>
Date:   2019-04-26T19:13:48.000Z

    10809 Performance optimization of AVL tree comparator functions
    Portions contributed by: Jerry Jelinek <jerry.jelinek@joyent.com>
    Reviewed by: Richard Elling <richard.elling@gmail.com>
    Reviewed by: Brian Behlendorf <behlendorf1@llnl.gov>
    Reviewed by: Toomas Soome <tsoome@me.com>
    Reviewed by: Robert Mustacchi <rm@joyent.com>
    Approved by: Richard Lowe <richlowe@richlowe.net>

#2

Updated by Joshua M. Clulow 7 months ago

  • Blocks Bug #10566: Multiple DVA Scrubbing Fix added
#3

Updated by Joshua M. Clulow 7 months ago

  • Status changed from New to Closed
  • % Done changed from 90 to 100
  • Tags deleted (needs-triage)
#4

Updated by Joshua M. Clulow 7 months ago

  • Description updated (diff)

Also available in: Atom PDF