FazBrowse GitHub Viewer | Trending |
URL:
| Home
Tools: [Download Repo ZIP]   [Original HTTPS Page]

deps: update histogram to 0.11.10 · nodejs/node@e0664f1 · GitHub

/ node Public

Commit e0664f1

Browse files
nodejs-github-bot
authored and
aduh95
committed
deps: update histogram to 0.11.10
PR-URL: #64296 Reviewed-By: Colin Ihrig <cjihrig@gmail.com>
1 parent cf0622b commit e0664f1

2 files changed

Lines changed: 103 additions & 17 deletions

File tree

‎deps/histogram/include/hdr/hdr_histogram_version.h‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -7,6 +7,6 @@
77
#ifndef HDR_HISTOGRAM_VERSION_H
88
#define HDR_HISTOGRAM_VERSION_H
99

10-
#define HDR_HISTOGRAM_VERSION "0.11.9"
10+
#define HDR_HISTOGRAM_VERSION "0.11.10"
1111

1212
#endif // HDR_HISTOGRAM_VERSION_H

‎deps/histogram/src/hdr_histogram.c‎

Lines changed: 102 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -23,6 +23,25 @@
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
6786
static 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

75103
static 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

84120
static 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

90133
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)
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

686772
int64_t hdr_value_at_percentile(const struct hdr_histogram* h, double percentile)

0 commit comments

Comments
 (0)
Back | FazBrowse Home | New Git URL