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

> Discover how mulle-objc-runtime's impcache implements lock-free method dispatch. Learn about its atomic operations for dynamic growth and efficient invalidation without blocking.

- Repository: [mulle-objc/mulle-objc-runtime](https://github.com/mulle-objc/mulle-objc-runtime)
- Tags: internals
- Published: 2026-03-07

---

**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](https://github.com/mulle-objc/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`](https://github.com/mulle-objc/mulle-objc-runtime/blob/main/src/mulle-objc-impcache.h), the `struct _mulle_objc_impcache` wraps the generic `mulle_objc_cache` with runtime-specific callbacks:

```c
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`](https://github.com/mulle-objc/mulle-objc-runtime/blob/main/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`](https://github.com/mulle-objc/mulle-objc-runtime/blob/main/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`](https://github.com/mulle-objc/mulle-objc-runtime/blob/main/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`](https://github.com/mulle-objc/mulle-objc-runtime/blob/main/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`](https://github.com/mulle-objc/mulle-objc-runtime/blob/main/test/demo/impcache.c) demonstrates the complete workflow:

```c
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`](https://github.com/mulle-objc/mulle-objc-runtime/blob/main/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`](https://github.com/mulle-objc/mulle-objc-runtime/blob/main/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`](https://github.com/mulle-objc/mulle-objc-runtime/blob/main/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.