blob: ef4e3ec0d35aa94f1cc36b1b6d9892e8b3629b3f [file]
// Copyright 2026 Google LLC
// SPDX-License-Identifier: Apache-2.0
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <cmath>
#include <cstring>
#include <random>
#include <vector>
#include "hwy/base.h"
// For dynamic dispatch, specify the name of the current file so that
// foreach_target.h can re-include it.
#undef HWY_TARGET_INCLUDE
#define HWY_TARGET_INCLUDE \
"hwy/examples/float_distribution.cc"
#include "hwy/aligned_allocator.h"
#include "hwy/foreach_target.h" // IWYU pragma: keep
#include "hwy/highway.h"
#include "hwy/nanobenchmark.h"
#include "hwy/per_target.h"
#include "hwy/timer.h"
/*
Highway SIMD Tutorial: Float magnitude based compaction
This example demonstrates how to filter and compact float32 values by
converting them to approximate log2 8-bit integers (via IEEE-754 exponent
extraction and narrowing) and storing only the values exceeding a threshold
using SIMD CompressBlendedStore.
Key SIMD techniques shown:
1. Float manipulation: Abs
2. BitCasts from float to uint32
3. Shift of multiple lanes via ShiftRight.
4. Narrowing Conversions: Demoting four 32-bit vectors to two 16-bit vectors,
then to one 8-bit vector using ReorderDemote2To.
5. Stream Compression: Using CompressBlendedStore to pack and write only
unmasked elements to memory without scalar loops or branches.
*/
HWY_BEFORE_NAMESPACE();
namespace hwy {
namespace HWY_NAMESPACE {
namespace hn = hwy::HWY_NAMESPACE;
// SIMD implementation of float distribution.
// Processes the input in blocks of 4 * Lanes(float) and handles any remainder
// using vector operations (LoadN) without falling back to scalar code.
// Returns the number of bytes written to 'out'.
// 'input_consumed' is updated with the number of input elements processed.
static HWY_INLINE size_t FloatDistributionSIMD(const float* HWY_RESTRICT in,
size_t count,
uint8_t threshold_val,
uint8_t* HWY_RESTRICT out) {
#if HWY_TARGET == HWY_SCALAR
// FloatDistributionSIMD is not supported on the HWY_SCALAR target
(void)in;
(void)count;
(void)threshold_val;
(void)out;
return 0;
#else
using DF32 = hn::ScalableTag<float>;
using DU32 = hn::ScalableTag<uint32_t>;
using DU16 = hn::Repartition<uint16_t, DU32>;
using DU8 = hn::Repartition<uint8_t, DU32>;
const DF32 df32;
const DU32 du32;
const DU16 du16;
const DU8 du8;
using VF32 = hn::Vec<DF32>;
using VU32 = hn::Vec<DU32>;
using VU16 = hn::Vec<DU16>;
using VU8 = hn::Vec<DU8>;
using MU8 = hn::Mask<DU8>;
(void)du16;
HWY_LANES_CONSTEXPR size_t lanes = hn::Lanes(df32);
size_t out_idx = 0;
const VU8 min_exp = hn::Set(du8, threshold_val);
size_t i = 0;
const size_t block_size = 4 * lanes;
auto to_exponent = [&](VF32 v) HWY_ATTR {
v = hn::Abs(v);
return hn::ShiftRight<23>(hn::BitCast(du32, v));
};
auto demote_and_store = [&](VU32 exp0, VU32 exp1, VU32 exp2,
VU32 exp3) HWY_ATTR {
// Demote compresses i32 -> i16 -> i8
// It performs also clamping of values.
// Reorder version dosen't assume any order of output elements.
// If you want to preserve order you should use OrderedDemote2To.
const VU16 exp16_01 = hn::ReorderDemote2To(du16, exp0, exp1);
const VU16 exp16_23 = hn::ReorderDemote2To(du16, exp2, exp3);
const VU8 exp8 = hn::ReorderDemote2To(du8, exp16_01, exp16_23);
const MU8 final_mask = hn::Gt(exp8, min_exp);
// CompressBlendedStore packs the values in 'exp8' according to 'final_mask'
// and stores them to 'out'.
// Blended version will not write outside number of bytes indicated by the
// mask.
// There is also CompressStore, which does the same job but faster but can
// write more than indicated by the mask.
out_idx += hn::CompressBlendedStore(exp8, final_mask, du8, out + out_idx);
};
for (; i + block_size <= count; i += block_size) {
demote_and_store(to_exponent(hn::LoadU(df32, in + i)),
to_exponent(hn::LoadU(df32, in + i + lanes)),
to_exponent(hn::LoadU(df32, in + i + 2 * lanes)),
to_exponent(hn::LoadU(df32, in + i + 3 * lanes)));
}
// Handle remainder using vector operations (LoadN).
const size_t remainder = count - i;
if (remainder > 0) {
auto load_chunk = [&](size_t offset) HWY_ATTR {
if (remainder <= offset) {
return hn::Zero(df32);
}
const size_t rem = remainder - offset;
return hn::LoadN(df32, in + i + offset, rem);
};
demote_and_store(
to_exponent(load_chunk(0 * lanes)), to_exponent(load_chunk(1 * lanes)),
to_exponent(load_chunk(2 * lanes)), to_exponent(load_chunk(3 * lanes)));
i += remainder;
(void)i;
}
return out_idx;
#endif
}
} // namespace HWY_NAMESPACE
} // namespace hwy
HWY_AFTER_NAMESPACE();
#if HWY_ONCE
namespace hwy {
// HWY_EXPORT registers the table of pointers to the target-specific
// implementations of FloatDistributionSIMD.
HWY_EXPORT(FloatDistributionSIMD);
// Helper to extract the exponent (approximate log2) of a float.
HWY_INLINE uint32_t GetExponent(float v) {
float abs_v = std::abs(v);
uint32_t int_v = hwy::BitCastScalar<uint32_t>(abs_v);
return int_v >> 23;
}
size_t FloatDistributionScalar(const float* HWY_RESTRICT in, size_t count,
float threshold, uint8_t* HWY_RESTRICT out) {
const uint8_t threshold_val = static_cast<uint8_t>(GetExponent(threshold));
size_t out_idx = 0;
for (size_t i = 0; i < count; ++i) {
const uint32_t exp = GetExponent(in[i]);
const uint8_t exp8 = static_cast<uint8_t>(exp);
if (exp8 > threshold_val) {
out[out_idx++] = exp8;
}
}
return out_idx;
}
// Verifies that SIMD and Scalar implementations produce the same output
// (modulo ordering, since SIMD uses ReorderDemote2To).
bool Verify(const float* HWY_RESTRICT in, size_t count, float threshold) {
std::vector<uint8_t> expected(count);
size_t expected_size =
FloatDistributionScalar(in, count, threshold, expected.data());
expected.resize(expected_size);
const uint8_t threshold_val = static_cast<uint8_t>(GetExponent(threshold));
std::vector<uint8_t> actual(count + hwy::VectorBytes());
size_t actual_size = HWY_DYNAMIC_DISPATCH(FloatDistributionSIMD)(
in, count, threshold_val, actual.data());
actual.resize(actual_size);
if (expected_size != actual_size) {
fprintf(stderr, "Size mismatch for threshold %e: expected %zu, got %zu\n",
threshold, expected_size, actual_size);
return false;
}
// We use XOR to verify since ReorderDemote2To does not preserve order,
// and XOR sum is order independent.
uint8_t expected_xor = 0;
for (uint8_t x : expected) expected_xor ^= x;
uint8_t actual_xor = 0;
for (uint8_t x : actual) actual_xor ^= x;
if (expected_xor ^ actual_xor) {
fprintf(stderr,
"XOR sum mismatch for threshold %e (count %zu): expected 0x%02x, "
"got 0x%02x\n",
threshold, count, expected_xor, actual_xor);
fprintf(stderr, "Expected (%zu): ", expected.size());
for (uint8_t x : expected) fprintf(stderr, "%d ", x);
fprintf(stderr, "\nActual (%zu): ", actual.size());
for (uint8_t x : actual) fprintf(stderr, "%d ", x);
fprintf(stderr, "\n");
return false;
}
return true;
}
int RunTests() {
printf("Running tests...\n");
// 1. Empty input
if (!Verify(nullptr, 0, 1e-4f)) return 1;
std::vector<float> thresholds = {0.0f, 1e-5f, 1e-4f, 1e-3f, 0.1f,
0.5f, 0.9f, 1.0f, 2.0f};
// 2. Random data test across various lengths to test vector remainder
// handling.
std::mt19937 gen(42);
std::uniform_real_distribution<float> dis(-1.5f, 1.5f);
for (size_t size :
{size_t{1}, size_t{2}, size_t{3}, size_t{4}, size_t{7},
size_t{8}, size_t{15}, size_t{16}, size_t{17}, size_t{31},
size_t{32}, size_t{33}, size_t{63}, size_t{64}, size_t{65},
size_t{100}, size_t{127}, size_t{128}, size_t{129}, size_t{255},
size_t{256}, size_t{257}, size_t{1000}, size_t{1024}, size_t{1025}}) {
AlignedVector<float> in(size);
for (size_t i = 0; i < size; ++i) {
in[i] = dis(gen);
}
for (float threshold : thresholds) {
if (!Verify(in.data(), in.size(), threshold)) return 1;
}
}
printf("All tests PASSED.\n");
// Benchmark
const size_t bench_size = 100'000;
const int reps = 1'000;
AlignedVector<float> bench_in(bench_size);
AlignedVector<uint8_t> bench_out(bench_size + HWY_MAX_BYTES);
for (size_t i = 0; i < bench_size; ++i) {
bench_in[i] = dis(gen);
}
const float bench_threshold = 0.1f;
const uint8_t bench_threshold_val =
static_cast<uint8_t>(GetExponent(bench_threshold));
printf("Benchmarking with array of %zu floats (%d reps)...\n", bench_size,
reps);
const double t_scalar_0 = hwy::platform::Now();
size_t scalar_written = 0;
for (int r = 0; r < reps; ++r) {
scalar_written = FloatDistributionScalar(bench_in.data(), bench_size,
bench_threshold, bench_out.data());
}
const double t_scalar_1 = hwy::platform::Now();
const double dt_scalar = t_scalar_1 - t_scalar_0;
const double t_simd_0 = hwy::platform::Now();
size_t simd_written = 0;
for (int r = 0; r < reps; ++r) {
simd_written = HWY_DYNAMIC_DISPATCH(FloatDistributionSIMD)(
bench_in.data(), bench_size, bench_threshold_val, bench_out.data());
}
const double t_simd_1 = hwy::platform::Now();
const double dt_simd = t_simd_1 - t_simd_0;
printf("Scalar written: %zu (took %f seconds)\n", scalar_written, dt_scalar);
printf("SIMD written: %zu (took %f seconds, speedup: %fx)\n", simd_written,
dt_simd, dt_scalar / dt_simd);
return 0;
}
} // namespace hwy
int main() { return hwy::RunTests(); }
#endif // HWY_ONCE