How mulle-objc-runtime Uses Unique IDs Instead of Names for Classes and Selectors

mulle-objc-runtime replaces all Objective-C class names and selector strings with 32-bit unique IDs at compile time, enabling O(1) integer-based hashmap lookups instead of expensive string comparisons.

The mulle-objc-runtime eliminates runtime string processing entirely by converting every class name, selector, ivar, and property name into a typed unique identifier during compilation. This design choice transforms method dispatch and class registration from linear string searches into constant-time hashmap operations backed by compact integer keys.

Converting Names to Unique IDs at Compile Time

The runtime generates unique IDs through mulle_objc_uniqueid_from_string(), which implements an FNV-1a hash algorithm with configurable bit rotation. This function is wrapped by type-specific inline helpers that provide type safety for different ID categories:

static inline mulle_objc_classid_t   mulle_objc_classid_from_string   (char *s) { return mulle_objc_uniqueid_from_string(s); }
static inline mulle_objc_methodid_t  mulle_objc_methodid_from_string  (char *s) { return mulle_objc_uniqueid_from_string(s); }

Source: src/mulle-objc-uniqueid.h (lines 28-44)

The hashing process in src/mulle-objc-uniqueid.c rotates the hash bits using MULLE_OBJC_UNIQUEHASH_SHIFT and explicitly rejects the sentinel values 0 and -1 to prevent collisions with invalid markers. The mulle_objc_uniqueid_is_sane() function validates that generated IDs fall within the acceptable range, ensuring that neither MULLE_OBJC_INVALID_UNIQUEID (0) nor -1 enter the runtime tables.

Runtime Data Structures That Store Unique IDs

Every major runtime structure replaces string pointers with typed 32-bit integer fields. The following table shows how identifiers propagate through core objects:

Structure	Field	Purpose	Definition Location
struct _mulle_objc_infraclass	classid	Concrete class identifier	src/mulle-objc-infraclass.c (line 176)
struct _mulle_objc_class	classid	Cached copy of the infra class ID	src/mulle-objc-class.c (line 99)
struct _mulle_objc_method	methodid	Selector identifier for method entries	src/mulle-objc-method.c (line 109)
struct _mulle_objc_property	propertyid, getter, setter	Property and accessor identifiers	src/mulle-objc-infraclass.c (lines 337-389)

By storing only 4-byte integers rather than variable-length C strings, the runtime reduces memory overhead and guarantees cache-friendly, fixed-size layout across all lookup tables.

Fast Lookup and Dispatch Using Integer IDs

All runtime lookups operate on hashmaps keyed by numeric IDs rather than string comparisons. The universe maintains concurrent hashmaps that map these identifiers to their corresponding structures:

infra = _mulle_concurrent_hashmap_lookup(&universe->classtable, classid);
desc  = _mulle_objc_universe_lookup_descriptor(universe, methodid);

Source: src/mulle-objc-universe.c (lines 1246-1290)

The class table (universe->classtable) uses the classid as a direct hash key, while the descriptor table maps methodid values to method descriptors. Because the keys are 32-bit integers, the hash function is trivial (often identity or simple masking), maximizing cache locality and minimizing latency during message dispatch.

The compiler emits code that resolves names to IDs at build time, as shown in this class registration pattern:

/* Generated by the mulle-objc compiler */
static void _MulleObjCClassRegister_MyClass(void)
{
    mulle_objc_classid_t classid = mulle_objc_classid_from_string("MyClass");
    _mulle_objc_universe_register_infraclass_for_classid(
        mulle_objc_global_universe(),
        classid);
}

Source: src/mulle-objc-classpair.c (lines 173-178)

Similarly, message sends compile to descriptor lookups using pre-hashed selector IDs:

/* Compiled call site for [obj doThing:] */
mulle_objc_methodid_t sel = mulle_objc_methodid_from_string("doThing:");
struct _mulle_objc_descriptor *desc =
    _mulle_objc_universe_lookup_descriptor(universe, sel);
return desc->implementation(obj, sel, NULL);

Source: src/mulle-objc-call.c (lines 208-213)

Safety and Validation of Unique IDs

Before executing sensitive operations like super-calls, the runtime validates that received IDs are sane:

if (!mulle_objc_uniqueid_is_sane(p->methodid)) abort();

Source: src/mulle-objc-super.c (line 54)

This validation ensures that malformed or zeroed memory cannot trigger undefined behavior. Property accessor lookups also rely on validated selector IDs:

struct _mulle_objc_property *prop =
    _mulle_objc_infraclass_find_property_for_methodid(infra, selector_id);

Source: src/mulle-objc-infraclass.c (lines 176-209)

Performance Benefits of the ID-Based Design

The shift from strings to unique IDs provides measurable advantages across four critical dimensions:

• Dispatch Speed: Integer comparison and hashmap lookup operate in constant time, whereas traditional Objective-C runtimes require string hashing or linear probing during method resolution.
• Memory Efficiency: Storing 4-byte integers instead of null-terminated UTF-8 strings reduces per-entry overhead significantly; original string literals reside only in the binary's read-only constant section.
• Cache Friendliness: Fixed-size integer keys enable predictable memory layout in fast method tables (mulle_objc_fastmethodtable), minimizing cache misses during hot-path dispatch.
• Collision Resistance: The FNV-1a algorithm produces astronomically low collision rates for typical identifier sets, while the sentinel check (mulle_objc_uniqueid_is_sane) guarantees that the theoretical collision producing 0 or -1 triggers an immediate abort rather than silent corruption.

Summary

• mulle-objc-runtime converts all Objective-C names to 32-bit unique IDs at compile time using mulle_objc_uniqueid_from_string().
• Core structures like struct _mulle_objc_infraclass and struct _mulle_objc_method store typed integer IDs (classid, methodid) instead of strings.
• Lookups occur through concurrent hashmaps keyed by integers, eliminating string comparison overhead.
• The runtime validates all IDs via mulle_objc_uniqueid_is_sane() to prevent undefined behavior from invalid sentinels.
• This architecture provides O(1) method dispatch, reduced memory footprint, and superior cache locality compared to traditional string-based Objective-C runtimes.

Frequently Asked Questions

What hashing algorithm does mulle-objc-runtime use to generate unique IDs?

The runtime uses an FNV-1a 32-bit hash implemented in src/mulle-objc-uniqueid.c, combined with a configurable bit rotation (MULLE_OBJC_UNIQUEHASH_SHIFT). This algorithm provides excellent distribution characteristics for identifier strings while remaining simple enough to execute at compile time.

How does the runtime handle hash collisions for class and selector names?

Collisions are theoretically possible but statistically improbable with the FNV-1a algorithm. The runtime explicitly reserves 0 and -1 as invalid sentinel values through mulle_objc_uniqueid_is_sane(). In the extremely unlikely event that a hash produces one of these values, the runtime aborts immediately rather than risking undefined behavior.

Why does mulle-objc-runtime use 32-bit integers instead of 64-bit pointers for identifiers?

Using 32-bit unique IDs reduces memory pressure in hash tables and method caches while providing 4 billion possible identifiers—more than sufficient for any practical Objective-C codebase. The smaller size improves CPU cache density during method dispatch, directly reducing latency in the hot path.

Can the runtime convert unique IDs back to human-readable names for debugging?

While the runtime stores only the integer IDs in its active tables, the original UTF-8 string literals remain in the binary's constant section. Debug builds can map IDs back to names using external symbol tables or the compiler's generated metadata, though production builds may strip these strings to minimize binary size.

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