📡 Repost Radar Engine

Ultra-Low Latency C++20 Text Deduplication & Stream Filtering Engine.
Powered by AVX2 SIMD Hardware Vectorization, Zero-Copy Token Shingling, and Concurrent Slab-Allocated LSH Indexing.

👉 Launch Interactive Mod Console Sandbox
Test duplicate checking, LSH band collisions, and vector Venn diagram overlaps live in your browser.

---

🚀 HERO PERFORMANCE BENCHMARKS

• Stream Processing Throughput: 22,450+ tokenized streams/sec
• AVX2 Vectorization Speedup: 4.2x faster MinHash signature generation over scalar loops
• Memory Allocation Footprint: 65% reduction in heap allocations via zero-copy std::string_view shingling
• LSH Lookup Latency: O(1) sub-microsecond hash bucket lookup under high thread concurrency

---

💡 The "Why" vs. "How" (Systems Rationale)

• The Bottleneck (Why standard deduplication scales poorly):
  Real-time deduplication across massive data streams (like Reddit submissions, log feeds, or document caches) traditionally requires allocating thousands of temporary string objects on the heap. Hashing input shingles sequentially in scalar CPU loops creates severe cache misses and memory allocation bottlenecks.
• The Low-Level Fix (How we solved it):
  Repost Radar eliminates heap allocations during tokenization by maintaining contiguous memory buffers and referencing shingle slices via zero-copy std::string_view. Hashing is hardware-accelerated using explicit Intel AVX2 SIMD intrinsics, parallelizing 128 universal hash variants across 256-bit YMM CPU registers simultaneously. Finally, external database calls are replaced with an in-memory concurrent Locality-Sensitive Hashing (LSH) index partitioned with std::shared_mutex for lock-free reader concurrency.

---

🛠️ How It Was Achieved (Engineering Deep-Dive)

To sustain 22,450+ streams/sec with a 4.2x SIMD speedup, three core low-level engineering optimizations were built:

1. Intel AVX2 SIMD Hardware Vectorization (256-Bit YMM Registers)

• Universal Hash Vectorization: MinHash computes 128 universal hash variants ($h_i(x) = (a_i \cdot x + b_i) \pmod p$).
• YMM Register Packing: 8x 32-bit hash coefficients are loaded into 256-bit AVX2 YMM registers using _mm256_load_si256.
• Parallel Minimum Reduction: Executes SIMD multiplication (_mm256_mullo_epi32), addition (_mm256_add_epi32), and element-wise minimum tracking (_mm256_min_epu32) across 16 YMM iterations, evaluating 8 hashes per instruction cycle.

// AVX2 SIMD MinHash vector reduction snippet
__m256i v_shingle = _mm256_set1_epi32(shingle_hash);
__m256i v_a       = _mm256_load_si256((__m256i*)&coeff_a[i]);
__m256i v_b       = _mm256_load_si256((__m256i*)&coeff_b[i]);
__m256i v_cur_min = _mm256_load_si256((__m256i*)&min_hashes[i]);

// Parallel AVX2 Vector Operations
__m256i v_hash = _mm256_add_epi32(_mm256_mullo_epi32(v_shingle, v_a), v_b);
v_cur_min      = _mm256_min_epu32(v_cur_min, v_hash); // 8-way minimum tracking
_mm256_store_si256((__m256i*)&min_hashes[i], v_cur_min);

2. Zero-Copy Token Shingling via std::string_view

• Zero Allocation Memory Model: Input stream text resides in a single contiguous string buffer.
• Slice Referencing: N-gram shingle arrays store lightweight 16-byte std::string_view structures referencing offsets within the raw buffer rather than copying sub-strings, eliminating 65% of dynamic heap allocations.

3. Concurrent Slab-Allocated LSH Hash Index

• Signature Banding: MinHash signatures (128 integers) are split into $b=16$ bands of $r=8$ rows.
• Sharded Lock Partitioning: LSH bucket tables are split into 32 mutex-protected shards using std::shared_mutex. Reader threads acquire shared read locks (std::shared_lock) to query candidate buckets concurrently without blocking other readers.

---

🏗️ Hardware Architecture & Vectorization Flow

flowchart TD
    Stream[Inbound Text Stream] -->|1. Contiguous Buffer| Shingle[Zero-Copy Shingling std::string_view]
    Shingle -->|2. Shingle Token Hashes| SIMD[SIMD MinHash Compute Engine]
    
    subgraph HardwareRegisters [Intel AVX2 256-Bit YMM Registers]
        SIMD -->|3. _mm256_load_si256| Reg1[YMM0: 8x 32-bit Hash Coefficients A]
        SIMD -->|4. _mm256_mullo_epi32| Reg2[YMM1: 8x 32-bit Hash Coefficients B]
        Reg1 & Reg2 -->|5. _mm256_min_epu32| Min[Parallel MinHash Register Reduction]
    end
    
    Min -->|6. MinHash Signature Vector| LSH[LSH Banding Engine]
    
    subgraph MemoryIndex [Concurrent Slab-Allocated LSH Index]
        LSH -->|7. Hash Band Keys| Buckets[Sharded Hash Buckets std::shared_mutex]
        Buckets -->|8. Candidate Probe| Match[Determine Jaccard Similarity Ratio]
    end
    
    Match -->|9. Action Result| Output[Accept / Mark Repost / Remove]

Loading

---

📊 Empirical Benchmarks

Benchmarked on an Intel Core i9 system (AVX2 enabled, 16 threads):

Module	Benchmark Method	Throughput	Latency	Memory Allocation
Token Shingling	Zero-Copy std::string_view	48,100 streams/sec	0.02 μs / shingle	0 Heap Allocations
Token Shingling	Standard std::string copies	14,200 streams/sec	0.07 μs / shingle	65% Allocation Overhead
MinHash Generation	AVX2 SIMD Vectorized	22,450 signatures/sec	0.84 μs / stream	Reg Memory Alignment
MinHash Generation	Scalar Loop (Sequential)	5,340 signatures/sec	3.52 μs / stream	High Instruction Latency
LSH Index Query	Sharded std::shared_mutex	1,450,000 queries/sec	0.68 μs / query	Thread-Safe Lock-Free Reads

---

⚡ Core Technical Features

1. Zero-Copy Token Shingling (std::string_view):
   Parses raw input text streams into n-gram shingles by storing lightweight string slices (std::string_view) pointing directly to the input buffer, eliminating dynamic memory allocations.
2. AVX2 SIMD Vectorized MinHash Generation:
   Utilizes explicit AVX2 SIMD instructions (_mm256_load_si256, _mm256_mullo_epi32, _mm256_add_epi32, _mm256_min_epu32) to compute 128 universal hash variants simultaneously across CPU registers, delivering a 4.2x speedup.
3. Concurrent Slab-Allocated LSH Index:
   Segments MinHash signatures into $b$ bands of $r$ rows. Stores buckets inside a concurrent, sharded hash map protected by reader-writer locks (std::shared_mutex), granting lock-free read access to multiple worker threads.
4. Reddit Devvit Moderation Integration:
   Productized as a live Reddit Developer Platform (Devvit) moderation app using TypeScript webhooks and Redis Sorted Sets to flag reposted content in real-time.

---

🚀 Quick Start (< 1 Minute)

Prerequisites

• C++20 compatible compiler (GCC 10+, Clang 10+, MSVC 2019+)
• CMake 3.16+
• CPU with AVX2 instruction support

Building & Running Benchmarks

# Clone repository
git clone https://github.com/harsharajkumar-273/Repost-Radar.git
cd Repost-Radar

# Configure and compile in Release mode
mkdir -p build && cd build
cmake -DCMAKE_BUILD_TYPE=Release ..
make -j$(nproc)

# Run performance benchmark suite
./bench_repost

Usage Example

#include "shingler.h"
#include "minhash.h"
#include "lsh_index.h"

// 1. Initialize SIMD Hasher and Sharded LSH Index
Shingler shingler(kShingleSize);
AVX2MinHasher hasher(numHashFunctions);
LSHIndex index(bands, rows);

// 2. Process input text with zero-copy views
std::string rawPost = "High performance C++20 deduplication engine...";
auto shingles = shingler.computeShingles(rawPost);

// 3. Compute AVX2 SIMD MinHash Signature
Signature sig = hasher.computeSignature(shingles);

// 4. Query LSH Index for candidate matches (O(1))
auto candidateIds = index.query(sig);
if (!candidateIds.empty()) {
    std::cout << "Duplicate submission detected! Matches: " << candidateIds.size() << std::endl;
} else {
    index.insert(postId, sig);
}

---

🗺️ Open-Source Roadmap & Good First Issues

• [Issue #1] ARM Neon SIMD Port: Implement fallback SIMD vectorization routines using ARM Neon intrinsics for Apple Silicon (M-series) and ARM64 servers.
• [Issue #2] Python / PyO3 C-Extension Bindings: Expose the C++ engine to Python via PyO3 / CFFI for use in PyTorch / pandas data processing pipelines.
• [Issue #3] CUDA GPU Acceleration: Add a CUDA kernel implementation to process batch data streams of 100,000+ items on NVIDIA GPUs.
• [Issue #4] Redis Module Wrapper: Package the engine as a native Redis C-module to enable custom REPOST.CHECK and REPOST.INSERT commands.

---

📜 License

Distributed under the MIT License. See LICENSE for details.