How the Implementation Cache (impcache) Works in mulle-objc-runtime: Lock-Free Method Dispatch

The implementation cache (impcache) is a per-class, lock-free hash table in mulle-objc-runtime that stores resolved method implementations (IMPs), using atomic compare-and-swap operations to grow dynamically and invalidate entries without blocking concurrent message sends.

The implementation cache (impcache) is a critical performance component in the mulle-objc-runtime, designed to eliminate repeated method lookup overhead during Objective-C message dispatch. Unlike traditional global caches, this architecture maintains a per-class, growable hash table that maps unique method identifiers to their compiled function pointers. By leveraging lock-free atomic operations, the runtime achieves high-concurrency method dispatch without mutex contention.

Core Architecture and Data Structures

The impcache Structure

In src/mulle-objc-impcache.h, the struct _mulle_objc_impcache wraps the generic mulle_objc_cache with runtime-specific callbacks:

struct _mulle_objc_impcache {
   struct _mulle_objc_cache               cache;
   struct _mulle_objc_impcache_callback   callback;
};

The callback structure contains function pointers for call_cache_miss, handling collisions, and super-call resolution, allowing the runtime to customize behavior without modifying the underlying cache logic.

The Pivot and Atomic Operations

The struct _mulle_objc_impcachepivot (also in src/mulle-objc-impcache.h) enables thread-safe cache replacement. It wraps struct _mulle_objc_cachepivot to provide atomic compare-and-swap (CAS) capabilities for the cache pointer, allowing the entire hash table to be swapped out when growth or invalidation is required.

Life Cycle of an Implementation Cache Entry

Cache Creation and Initialization

Creation begins with mulle_objc_impcache_new in src/mulle-objc-impcache.c. This function allocates a contiguous memory block containing the cache structure plus its initial hash buckets, normalizing the size to a power-of-two within runtime limits (MULLE_OBJC_MIN_CACHE_SIZE to MULLE_OBJC_MAX_CACHE_SIZE).

Fast-Path Lookup via Hash Probing

During message dispatch, the runtime calls inline helpers like _mulle_objc_impcachepivot_probe_inline or _mulle_objc_impcachepivot_lookup_inline_full (defined in src/mulle-objc-class-impcache.h). These functions:

• Atomically load the cache pointer from the pivot using _mulle_objc_class_get_impcache_cache_atomic
• Compute the bucket index by masking the method's unique identifier (uniqueid)
• Use linear probing to locate the matching entry or an empty slot

Handling Cache Misses

When the lookup fails, the runtime invokes the callback.call_cache_miss handler. This callback traverses the class hierarchy to resolve the method implementation, then fills the cache using _mulle_objc_impcachepivot_fill.

Growth and Atomic Swapping

If the cache exceeds its fill threshold during insertion, _mulle_objc_impcache_grow_with_strategy creates a larger impcache using strategies like MULLE_OBJC_CACHESIZE_GROW. The new cache is installed atomically via _mulle_objc_impcachepivot_convenient_swap, which performs a CAS on pivot.entries.

If the CAS fails because another thread already swapped the cache, the current thread frees its temporary cache and retries. If successful, the old cache enters ABA-free deallocation via _mulle_objc_impcache_abafree.

Invalidation and Deallocation

Individual entries or entire caches are invalidated using _mulle_objc_class_invalidate_impcacheentry (from src/mulle-objc-class-impcache.c), which atomically resets bucket keys to MULLE_OBJC_NO_UNIQUEID to force re-resolution. Final cleanup uses _mulle_objc_impcache_free or the ABA-safe variant when concurrent readers might still hold stale pointers.

Thread Safety and Lock-Free Design

The implementation cache achieves lock-free concurrency through several mechanisms:

• Atomic reads: Cache pointers are loaded with _mulle_atomic_pointer_read_nonatomic during lookups
• CAS insertion: Only one thread succeeds in swapping a new cache during growth; others retry with the updated pointer
• ABA-free memory: The _mulle_objc_impcache_abafree function ensures memory remains valid even if a thread observes a stale cache pointer during a race condition

Practical Implementation Example

The test suite in test/demo/impcache.c demonstrates the complete workflow:

static struct _mulle_objc_cacheentry *
demo_impcachepivot_fill( struct _mulle_objc_impcachepivot *cachepivot,
                         mulle_objc_implementation_t imp,
                         mulle_objc_uniqueid_t uniqueid,
                         unsigned int fillrate,
                         struct mulle_allocator *allocator)
{
    struct _mulle_objc_impcache *icache, *old_cache;
    struct _mulle_objc_cache *cache;
    struct _mulle_objc_cacheentry *entry;

    for (;;)
    {
        cache = _mulle_objc_cachepivot_get_cache_atomic(&cachepivot->pivot);
        if (_mulle_objc_cache_should_grow(cache, fillrate))
        {
            old_cache = _mulle_objc_cache_get_impcache_from_cache(cache);
            icache = _mulle_objc_impcache_grow_with_strategy(old_cache,
                                 MULLE_OBJC_CACHESIZE_GROW, allocator);
            _mulle_objc_impcachepivot_swap(cachepivot, icache, old_cache,
                                           allocator);
            continue;
        }
        entry = _mulle_objc_cache_add_functionpointer_entry(cache,
                                 (mulle_functionpointer_t)imp, uniqueid);
        if (entry) break;
    }
    return entry;
}

This function implements the standard fill pattern: check if growth is needed using _mulle_objc_cache_should_grow, allocate a larger cache with _mulle_objc_impcache_grow_with_strategy, attempt atomic swap with _mulle_objc_impcachepivot_swap, and retry if another thread modified the cache concurrently.

Summary

• The implementation cache stores method implementations in a per-class, lock-free hash table built atop struct _mulle_objc_cache
• Atomic compare-and-swap operations in _mulle_objc_impcachepivot_swap enable cache growth without blocking message dispatch
• The pivot structure (_mulle_objc_impcachepivot) manages safe pointer replacement during concurrent access via CAS loops
• ABA-free deallocation (_mulle_objc_impcache_abafree) prevents use-after-free when threads hold stale cache references
• Cache invalidation via _mulle_objc_class_invalidate_impcacheentry forces method re-resolution when class hierarchies change or methods are modified

Frequently Asked Questions

What is the difference between mulle_objc_cache and mulle_objc_impcache?

The mulle_objc_cache is a generic, reusable hash table structure defined in the core headers, while mulle_objc_impcache (defined in src/mulle-objc-impcache.h) wraps this generic cache with runtime-specific callback functions for handling cache misses, super-calls, and method refreshes. This separation allows the core caching logic to remain agnostic while the impcache adapts it specifically for Objective-C method dispatch.

How does the impcache handle concurrent growth without locks?

When a thread detects the cache needs growth during _mulle_objc_impcachepivot_fill, it allocates a new larger cache using _mulle_objc_impcache_grow_with_strategy and attempts to install it using _mulle_objc_impcachepivot_swap, which performs an atomic compare-and-swap on the pivot's entries pointer. If another thread wins the race, the losing thread frees its temporary cache and retries with the winner's cache, ensuring lock-free progress according to the algorithm in src/mulle-objc-impcache.c.

What happens to old caches when they are replaced?

Replaced caches enter ABA-free deallocation via _mulle_objc_impcache_abafree rather than immediate freeing. This safety mechanism, implemented in the runtime's allocator subsystem, ensures that if a concurrent reader still holds a pointer to the old cache during a race condition, the memory remains valid and reusable, preventing crashes from use-after-free scenarios.

How are cache entries invalidated when methods change?

The runtime calls _mulle_objc_class_invalidate_impcacheentry (from src/mulle-objc-class-impcache.c) to atomically reset a bucket's unique identifier key to MULLE_OBJC_NO_UNIQUEID. This forces subsequent lookups to trigger a cache miss, prompting the runtime to re-resolve the method implementation against the current class hierarchy and install the updated IMP.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}