Author: avg Date: Wed Oct 16 09:20:08 2019 New Revision: 353636 URL: https://svnweb.freebsd.org/changeset/base/353636
Log: MFV r353630: 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 This is a followup to r337567 that imported the ZoL commit directly into FreeBSD. It seems that at the time we did not have some of the earlier changes, so some pieces of the ZoL change were not applicable. Also, the illumos version got a few style cleanups. Some changes were missed or incorrectly merged (e.g., vdev_cache_lastused_compare and metaslab_rangesize_compare). Obtained from: ZoL, illumos MFC after: 25 days X-MFC after: r353634 Modified: head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/ddt.c head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/lz4.c head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/metaslab.c head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/range_tree.c head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/vdev_cache.c head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/vdev_queue.c head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/zfs_rlock.c head/sys/cddl/contrib/opensolaris/uts/common/sys/avl.h Directory Properties: head/cddl/contrib/opensolaris/ (props changed) head/sys/cddl/contrib/opensolaris/ (props changed) Modified: head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/ddt.c ============================================================================== --- head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/ddt.c Wed Oct 16 09:11:49 2019 (r353635) +++ head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/ddt.c Wed Oct 16 09:20:08 2019 (r353636) @@ -768,22 +768,31 @@ ddt_prefetch(spa_t *spa, const blkptr_t *bp) } } +/* + * Opaque struct used for ddt_key comparison + */ +#define DDT_KEY_CMP_LEN (sizeof (ddt_key_t) / sizeof (uint16_t)) + +typedef struct ddt_key_cmp { + uint16_t u16[DDT_KEY_CMP_LEN]; +} ddt_key_cmp_t; + int ddt_entry_compare(const void *x1, const void *x2) { const ddt_entry_t *dde1 = x1; const ddt_entry_t *dde2 = x2; - const uint64_t *u1 = (const uint64_t *)&dde1->dde_key; - const uint64_t *u2 = (const uint64_t *)&dde2->dde_key; + const ddt_key_cmp_t *k1 = (const ddt_key_cmp_t *)&dde1->dde_key; + const ddt_key_cmp_t *k2 = (const ddt_key_cmp_t *)&dde2->dde_key; + int32_t cmp = 0; - for (int i = 0; i < DDT_KEY_WORDS; i++) { - if (u1[i] < u2[i]) - return (-1); - if (u1[i] > u2[i]) - return (1); + for (int i = 0; i < DDT_KEY_CMP_LEN; i++) { + cmp = (int32_t)k1->u16[i] - (int32_t)k2->u16[i]; + if (likely(cmp)) + break; } - return (0); + return (AVL_ISIGN(cmp)); } static ddt_t * Modified: head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/lz4.c ============================================================================== --- head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/lz4.c Wed Oct 16 09:11:49 2019 (r353635) +++ head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/lz4.c Wed Oct 16 09:20:08 2019 (r353636) @@ -259,8 +259,13 @@ lz4_decompress(void *s_start, void *d_start, size_t s_ #undef unlikely #endif +#ifndef likely #define likely(expr) expect((expr) != 0, 1) +#endif + +#ifndef unlikely #define unlikely(expr) expect((expr) != 0, 0) +#endif /* Basic types */ #define BYTE uint8_t Modified: head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/metaslab.c ============================================================================== --- head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/metaslab.c Wed Oct 16 09:11:49 2019 (r353635) +++ head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/metaslab.c Wed Oct 16 09:20:08 2019 (r353636) @@ -1203,9 +1203,6 @@ metaslab_rangesize_compare(const void *x1, const void if (likely(cmp)) return (cmp); - if (r1->rs_start < r2->rs_start) - return (-1); - return (AVL_CMP(r1->rs_start, r2->rs_start)); } Modified: head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/range_tree.c ============================================================================== --- head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/range_tree.c Wed Oct 16 09:11:49 2019 (r353635) +++ head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/range_tree.c Wed Oct 16 09:20:08 2019 (r353636) @@ -164,7 +164,7 @@ range_tree_seg_compare(const void *x1, const void *x2) ASSERT3U(r1->rs_start, <=, r1->rs_end); ASSERT3U(r2->rs_start, <=, r2->rs_end); - + return ((r1->rs_start >= r2->rs_end) - (r1->rs_end <= r2->rs_start)); } Modified: head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/vdev_cache.c ============================================================================== --- head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/vdev_cache.c Wed Oct 16 09:11:49 2019 (r353635) +++ head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/vdev_cache.c Wed Oct 16 09:20:08 2019 (r353636) @@ -114,29 +114,24 @@ static vdc_stats_t vdc_stats = { #define VDCSTAT_BUMP(stat) atomic_inc_64(&vdc_stats.stat.value.ui64); -static int +static inline int vdev_cache_offset_compare(const void *a1, const void *a2) { - const vdev_cache_entry_t *ve1 = a1; - const vdev_cache_entry_t *ve2 = a2; + const vdev_cache_entry_t *ve1 = (const vdev_cache_entry_t *)a1; + const vdev_cache_entry_t *ve2 = (const vdev_cache_entry_t *)a2; - if (ve1->ve_offset < ve2->ve_offset) - return (-1); - if (ve1->ve_offset > ve2->ve_offset) - return (1); - return (0); + return (AVL_CMP(ve1->ve_offset, ve2->ve_offset)); } static int vdev_cache_lastused_compare(const void *a1, const void *a2) { - const vdev_cache_entry_t *ve1 = a1; - const vdev_cache_entry_t *ve2 = a2; + const vdev_cache_entry_t *ve1 = (const vdev_cache_entry_t *)a1; + const vdev_cache_entry_t *ve2 = (const vdev_cache_entry_t *)a2; - if (ve1->ve_lastused < ve2->ve_lastused) - return (-1); - if (ve1->ve_lastused > ve2->ve_lastused) - return (1); + int cmp = AVL_CMP(ve1->ve_lastused, ve2->ve_lastused); + if (likely(cmp)) + return (cmp); /* * Among equally old entries, sort by offset to ensure uniqueness. Modified: head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/vdev_queue.c ============================================================================== --- head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/vdev_queue.c Wed Oct 16 09:11:49 2019 (r353635) +++ head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/vdev_queue.c Wed Oct 16 09:20:08 2019 (r353636) @@ -353,25 +353,15 @@ vdev_queue_type_tree(vdev_queue_t *vq, zio_type_t t) int vdev_queue_timestamp_compare(const void *x1, const void *x2) { - const zio_t *z1 = x1; - const zio_t *z2 = x2; + const zio_t *z1 = (const zio_t *)x1; + const zio_t *z2 = (const zio_t *)x2; - if (z1->io_timestamp < z2->io_timestamp) - return (-1); - if (z1->io_timestamp > z2->io_timestamp) - return (1); + int cmp = AVL_CMP(z1->io_timestamp, z2->io_timestamp); - if (z1->io_offset < z2->io_offset) - return (-1); - if (z1->io_offset > z2->io_offset) - return (1); + if (likely(cmp)) + return (cmp); - if (z1 < z2) - return (-1); - if (z1 > z2) - return (1); - - return (0); + return (AVL_PCMP(z1, z2)); } void Modified: head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/zfs_rlock.c ============================================================================== --- head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/zfs_rlock.c Wed Oct 16 09:11:49 2019 (r353635) +++ head/sys/cddl/contrib/opensolaris/uts/common/fs/zfs/zfs_rlock.c Wed Oct 16 09:20:08 2019 (r353636) @@ -107,14 +107,10 @@ static int rangelock_compare(const void *arg1, const void *arg2) { - const locked_range_t *rl1 = arg1; - const locked_range_t *rl2 = arg2; + const locked_range_t *rl1 = (const locked_range_t *)arg1; + const locked_range_t *rl2 = (const locked_range_t *)arg2; - if (rl1->lr_offset > rl2->lr_offset) - return (1); - if (rl1->lr_offset < rl2->lr_offset) - return (-1); - return (0); + return (AVL_CMP(rl1->lr_offset, rl2->lr_offset)); } /* Modified: head/sys/cddl/contrib/opensolaris/uts/common/sys/avl.h ============================================================================== --- head/sys/cddl/contrib/opensolaris/uts/common/sys/avl.h Wed Oct 16 09:11:49 2019 (r353635) +++ head/sys/cddl/contrib/opensolaris/uts/common/sys/avl.h Wed Oct 16 09:20:08 2019 (r353636) @@ -105,6 +105,13 @@ extern "C" { * as is needed for any linked list implementation. */ +/* + * AVL comparator helpers + */ +#define AVL_ISIGN(a) (((a) > 0) - ((a) < 0)) +#define AVL_CMP(a, b) (((a) > (b)) - ((a) < (b))) +#define AVL_PCMP(a, b) \ + (((uintptr_t)(a) > (uintptr_t)(b)) - ((uintptr_t)(a) < (uintptr_t)(b))) /* * AVL comparator helpers _______________________________________________ svn-src-all@freebsd.org mailing list https://lists.freebsd.org/mailman/listinfo/svn-src-all To unsubscribe, send any mail to "svn-src-all-unsubscr...@freebsd.org"
