Survey Memoization Tracking Performance Degradation

[chikuwait]

Problem

The memoization tracking mechanism may have performance overhead. When there are few or no memoizable points in the WebAssembly bytecode, the tracking overhead could negatively impact execution performance.

Current Implementation

The memoization mechanism caches execution results of code blocks (not individual instructions) to avoid redundant computation. Key components:

Block Caching: Caches blocks of code based on instruction pointer range (start_ip, end_ip), stack state, and local variables. A block is only cached after being executed 10 times (CACHE_EXECUTION_THRESHOLD).

Cache Key: Uses FxHasher to compute hash of stack (last 8 values) and all local variables. The cache key includes start_ip, end_ip, stack_hash, and locals_hash.

Dependency Tracking: Tracks dependencies to determine cache validity:

• Local variables: Tracks which locals are accessed with version numbers
• Memory chunks: Tracks memory writes by chunk (4KB regions) with version numbers
• Global variables: Tracks global variable accesses with version numbers

Cache Invalidation: Before using cached result, checks if any tracked dependencies have changed versions. Invalidates on any version mismatch.

LRU Eviction: Uses LRU cache (max 5000 blocks) with eviction tracking.

Objective

Survey and identify the reasons for performance degradation in the memoization tracking mechanism.

Analysis Approach

This issue focuses on analyzing the memoization tracking mechanism to understand why it causes performance degradation. The analysis will investigate several key areas:

Tracking Overhead: We will measure the time cost of the tracking mechanism itself, including cache lookup operations, cache key generation, and LRU cache management. This will help quantify how much overhead the tracking adds compared to actual instruction execution.

Cache Effectiveness: We will analyze cache hit rates across different types of workloads to understand when memoization is actually beneficial. Low cache hit rates indicate that the overhead of tracking exceeds any performance gains from caching results.

Workload Characteristics: Different WebAssembly programs have different patterns of instruction execution. Programs with many repeated operations should benefit from memoization, while programs with few repeated operations will suffer from pure overhead. We will characterize what types of workloads cause performance degradation.

Implementation Bottlenecks: By profiling the memoization code path, we can identify specific operations that contribute most to the overhead. This includes analyzing the cost of hash computation, cache lookups, and eviction policies in the LRU cache.

The goal is to produce concrete measurements and identify specific bottlenecks that explain why memoization tracking degrades performance when there are few memoizable points in the bytecode.