Implementation:ClickHouse ClickHouse MemcmpSmall

Knowledge Sources	ClickHouse
Domains	Memory, SIMD
Last Updated	2026-02-08 00:00 GMT

Overview

SIMD-optimized memory comparison functions specialized for small memory regions with support for overflow reads.

Description

This code provides a family of optimized memory comparison functions designed for comparing small strings and fixed-size data. The implementation uses SIMD instructions (AVX-512, SSE2, or ARM NEON) to compare 16 bytes at a time, significantly faster than byte-by-byte comparison. A key feature is "allow overflow 15" - the functions can safely read up to 15 bytes beyond the valid region, simplifying the code by eliminating edge case handling. The implementation provides several variants: comparing regions of different sizes, comparing with zero-padding semantics (for SQL compatibility), comparing equal-sized regions, and specialized 16-byte comparisons. Platform-specific implementations ensure optimal performance across x86 and ARM architectures.

Usage

Use this when comparing small strings or fixed-size memory regions (typically under 1KB) in performance-critical code. The "allow overflow" variants require that the memory allocator or caller guarantees readable memory for 15 bytes past the valid region. Common use cases include string comparison in hash tables, sorting small keys, and comparing fixed-width database columns.

Code Reference

Source Location

• Repository: ClickHouse
• File: base/base/memcmpSmall.h
• Lines: 1-842

Signature

// Compare memory regions with different sizes (can read 15 bytes past end)
template <typename Char>
inline int memcmpSmallAllowOverflow15(const Char * a, size_t a_size,
                                      const Char * b, size_t b_size);

// Compare with zero-padding semantics (SQL compatibility)
template <typename Char>
inline int memcmpSmallLikeZeroPaddedAllowOverflow15(const Char * a, size_t a_size,
                                                     const Char * b, size_t b_size);

// Compare equal-sized regions (can read 15 bytes past end)
template <typename Char>
inline int memcmpSmallAllowOverflow15(const Char * a, const Char * b, size_t size);

// Compare for equality
template <typename Char>
inline bool memequalSmallAllowOverflow15(const Char * a, size_t a_size,
                                         const Char * b, size_t b_size);

// Specialized for sizes that are multiples of 16
template <typename Char>
inline int memcmpSmallMultipleOf16(const Char * a, const Char * b, size_t size);

// Specialized for exactly 16 bytes
template <typename Char>
inline int memcmp16(const Char * a, const Char * b);

inline bool memequal16(const void * a, const void * b);

// Check if memory region is all zeros
inline bool memoryIsZeroSmallAllowOverflow15(const void * data, size_t size);

// AVX-512 specific helper
inline bool compare16(const char * p1, const char * p2);
inline bool compare64(const char * p1, const char * p2);

Import

#include <base/memcmpSmall.h>

I/O Contract

Inputs

Name	Type	Required	Description
a, b	const Char *	Yes	Pointers to memory regions to compare
a_size, b_size	size_t	Yes	Sizes of memory regions
size	size_t	Yes	Size when both regions are same size
data	const void *	Yes	Memory region to check for zeros

Outputs

Name	Type	Description
comparison	int	-1 if a < b, 0 if equal, 1 if a > b
equal	bool	True if memory regions are equal
is_zero	bool	True if memory region contains only zeros

Usage Examples

#include <base/memcmpSmall.h>

// Compare short strings
const char * s1 = "hello";
const char * s2 = "world";
int cmp = memcmpSmallAllowOverflow15(s1, 5, s2, 5);
if (cmp < 0) {
    // s1 < s2
}

// Compare with different sizes
const char * short_str = "abc";
const char * long_str = "abcdefgh";
int result = memcmpSmallAllowOverflow15(short_str, 3, long_str, 8);
// result < 0 because shorter string is "less"

// SQL-style zero-padded comparison
// "abc" compared to "abc\0\0" should be equal
const char * a = "abc";
const char * b = "abc\0\0\0\0\0";
int sql_cmp = memcmpSmallLikeZeroPaddedAllowOverflow15(a, 3, b, 8);
// sql_cmp == 0 (equal)

// Fast equality check
const char * str1 = "test";
const char * str2 = "test";
bool equal = memequalSmallAllowOverflow15(str1, 4, str2, 4);
// equal == true

// Specialized 16-byte comparison (e.g., UUID)
struct UUID {
    uint8_t bytes[16];
};
UUID uuid1, uuid2;
int uuid_cmp = memcmp16(uuid1.bytes, uuid2.bytes);

// Fast 16-byte equality (e.g., hash comparison)
uint8_t hash1[16] = {...};
uint8_t hash2[16] = {...};
if (memequal16(hash1, hash2)) {
    // Hashes match
}

// Check if memory is zeroed
uint8_t buffer[64];
memset(buffer, 0, sizeof(buffer));
if (memoryIsZeroSmallAllowOverflow15(buffer, 64)) {
    // Buffer is all zeros
}

// Multiple of 16 bytes (optimized path)
char aligned_data1[64];
char aligned_data2[64];
int aligned_cmp = memcmpSmallMultipleOf16(aligned_data1, aligned_data2, 64);

// Use in hash table comparison
struct StringKey {
    const char * data;
    size_t size;

    bool operator==(const StringKey & other) const {
        if (size != other.size) return false;
        return memequalSmallAllowOverflow15(data, size, other.data, other.size);
    }
};

// Fixed-size string comparison in sorting
std::vector<std::string> strings;
std::sort(strings.begin(), strings.end(), [](const auto & a, const auto & b) {
    return memcmpSmallAllowOverflow15(a.data(), a.size(), b.data(), b.size()) < 0;
});

Related Pages

• Principle:ClickHouse_ClickHouse_SIMD_Memory_Comparison