2x faster HHCat buffering; add support for arm/ppc; target-specific test and measurement; namespaces to avoid ODR violation; shared padding/Load3 code; variadic args for Run; simpler byte swapping; separate robust_statistics header; avoid overriding CXXFLAGS; add auto-dependency; simplify c binding; threaded test; simplify CPU detection; hide nanobenchmark implementation; improved vector<->intrinsic conversion
diff --git a/Makefile b/Makefile index bc9f88d..de631a3 100644 --- a/Makefile +++ b/Makefile
@@ -1,90 +1,95 @@ -# The -m machine flag here indicates the minimum CPU required to run any of the -# binaries. The instruction_sets dispatcher allows highwayhash_test to test all -# implementations supported by the compiler and CPU regardless of this flag. -# By contrast, benchmark only measures implementations enabled by this flag so -# that it can call HighwayHashT directly, which is slightly faster. -HH_ARCH := -mavx2 -HH_CXXFLAGS := -CXXFLAGS = -I. -std=c++11 -Wall -O3 $(HH_ARCH) $(HH_CXXFLAGS) +# We assume X64 unless HH_POWER or HH_AARCH64 are defined. -PROFILER_OBJS := $(addprefix highwayhash/, \ - profiler_example.o \ - os_specific.o \ -) +override CPPFLAGS += -I../.. +override CXXFLAGS +=-std=c++11 -Wall -O3 -NANOBENCHMARK_OBJS := $(addprefix highwayhash/, \ - nanobenchmark.o \ - nanobenchmark_example.o \ - os_specific.o \ -) - -VECTOR_TEST_OBJS := $(addprefix highwayhash/, \ - vector_test.o \ -) - -SIP_OBJS := $(addprefix highwayhash/, \ +SIP_OBJS := $(addprefix obj/, \ sip_hash.o \ sip_tree_hash.o \ scalar_sip_tree_hash.o \ ) -SIP_TEST_OBJS := $(addprefix highwayhash/, \ - sip_hash_test.o \ -) - -HIGHWAYHASH_OBJS := $(addprefix highwayhash/, \ +DISPATCHER_OBJS := $(addprefix obj/, \ arch_specific.o \ - c_bindings.o \ - hh_avx2.o \ - hh_sse41.o \ - hh_portable.o \ instruction_sets.o \ -) - -HIGHWAYHASH_TEST_OBJS := $(addprefix highwayhash/, \ - highwayhash_test.o \ -) - -BENCHMARK_OBJS := $(addprefix highwayhash/, \ - arch_specific.o \ - benchmark.o \ + nanobenchmark.o \ os_specific.o \ ) -all: profiler_example nanobenchmark_example vector_test sip_hash_test\ - highwayhash_test benchmark +HIGHWAYHASH_OBJS := $(DISPATCHER_OBJS) obj/hh_portable.o +HIGHWAYHASH_TEST_OBJS := $(DISPATCHER_OBJS) obj/highwayhash_test_portable.o +VECTOR_TEST_OBJS := $(DISPATCHER_OBJS) obj/vector_test_portable.o -profiler_example: $(PROFILER_OBJS) - $(CXX) $(CXXFLAGS) $^ -o $@ +ifdef HH_AARCH64 +HH_X64 = +else +ifdef HH_POWER +HH_X64 = +else +HH_X64 = 1 +HIGHWAYHASH_OBJS += obj/hh_avx2.o obj/hh_sse41.o +HIGHWAYHASH_TEST_OBJS += obj/highwayhash_test_avx2.o obj/highwayhash_test_sse41.o +VECTOR_TEST_OBJS += obj/vector_test_avx2.o obj/vector_test_sse41.o +endif +endif -nanobenchmark_example: $(NANOBENCHMARK_OBJS) - $(CXX) $(CXXFLAGS) $^ -o $@ +all: $(addprefix bin/, \ + profiler_example nanobenchmark_example vector_test sip_hash_test \ + highwayhash_test benchmark) lib/libhighwayhash.a -vector_test: $(VECTOR_TEST_OBJS) - $(CXX) $(CXXFLAGS) -mavx2 $^ -o $@ +obj/%.o: highwayhash/%.cc + @mkdir -p -- $(dir $@) + $(CXX) -c $(CPPFLAGS) $(CXXFLAGS) $< -o $@ -sip_hash_test: $(SIP_TEST_OBJS) - $(CXX) $(CXXFLAGS) $^ -o $@ +bin/%: obj/%.o + @mkdir -p -- $(dir $@) + $(CXX) $(LDFLAGS) $^ -o $@ -# CPU-specific implementations (same source file, different compiler flags) -highwayhash/hh_avx2.o: highwayhash/highwayhash_target.cc highwayhash/hh_avx2.h - $(CXX) $(CXXFLAGS) -mavx2 -DHH_TARGET=TargetAVX2 -DHH_TARGET_AVX2 -c highwayhash/highwayhash_target.cc -o $@ +.DELETE_ON_ERROR: +deps.mk: $(wildcard highwayhash/*.cc) $(wildcard highwayhash/*.h) Makefile + set -eu; for file in highwayhash/*.cc; do \ + target=obj/$${file##*/}; target=$${target%.*}.o; \ + [ "$$target" = "obj/highwayhash_target.o" ] || \ + [ "$$target" = "obj/data_parallel_benchmark.o" ] || \ + [ "$$target" = "obj/data_parallel_test.o" ] || \ + $(CXX) -c $(CPPFLAGS) $(CXXFLAGS) -DHH_DISABLE_TARGET_SPECIFIC -MM -MT \ + "$$target" "$$file"; \ + done | sed -e ':b' -e 's-../[^./]*/--' -e 'tb' >$@ +-include deps.mk -highwayhash/hh_portable.o: highwayhash/highwayhash_target.cc highwayhash/hh_portable.h - $(CXX) $(CXXFLAGS) -DHH_TARGET=TargetPortable -DHH_TARGET_PORTABLE -c highwayhash/highwayhash_target.cc -o $@ +bin/profiler_example: $(DISPATCHER_OBJS) -highwayhash/hh_sse41.o: highwayhash/highwayhash_target.cc highwayhash/hh_sse41.h - $(CXX) $(CXXFLAGS) -msse4.1 -DHH_TARGET=TargetSSE41 -DHH_TARGET_SSE41 -c highwayhash/highwayhash_target.cc -o $@ +bin/nanobenchmark_example: $(DISPATCHER_OBJS) obj/nanobenchmark.o -libhighwayhash.a: $(SIP_OBJS) $(HIGHWAYHASH_OBJS) +ifdef HH_X64 +obj/sip_tree_hash.o: CXXFLAGS+=-mavx2 +# (Compiled from same source file with different compiler flags) +obj/highwayhash_test_avx2.o: CXXFLAGS+=-mavx2 +obj/highwayhash_test_sse41.o: CXXFLAGS+=-msse4.1 +obj/hh_avx2.o: CXXFLAGS+=-mavx2 +obj/hh_sse41.o: CXXFLAGS+=-msse4.1 +obj/vector_test_avx2.o: CXXFLAGS+=-mavx2 +obj/vector_test_sse41.o: CXXFLAGS+=-msse4.1 + +obj/benchmark.o: CXXFLAGS+=-mavx2 +endif + +lib/libhighwayhash.a: $(SIP_OBJS) $(HIGHWAYHASH_OBJS) obj/c_bindings.o + @mkdir -p -- $(dir $@) $(AR) rcs $@ $^ + ./test_exports.sh $@ -highwayhash_test: $(HIGHWAYHASH_OBJS) $(HIGHWAYHASH_TEST_OBJS) - $(CXX) $(CXXFLAGS) $^ -o $@ +bin/highwayhash_test: $(HIGHWAYHASH_TEST_OBJS) +bin/vector_test: $(VECTOR_TEST_OBJS) -benchmark: $(SIP_OBJS) $(HIGHWAYHASH_OBJS) $(BENCHMARK_OBJS) - $(CXX) $(CXXFLAGS) $^ -o $@ +bin/benchmark: obj/benchmark.o $(HIGHWAYHASH_TEST_OBJS) +bin/benchmark: $(SIP_OBJS) $(HIGHWAYHASH_OBJS) -.PHONY: clean all clean: - $(RM) $(PROFILER_OBJS) $(NANOBENCHMARK_OBJS) $(VECTOR_TEST_OBJS) $(SIP_OBJS) $(SIP_TEST_OBJS) $(HIGHWAYHASH_OBJS) $(HIGHWAYHASH_TEST_OBJS) $(BENCHMARK_OBJS) profiler_example nanobenchmark_example vector_test sip_hash_test highwayhash_test benchmark libhighwayhash.a + [ ! -d obj ] || $(RM) -r -- obj/ + +distclean: clean + [ ! -d bin ] || $(RM) -r -- bin/ + [ ! -d lib ] || $(RM) -r -- lib/ + +.PHONY: clean distclean all
diff --git a/README.md b/README.md index 53c5d2d..2d311c6 100644 --- a/README.md +++ b/README.md
@@ -21,18 +21,17 @@ char in[8] = {1}; return SipHash(key2, in, 8); -64, 128 or 256 bit HighwayHash for a specified CPU (AVX2, SSE41 or any): +64, 128 or 256 bit HighwayHash for the CPU determined by compiler flags: #include "highwayhash/highwayhash.h" using namespace highwayhash; const HHKey key HH_ALIGNAS(32) = {1, 2, 3, 4}; char in[8] = {1}; HHResult64 result; // or HHResult128 or HHResult256 - HHState<TargetAVX2> state(key); // or TargetSSE41 or TargetPortable, or - // HH_TARGET_PREFERRED to choose based on compiler flags. + HHStateT<HH_TARGET> state(key); HighwayHashT(&state, in, 8, &result); -64, 128 or 256 bit HighwayHash for the *current* CPU: +64, 128 or 256 bit HighwayHash for the CPU on which we're currently running: #include "highwayhash/highwayhash_target.h" #include "highwayhash/instruction_sets.h" @@ -40,14 +39,14 @@ const HHKey key HH_ALIGNAS(32) = {1, 2, 3, 4}; char in[8] = {1}; HHResult64 result; // or HHResult128 or HHResult256 - InstructionSets::Run<HighwayHash>(key, in, 8, &result, /*unused=*/0); + InstructionSets::Run<HighwayHash>(key, in, 8, &result); -C-callable 64-bit HighwayHash for the *current* CPU: +C-callable 64-bit HighwayHash for the CPU on which we're currently running: #include "highwayhash/c_bindings.h" const uint64_t key[4] = {1, 2, 3, 4}; char in[8] = {1}; - return HighwayHash64_Dispatcher(key, in, 8); + return HighwayHash64(key, in, 8); ## Introduction @@ -197,9 +196,7 @@ To minimize dispatch overhead when hashes are computed often (e.g. in a loop), we can inline the hash function into its caller using templates. The dispatch overhead will only be paid once (e.g. before the loop). The template mechanism -also avoids duplicating code in each CPU-specific implementation - basic SIMD -operations are expressed using the same notation/operators, which can be -extended by adding functions to the `Target*` traits classes. +also avoids duplicating code in each CPU-specific implementation. ## Defending against hash flooding @@ -348,6 +345,6 @@ * vector256.h and vector128.h contain wrapper classes for AVX2 and SSE4.1. By Jan Wassenberg <jan.wassenberg@gmail.com> and Jyrki Alakuijala -<jyrki.alakuijala@gmail.com>, updated 2017-01-28 +<jyrki.alakuijala@gmail.com>, updated 2017-02-07 This is not an official Google product.
diff --git a/highwayhash/arch_specific.cc b/highwayhash/arch_specific.cc index ed100e4..1ab839f 100644 --- a/highwayhash/arch_specific.cc +++ b/highwayhash/arch_specific.cc
@@ -14,15 +14,32 @@ #include "highwayhash/arch_specific.h" -#if HH_ARCH_X64 -#if !HH_MSC_VERSION -#include <cpuid.h> +#include <stdint.h> + +#if HH_ARCH_X64 && !HH_MSC_VERSION +# include <cpuid.h> #endif -#endif + +#include <string.h> // memcpy +#include <string> namespace highwayhash { +const char* TargetName(const TargetBits target_bit) { + switch (target_bit) { + case HH_TARGET_Portable: + return "Portable"; + case HH_TARGET_SSE41: + return "SSE41"; + case HH_TARGET_AVX2: + return "AVX2"; + default: + return nullptr; // zero, multiple, or unknown bits + } +} + #if HH_ARCH_X64 + void Cpuid(const uint32_t level, const uint32_t count, uint32_t* HH_RESTRICT abcd) { #if HH_MSC_VERSION @@ -40,6 +57,62 @@ abcd[3] = d; #endif } + +uint32_t ApicId() { + uint32_t abcd[4]; + Cpuid(1, 0, abcd); + return abcd[1] >> 24; // ebx +} + +namespace { + +std::string BrandString() { + char brand_string[49]; + uint32_t abcd[4]; + + // Check if brand string is supported (it is on all reasonable Intel/AMD) + Cpuid(0x80000000U, 0, abcd); + if (abcd[0] < 0x80000004U) { + return std::string(); + } + + for (int i = 0; i < 3; ++i) { + Cpuid(0x80000002U + i, 0, abcd); + memcpy(brand_string + i * 16, &abcd, sizeof(abcd)); + } + brand_string[48] = 0; + return brand_string; +} + +double DetectInvariantCyclesPerSecond() { + const std::string& brand_string = BrandString(); + // Brand strings include the maximum configured frequency. These prefixes are + // defined by Intel CPUID documentation. + const char* prefixes[3] = {"MHz", "GHz", "THz"}; + const double multipliers[3] = {1E6, 1E9, 1E12}; + for (size_t i = 0; i < 3; ++i) { + const size_t pos_prefix = brand_string.find(prefixes[i]); + if (pos_prefix != std::string::npos) { + const size_t pos_space = brand_string.rfind(' ', pos_prefix - 1); + if (pos_space != std::string::npos) { + const std::string digits = + brand_string.substr(pos_space + 1, pos_prefix - pos_space - 1); + return std::stod(digits) * multipliers[i]; + } + } + } + + return 0.0; +} + +} // namespace + +double InvariantCyclesPerSecond() { + // Thread-safe caching - this is called several times. + static const double cycles_per_second = DetectInvariantCyclesPerSecond(); + return cycles_per_second; +} + #endif // HH_ARCH_X64 } // namespace highwayhash
diff --git a/highwayhash/arch_specific.h b/highwayhash/arch_specific.h index a777867..7698166 100644 --- a/highwayhash/arch_specific.h +++ b/highwayhash/arch_specific.h
@@ -18,10 +18,14 @@ // WARNING: compiled with different flags => must not define/instantiate any // inline functions, nor include any headers that do - see instruction_sets.h. -#include <stdint.h> -#include <cstdlib> // _byteswap_* #include "highwayhash/compiler_specific.h" +#include <stdint.h> + +#if HH_MSC_VERSION +#include <intrin.h> // _byteswap_* +#endif + namespace highwayhash { #if defined(__x86_64__) || defined(_M_X64) @@ -30,39 +34,101 @@ #define HH_ARCH_X64 0 #endif -// TODO(janwas): add other platforms as needed. -#if HH_ARCH_X64 -#define HH_LITTLE_ENDIAN 1 -#define HH_BIG_ENDIAN 0 +#ifdef __aarch64__ +#define HH_ARCH_AARCH64 1 #else -#define HH_LITTLE_ENDIAN 0 -#define HH_BIG_ENDIAN 1 +#define HH_ARCH_AARCH64 0 #endif -#if (HH_ARCH_X64 && HH_MSC_VERSION) || defined(__SSE4_1__) -#define HH_ENABLE_SSE41 1 +#if defined(__powerpc64__) || defined(_M_PPC) +#define HH_ARCH_PPC 1 #else -#define HH_ENABLE_SSE41 0 +#define HH_ARCH_PPC 0 #endif -#if (HH_ARCH_X64 && HH_MSC_VERSION) || defined(__AVX2__) -#define HH_ENABLE_AVX2 1 +// Target := instruction set extension(s) such as SSE41. A translation unit can +// only provide a single target-specific implementation because they require +// different compiler flags. + +// Either the build system specifies the target by defining HH_TARGET_NAME +// (which is necessary for Portable on X64, and SSE41 on MSVC), or we'll choose +// the most efficient one that can be compiled given the current flags: +#ifndef HH_TARGET_NAME + +// To avoid excessive code size and dispatch overhead, we only support a few +// groups of extensions, e.g. FMA+BMI2+AVX+AVX2 =: "AVX2". These names must +// match the HH_TARGET_* suffixes below. +#ifdef __AVX2__ +#define HH_TARGET_NAME AVX2 +#elif defined(__SSE4_1__) +#define HH_TARGET_NAME SSE41 #else -#define HH_ENABLE_AVX2 0 +#define HH_TARGET_NAME Portable #endif -#ifdef _MSC_VER -#define HH_BSWAP32(x) _byteswap_ulong(x) -#define HH_BSWAP64(x) _byteswap_uint64(x) -#else -#define HH_BSWAP32(x) __builtin_bswap32(x) -#define HH_BSWAP64(x) __builtin_bswap64(x) -#endif +#endif // HH_TARGET_NAME + +#define HH_CONCAT(first, second) first##second +// Required due to macro expansion rules. +#define HH_EXPAND_CONCAT(first, second) HH_CONCAT(first, second) +// Appends HH_TARGET_NAME to "identifier_prefix". +#define HH_ADD_TARGET_SUFFIX(identifier_prefix) \ + HH_EXPAND_CONCAT(identifier_prefix, HH_TARGET_NAME) + +// HH_TARGET expands to an integer constant. Typical usage: HHStateT<HH_TARGET>. +// This ensures your code will work correctly when compiler flags are changed, +// and benefit from subsequently added targets/specializations. +#define HH_TARGET HH_ADD_TARGET_SUFFIX(HH_TARGET_) + +// Deprecated former name of HH_TARGET; please use HH_TARGET instead. +#define HH_TARGET_PREFERRED HH_TARGET + +// Associate targets with integer literals so the preprocessor can compare them +// with HH_TARGET. Do not instantiate templates with these values - use +// HH_TARGET instead. Must be unique powers of two, see TargetBits. Always +// defined even if unavailable on this HH_ARCH to allow calling TargetName. +// The suffixes must match the HH_TARGET_NAME identifiers. +#define HH_TARGET_Portable 1 +#define HH_TARGET_SSE41 2 +#define HH_TARGET_AVX2 4 + +// Bit array for one or more HH_TARGET_*. Used to indicate which target(s) are +// supported or were called by InstructionSets::RunAll. +using TargetBits = unsigned; + +namespace HH_TARGET_NAME { + +// Calls func(bit_value) for every nonzero bit in "bits". +template <class Func> +void ForeachTarget(TargetBits bits, const Func& func) { + while (bits != 0) { + const TargetBits lowest = bits & (~bits + 1); + func(lowest); + bits &= ~lowest; + } +} + +} // namespace HH_TARGET_NAME + +// Returns a brief human-readable string literal identifying one of the above +// bits, or nullptr if zero, multiple, or unknown bits are set. +const char* TargetName(const TargetBits target_bit); #if HH_ARCH_X64 + +// Calls CPUID instruction with eax=level and ecx=count and returns the result +// in abcd array where abcd = {eax, ebx, ecx, edx} (hence the name abcd). void Cpuid(const uint32_t level, const uint32_t count, uint32_t* HH_RESTRICT abcd); -#endif + +// Returns the APIC ID of the CPU on which we're currently running. +uint32_t ApicId(); + +// Returns nominal CPU clock frequency for converting tsc_timer cycles to +// seconds. This is unaffected by CPU throttling ("invariant"). Thread-safe. +double InvariantCyclesPerSecond(); + +#endif // HH_ARCH_X64 } // namespace highwayhash
diff --git a/highwayhash/benchmark.cc b/highwayhash/benchmark.cc index 03c3e0b..828a2be 100644 --- a/highwayhash/benchmark.cc +++ b/highwayhash/benchmark.cc
@@ -25,21 +25,19 @@ #include <vector> #include "highwayhash/compiler_specific.h" +#include "highwayhash/instruction_sets.h" #include "highwayhash/nanobenchmark.h" #include "highwayhash/os_specific.h" +#include "highwayhash/robust_statistics.h" // Which functions to enable (includes check for compiler support) -#define BENCHMARK_SIP 1 -#define BENCHMARK_SIP_TREE 1 && HH_ENABLE_AVX2 -#define BENCHMARK_HIGHWAY_AVX2 1 && HH_ENABLE_AVX2 -#define BENCHMARK_HIGHWAY_SSE41 1 && HH_ENABLE_SSE41 -#define BENCHMARK_HIGHWAY_PORTABLE 1 +#define BENCHMARK_SIP 0 +#define BENCHMARK_SIP_TREE 0 +#define BENCHMARK_HIGHWAY 1 +#define BENCHMARK_HIGHWAY_CAT 1 #define BENCHMARK_FARM 0 -#if BENCHMARK_HIGHWAY_AVX2 || BENCHMARK_HIGHWAY_SSE41 || \ - BENCHMARK_HIGHWAY_PORTABLE -#include "highwayhash/highwayhash.h" -#endif +#include "highwayhash/highwayhash_test_target.h" #if BENCHMARK_SIP #include "highwayhash/sip_hash.h" #endif @@ -54,9 +52,6 @@ namespace highwayhash { namespace { -constexpr size_t kMaxInputSize = 1024; -static_assert(kMaxInputSize >= sizeof(size_t), "Too small"); - // Stores time measurements from benchmarks, with support for printing them // as LaTeX figures or tables. class Measurements { @@ -85,7 +80,7 @@ const SpeedsForCaption cpb_for_caption = SortByCaptionFilterBySize(unique); for (const auto& item : cpb_for_caption) { - printf("%17s", item.first.c_str()); + printf("%22s", item.first.c_str()); for (const float cpb : item.second) { printf(" & %5.2f", cpb); } @@ -126,8 +121,8 @@ Result(const char* caption, const int in_size, const float cpb) : caption(caption), in_size(in_size), cpb(cpb) {} - // Algorithm name (string literal). - const char* caption; + // Algorithm name. + std::string caption; // Size of the input data [bytes]. int in_size; // Measured throughput [cycles per byte]. @@ -173,123 +168,113 @@ std::vector<Result> results_; }; -template <class Func> -void AddMeasurements(const std::vector<size_t>& in_sizes, const char* caption, - Measurements* measurements, const Func& func) { - for (auto& size_samples : - nanobenchmark::RepeatedMeasureWithArguments(in_sizes, func, 40)) { - const size_t size = size_samples.first; - auto& samples = size_samples.second; - const float median = nanobenchmark::Median(&samples); - const float mad = nanobenchmark::MedianAbsoluteDeviation(samples, median); +void AddMeasurements(DurationsForInputs* input_map, const char* caption, + Measurements* measurements) { + for (size_t i = 0; i < input_map->num_items; ++i) { + const DurationsForInputs::Item& item = input_map->items[i]; + std::vector<float> durations(item.durations, + item.durations + item.num_durations); + const float median = Median(&durations); + const float variability = MedianAbsoluteDeviation(durations, median); printf("%s %4zu: median=%6.1f cycles; median L1 norm =%4.1f cycles\n", - caption, size, median, mad); - measurements->Add(caption, size, median); + caption, item.input, median, variability); + measurements->Add(caption, item.input, median); } + input_map->num_items = 0; } -void AddMeasurementsSip(const std::vector<size_t>& in_sizes, - Measurements* measurements) { +void MeasureAndAdd(DurationsForInputs* input_map, const char* caption, + const Func func, Measurements* measurements) { + MeasureDurations(func, input_map); + AddMeasurements(input_map, caption, measurements); +} + +// InstructionSets::RunAll callback. +void AddMeasurementsWithPrefix(const char* prefix, const char* target_name, + DurationsForInputs* input_map, void* context) { + std::string caption(prefix); + caption += target_name; + AddMeasurements(input_map, caption.c_str(), + static_cast<Measurements*>(context)); +} + #if BENCHMARK_SIP + +uint64_t RunSip(const size_t size) { const HH_U64 key2[2] HH_ALIGNAS(16) = {0, 1}; - AddMeasurements(in_sizes, "SipHash", measurements, - [&key2](const size_t size) { - char in[kMaxInputSize]; - memcpy(in, &size, sizeof(size)); - return SipHash(key2, in, size); - }); - - AddMeasurements(in_sizes, "SipHash13", measurements, - [&key2](const size_t size) { - char in[kMaxInputSize]; - memcpy(in, &size, sizeof(size)); - return SipHash13(key2, in, size); - }); -#endif + char in[kMaxBenchmarkInputSize]; + memcpy(in, &size, sizeof(size)); + return SipHash(key2, in, size); } -void AddMeasurementsSipTree(const std::vector<size_t>& in_sizes, - Measurements* measurements) { +uint64_t RunSip13(const size_t size) { + const HH_U64 key2[2] HH_ALIGNAS(16) = {0, 1}; + char in[kMaxBenchmarkInputSize]; + memcpy(in, &size, sizeof(size)); + return SipHash13(key2, in, size); +} + +#endif + #if BENCHMARK_SIP_TREE + +uint64_t RunSipTree(const size_t size) { const HH_U64 key4[4] HH_ALIGNAS(32) = {0, 1, 2, 3}; - AddMeasurements(in_sizes, "SipTreeHash", measurements, - [&key4](const size_t size) { - char in[kMaxInputSize]; - memcpy(in, &size, sizeof(size)); - return SipTreeHash(key4, in, size); - }); - - AddMeasurements(in_sizes, "SipTreeHash13", measurements, - [&key4](const size_t size) { - char in[kMaxInputSize]; - memcpy(in, &size, sizeof(size)); - return SipTreeHash13(key4, in, size); - }); -#endif + char in[kMaxBenchmarkInputSize]; + memcpy(in, &size, sizeof(size)); + return SipTreeHash(key4, in, size); } -void AddMeasurementsHighway(const std::vector<size_t>& in_sizes, - Measurements* measurements) { -#if BENCHMARK_HIGHWAY_AVX2 || BENCHMARK_HIGHWAY_SSE41 || \ - BENCHMARK_HIGHWAY_PORTABLE - const HHKey key HH_ALIGNAS(32) = {0, 1, 2, 3}; -#endif -#if BENCHMARK_HIGHWAY_AVX2 - AddMeasurements(in_sizes, "HighwayHashAVX2", measurements, - [&key](const size_t size) { - char in[kMaxInputSize]; - memcpy(in, &size, sizeof(size)); - HHResult64 result; - HHState<TargetAVX2> state(key); - HighwayHashT(&state, in, size, &result); - return result; - }); -#endif -#if BENCHMARK_HIGHWAY_SSE41 - AddMeasurements(in_sizes, "HighwayHashSSE41", measurements, - [&key](const size_t size) { - char in[kMaxInputSize]; - memcpy(in, &size, sizeof(size)); - HHResult64 result; - HHState<TargetSSE41> state(key); - HighwayHashT(&state, in, size, &result); - return result; - }); -#endif -#if BENCHMARK_HIGHWAY_PORTABLE - AddMeasurements(in_sizes, "HighwayHashPortable", measurements, - [&key](const size_t size) { - char in[kMaxInputSize]; - memcpy(in, &size, sizeof(size)); - HHResult64 result; - HHState<TargetPortable> state(key); - HighwayHashT(&state, in, size, &result); - return result; - }); -#endif +uint64_t RunSipTree13(const size_t size) { + const HH_U64 key4[4] HH_ALIGNAS(32) = {0, 1, 2, 3}; + char in[kMaxBenchmarkInputSize]; + memcpy(in, &size, sizeof(size)); + return SipTreeHash13(key4, in, size); } -void AddMeasurementsFarm(const std::vector<size_t>& in_sizes, - Measurements* measurements) { +#endif + #if BENCHMARK_FARM - AddMeasurements(in_sizes, "Farm", measurements, [](const size_t size) { - char in[kMaxInputSize]; - memcpy(in, &size, sizeof(size)); - return farmhash::Fingerprint64(reinterpret_cast<const char*>(in), size); - }); -#endif + +uint64_t RunFarm(const size_t size) { + char in[kMaxBenchmarkInputSize]; + memcpy(in, &size, sizeof(size)); + return farmhash::Fingerprint64(reinterpret_cast<const char*>(in), size); } +#endif + void AddMeasurements(const std::vector<size_t>& in_sizes, Measurements* measurements) { - AddMeasurementsSip(in_sizes, measurements); - AddMeasurementsSipTree(in_sizes, measurements); - AddMeasurementsHighway(in_sizes, measurements); - AddMeasurementsFarm(in_sizes, measurements); + DurationsForInputs input_map(in_sizes.data(), in_sizes.size(), 40); +#if BENCHMARK_SIP + MeasureAndAdd(&input_map, "SipHash", RunSip, measurements); + MeasureAndAdd(&input_map, "SipHash13", RunSip13, measurements); +#endif + +#if BENCHMARK_SIP_TREE && defined(__AVX2__) + MeasureAndAdd(&input_map, "SipTreeHash", RunSipTree, measurements); + MeasureAndAdd(&input_map, "SipTreeHash13", RunSipTree13, measurements); +#endif + +#if BENCHMARK_FARM + MeasureAndAdd(&input_map, "Farm", &RunFarm, measurements); +#endif + +#if BENCHMARK_HIGHWAY + InstructionSets::RunAll<HighwayHashBenchmark>( + &input_map, &AddMeasurementsWithPrefix, measurements); +#endif + +#if BENCHMARK_HIGHWAY_CAT + InstructionSets::RunAll<HighwayHashCatBenchmark>( + &input_map, &AddMeasurementsWithPrefix, measurements); +#endif } void PrintTable() { - const std::vector<size_t> in_sizes = {8, 31, 32, 63, 64, kMaxInputSize}; + const std::vector<size_t> in_sizes = { + 7, 8, 31, 32, 63, 64, kMaxBenchmarkInputSize}; Measurements measurements; AddMeasurements(in_sizes, &measurements); measurements.PrintTable(in_sizes); @@ -300,7 +285,7 @@ for (int num_vectors = 0; num_vectors < 12; ++num_vectors) { for (int remainder : {0, 9, 18, 27}) { in_sizes.push_back(num_vectors * 32 + remainder); - assert(in_sizes.back() <= kMaxInputSize); + assert(in_sizes.back() <= kMaxBenchmarkInputSize); } } @@ -313,7 +298,7 @@ } // namespace highwayhash int main(int argc, char* argv[]) { - os_specific::PinThreadToRandomCPU(); + highwayhash::PinThreadToRandomCPU(); // No argument or t => table if (argc < 2 || argv[1][0] == 't') { highwayhash::PrintTable();
diff --git a/highwayhash/c_bindings.cc b/highwayhash/c_bindings.cc index 416a891..7e0488f 100644 --- a/highwayhash/c_bindings.cc +++ b/highwayhash/c_bindings.cc
@@ -17,20 +17,18 @@ #include "highwayhash/highwayhash_target.h" #include "highwayhash/instruction_sets.h" -using highwayhash::HHKey; using highwayhash::InstructionSets; -using highwayhash::HHResult64; using highwayhash::HighwayHash; extern "C" { // Ideally this would reside in highwayhash_target.cc, but that file is // compiled multiple times and we must only define this function once. -uint64_t HighwayHash64_Dispatcher(const uint64_t* key, const char* bytes, - const uint64_t size) { +uint64_t HighwayHash64(const HHKey key, const char* bytes, + const uint64_t size) { HHResult64 result; InstructionSets::Run<HighwayHash>(*reinterpret_cast<const HHKey*>(key), bytes, - size, &result, 0); + size, &result); return result; }
diff --git a/highwayhash/c_bindings.h b/highwayhash/c_bindings.h index 9218224..7d52de7 100644 --- a/highwayhash/c_bindings.h +++ b/highwayhash/c_bindings.h
@@ -19,25 +19,33 @@ #include <stdint.h> +#include "hh_types.h" + #ifdef __cplusplus extern "C" { + +// Bring the symbols out of the namespace. +using highwayhash::HHKey; +using highwayhash::HHPacket; +using highwayhash::HHResult64; +using highwayhash::HHResult128; +using highwayhash::HHResult256; #endif uint64_t SipHashC(const uint64_t* key, const char* bytes, const uint64_t size); uint64_t SipHash13C(const uint64_t* key, const char* bytes, const uint64_t size); -// Defined by highwayhash_target.cc, which requires a _Target* suffix. -uint64_t HighwayHash64_TargetPortable(const uint64_t* key, const char* bytes, - const uint64_t size); -uint64_t HighwayHash64_TargetSSE41(const uint64_t* key, const char* bytes, - const uint64_t size); -uint64_t HighwayHash64_TargetAVX2(const uint64_t* key, const char* bytes, - const uint64_t size); +// Uses the best implementation of HighwayHash for the current CPU and +// calculates 64-bit hash of given data. +uint64_t HighwayHash64(const HHKey key, const char* bytes, const uint64_t size); -// Detects current CPU (once) and invokes the best _Target* variant. -// "key" points to an array of four 64-bit values. -uint64_t HighwayHash64_Dispatcher(const uint64_t* key, const char* bytes, +// Defined by highwayhash_target.cc, which requires a _Target* suffix. +uint64_t HighwayHash64_TargetPortable(const HHKey key, const char* bytes, + const uint64_t size); +uint64_t HighwayHash64_TargetSSE41(const HHKey key, const char* bytes, + const uint64_t size); +uint64_t HighwayHash64_TargetAVX2(const HHKey key, const char* bytes, const uint64_t size); #ifdef __cplusplus
diff --git a/highwayhash/compiler_specific.h b/highwayhash/compiler_specific.h index c78ba49..3c25dd6 100644 --- a/highwayhash/compiler_specific.h +++ b/highwayhash/compiler_specific.h
@@ -85,4 +85,4 @@ #define HH_COMPILER_FENCE #endif -#endif // #ifndef HIGHWAYHASH_COMPILER_SPECIFIC_H_ +#endif // HIGHWAYHASH_COMPILER_SPECIFIC_H_
diff --git a/highwayhash/data_parallel.h b/highwayhash/data_parallel.h index 087abf7..89977d0 100644 --- a/highwayhash/data_parallel.h +++ b/highwayhash/data_parallel.h
@@ -37,7 +37,7 @@ abort(); \ } -namespace data_parallel { +namespace highwayhash { // Highly scalable thread pool, especially suitable for data-parallel // computations in the fork-join model, where clients need to know when all @@ -334,6 +334,6 @@ } }; -} // namespace data_parallel +} // namespace highwayhash #endif // HIGHWAYHASH_DATA_PARALLEL_H_
diff --git a/highwayhash/data_parallel_benchmark.cc b/highwayhash/data_parallel_benchmark.cc index 7e3b32a..ddc88b0 100644 --- a/highwayhash/data_parallel_benchmark.cc +++ b/highwayhash/data_parallel_benchmark.cc
@@ -17,38 +17,15 @@ #include <future> //NOLINT #include <set> #include "testing/base/public/gunit.h" +#include "highwayhash/arch_specific.h" #include "highwayhash/data_parallel.h" #include "thread/threadpool.h" -#if defined(_M_X64) || defined(__x86_64) || defined(__amd64) || \ - defined(__x86_64__) || defined(__amd64__) -#if defined(_MSC_VER) -#include <intrin.h> - -#define CPUID __cpuid -#else // GCC, clang -#include <cpuid.h> - -#define CPUID(regs, input) \ - __get_cpuid(input, ®s[0], ®s[1], ®s[2], ®s[3]) -#endif -#else -#define CPUID(regs, input) -#endif - -namespace data_parallel { +namespace highwayhash { namespace { constexpr int kBenchmarkTasks = 1000000; -unsigned ProcessorID() { - unsigned regs[4] = {0}; - // CPUID function 1 is always supported, but the APIC ID is zero on very - // old CPUs (Pentium III). - CPUID(regs, 1); - return regs[1] >> 24; -} - // Returns elapsed time [nanoseconds] for std::async. double BenchmarkAsync(uint64_t* total) { const base::Time t0 = base::Now(); @@ -134,7 +111,7 @@ } // Ensures multiple hardware threads are used (decided by the OS scheduler). -TEST(DataParallelTest, TestProcessorIDs) { +TEST(DataParallelTest, TestApicIds) { for (int num_threads = 1; num_threads <= std::thread::hardware_concurrency(); ++num_threads) { ThreadPool pool(num_threads); @@ -151,7 +128,7 @@ } mutex.lock(); - ids.insert(ProcessorID()); + ids.insert(ApicId()); total += sum; mutex.unlock(); }); @@ -171,4 +148,4 @@ } } // namespace -} // namespace data_parallel +} // namespace highwayhash
diff --git a/highwayhash/data_parallel_test.cc b/highwayhash/data_parallel_test.cc index 105d736..2728b7d 100644 --- a/highwayhash/data_parallel_test.cc +++ b/highwayhash/data_parallel_test.cc
@@ -18,7 +18,7 @@ #include "testing/base/public/gunit.h" #include "highwayhash/data_parallel.h" -namespace data_parallel { +namespace highwayhash { namespace { int PopulationCount(uint64_t bits) { @@ -172,4 +172,4 @@ } } // namespace -} // namespace data_parallel +} // namespace highwayhash
diff --git a/highwayhash/endianess.h b/highwayhash/endianess.h new file mode 100644 index 0000000..d2e108d --- /dev/null +++ b/highwayhash/endianess.h
@@ -0,0 +1,104 @@ +// Copyright 2017 Google Inc. All Rights Reserved. +// +// 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. + +#ifndef HIGHWAYHASH_ENDIANESS_H_ +#define HIGHWAYHASH_ENDIANESS_H_ + +#include <stdint.h> + + +#if defined(BYTE_ORDER) && defined(LITTLE_ENDIAN) && defined(BIG_ENDIAN) + + /* Someone has already included <endian.h> or equivalent. */ + +#elif defined(__LITTLE_ENDIAN__) + +# define HH_IS_LITTLE_ENDIAN 1 +# define HH_IS_BIG_ENDIAN 0 +# ifdef __BIG_ENDIAN__ +# error "Platform is both little and big endian?" +# endif + +#elif defined(__BIG_ENDIAN__) + +# define HH_IS_LITTLE_ENDIAN 0 +# define HH_IS_BIG_ENDIAN 1 + +#elif defined(__BYTE_ORDER__) && defined(__ORDER_BIG_ENDIAN__) && \ + defined(__ORDER_LITTLE_ENDIAN__) + +# define HH_IS_LITTLE_ENDIAN (__BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__) +# define HH_IS_BIG_ENDIAN (__BYTE_ORDER__ == __ORDER_BIG_ENDIAN__) + +#elif defined(__linux__) || defined(__CYGWIN__) || defined( __GNUC__ ) || \ + defined( __GNU_LIBRARY__ ) + +# include <endian.h> + +#elif defined(__OpenBSD__) || defined(__NetBSD__) || defined(__FreeBSD__) || \ + defined(__DragonFly__) + +# include <sys/endian.h> + +#elif defined(_WIN32) + +# include <sys/param.h> + +#else + +# error "Unsupported platform. Cannot determine byte order." + +#endif + + +#ifndef HH_IS_LITTLE_ENDIAN +# define HH_IS_LITTLE_ENDIAN (BYTE_ORDER == LITTLE_ENDIAN) +# define HH_IS_BIG_ENDIAN (BYTE_ORDER == BIG_ENDIAN) +#endif + + +namespace highwayhash { + +#if HH_IS_LITTLE_ENDIAN + +static inline uint32_t le32_from_host(uint32_t x) { return x; } +static inline uint32_t host_from_le32(uint32_t x) { return x; } +static inline uint64_t le64_from_host(uint64_t x) { return x; } +static inline uint64_t host_from_le64(uint64_t x) { return x; } + +#elif !HH_IS_BIG_ENDIAN + +# error "Unsupported byte order." + +#elif defined(_WIN16) || defined(_WIN32) || defined(_WIN64) + +#include <intrin.h> +static inline uint32_t host_from_le32(uint32_t x) { return _byteswap_ulong(x); } +static inline uint32_t le32_from_host(uint32_t x) { return _byteswap_ulong(x); } +static inline uint64_t host_from_le64(uint64_t x) { return _byteswap_uint64(x);} +static inline uint64_t le64_from_host(uint64_t x) { return _byteswap_uint64(x);} + +#else + +static inline uint32_t host_from_le32(uint32_t x) {return __builtin_bswap32(x);} +static inline uint32_t le32_from_host(uint32_t x) {return __builtin_bswap32(x);} +static inline uint64_t host_from_le64(uint64_t x) {return __builtin_bswap64(x);} +static inline uint64_t le64_from_host(uint64_t x) {return __builtin_bswap64(x);} + +#endif + +} // namespace highwayhash + + +#endif // HIGHWAYHASH_ENDIANESS_H_
diff --git a/highwayhash/example.cc b/highwayhash/example.cc new file mode 100644 index 0000000..587e3c5 --- /dev/null +++ b/highwayhash/example.cc
@@ -0,0 +1,30 @@ +// Minimal usage example: prints a hash. Tested on x86, ppc, arm. + +#include "highwayhash/highwayhash.h" + +#include <algorithm> +#include <iostream> + +using namespace highwayhash; + +int main(int argc, char* argv[]) { + // Please use a different key to ensure your hashes aren't identical. + const HHKey key HH_ALIGNAS(32) = {1, 2, 3, 4}; + // Aligning inputs to 32 bytes may help but is not required. + const char in[] = "bytes_to_hash"; + // Type determines the hash size; can also be HHResult128 or HHResult256. + HHResult64 result; + // HH_TARGET_PREFERRED expands to the best specialization available for the + // CPU detected via compiler flags (e.g. AVX2 #ifdef __AVX2__). + HHStateT<HH_TARGET_PREFERRED> state(key); + // Using argc prevents the compiler from eliding the hash computations. + const size_t size = std::min(sizeof(in), static_cast<size_t>(argc)); + HighwayHashT(&state, in, size, &result); + std::cout << "Hash : " << result << std::endl; + + HighwayHashCatT<HH_TARGET_PREFERRED> cat(key); + cat.Append(in, size); + cat.Finalize(&result); + std::cout << "HashCat: " << result << std::endl; + return 0; +}
diff --git a/highwayhash/hh_avx2.cc b/highwayhash/hh_avx2.cc index 8ad1f02..3549460 100644 --- a/highwayhash/hh_avx2.cc +++ b/highwayhash/hh_avx2.cc
@@ -12,6 +12,5 @@ // See the License for the specific language governing permissions and // limitations under the License. -#define HH_TARGET TargetAVX2 -#define HH_TARGET_AVX2 +#define HH_TARGET_NAME AVX2 #include "highwayhash/highwayhash_target.cc"
diff --git a/highwayhash/hh_avx2.h b/highwayhash/hh_avx2.h index 466a397..aecbdaf 100644 --- a/highwayhash/hh_avx2.h +++ b/highwayhash/hh_avx2.h
@@ -18,20 +18,28 @@ // WARNING: compiled with different flags => must not define/instantiate any // inline functions, nor include any headers that do - see instruction_sets.h. -#include <cstddef> -#include <cstdio> -#include <cstring> +#include "highwayhash/arch_specific.h" #include "highwayhash/compiler_specific.h" +#include "highwayhash/hh_buffer.h" #include "highwayhash/hh_types.h" +#include "highwayhash/load3.h" #include "highwayhash/vector128.h" #include "highwayhash/vector256.h" -namespace highwayhash { +// For auto-dependency generation, we need to include all headers but not their +// contents (otherwise compilation fails because -mavx2 is not specified). +#ifndef HH_DISABLE_TARGET_SPECIFIC -template <> -class HHState<TargetAVX2> { +namespace highwayhash { +// See vector128.h for why this namespace is necessary; matching it here makes +// it easier use the vector128 symbols, but requires textual inclusion. +namespace HH_TARGET_NAME { + +class HHStateAVX2 { public: - explicit HH_INLINE HHState(const HHKey& key_lanes) { + explicit HH_INLINE HHStateAVX2(const HHKey key_lanes) { Reset(key_lanes); } + + HH_INLINE void Reset(const HHKey key_lanes) { // "Nothing up my sleeve" numbers, concatenated hex digits of Pi from // http://www.numberworld.org/digits/Pi/, retrieved Feb 22, 2016. // @@ -57,72 +65,51 @@ mul1 = init1; } - HH_INLINE void Update(const HHPacket& packet) { - Update(LoadUnaligned<V4x64U>(&packet[0])); + HH_INLINE void Update(const HHPacket& packet_bytes) { + const uint64_t* HH_RESTRICT packet = + reinterpret_cast<const uint64_t * HH_RESTRICT>(packet_bytes); + Update(LoadUnaligned<V4x64U>(packet)); } - HH_INLINE void UpdateRemainder(const char* bytes, const uint64_t size_mod32) { + HH_INLINE void UpdateRemainder(const char* bytes, const size_t size_mod32) { // 'Length padding' differentiates zero-valued inputs that have the same // size/32. mod32 is sufficient because each Update behaves as if a // counter were injected, because the state is large and mixed thoroughly. - const V8x32U vsize_mod32( + const V8x32U size256( _mm256_broadcastd_epi32(_mm_cvtsi64_si128(size_mod32))); // Equivalent to storing size_mod32 in packet. - v0 += V4x64U(vsize_mod32); + v0 += V4x64U(size256); // Boosts the avalanche effect of mod32. - v1 = Rotate32By(v1, vsize_mod32); + v1 = Rotate32By(v1, size256); - const uint64_t size_mod4 = size_mod32 & 3; + const char* remainder = bytes + (size_mod32 & ~3); + const size_t size_mod4 = size_mod32 & 3; - // (Branching is faster than a single _mm256_maskload_epi32 and is - // similar to what is required for SSE41.) + const V4x32U size(_mm256_castsi256_si128(size256)); + + // (Branching is faster than a single _mm256_maskload_epi32.) if (HH_UNLIKELY(size_mod32 & 16)) { // 16..31 bytes left const V4x32U packetL = LoadUnaligned<V4x32U>(reinterpret_cast<const uint32_t*>(bytes)); - // 0..15 bytes left; a masked load prevents reading past the end. - // We can read int n=0..3 if size_mod32 >= 16 + (n + 1) * 4; subtract - // one because we only have > comparisons. - const V4x32U min_minus_one(31, 27, 23, 19); - const V4x32U whole_ints( - _mm_cmpgt_epi32(_mm256_castsi256_si128(vsize_mod32), min_minus_one)); - V4x32U packetH(_mm_maskload_epi32( - reinterpret_cast<const int*>(bytes + 16), whole_ints)); - - // Read the last 0..3 bytes into the most significant bytes. - uint32_t last4; - memcpy(&last4, bytes + size_mod32 - 4, 4); + const V4x32U int_mask = IntMask<16>()(size); + const V4x32U int_lanes = MaskedLoadInt(bytes + 16, int_mask); + const uint32_t last4 = + Load3()(Load3::AllowReadBeforeAndReturn(), remainder, size_mod4); // The upper four bytes of packetH are zero, so insert there. - packetH = V4x32U(_mm_insert_epi32(packetH, last4, 3)); - Update(V256From128(packetH, packetL)); + const V4x32U packetH(_mm_insert_epi32(int_lanes, last4, 3)); + Update(packetH, packetL); } else { // size_mod32 < 16 - const V4x32U min_minus_one(15, 11, 7, 3); - const V4x32U whole_ints( - _mm_cmpgt_epi32(_mm256_castsi256_si128(vsize_mod32), min_minus_one)); - const V4x32U packetL( - _mm_maskload_epi32(reinterpret_cast<const int*>(bytes), whole_ints)); - - // Read the last 0..3 bytes into the most significant bytes (faster than - // two conditional branches with 16/8 bit loads). - uint64_t last4 = 0; - if (size_mod4 != 0) { - // {idx0, idx1, idx2} is a subset of [0, size_mod4), so it is - // safe to read final_bytes at those offsets. - const char* final_bytes = bytes + (size_mod32 & ~3); - const uint64_t idx0 = 0; - const uint64_t idx1 = size_mod4 >> 1; - const uint64_t idx2 = size_mod4 - 1; - // Store into least significant bytes (avoids one shift). - last4 = static_cast<uint64_t>(final_bytes[idx0]); - last4 += static_cast<uint64_t>(final_bytes[idx1]) << 8; - last4 += static_cast<uint64_t>(final_bytes[idx2]) << 16; - } + const V4x32U int_mask = IntMask<0>()(size); + const V4x32U packetL = MaskedLoadInt(bytes, int_mask); + const uint64_t last3 = + Load3()(Load3::AllowUnordered(), remainder, size_mod4); // Rather than insert into packetL[3], it is faster to initialize // the otherwise empty packetH. - const V4x32U packetH(_mm_cvtsi64_si128(last4)); - Update(V256From128(packetH, packetL)); + const V4x32U packetH(_mm_cvtsi64_si128(last3)); + Update(packetH, packetL); } } @@ -165,9 +152,113 @@ StoreUnaligned(hash, &(*result)[0]); } + // "buffer" must be 32-byte aligned. + static HH_INLINE void ZeroInitialize(char* HH_RESTRICT buffer) { + const __m256i zero = _mm256_setzero_si256(); + _mm256_store_si256(reinterpret_cast<__m256i*>(buffer), zero); + } + + // "buffer" must be 32-byte aligned. + static HH_INLINE void CopyPartial(const char* HH_RESTRICT from, + const size_t size_mod32, + char* HH_RESTRICT buffer) { + const V4x32U size(size_mod32); + const uint32_t* const HH_RESTRICT from_u32 = + reinterpret_cast<const uint32_t * HH_RESTRICT>(from); + uint32_t* const HH_RESTRICT buffer_u32 = + reinterpret_cast<uint32_t * HH_RESTRICT>(buffer); + if (HH_UNLIKELY(size_mod32 & 16)) { // Copying 16..31 bytes + const V4x32U inL = LoadUnaligned<V4x32U>(from_u32); + Store(inL, buffer_u32); + const V4x32U inH = Load0To16<16, Load3::AllowReadBefore>( + from + 16, size_mod32 - 16, size); + Store(inH, buffer_u32 + V4x32U::N); + } else { // Copying 0..15 bytes + const V4x32U inL = Load0To16<>(from, size_mod32, size); + Store(inL, buffer_u32); + // No need to change upper 16 bytes of buffer. + } + } + + // "buffer" must be 32-byte aligned. + static HH_INLINE void AppendPartial(const char* HH_RESTRICT from, + const size_t size_mod32, + char* HH_RESTRICT buffer, + const size_t buffer_valid) { + const V4x32U size(size_mod32); + uint32_t* const HH_RESTRICT buffer_u32 = + reinterpret_cast<uint32_t * HH_RESTRICT>(buffer); + // buffer_valid + size <= 32 => appending 0..16 bytes inside upper 16 bytes. + if (HH_UNLIKELY(buffer_valid & 16)) { + const V4x32U suffix = Load0To16<>(from, size_mod32, size); + const V4x32U bufferH = Load<V4x32U>(buffer_u32 + V4x32U::N); + const V4x32U outH = Concatenate(bufferH, buffer_valid - 16, suffix); + Store(outH, buffer_u32 + V4x32U::N); + } else { // Appending 0..32 bytes starting at offset 0..15. + const V4x32U bufferL = Load<V4x32U>(buffer_u32); + const V4x32U suffixL = Load0To16<>(from, size_mod32, size); + const V4x32U outL = Concatenate(bufferL, buffer_valid, suffixL); + Store(outL, buffer_u32); + const size_t offsetH = sizeof(V4x32U) - buffer_valid; + // Do we have enough input to start filling the upper 16 buffer bytes? + if (size_mod32 > offsetH) { + const size_t sizeH = size_mod32 - offsetH; + const V4x32U outH = Load0To16<>(from + offsetH, sizeH, V4x32U(sizeH)); + Store(outH, buffer_u32 + V4x32U::N); + } + } + } + + // "buffer" must be 32-byte aligned. + HH_INLINE void AppendAndUpdate(const char* HH_RESTRICT from, + const size_t size_mod32, + const char* HH_RESTRICT buffer, + const size_t buffer_valid) { + const V4x32U size(size_mod32); + const uint32_t* const HH_RESTRICT buffer_u32 = + reinterpret_cast<const uint32_t * HH_RESTRICT>(buffer); + // buffer_valid + size <= 32 => appending 0..16 bytes inside upper 16 bytes. + if (HH_UNLIKELY(buffer_valid & 16)) { + const V4x32U suffix = Load0To16<>(from, size_mod32, size); + const V4x32U packetL = Load<V4x32U>(buffer_u32); + const V4x32U bufferH = Load<V4x32U>(buffer_u32 + V4x32U::N); + const V4x32U packetH = Concatenate(bufferH, buffer_valid - 16, suffix); + Update(packetH, packetL); + } else { // Appending 0..32 bytes starting at offset 0..15. + const V4x32U bufferL = Load<V4x32U>(buffer_u32); + const V4x32U suffixL = Load0To16<>(from, size_mod32, size); + const V4x32U packetL = Concatenate(bufferL, buffer_valid, suffixL); + const size_t offsetH = sizeof(V4x32U) - buffer_valid; + V4x32U packetH = packetL - packetL; + // Do we have enough input to start filling the upper 16 packet bytes? + if (size_mod32 > offsetH) { + const size_t sizeH = size_mod32 - offsetH; + packetH = Load0To16<>(from + offsetH, sizeH, V4x32U(sizeH)); + } + + Update(packetH, packetL); + } + } + private: - static HH_INLINE V4x64U V256From128(const V4x32U& hi, const V4x32U& lo) { - return V4x64U(_mm256_inserti128_si256(_mm256_castsi128_si256(lo), hi, 1)); + static HH_INLINE V4x32U MaskedLoadInt(const char* from, + const V4x32U& int_mask) { + // No faults will be raised when reading n=0..3 ints from "from" provided + // int_mask[n] = 0. + const int* HH_RESTRICT int_from = reinterpret_cast<const int*>(from); + return V4x32U(_mm_maskload_epi32(int_from, int_mask)); + } + + // Loads <= 16 bytes without accessing any byte outside [from, from + size). + // from[i] is loaded into lane i; from[i >= size] is undefined. + template <uint32_t kSizeOffset = 0, class Load3Policy = Load3::AllowNone> + static HH_INLINE V4x32U Load0To16(const char* from, const size_t size_mod32, + const V4x32U& size) { + const char* remainder = from + (size_mod32 & ~3); + const uint64_t last3 = Load3()(Load3Policy(), remainder, size_mod32 & 3); + const V4x32U int_mask = IntMask<kSizeOffset>()(size); + const V4x32U int_lanes = MaskedLoadInt(from, int_mask); + return Insert4AboveMask(last3, int_mask, int_lanes); } static HH_INLINE V4x64U Rotate64By32(const V4x64U& v) { @@ -225,6 +316,11 @@ v1 += ZipperMerge(v0); } + HH_INLINE void Update(const V4x32U& packetH, const V4x32U& packetL) { + const __m256i packetL256 = _mm256_castsi128_si256(packetL); + Update(V4x64U(_mm256_inserti128_si256(packetL256, packetH, 1))); + } + // XORs a << 1 and a << 2 into *out after clearing the upper two bits of a. // Also does the same for the upper 128 bit lane "b". Bit shifts are only // possible on independent 64-bit lanes. We therefore insert the upper bits @@ -272,19 +368,14 @@ return out; } - static void Print(const V4x64U& v) { - uint64_t lanes[V4x64U::N] HH_ALIGNAS(32); - Store(v, lanes); - printf("A: %016lX %016lX %016lX %016lX\n", lanes[3], lanes[2], lanes[1], - lanes[0]); - } - V4x64U v0; V4x64U v1; V4x64U mul0; V4x64U mul1; }; +} // namespace HH_TARGET_NAME } // namespace highwayhash -#endif // #ifndef HIGHWAYHASH_HH_AVX2_H_ +#endif // HH_DISABLE_TARGET_SPECIFIC +#endif // HIGHWAYHASH_HH_AVX2_H_
diff --git a/highwayhash/hh_buffer.h b/highwayhash/hh_buffer.h new file mode 100644 index 0000000..6827d9b --- /dev/null +++ b/highwayhash/hh_buffer.h
@@ -0,0 +1,98 @@ +// Copyright 2017 Google Inc. All Rights Reserved. +// +// 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. + +#ifndef HIGHWAYHASH_HH_BUFFER_H_ +#define HIGHWAYHASH_HH_BUFFER_H_ + +// Helper functions used by hh_avx2 and hh_sse41. + +#include "highwayhash/vector128.h" + +// For auto-dependency generation, we need to include all headers but not their +// contents (otherwise compilation fails because -msse4.1 is not specified). +#ifndef HH_DISABLE_TARGET_SPECIFIC + +namespace highwayhash { +// To prevent ODR violations when including this from multiple translation +// units (TU) that are compiled with different flags, the contents must reside +// in a namespace whose name is unique to the TU. NOTE: this behavior is +// incompatible with precompiled modules and requires textual inclusion instead. +namespace HH_TARGET_NAME { + +template <uint32_t kSizeOffset> +struct IntMask {}; // primary template + +template <> +struct IntMask<0> { + // Returns 32-bit lanes : ~0U if that lane can be loaded given "size" bytes. + // Typical case: size = 0..16, nothing deducted. + HH_INLINE V4x32U operator()(const V4x32U& size) const { + // Lane n is valid if size >= (n + 1) * 4; subtract one because we only have + // greater-than comparisons and don't want a negated mask. + return V4x32U(_mm_cmpgt_epi32(size, V4x32U(15, 11, 7, 3))); + } +}; + +template <> +struct IntMask<16> { + // "size" is 16..31; this is for loading the upper half of a packet, so + // effectively deduct 16 from size by changing the comparands. + HH_INLINE V4x32U operator()(const V4x32U& size) const { + return V4x32U(_mm_cmpgt_epi32(size, V4x32U(31, 27, 23, 19))); + } +}; + +// Inserts "bytes4" into "prev" at the lowest i such that mask[i] = 0. +// Assumes prev[j] == 0 if mask[j] = 0. +HH_INLINE V4x32U Insert4AboveMask(const uint32_t bytes4, const V4x32U& mask, + const V4x32U& prev) { + // There is no 128-bit shift by a variable count. Using shuffle_epi8 with a + // control mask requires a table lookup. We know the shift count is a + // multiple of 4 bytes, so we can broadcastd_epi32 and clear all lanes except + // those where mask != 0. This works because any upper output lanes need not + // be zero. + return prev | AndNot(mask, V4x32U(bytes4)); +} + +// Shifts "suffix" left by "prefix_len" = 0..15 bytes, clears upper bytes of +// "prefix", and returns the merged/concatenated bytes. +HH_INLINE V4x32U Concatenate(const V4x32U& prefix, const size_t prefix_len, + const V4x32U& suffix) { + static const uint64_t table[V16x8U::N][V2x64U::N] = { + {0x0706050403020100ull, 0x0F0E0D0C0B0A0908ull}, + {0x06050403020100FFull, 0x0E0D0C0B0A090807ull}, + {0x050403020100FFFFull, 0x0D0C0B0A09080706ull}, + {0x0403020100FFFFFFull, 0x0C0B0A0908070605ull}, + {0x03020100FFFFFFFFull, 0x0B0A090807060504ull}, + {0x020100FFFFFFFFFFull, 0x0A09080706050403ull}, + {0x0100FFFFFFFFFFFFull, 0x0908070605040302ull}, + {0x00FFFFFFFFFFFFFFull, 0x0807060504030201ull}, + {0xFFFFFFFFFFFFFFFFull, 0x0706050403020100ull}, + {0xFFFFFFFFFFFFFFFFull, 0x06050403020100FFull}, + {0xFFFFFFFFFFFFFFFFull, 0x050403020100FFFFull}, + {0xFFFFFFFFFFFFFFFFull, 0x0403020100FFFFFFull}, + {0xFFFFFFFFFFFFFFFFull, 0x03020100FFFFFFFFull}, + {0xFFFFFFFFFFFFFFFFull, 0x020100FFFFFFFFFFull}, + {0xFFFFFFFFFFFFFFFFull, 0x0100FFFFFFFFFFFFull}, + {0xFFFFFFFFFFFFFFFFull, 0x00FFFFFFFFFFFFFFull}}; + const V2x64U control = Load<V2x64U>(&table[prefix_len][0]); + const V2x64U shifted_suffix(_mm_shuffle_epi8(suffix, control)); + return V4x32U(_mm_blendv_epi8(shifted_suffix, prefix, control)); +} + +} // namespace HH_TARGET_NAME +} // namespace highwayhash + +#endif // HH_DISABLE_TARGET_SPECIFIC +#endif // HIGHWAYHASH_HH_BUFFER_H_
diff --git a/highwayhash/hh_portable.cc b/highwayhash/hh_portable.cc index 8d8bbcc..8e4c902 100644 --- a/highwayhash/hh_portable.cc +++ b/highwayhash/hh_portable.cc
@@ -12,6 +12,5 @@ // See the License for the specific language governing permissions and // limitations under the License. -#define HH_TARGET TargetPortable -#define HH_TARGET_PORTABLE +#define HH_TARGET_NAME Portable #include "highwayhash/highwayhash_target.cc"
diff --git a/highwayhash/hh_portable.h b/highwayhash/hh_portable.h index 667c082..84a17be 100644 --- a/highwayhash/hh_portable.h +++ b/highwayhash/hh_portable.h
@@ -18,27 +18,30 @@ // WARNING: compiled with different flags => must not define/instantiate any // inline functions, nor include any headers that do - see instruction_sets.h. -#include <stddef.h> -#include <cstdio> -#include <cstring> // memcpy - +#include "highwayhash/arch_specific.h" #include "highwayhash/compiler_specific.h" +#include "highwayhash/endianess.h" #include "highwayhash/hh_types.h" +#include "highwayhash/load3.h" namespace highwayhash { +// See vector128.h for why this namespace is necessary; we match it here for +// consistency. As a result, this header requires textual inclusion. +namespace HH_TARGET_NAME { -template <> -class HHState<TargetPortable> { +class HHStatePortable { public: static const int kNumLanes = 4; - explicit HH_INLINE HHState(const HHKey& keys) { - static const HHPacket init0 = {0xdbe6d5d5fe4cce2full, 0xa4093822299f31d0ull, - 0x13198a2e03707344ull, - 0x243f6a8885a308d3ull}; - static const HHPacket init1 = {0x3bd39e10cb0ef593ull, 0xc0acf169b5f18a8cull, - 0xbe5466cf34e90c6cull, - 0x452821e638d01377ull}; - HHPacket rotated_keys; + using Lanes = uint64_t[kNumLanes]; + + explicit HH_INLINE HHStatePortable(const HHKey keys) { Reset(keys); } + + HH_INLINE void Reset(const HHKey keys) { + static const Lanes init0 = {0xdbe6d5d5fe4cce2full, 0xa4093822299f31d0ull, + 0x13198a2e03707344ull, 0x243f6a8885a308d3ull}; + static const Lanes init1 = {0x3bd39e10cb0ef593ull, 0xc0acf169b5f18a8cull, + 0xbe5466cf34e90c6cull, 0x452821e638d01377ull}; + Lanes rotated_keys; Rotate64By32(keys, &rotated_keys); Copy(init0, &mul0); Copy(init1, &mul1); @@ -47,26 +50,16 @@ } HH_INLINE void Update(const HHPacket& packet) { - Add(packet, &v1); - Add(mul0, &v1); - - // (Loop is faster than unrolling) + Lanes packet_lanes; + CopyPartial(&packet[0], sizeof(HHPacket), + reinterpret_cast<char*>(&packet_lanes)); for (int lane = 0; lane < kNumLanes; ++lane) { - const uint32_t v1_32 = static_cast<uint32_t>(v1[lane]); - mul0[lane] ^= v1_32 * (v0[lane] >> 32); - v0[lane] += mul1[lane]; - const uint32_t v0_32 = static_cast<uint32_t>(v0[lane]); - mul1[lane] ^= v0_32 * (v1[lane] >> 32); + packet_lanes[lane] = host_from_le64(packet_lanes[lane]); } - - ZipperMergeAndAdd(v1[1], v1[0], &v0[1], &v0[0]); - ZipperMergeAndAdd(v1[3], v1[2], &v0[3], &v0[2]); - - ZipperMergeAndAdd(v0[1], v0[0], &v1[1], &v1[0]); - ZipperMergeAndAdd(v0[3], v0[2], &v1[3], &v1[2]); + Update(packet_lanes); } - HH_INLINE void UpdateRemainder(const char* bytes, const uint64_t size_mod32) { + HH_INLINE void UpdateRemainder(const char* bytes, const size_t size_mod32) { // 'Length padding' differentiates zero-valued inputs that have the same // size/32. mod32 is sufficient because each Update behaves as if a // counter were injected, because the state is large and mixed thoroughly. @@ -76,38 +69,25 @@ } Rotate32By(reinterpret_cast<uint32_t*>(&v1), size_mod32); - const uint64_t size_mod4 = size_mod32 & 3; + const size_t size_mod4 = size_mod32 & 3; + const char* remainder = bytes + (size_mod32 & ~3); HHPacket packet HH_ALIGNAS(32) = {0}; - memcpy(packet, bytes, size_mod32 & ~3); + CopyPartial(bytes, remainder - bytes, &packet[0]); if (size_mod32 & 16) { // 16..31 bytes left // Read the last 0..3 bytes and previous 1..4 into the upper bits. - uint32_t last4; - memcpy(&last4, bytes + size_mod32 - 4, 4); - - // The upper four bytes of packet are zero, so insert there. - packet[3] |= static_cast<uint64_t>(last4) << 32; + // Insert into the upper four bytes of packet, which are zero. + uint32_t last4 = + Load3()(Load3::AllowReadBeforeAndReturn(), remainder, size_mod4); + CopyPartial(reinterpret_cast<const char*>(&last4), 4, &packet[28]); } else { // size_mod32 < 16 - // Read the last 0..3 bytes into the least significant bytes (faster than - // two conditional branches with 16/8 bit loads). - uint64_t last4 = 0; - if (size_mod4 != 0) { - // {idx0, idx1, idx2} is a subset of [0, size_mod4), so it is - // safe to read final_bytes at those offsets. - const char* final_bytes = bytes + (size_mod32 & ~3); - const uint64_t idx0 = 0; - const uint64_t idx1 = size_mod4 >> 1; - const uint64_t idx2 = size_mod4 - 1; - // Store into least significant bytes (avoids one shift). - last4 = static_cast<uint64_t>(final_bytes[idx0]); - last4 += static_cast<uint64_t>(final_bytes[idx1]) << 8; - last4 += static_cast<uint64_t>(final_bytes[idx2]) << 16; - } + uint64_t last4 = Load3()(Load3::AllowUnordered(), remainder, size_mod4); - // Rather than insert at packet + 12, it is faster to initialize + // Rather than insert at packet + 28, it is faster to initialize // the otherwise empty packet + 16 with up to 64 bits of padding. - packet[2] = last4; + CopyPartial(reinterpret_cast<const char*>(&last4), sizeof(last4), + &packet[16]); } Update(packet); } @@ -143,23 +123,59 @@ v0[2] + mul0[2], &(*result)[3], &(*result)[2]); } + static HH_INLINE void ZeroInitialize(char* HH_RESTRICT buffer) { + for (size_t i = 0; i < sizeof(HHPacket); ++i) { + buffer[i] = 0; + } + } + + static HH_INLINE void CopyPartial(const char* HH_RESTRICT from, + const size_t size_mod32, + char* HH_RESTRICT buffer) { + for (size_t i = 0; i < size_mod32; ++i) { + buffer[i] = from[i]; + } + } + + static HH_INLINE void AppendPartial(const char* HH_RESTRICT from, + const size_t size_mod32, + char* HH_RESTRICT buffer, + const size_t buffer_valid) { + for (size_t i = 0; i < size_mod32; ++i) { + buffer[buffer_valid + i] = from[i]; + } + } + + HH_INLINE void AppendAndUpdate(const char* HH_RESTRICT from, + const size_t size_mod32, + const char* HH_RESTRICT buffer, + const size_t buffer_valid) { + HHPacket tmp HH_ALIGNAS(32); + for (size_t i = 0; i < buffer_valid; ++i) { + tmp[i] = buffer[i]; + } + for (size_t i = 0; i < size_mod32; ++i) { + tmp[buffer_valid + i] = from[i]; + } + Update(tmp); + } + private: - static HH_INLINE void Copy(const HHPacket& source, - HHPacket* HH_RESTRICT dest) { + static HH_INLINE void Copy(const Lanes& source, Lanes* HH_RESTRICT dest) { for (int lane = 0; lane < kNumLanes; ++lane) { (*dest)[lane] = source[lane]; } } - static HH_INLINE void Add(const HHPacket& source, - HHPacket* HH_RESTRICT dest) { + static HH_INLINE void Add(const Lanes& source, Lanes* HH_RESTRICT dest) { for (int lane = 0; lane < kNumLanes; ++lane) { (*dest)[lane] += source[lane]; } } - static HH_INLINE void Xor(const HHPacket& op1, const HHPacket& op2, - HHPacket* HH_RESTRICT dest) { + template <typename LanesOrPointer> + static HH_INLINE void Xor(const Lanes& op1, const LanesOrPointer& op2, + Lanes* HH_RESTRICT dest) { for (int lane = 0; lane < kNumLanes; ++lane) { (*dest)[lane] = op1[lane] ^ op2[lane]; } @@ -184,12 +200,34 @@ #undef MASK + // For inputs that are already in native byte order (e.g. PermuteAndAdd) + HH_INLINE void Update(const Lanes& packet_lanes) { + Add(packet_lanes, &v1); + Add(mul0, &v1); + + // (Loop is faster than unrolling) + for (int lane = 0; lane < kNumLanes; ++lane) { + const uint32_t v1_32 = static_cast<uint32_t>(v1[lane]); + mul0[lane] ^= v1_32 * (v0[lane] >> 32); + v0[lane] += mul1[lane]; + const uint32_t v0_32 = static_cast<uint32_t>(v0[lane]); + mul1[lane] ^= v0_32 * (v1[lane] >> 32); + } + + ZipperMergeAndAdd(v1[1], v1[0], &v0[1], &v0[0]); + ZipperMergeAndAdd(v1[3], v1[2], &v0[3], &v0[2]); + + ZipperMergeAndAdd(v0[1], v0[0], &v1[1], &v1[0]); + ZipperMergeAndAdd(v0[3], v0[2], &v1[3], &v1[2]); + } + static HH_INLINE uint64_t Rotate64By32(const uint64_t x) { return (x >> 32) | (x << 32); } - static HH_INLINE void Rotate64By32(const HHPacket& v, - HHPacket* HH_RESTRICT rotated) { + template <typename LanesOrPointer> + static HH_INLINE void Rotate64By32(const LanesOrPointer& v, + Lanes* HH_RESTRICT rotated) { for (int i = 0; i < kNumLanes; ++i) { (*rotated)[i] = Rotate64By32(v[i]); } @@ -202,8 +240,7 @@ } } - static HH_INLINE void Permute(const HHPacket& v, - HHPacket* HH_RESTRICT permuted) { + static HH_INLINE void Permute(const Lanes& v, Lanes* HH_RESTRICT permuted) { (*permuted)[0] = Rotate64By32(v[2]); (*permuted)[1] = Rotate64By32(v[3]); (*permuted)[2] = Rotate64By32(v[0]); @@ -211,7 +248,7 @@ } HH_INLINE void PermuteAndUpdate() { - HHPacket permuted; + Lanes permuted; Permute(v0, &permuted); Update(permuted); } @@ -250,17 +287,13 @@ *m0 = a0 ^ a2_shl1 ^ a2_shl2; } - static void Print(const HHPacket& lanes) { - printf("P: %016lX %016lX %016lX %016lX\n", lanes[3], lanes[2], lanes[1], - lanes[0]); - } - - HHPacket v0; - HHPacket v1; - HHPacket mul0; - HHPacket mul1; + Lanes v0; + Lanes v1; + Lanes mul0; + Lanes mul1; }; +} // namespace HH_TARGET_NAME } // namespace highwayhash #endif // HIGHWAYHASH_HH_PORTABLE_H_
diff --git a/highwayhash/hh_sse41.cc b/highwayhash/hh_sse41.cc index b73845c..f414b67 100644 --- a/highwayhash/hh_sse41.cc +++ b/highwayhash/hh_sse41.cc
@@ -12,6 +12,5 @@ // See the License for the specific language governing permissions and // limitations under the License. -#define HH_TARGET TargetSSE41 -#define HH_TARGET_SSE41 +#define HH_TARGET_NAME SSE41 #include "highwayhash/highwayhash_target.cc"
diff --git a/highwayhash/hh_sse41.h b/highwayhash/hh_sse41.h index 5df5722..e8ae957 100644 --- a/highwayhash/hh_sse41.h +++ b/highwayhash/hh_sse41.h
@@ -18,23 +18,30 @@ // WARNING: compiled with different flags => must not define/instantiate any // inline functions, nor include any headers that do - see instruction_sets.h. -#include <stdint.h> -#include <cstdio> -#include <cstring> // memcpy - +#include "highwayhash/arch_specific.h" #include "highwayhash/compiler_specific.h" +#include "highwayhash/hh_buffer.h" #include "highwayhash/hh_types.h" +#include "highwayhash/load3.h" #include "highwayhash/vector128.h" +// For auto-dependency generation, we need to include all headers but not their +// contents (otherwise compilation fails because -msse4.1 is not specified). +#ifndef HH_DISABLE_TARGET_SPECIFIC + namespace highwayhash { +// See vector128.h for why this namespace is necessary; matching it here makes +// it easier use the vector128 symbols, but requires textual inclusion. +namespace HH_TARGET_NAME { // J-lanes tree hashing: see http://dx.doi.org/10.4236/jis.2014.53010 // Uses pairs of SSE4.1 instructions to emulate the AVX-2 algorithm. -template <> -class HHState<TargetSSE41> { +class HHStateSSE41 { public: - explicit HH_INLINE HHState(const uint64_t (&key)[4]) { - // "Nothing up my sleeve numbers"; see HHStateAVX2. + explicit HH_INLINE HHStateSSE41(const HHKey key) { Reset(key); } + + HH_INLINE void Reset(const HHKey key) { + // "Nothing up my sleeve numbers"; see HHStateTAVX2. const V2x64U init0L(0xa4093822299f31d0ull, 0xdbe6d5d5fe4cce2full); const V2x64U init0H(0x243f6a8885a308d3ull, 0x13198a2e03707344ull); const V2x64U init1L(0xc0acf169b5f18a8cull, 0x3bd39e10cb0ef593ull); @@ -51,13 +58,15 @@ mul1H = init1H; } - HH_INLINE void Update(const HHPacket& packet) { - const V2x64U packetL = LoadUnaligned<V2x64U>(&packet[0]); - const V2x64U packetH = LoadUnaligned<V2x64U>(&packet[2]); + HH_INLINE void Update(const HHPacket& packet_bytes) { + const uint64_t* HH_RESTRICT packet = + reinterpret_cast<const uint64_t * HH_RESTRICT>(packet_bytes); + const V2x64U packetL = LoadUnaligned<V2x64U>(packet + 0); + const V2x64U packetH = LoadUnaligned<V2x64U>(packet + 2); Update(packetH, packetL); } - HH_INLINE void UpdateRemainder(const char* bytes, const uint64_t size_mod32) { + HH_INLINE void UpdateRemainder(const char* bytes, const size_t size_mod32) { // 'Length padding' differentiates zero-valued inputs that have the same // size/32. mod32 is sufficient because each Update behaves as if a // counter were injected, because the state is large and mixed thoroughly. @@ -68,7 +77,8 @@ // Boosts the avalanche effect of mod32. Rotate32By(&v1H, &v1L, size_mod32); - const uint64_t size_mod4 = size_mod32 & 3; + const size_t size_mod4 = size_mod32 & 3; + const char* HH_RESTRICT remainder = bytes + (size_mod32 & ~3); if (HH_UNLIKELY(size_mod32 & 16)) { // 16..31 bytes left const V2x64U packetL = @@ -76,9 +86,8 @@ V2x64U packetH = LoadMultipleOfFour(bytes + 16, size_mod32); - // Read the last 0..3 bytes into the most significant bytes. - uint32_t last4; - memcpy(&last4, bytes + size_mod32 - 4, 4); + const uint32_t last4 = + Load3()(Load3::AllowReadBeforeAndReturn(), remainder, size_mod4); // The upper four bytes of packetH are zero, so insert there. packetH = V2x64U(_mm_insert_epi32(packetH, last4, 3)); @@ -86,21 +95,8 @@ } else { // size_mod32 < 16 const V2x64U packetL = LoadMultipleOfFour(bytes, size_mod32); - // Read the last 0..3 bytes into the most significant bytes (faster than - // two conditional branches with 16/8 bit loads). - uint64_t last4 = 0; - if (size_mod4 != 0) { - // {idx0, idx1, idx2} is a subset of [0, size_mod4), so it is - // safe to read final_bytes at those offsets. - const char* final_bytes = bytes + (size_mod32 & ~3); - const uint64_t idx0 = 0; - const uint64_t idx1 = size_mod4 >> 1; - const uint64_t idx2 = size_mod4 - 1; - // Store into least significant bytes (avoids one shift). - last4 = static_cast<uint64_t>(final_bytes[idx0]); - last4 += static_cast<uint64_t>(final_bytes[idx1]) << 8; - last4 += static_cast<uint64_t>(final_bytes[idx2]) << 16; - } + const uint64_t last4 = + Load3()(Load3::AllowUnordered(), remainder, size_mod4); // Rather than insert into packetL[3], it is faster to initialize // the otherwise empty packetH. @@ -150,6 +146,44 @@ StoreUnaligned(hashH, &(*result)[2]); } + static HH_INLINE void ZeroInitialize(char* HH_RESTRICT buffer_bytes) { + __m128i* buffer = reinterpret_cast<__m128i*>(buffer_bytes); + const __m128i zero = _mm_setzero_si128(); + _mm_store_si128(buffer + 0, zero); + _mm_store_si128(buffer + 1, zero); + } + + static HH_INLINE void CopyPartial(const char* HH_RESTRICT from, + const size_t size_mod32, + char* HH_RESTRICT buffer) { + for (size_t i = 0; i < size_mod32; ++i) { + buffer[i] = from[i]; + } + } + + static HH_INLINE void AppendPartial(const char* HH_RESTRICT from, + const size_t size_mod32, + char* HH_RESTRICT buffer, + const size_t buffer_valid) { + for (size_t i = 0; i < size_mod32; ++i) { + buffer[buffer_valid + i] = from[i]; + } + } + + HH_INLINE void AppendAndUpdate(const char* HH_RESTRICT from, + const size_t size_mod32, + const char* HH_RESTRICT buffer, + const size_t buffer_valid) { + HHPacket tmp HH_ALIGNAS(32); + for (size_t i = 0; i < buffer_valid; ++i) { + tmp[i] = buffer[i]; + } + for (size_t i = 0; i < size_mod32; ++i) { + tmp[buffer_valid + i] = from[i]; + } + Update(tmp); + } + private: // Swap 32-bit halves of each lane (caller swaps 128-bit halves) static HH_INLINE V2x64U Rotate64By32(const V2x64U& v) { @@ -213,7 +247,7 @@ // Returns zero-initialized vector with the lower "size" = 0, 4, 8 or 12 // bytes loaded from "bytes". Serves as a replacement for AVX2 maskload_epi32. static HH_INLINE V2x64U LoadMultipleOfFour(const char* bytes, - const uint64_t size) { + const size_t size) { const uint32_t* words = reinterpret_cast<const uint32_t*>(bytes); // Mask of 1-bits where the final 4 bytes should be inserted (replacement // for variable shift/insert using broadcast+blend). @@ -277,15 +311,6 @@ return out; } - static void Print(const V2x64U& H, const V2x64U& L) { - uint64_t lanesL[2] HH_ALIGNAS(16) = {0}; - uint64_t lanesH[2] HH_ALIGNAS(16) = {0}; - Store(L, lanesL); - Store(H, lanesH); - printf("S: %016lX %016lX %016lX %016lX\n", lanesH[1], lanesH[0], lanesL[1], - lanesL[0]); - } - V2x64U v0L; V2x64U v0H; V2x64U v1L; @@ -296,6 +321,8 @@ V2x64U mul1H; }; +} // namespace HH_TARGET_NAME } // namespace highwayhash -#endif // #ifndef HIGHWAYHASH_HH_SSE41_H_ +#endif // HH_DISABLE_TARGET_SPECIFIC +#endif // HIGHWAYHASH_HH_SSE41_H_
diff --git a/highwayhash/hh_types.h b/highwayhash/hh_types.h index 9fe7128..8ff0f8e 100644 --- a/highwayhash/hh_types.h +++ b/highwayhash/hh_types.h
@@ -15,31 +15,34 @@ #ifndef HIGHWAYHASH_HH_TYPES_H_ #define HIGHWAYHASH_HH_TYPES_H_ +// WARNING: included from c_bindings => must be C-compatible. // WARNING: compiled with different flags => must not define/instantiate any // inline functions, nor include any headers that do - see instruction_sets.h. +#include <stddef.h> // size_t #include <stdint.h> -#include "highwayhash/instruction_sets.h" +#ifdef __cplusplus namespace highwayhash { +#endif // 256-bit secret key that should remain unknown to attackers. // We recommend initializing it to a random value. -using HHKey = uint64_t[4]; +typedef uint64_t HHKey[4]; -// How much input is hashed by one call to HHState::Update. -using HHPacket = uint64_t[4]; +// How much input is hashed by one call to HHStateT::Update. +typedef char HHPacket[32]; // Hash 'return' types. -using HHResult64 = uint64_t; // returned directly -using HHResult128 = uint64_t[2]; -using HHResult256 = uint64_t[4]; +typedef uint64_t HHResult64; // returned directly +typedef uint64_t HHResult128[2]; +typedef uint64_t HHResult256[4]; -// Primary template; hh_*.h provide specializations for Target*, which are -// forward-declared in instruction_sets.h. -template <class Target> -class HHState {}; +// Called if a test fails, indicating which target and size. +typedef void (*HHNotify)(const char*, size_t); +#ifdef __cplusplus } // namespace highwayhash +#endif #endif // HIGHWAYHASH_HH_TYPES_H_
diff --git a/highwayhash/highwayhash.h b/highwayhash/highwayhash.h index 0703d3b..82aa4a5 100644 --- a/highwayhash/highwayhash.h +++ b/highwayhash/highwayhash.h
@@ -18,50 +18,59 @@ // WARNING: compiled with different flags => must not define/instantiate any // inline functions, nor include any headers that do - see instruction_sets.h. -// Function template for direct invocation via CPU-specific templates (e.g. -// template<class Target> CodeUsingHash() { HighwayHashT<Target>(...); }, or if -// Target matches the minimum CPU requirement (specified via compiler flag). -#include <stddef.h> +// This header's templates are useful for inlining into other CPU-specific code: +// template<TargetBits Target> CodeUsingHash() { HighwayHashT<Target>(...); }, +// and can also be instantiated with HH_TARGET when callers don't care about the +// exact implementation. Otherwise, they are implementation details of the +// highwayhash_target wrapper. Use that instead if you need to detect the best +// available implementation at runtime. -#include "highwayhash/arch_specific.h" // HH_ENABLE_* +#include "highwayhash/arch_specific.h" #include "highwayhash/compiler_specific.h" #include "highwayhash/hh_types.h" #include "highwayhash/iaca.h" -// HH_TARGET_PREFERRED enables us to provide new specializations without -// having to update each call site. Example usage: -// -// HHState<HH_TARGET_PREFERRED> state(key); -// HighwayHashT(&state, in, size, &result); -// -// This is useful for binaries that target a lowest-common denominator CPU -// without conditionally using newer instructions if available. Such binaries -// are compiled with the same flags for each translation unit, which avoids -// difficulties with inline functions mentioned in instruction_sets.h. -// -// If you want to select the best available specialization at runtime, -// use InstructionSets<HighwayHash>() instead. - -#include "highwayhash/hh_portable.h" -#define HH_TARGET_PREFERRED TargetPortable - -#if HH_ENABLE_SSE41 -#include "highwayhash/hh_sse41.h" -#undef HH_TARGET_PREFERRED -#define HH_TARGET_PREFERRED TargetSSE41 -#endif - -#if HH_ENABLE_AVX2 +// Include exactly one (see arch_specific.h) header, which defines a state +// object in a target-specific namespace, e.g. AVX2::HHStateAVX2. +// Attempts to use "computed includes" (#define MACRO "path/or_just_filename", +// #include MACRO) fail with 'file not found', so we need an #if chain. +#if HH_TARGET == HH_TARGET_AVX2 #include "highwayhash/hh_avx2.h" -#undef HH_TARGET_PREFERRED -#define HH_TARGET_PREFERRED TargetAVX2 +#elif HH_TARGET == HH_TARGET_SSE41 +#include "highwayhash/hh_sse41.h" +#elif HH_TARGET == HH_TARGET_Portable +#include "highwayhash/hh_portable.h" +#else +#error "Unknown target, add its hh_*.h include here." #endif +#ifndef HH_DISABLE_TARGET_SPECIFIC namespace highwayhash { -// Computes HighwayHash of "bytes" using the implementation for "Target" CPU. +// Alias templates (HHStateT) cannot be specialized, so we need a helper struct. +// Note that hh_*.h don't just specialize HHStateT directly because vector128.h +// must reside in a distinct namespace (to allow including it from multiple +// translation units), and it is easier if its users, i.e. the concrete HHState, +// also reside in that same namespace, which precludes specialization. +template <TargetBits Target> +struct HHStateForTarget {}; + +template <> +struct HHStateForTarget<HH_TARGET> { + // (The namespace is sufficient and the additional HH_TARGET_NAME suffix is + // technically redundant, but it makes searching easier.) + using type = HH_TARGET_NAME::HH_ADD_TARGET_SUFFIX(HHState); +}; + +// Typically used as HHStateT<HH_TARGET>. It would be easier to just have a +// concrete type HH_STATE, but this alias template is required by the +// templates in highwayhash_target.cc. +template <TargetBits Target> +using HHStateT = typename HHStateForTarget<Target>::type; + +// Computes HighwayHash of "bytes" using the implementation chosen by "State". // -// "state" is a HHState<> initialized with a key. +// "state" is a HHStateT<> initialized with a key. // "bytes" is the data to hash (possibly unaligned). // "size" is the number of bytes to hash; we do not read any additional bytes. // "hash" is a HHResult* (either 64, 128 or 256 bits). @@ -76,12 +85,12 @@ // the wrapper in highwayhash_target.h instead. // // Callers wanting to hash multiple pieces of data should duplicate this -// function, calling HHState::Update for each input and only Finalizing once. -template <class Target, typename Result> -HH_INLINE void HighwayHashT(HHState<Target>* HH_RESTRICT state, +// function, calling HHStateT::Update for each input and only Finalizing once. +template <class State, typename Result> +HH_INLINE void HighwayHashT(State* HH_RESTRICT state, const char* HH_RESTRICT bytes, const size_t size, Result* HH_RESTRICT hash) { - BeginIACA(); + // BeginIACA(); const size_t remainder = size & (sizeof(HHPacket) - 1); const size_t truncated = size & ~(sizeof(HHPacket) - 1); for (size_t offset = 0; offset < truncated; offset += sizeof(HHPacket)) { @@ -93,70 +102,99 @@ } state->Finalize(hash); - EndIACA(); + // EndIACA(); } // Wrapper class for incrementally hashing a series of data ranges. The final // result is the same as HighwayHashT of the concatenation of all the ranges. // This is useful for computing the hash of cords, iovecs, and similar // data structures. - -template <class Target> +template <TargetBits Target> class HighwayHashCatT { public: - HighwayHashCatT(const HHKey& key) : state_(key) {} + HH_INLINE HighwayHashCatT(const HHKey& key) : state_(key) { + // Avoids msan uninitialized-memory warnings. + HHStateT<Target>::ZeroInitialize(buffer_); + } - // Adds "bytes" to the internal buffer, feeding it to HHState::Update as - // required. Call this as often as desired. There are no alignment - // requirements. No effect if "num_bytes" == 0. - void Append(const char* HH_RESTRICT bytes, size_t num_bytes) { - char* buffer_bytes = reinterpret_cast<char*>(buffer_); + // Resets the state of the hasher so it can be used to hash a new string. + HH_INLINE void Reset(const HHKey& key) { + state_.Reset(key); + buffer_usage_ = 0; + } + + // Adds "bytes" to the internal buffer, feeding it to HHStateT::Update as + // required. Call this as often as desired. Only reads bytes within the + // interval [bytes, bytes + num_bytes). "num_bytes" == 0 has no effect. + // There are no alignment requirements. + HH_INLINE void Append(const char* HH_RESTRICT bytes, size_t num_bytes) { + // BeginIACA(); + const size_t capacity = sizeof(HHPacket) - buffer_usage_; + // New bytes fit within buffer, but still not enough to Update. + if (HH_UNLIKELY(num_bytes < capacity)) { + HHStateT<Target>::AppendPartial(bytes, num_bytes, buffer_, buffer_usage_); + buffer_usage_ += num_bytes; + return; + } + + // HACK: ensures the state is kept in SIMD registers; otherwise, Update + // constantly load/stores its operands, which is much slower. + // Restrict-qualified pointers to external state or the state_ member are + // not sufficient for keeping this in registers. + HHStateT<Target> state_copy = state_; + // Have prior bytes to flush. - if (buffer_usage_ != 0) { - const size_t capacity = sizeof(HHPacket) - buffer_usage_; - if (num_bytes < capacity) { - // New bytes fit within buffer, but still not enough to Update. - memcpy(buffer_bytes + buffer_usage_, bytes, num_bytes); - buffer_usage_ += num_bytes; - return; - } - memcpy(buffer_bytes + buffer_usage_, bytes, capacity); - state_.Update(*reinterpret_cast<const HHPacket*>(buffer_)); - buffer_usage_ = 0; + const size_t buffer_usage = buffer_usage_; + if (HH_LIKELY(buffer_usage != 0)) { + // Calls update with prior buffer contents plus new data. Does not modify + // the buffer because some implementations can load into SIMD registers + // and Append to them directly. + state_copy.AppendAndUpdate(bytes, capacity, buffer_, buffer_usage); bytes += capacity; num_bytes -= capacity; } // Buffer currently empty => Update directly from the source. while (num_bytes >= sizeof(HHPacket)) { - state_.Update(*reinterpret_cast<const HHPacket*>(bytes)); + state_copy.Update(*reinterpret_cast<const HHPacket*>(bytes)); bytes += sizeof(HHPacket); num_bytes -= sizeof(HHPacket); } - // Store any remainders in buffer, no-op if multiple of a packet. - memcpy(buffer_bytes, bytes, num_bytes); + // Unconditionally assign even if zero because we didn't reset to zero + // after the AppendAndUpdate above. buffer_usage_ = num_bytes; + + state_ = state_copy; + + // Store any remainders in buffer, no-op if multiple of a packet. + if (HH_LIKELY(num_bytes != 0)) { + HHStateT<Target>::CopyPartial(bytes, num_bytes, buffer_); + } + // EndIACA(); } // Stores the resulting 64, 128 or 256-bit hash of all data passed to Append. - // Must be called exactly once. + // Must be called exactly once, or after a prior Reset. template <typename Result> // HHResult* - void Finalize(Result* HH_RESTRICT hash) { - if (buffer_usage_ != 0) { - const char* buffer_bytes = reinterpret_cast<const char*>(buffer_); - state_.UpdateRemainder(buffer_bytes, buffer_usage_); + HH_INLINE void Finalize(Result* HH_RESTRICT hash) { + // BeginIACA(); + HHStateT<Target> state_copy = state_; + const size_t buffer_usage = buffer_usage_; + if (HH_LIKELY(buffer_usage != 0)) { + state_copy.UpdateRemainder(buffer_, buffer_usage); } - state_.Finalize(hash); + state_copy.Finalize(hash); + // EndIACA(); } private: HHPacket buffer_ HH_ALIGNAS(64); - HHState<Target> state_; + HHStateT<Target> state_ HH_ALIGNAS(32); // How many bytes in buffer_ (starting with offset 0) are valid. size_t buffer_usage_ = 0; }; } // namespace highwayhash - +#endif // HH_DISABLE_TARGET_SPECIFIC #endif // HIGHWAYHASH_HIGHWAYHASH_H_
diff --git a/highwayhash/highwayhash_target.cc b/highwayhash/highwayhash_target.cc index 4affa98..6bc913d 100644 --- a/highwayhash/highwayhash_target.cc +++ b/highwayhash/highwayhash_target.cc
@@ -18,187 +18,50 @@ #include "highwayhash/highwayhash_target.h" #include "highwayhash/highwayhash.h" -#include "highwayhash/targets.h" +#ifndef HH_DISABLE_TARGET_SPECIFIC namespace highwayhash { extern "C" { -#define HH_CONCAT(first, second) first##second -// Need to expand in a second macro because HH_TARGET is a predefined macro. -#define HH_EXPAND_CONCAT(first, second) HH_CONCAT(first, second) -uint64_t HH_EXPAND_CONCAT(HighwayHash64_, HH_TARGET)(const uint64_t* key, - const char* bytes, - const uint64_t size) { - HHState<HH_TARGET> state(*reinterpret_cast<const HHKey*>(key)); +uint64_t HH_ADD_TARGET_SUFFIX(HighwayHash64_)(const HHKey key, + const char* bytes, + const uint64_t size) { + HHStateT<HH_TARGET> state(key); HHResult64 result; HighwayHashT(&state, bytes, size, &result); return result; } } // extern "C" -template <class Target> +template <TargetBits Target> void HighwayHash<Target>::operator()(const HHKey& key, const char* HH_RESTRICT bytes, const size_t size, - HHResult64* HH_RESTRICT hash, int) const { - HHState<Target> state(key); + HHResult64* HH_RESTRICT hash) const { + HHStateT<Target> state(key); HighwayHashT(&state, bytes, size, hash); } -template <class Target> +template <TargetBits Target> void HighwayHash<Target>::operator()(const HHKey& key, const char* HH_RESTRICT bytes, const size_t size, - HHResult128* HH_RESTRICT hash, int) const { - HHState<Target> state(key); + HHResult128* HH_RESTRICT hash) const { + HHStateT<Target> state(key); HighwayHashT(&state, bytes, size, hash); } -template <class Target> +template <TargetBits Target> void HighwayHash<Target>::operator()(const HHKey& key, const char* HH_RESTRICT bytes, const size_t size, - HHResult256* HH_RESTRICT hash, int) const { - HHState<Target> state(key); + HHResult256* HH_RESTRICT hash) const { + HHStateT<Target> state(key); HighwayHashT(&state, bytes, size, hash); } -namespace { - -template <class Target> -void NotifyWhetherEqual(Target, const uint64_t size, const HHResult64& expected, - const HHResult64& actual, - void (*notify)(const char*, bool)) { - if (expected != actual) { - printf("%8s: mismatch at %zu: %016lX %016lX\n", Target::Name(), size, - expected, actual); - (*notify)(Target::Name(), false); - } else { - (*notify)(Target::Name(), true); - } -} - -// Overload for HHResult128 or HHResult256 (arrays). -template <class Target, size_t kNumLanes> -void NotifyWhetherEqual(Target, const size_t size, - const uint64_t (&expected)[kNumLanes], - const uint64_t (&actual)[kNumLanes], - void (*notify)(const char*, bool)) { - for (size_t i = 0; i < kNumLanes; ++i) { - if (expected[i] != actual[i]) { - printf("%8s: mismatch at %zu[%zu]: %016lX %016lX\n", Target::Name(), size, - i, expected[i], actual[i]); - (*notify)(Target::Name(), false); - return; - } - } - (*notify)(Target::Name(), true); -} - -// Shared logic for all HighwayHashTest::operator() overloads. -template <class Target, typename Result> -void TestHighwayHash(HHState<Target>* state, const char* HH_RESTRICT bytes, - const size_t size, const Result* expected, - void (*notify)(const char*, bool)) { - Result actual; - HighwayHashT(state, bytes, size, &actual); - NotifyWhetherEqual(Target(), size, *expected, actual, notify); -} - -// Shared logic for all HighwayHashCatTest::operator() overloads. -template <class Target, typename Result> -void TestHighwayHashCat(const HHKey& key, HHState<Target>* state, - const char* HH_RESTRICT bytes, const size_t size, - const Result* expected, - void (*notify)(const char*, bool)) { - // Slightly faster to compute the expected prefix hashes only once. - // Use new instead of vector to avoid headers with inline functions. - Result* results = new Result[size]; - for (size_t i = 0; i < size; ++i) { - HHState<Target> state_flat(key); - HighwayHashT(&state_flat, bytes, i, &results[i]); - } - - // Splitting into three fragments/Append should cover all codepaths. - const size_t max_fragment_size = size / 3; - for (size_t size1 = 0; size1 < max_fragment_size; ++size1) { - for (size_t size2 = 0; size2 < max_fragment_size; ++size2) { - for (size_t size3 = 0; size3 < max_fragment_size; ++size3) { - HighwayHashCatT<Target> cat(key); - const char* pos = bytes; - cat.Append(pos, size1); - pos += size1; - cat.Append(pos, size2); - pos += size2; - cat.Append(pos, size3); - pos += size3; - - Result result_cat; - cat.Finalize(&result_cat); - - const size_t total_size = pos - bytes; - NotifyWhetherEqual(Target(), total_size, results[total_size], - result_cat, notify); - } - } - } - - delete[] results; -} - -} // namespace - -template <class Target> -void HighwayHashTest<Target>::operator()( - const HHKey& key, const char* HH_RESTRICT bytes, const size_t size, - const HHResult64* expected, void (*notify)(const char*, bool)) const { - HHState<Target> state(key); - TestHighwayHash(&state, bytes, size, expected, notify); -} - -template <class Target> -void HighwayHashTest<Target>::operator()( - const HHKey& key, const char* HH_RESTRICT bytes, const size_t size, - const HHResult128* expected, void (*notify)(const char*, bool)) const { - HHState<Target> state(key); - TestHighwayHash(&state, bytes, size, expected, notify); -} - -template <class Target> -void HighwayHashTest<Target>::operator()( - const HHKey& key, const char* HH_RESTRICT bytes, const size_t size, - const HHResult256* expected, void (*notify)(const char*, bool)) const { - HHState<Target> state(key); - TestHighwayHash(&state, bytes, size, expected, notify); -} - -template <class Target> -void HighwayHashCatTest<Target>::operator()( - const HHKey& key, const char* HH_RESTRICT bytes, const uint64_t size, - const HHResult64* expected, void (*notify)(const char*, bool)) const { - HHState<Target> state(key); - TestHighwayHashCat(key, &state, bytes, size, expected, notify); -} - -template <class Target> -void HighwayHashCatTest<Target>::operator()( - const HHKey& key, const char* HH_RESTRICT bytes, const uint64_t size, - const HHResult128* expected, void (*notify)(const char*, bool)) const { - HHState<Target> state(key); - TestHighwayHashCat(key, &state, bytes, size, expected, notify); -} - -template <class Target> -void HighwayHashCatTest<Target>::operator()( - const HHKey& key, const char* HH_RESTRICT bytes, const uint64_t size, - const HHResult256* expected, void (*notify)(const char*, bool)) const { - HHState<Target> state(key); - TestHighwayHashCat(key, &state, bytes, size, expected, notify); -} - // Instantiate for the current target. template struct HighwayHash<HH_TARGET>; -template struct HighwayHashTest<HH_TARGET>; -template struct HighwayHashCatTest<HH_TARGET>; } // namespace highwayhash +#endif // HH_DISABLE_TARGET_SPECIFIC
diff --git a/highwayhash/highwayhash_target.h b/highwayhash/highwayhash_target.h index 3f7c297..2d9ed1e 100644 --- a/highwayhash/highwayhash_target.h +++ b/highwayhash/highwayhash_target.h
@@ -18,20 +18,21 @@ // WARNING: compiled with different flags => must not define/instantiate any // inline functions, nor include any headers that do - see instruction_sets.h. -// Adapters for the InstructionSets::Run (or RunAll) dispatcher, which invokes -// the best (or all) implementations available on the current CPU. +// Adapter for the InstructionSets::Run dispatcher, which invokes the best +// implementations available on the current CPU. +#include "highwayhash/arch_specific.h" #include "highwayhash/compiler_specific.h" #include "highwayhash/hh_types.h" namespace highwayhash { -// Usage: InstructionSets::Run<HighwayHash>(key, bytes, size, hash, 0). +// Usage: InstructionSets::Run<HighwayHash>(key, bytes, size, hash). // This incurs some small dispatch overhead. If the entire program is compiled // for the target CPU, you can instead call HighwayHashT directly to avoid any // overhead. This template is instantiated in the source file, which is // compiled once for every target with the required flags (e.g. -mavx2). -template <class Target> +template <TargetBits Target> struct HighwayHash { // Stores a 64/128/256 bit hash of "bytes" using the HighwayHash // implementation for the "Target" CPU. The hash result is identical @@ -41,54 +42,18 @@ // "bytes" is the data to hash (possibly unaligned). // "size" is the number of bytes to hash; we do not read any additional bytes. // "hash" is a HHResult* (either 64, 128 or 256 bits). - // The final parameter ensures the argument count matches HighwayHashTest. // // HighwayHash is a strong pseudorandom function with security claims // [https://arxiv.org/abs/1612.06257]. It is intended as a safer - // general-purpose hash, 4x faster than SipHash and 10x faster than BLAKE2. + // general-purpose hash, 5x faster than SipHash and 10x faster than BLAKE2. void operator()(const HHKey& key, const char* HH_RESTRICT bytes, - const size_t size, HHResult64* HH_RESTRICT hash, int) const; + const size_t size, HHResult64* HH_RESTRICT hash) const; void operator()(const HHKey& key, const char* HH_RESTRICT bytes, - const size_t size, HHResult128* HH_RESTRICT hash, int) const; + const size_t size, HHResult128* HH_RESTRICT hash) const; void operator()(const HHKey& key, const char* HH_RESTRICT bytes, - const size_t size, HHResult256* HH_RESTRICT hash, int) const; + const size_t size, HHResult256* HH_RESTRICT hash) const; }; -// Intended for use with a test; packaging this in target-specific code allows -// invocation via InstructionSets::RunAll. -template <class Target> -struct HighwayHashTest { - // Verifies the hash result matches "expected". Calls "notify" with - // Target::Name() and whether the comparison succeeded. - void operator()(const HHKey& key, const char* HH_RESTRICT bytes, - const size_t size, const HHResult64* expected, - void (*notify)(const char*, bool)) const; - void operator()(const HHKey& key, const char* HH_RESTRICT bytes, - const size_t size, const HHResult128* expected, - void (*notify)(const char*, bool)) const; - void operator()(const HHKey& key, const char* HH_RESTRICT bytes, - const size_t size, const HHResult256* expected, - void (*notify)(const char*, bool)) const; -}; - -template <class Target> -struct HighwayHashCatTest { - // Partitions "bytes" into zero to three fragments and ensures HighwayHashCat - // returns the same result as HighwayHashT(bytes, sum_fragment_size). - // Calls "notify" with Target::Name() and whether the comparison succeeded. - // The value of "expected" is ignored; it is only used for overloading. - void operator()(const HHKey& key, const char* HH_RESTRICT bytes, - const uint64_t size, const HHResult64* expected, - void (*notify)(const char*, bool)) const; - void operator()(const HHKey& key, const char* HH_RESTRICT bytes, - const uint64_t size, const HHResult128* expected, - void (*notify)(const char*, bool)) const; - void operator()(const HHKey& key, const char* HH_RESTRICT bytes, - const uint64_t size, const HHResult256* expected, - void (*notify)(const char*, bool)) const; -}; - - } // namespace highwayhash #endif // HIGHWAYHASH_HIGHWAYHASH_TARGET_H_
diff --git a/highwayhash/highwayhash_test.cc b/highwayhash/highwayhash_test.cc index 6bdede7..b0f8b88 100644 --- a/highwayhash/highwayhash_test.cc +++ b/highwayhash/highwayhash_test.cc
@@ -15,18 +15,21 @@ // Ensures each implementation of HighwayHash returns consistent and unchanging // hash values. -#include "highwayhash/highwayhash_target.h" +#include "highwayhash/highwayhash_test_target.h" +#include <stddef.h> +#include <atomic> #include <cstdio> #include <cstdlib> -#include <map> -#include <string> #include <vector> #ifdef HH_GOOGLETEST #include "testing/base/public/gunit.h" #endif +#include "highwayhash/data_parallel.h" +#include "highwayhash/instruction_sets.h" + // Define to nonzero in order to print the (new) golden outputs. #define PRINT_RESULTS 0 @@ -37,7 +40,7 @@ const size_t kMaxSize = 64; #if PRINT_RESULTS -void Print(const HHResult64 result) { printf("0x%016llXull,\n", result); } +void Print(const HHResult64 result) { printf("0x%016lXull,\n", result); } // For HHResult128/256. template <int kNumLanes> @@ -47,61 +50,62 @@ if (i != 0) { printf(", "); } - printf("0x%016llXull", result[i]); + printf("0x%016lXull", result[i]); } printf("},\n"); } #endif // PRINT_RESULTS -// Keyed by Target::Name() so we can report which Targets were tested. -using FailureCounts = std::map<std::string, int>; - -// 'Global' data because the notify callbacks cannot accept state arguments. -FailureCounts& ImplementationFailures() { - // Local static ensures init order is well-defined. - static FailureCounts counts; - return counts; +// Called when any test fails; exits immediately because one mismatch usually +// implies many others. +void OnFailure(const char* target_name, const size_t size) { + printf("Mismatch at size %zu\n", size); +#ifdef HH_GOOGLETEST + EXPECT_TRUE(false); +#endif + exit(1); } -void NotifyImplementationResult(const char* target_name, const bool ok) { - ImplementationFailures()[target_name] += !ok; -} - -// Verifies every combination of implementation and input size. +// Verifies every combination of implementation and input size. Returns which +// targets were run/verified. template <typename Result> -void VerifyImplementations(const Result (&known_good)[kMaxSize + 1]) { +TargetBits VerifyImplementations(const Result (&known_good)[kMaxSize + 1]) { const HHKey key = {0x0706050403020100ULL, 0x0F0E0D0C0B0A0908ULL, 0x1716151413121110ULL, 0x1F1E1D1C1B1A1918ULL}; + TargetBits targets = ~0U; + // For each test input: empty string, 00, 00 01, ... char in[kMaxSize + 1] = {0}; + // Fast enough that we don't need a thread pool. for (uint64_t size = 0; size <= kMaxSize; ++size) { in[size] = static_cast<char>(size); #if PRINT_RESULTS Result actual; - InstructionSets::Run<HighwayHash>(key, in, size, &actual, 0); + targets &= InstructionSets::Run<HighwayHash>(key, in, size, &actual); Print(actual); #else const Result* expected = &known_good[size]; - InstructionSets::RunAll<HighwayHashTest>(key, in, size, expected, - &NotifyImplementationResult); + targets &= InstructionSets::RunAll<HighwayHashTest>(key, in, size, expected, + &OnFailure); #endif } + return targets; } // Cat -FailureCounts& CatFailures() { - static FailureCounts counts; - return counts; +void OnCatFailure(const char* target_name, const size_t size) { + printf("Cat mismatch at size %zu\n", size); +#ifdef HH_GOOGLETEST + EXPECT_TRUE(false); +#endif + exit(1); } -void NotifyCatResult(const char* target_name, const bool ok) { - CatFailures()[target_name] += !ok; -} - +// Returns which targets were run/verified. template <typename Result> -void VerifyCat() { +TargetBits VerifyCat(ThreadPool* pool) { // Reversed order vs prior test. const HHKey key = {0x1F1E1D1C1B1A1918ULL, 0x1716151413121110ULL, 0x0F0E0D0C0B0A0908ULL, 0x0706050403020100ULL}; @@ -111,11 +115,17 @@ flat.reserve(kMaxSize); srand(129); for (size_t size = 0; size < kMaxSize; ++size) { - Result dummy; - InstructionSets::RunAll<HighwayHashCatTest>(key, flat.data(), size, &dummy, - &NotifyCatResult); flat.push_back(static_cast<char>(rand() & 0xFF)); } + + std::atomic<TargetBits> targets{~0U}; + + pool->Run(0, kMaxSize, [&key, &flat, &targets](const uint32_t i) { + Result dummy; + targets.fetch_and(InstructionSets::RunAll<HighwayHashCatTest>( + key, flat.data(), i, &dummy, &OnCatFailure)); + }); + return targets.load(); } const HHResult64 kExpected64[kMaxSize + 1] = { @@ -342,29 +352,25 @@ 0x24CFDCA800C34770ull}}; void RunTests() { - bool ok = true; + // TODO(janwas): detect number of cores. + ThreadPool pool(4); - VerifyImplementations(kExpected64); - VerifyImplementations(kExpected128); - VerifyImplementations(kExpected256); - for (const auto& pair : ImplementationFailures()) { - printf("%10s: %s\n", pair.first.c_str(), - pair.second == 0 ? "OK" : "failed"); - ok &= pair.second == 0; - } + TargetBits tested = ~0U; + tested &= VerifyImplementations(kExpected64); + tested &= VerifyImplementations(kExpected128); + tested &= VerifyImplementations(kExpected256); + // Any failure causes immediate exit, so apparently all succeeded. + HH_TARGET_NAME::ForeachTarget(tested, [](const TargetBits target) { + printf("%10s: OK\n", TargetName(target)); + }); - VerifyCat<HHResult64>(); - VerifyCat<HHResult128>(); - VerifyCat<HHResult256>(); - for (const auto& pair : CatFailures()) { - printf("%10s: %s\n", pair.first.c_str(), - pair.second == 0 ? "OK" : "failed"); - ok &= pair.second == 0; - } - -#ifdef HH_GOOGLETEST - EXPECT_TRUE(ok); -#endif + tested = ~0U; + tested &= VerifyCat<HHResult64>(&pool); + tested &= VerifyCat<HHResult128>(&pool); + tested &= VerifyCat<HHResult256>(&pool); + HH_TARGET_NAME::ForeachTarget(tested, [](const TargetBits target) { + printf("%10sCat: OK\n", TargetName(target)); + }); } #ifdef HH_GOOGLETEST
diff --git a/highwayhash/highwayhash_test_avx2.cc b/highwayhash/highwayhash_test_avx2.cc new file mode 100644 index 0000000..6bb60b9 --- /dev/null +++ b/highwayhash/highwayhash_test_avx2.cc
@@ -0,0 +1,16 @@ +// Copyright 2017 Google Inc. All Rights Reserved. +// +// 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. + +#define HH_TARGET_NAME AVX2 +#include "highwayhash/highwayhash_test_target.cc"
diff --git a/highwayhash/highwayhash_test_portable.cc b/highwayhash/highwayhash_test_portable.cc new file mode 100644 index 0000000..67213e5 --- /dev/null +++ b/highwayhash/highwayhash_test_portable.cc
@@ -0,0 +1,16 @@ +// Copyright 2017 Google Inc. All Rights Reserved. +// +// 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. + +#define HH_TARGET_NAME Portable +#include "highwayhash/highwayhash_test_target.cc"
diff --git a/highwayhash/highwayhash_test_sse41.cc b/highwayhash/highwayhash_test_sse41.cc new file mode 100644 index 0000000..5e7da27 --- /dev/null +++ b/highwayhash/highwayhash_test_sse41.cc
@@ -0,0 +1,16 @@ +// Copyright 2017 Google Inc. All Rights Reserved. +// +// 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. + +#define HH_TARGET_NAME SSE41 +#include "highwayhash/highwayhash_test_target.cc"
diff --git a/highwayhash/highwayhash_test_target.cc b/highwayhash/highwayhash_test_target.cc new file mode 100644 index 0000000..f5d10d5 --- /dev/null +++ b/highwayhash/highwayhash_test_target.cc
@@ -0,0 +1,211 @@ +// Copyright 2017 Google Inc. All Rights Reserved. +// +// 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. + +// WARNING: compiled with different flags => must not define/instantiate any +// inline functions, nor include any headers that do - see instruction_sets.h. + +#include "highwayhash/highwayhash_test_target.h" + +#include "highwayhash/highwayhash.h" + +#ifndef HH_DISABLE_TARGET_SPECIFIC +namespace highwayhash { +namespace { + +void NotifyIfUnequal(const size_t size, const HHResult64& expected, + const HHResult64& actual, const HHNotify notify) { + if (expected != actual) { + (*notify)(TargetName(HH_TARGET), size); + } +} + +// Overload for HHResult128 or HHResult256 (arrays). +template <size_t kNumLanes> +void NotifyIfUnequal(const size_t size, const uint64_t (&expected)[kNumLanes], + const uint64_t (&actual)[kNumLanes], + const HHNotify notify) { + for (size_t i = 0; i < kNumLanes; ++i) { + if (expected[i] != actual[i]) { + (*notify)(TargetName(HH_TARGET), size); + return; + } + } +} + +// Shared logic for all HighwayHashTest::operator() overloads. +template <typename Result> +void TestHighwayHash(HHStateT<HH_TARGET>* HH_RESTRICT state, + const char* HH_RESTRICT bytes, const size_t size, + const Result* expected, const HHNotify notify) { + Result actual; + HighwayHashT(state, bytes, size, &actual); + NotifyIfUnequal(size, *expected, actual, notify); +} + +// Shared logic for all HighwayHashCatTest::operator() overloads. +template <typename Result> +void TestHighwayHashCat(const HHKey& key, const char* HH_RESTRICT bytes, + const size_t size, const Result* expected, + const HHNotify notify) { + // Slightly faster to compute the expected prefix hashes only once. + // Use new instead of vector to avoid headers with inline functions. + Result* results = new Result[size + 1]; + for (size_t i = 0; i <= size; ++i) { + HHStateT<HH_TARGET> state_flat(key); + HighwayHashT(&state_flat, bytes, i, &results[i]); + } + + // Splitting into three fragments/Append should cover all codepaths. + const size_t max_fragment_size = size / 3; + for (size_t size1 = 0; size1 < max_fragment_size; ++size1) { + for (size_t size2 = 0; size2 < max_fragment_size; ++size2) { + for (size_t size3 = 0; size3 < max_fragment_size; ++size3) { + HighwayHashCatT<HH_TARGET> cat(key); + const char* pos = bytes; + cat.Append(pos, size1); + pos += size1; + cat.Append(pos, size2); + pos += size2; + cat.Append(pos, size3); + pos += size3; + + Result result_cat; + cat.Finalize(&result_cat); + + const size_t total_size = pos - bytes; + NotifyIfUnequal(total_size, results[total_size], result_cat, notify); + } + } + } + + delete[] results; +} + +} // namespace + +template <TargetBits Target> +void HighwayHashTest<Target>::operator()(const HHKey& key, + const char* HH_RESTRICT bytes, + const size_t size, + const HHResult64* expected, + const HHNotify notify) const { + HHStateT<Target> state(key); + TestHighwayHash(&state, bytes, size, expected, notify); +} + +template <TargetBits Target> +void HighwayHashTest<Target>::operator()(const HHKey& key, + const char* HH_RESTRICT bytes, + const size_t size, + const HHResult128* expected, + const HHNotify notify) const { + HHStateT<Target> state(key); + TestHighwayHash(&state, bytes, size, expected, notify); +} + +template <TargetBits Target> +void HighwayHashTest<Target>::operator()(const HHKey& key, + const char* HH_RESTRICT bytes, + const size_t size, + const HHResult256* expected, + const HHNotify notify) const { + HHStateT<Target> state(key); + TestHighwayHash(&state, bytes, size, expected, notify); +} + +template <TargetBits Target> +void HighwayHashCatTest<Target>::operator()(const HHKey& key, + const char* HH_RESTRICT bytes, + const uint64_t size, + const HHResult64* expected, + const HHNotify notify) const { + TestHighwayHashCat(key, bytes, size, expected, notify); +} + +template <TargetBits Target> +void HighwayHashCatTest<Target>::operator()(const HHKey& key, + const char* HH_RESTRICT bytes, + const uint64_t size, + const HHResult128* expected, + const HHNotify notify) const { + TestHighwayHashCat(key, bytes, size, expected, notify); +} + +template <TargetBits Target> +void HighwayHashCatTest<Target>::operator()(const HHKey& key, + const char* HH_RESTRICT bytes, + const uint64_t size, + const HHResult256* expected, + const HHNotify notify) const { + TestHighwayHashCat(key, bytes, size, expected, notify); +} + +// Instantiate for the current target. +template struct HighwayHashTest<HH_TARGET>; +template struct HighwayHashCatTest<HH_TARGET>; + +//----------------------------------------------------------------------------- +// benchmark + +namespace { + +template <TargetBits Target> +uint64_t RunHighway(const size_t size) { + static const HHKey key HH_ALIGNAS(32) = {0, 1, 2, 3}; + char in[kMaxBenchmarkInputSize]; + in[0] = static_cast<char>(size & 0xFF); + HHResult64 result; + HHStateT<Target> state(key); + HighwayHashT(&state, in, size, &result); + return result; +} + +template <TargetBits Target> +uint64_t RunHighwayCat(const size_t size) { + static const HHKey key HH_ALIGNAS(32) = {0, 1, 2, 3}; + HH_ALIGNAS(64) HighwayHashCatT<Target> cat(key); + char in[kMaxBenchmarkInputSize]; + in[0] = static_cast<char>(size & 0xFF); + const size_t half_size = size / 2; + cat.Append(in, half_size); + cat.Append(in + half_size, size - half_size); + HHResult64 result; + cat.Finalize(&result); + return result; +} + +} // namespace + +template <TargetBits Target> +void HighwayHashBenchmark<Target>::operator()(DurationsForInputs* input_map, + NotifyBenchmark notify, + void* context) const { + MeasureDurations(&RunHighway<Target>, input_map); + notify("HighwayHash", TargetName(Target), input_map, context); +} + +template <TargetBits Target> +void HighwayHashCatBenchmark<Target>::operator()(DurationsForInputs* input_map, + NotifyBenchmark notify, + void* context) const { + MeasureDurations(&RunHighwayCat<Target>, input_map); + notify("HighwayHashCat", TargetName(Target), input_map, context); +} + +// Instantiate for the current target. +template struct HighwayHashBenchmark<HH_TARGET>; +template struct HighwayHashCatBenchmark<HH_TARGET>; + +} // namespace highwayhash +#endif // HH_DISABLE_TARGET_SPECIFIC
diff --git a/highwayhash/highwayhash_test_target.h b/highwayhash/highwayhash_test_target.h new file mode 100644 index 0000000..78f6d36 --- /dev/null +++ b/highwayhash/highwayhash_test_target.h
@@ -0,0 +1,87 @@ +// Copyright 2017 Google Inc. All Rights Reserved. +// +// 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. + +#ifndef HIGHWAYHASH_HIGHWAYHASH_TARGET_H_ +#define HIGHWAYHASH_HIGHWAYHASH_TARGET_H_ + +// Tests called by InstructionSets::RunAll, so we can verify all +// implementations supported by the current CPU. + +// WARNING: compiled with different flags => must not define/instantiate any +// inline functions, nor include any headers that do - see instruction_sets.h. + +#include <stddef.h> + +#include "highwayhash/arch_specific.h" +#include "highwayhash/compiler_specific.h" +#include "highwayhash/hh_types.h" +#include "highwayhash/nanobenchmark.h" + +namespace highwayhash { + +// Verifies the hash result matches "expected" and calls "notify" if not. +template <TargetBits Target> +struct HighwayHashTest { + void operator()(const HHKey& key, const char* HH_RESTRICT bytes, + const size_t size, const HHResult64* expected, + const HHNotify notify) const; + void operator()(const HHKey& key, const char* HH_RESTRICT bytes, + const size_t size, const HHResult128* expected, + const HHNotify notify) const; + void operator()(const HHKey& key, const char* HH_RESTRICT bytes, + const size_t size, const HHResult256* expected, + const HHNotify notify) const; +}; + +// For every possible partition of "bytes" into zero to three fragments, +// verifies HighwayHashCat returns the same result as HighwayHashT of the +// concatenated fragments, and calls "notify" if not. The value of "expected" +// is ignored; it is only used for overloading. +template <TargetBits Target> +struct HighwayHashCatTest { + void operator()(const HHKey& key, const char* HH_RESTRICT bytes, + const uint64_t size, const HHResult64* expected, + const HHNotify notify) const; + void operator()(const HHKey& key, const char* HH_RESTRICT bytes, + const uint64_t size, const HHResult128* expected, + const HHNotify notify) const; + void operator()(const HHKey& key, const char* HH_RESTRICT bytes, + const uint64_t size, const HHResult256* expected, + const HHNotify notify) const; +}; + +// Called by benchmark with prefix, target_name, input_map, context. +// This function must set input_map->num_items to 0. +using NotifyBenchmark = void (*)(const char*, const char*, DurationsForInputs*, + void*); + +constexpr size_t kMaxBenchmarkInputSize = 1024; + +// Calls "notify" with benchmark results for the input sizes specified by +// "input_map" (<= kMaxBenchmarkInputSize) plus a "context" parameter. +template <TargetBits Target> +struct HighwayHashBenchmark { + void operator()(DurationsForInputs* input_map, NotifyBenchmark notify, + void* context) const; +}; + +template <TargetBits Target> +struct HighwayHashCatBenchmark { + void operator()(DurationsForInputs* input_map, NotifyBenchmark notify, + void* context) const; +}; + +} // namespace highwayhash + +#endif // HIGHWAYHASH_HIGHWAYHASH_TARGET_H_
diff --git a/highwayhash/instruction_sets.cc b/highwayhash/instruction_sets.cc index 514bf31..a02e1f8 100644 --- a/highwayhash/instruction_sets.cc +++ b/highwayhash/instruction_sets.cc
@@ -13,21 +13,22 @@ // limitations under the License. #include "highwayhash/instruction_sets.h" +#include "highwayhash/arch_specific.h" + +// Currently there are only specialized targets for X64; other architectures +// only use HH_TARGET_Portable, in which case Supported() just returns that. +#if HH_ARCH_X64 #include <atomic> -#if HH_ARCH_X64 -#include <xmmintrin.h> // _mm_pause -#endif - namespace highwayhash { + namespace { bool IsBitSet(const uint32_t reg, const int index) { return (reg & (1U << index)) != 0; } -#if HH_ARCH_X64 // Returns the lower 32 bits of extended control register 0. // Requires CPU support for "OSXSAVE" (see below). uint32_t ReadXCR0() { @@ -42,76 +43,67 @@ return xcr0; #endif } -#endif // HH_ARCH_X64 - -// The first thread to increment this will initialize instruction_set_bits_. -std::atomic<int> init_counter{0}; - -} // namespace // 0 iff not yet initialized by Supported(). // Not function-local => no compiler-generated locking. -std::atomic<uint64_t> instruction_set_bits_{0}; +std::atomic<TargetBits> supported_{0}; -uint64_t InstructionSets::Supported() { - uint64_t flags = instruction_set_bits_.load(std::memory_order_acquire); +// Bits indicating which instruction set extensions are supported. +enum { + kBitSSE = 1 << 0, + kBitSSE2 = 1 << 1, + kBitSSE3 = 1 << 2, + kBitSSSE3 = 1 << 3, + kBitSSE41 = 1 << 4, + kBitSSE42 = 1 << 5, + kBitAVX = 1 << 6, + kBitAVX2 = 1 << 7, + kBitFMA = 1 << 8, + kBitLZCNT = 1 << 9, + kBitBMI = 1 << 10, + kBitBMI2 = 1 << 11, + + kGroupAVX2 = kBitAVX | kBitAVX2 | kBitFMA | kBitLZCNT | kBitBMI | kBitBMI2, + kGroupSSE41 = kBitSSE | kBitSSE2 | kBitSSE3 | kBitSSSE3 | kBitSSE41 +}; + +} // namespace + +TargetBits InstructionSets::Supported() { + TargetBits supported = supported_.load(std::memory_order_acquire); // Already initialized, return that. - if (HH_LIKELY(flags != 0)) { - return flags; + if (HH_LIKELY(supported)) { + return supported; } - // Another thread is initializing; wait until it finishes. - if (HH_UNLIKELY(init_counter.fetch_add(1) != 0)) { - for (;;) { - flags = instruction_set_bits_.load(std::memory_order_acquire); - if (flags != 0) { - return flags; - } -#if HH_ARCH_X64 - _mm_pause(); -#endif - } - } + uint32_t flags = 0; + uint32_t abcd[4]; - flags = kInitialized; - -#if HH_ARCH_X64 - const uint32_t max_level = []() { - uint32_t abcd[4]; - Cpuid(0, 0, abcd); - return abcd[0]; - }(); + Cpuid(0, 0, abcd); + const uint32_t max_level = abcd[0]; // Standard feature flags - const bool has_osxsave = [&flags]() { - uint32_t abcd[4]; - Cpuid(1, 0, abcd); - flags += IsBitSet(abcd[3], 25) ? kSSE : 0; - flags += IsBitSet(abcd[3], 26) ? kSSE2 : 0; - flags += IsBitSet(abcd[2], 0) ? kSSE3 : 0; - flags += IsBitSet(abcd[2], 9) ? kSSSE3 : 0; - flags += IsBitSet(abcd[2], 19) ? kSSE41 : 0; - flags += IsBitSet(abcd[2], 20) ? kSSE42 : 0; - flags += IsBitSet(abcd[2], 23) ? kPOPCNT : 0; - flags += IsBitSet(abcd[2], 12) ? kFMA : 0; - flags += IsBitSet(abcd[2], 28) ? kAVX : 0; - return IsBitSet(abcd[2], 27); // has_osxsave - }(); + Cpuid(1, 0, abcd); + flags |= IsBitSet(abcd[3], 25) ? kBitSSE : 0; + flags |= IsBitSet(abcd[3], 26) ? kBitSSE2 : 0; + flags |= IsBitSet(abcd[2], 0) ? kBitSSE3 : 0; + flags |= IsBitSet(abcd[2], 9) ? kBitSSSE3 : 0; + flags |= IsBitSet(abcd[2], 19) ? kBitSSE41 : 0; + flags |= IsBitSet(abcd[2], 20) ? kBitSSE42 : 0; + flags |= IsBitSet(abcd[2], 12) ? kBitFMA : 0; + flags |= IsBitSet(abcd[2], 28) ? kBitAVX : 0; + const bool has_osxsave = IsBitSet(abcd[2], 27); // Extended feature flags - { - uint32_t abcd[4]; - Cpuid(0x80000001U, 0, abcd); - flags += IsBitSet(abcd[2], 5) ? kLZCNT : 0; - } + Cpuid(0x80000001U, 0, abcd); + flags |= IsBitSet(abcd[2], 5) ? kBitLZCNT : 0; // Extended features if (max_level >= 7) { - uint32_t abcd[4]; Cpuid(7, 0, abcd); - flags += IsBitSet(abcd[1], 3) ? kBMI : 0; - flags += IsBitSet(abcd[1], 5) ? kAVX2 : 0; - flags += IsBitSet(abcd[1], 8) ? kBMI2 : 0; + flags |= IsBitSet(abcd[1], 3) ? kBitBMI : 0; + flags |= IsBitSet(abcd[1], 5) ? kBitAVX2 : 0; + flags |= IsBitSet(abcd[1], 8) ? kBitBMI2 : 0; } // Verify OS support for XSAVE, without which XMM/YMM registers are not @@ -120,18 +112,30 @@ const uint32_t xcr0 = ReadXCR0(); // XMM if ((xcr0 & 2) == 0) { - flags &= ~(kSSE | kSSE2 | kSSE3 | kSSSE3 | kSSE41 | kSSE42 | kAVX | - kAVX2 | kFMA); + flags &= ~(kBitSSE | kBitSSE2 | kBitSSE3 | kBitSSSE3 | kBitSSE41 | + kBitSSE42 | kBitAVX | kBitAVX2 | kBitFMA); } // YMM if ((xcr0 & 4) == 0) { - flags &= ~(kAVX | kAVX2); + flags &= ~(kBitAVX | kBitAVX2); } } -#endif // HH_ARCH_X64 - instruction_set_bits_.store(flags, std::memory_order_release); - return flags; + // Also indicates "supported" has been initialized. + supported = HH_TARGET_Portable; + + // Set target bit(s) if all their group's flags are all set. + if ((flags & kGroupAVX2) == kGroupAVX2) { + supported |= HH_TARGET_AVX2; + } + if ((flags & kGroupSSE41) == kGroupSSE41) { + supported |= HH_TARGET_SSE41; + } + + supported_.store(supported, std::memory_order_release); + return supported; } } // namespace highwayhash + +#endif // HH_ARCH_X64
diff --git a/highwayhash/instruction_sets.h b/highwayhash/instruction_sets.h index 60ba1a1..88bc1bc 100644 --- a/highwayhash/instruction_sets.h +++ b/highwayhash/instruction_sets.h
@@ -21,115 +21,66 @@ // argument, add a source file defining its operator() and instantiating // Functor<HH_TARGET>, add a cc_library_for_targets rule for that source file, // and call InstructionSets::Run<Functor>(/*args*/). -// -// WARNING: any source or header file that is compiled with special flags -// (i.e. *_target.cc and its transitive dependencies, including this header) -// must not define inline functions also used from other code. -// -// Background: AVX2 intrinsics require a compiler flag that also allows the -// compiler to generate AVX2 code. Compiling inline functions with differing -// flags violates the one definition rule because the generated code may differ. -// This can lead to crashes if the linker chooses the AVX2 version and uses it -// outside the codepaths guarded by the CPU capability checks in Run(). -// -// Workaround: please ensure such source/header files do NOT include any -// headers containing inline functions, nor define/instantiate any inline -// functions themselves that might be used in other code. Note that Run* below -// are only instantiated from normal code, so they are safe. -#include <stdint.h> +#include <utility> // std::forward -#include "highwayhash/arch_specific.h" +#include "highwayhash/arch_specific.h" // HH_TARGET_* #include "highwayhash/compiler_specific.h" namespace highwayhash { -// Forward declarations because the definitions require target-specific copts. -#if HH_ARCH_X64 -struct TargetAVX2; -struct TargetSSE41; -#endif -struct TargetPortable; - -// Detects instruction sets and dispatches to the best available specialization -// of a user-defined functor. +// Detects TargetBits and calls specializations of a user-defined functor. class InstructionSets { public: - // Chooses the best available Target* for the current CPU and returns - // Func<Target>::operator()(a1..a5). Dispatch overhead is low, about 4 cycles, - // but this should be called infrequently (by hoisting it out of loops). - // We cannot use variadic arguments because std::forward is defined by - // <utility>, which also defines other inline functions. - template <template <class Target> class Func, typename T1, typename T2, - typename T3, typename T4, typename T5> - static HH_INLINE void Run(const T1& a1, const T2 a2, const T3 a3, const T4 a4, - const T5 a5) { - const uint64_t flags = Supported(); - +// Returns bit array of HH_TARGET_* supported by the current CPU. +// The HH_TARGET_Portable bit is guaranteed to be set. #if HH_ARCH_X64 - if (HH_LIKELY((flags & kGroupAVX2) == kGroupAVX2)) { - return Func<TargetAVX2>()(a1, a2, a3, a4, a5); - } else if (HH_LIKELY((flags & kGroupSSE41) == kGroupSSE41)) { - return Func<TargetSSE41>()(a1, a2, a3, a4, a5); - } else -#endif // HH_ARCH_X64 - { - return Func<TargetPortable>()(a1, a2, a3, a4, a5); + static TargetBits Supported(); +#else + static HH_INLINE TargetBits Supported() { return HH_TARGET_Portable; } +#endif + + // Chooses the best available "Target" for the current CPU, runs the + // corresponding Func<Target>::operator()(args) and returns that Target + // (a single bit). The overhead of dispatching is low, about 4 cycles, but + // this should only be called infrequently (e.g. hoisting it out of loops). + template <template <TargetBits> class Func, typename... Args> + static HH_INLINE TargetBits Run(Args&&... args) { +#if HH_ARCH_X64 + const TargetBits supported = Supported(); + if (supported & HH_TARGET_AVX2) { + Func<HH_TARGET_AVX2>()(std::forward<Args>(args)...); + return HH_TARGET_AVX2; } + if (supported & HH_TARGET_SSE41) { + Func<HH_TARGET_SSE41>()(std::forward<Args>(args)...); + return HH_TARGET_SSE41; + } +#endif // HH_ARCH_X64 + + Func<HH_TARGET_Portable>()(std::forward<Args>(args)...); + return HH_TARGET_Portable; } - // Calls Func<Target>::operator()(a1..a5) for all targets supported by the - // current CPU. We cannot use variadic arguments because std::forward is - // defined by <utility>, which also defines other inline functions. - template <template <class Target> class Func, typename T1, typename T2, - typename T3, typename T4, typename T5> - static HH_INLINE void RunAll(const T1& a1, const T2 a2, const T3 a3, - const T4 a4, const T5 a5) { - const uint64_t flags = Supported(); - + // Calls Func<Target>::operator()(args) for all Target supported by the + // current CPU, and returns their HH_TARGET_* bits. + template <template <TargetBits> class Func, typename... Args> + static HH_INLINE TargetBits RunAll(Args&&... args) { #if HH_ARCH_X64 - if (HH_LIKELY((flags & kGroupAVX2) == kGroupAVX2)) { - Func<TargetAVX2>()(a1, a2, a3, a4, a5); + const TargetBits supported = Supported(); + if (supported & HH_TARGET_AVX2) { + Func<HH_TARGET_AVX2>()(std::forward<Args>(args)...); } - if (HH_LIKELY((flags & kGroupSSE41) == kGroupSSE41)) { - Func<TargetSSE41>()(a1, a2, a3, a4, a5); + if (supported & HH_TARGET_SSE41) { + Func<HH_TARGET_SSE41>()(std::forward<Args>(args)...); } +#else + const TargetBits supported = HH_TARGET_Portable; #endif // HH_ARCH_X64 - Func<TargetPortable>()(a1, a2, a3, a4, a5); + Func<HH_TARGET_Portable>()(std::forward<Args>(args)...); + return supported; // i.e. all that were run } - - private: - // Bits indicating which instruction set extensions are supported. - // This enables compact/fast implementations of Has*() below. - enum { - // Always set so we can distinguish between "not yet initialized" and - // "no extensions available". - kInitialized = 1, - -#if HH_ARCH_X64 - kSSE = 2, - kSSE2 = 4, - kSSE3 = 8, - kSSSE3 = 0x10, - kSSE41 = 0x20, - kSSE42 = 0x40, - kPOPCNT = 0x80, - kAVX = 0x100, - kAVX2 = 0x200, - kFMA = 0x400, - kLZCNT = 0x800, - kBMI = 0x1000, - kBMI2 = 0x2000, - - kGroupAVX2 = kAVX | kAVX2 | kFMA | kLZCNT | kBMI | kBMI2, - kGroupSSE41 = kSSE | kSSE2 | kSSE3 | kSSSE3 | kSSE41 | kPOPCNT -#endif // HH_ARCH_X64 - }; - - // Returns bitfield of all instruction sets supported on this CPU. - // Thread-safe, only detects CPU support once. - static uint64_t Supported(); }; } // namespace highwayhash
diff --git a/highwayhash/load3.h b/highwayhash/load3.h new file mode 100644 index 0000000..3ff1bbd --- /dev/null +++ b/highwayhash/load3.h
@@ -0,0 +1,131 @@ +// Copyright 2017 Google Inc. All Rights Reserved. +// +// 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. + +#ifndef HIGHWAYHASH_HH_LOAD3_H_ +#define HIGHWAYHASH_HH_LOAD3_H_ + +// WARNING: compiled with different flags => must not define/instantiate any +// inline functions, nor include any headers that do - see instruction_sets.h. + +#include <stddef.h> +#include <stdint.h> + +#include "highwayhash/arch_specific.h" +#include "highwayhash/compiler_specific.h" +#include "highwayhash/endianess.h" + +namespace highwayhash { +// To prevent ODR violations when including this from multiple translation +// units (TU) that are compiled with different flags, the contents must reside +// in a namespace whose name is unique to the TU. NOTE: this behavior is +// incompatible with precompiled modules and requires textual inclusion instead. +namespace HH_TARGET_NAME { + +// Loads 0 to 3 bytes from a given location using one of several policies. +// These are potentially faster than 8-bit loads, but require certain additional +// promises by the caller: that 'out of bounds' memory accesses are allowed, +// and/or that the bytes may be permuted or duplicated. +class Load3 { + public: + // In increasing order of complexity: + struct AllowReadBeforeAndReturn {}; + struct AllowReadBefore {}; + struct AllowUnordered {}; + struct AllowNone {}; + + // Up to 4 preceding bytes may be read and returned along with the 0..3 + // valid bytes. The valid bytes are in little-endian order, except that the + // preceding bytes occupy the least-significant bytes. + HH_INLINE uint32_t operator()(AllowReadBeforeAndReturn, const char* from, + const size_t size_mod4) { + // It's safe to read before "from", so we can load 32 bits, which is faster + // than individual byte loads. We assume little-endian byte order, so + // big-endian platforms will need to swap. Type punning can generate + // incorrect code if compiled with strict aliasing; the only safe + // alternatives are memcpy and reading through char*. We must avoid memcpy + // because string.h must not be included per the warning above. On GCC and + // Clang, we can use a builtin instead. + uint32_t last4; + __builtin_memcpy(&last4, from + size_mod4 - 4, 4); + return host_from_le32(last4); + } + + // As above, but preceding bytes are removed and upper byte(s) are zero. + HH_INLINE uint64_t operator()(AllowReadBefore, const char* from, + const size_t size_mod4) { + // Shift 0..3 valid bytes into LSB as if loaded in little-endian order. + // 64-bit type enables 32-bit shift when size_mod4 == 0. + uint64_t last3 = operator()(AllowReadBeforeAndReturn(), from, size_mod4); + last3 >>= 32 - (size_mod4 * 8); + return last3; + } + + // The bytes need not be loaded in little-endian order. This particular order + // (and the duplication of some bytes depending on "size_mod4") was chosen for + // computational convenience and can no longer be changed because it is part + // of the HighwayHash length padding definition. + HH_INLINE uint64_t operator()(AllowUnordered, const char* from, + const size_t size_mod4) { + uint64_t last3 = 0; + // Not allowed to read any bytes; early-out is faster than reading from a + // constant array of zeros. + if (size_mod4 == 0) { + return last3; + } + + // These indices are chosen as an easy-to-compute sequence containing the + // same elements as [0, size), but repeated and/or reordered. This enables + // unconditional loads, which outperform conditional 8 or 16+8 bit loads. + const uint64_t idx0 = 0; + const uint64_t idx1 = size_mod4 >> 1; + const uint64_t idx2 = size_mod4 - 1; + // Store into least significant bytes (avoids one shift). + last3 = static_cast<uint64_t>(from[idx0]); + last3 += static_cast<uint64_t>(from[idx1]) << 8; + last3 += static_cast<uint64_t>(from[idx2]) << 16; + return last3; + } + + // Must read exactly [0, size) bytes in little-endian order. + HH_INLINE uint64_t operator()(AllowNone, const char* from, + const size_t size_mod4) { + // We need to load in little-endian order without accessing anything outside + // [from, from + size_mod4). Unrolling is faster than looping backwards. + uint64_t last3 = 0; + if (size_mod4 >= 1) { + last3 += U64FromChar(from[0]); + } + if (size_mod4 >= 2) { + last3 += U64FromChar(from[1]) << 8; + } + if (size_mod4 == 3) { + last3 += U64FromChar(from[2]) << 16; + } + return last3; + } + + private: + static HH_INLINE uint32_t U32FromChar(const char c) { + return static_cast<uint32_t>(static_cast<unsigned char>(c)); + } + + static HH_INLINE uint64_t U64FromChar(const char c) { + return static_cast<uint64_t>(static_cast<unsigned char>(c)); + } +}; + +} // namespace HH_TARGET_NAME +} // namespace highwayhash + +#endif // HIGHWAYHASH_LOAD3_H_
diff --git a/highwayhash/nanobenchmark.cc b/highwayhash/nanobenchmark.cc index 38aa4ba..f0ba6ad 100644 --- a/highwayhash/nanobenchmark.cc +++ b/highwayhash/nanobenchmark.cc
@@ -14,17 +14,424 @@ #include "highwayhash/nanobenchmark.h" +#include <algorithm> +#include <cmath> +#include <cstdio> +#include <map> +#include <random> +#include <vector> + +#include <stddef.h> + +#include "highwayhash/os_specific.h" +#include "highwayhash/robust_statistics.h" +#include "highwayhash/tsc_timer.h" + +namespace highwayhash { +namespace { + +// Enables sanity checks that verify correct operation at the cost of +// longer benchmark runs. +#ifndef NANOBENCHMARK_ENABLE_CHECKS +#define NANOBENCHMARK_ENABLE_CHECKS 0 +#endif + +#define NANOBENCHMARK_CHECK_ALWAYS(condition) \ + while (!(condition)) { \ + printf("Nanobenchmark check failed at line %d\n", __LINE__); \ + abort(); \ + } + +#if NANOBENCHMARK_ENABLE_CHECKS +#define NANOBENCHMARK_CHECK(condition) NANOBENCHMARK_CHECK_ALWAYS(condition) +#else +#define NANOBENCHMARK_CHECK(condition) +#endif + #if HH_MSC_VERSION +// MSVC does not support inline assembly anymore (and never supported GCC's +// RTL constraints used below). #pragma optimize("", off) - -namespace nanobenchmark { - // Self-assignment with #pragma optimize("off") might be expected to prevent // elision, but it does not with MSVC 2015. void UseCharPointer(volatile const char*) {} -} - #pragma optimize("", on) +template <class T> +inline void PreventElision(T&& output) { + UseCharPointer(reinterpret_cast<volatile const char*>(&output)); +} + +#else + +// Prevents the compiler from eliding the computations that led to "output". +// Works by indicating to the compiler that "output" is being read and modified. +// The +r constraint avoids unnecessary writes to memory, but only works for +// FuncOutput. +template <class T> +inline void PreventElision(T&& output) { + asm volatile("" : "+r"(output) : : "memory"); +} + #endif + +HH_NOINLINE FuncOutput Func1(const FuncInput input) { return input + 1; } +HH_NOINLINE FuncOutput Func2(const FuncInput input) { return input + 2; } + +// Cycles elapsed = difference between two cycle counts. Must be unsigned to +// ensure wraparound on overflow. +using Duration = uint32_t; + +// Even with high-priority pinned threads and frequency throttling disabled, +// elapsed times are noisy due to interrupts or SMM operations. It might help +// to detect such events via transactions and omit affected measurements. +// Unfortunately, TSX is currently unavailable due to a bug. We achieve +// repeatable results with a robust measure of the central tendency ("mode"). + +// Returns time elapsed between timer Start/Stop. +Duration EstimateResolutionOnCurrentCPU(const Func func) { + // Even 128K samples are not enough to achieve repeatable results when + // throttling is enabled; the caller must perform additional aggregation. + const size_t kNumSamples = 512; + Duration samples[kNumSamples]; + for (size_t i = 0; i < kNumSamples; ++i) { + const volatile Duration t0 = Start<Duration>(); + PreventElision(func(i)); + const volatile Duration t1 = Stop<Duration>(); + NANOBENCHMARK_CHECK(t0 <= t1); + samples[i] = t1 - t0; + } + CountingSort(samples, samples + kNumSamples); + const Duration resolution = Mode(samples, kNumSamples); + NANOBENCHMARK_CHECK(resolution != 0); + return resolution; +} + +// Returns mode of EstimateResolutionOnCurrentCPU across all CPUs. This +// increases repeatability because some CPUs may be throttled or slowed down by +// interrupts. +Duration EstimateResolution(const Func func_to_measure) { + Func func = (func_to_measure == &Func2) ? &Func1 : &Func2; + + const size_t kNumSamples = 512; + std::vector<Duration> resolutions; + resolutions.reserve(kNumSamples); + + const auto cpus = AvailableCPUs(); + const size_t repetitions_per_cpu = kNumSamples / cpus.size(); + + auto affinity = GetThreadAffinity(); + for (const int cpu : cpus) { + PinThreadToCPU(cpu); + for (size_t i = 0; i < repetitions_per_cpu; ++i) { + resolutions.push_back(EstimateResolutionOnCurrentCPU(func)); + } + } + SetThreadAffinity(affinity); + free(affinity); + + Duration* const begin = resolutions.data(); + CountingSort(begin, begin + resolutions.size()); + const Duration resolution = Mode(begin, resolutions.size()); + printf("Resolution %lu\n", long(resolution)); + return resolution; +} + +// Returns cycles elapsed when running an empty region, i.e. the timer +// resolution/overhead, which will be deducted from other measurements and +// also used by InitReplicas. +Duration Resolution(const Func func) { + // Initialization is expensive and should only happen once. + static const Duration resolution = EstimateResolution(func); + return resolution; +} + +// Returns cycles elapsed when passing each of "inputs" (after in-place +// shuffling) to "func", which must return something it has computed +// so the compiler does not optimize it away. +Duration CyclesElapsed(const Duration resolution, const Func func, + std::vector<FuncInput>* inputs) { + // This benchmark attempts to measure the performance of "func" when + // called with realistic inputs, which we assume are randomly drawn + // from the given "inputs" distribution, so we shuffle those values. + std::random_shuffle(inputs->begin(), inputs->end()); + + const Duration t0 = Start<Duration>(); + for (const FuncInput input : *inputs) { + PreventElision(func(input)); + } + const Duration t1 = Stop<Duration>(); + const Duration elapsed = t1 - t0; + NANOBENCHMARK_CHECK(elapsed > resolution); + return elapsed - resolution; +} + +// Stores input values for a series of calls to the function to measure. +// We assume inputs are drawn from a known discrete probability distribution, +// modeled as a vector<FuncInput> v. The probability of a value X +// in v is count(v.begin(), v.end(), X) / v.size(). +class Inputs { + Inputs(const Inputs&) = delete; + Inputs& operator=(const Inputs&) = delete; + + public: + Inputs(const Duration resolution, const std::vector<FuncInput>& distribution, + const Func func) + : unique_(InitUnique(distribution)), + replicas_(InitReplicas(distribution, resolution, func)), + num_replicas_(replicas_.size() / distribution.size()) { + printf("NumReplicas %zu\n", num_replicas_); + } + + // Returns vector of the unique values from the input distribution. + const std::vector<FuncInput>& Unique() const { return unique_; } + + // Returns how many instances of "distribution" are in "replicas_", i.e. + // the number of occurrences of an input value that occurred only once + // in the distribution. This is the divisor for computing the duration + // of a single call. + size_t NumReplicas() const { return num_replicas_; } + + // Returns the (replicated) input distribution. Modified by caller + // (shuffled in-place) => not thread-safe. + std::vector<FuncInput>& Replicas() { return replicas_; } + + // Returns a copy of Replicas() with NumReplicas() occurrences of "input" + // removed. Used for the leave-one-out measurement. + std::vector<FuncInput> Without(const FuncInput input_to_remove) const { + // "input_to_remove" should be in the original distribution. + NANOBENCHMARK_CHECK(std::find(unique_.begin(), unique_.end(), + input_to_remove) != unique_.end()); + + std::vector<FuncInput> copy = replicas_; + auto pos = std::partition(copy.begin(), copy.end(), + [input_to_remove](const FuncInput input) { + return input_to_remove != input; + }); + // Must occur at least num_replicas_ times. + NANOBENCHMARK_CHECK(copy.end() - pos >= num_replicas_); + // (Avoids unused-variable warning.) + PreventElision(&*pos); + copy.resize(copy.size() - num_replicas_); + return copy; + } + + private: + // Returns a copy with any duplicate values removed. Initializing unique_ + // through this function allows it to be const. + static std::vector<FuncInput> InitUnique( + const std::vector<FuncInput>& distribution) { + std::vector<FuncInput> unique = distribution; + std::sort(unique.begin(), unique.end()); + unique.erase(std::unique(unique.begin(), unique.end()), unique.end()); + // Our leave-one-out measurement technique only makes sense when + // there are multiple input values. + NANOBENCHMARK_CHECK(unique.size() >= 2); + return unique; + } + + // Returns how many replicas of "distribution" are required before + // CyclesElapsed is large enough compared to the timer resolution. + static std::vector<FuncInput> InitReplicas( + const std::vector<FuncInput>& distribution, const Duration resolution, + const Func func) { + // We compute the difference in duration for inputs = Replicas() vs. + // Without(). Dividing this by num_replicas must yield a value where the + // quantization error (from the timer resolution) is sufficiently small. + const uint64_t min_elapsed = distribution.size() * resolution * 400; + + std::vector<FuncInput> replicas; + for (;;) { + AppendReplica(distribution, &replicas); + +#if NANOBENCHMARK_ENABLE_CHECKS + const uint64_t t0 = Start64(); +#endif + const Duration elapsed = CyclesElapsed(resolution, func, &replicas); +#if NANOBENCHMARK_ENABLE_CHECKS + const uint64_t t1 = Stop64(); +#endif + // Ensure the 32-bit timer didn't and won't overflow. + NANOBENCHMARK_CHECK((t1 - t0) < (1ULL << 30)); + + if (elapsed >= min_elapsed) { + return replicas; + } + } + } + + // Appends all values in "distribution" to "replicas". + static void AppendReplica(const std::vector<FuncInput>& distribution, + std::vector<FuncInput>* replicas) { + replicas->reserve(replicas->size() + distribution.size()); + for (const FuncInput input : distribution) { + replicas->push_back(input); + } + } + + const std::vector<FuncInput> unique_; + + // Modified by caller (shuffled in-place) => non-const. + std::vector<FuncInput> replicas_; + + // Initialized from replicas_. + const size_t num_replicas_; +}; + +// Holds samples of measured durations, and (robustly) reduces them to a +// single result for each unique input value. +class DurationSamples { + public: + DurationSamples(const std::vector<FuncInput>& unique_inputs, + const size_t num_samples) + : num_samples_(num_samples) { + // Preallocate storage. + for (const FuncInput input : unique_inputs) { + samples_for_input_[input].reserve(num_samples); + } + } + + void Add(const FuncInput input, const Duration sample) { + // "input" should be one of the values passed to the ctor. + NANOBENCHMARK_CHECK(samples_for_input_.find(input) != + samples_for_input_.end()); + + samples_for_input_[input].push_back(sample); + } + + // Invokes "lambda" for each (input, duration) pair. The per-call duration + // is the central tendency (the mode) of the samples. + template <class Lambda> + void Reduce(const Lambda& lambda) { + for (auto& input_and_samples : samples_for_input_) { + const FuncInput input = input_and_samples.first; + std::vector<Duration>& samples = input_and_samples.second; + + NANOBENCHMARK_CHECK(samples.size() <= num_samples_); + std::sort(samples.begin(), samples.end()); + const Duration duration = Mode(samples.data(), samples.size()); + lambda(input, duration); + } + } + + private: + const size_t num_samples_; + std::map<FuncInput, std::vector<Duration>> samples_for_input_; +}; + +// Gathers "num_samples" durations via repeated leave-one-out measurements. +DurationSamples GatherDurationSamples(const Duration resolution, Inputs& inputs, + const Func func, + const size_t num_samples) { + DurationSamples samples(inputs.Unique(), num_samples); + for (size_t i = 0; i < num_samples; ++i) { + // Total duration for all shuffled input values. This may change over time, + // so recompute it for each sample. + const Duration total = CyclesElapsed(resolution, func, &inputs.Replicas()); + + for (const FuncInput input : inputs.Unique()) { + // To isolate the durations of the calls with this input value, + // we measure the duration without those values and subtract that + // from the total, and later divide by NumReplicas. + std::vector<FuncInput> without = inputs.Without(input); + for (int rep = 0; rep < 3; ++rep) { + const Duration elapsed = CyclesElapsed(resolution, func, &without); + if (elapsed < total) { + samples.Add(input, total - elapsed); + break; + } + } + } + } + return samples; +} + +} // namespace + +DurationsForInputs::DurationsForInputs(const FuncInput* inputs, + const size_t num_inputs, + const size_t max_durations) + : num_items(0), + inputs_(inputs), + num_inputs_(num_inputs), + max_durations_(max_durations), + all_durations_(new float[num_inputs * max_durations]) { + NANOBENCHMARK_CHECK(num_inputs != 0); + NANOBENCHMARK_CHECK(max_durations != 0); + + items = new Item[num_inputs]; + for (size_t i = 0; i < num_inputs_; ++i) { + items[i].input = 0; // initialized later + items[i].num_durations = 0; + items[i].durations = all_durations_ + i * max_durations; + } +} + +DurationsForInputs::~DurationsForInputs() { + delete[] all_durations_; + delete[] items; +} + +void DurationsForInputs::AddItem(const FuncInput input, const float sample) { + for (size_t i = 0; i < num_items; ++i) { + NANOBENCHMARK_CHECK(items[i].input != input); + } + Item& item = items[num_items]; + item.input = input; + item.num_durations = 1; + item.durations[0] = sample; + ++num_items; +} + +void DurationsForInputs::AddSample(const FuncInput input, const float sample) { + for (size_t i = 0; i < num_items; ++i) { + Item& item = items[i]; + if (item.input == input) { + item.durations[item.num_durations] = sample; + ++item.num_durations; + return; + } + } + NANOBENCHMARK_CHECK(!"Item not found"); +} + +void DurationsForInputs::Item::PrintMedianAndVariability() { + // Copy so that Median can modify. + std::vector<float> duration_vec(durations, durations + num_durations); + const float median = Median(&duration_vec); + const float variability = MedianAbsoluteDeviation(duration_vec, median); + printf("%5zu: median=%5.1f cycles; median abs. deviation=%4.1f cycles\n", + input, median, variability); +} + +void MeasureDurations(const Func func, DurationsForInputs* input_map) { + const Duration resolution = Resolution(func); + + // Adds enough 'replicas' of the distribution to measure "func" given + // the timer resolution. + const std::vector<FuncInput> distribution( + input_map->inputs_, input_map->inputs_ + input_map->num_inputs_); + Inputs inputs(resolution, distribution, func); + const double per_call = 1.0 / static_cast<int>(inputs.NumReplicas()); + + // First iteration: populate input_map items. + auto samples = GatherDurationSamples(resolution, inputs, func, 512); + samples.Reduce( + [per_call, input_map](const FuncInput input, const Duration duration) { + const float sample = static_cast<float>(duration * per_call); + input_map->AddItem(input, sample); + }); + + // Subsequent iteration(s): append to input_map items' array. + for (size_t rep = 1; rep < input_map->max_durations_; ++rep) { + auto samples = GatherDurationSamples(resolution, inputs, func, 512); + samples.Reduce( + [per_call, input_map](const FuncInput input, const Duration duration) { + const float sample = static_cast<float>(duration * per_call); + input_map->AddSample(input, sample); + }); + } +} + +} // namespace highwayhash
diff --git a/highwayhash/nanobenchmark.h b/highwayhash/nanobenchmark.h index 9789c7b..ecd51d5 100644 --- a/highwayhash/nanobenchmark.h +++ b/highwayhash/nanobenchmark.h
@@ -20,36 +20,30 @@ // Measurements are precise to about 0.2 cycles. // // Example: -// #include "highwayhash/nanobenchmark.h" -// nanobenchmark::RaiseThreadPriority(); -// nanobenchmark::PinThreadToCPU(); -// const std::map<size_t, float> durations = -// nanobenchmark::MeasureWithArguments({3, 4, 7, 8}, [](const size_t size) { -// char from[8] = {static_cast<char>(size)}; -// char to[8]; -// memcpy(to, from, size); -// return to[0]; -// }); -// printf("Cycles for input = 3: %4.1f\n", durations[3]); -// printf("Cycles for input = 7: %4.1f\n", durations[7]); +// #include "highwayhash/nanobenchmark.h" +// using namespace highwayhash; // -// Alternatively, repeating samples and measurements increases the precision: +// uint64_t RegionToMeasure(size_t size) { +// char from[8] = {static_cast<char>(size)}; +// char to[8]; +// memcpy(to, from, size); +// return to[0]; +// } // -// for (const auto& size_samples : nanobenchmark::RepeatedMeasureWithArguments( -// {3, 3, 4, 4, 7, 7, 8, 8}, [](const size_t size) { -// char from[8] = {static_cast<char>(size)}; -// char to[8]; -// memcpy(to, from, size); -// return to[0]; -// })) { -// nanobenchmark::PrintMedianAndVariability(size_samples); -// } +// PinThreadToRandomCPU(); +// +// static const size_t distribution[] = {3, 3, 4, 4, 7, 7, 8, 8}; +// DurationsForInputs input_map = MakeDurationsForInputs(distribution, 10); +// MeasureDurations(&RegionToMeasure, &input_map); +// for (size_t i = 0; i < input_map.num_items; ++i) { +// input_map.items[i].PrintMedianAndVariability(); +// } // // Output: -// 3: median= 20.8 cycles; median abs. deviation= 0.1 cycles -// 4: median= 8.8 cycles; median abs. deviation= 0.2 cycles -// 7: median= 8.8 cycles; median abs. deviation= 0.2 cycles -// 8: median= 27.5 cycles; median abs. deviation= 0.1 cycles +// 3: median= 25.2 cycles; median abs. deviation= 0.1 cycles +// 4: median= 13.5 cycles; median abs. deviation= 0.1 cycles +// 7: median= 13.5 cycles; median abs. deviation= 0.1 cycles +// 8: median= 27.5 cycles; median abs. deviation= 0.2 cycles // (7 is presumably faster because it can use two unaligned 32-bit load/stores.) // // Background: Microbenchmarks such as http://github.com/google/benchmark @@ -75,442 +69,88 @@ // central tendency of the measurement samples with the "half sample mode", // which is more robust to outliers and skewed data than the mean or median. -#include <algorithm> -#include <cmath> -#include <cstddef> -#include <cstdint> -#include <cstdio> -#include <map> -#include <random> -#include <type_traits> -#include <utility> -#include <vector> +// WARNING: compiled with different flags => must not define/instantiate any +// inline functions, nor include any headers that do - see instruction_sets.h. +#include <stddef.h> +#include <stdint.h> #include "highwayhash/arch_specific.h" #include "highwayhash/compiler_specific.h" -#include "highwayhash/os_specific.h" -#include "highwayhash/tsc_timer.h" -// Enables sanity checks that verify correct operation at the cost of -// longer benchmark runs. -#ifndef NANOBENCHMARK_ENABLE_CHECKS -#define NANOBENCHMARK_ENABLE_CHECKS 0 -#endif +namespace highwayhash { -#define NANOBENCHMARK_CHECK_ALWAYS(condition) \ - while (!(condition)) { \ - printf("Nanobenchmark check failed at line %d\n", __LINE__); \ - abort(); \ - } +// Argument to the function being measured (e.g. number of bytes to copy). +using FuncInput = size_t; -#if NANOBENCHMARK_ENABLE_CHECKS -#define NANOBENCHMARK_CHECK(condition) NANOBENCHMARK_CHECK_ALWAYS(condition) -#else -#define NANOBENCHMARK_CHECK(condition) -#endif +// "Proof of work" returned by the function to ensure it is not elided. +using FuncOutput = uint64_t; -namespace nanobenchmark { +// Function to measure (cannot use std::function in a restricted header). +using Func = FuncOutput (*)(FuncInput); -#if HH_MSC_VERSION - -// MSVC does not support inline assembly anymore (and never supported GCC's -// RTL constraints used below), so we instead pass the address to another -// translation unit and assume that link-time code generation is disabled. -void UseCharPointer(volatile const char*); - -template <class T> -inline void PreventElision(T&& output) { - UseCharPointer(reinterpret_cast<volatile const char*>(&output)); -} - -#else - -// Convenience function similar to std::enable_if_t (C++14). -// "Condition" provides a bool value, like std::integral_constant. -// Evaluates to a void return type if Condition is true, otherwise removes from -// consideration the function it annotates. -template <typename Condition> -using EnableIf = typename std::enable_if<Condition::value>::type; - -// Simplifies the predicates below; we only special-case floats on x86. -#if HH_ARCH_X64 -#define NANOBENCHMARK_IS_FLOAT(T) std::is_floating_point<T>::value -#else -#define NANOBENCHMARK_IS_FLOAT(T) false -#endif - -// True for T that can efficiently satisfy +r constraints. -template <typename T> -struct IsRegister { - // Exclude member pointers, which may be larger. On x86, also exclude - // floating-point numbers because they reside in separate registers. - static constexpr bool value = std::is_scalar<T>::value && - !NANOBENCHMARK_IS_FLOAT(T) && - !std::is_member_pointer<T>::value; -}; - -// True for all other T that do not need special handling. -template <typename T> -struct IsMemory { - static constexpr bool value = - !NANOBENCHMARK_IS_FLOAT(T) && !IsRegister<T>::value; -}; - -// Prevents the compiler from eliding the computations that led to "output". -// Works by indicating to the compiler that "output" is being read and modified. -// To avoid unnecessary writes to memory, this should use a +r constraint. That -// fails to compile with T = string/iterator etc, which we also need to protect -// from elision. Always using +m generates unnecessary stores to memory for -// integer/float arguments. +r,+m?? or even +m! should penalize m and only -// choose it if necessary, but that has the same effect as +m on clang. -// We therefore choose between functions specifying +r and +m based on T. -// SFINAE must be applied to the return type instead of the argument so that T -// can be deduced. -template <class T> -inline EnableIf<IsRegister<T>> PreventElision(T&& output) { - asm volatile("" : "+r"(output) : : "memory"); -} - -// x86: Avoids copying floating-point numbers to memory/eax. -#if defined(__x86_64__) || defined(_M_X64) -template <class T> -inline EnableIf<std::is_floating_point<T>> PreventElision(T&& output) { - // +x = SSE register (used on all x64 for float/double arithmetic). - asm volatile("" : "+x"(output) : : "memory"); -} -#endif - -template <class T> -inline EnableIf<IsMemory<T>> PreventElision(T&& output) { - // Clang generates redundant stores when using +X (anything) or +g - // (register, memory or immediate). - asm volatile("" : "+m"(output) : : "memory"); -} - -#endif - -// Input parameter for the function being measured. -using Input = size_t; - -// Cycles elapsed = difference between two cycle counts. Must be unsigned to -// ensure wraparound on overflow. -using Duration = uint32_t; - -// Returns cycles elapsed when passing each of "inputs" (after in-place -// shuffling) to "func", which must return something it has computed -// so the compiler does not optimize it away. -template <typename Func> -Duration CyclesElapsed(const Duration resolution, const Func& func, - std::vector<Input>* inputs) { - // This benchmark attempts to measure the performance of "func" when - // called with realistic inputs, which we assume are randomly drawn - // from the given "inputs" distribution, so we shuffle those values. - std::random_shuffle(inputs->begin(), inputs->end()); - - const Duration t0 = tsc_timer::Start<Duration>(); - for (const Input input : *inputs) { - PreventElision(func(input)); - } - const Duration t1 = tsc_timer::Stop<Duration>(); - const Duration elapsed = t1 - t0; - NANOBENCHMARK_CHECK(elapsed > resolution); - return elapsed - resolution; -} - -// Stores input values for a series of calls to the function to measure. -// We assume inputs are drawn from a known discrete probability distribution, -// modeled as a vector<Input> v. The probability of a value X in v is -// count(v.begin(), v.end(), X) / v.size(). -// -// Parameterizing the entire class on Func avoids std::function overhead or -// requiring users to call InitReplicas. Code size is not a major concern. -template <typename Func> -class Inputs { - Inputs(const Inputs&) = delete; - Inputs& operator=(const Inputs&) = delete; - +// Flat map of input -> durations[]. +class DurationsForInputs { public: - Inputs(const Duration resolution, const std::vector<Input>& distribution, - const Func& func) - : unique_(InitUnique(distribution)), - replicas_(InitReplicas(distribution, resolution, func)), - num_replicas_(replicas_.size() / distribution.size()) { - printf("NumReplicas %zu\n", num_replicas_); - } + struct Item { + void PrintMedianAndVariability(); - // Returns vector of the unique values from the input distribution. - const std::vector<Input>& Unique() const { return unique_; } + FuncInput input; // read-only (set by AddItem). + size_t num_durations; // written so far: [0, max_durations). + float* durations; // max_durations entries; points into all_durations. + }; - // Returns how many instances of "distribution" are in "replicas_", i.e. - // the number of occurrences of an input value that occurred only once - // in the distribution. This is the divisor for computing the duration - // of a single call. - size_t NumReplicas() const { return num_replicas_; } + // "inputs" is an array of "num_inputs" (not necessarily unique) arguments to + // "func". The values are chosen to maximize coverage of "func". The pointer + // must remain valid until after MeasureDurations. This represents a + // distribution, so a value's frequency should reflect its probability in the + // real application. Order does not matter; for example, a uniform + // distribution over [0, 4) could be represented as {3,0,2,1}. Repeating each + // value at least once ensures the leave-one-out distribution is closer to the + // original distribution, leading to more realistic results. + // + // "max_durations" is the number of duration samples to measure for each + // unique input value. Larger values decrease variability. + // + // Runtime is proportional to "num_inputs" * #unique * "max_durations". + DurationsForInputs(const FuncInput* inputs, const size_t num_inputs, + const size_t max_durations); + ~DurationsForInputs(); - // Returns the (replicated) input distribution. Modified by caller - // (shuffled in-place) => not thread-safe. - std::vector<Input>& Replicas() { return replicas_; } + // Adds an item with the given "input" and "sample". Must only be called once + // per unique "input" value. + void AddItem(const FuncInput input, const float sample); - // Returns a copy of Replicas() with NumReplicas() occurrences of "input" - // removed. Used for the leave-one-out measurement. - std::vector<Input> Without(const Input input_to_remove) const { - // "input_to_remove" should be in the original distribution. - NANOBENCHMARK_CHECK(std::find(unique_.begin(), unique_.end(), - input_to_remove) != unique_.end()); + // Adds "sample" to an already existing Item with the given "input". + void AddSample(const FuncInput input, const float sample); - std::vector<Input> copy = replicas_; - auto pos = std::partition(copy.begin(), copy.end(), - [input_to_remove](const Input input) { - return input_to_remove != input; - }); - // Must occur at least num_replicas_ times. - NANOBENCHMARK_CHECK(copy.end() - pos >= num_replicas_); - // (Avoids unused-variable warning.) - PreventElision(pos); - copy.resize(copy.size() - num_replicas_); - return copy; - } + // Allow direct inspection of items[0..num_items-1] because accessor or + // ForeachItem functions are unsafe in a restricted header. + Item* items; // owned by this class, do not allocate/free. + size_t num_items; // safe to reset to zero. private: - // Returns a copy with any duplicate values removed. Initializing unique_ - // through this function allows it to be const. - static std::vector<Input> InitUnique(const std::vector<Input>& distribution) { - std::vector<Input> unique = distribution; - std::sort(unique.begin(), unique.end()); - unique.erase(std::unique(unique.begin(), unique.end()), unique.end()); - // Our leave-one-out measurement technique only makes sense when - // there are multiple input values. - NANOBENCHMARK_CHECK(unique.size() >= 2); - return unique; - } + friend void MeasureDurations(Func, DurationsForInputs*); - // Returns how many replicas of "distribution" are required before - // CyclesElapsed is large enough compared to the timer resolution. - static std::vector<Input> InitReplicas(const std::vector<Input>& distribution, - const Duration resolution, - const Func& func) { - // We compute the difference in duration for inputs = Replicas() vs. - // Without(). Dividing this by num_replicas must yield a value where the - // quantization error (from the timer resolution) is sufficiently small. - const uint64_t min_elapsed = distribution.size() * resolution * 400; - - std::vector<Input> replicas; - for (;;) { - AppendReplica(distribution, &replicas); - -#if NANOBENCHMARK_ENABLE_CHECKS - const uint64_t t0 = tsc_timer::Start64(); -#endif - const Duration elapsed = CyclesElapsed(resolution, func, &replicas); -#if NANOBENCHMARK_ENABLE_CHECKS - const uint64_t t1 = tsc_timer::Stop64(); -#endif - // Ensure the 32-bit timer didn't and won't overflow. - NANOBENCHMARK_CHECK((t1 - t0) < (1ULL << 30)); - - if (elapsed >= min_elapsed) { - return replicas; - } - } - } - - // Appends all values in "distribution" to "replicas". - static void AppendReplica(const std::vector<Input>& distribution, - std::vector<Input>* replicas) { - replicas->reserve(replicas->size() + distribution.size()); - for (const Input input : distribution) { - replicas->push_back(input); - } - } - - const std::vector<Input> unique_; - - // Modified by caller (shuffled in-place) => non-const. - std::vector<Input> replicas_; - - // Initialized from replicas_. - const size_t num_replicas_; + const FuncInput* const inputs_; + const size_t num_inputs_; + const size_t max_durations_; + float* const all_durations_; }; -// Holds samples of measured durations, and (robustly) reduces them to a -// single result for each unique input value. -class DurationSamples { - public: - DurationSamples(const std::vector<Input>& unique_inputs, - const size_t num_samples) - : num_samples_(num_samples) { - // Preallocate storage. - for (const Input input : unique_inputs) { - samples_for_input_[input].reserve(num_samples); - } - } - - void Add(const Input input, const Duration sample) { - // "input" should be one of the values passed to the ctor. - NANOBENCHMARK_CHECK(samples_for_input_.find(input) != - samples_for_input_.end()); - - samples_for_input_[input].push_back(sample); - } - - // Invokes "lambda" for each (input, duration) pair. The per-call duration - // is the central tendency (the mode) of the samples. - template <class Lambda> - void Reduce(const Lambda& lambda) { - for (auto& input_and_samples : samples_for_input_) { - const Input input = input_and_samples.first; - std::vector<Duration>& samples = input_and_samples.second; - - NANOBENCHMARK_CHECK(samples.size() <= num_samples_); - std::sort(samples.begin(), samples.end()); - const Duration duration = tsc_timer::Mode(samples.data(), samples.size()); - lambda(input, duration); - } - } - - private: - const size_t num_samples_; - std::map<Input, std::vector<Duration>> samples_for_input_; -}; - -// Gathers "num_samples" durations via repeated leave-one-out measurements. -template <typename Func> -DurationSamples GatherDurationSamples(const Duration resolution, - Inputs<Func>& inputs, const Func& func, - const size_t num_samples) { - DurationSamples samples(inputs.Unique(), num_samples); - for (size_t i = 0; i < num_samples; ++i) { - // Total duration for all shuffled input values. This may change over time, - // so recompute it for each sample. - const Duration total = CyclesElapsed(resolution, func, &inputs.Replicas()); - - for (const Input input : inputs.Unique()) { - // To isolate the durations of the calls with this input value, - // we measure the duration without those values and subtract that - // from the total, and later divide by NumReplicas. - std::vector<Input> without = inputs.Without(input); - for (int rep = 0; rep < 3; ++rep) { - const Duration elapsed = CyclesElapsed(resolution, func, &without); - if (elapsed < total) { - samples.Add(input, total - elapsed); - break; - } - } - } - } - return samples; +// Helper function to detect num_inputs from arrays. +template <size_t N> +static HH_INLINE DurationsForInputs MakeDurationsForInputs( + const FuncInput (&inputs)[N], const size_t max_durations) { + return DurationsForInputs(&inputs[0], N, max_durations); } -// Public API follows: - -// Returns measurements of the cycles elapsed when calling "func" with each -// unique input value from the given "distribution", taking special care to -// maintain realistic branch prediction hit rates. +// Returns precise measurements of the cycles elapsed when calling "func" with +// each unique input value in "input_map", taking special care to maintain +// realistic branch prediction hit rates. // -// "distribution" should contain the input values required to trigger both -// sides of all conditional branches in "func". A value's probability of -// being used in the real application should be proportional to its frequency -// in the vector. Order does not matter; for example, a uniform distribution -// over [0, 4) could be represented as {3,0,2,1}. The benchmark duration is -// proportional to |distribution| * |unique values|. Repeating each value at -// least once ensures the leave-one-out distribution is closer to the original -// distribution, leading to more realistic results. -// -// "func" acts like std::function<T(Input)>, where T is a 'proof of work' -// return value used to ensure the computations are not elided. -template <typename Func> -std::map<Input, float> MeasureWithArguments( - const std::vector<Input>& distribution, const Func& func) { - const Duration resolution = tsc_timer::Resolution<Duration>(); +// "func" returns a 'proof of work' to ensure its computations are not elided. +void MeasureDurations(const Func func, DurationsForInputs* input_map); - // Adds enough 'replicas' of the distribution to measure "func" given - // the timer resolution. - Inputs<Func> inputs(resolution, distribution, func); - const double per_call = 1.0 / static_cast<int>(inputs.NumReplicas()); - - auto samples = GatherDurationSamples(resolution, inputs, func, 1024); - - // Return map of duration [cycles] for every unique input value. - std::map<Input, float> durations; - samples.Reduce( - [&durations, per_call](const Input input, const Duration duration) { - durations[input] = static_cast<float>(duration * per_call); - }); - NANOBENCHMARK_CHECK(durations.size() == inputs.Unique().size()); - return durations; -} - -// Optional functions for robust pooling of multiple measurements: - -// Returns vectors of duration samples for each input, for subsequent analysis -// by Median/MedianAbsoluteDeviation. The parameters are documented in -// MeasureWithArguments. -template <typename Func> -std::map<Input, std::vector<float>> RepeatedMeasureWithArguments( - const std::vector<Input>& distribution, const Func& func, - const int repetitions = 25) { - const Duration resolution = tsc_timer::Resolution<Duration>(); - - // Adds enough 'replicas' of the distribution to measure "func" given - // the timer resolution. - Inputs<Func> inputs(resolution, distribution, func); - const double per_call = 1.0 / static_cast<int>(inputs.NumReplicas()); - - // Preallocate sample storage. - std::map<Input, std::vector<float>> samples_for_input; - for (const Input input : distribution) { - samples_for_input[input].reserve(repetitions); - } - - for (int i = 0; i < repetitions; ++i) { - auto samples = GatherDurationSamples(resolution, inputs, func, 512); - // Scatter each input's duration into the sample arrays. - samples.Reduce([&samples_for_input, per_call](const Input input, - const Duration duration) { - const float sample = static_cast<float>(duration * per_call); - samples_for_input[input].push_back(sample); - }); - } - return samples_for_input; -} - -// Returns the median value. Side effect: sorts "samples". -template <typename T> -T Median(std::vector<T>* samples) { - NANOBENCHMARK_CHECK(!samples->empty()); - std::sort(samples->begin(), samples->end()); - const size_t half = samples->size() / 2; - // Odd count: return middle - if (samples->size() % 2) { - return (*samples)[half]; - } - // Even count: return average of middle two. - return ((*samples)[half] + (*samples)[half - 1]) / 2; -} - -// Returns a robust measure of variability. -template <typename T> -T MedianAbsoluteDeviation(const std::vector<T>& samples, const T median) { - NANOBENCHMARK_CHECK(!samples.empty()); - std::vector<T> abs_deviations; - abs_deviations.reserve(samples.size()); - for (const T sample : samples) { - abs_deviations.push_back(std::abs(sample - median)); - } - return Median(&abs_deviations); -} - -// Print median duration and variability for this size's samples. -inline void PrintMedianAndVariability( - const std::pair<Input, std::vector<float>>& input_samples) { - const Input input = input_samples.first; - auto samples = input_samples.second; // Copy (modified by Median) - const float median = Median(&samples); - const float variability = MedianAbsoluteDeviation(samples, median); - printf("%5zu: median=%5.1f cycles; median abs. deviation=%4.1f cycles\n", - input, median, variability); -} - -} // namespace nanobenchmark +} // namespace highwayhash #endif // HIGHWAYHASH_NANOBENCHMARK_H_
diff --git a/highwayhash/nanobenchmark_example.cc b/highwayhash/nanobenchmark_example.cc index 296fc1c..d95acf1 100644 --- a/highwayhash/nanobenchmark_example.cc +++ b/highwayhash/nanobenchmark_example.cc
@@ -19,27 +19,30 @@ #include "highwayhash/nanobenchmark.h" #include "highwayhash/os_specific.h" -namespace nanobenchmark { +namespace highwayhash { namespace { -void TestMemcpy() { - os_specific::PinThreadToRandomCPU(); +uint64_t RegionToMeasure(FuncInput size) { + char from[8] = {static_cast<char>(size)}; + char to[8]; + memcpy(to, from, size); + return to[0]; +} - for (const auto& size_samples : RepeatedMeasureWithArguments( - {3, 3, 4, 4, 7, 7, 8, 8}, [](const size_t size) { - char from[8] = {static_cast<char>(size)}; - char to[8]; - memcpy(to, from, size); - return to[0]; - })) { - PrintMedianAndVariability(size_samples); +void TestMemcpy() { + PinThreadToRandomCPU(); + static const size_t distribution[] = {3, 3, 4, 4, 7, 7, 8, 8}; + DurationsForInputs input_map = MakeDurationsForInputs(distribution, 10); + MeasureDurations(&RegionToMeasure, &input_map); + for (size_t i = 0; i < input_map.num_items; ++i) { + input_map.items[i].PrintMedianAndVariability(); } } } // namespace -} // namespace nanobenchmark +} // namespace highwayhash int main(int argc, char* argv[]) { - nanobenchmark::TestMemcpy(); + highwayhash::TestMemcpy(); return 0; }
diff --git a/highwayhash/os_specific.cc b/highwayhash/os_specific.cc index 7b11a5e..9364b32 100644 --- a/highwayhash/os_specific.cc +++ b/highwayhash/os_specific.cc
@@ -22,7 +22,7 @@ #include <ctime> #include <random> -#include "highwayhash/compiler_specific.h" +#include "highwayhash/arch_specific.h" #if defined(_WIN32) || defined(_WIN64) #define OS_WIN 1 @@ -34,7 +34,6 @@ #ifdef __linux__ #define OS_LINUX 1 -#include <cpuid.h> #include <sched.h> #include <sys/time.h> #else @@ -49,7 +48,7 @@ #define OS_MAC 0 #endif -namespace os_specific { +namespace highwayhash { #define CHECK(condition) \ while (!(condition)) { \ @@ -184,18 +183,6 @@ SetThreadAffinity(&affinity); } -uint32_t ApicId() { -#if HH_MSC_VERSION - int regs[4] = {0}; - __cpuid(regs, 1); - return uint32_t(regs[1]) >> 24; -#else - unsigned a, b, c, d; - __cpuid(1, a, b, c, d); - return b >> 24; -#endif -} - void PinThreadToRandomCPU() { std::vector<int> cpus = AvailableCPUs(); @@ -211,8 +198,12 @@ PinThreadToCPU(cpu); +#if HH_ARCH_X64 // After setting affinity, we should be running on the desired CPU. printf("Running on CPU #%d, APIC ID %02x\n", cpu, ApicId()); +#else + printf("Running on CPU #%d\n", cpu); +#endif } -} // namespace os_specific +} // namespace highwayhash
diff --git a/highwayhash/os_specific.h b/highwayhash/os_specific.h index 50b8ffd..46f3c3e 100644 --- a/highwayhash/os_specific.h +++ b/highwayhash/os_specific.h
@@ -17,7 +17,7 @@ #include <vector> -namespace os_specific { +namespace highwayhash { // Returns current wall-clock time [seconds]. double Now(); @@ -49,6 +49,6 @@ // Uses SetThreadAffinity. void PinThreadToRandomCPU(); -} // namespace os_specific +} // namespace highwayhash #endif // HIGHWAYHASH_OS_SPECIFIC_H_
diff --git a/highwayhash/profiler.h b/highwayhash/profiler.h index e1bd4df..e22d972 100644 --- a/highwayhash/profiler.h +++ b/highwayhash/profiler.h
@@ -42,7 +42,6 @@ #if PROFILER_ENABLED -#include <emmintrin.h> #include <algorithm> // min/max #include <atomic> #include <cassert> @@ -53,6 +52,7 @@ #include <cstring> // memcpy #include <new> +#include "highwayhash/arch_specific.h" #include "highwayhash/compiler_specific.h" // Non-portable aspects: @@ -60,12 +60,16 @@ // - RDTSCP timestamps (serializing, high-resolution) // - assumes string literals are stored within an 8 MiB range // - compiler-specific annotations (restrict, alignment, fences) +#if HH_ARCH_X64 +#include <emmintrin.h> #if HH_MSC_VERSION #include <intrin.h> #else #include <x86intrin.h> #endif +#endif +#include "highwayhash/robust_statistics.h" #include "highwayhash/tsc_timer.h" #define PROFILER_CHECK(condition) \ @@ -74,7 +78,7 @@ abort(); \ } -namespace profiler { +namespace highwayhash { // Upper bounds for various fixed-size data structures (guarded via assert): @@ -125,36 +129,27 @@ free(allocated); } +#if HH_ARCH_X64 // Overwrites "to" without loading it into the cache (read-for-ownership). template <typename T> - static void StreamCacheLine(const T* from, T* to) { - static_assert(sizeof(__m128i) % sizeof(T) == 0, "Cannot divide"); - const size_t kLanes = sizeof(__m128i) / sizeof(T); + static void StreamCacheLine(const T* from_items, T* to_items) { + const __m128i* const from = reinterpret_cast<const __m128i*>(from_items); + __m128i* const to = reinterpret_cast<__m128i*>(to_items); HH_COMPILER_FENCE; - const __m128i v0 = LoadVector(from + 0 * kLanes); - const __m128i v1 = LoadVector(from + 1 * kLanes); - const __m128i v2 = LoadVector(from + 2 * kLanes); - const __m128i v3 = LoadVector(from + 3 * kLanes); + const __m128i v0 = _mm_load_si128(from + 0); + const __m128i v1 = _mm_load_si128(from + 1); + const __m128i v2 = _mm_load_si128(from + 2); + const __m128i v3 = _mm_load_si128(from + 3); // Fences prevent the compiler from reordering loads/stores, which may // interfere with write-combining. HH_COMPILER_FENCE; - StreamVector(v0, to + 0 * kLanes); - StreamVector(v1, to + 1 * kLanes); - StreamVector(v2, to + 2 * kLanes); - StreamVector(v3, to + 3 * kLanes); + _mm_stream_si128(to + 0, v0); + _mm_stream_si128(to + 1, v1); + _mm_stream_si128(to + 2, v2); + _mm_stream_si128(to + 3, v3); HH_COMPILER_FENCE; } - - private: - // Loads 128-bit vector from memory. - static __m128i LoadVector(const void* from) { - return _mm_load_si128(reinterpret_cast<const __m128i*>(from)); - } - - // Adds a 128-bit vector to the CPU's write-combine buffer. - static void StreamVector(const __m128i& v, void* to) { - _mm_stream_si128(reinterpret_cast<__m128i*>(to), v); - } +#endif }; // Represents zone entry/exit events. Stores a full-resolution timestamp plus @@ -218,7 +213,9 @@ uint64_t num_calls = 0; // upper bits = biased_offset. uint64_t total_duration = 0; }; +#if HH_ARCH_X64 static_assert(sizeof(Accumulator) == sizeof(__m128i), "Wrong Accumulator size"); +#endif template <typename T> static inline T ClampedSubtract(const T minuend, const T subtrahend) { @@ -261,8 +258,7 @@ // Draw all required information from the packets, which can be discarded // afterwards. Called whenever this thread's storage is full. void AnalyzePackets(const Packet* packets, const size_t num_packets) { - const uint64_t t0 = tsc_timer::Start<uint64_t>(); - const __m128i one_64 = _mm_set1_epi64x(1); + const uint64_t t0 = Start<uint64_t>(); for (size_t i = 0; i < num_packets; ++i) { const Packet p = packets[i]; @@ -283,7 +279,7 @@ const uint64_t self_duration = ClampedSubtract( duration, self_overhead_ + child_overhead_ + node.child_total); - UpdateOrAdd(node.packet.BiasedOffset(), self_duration, one_64); + UpdateOrAdd(node.packet.BiasedOffset(), self_duration); --depth_; // Deduct this nested node's time from its parent's self_duration. @@ -291,29 +287,29 @@ nodes_[depth_ - 1].child_total += duration + child_overhead_; } } - const uint64_t t1 = tsc_timer::Stop<uint64_t>(); + + const uint64_t t1 = Stop<uint64_t>(); analyze_elapsed_ += t1 - t0; } // Incorporates results from another thread. Call after all threads have // exited any zones. void Assimilate(const Results& other) { - const uint64_t t0 = tsc_timer::Start<uint64_t>(); + const uint64_t t0 = Start<uint64_t>(); assert(depth_ == 0); assert(other.depth_ == 0); - const __m128i one_64 = _mm_set1_epi64x(1); for (size_t i = 0; i < other.num_zones_; ++i) { const Accumulator& zone = other.zones_[i]; - UpdateOrAdd(zone.BiasedOffset(), zone.total_duration, one_64); + UpdateOrAdd(zone.BiasedOffset(), zone.total_duration); } - const uint64_t t1 = tsc_timer::Stop<uint64_t>(); + const uint64_t t1 = Stop<uint64_t>(); analyze_elapsed_ += t1 - t0 + other.analyze_elapsed_; } // Single-threaded. void Print() { - const uint64_t t0 = tsc_timer::Start<uint64_t>(); + const uint64_t t0 = Start<uint64_t>(); MergeDuplicates(); // Sort by decreasing total (self) cost. @@ -330,26 +326,29 @@ num_calls, r.total_duration / num_calls, r.total_duration); } - const uint64_t t1 = tsc_timer::Stop<uint64_t>(); + const uint64_t t1 = Stop<uint64_t>(); analyze_elapsed_ += t1 - t0; printf("Total clocks during analysis: %zu\n", analyze_elapsed_); } private: +#if HH_ARCH_X64 static bool SameOffset(const __m128i& zone, const size_t biased_offset) { const uint64_t num_calls = _mm_cvtsi128_si64(zone); return (num_calls >> Accumulator::kNumCallBits) == biased_offset; } +#endif // Updates an existing Accumulator (uniquely identified by biased_offset) or // adds one if this is the first time this thread analyzed that zone. // Uses a self-organizing list data structure, which avoids dynamic memory // allocations and is far faster than unordered_map. Loads, updates and // stores the entire Accumulator with vector instructions. - void UpdateOrAdd(const size_t biased_offset, const uint64_t duration, - const __m128i& one_64) { + void UpdateOrAdd(const size_t biased_offset, const uint64_t duration) { assert(biased_offset < (1ULL << Packet::kOffsetBits)); +#if HH_ARCH_X64 + const __m128i one_64 = _mm_set1_epi64x(1); const __m128i duration_64 = _mm_cvtsi64_si128(duration); const __m128i add_duration_call = _mm_unpacklo_epi64(one_64, duration_64); @@ -388,6 +387,38 @@ assert(num_zones_ < kMaxZones); _mm_store_si128(zones + num_zones_, zone); ++num_zones_; +#else + // Special case for first zone: (maybe) update, without swapping. + if (zones_[0].BiasedOffset() == biased_offset) { + zones_[0].total_duration += duration; + zones_[0].num_calls += 1; + assert(zones_[0].BiasedOffset() == biased_offset); + return; + } + + // Look for a zone with the same offset. + for (size_t i = 1; i < num_zones_; ++i) { + if (zones_[i].BiasedOffset() == biased_offset) { + zones_[i].total_duration += duration; + zones_[i].num_calls += 1; + assert(zones_[i].BiasedOffset() == biased_offset); + // Swap with predecessor (more conservative than move to front, + // but at least as successful). + const Accumulator prev = zones_[i - 1]; + zones_[i - 1] = zones_[i]; + zones_[i] = prev; + return; + } + } + + // Not found; create a new Accumulator. + assert(num_zones_ < kMaxZones); + Accumulator* HH_RESTRICT zone = zones_ + num_zones_; + zone->num_calls = (biased_offset << Accumulator::kNumCallBits) + 1; + zone->total_duration = duration; + assert(zone->BiasedOffset() == biased_offset); + ++num_zones_; +#endif } // Each instantiation of a function template seems to get its own copy of @@ -440,8 +471,7 @@ public: // "name" is used to sanity-check offsets fit in kOffsetBits. explicit ThreadSpecific(const char* name) - : buffer_size_(0), - packets_(static_cast<Packet*>( + : packets_(static_cast<Packet*>( CacheAligned::Allocate(PROFILER_THREAD_STORAGE << 20))), num_packets_(0), max_packets_(PROFILER_THREAD_STORAGE << 17), @@ -471,6 +501,7 @@ } void AnalyzeRemainingPackets() { +#if HH_ARCH_X64 // Ensures prior weakly-ordered streaming stores are globally visible. _mm_sfence(); @@ -481,6 +512,8 @@ } memcpy(packets_ + num_packets_, buffer_, buffer_size_ * sizeof(Packet)); num_packets_ += buffer_size_; +#endif + results_.AnalyzePackets(packets_, num_packets_); num_packets_ = 0; } @@ -490,6 +523,7 @@ private: // Write packet to buffer/storage, emptying them as needed. void Write(const Packet packet) { +#if HH_ARCH_X64 // Buffer full => copy to storage. if (buffer_size_ == kBufferCapacity) { // Storage full => empty it. @@ -505,12 +539,23 @@ } buffer_[buffer_size_] = packet; ++buffer_size_; +#else + // Write directly to storage. + if (num_packets_ >= max_packets_) { + results_.AnalyzePackets(packets_, num_packets_); + num_packets_ = 0; + } + packets_[num_packets_] = packet; + ++num_packets_; +#endif } // Write-combining buffer to avoid cache pollution. Must be the first // non-static member to ensure cache-line alignment. +#if HH_ARCH_X64 Packet buffer_[kBufferCapacity]; - size_t buffer_size_; + size_t buffer_size_ = 0; +#endif // Contiguous storage for zone enter/exit packets. Packet* const HH_RESTRICT packets_; @@ -572,13 +617,13 @@ // (Capture timestamp ASAP, not inside WriteEntry.) HH_COMPILER_FENCE; - const uint64_t timestamp = tsc_timer::Start<uint64_t>(); + const uint64_t timestamp = Start<uint64_t>(); thread_specific->WriteEntry(name, timestamp); } HH_NOINLINE ~Zone() { HH_COMPILER_FENCE; - const uint64_t timestamp = tsc_timer::Stop<uint64_t>(); + const uint64_t timestamp = Stop<uint64_t>(); StaticThreadSpecific()->WriteExit(timestamp); HH_COMPILER_FENCE; } @@ -606,17 +651,17 @@ // "name" must be a string literal, which is ensured by merging with "". #define PROFILER_ZONE(name) \ HH_COMPILER_FENCE; \ - const profiler::Zone zone("" name); \ + const Zone zone("" name); \ HH_COMPILER_FENCE // Creates a zone for an entire function (when placed at its beginning). // Shorter/more convenient than ZONE. #define PROFILER_FUNC \ HH_COMPILER_FENCE; \ - const profiler::Zone zone(__func__); \ + const Zone zone(__func__); \ HH_COMPILER_FENCE -#define PROFILER_PRINT_RESULTS profiler::Zone::PrintResults +#define PROFILER_PRINT_RESULTS Zone::PrintResults inline void ThreadSpecific::ComputeOverhead() { // Delay after capturing timestamps before/after the actual zone runs. Even @@ -633,16 +678,21 @@ for (size_t idx_duration = 0; idx_duration < kNumDurations; ++idx_duration) { { PROFILER_ZONE("Dummy Zone (never shown)"); } - durations[idx_duration] = - static_cast<uint32_t>(results_.ZoneDuration(buffer_)); +#if HH_ARCH_X64 + const uint64_t duration = results_.ZoneDuration(buffer_); buffer_size_ = 0; +#else + const uint64_t duration = results_.ZoneDuration(packets_); + num_packets_ = 0; +#endif + durations[idx_duration] = static_cast<uint32_t>(duration); PROFILER_CHECK(num_packets_ == 0); } - tsc_timer::CountingSort(durations, durations + kNumDurations); - samples[idx_sample] = tsc_timer::Mode(durations, kNumDurations); + CountingSort(durations, durations + kNumDurations); + samples[idx_sample] = Mode(durations, kNumDurations); } // Median. - tsc_timer::CountingSort(samples, samples + kNumSamples); + CountingSort(samples, samples + kNumSamples); self_overhead = samples[kNumSamples / 2]; printf("Overhead: %zu\n", self_overhead); results_.SetSelfOverhead(self_overhead); @@ -659,30 +709,38 @@ const size_t kReps = 10000; // Analysis time should not be included => must fit within buffer. PROFILER_CHECK(kReps * 2 < max_packets_); +#if HH_ARCH_X64 _mm_mfence(); - const uint64_t t0 = tsc_timer::Start<uint64_t>(); +#endif + const uint64_t t0 = Start<uint64_t>(); for (size_t i = 0; i < kReps; ++i) { PROFILER_ZONE("Dummy"); } +#if HH_ARCH_X64 _mm_sfence(); - const uint64_t t1 = tsc_timer::Stop<uint64_t>(); +#endif + const uint64_t t1 = Stop<uint64_t>(); +#if HH_ARCH_X64 PROFILER_CHECK(num_packets_ + buffer_size_ == kReps * 2); - num_packets_ = 0; buffer_size_ = 0; +#else + PROFILER_CHECK(num_packets_ == kReps * 2); +#endif + num_packets_ = 0; const uint64_t avg_duration = (t1 - t0 + kReps / 2) / kReps; durations[idx_duration] = static_cast<uint32_t>(ClampedSubtract(avg_duration, self_overhead)); } - tsc_timer::CountingSort(durations, durations + kNumDurations); - samples[idx_sample] = tsc_timer::Mode(durations, kNumDurations); + CountingSort(durations, durations + kNumDurations); + samples[idx_sample] = Mode(durations, kNumDurations); } - tsc_timer::CountingSort(samples, samples + kNumSamples); + CountingSort(samples, samples + kNumSamples); const uint64_t child_overhead = samples[9 * kNumSamples / 10]; printf("Child overhead: %zu\n", child_overhead); results_.SetChildOverhead(child_overhead); } -} // namespace profiler +} // namespace highwayhash #else // !PROFILER_ENABLED #define PROFILER_ZONE(name)
diff --git a/highwayhash/profiler_example.cc b/highwayhash/profiler_example.cc index 01c2f9e..999cc45 100644 --- a/highwayhash/profiler_example.cc +++ b/highwayhash/profiler_example.cc
@@ -19,12 +19,13 @@ #include "highwayhash/os_specific.h" #include "highwayhash/profiler.h" +namespace highwayhash { namespace { void Spin(const double min_time) { - const double t0 = os_specific::Now(); + const double t0 = Now(); for (;;) { - const double elapsed = os_specific::Now() - t0; + const double elapsed = Now() - t0; if (elapsed > min_time) { break; } @@ -75,10 +76,8 @@ Level2(); } -} // namespace - -int main(int argc, char* argv[]) { - os_specific::PinThreadToRandomCPU(); +void ProfilerExample() { + PinThreadToRandomCPU(); { PROFILER_FUNC; Spin10(); @@ -87,5 +86,12 @@ Level1(); } PROFILER_PRINT_RESULTS(); +} + +} // namespace +} // namespace highwayhash + +int main(int argc, char* argv[]) { + highwayhash::ProfilerExample(); return 0; }
diff --git a/highwayhash/robust_statistics.h b/highwayhash/robust_statistics.h new file mode 100644 index 0000000..bbcbbfa --- /dev/null +++ b/highwayhash/robust_statistics.h
@@ -0,0 +1,134 @@ +// Copyright 2017 Google Inc. All Rights Reserved. +// +// 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. + +#ifndef HIGHWAYHASH_ROBUST_STATISTICS_H_ +#define HIGHWAYHASH_ROBUST_STATISTICS_H_ + +// Robust statistics: Mode, Median, MedianAbsoluteDeviation. + +#include <stddef.h> +#include <algorithm> +#include <cassert> +#include <limits> +#include <vector> + +#include "highwayhash/arch_specific.h" +#include "highwayhash/compiler_specific.h" + +namespace highwayhash { + +// @return i in [idx_begin, idx_begin + half_count) that minimizes +// sorted[i + half_count] - sorted[i]. +template <typename T> +size_t MinRange(const T* const HH_RESTRICT sorted, const size_t idx_begin, + const size_t half_count) { + T min_range = std::numeric_limits<T>::max(); + size_t min_idx = 0; + + for (size_t idx = idx_begin; idx < idx_begin + half_count; ++idx) { + assert(sorted[idx] <= sorted[idx + half_count]); + const T range = sorted[idx + half_count] - sorted[idx]; + if (range < min_range) { + min_range = range; + min_idx = idx; + } + } + + return min_idx; +} + +// Returns an estimate of the mode by calling MinRange on successively +// halved intervals. "sorted" must be in ascending order. This is the +// Half Sample Mode estimator proposed by Bickel in "On a fast, robust +// estimator of the mode", with complexity O(N log N). The mode is less +// affected by outliers in highly-skewed distributions than the median. +// The averaging operation below assumes "T" is an unsigned integer type. +template <typename T> +T Mode(const T* const HH_RESTRICT sorted, const size_t num_values) { + size_t idx_begin = 0; + size_t half_count = num_values / 2; + while (half_count > 1) { + idx_begin = MinRange(sorted, idx_begin, half_count); + half_count >>= 1; + } + + const T x = sorted[idx_begin + 0]; + if (half_count == 0) { + return x; + } + assert(half_count == 1); + const T average = (x + sorted[idx_begin + 1] + 1) / 2; + return average; +} + +// Sorts integral values in ascending order. About 3x faster than std::sort for +// input distributions with very few unique values. +template <class T> +void CountingSort(T* begin, T* end) { + // Unique values and their frequency (similar to flat_map). + using Unique = std::pair<T, int>; + std::vector<Unique> unique; + for (const T* p = begin; p != end; ++p) { + const T value = *p; + const auto pos = + std::find_if(unique.begin(), unique.end(), + [value](const Unique& u) { return u.first == value; }); + if (pos == unique.end()) { + unique.push_back(std::make_pair(*p, 1)); + } else { + ++pos->second; + } + } + + // Sort in ascending order of value (pair.first). + std::sort(unique.begin(), unique.end()); + + // Write that many copies of each unique value to the array. + T* HH_RESTRICT p = begin; + for (const auto& value_count : unique) { + std::fill(p, p + value_count.second, value_count.first); + p += value_count.second; + } + assert(p == end); +} + +// Returns the median value. Side effect: sorts "samples". +template <typename T> +T Median(std::vector<T>* samples) { + assert(!samples->empty()); + std::sort(samples->begin(), samples->end()); + const size_t half = samples->size() / 2; + // Odd count: return middle + if (samples->size() % 2) { + return (*samples)[half]; + } + // Even count: return average of middle two. + return ((*samples)[half] + (*samples)[half - 1]) / 2; +} + +// Returns a robust measure of variability. +template <typename T> +T MedianAbsoluteDeviation(const std::vector<T>& samples, const T median) { + assert(!samples.empty()); + std::vector<T> abs_deviations; + abs_deviations.reserve(samples.size()); + for (const T sample : samples) { + abs_deviations.push_back(std::abs(sample - median)); + } + return Median(&abs_deviations); +} + +} // namespace highwayhash + +#endif // HIGHWAYHASH_ROBUST_STATISTICS_H_
diff --git a/highwayhash/scalar.h b/highwayhash/scalar.h index 320ad0a..05705eb 100644 --- a/highwayhash/scalar.h +++ b/highwayhash/scalar.h
@@ -18,15 +18,25 @@ #include <stddef.h> // size_t #include <stdint.h> +#include "highwayhash/arch_specific.h" #include "highwayhash/compiler_specific.h" namespace highwayhash { +// To prevent ODR violations when including this from multiple translation +// units (TU) that are compiled with different flags, the contents must reside +// in a namespace whose name is unique to the TU. NOTE: this behavior is +// incompatible with precompiled modules and requires textual inclusion instead. +namespace HH_TARGET_NAME { // Single-lane "vector" type with the same interface as V128/Scalar. Allows the // same client template to generate both SIMD and portable code. template <typename Type> class Scalar { public: + struct Intrinsic { + Type t; + }; + using T = Type; static constexpr size_t N = 1; @@ -42,19 +52,27 @@ return *this; } + // Convert from/to intrinsics. + HH_INLINE Scalar(const Intrinsic& v) : v_(v.t) {} + HH_INLINE Scalar& operator=(const Intrinsic& v) { + v_ = v.t; + return *this; + } + HH_INLINE operator Intrinsic() const { return {v_}; } + HH_INLINE Scalar operator==(const Scalar& other) const { Scalar eq; - memset(&eq.v_, v_ == other.v_ ? 0xFF : 0x00, sizeof(v_)); + eq.FillWithByte(v_ == other.v_ ? 0xFF : 0x00); return eq; } HH_INLINE Scalar operator<(const Scalar& other) const { Scalar lt; - memset(<.v_, v_ < other.v_ ? 0xFF : 0x00, sizeof(v_)); + lt.FillWithByte(v_ < other.v_ ? 0xFF : 0x00); return lt; } HH_INLINE Scalar operator>(const Scalar& other) const { Scalar gt; - memset(>.v_, v_ > other.v_ ? 0xFF : 0x00, sizeof(v_)); + gt.FillWithByte(v_ > other.v_ ? 0xFF : 0x00); return gt; } @@ -89,15 +107,42 @@ } HH_INLINE Scalar& operator<<=(const int count) { - v_ <<= count; + // In C, int64_t << 64 is undefined, but we want to match the sensible + // behavior of SSE2 (zeroing). + if (count >= sizeof(T) * 8) { + v_ = 0; + } else { + v_ <<= count; + } return *this; } HH_INLINE Scalar& operator>>=(const int count) { - v_ >>= count; + if (count >= sizeof(T) * 8) { + v_ = 0; + } else { + v_ >>= count; + } return *this; } + // For internal use only. We need to avoid memcpy/memset because this is a + // restricted header. + void FillWithByte(const unsigned char value) { + unsigned char* bytes = reinterpret_cast<unsigned char*>(&v_); + for (size_t i = 0; i < sizeof(T); ++i) { + bytes[i] = value; + } + } + + void CopyTo(unsigned char* HH_RESTRICT to_bytes) const { + const unsigned char* from_bytes = + reinterpret_cast<const unsigned char*>(&v_); + for (size_t i = 0; i < sizeof(T); ++i) { + to_bytes[i] = from_bytes[i]; + } + } + private: T v_; }; @@ -171,19 +216,12 @@ // We differentiate between targets' vector types via template specialization. // Calling Load<V>(floats) is more natural than Load(V8x32F(), floats) and may -// generate better code in unoptimized builds. The primary template can only -// be defined once, even if multiple vector headers are included. -#ifndef HH_DEFINED_PRIMARY_TEMPLATE_FOR_LOAD -#define HH_DEFINED_PRIMARY_TEMPLATE_FOR_LOAD +// generate better code in unoptimized builds. Only declare the primary +// templates to avoid needing mutual exclusion with vector128/256. template <class V> -HH_INLINE V Load(const typename V::T* const HH_RESTRICT from) { - return V(); // must specialize for each type. -} +HH_INLINE V Load(const typename V::T* const HH_RESTRICT from); template <class V> -HH_INLINE V LoadUnaligned(const typename V::T* const HH_RESTRICT from) { - return V(); // must specialize for each type. -} -#endif +HH_INLINE V LoadUnaligned(const typename V::T* const HH_RESTRICT from); template <> HH_INLINE V1x8U Load<V1x8U>(const V1x8U::T* const HH_RESTRICT from) { @@ -260,17 +298,17 @@ template <typename T> HH_INLINE void Store(const Scalar<T>& v, T* const HH_RESTRICT to) { - memcpy(to, &v, sizeof(v)); + v.CopyTo(reinterpret_cast<unsigned char*>(to)); } template <typename T> HH_INLINE void StoreUnaligned(const Scalar<T>& v, T* const HH_RESTRICT to) { - memcpy(to, &v, sizeof(v)); + v.CopyTo(reinterpret_cast<unsigned char*>(to)); } template <typename T> HH_INLINE void Stream(const Scalar<T>& v, T* const HH_RESTRICT to) { - memcpy(to, &v, sizeof(v)); + v.CopyTo(reinterpret_cast<unsigned char*>(to)); } // Miscellaneous functions. @@ -289,9 +327,8 @@ template <typename T> HH_INLINE Scalar<T> Select(const Scalar<T>& a, const Scalar<T>& b, const Scalar<T>& mask) { - uint8_t bytes[sizeof(T)]; - memcpy(bytes, &mask, sizeof(T)); - return (bytes[sizeof(T) - 1] & 0x80) ? b : a; + const char* mask_bytes = reinterpret_cast<const char*>(&mask); + return (mask_bytes[sizeof(T) - 1] & 0x80) ? b : a; } template <typename T> @@ -304,6 +341,7 @@ return (v0 < v1) ? v1 : v0; } +} // namespace HH_TARGET_NAME } // namespace highwayhash #endif // HIGHWAYHASH_SCALAR_H_
diff --git a/highwayhash/scalar_sip_tree_hash.h b/highwayhash/scalar_sip_tree_hash.h index 031ebbd..2f79f3a 100644 --- a/highwayhash/scalar_sip_tree_hash.h +++ b/highwayhash/scalar_sip_tree_hash.h
@@ -34,4 +34,4 @@ } // namespace highwayhash #endif -#endif // #ifndef HIGHWAYHASH_SCALAR_SIP_TREE_HASH_H_ +#endif // HIGHWAYHASH_SCALAR_SIP_TREE_HASH_H_
diff --git a/highwayhash/sip_hash.h b/highwayhash/sip_hash.h index 0ffcb64..eebe3dc 100644 --- a/highwayhash/sip_hash.h +++ b/highwayhash/sip_hash.h
@@ -22,6 +22,7 @@ #include "highwayhash/arch_specific.h" #include "highwayhash/compiler_specific.h" +#include "highwayhash/endianess.h" #include "highwayhash/state_helpers.h" namespace highwayhash { @@ -43,9 +44,7 @@ HH_INLINE void Update(const char* bytes) { HH_U64 packet; memcpy(&packet, bytes, sizeof(packet)); -#if HH_BIG_ENDIAN - packet = HH_BSWAP64(packet); -#endif + packet = host_from_le64(packet); v3 ^= packet; @@ -169,4 +168,4 @@ } // namespace highwayhash -#endif // #ifndef HIGHWAYHASH_SIP_HASH_H_ +#endif // HIGHWAYHASH_SIP_HASH_H_
diff --git a/highwayhash/sip_hash_test.cc b/highwayhash/sip_hash_test.cc index b3b5c45..a77239e 100644 --- a/highwayhash/sip_hash_test.cc +++ b/highwayhash/sip_hash_test.cc
@@ -128,7 +128,7 @@ DEFINE_HASHER(ScalarSipTreeHash, 4); BENCHMARK(BM<ScalarSipTreeHasher>)->Apply(Args); -#if HH_ENABLE_AVX2 +#ifdef __AVX2__ DEFINE_HASHER(SipTreeHash, 4); BENCHMARK(BM<SipTreeHasher>)->Apply(Args); #endif
diff --git a/highwayhash/sip_tree_hash.cc b/highwayhash/sip_tree_hash.cc index dc7ad95..59568f1 100644 --- a/highwayhash/sip_tree_hash.cc +++ b/highwayhash/sip_tree_hash.cc
@@ -16,12 +16,14 @@ #include <cstring> // memcpy +#include "highwayhash/arch_specific.h" #include "highwayhash/compiler_specific.h" #include "highwayhash/sip_hash.h" -#include "highwayhash/vector256.h" -#if HH_ENABLE_AVX2 +#if HH_TARGET == HH_TARGET_AVX2 +#include "highwayhash/vector256.h" namespace highwayhash { +namespace HH_TARGET_NAME { namespace { // Paper: https://www.131002.net/siphash/siphash.pdf @@ -161,10 +163,12 @@ } } // namespace +} // namespace HH_TARGET_NAME template <size_t kUpdateRounds, size_t kFinalizeRounds> -HH_U64 SipTreeHashT(const HH_U64 (&key)[kNumLanes], const char* bytes, +HH_U64 SipTreeHashT(const HH_U64 (&key)[4], const char* bytes, const HH_U64 size) { + using namespace HH_TARGET_NAME; SipTreeHashStateT<kUpdateRounds, kFinalizeRounds> state(key); const size_t remainder = size & (kPacketSize - 1); @@ -191,15 +195,16 @@ reduce_key, hashes); } -HH_U64 SipTreeHash(const HH_U64 (&key)[kNumLanes], const char* bytes, +HH_U64 SipTreeHash(const HH_U64 (&key)[4], const char* bytes, const HH_U64 size) { return SipTreeHashT<2, 4>(key, bytes, size); } -HH_U64 SipTreeHash13(const HH_U64 (&key)[kNumLanes], const char* bytes, +HH_U64 SipTreeHash13(const HH_U64 (&key)[4], const char* bytes, const HH_U64 size) { return SipTreeHashT<1, 3>(key, bytes, size); } + } // namespace highwayhash using highwayhash::HH_U64; @@ -219,4 +224,4 @@ } // extern "C" -#endif // #if HH_ENABLE_AVX2 +#endif // HH_TARGET == HH_TARGET_AVX2
diff --git a/highwayhash/sip_tree_hash.h b/highwayhash/sip_tree_hash.h index 38cae7e..ee5a423 100644 --- a/highwayhash/sip_tree_hash.h +++ b/highwayhash/sip_tree_hash.h
@@ -49,4 +49,4 @@ } // namespace highwayhash #endif -#endif // #ifndef HIGHWAYHASH_SIP_TREE_HASH_H_ +#endif // HIGHWAYHASH_SIP_TREE_HASH_H_
diff --git a/highwayhash/targets.h b/highwayhash/targets.h deleted file mode 100644 index 5cd7164..0000000 --- a/highwayhash/targets.h +++ /dev/null
@@ -1,83 +0,0 @@ -// Copyright 2017 Google Inc. All Rights Reserved. -// -// 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. - -#ifndef HIGHWAYHASH_TARGETS_H_ -#define HIGHWAYHASH_TARGETS_H_ - -// WARNING: compiled with different flags => must not define/instantiate any -// inline functions, nor include any headers that do - see instruction_sets.h. - -// Defines 'traits' for the current target (mainly its vector type). The -// HH_TARGET BUILD macro expands to one of the Target* structs defined here. -// -// This header must only be included from target-specific source files. Example: -// #include "highwayhash/targets.h" -// template <class Target> void Functor<Target>::operator()(/*args*/) const {} -// template class Functor<HH_TARGET>; // instantiate -// -// The corresponding header need only contain: -// template <class Target> struct Functor { void operator()(/*args*/) const; }; - -// To avoid inadvertent usage of other targets' functionality, we only provide -// Target* if the corresponding HH_TARGET_* macro is defined. This is necessary -// because the preprocessor can't test whether #HH_TARGET == "TargetAVX2". -#ifdef HH_TARGET_AVX2 -#include "highwayhash/vector256.h" -#endif -#ifdef HH_TARGET_SSE41 -#include "highwayhash/vector128.h" -#endif -#ifdef HH_TARGET_PORTABLE -#include "highwayhash/scalar.h" -#endif - -namespace highwayhash { - -// Target traits: each defines a "vector" type plus some static member -// functions not provided by the vector class. The Target* type can also be -// used as a tag for function overloading or template specialization. - -#ifdef HH_TARGET_AVX2 -// Intel Haswell and AMD Zen CPUs also support FMA/BMI2/AVX2 -// [https://sourceware.org/ml/binutils/2015-03/msg00078.html] -struct TargetAVX2 { - template <typename T> - using V = V256<T>; - - static const char* Name() { return "AVX2"; } -}; -#endif - -#ifdef HH_TARGET_SSE41 -// SSE4.1 is available since 2008 (Intel) and 2011 (AMD). -struct TargetSSE41 { - template <typename T> - using V = V128<T>; - - static const char* Name() { return "SSE41"; } -}; -#endif - -#ifdef HH_TARGET_PORTABLE -struct TargetPortable { - template <typename T> - using V = Scalar<T>; - - static const char* Name() { return "Portable"; } -}; -#endif - -} // namespace highwayhash - -#endif // HIGHWAYHASH_TARGETS_H_
diff --git a/highwayhash/tsc_timer.h b/highwayhash/tsc_timer.h index e2b795e..4a88c0f 100644 --- a/highwayhash/tsc_timer.h +++ b/highwayhash/tsc_timer.h
@@ -18,30 +18,17 @@ // High-resolution (~10 ns) timestamps, using fences to prevent reordering and // ensure exactly the desired regions are measured. -#include <algorithm> -#include <cstddef> -#include <cstdint> -#include <cstdio> -#include <cstdlib> -#include <limits> -#include <utility> -#include <vector> +#include <stdint.h> +#include "highwayhash/arch_specific.h" #include "highwayhash/compiler_specific.h" -#include "highwayhash/os_specific.h" -#if HH_MSC_VERSION +#if HH_ARCH_X64 && HH_MSC_VERSION #include <emmintrin.h> // _mm_lfence #include <intrin.h> #endif -namespace tsc_timer { - -#define TSC_TIMER_CHECK(condition) \ - while (!(condition)) { \ - printf("tsc_timer check failed at line %d\n", __LINE__); \ - abort(); \ - } +namespace highwayhash { // Start/Stop return absolute timestamps and must be placed immediately before // and after the region to measure. We provide separate Start/Stop functions @@ -92,73 +79,27 @@ // prefer to avoid kernel-mode drivers. Performance counters are also affected // by several under/over-count errata, so we use the TSC instead. +// Primary templates; must use one of the specializations. template <typename T> -inline T Start() { - TSC_TIMER_CHECK(false); // Must use one of the specializations. -} +inline T Start(); template <typename T> -inline T Stop() { - TSC_TIMER_CHECK(false); // Must use one of the specializations. -} - -// Returns a 32-bit timestamp with about 4 cycles less overhead than -// Start<uint64_t>. Only suitable for measuring very short regions because the -// timestamp overflows about once a second. -template <> -inline uint32_t Start<uint32_t>() { - uint32_t t; -#if HH_MSC_VERSION - _mm_lfence(); - HH_COMPILER_FENCE; - t = static_cast<uint32_t>(__rdtsc()); - _mm_lfence(); - HH_COMPILER_FENCE; -#elif HH_CLANG_VERSION || HH_GCC_VERSION - asm volatile( - "lfence\n\t" - "rdtsc\n\t" - "lfence" - : "=a"(t) - : - // "memory" avoids reordering. rdx = TSC >> 32. - : "rdx", "memory"); -#endif - return t; -} - -template <> -inline uint32_t Stop<uint32_t>() { - uint32_t t; -#if HH_MSC_VERSION - HH_COMPILER_FENCE; - unsigned aux; - t = static_cast<uint32_t>(__rdtscp(&aux)); - _mm_lfence(); - HH_COMPILER_FENCE; -#elif HH_CLANG_VERSION || HH_GCC_VERSION - // Use inline asm because __rdtscp generates code to store TSC_AUX (ecx). - asm volatile( - "rdtscp\n\t" - "lfence" - : "=a"(t) - : - // "memory" avoids reordering. rcx = TSC_AUX. rdx = TSC >> 32. - : "rcx", "rdx", "memory"); -#endif - return t; -} +inline T Stop(); template <> inline uint64_t Start<uint64_t>() { uint64_t t; -#if HH_MSC_VERSION +#if HH_ARCH_PPC + asm volatile("mfspr %0, %1" : "=r"(t) : "i"(268)); +#elif HH_ARCH_AARCH64 + asm volatile("mrs %0, cntvct_el0" : "=r"(t)); +#elif HH_ARCH_X64 && HH_MSC_VERSION _mm_lfence(); HH_COMPILER_FENCE; t = __rdtsc(); _mm_lfence(); HH_COMPILER_FENCE; -#elif HH_CLANG_VERSION || HH_GCC_VERSION +#elif HH_ARCH_X64 && (HH_CLANG_VERSION || HH_GCC_VERSION) asm volatile( "lfence\n\t" "rdtsc\n\t" @@ -170,6 +111,8 @@ // "memory" avoids reordering. rdx = TSC >> 32. // "cc" = flags modified by SHL. : "rdx", "memory", "cc"); +#else +#error "Port" #endif return t; } @@ -177,13 +120,17 @@ template <> inline uint64_t Stop<uint64_t>() { uint64_t t; -#if HH_MSC_VERSION +#if HH_ARCH_PPC + asm volatile("mfspr %0, %1" : "=r"(t) : "i"(268)); +#elif HH_ARCH_AARCH64 + asm volatile("mrs %0, cntvct_el0" : "=r"(t)); +#elif HH_ARCH_X64 && HH_MSC_VERSION HH_COMPILER_FENCE; unsigned aux; t = __rdtscp(&aux); _mm_lfence(); HH_COMPILER_FENCE; -#elif HH_CLANG_VERSION || HH_GCC_VERSION +#elif HH_ARCH_X64 && (HH_CLANG_VERSION || HH_GCC_VERSION) // Use inline asm because __rdtscp generates code to store TSC_AUX (ecx). asm volatile( "rdtscp\n\t" @@ -195,145 +142,63 @@ // "memory" avoids reordering. rcx = TSC_AUX. rdx = TSC >> 32. // "cc" = flags modified by SHL. : "rcx", "rdx", "memory", "cc"); +#else +#error "Port" #endif return t; } -// Even with high-priority pinned threads and frequency throttling disabled, -// elapsed times are noisy due to interrupts or SMM operations. It might help -// to detect such events via transactions and omit affected measurements. -// Unfortunately, TSX is currently unavailable due to a bug. We achieve -// repeatable results with a robust measure of the central tendency. The mode -// is less affected by outliers in highly-skewed distributions than the -// median. We use the Half Sample Mode estimator proposed by Bickel in -// "On a fast, robust estimator of the mode". It requires N log N time. - -// @return i in [idx_begin, idx_begin + half_count) that minimizes -// sorted[i + half_count] - sorted[i]. -template <typename T> -size_t MinRange(const T* const HH_RESTRICT sorted, const size_t idx_begin, - const size_t half_count) { - T min_range = std::numeric_limits<T>::max(); - size_t min_idx = 0; - - for (size_t idx = idx_begin; idx < idx_begin + half_count; ++idx) { - TSC_TIMER_CHECK(sorted[idx] <= sorted[idx + half_count]); - const T range = sorted[idx + half_count] - sorted[idx]; - if (range < min_range) { - min_range = range; - min_idx = idx; - } - } - - return min_idx; +// Returns a 32-bit timestamp with about 4 cycles less overhead than +// Start<uint64_t>. Only suitable for measuring very short regions because the +// timestamp overflows about once a second. +template <> +inline uint32_t Start<uint32_t>() { + uint32_t t; +#if HH_ARCH_X64 && HH_MSC_VERSION + _mm_lfence(); + HH_COMPILER_FENCE; + t = static_cast<uint32_t>(__rdtsc()); + _mm_lfence(); + HH_COMPILER_FENCE; +#elif HH_ARCH_X64 && (HH_CLANG_VERSION || HH_GCC_VERSION) + asm volatile( + "lfence\n\t" + "rdtsc\n\t" + "lfence" + : "=a"(t) + : + // "memory" avoids reordering. rdx = TSC >> 32. + : "rdx", "memory"); +#else + t = static_cast<uint32_t>(Start<uint64_t>()); +#endif + return t; } -// Returns an estimate of the mode by calling MinRange on successively -// halved intervals. "sorted" must be in ascending order. -template <typename T> -T Mode(const T* const HH_RESTRICT sorted, const size_t num_values) { - size_t idx_begin = 0; - size_t half_count = num_values / 2; - while (half_count > 1) { - idx_begin = MinRange(sorted, idx_begin, half_count); - half_count >>= 1; - } - - const T x = sorted[idx_begin + 0]; - if (half_count == 0) { - return x; - } - TSC_TIMER_CHECK(half_count == 1); - const T average = (x + sorted[idx_begin + 1] + 1) / 2; - return average; +template <> +inline uint32_t Stop<uint32_t>() { + uint32_t t; +#if HH_ARCH_X64 && HH_MSC_VERSION + HH_COMPILER_FENCE; + unsigned aux; + t = static_cast<uint32_t>(__rdtscp(&aux)); + _mm_lfence(); + HH_COMPILER_FENCE; +#elif HH_ARCH_X64 && (HH_CLANG_VERSION || HH_GCC_VERSION) + // Use inline asm because __rdtscp generates code to store TSC_AUX (ecx). + asm volatile( + "rdtscp\n\t" + "lfence" + : "=a"(t) + : + // "memory" avoids reordering. rcx = TSC_AUX. rdx = TSC >> 32. + : "rcx", "rdx", "memory"); +#else + t = static_cast<uint32_t>(Stop<uint64_t>()); +#endif + return t; } -// Sorts integral values in ascending order. About 3x faster than std::sort for -// input distributions with very few unique values. -template <class T> -void CountingSort(T* begin, T* end) { - // Unique values and their frequency (similar to flat_map). - using Unique = std::pair<T, int>; - std::vector<Unique> unique; - for (const T* p = begin; p != end; ++p) { - const T value = *p; - const auto pos = - std::find_if(unique.begin(), unique.end(), - [value](const Unique& u) { return u.first == value; }); - if (pos == unique.end()) { - unique.push_back(std::make_pair(*p, 1)); - } else { - ++pos->second; - } - } - - // Sort in ascending order of value (pair.first). - std::sort(unique.begin(), unique.end()); - - // Write that many copies of each unique value to the array. - T* HH_RESTRICT p = begin; - for (const auto& value_count : unique) { - std::fill(p, p + value_count.second, value_count.first); - p += value_count.second; - } - TSC_TIMER_CHECK(p == end); -} - -// Returns an estimate of timer overhead on the current CPU. -template <typename T> -T EstimateResolution() { - // Even 128K samples are not enough to achieve repeatable results when - // throttling is enabled; the caller must perform additional aggregation. - const size_t kNumSamples = 512; - T samples[kNumSamples]; - for (size_t i = 0; i < kNumSamples; ++i) { - const volatile T t0 = Start<T>(); - const volatile T t1 = Stop<T>(); - TSC_TIMER_CHECK(t0 <= t1); - samples[i] = t1 - t0; - } - CountingSort(samples, samples + kNumSamples); - const T resolution = Mode(samples, kNumSamples); - TSC_TIMER_CHECK(resolution != 0); - return resolution; -} - -// Returns cycles elapsed when running an empty region, i.e. the timer -// resolution/overhead, which will be deducted from other measurements and -// also used by InitReplicas. -// T is the timestamp type, uint32_t or uint64_t. -template <typename T> -T Resolution() { - // Initialization is expensive and should only happen once. This function is - // called from function templates; we need to keep and initialize a static - // variable here because each function template has its own static variables. - static const T resolution = []() { - // It is important to return consistent results between runs. Individual - // CPUs may be slowed down by interrupts or throttled down. We instead - // measure on all CPUs, and repeat several times so the mode is distinct. - std::vector<T> resolutions; - const auto cpus = os_specific::AvailableCPUs(); - const size_t repetitions_per_cpu = 512 / cpus.size(); - - auto affinity = os_specific::GetThreadAffinity(); - for (const int cpu : cpus) { - os_specific::PinThreadToCPU(cpu); - for (size_t i = 0; i < repetitions_per_cpu; ++i) { - resolutions.push_back(EstimateResolution<T>()); - } - } - os_specific::SetThreadAffinity(affinity); - free(affinity); - - T* const begin = resolutions.data(); - CountingSort(begin, begin + resolutions.size()); - const T resolution = Mode(begin, resolutions.size()); - printf("Resolution<%zu> %lu\n", sizeof(T) * 8, long(resolution)); - return resolution; - }(); - return resolution; -} - -} // namespace tsc_timer +} // namespace highwayhash #endif // HIGHWAYHASH_TSC_TIMER_H_
diff --git a/highwayhash/vector128.h b/highwayhash/vector128.h index 2114ced..2c22925 100644 --- a/highwayhash/vector128.h +++ b/highwayhash/vector128.h
@@ -24,19 +24,36 @@ // The naming convention is VNxBBT where N is the number of lanes, BB the // number of bits per lane and T is the lane type: unsigned integer (U), // signed integer (I), or floating-point (F). -// -// Requires reasonable C++11 support (VC2015) and SSE4.1. + +// WARNING: compiled with different flags => must not define/instantiate any +// inline functions, nor include any headers that do - see instruction_sets.h. + +#include <stddef.h> +#include <stdint.h> #include "highwayhash/arch_specific.h" #include "highwayhash/compiler_specific.h" -#if HH_ENABLE_SSE41 +// For auto-dependency generation, we need to include all headers but not their +// contents (otherwise compilation fails because -msse4.1 is not specified). +#ifndef HH_DISABLE_TARGET_SPECIFIC +// WARNING: smmintrin.h will also be included through immintrin.h in the AVX2 +// translation unit, which is compiled with different flags. This risks ODR +// violations, and can cause crashes when functions are not inlined and the +// linker selects the AVX2 version. Unfortunately this include cannot reside +// within a namespace due to conflicts with other system headers. We need to +// assume all the intrinsic functions (defined as static inline by Clang's +// library and as extern inline by GCC) are in fact inlined. targets.bzl +// generates a test that verifies this by detecting duplicate symbols. #include <smmintrin.h> // SSE4.1 -#include <stddef.h> -#include <stdint.h> namespace highwayhash { +// To prevent ODR violations when including this from multiple translation +// units (TU) that are compiled with different flags, the contents must reside +// in a namespace whose name is unique to the TU. NOTE: this behavior is +// incompatible with precompiled modules and requires textual inclusion instead. +namespace HH_TARGET_NAME { // Primary template for 128-bit SSE4.1 vectors; only specializations are used. template <typename T> @@ -45,6 +62,7 @@ template <> class V128<uint8_t> { public: + using Intrinsic = __m128i; using T = uint8_t; static constexpr size_t N = 16; @@ -64,12 +82,12 @@ } // Convert from/to intrinsics. - HH_INLINE V128(const __m128i& v) : v_(v) {} - HH_INLINE V128& operator=(const __m128i& v) { + HH_INLINE V128(const Intrinsic& v) : v_(v) {} + HH_INLINE V128& operator=(const Intrinsic& v) { v_ = v; return *this; } - HH_INLINE operator __m128i() const { return v_; } + HH_INLINE operator Intrinsic() const { return v_; } // There are no greater-than comparison instructions for unsigned T. HH_INLINE V128 operator==(const V128& other) const { @@ -99,12 +117,13 @@ } private: - __m128i v_; + Intrinsic v_; }; template <> class V128<uint16_t> { public: + using Intrinsic = __m128i; using T = uint16_t; static constexpr size_t N = 8; @@ -128,12 +147,12 @@ } // Convert from/to intrinsics. - HH_INLINE V128(const __m128i& v) : v_(v) {} - HH_INLINE V128& operator=(const __m128i& v) { + HH_INLINE V128(const Intrinsic& v) : v_(v) {} + HH_INLINE V128& operator=(const Intrinsic& v) { v_ = v; return *this; } - HH_INLINE operator __m128i() const { return v_; } + HH_INLINE operator Intrinsic() const { return v_; } // There are no greater-than comparison instructions for unsigned T. HH_INLINE V128 operator==(const V128& other) const { @@ -166,7 +185,7 @@ v_ = _mm_slli_epi16(v_, count); return *this; } - HH_INLINE V128& operator<<=(const __m128i& count) { + HH_INLINE V128& operator<<=(const Intrinsic& count) { v_ = _mm_sll_epi16(v_, count); return *this; } @@ -175,18 +194,19 @@ v_ = _mm_srli_epi16(v_, count); return *this; } - HH_INLINE V128& operator>>=(const __m128i& count) { + HH_INLINE V128& operator>>=(const Intrinsic& count) { v_ = _mm_srl_epi16(v_, count); return *this; } private: - __m128i v_; + Intrinsic v_; }; template <> class V128<uint32_t> { public: + using Intrinsic = __m128i; using T = uint32_t; static constexpr size_t N = 4; @@ -210,12 +230,12 @@ } // Convert from/to intrinsics. - HH_INLINE V128(const __m128i& v) : v_(v) {} - HH_INLINE V128& operator=(const __m128i& v) { + HH_INLINE V128(const Intrinsic& v) : v_(v) {} + HH_INLINE V128& operator=(const Intrinsic& v) { v_ = v; return *this; } - HH_INLINE operator __m128i() const { return v_; } + HH_INLINE operator Intrinsic() const { return v_; } // There are no greater-than comparison instructions for unsigned T. HH_INLINE V128 operator==(const V128& other) const { @@ -248,7 +268,7 @@ v_ = _mm_slli_epi32(v_, count); return *this; } - HH_INLINE V128& operator<<=(const __m128i& count) { + HH_INLINE V128& operator<<=(const Intrinsic& count) { v_ = _mm_sll_epi32(v_, count); return *this; } @@ -257,18 +277,19 @@ v_ = _mm_srli_epi32(v_, count); return *this; } - HH_INLINE V128& operator>>=(const __m128i& count) { + HH_INLINE V128& operator>>=(const Intrinsic& count) { v_ = _mm_srl_epi32(v_, count); return *this; } private: - __m128i v_; + Intrinsic v_; }; template <> class V128<uint64_t> { public: + using Intrinsic = __m128i; using T = uint64_t; static constexpr size_t N = 2; @@ -291,12 +312,12 @@ } // Convert from/to intrinsics. - HH_INLINE V128(const __m128i& v) : v_(v) {} - HH_INLINE V128& operator=(const __m128i& v) { + HH_INLINE V128(const Intrinsic& v) : v_(v) {} + HH_INLINE V128& operator=(const Intrinsic& v) { v_ = v; return *this; } - HH_INLINE operator __m128i() const { return v_; } + HH_INLINE operator Intrinsic() const { return v_; } // There are no greater-than comparison instructions for unsigned T. HH_INLINE V128 operator==(const V128& other) const { @@ -329,7 +350,7 @@ v_ = _mm_slli_epi64(v_, count); return *this; } - HH_INLINE V128& operator<<=(const __m128i& count) { + HH_INLINE V128& operator<<=(const Intrinsic& count) { v_ = _mm_sll_epi64(v_, count); return *this; } @@ -338,18 +359,19 @@ v_ = _mm_srli_epi64(v_, count); return *this; } - HH_INLINE V128& operator>>=(const __m128i& count) { + HH_INLINE V128& operator>>=(const Intrinsic& count) { v_ = _mm_srl_epi64(v_, count); return *this; } private: - __m128i v_; + Intrinsic v_; }; template <> class V128<float> { public: + using Intrinsic = __m128; using T = float; static constexpr size_t N = 4; @@ -373,12 +395,12 @@ } // Convert from/to intrinsics. - HH_INLINE V128(const __m128& v) : v_(v) {} - HH_INLINE V128& operator=(const __m128& v) { + HH_INLINE V128(const Intrinsic& v) : v_(v) {} + HH_INLINE V128& operator=(const Intrinsic& v) { v_ = v; return *this; } - HH_INLINE operator __m128() const { return v_; } + HH_INLINE operator Intrinsic() const { return v_; } HH_INLINE V128 operator==(const V128& other) const { return V128(_mm_cmpeq_ps(v_, other.v_)); @@ -421,12 +443,13 @@ } private: - __m128 v_; + Intrinsic v_; }; template <> class V128<double> { public: + using Intrinsic = __m128d; using T = double; static constexpr size_t N = 2; @@ -449,12 +472,12 @@ } // Convert from/to intrinsics. - HH_INLINE V128(const __m128d& v) : v_(v) {} - HH_INLINE V128& operator=(const __m128d& v) { + HH_INLINE V128(const Intrinsic& v) : v_(v) {} + HH_INLINE V128& operator=(const Intrinsic& v) { v_ = v; return *this; } - HH_INLINE operator __m128d() const { return v_; } + HH_INLINE operator Intrinsic() const { return v_; } HH_INLINE V128 operator==(const V128& other) const { return V128(_mm_cmpeq_pd(v_, other.v_)); @@ -497,7 +520,7 @@ } private: - __m128d v_; + Intrinsic v_; }; // Nonmember functions for any V128 via member functions. @@ -579,19 +602,14 @@ // We differentiate between targets' vector types via template specialization. // Calling Load<V>(floats) is more natural than Load(V8x32F(), floats) and may -// generate better code in unoptimized builds. The primary template can only -// be defined once, even if multiple vector headers are included. -#ifndef HH_DEFINED_PRIMARY_TEMPLATE_FOR_LOAD -#define HH_DEFINED_PRIMARY_TEMPLATE_FOR_LOAD +// generate better code in unoptimized builds. Only declare the primary +// templates to avoid needing mutual exclusion with vector256. + template <class V> -HH_INLINE V Load(const typename V::T* const HH_RESTRICT from) { - return V(); // must specialize for each type. -} +HH_INLINE V Load(const typename V::T* const HH_RESTRICT from); + template <class V> -HH_INLINE V LoadUnaligned(const typename V::T* const HH_RESTRICT from) { - return V(); // must specialize for each type. -} -#endif +HH_INLINE V LoadUnaligned(const typename V::T* const HH_RESTRICT from); // "from" must be vector-aligned. template <> @@ -769,7 +787,8 @@ return V2x64F(_mm_max_pd(v0, v1)); } +} // namespace HH_TARGET_NAME } // namespace highwayhash -#endif // HH_ENABLE_SSE41 +#endif // HH_DISABLE_TARGET_SPECIFIC #endif // HIGHWAYHASH_VECTOR128_H_
diff --git a/highwayhash/vector256.h b/highwayhash/vector256.h index 965c5a2..c508816 100644 --- a/highwayhash/vector256.h +++ b/highwayhash/vector256.h
@@ -24,17 +24,30 @@ // The naming convention is VNxBBT where N is the number of lanes, BB the // number of bits per lane and T is the lane type: unsigned integer (U), // signed integer (I), or floating-point (F). -// -// Requires reasonable C++11 support (VC2015) and an AVX2-capable CPU. + +// WARNING: compiled with different flags => must not define/instantiate any +// inline functions, nor include any headers that do - see instruction_sets.h. + +#include <stddef.h> +#include <stdint.h> #include "highwayhash/arch_specific.h" #include "highwayhash/compiler_specific.h" -#if HH_ENABLE_AVX2 +// For auto-dependency generation, we need to include all headers but not their +// contents (otherwise compilation fails because -mavx2 is not specified). +#ifndef HH_DISABLE_TARGET_SPECIFIC + +// (This include cannot be moved within a namespace due to conflicts with +// other system headers; see the comment in hh_sse41.h.) #include <immintrin.h> -#include <stdint.h> namespace highwayhash { +// To prevent ODR violations when including this from multiple translation +// units (TU) that are compiled with different flags, the contents must reside +// in a namespace whose name is unique to the TU. NOTE: this behavior is +// incompatible with precompiled modules and requires textual inclusion instead. +namespace HH_TARGET_NAME { // Primary template for 256-bit AVX2 vectors; only specializations are used. template <typename T> @@ -43,6 +56,7 @@ template <> class V256<uint8_t> { public: + using Intrinsic = __m256i; using T = uint8_t; static constexpr size_t N = 32; @@ -63,12 +77,12 @@ } // Convert from/to intrinsics. - HH_INLINE V256(const __m256i& v) : v_(v) {} - HH_INLINE V256& operator=(const __m256i& v) { + HH_INLINE V256(const Intrinsic& v) : v_(v) {} + HH_INLINE V256& operator=(const Intrinsic& v) { v_ = v; return *this; } - HH_INLINE operator __m256i() const { return v_; } + HH_INLINE operator Intrinsic() const { return v_; } // There are no greater-than comparison instructions for unsigned T. HH_INLINE V256 operator==(const V256& other) const { @@ -98,12 +112,13 @@ } private: - __m256i v_; + Intrinsic v_; }; template <> class V256<uint16_t> { public: + using Intrinsic = __m256i; using T = uint16_t; static constexpr size_t N = 16; @@ -130,12 +145,12 @@ } // Convert from/to intrinsics. - HH_INLINE V256(const __m256i& v) : v_(v) {} - HH_INLINE V256& operator=(const __m256i& v) { + HH_INLINE V256(const Intrinsic& v) : v_(v) {} + HH_INLINE V256& operator=(const Intrinsic& v) { v_ = v; return *this; } - HH_INLINE operator __m256i() const { return v_; } + HH_INLINE operator Intrinsic() const { return v_; } // There are no greater-than comparison instructions for unsigned T. HH_INLINE V256 operator==(const V256& other) const { @@ -175,12 +190,13 @@ } private: - __m256i v_; + Intrinsic v_; }; template <> class V256<uint32_t> { public: + using Intrinsic = __m256i; using T = uint32_t; static constexpr size_t N = 8; @@ -205,12 +221,12 @@ } // Convert from/to intrinsics. - HH_INLINE V256(const __m256i& v) : v_(v) {} - HH_INLINE V256& operator=(const __m256i& v) { + HH_INLINE V256(const Intrinsic& v) : v_(v) {} + HH_INLINE V256& operator=(const Intrinsic& v) { v_ = v; return *this; } - HH_INLINE operator __m256i() const { return v_; } + HH_INLINE operator Intrinsic() const { return v_; } // There are no greater-than comparison instructions for unsigned T. HH_INLINE V256 operator==(const V256& other) const { @@ -250,12 +266,13 @@ } private: - __m256i v_; + Intrinsic v_; }; template <> class V256<uint64_t> { public: + using Intrinsic = __m256i; using T = uint64_t; static constexpr size_t N = 4; @@ -280,12 +297,12 @@ } // Convert from/to intrinsics. - HH_INLINE V256(const __m256i& v) : v_(v) {} - HH_INLINE V256& operator=(const __m256i& v) { + HH_INLINE V256(const Intrinsic& v) : v_(v) {} + HH_INLINE V256& operator=(const Intrinsic& v) { v_ = v; return *this; } - HH_INLINE operator __m256i() const { return v_; } + HH_INLINE operator Intrinsic() const { return v_; } // There are no greater-than comparison instructions for unsigned T. HH_INLINE V256 operator==(const V256& other) const { @@ -325,12 +342,13 @@ } private: - __m256i v_; + Intrinsic v_; }; template <> class V256<float> { public: + using Intrinsic = __m256; using T = float; static constexpr size_t N = 8; @@ -354,12 +372,12 @@ } // Convert from/to intrinsics. - HH_INLINE V256(const __m256& v) : v_(v) {} - HH_INLINE V256& operator=(const __m256& v) { + HH_INLINE V256(const Intrinsic& v) : v_(v) {} + HH_INLINE V256& operator=(const Intrinsic& v) { v_ = v; return *this; } - HH_INLINE operator __m256() const { return v_; } + HH_INLINE operator Intrinsic() const { return v_; } HH_INLINE V256 operator==(const V256& other) const { return V256(_mm256_cmp_ps(v_, other.v_, 0)); @@ -402,12 +420,13 @@ } private: - __m256 v_; + Intrinsic v_; }; template <> class V256<double> { public: + using Intrinsic = __m256d; using T = double; static constexpr size_t N = 4; @@ -431,12 +450,12 @@ } // Convert from/to intrinsics. - HH_INLINE V256(const __m256d& v) : v_(v) {} - HH_INLINE V256& operator=(const __m256d& v) { + HH_INLINE V256(const Intrinsic& v) : v_(v) {} + HH_INLINE V256& operator=(const Intrinsic& v) { v_ = v; return *this; } - HH_INLINE operator __m256d() const { return v_; } + HH_INLINE operator Intrinsic() const { return v_; } HH_INLINE V256 operator==(const V256& other) const { return V256(_mm256_cmp_pd(v_, other.v_, 0)); @@ -479,7 +498,7 @@ } private: - __m256d v_; + Intrinsic v_; }; // Nonmember functions for any V256 via member functions. @@ -552,19 +571,14 @@ // We differentiate between targets' vector types via template specialization. // Calling Load<V>(floats) is more natural than Load(V8x32F(), floats) and may -// generate better code in unoptimized builds. The primary template can only -// be defined once, even if multiple vector headers are included. -#ifndef HH_DEFINED_PRIMARY_TEMPLATE_FOR_LOAD -#define HH_DEFINED_PRIMARY_TEMPLATE_FOR_LOAD +// generate better code in unoptimized builds. Only declare the primary +// templates to avoid needing mutual exclusion with vector128. + template <class V> -HH_INLINE V Load(const typename V::T* const HH_RESTRICT from) { - return V(); // must specialize for each type. -} +HH_INLINE V Load(const typename V::T* const HH_RESTRICT from); + template <class V> -HH_INLINE V LoadUnaligned(const typename V::T* const HH_RESTRICT from) { - return V(); // must specialize for each type. -} -#endif +HH_INLINE V LoadUnaligned(const typename V::T* const HH_RESTRICT from); template <> HH_INLINE V32x8U Load(const V32x8U::T* const HH_RESTRICT from) { @@ -735,7 +749,8 @@ return V4x64F(_mm256_max_pd(v0, v1)); } +} // namespace HH_TARGET_NAME } // namespace highwayhash -#endif // HH_ENABLE_AVX2 +#endif // HH_DISABLE_TARGET_SPECIFIC #endif // HIGHWAYHASH_VECTOR256_H_
diff --git a/highwayhash/vector_test.cc b/highwayhash/vector_test.cc index d632740..d9f0256 100644 --- a/highwayhash/vector_test.cc +++ b/highwayhash/vector_test.cc
@@ -12,184 +12,40 @@ // See the License for the specific language governing permissions and // limitations under the License. -#include <algorithm> -#include <limits> +#include <stdio.h> #ifdef HH_GOOGLETEST #include "testing/base/public/gmock.h" #include "testing/base/public/gunit.h" #endif -#include "highwayhash/vector128.h" -#include "highwayhash/vector256.h" +#include "highwayhash/instruction_sets.h" +#include "highwayhash/vector_test_target.h" namespace highwayhash { namespace { -#ifndef HH_GOOGLETEST -template <typename T1, typename T2> -void EXPECT_EQ(const T1 expected, const T2 actual) { - if (actual != expected) { - printf("Mismatch\n"); - abort(); - } -} +void NotifyFailure(const char* target, const size_t size) { + const size_t lane_bits = (size & 0xFF) * 8; + const size_t lane_index = size >> 8; +#ifdef HH_GOOGLETEST + EXPECT_TRUE(false) << "VectorTest failed for " << target << " T=" << lane_bits + << ", lane " << lane_index; +#else + printf("VectorTest failed for %10s T=%zu, lane=%zu\n", target, lane_bits, + lane_index); #endif - -template <class V> -void AllEqual(const V& v, const typename V::T expected) { - using T = typename V::T; - T lanes[V::N] HH_ALIGNAS(32); - Store(v, lanes); - for (size_t i = 0; i < V::N; ++i) { - EXPECT_EQ(expected, lanes[i]); - } } -// "Native" is the __m256i etc. underlying "V". -template <class V, typename Native> -void TestMembersAndBinaryOperatorsExceptShifts() { - using T = typename V::T; - - // uninitialized - V v; - - // broadcast - const V v2(2); - AllEqual(v2, T(2)); - - // assign from V - const V v3(3); - V v3b; - v3b = v3; - AllEqual(v3b, T(3)); - - // equal - const V veq(v3 == v3b); - AllEqual(veq, std::numeric_limits<T>::max()); - - // Copying to native and constructing from native yields same result. - Native nv2 = v2; - V v2b(nv2); - AllEqual(v2b, T(2)); - - // .. same for assignment from native. - V v2c; - v2c = nv2; - AllEqual(v2c, T(2)); - - const V add = v2 + v3; - AllEqual(add, T(5)); - - const V sub = v3 - v2; - AllEqual(sub, T(1)); - - const V vand = v3 & v2; - AllEqual(vand, T(2)); - - const V vor = add | v2; - AllEqual(vor, T(7)); - - const V vxor = v3 ^ v2; - AllEqual(vxor, T(1)); -} - -// SSE does not allow shifting uint8_t, so instantiate for all other types. -template <class V> -void TestShifts() { - using T = typename V::T; - - const V v1(1); - // Shifting out of right side => zero - AllEqual(v1 >> 1, T(0)); - - // Simple left shift - AllEqual(v1 << 1, T(2)); - - // Sign bit - constexpr int kSign = (sizeof(T) * 8) - 1; - constexpr T max = std::numeric_limits<T>::max(); - constexpr T sign = ~(max >> 1); - AllEqual(v1 << kSign, sign); - - // Shifting out of left side => zero - AllEqual(v1 << (kSign + 1), T(0)); -} - -template <class V> -void TestLoadStore() { - const size_t n = V::N; - using T = typename V::T; - T lanes[2 * n] HH_ALIGNAS(32); - std::fill(lanes, lanes + n, 4); - std::fill(lanes + n, lanes + 2 * n, 5); - // Aligned load - const V v4 = Load<V>(lanes); - AllEqual(v4, T(4)); - - // Aligned store - T lanes4[n] HH_ALIGNAS(32); - Store(v4, lanes4); - for (const T value4 : lanes4) { - EXPECT_EQ(4, value4); - } - - // Unaligned load - const V vu = LoadUnaligned<V>(lanes + 1); - Store(vu, lanes4); - EXPECT_EQ(5, lanes4[n - 1]); - for (size_t i = 1; i < n - 1; ++i) { - EXPECT_EQ(4, lanes4[i]); - } - - // Unaligned store - StoreUnaligned(v4, lanes + n / 2); - size_t i; - for (i = 0; i < 3 * n / 2; ++i) { - EXPECT_EQ(4, lanes[i]); - } - // Subsequent values remain unchanged. - for (; i < 2 * n; ++i) { - EXPECT_EQ(5, lanes[i]); - } -} - -void TestVector() { -#if HH_ENABLE_SSE41 - TestMembersAndBinaryOperatorsExceptShifts<V16x8U, __m128i>(); - TestMembersAndBinaryOperatorsExceptShifts<V8x16U, __m128i>(); - TestMembersAndBinaryOperatorsExceptShifts<V4x32U, __m128i>(); - TestMembersAndBinaryOperatorsExceptShifts<V2x64U, __m128i>(); - - TestShifts<V8x16U>(); - TestShifts<V4x32U>(); - TestShifts<V2x64U>(); - - TestLoadStore<V16x8U>(); - TestLoadStore<V8x16U>(); - TestLoadStore<V4x32U>(); - TestLoadStore<V2x64U>(); -#endif - -#if HH_ENABLE_AVX2 - TestMembersAndBinaryOperatorsExceptShifts<V32x8U, __m256i>(); - TestMembersAndBinaryOperatorsExceptShifts<V16x16U, __m256i>(); - TestMembersAndBinaryOperatorsExceptShifts<V8x32U, __m256i>(); - TestMembersAndBinaryOperatorsExceptShifts<V4x64U, __m256i>(); - - TestShifts<V16x16U>(); - TestShifts<V8x32U>(); - TestShifts<V4x64U>(); - - TestLoadStore<V32x8U>(); - TestLoadStore<V16x16U>(); - TestLoadStore<V8x32U>(); - TestLoadStore<V4x64U>(); -#endif +void RunTests() { + const TargetBits tested = InstructionSets::RunAll<VectorTest>(&NotifyFailure); + HH_TARGET_NAME::ForeachTarget(tested, [](const TargetBits target) { + printf("%10s: done\n", TargetName(target)); + }); } #ifdef HH_GOOGLETEST -TEST(VectorTest, Run) { TestVector(); } +TEST(VectorTest, Run) { RunTests(); } #endif } // namespace @@ -197,8 +53,7 @@ #ifndef HH_GOOGLETEST int main(int argc, char* argv[]) { - highwayhash::TestVector(); - printf("TestVector succeeded.\n"); + highwayhash::RunTests(); return 0; } #endif
diff --git a/highwayhash/vector_test_avx2.cc b/highwayhash/vector_test_avx2.cc new file mode 100644 index 0000000..e5bdb33 --- /dev/null +++ b/highwayhash/vector_test_avx2.cc
@@ -0,0 +1,16 @@ +// Copyright 2017 Google Inc. All Rights Reserved. +// +// 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. + +#define HH_TARGET_NAME AVX2 +#include "highwayhash/vector_test_target.cc"
diff --git a/highwayhash/vector_test_portable.cc b/highwayhash/vector_test_portable.cc new file mode 100644 index 0000000..638f69d --- /dev/null +++ b/highwayhash/vector_test_portable.cc
@@ -0,0 +1,16 @@ +// Copyright 2017 Google Inc. All Rights Reserved. +// +// 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. + +#define HH_TARGET_NAME Portable +#include "highwayhash/vector_test_target.cc"
diff --git a/highwayhash/vector_test_sse41.cc b/highwayhash/vector_test_sse41.cc new file mode 100644 index 0000000..9addaff --- /dev/null +++ b/highwayhash/vector_test_sse41.cc
@@ -0,0 +1,16 @@ +// Copyright 2017 Google Inc. All Rights Reserved. +// +// 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. + +#define HH_TARGET_NAME SSE41 +#include "highwayhash/vector_test_target.cc"
diff --git a/highwayhash/vector_test_target.cc b/highwayhash/vector_test_target.cc new file mode 100644 index 0000000..c9371de --- /dev/null +++ b/highwayhash/vector_test_target.cc
@@ -0,0 +1,199 @@ +// Copyright 2017 Google Inc. All Rights Reserved. +// +// 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. + +// WARNING: compiled with different flags => must not define/instantiate any +// inline functions, nor include any headers that do - see instruction_sets.h. + +#include "highwayhash/vector_test_target.h" + +#include <algorithm> +#include <limits> + +#include "highwayhash/arch_specific.h" + +#if HH_TARGET == HH_TARGET_AVX2 +#include "highwayhash/vector256.h" +#elif HH_TARGET == HH_TARGET_SSE41 +#include "highwayhash/vector128.h" +#elif HH_TARGET == HH_TARGET_Portable +#include "highwayhash/scalar.h" +#else +#error "Unknown target, add its include here." +#endif + +#ifndef HH_DISABLE_TARGET_SPECIFIC +namespace highwayhash { +namespace HH_TARGET_NAME { +namespace { + +#if HH_TARGET == HH_TARGET_AVX2 +template <typename T> +using V = V256<T>; +#elif HH_TARGET == HH_TARGET_SSE41 +template <typename T> +using V = V128<T>; +#elif HH_TARGET == HH_TARGET_Portable +template <typename T> +using V = Scalar<T>; +#else +#error "Unknown target, add its vector typedef here." +#endif + +template <class T> +void NotifyIfUnequal(const V<T>& v, const T expected, const HHNotify notify) { + T lanes[V<T>::N] HH_ALIGNAS(32); + Store(v, lanes); + for (size_t i = 0; i < V<T>::N; ++i) { + if (lanes[i] != expected) { + notify(TargetName(HH_TARGET), (i << 8) | sizeof(T)); + } + } +} + +template <class T> +void NotifyIfUnequal(const T& t, const T expected, const HHNotify notify) { + if (t != expected) { + notify(TargetName(HH_TARGET), sizeof(T)); + } +} + +template <typename T> +void TestMembersAndBinaryOperatorsExceptShifts(const HHNotify notify) { + // uninitialized + V<T> v; + + // broadcast + const V<T> v2(2); + NotifyIfUnequal(v2, T(2), notify); + + // assign from V + const V<T> v3(3); + V<T> v3b; + v3b = v3; + NotifyIfUnequal(v3b, T(3), notify); + + // equal + const V<T> veq(v3 == v3b); + NotifyIfUnequal(veq, std::numeric_limits<T>::max(), notify); + + // Copying to, and constructing from intrinsic yields same result. + typename V<T>::Intrinsic nv2 = v2; + V<T> v2b(nv2); + NotifyIfUnequal(v2b, T(2), notify); + + // .. assignment also works. + V<T> v2c; + v2c = nv2; + NotifyIfUnequal(v2c, T(2), notify); + + const V<T> add = v2 + v3; + NotifyIfUnequal(add, T(5), notify); + + const V<T> sub = v3 - v2; + NotifyIfUnequal(sub, T(1), notify); + + const V<T> vand = v3 & v2; + NotifyIfUnequal(vand, T(2), notify); + + const V<T> vor = add | v2; + NotifyIfUnequal(vor, T(7), notify); + + const V<T> vxor = v3 ^ v2; + NotifyIfUnequal(vxor, T(1), notify); +} + +// SSE does not allow shifting uint8_t, so instantiate for all other types. +template <class T> +void TestShifts(const HHNotify notify) { + const V<T> v1(1); + // Shifting out of right side => zero + NotifyIfUnequal(v1 >> 1, T(0), notify); + + // Simple left shift + NotifyIfUnequal(v1 << 1, T(2), notify); + + // Sign bit + constexpr int kSign = (sizeof(T) * 8) - 1; + constexpr T max = std::numeric_limits<T>::max(); + constexpr T sign = ~(max >> 1); + NotifyIfUnequal(v1 << kSign, sign, notify); + + // Shifting out of left side => zero + NotifyIfUnequal(v1 << (kSign + 1), T(0), notify); +} + +template <class T> +void TestLoadStore(const HHNotify notify) { + const size_t n = V<T>::N; + T lanes[2 * n] HH_ALIGNAS(32); + std::fill(lanes, lanes + n, 4); + std::fill(lanes + n, lanes + 2 * n, 5); + // Aligned load + const V<T> v4 = Load<V<T>>(lanes); + NotifyIfUnequal(v4, T(4), notify); + + // Aligned store + T lanes4[n] HH_ALIGNAS(32); + Store(v4, lanes4); + NotifyIfUnequal(Load<V<T>>(lanes4), T(4), notify); + + // Unaligned load + const V<T> vu = LoadUnaligned<V<T>>(lanes + 1); + Store(vu, lanes4); + NotifyIfUnequal(lanes4[n - 1], T(5), notify); + for (size_t i = 1; i < n - 1; ++i) { + NotifyIfUnequal(lanes4[i], T(4), notify); + } + + // Unaligned store + StoreUnaligned(v4, lanes + n / 2); + size_t i; + for (i = 0; i < 3 * n / 2; ++i) { + NotifyIfUnequal(lanes[i], T(4), notify); + } + // Subsequent values remain unchanged. + for (; i < 2 * n; ++i) { + NotifyIfUnequal(lanes[i], T(5), notify); + } +} + +void TestAll(const HHNotify notify) { + TestMembersAndBinaryOperatorsExceptShifts<uint8_t>(notify); + TestMembersAndBinaryOperatorsExceptShifts<uint16_t>(notify); + TestMembersAndBinaryOperatorsExceptShifts<uint32_t>(notify); + TestMembersAndBinaryOperatorsExceptShifts<uint64_t>(notify); + + TestShifts<uint16_t>(notify); + TestShifts<uint32_t>(notify); + TestShifts<uint64_t>(notify); + + TestLoadStore<uint8_t>(notify); + TestLoadStore<uint16_t>(notify); + TestLoadStore<uint32_t>(notify); + TestLoadStore<uint64_t>(notify); +} + +} // namespace +} // namespace HH_TARGET_NAME + +template <TargetBits Target> +void VectorTest<Target>::operator()(const HHNotify notify) const { + HH_TARGET_NAME::TestAll(notify); +} + +// Instantiate for the current target. +template struct VectorTest<HH_TARGET>; + +} // namespace highwayhash +#endif // HH_DISABLE_TARGET_SPECIFIC
diff --git a/highwayhash/vector_test_target.h b/highwayhash/vector_test_target.h new file mode 100644 index 0000000..f9310d4 --- /dev/null +++ b/highwayhash/vector_test_target.h
@@ -0,0 +1,35 @@ +// Copyright 2017 Google Inc. All Rights Reserved. +// +// 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. + +#ifndef HIGHWAYHASH_VECTOR_TEST_TARGET_H_ +#define HIGHWAYHASH_VECTOR_TEST_TARGET_H_ + +// WARNING: compiled with different flags => must not define/instantiate any +// inline functions, nor include any headers that do - see instruction_sets.h. + +#include "highwayhash/arch_specific.h" +#include "highwayhash/hh_types.h" + +namespace highwayhash { + +// Usage: InstructionSets::RunAll<VectorTest>(). Calls "notify" for each test +// failure. +template <TargetBits Target> +struct VectorTest { + void operator()(const HHNotify notify) const; +}; + +} // namespace highwayhash + +#endif // HIGHWAYHASH_VECTOR_TEST_TARGET_H_