2323
2424#include HDR_MALLOC_INCLUDE
2525
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+
2645/* ###### ####### ## ## ## ## ######## ###### */
2746/* ## ## ## ## ## ## ### ## ## ## ## */
2847/* ## ## ## ## ## #### ## ## ## */
@@ -67,24 +86,48 @@ static int64_t counts_get_normalised(const struct hdr_histogram* h, int32_t inde
6786static void counts_inc_normalised (
6887 struct hdr_histogram * h , int32_t index , int64_t value )
6988{
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+ }
72100 h -> total_count += value ;
73101}
74102
75103static void counts_inc_normalised_atomic (
76104 struct hdr_histogram * h , int32_t index , int64_t value )
77105{
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+ }
81117 hdr_atomic_add_fetch_64 (& h -> total_count , value );
82118}
83119
84120static void update_min_max (struct hdr_histogram * h , int64_t value )
85121{
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+ }
88131}
89132
90133static 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)
498541 }
499542
500543 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 )
502545 {
503546 return false;
504547 }
@@ -520,7 +563,7 @@ bool hdr_record_values_atomic(struct hdr_histogram* h, int64_t value, int64_t co
520563
521564 counts_index = counts_index_for (h , value );
522565
523- if (counts_index < 0 || h -> counts_len <= counts_index )
566+ if (( uint32_t ) counts_index >= ( uint32_t ) h -> counts_len )
524567 {
525568 return false;
526569 }
@@ -665,22 +708,65 @@ int64_t hdr_min(const struct hdr_histogram* h)
665708 return non_zero_min (h );
666709}
667710
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 )
669713{
670714 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 ++ ) {
675716 count_to_idx += h -> counts [idx ];
676717 if (count_to_idx >= count_at_percentile )
677- {
678718 return hdr_value_at_index (h , idx );
679- }
680719 }
720+ return 0 ;
721+ }
681722
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+ }
682757 return 0 ;
683758}
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+ }
684770
685771
686772int64_t hdr_value_at_percentile (const struct hdr_histogram * h , double percentile )
0 commit comments