ABI: Performance Concern: ABI Datatype Converter Uses Linear Search in Hot Path

[hppritcha]

Performance Concern: ABI Datatype Converter Uses Linear Search in Hot Path

Summary

The standard ABI datatype converter functions currently use a linear if/else if chain to convert between ABI handle values and internal Open MPI datatype pointers. This chain scans through ~60-70 predefined datatypes (50 from PREDEFINED_DATATYPES plus ~18 from PREDEFINED_OPTIONAL_FORTRAN_DATATYPES). Because these converter functions are marked with __opal_attribute_always_inline__, this linear search is inlined into every standard-ABI call site that converts a datatype, including the critical point-to-point and collective communication hot paths.

Impact

This design has two primary concerns:

1. Latency: User-defined datatypes must scan through the entire predefined list before falling through to the default case. In a project where short-message latency is a headline metric, this overhead is measurable.

2. Code size: The ~60-70-branch scan is duplicated at every ABI converter call site due to forced inlining, leading to code bloat.

Current Implementation

The converter is generated in ompi/mpi/bindings/ompi_bindings/c.py:247 and produces code similar to:

static inline MPI_Datatype convert_datatype_abi_to_ompi(MPI_Datatype datatype) {
    if (datatype == MPI_CHAR_ABI_INTERNAL) return ompi_mpi_char;
    else if (datatype == MPI_SHORT_ABI_INTERNAL) return ompi_mpi_short;
    else if (datatype == MPI_INT_ABI_INTERNAL) return ompi_mpi_int;
    // ... ~60-70 more comparisons ...
    else return (MPI_Datatype) datatype;  // user-defined or pass-through
}

Attempted Solutions and Constraints

Initial proposal: Generate a switch statement over the sequential ABI handle values to enable compiler jump table optimization:

switch ((intptr_t) datatype) {
    case <abi_value_1>: return <ompi_name_1>;
    case <abi_value_2>: return <ompi_name_2>;
    // ...
    default: return (MPI_Datatype) datatype;
}

Problem: This approach is not portable. The predefined ABI handle constants are defined as pointer-typed compile-time constants (e.g., ((MPI_Datatype)((void*)N))). According to C11 §6.6, switch case labels must be integer constant expressions, which cannot contain casts from pointer types. Therefore, case (intptr_t) MPI_INT_ABI_INTERNAL: is not a valid constant expression and will not compile.

The linear if/else if chain is currently the only portable form for comparing these pointer constants.

Additional Complexity

The converter functions also include:

• An offset fast-path optimization for certain handle ranges
• A pass-through default case for user-defined types
• Multiple converter functions for different handle types (datatypes, communicators, groups, etc.)

This means the handle space is not dense or contiguous, which would complicate any perfect-hash or jump-table approach.

Potential Future Optimizations

If profiling demonstrates that this linear search appears in latency-critical paths, possible optimization approaches include:

1. Perfect hash function: Design a minimal perfect hash for the ~60-70 predefined constants
2. Range check optimization: Exploit the fact that ABI handles use the reserved 1-4095 integer band; could use a lookup table for this range
3. Compiler-specific extensions: Investigate if specific compilers offer pragmas/attributes to optimize the linear chain
4. Binary search: Convert the linear chain to a binary search tree (though this would require sortable handle values)

Questions for Discussion

1. Has anyone profiled whether this converter overhead is measurable in real-world MPI application latency?
2. Would removing the __opal_attribute_always_inline__ attribute (allowing the compiler to decide) help with code size without hurting latency?
3. Are there other handle types (communicators, groups, etc.) with similar concerns?
4. Should we add this as a known performance consideration in the ABI documentation?

References

• PR Updated ABI generation code and new libraries #13280, discussion comments:
  • Updated ABI generation code and new libraries #13280 (comment)
  • Updated ABI generation code and new libraries #13280 (comment)
• Code location: ompi/mpi/bindings/ompi_bindings/c.py:247 (generator)
• Affected converter pattern: generic_convert function for all handle types

Labels

performance, abi, optimization, latency