|
23 | 23 |
|
24 | 24 | #include HDR_MALLOC_INCLUDE |
25 | 25 |
|
| 26 | +/* Prefetch hint for upcoming write access */ |
| 27 | +#if defined(__GNUC__) || defined(__clang__) |
| 28 | +# define HDR_PREFETCH_WRITE(addr) __builtin_prefetch((addr), 1, 3) |
| 29 | +# define HDR_LIKELY(x) __builtin_expect(!!(x), 1) |
| 30 | +# define HDR_UNLIKELY(x) __builtin_expect(!!(x), 0) |
| 31 | +#else |
| 32 | +# define HDR_PREFETCH_WRITE(addr) ((void)(addr)) |
| 33 | +# define HDR_LIKELY(x) (x) |
| 34 | +# define HDR_UNLIKELY(x) (x) |
| 35 | +#endif |
| 36 | + |
| 37 | +/* Runtime-dispatched AVX2 path: keep the rest of this TU at the project's |
| 38 | + baseline ISA so the shipped binary does not silently require AVX2. */ |
| 39 | +#if (defined(__x86_64__) || defined(_M_X64) || defined(__i386__) || defined(_M_IX86)) \ |
| 40 | + && (defined(__GNUC__) || defined(__clang__)) && !defined(__INTEL_COMPILER) |
| 41 | +# define HDR_HAS_AVX2_DISPATCH 1 |
| 42 | +# include <immintrin.h> |
| 43 | +#endif |
| 44 | + |
26 | 45 | /* ###### ####### ## ## ## ## ######## ###### */ |
27 | 46 | /* ## ## ## ## ## ## ### ## ## ## ## */ |
28 | 47 | /* ## ## ## ## ## #### ## ## ## */ |
@@ -67,24 +86,48 @@ static int64_t counts_get_normalised(const struct hdr_histogram* h, int32_t inde |
67 | 86 | static void counts_inc_normalised( |
68 | 87 | struct hdr_histogram* h, int32_t index, int64_t value) |
69 | 88 | { |
70 | | - int32_t normalised_index = normalize_index(h, index); |
71 | | - h->counts[normalised_index] += value; |
| 89 | + if (HDR_LIKELY(h->normalizing_index_offset == 0)) |
| 90 | + { |
| 91 | + HDR_PREFETCH_WRITE(&h->counts[index]); |
| 92 | + h->counts[index] += value; |
| 93 | + } |
| 94 | + else |
| 95 | + { |
| 96 | + int32_t normalised_index = normalize_index(h, index); |
| 97 | + HDR_PREFETCH_WRITE(&h->counts[normalised_index]); |
| 98 | + h->counts[normalised_index] += value; |
| 99 | + } |
72 | 100 | h->total_count += value; |
73 | 101 | } |
74 | 102 |
|
75 | 103 | static void counts_inc_normalised_atomic( |
76 | 104 | struct hdr_histogram* h, int32_t index, int64_t value) |
77 | 105 | { |
78 | | - int32_t normalised_index = normalize_index(h, index); |
79 | | - |
80 | | - hdr_atomic_add_fetch_64(&h->counts[normalised_index], value); |
| 106 | + if (HDR_LIKELY(h->normalizing_index_offset == 0)) |
| 107 | + { |
| 108 | + HDR_PREFETCH_WRITE(&h->counts[index]); |
| 109 | + hdr_atomic_add_fetch_64(&h->counts[index], value); |
| 110 | + } |
| 111 | + else |
| 112 | + { |
| 113 | + int32_t normalised_index = normalize_index(h, index); |
| 114 | + HDR_PREFETCH_WRITE(&h->counts[normalised_index]); |
| 115 | + hdr_atomic_add_fetch_64(&h->counts[normalised_index], value); |
| 116 | + } |
81 | 117 | hdr_atomic_add_fetch_64(&h->total_count, value); |
82 | 118 | } |
83 | 119 |
|
84 | 120 | static void update_min_max(struct hdr_histogram* h, int64_t value) |
85 | 121 | { |
86 | | - h->min_value = (value < h->min_value && value != 0) ? value : h->min_value; |
87 | | - h->max_value = (value > h->max_value) ? value : h->max_value; |
| 122 | + if (HDR_UNLIKELY(value > h->max_value)) |
| 123 | + { |
| 124 | + h->max_value = value; |
| 125 | + } |
| 126 | + |
| 127 | + if (HDR_UNLIKELY(value != 0 && value < h->min_value)) |
| 128 | + { |
| 129 | + h->min_value = value; |
| 130 | + } |
88 | 131 | } |
89 | 132 |
|
90 | 133 | static void update_min_max_atomic(struct hdr_histogram* h, int64_t value) |
@@ -498,7 +541,7 @@ bool hdr_record_values(struct hdr_histogram* h, int64_t value, int64_t count) |
498 | 541 | } |
499 | 542 |
|
500 | 543 | counts_index = counts_index_for(h, value); |
501 | | - if (counts_index < 0 || h->counts_len <= counts_index) |
| 544 | + if ((uint32_t)counts_index >= (uint32_t)h->counts_len) |
502 | 545 | { |
503 | 546 | return false; |
504 | 547 | } |
@@ -520,7 +563,7 @@ bool hdr_record_values_atomic(struct hdr_histogram* h, int64_t value, int64_t co |
520 | 563 |
|
521 | 564 | counts_index = counts_index_for(h, value); |
522 | 565 |
|
523 | | - if (counts_index < 0 || h->counts_len <= counts_index) |
| 566 | + if ((uint32_t)counts_index >= (uint32_t)h->counts_len) |
524 | 567 | { |
525 | 568 | return false; |
526 | 569 | } |
@@ -665,22 +708,65 @@ int64_t hdr_min(const struct hdr_histogram* h) |
665 | 708 | return non_zero_min(h); |
666 | 709 | } |
667 | 710 |
|
668 | | -static int64_t get_value_from_idx_up_to_count(const struct hdr_histogram* h, int64_t count_at_percentile) |
| 711 | +static int64_t get_value_from_idx_up_to_count_scalar( |
| 712 | + const struct hdr_histogram* h, int64_t count_at_percentile) |
669 | 713 | { |
670 | 714 | int64_t count_to_idx = 0; |
671 | | - |
672 | | - count_at_percentile = 0 < count_at_percentile ? count_at_percentile : 1; |
673 | | - for (int32_t idx = 0; idx < h->counts_len; idx++) |
674 | | - { |
| 715 | + for (int32_t idx = 0; idx < h->counts_len; idx++) { |
675 | 716 | count_to_idx += h->counts[idx]; |
676 | 717 | if (count_to_idx >= count_at_percentile) |
677 | | - { |
678 | 718 | return hdr_value_at_index(h, idx); |
679 | | - } |
680 | 719 | } |
| 720 | + return 0; |
| 721 | +} |
681 | 722 |
|
| 723 | +#ifdef HDR_HAS_AVX2_DISPATCH |
| 724 | +__attribute__((target("avx2"))) |
| 725 | +static int64_t get_value_from_idx_up_to_count_avx2( |
| 726 | + const struct hdr_histogram* h, int64_t count_at_percentile) |
| 727 | +{ |
| 728 | + int64_t running = 0; |
| 729 | + int32_t idx = 0; |
| 730 | + const int32_t limit = h->counts_len & ~3; |
| 731 | + |
| 732 | + for (; idx < limit; idx += 4) { |
| 733 | + __m256i v = _mm256_loadu_si256((const __m256i*)&h->counts[idx]); |
| 734 | + __m128i lo = _mm256_castsi256_si128(v); |
| 735 | + __m128i hi = _mm256_extracti128_si256(v, 1); |
| 736 | + __m128i s = _mm_add_epi64(lo, hi); |
| 737 | + /* Lanes are non-negative counts whose total fits in int64_t (total_count |
| 738 | + invariant), so the chunk sum cannot overflow under valid state. Use |
| 739 | + unsigned add to avoid signed-overflow UB if invariants are violated. */ |
| 740 | + int64_t chunk = (int64_t)((uint64_t)_mm_extract_epi64(s, 0) |
| 741 | + + (uint64_t)_mm_extract_epi64(s, 1)); |
| 742 | + |
| 743 | + if (__builtin_expect(running + chunk >= count_at_percentile, 0)) { |
| 744 | + for (int32_t j = idx; j < idx + 4; j++) { |
| 745 | + running += h->counts[j]; |
| 746 | + if (running >= count_at_percentile) |
| 747 | + return hdr_value_at_index(h, j); |
| 748 | + } |
| 749 | + } |
| 750 | + running += chunk; |
| 751 | + } |
| 752 | + for (; idx < h->counts_len; idx++) { |
| 753 | + running += h->counts[idx]; |
| 754 | + if (running >= count_at_percentile) |
| 755 | + return hdr_value_at_index(h, idx); |
| 756 | + } |
682 | 757 | return 0; |
683 | 758 | } |
| 759 | +#endif |
| 760 | + |
| 761 | +static int64_t get_value_from_idx_up_to_count(const struct hdr_histogram* h, int64_t count_at_percentile) |
| 762 | +{ |
| 763 | + count_at_percentile = count_at_percentile > 0 ? count_at_percentile : 1; |
| 764 | +#ifdef HDR_HAS_AVX2_DISPATCH |
| 765 | + if (__builtin_cpu_supports("avx2")) |
| 766 | + return get_value_from_idx_up_to_count_avx2(h, count_at_percentile); |
| 767 | +#endif |
| 768 | + return get_value_from_idx_up_to_count_scalar(h, count_at_percentile); |
| 769 | +} |
684 | 770 |
|
685 | 771 |
|
686 | 772 | int64_t hdr_value_at_percentile(const struct hdr_histogram* h, double percentile) |
|