87fa27518c
Transform existing array-based UnifiedCache from FIFO ring to LIFO stack.
A/B Results:
- Mixed (16-1024B): -0.70% (52,965,966 → 52,593,948 ops/s)
- C7-only (1025-2048B): +0.42% (78,010,783 → 78,335,509 ops/s)
Verdict: NEUTRAL (both below +1.0% GO threshold) - freeze as research box
Implementation:
- L0 ENV gate: tiny_unified_lifo_env_box.{h,c} (HAKMEM_TINY_UNIFIED_LIFO=0/1)
- L1 LIFO ops: tiny_unified_lifo_box.h (unified_cache_try_pop/push_lifo)
- L2 integration: tiny_front_hot_box.h (mode check at entry)
- Reuses existing slots[] array (no intrusive pointers)
Root Causes:
1. Mode check overhead (tiny_unified_lifo_enabled() call)
2. Minimal LIFO vs FIFO locality delta in practice
3. Existing FIFO ring already well-optimized
Bonus Fix: LTO bug for tiny_c7_preserve_header_enabled() (Phase 13/14 latent issue)
- Converted static inline to extern + non-inline implementation
- Fixes undefined reference during LTO linking
Design: docs/analysis/PHASE15_UNIFIEDCACHE_LIFO_1_DESIGN.md
Results: docs/analysis/PHASE15_UNIFIEDCACHE_LIFO_1_AB_TEST_RESULTS.md
🤖 Generated with [Claude Code](https://claude.com/claude-code)
Co-Authored-By: Claude Sonnet 4.5 <noreply@anthropic.com>
122 lines
3.5 KiB
C
122 lines
3.5 KiB
C
// ============================================================================
|
|
// Phase 15 v1: Tiny Unified LIFO Box (L1) - LIFO Stack Operations
|
|
// ============================================================================
|
|
//
|
|
// Purpose: LIFO (stack) operations for UnifiedCache
|
|
//
|
|
// Design: docs/analysis/PHASE15_UNIFIEDCACHE_LIFO_1_DESIGN.md
|
|
//
|
|
// Strategy:
|
|
// - Reuse existing TinyUnifiedCache.slots[] array
|
|
// - Treat `tail` as stack top (depth)
|
|
// - Treat `head` as unused (always 0)
|
|
// - No wrap-around (`mask` unused)
|
|
//
|
|
// Invariants:
|
|
// - 0 <= tail <= capacity (stack depth)
|
|
// - head == 0 (unused in LIFO mode)
|
|
// - LIFO and FIFO modes are mutually exclusive
|
|
//
|
|
// API:
|
|
// unified_cache_try_pop_lifo(class_idx) -> void* (BASE or NULL)
|
|
// unified_cache_try_push_lifo(class_idx, base) -> int (1=success, 0=full)
|
|
//
|
|
// Safety:
|
|
// - Debug: assert tail <= capacity
|
|
// - Release: fast path, no checks
|
|
//
|
|
// ============================================================================
|
|
|
|
#ifndef TINY_UNIFIED_LIFO_BOX_H
|
|
#define TINY_UNIFIED_LIFO_BOX_H
|
|
|
|
#include <stdint.h>
|
|
#include <assert.h>
|
|
#include "../hakmem_build_flags.h"
|
|
#include "../hakmem_tiny_config.h" // TINY_NUM_CLASSES
|
|
#include "../front/tiny_unified_cache.h" // TinyUnifiedCache
|
|
#include "tiny_unified_lifo_env_box.h" // tiny_unified_lifo_enabled
|
|
|
|
// ============================================================================
|
|
// LIFO Pop (Alloc Fast Path)
|
|
// ============================================================================
|
|
//
|
|
// Arguments:
|
|
// class_idx - Tiny class index (0-7)
|
|
//
|
|
// Returns:
|
|
// BASE pointer - Block from top of stack
|
|
// NULL - Stack empty
|
|
//
|
|
// Side effects:
|
|
// - Decrements tail (stack depth)
|
|
//
|
|
// LIFO semantics:
|
|
// - Pop from top of stack (tail - 1)
|
|
// - tail is "one past last element" (like vector.size())
|
|
//
|
|
|
|
__attribute__((always_inline))
|
|
static inline void* unified_cache_try_pop_lifo(int class_idx) {
|
|
extern __thread TinyUnifiedCache g_unified_cache[];
|
|
TinyUnifiedCache* cache = &g_unified_cache[class_idx];
|
|
|
|
// Empty check (tail == 0 means stack is empty)
|
|
if (__builtin_expect(cache->tail == 0, 0)) {
|
|
return NULL; // Empty
|
|
}
|
|
|
|
// Pop from top of stack (LIFO)
|
|
void* base = cache->slots[--cache->tail];
|
|
|
|
// Debug: validate stack depth
|
|
#if !HAKMEM_BUILD_RELEASE
|
|
assert(cache->tail <= cache->capacity);
|
|
#endif
|
|
|
|
return base; // HIT (BASE pointer)
|
|
}
|
|
|
|
// ============================================================================
|
|
// LIFO Push (Free Fast Path)
|
|
// ============================================================================
|
|
//
|
|
// Arguments:
|
|
// class_idx - Tiny class index (0-7)
|
|
// base - BASE pointer to freed block
|
|
//
|
|
// Returns:
|
|
// 1 - Block pushed to stack (success)
|
|
// 0 - Stack full (overflow)
|
|
//
|
|
// Side effects:
|
|
// - Increments tail (stack depth)
|
|
//
|
|
// LIFO semantics:
|
|
// - Push to top of stack (tail)
|
|
// - tail is "one past last element"
|
|
//
|
|
|
|
__attribute__((always_inline))
|
|
static inline int unified_cache_try_push_lifo(int class_idx, void* base) {
|
|
extern __thread TinyUnifiedCache g_unified_cache[];
|
|
TinyUnifiedCache* cache = &g_unified_cache[class_idx];
|
|
|
|
// Full check (tail == capacity means stack is full)
|
|
if (__builtin_expect(cache->tail >= cache->capacity, 0)) {
|
|
return 0; // Full
|
|
}
|
|
|
|
// Push to top of stack (LIFO)
|
|
cache->slots[cache->tail++] = base;
|
|
|
|
// Debug: validate stack depth
|
|
#if !HAKMEM_BUILD_RELEASE
|
|
assert(cache->tail <= cache->capacity);
|
|
#endif
|
|
|
|
return 1; // SUCCESS
|
|
}
|
|
|
|
#endif // TINY_UNIFIED_LIFO_BOX_H
|