# UNDF: UNDF-2026-000000399
# ompi-0001: ompi_group O(N×M) nested process-name scan in group set operations

## Classification

| Field | Value |
|-------|-------|
| Project | Open MPI |
| Component | `ompi/group/group.c` |
| Severity | HIGH |
| CWE | CWE-407: Inefficient Algorithmic Complexity |
| Pattern | O(N) process-name scan inside O(N) outer loop → O(N×M) |
| Speedup | ~250x at N=M=500 (large MPI groups, non-sparse path) |
| Status | DEFECT — unpatched |

## Affected Functions

Three functions in `ompi/group/group.c` use nested loops over
`ompi_group_get_proc_name` + `opal_compare_proc` with no hash acceleration
on the dense (non-sparse) code path:

| Function | File:Line | Complexity |
|----------|-----------|-----------|
| `ompi_group_translate_ranks` | `group.c:47` (fallback at ~105) | O(n_ranks × M) |
| `ompi_group_intersection` | `group.c:444` | O(N × M) |
| `ompi_group_overlap` | `group.c:629` | O(N × M) |

A fourth function `ompi_group_compare` (group.c:491) contains the same
nested loop pattern:

| Function | File:Line | Complexity |
|----------|-----------|-----------|
| `ompi_group_compare` | `group.c:491` | O(N²) |

## Root Cause

### `ompi_group_translate_ranks` (dense fallback, group.c:105–130)

When neither group is the parent of the other (the sparse fast-path is
skipped), the function falls through to a dense O(n_ranks × M) scan:

```c
/* loop over all ranks */
for (int proc = 0; proc < n_ranks; ++proc) {
    ompi_process_name_t proc1_name, proc2_name;
    int rank = ranks1[proc];
    proc1_name = ompi_group_get_proc_name(group1, rank);
    ranks2[proc] = MPI_UNDEFINED;
    for (int proc2 = 0; proc2 < group2->grp_proc_count; ++proc2) {
        proc2_name = ompi_group_get_proc_name(group2, proc2);
        if(0 == opal_compare_proc(proc1_name, proc2_name)) {
            ranks2[proc] = proc2;
            break;
        }
    }  /* end proc2 loop */
} /* end proc loop */
```

### `ompi_group_intersection` (group.c:464–484)

Same double loop:

```c
for (proc1 = 0; proc1 < group1_pointer->grp_proc_count; proc1++) {
    proc1_name = ompi_group_get_proc_name(group1_pointer, proc1);
    for (proc2 = 0; proc2 < group2_pointer->grp_proc_count; proc2++) {
        proc2_name = ompi_group_get_proc_name(group2_pointer, proc2);
        if(0 == opal_compare_proc(proc1_name, proc2_name)) {
            ranks_included[k] = proc1;
            k++;
            break;
        }
    }  /* end proc2 loop */
}  /* end proc1 loop */
```

### `ompi_group_overlap` (group.c:629–640)

```c
for (int i = 0 ; i < group1->grp_proc_count ; ++i) {
    opal_process_name_t proc1 = ompi_group_get_proc_name(group1, i);
    for (int j = 0 ; j < group2->grp_proc_count ; ++j) {
        opal_process_name_t proc2 = ompi_group_get_proc_name(group2, j);
        if (0 == opal_compare_proc (proc1, proc2)) {
            return true;
        }
    }
}
```

The sparse group optimisation (`#if OMPI_GROUP_SPARSE`) exists for
parent-child relationships (e.g., a subgroup derived directly from a
parent communicator). However when two **independent** groups are compared —
the typical case in MPI collective communicator creation, multi-communicator
algorithms, and fault-tolerance operations — the sparse fast-path is skipped
and the O(N×M) path executes.

## Complexity Proof

- N = `group1->grp_proc_count`, M = `group2->grp_proc_count`
- `ompi_group_translate_ranks` (dense path): O(n_ranks × M)
- `ompi_group_intersection`: O(N × M) comparisons
- `ompi_group_overlap`: O(N × M) comparisons, worst case

For N = M = 500 (a 500-rank MPI group): 250,000 name comparisons vs 500 with hash.

`opal_compare_proc` compares two `opal_process_name_t` structs (jobid + vpid),
typically an 8-byte comparison — lightweight but executed N×M times.

## Fix

Build an `opal_hash_table_t` keyed on `opal_process_name_t` (encoded as
`uint64_t`) mapping to rank index for `group2` before entering the outer loop.
Replace the inner `for (proc2...)` with a single O(1) hash lookup.

### Patch: `ompi/group/group.c` — `ompi_group_translate_ranks` fallback

```diff
+    /* Build reverse hash for group2: proc_name_key -> rank */
+    opal_hash_table_t *g2_ht = OBJ_NEW(opal_hash_table_t);
+    opal_hash_table_init(g2_ht, group2->grp_proc_count * 2);
+    for (int i = 0; i < group2->grp_proc_count; i++) {
+        opal_process_name_t n = ompi_group_get_proc_name(group2, i);
+        uint64_t key = (((uint64_t)n.jobid) << 32) | n.vpid;
+        opal_hash_table_set_value_uint64(g2_ht, key, (void *)(uintptr_t)(i + 1));
+    }
+
     /* loop over all ranks */
     for (int proc = 0; proc < n_ranks; ++proc) {
         ompi_process_name_t proc1_name;
         int rank = ranks1[proc];
         if ( MPI_PROC_NULL == rank) {
             ranks2[proc] = MPI_PROC_NULL;
             continue;
         }
         proc1_name = ompi_group_get_proc_name(group1, rank);
-        ranks2[proc] = MPI_UNDEFINED;
-        for (int proc2 = 0; proc2 < group2->grp_proc_count; ++proc2) {
-            proc2_name = ompi_group_get_proc_name(group2, proc2);
-            if(0 == opal_compare_proc(proc1_name, proc2_name)) {
-                ranks2[proc] = proc2;
-                break;
-            }
-        }  /* end proc2 loop */
+        uint64_t key = (((uint64_t)proc1_name.jobid) << 32) | proc1_name.vpid;
+        void *val = NULL;
+        opal_hash_table_get_value_uint64(g2_ht, key, &val);
+        ranks2[proc] = val ? (int)((uintptr_t)val - 1) : MPI_UNDEFINED;
     } /* end proc loop */
+
+    OBJ_RELEASE(g2_ht);
```

The same pattern applies to `ompi_group_intersection` and
`ompi_group_overlap`: build a hash of group2 process names before the outer
loop, replace the inner loop with a single lookup.

## Speedup Estimate

| N = M (group size) | Current comparisons | Patched | Speedup |
|--------------------|---------------------|---------|---------|
| 100 | 10,000 | 200 | 50x |
| 500 | 250,000 | 1,000 | 250x |
| 2000 | 4,000,000 | 4,000 | 1000x |

In a 2000-rank collective algorithm that calls `MPI_Group_translate_ranks`
during communicator setup, this reduces 4M name comparisons to 4K.

## Relationship to Existing Sparse Optimisation

The existing `#if OMPI_GROUP_SPARSE` fast-path handles only parent-child
group relationships (a subgroup derived from a parent communicator). The
O(N×M) path triggers for **all other combinations**, which includes any two
independently-created groups. The hash fix handles the general case and
does not conflict with the sparse path.

## Evidence

- `ompi/group/group.c:105–130`: nested loop in `ompi_group_translate_ranks`
- `ompi/group/group.c:464–484`: nested loop in `ompi_group_intersection`
- `ompi/group/group.c:629–640`: nested loop in `ompi_group_overlap`
- `ompi/group/group.c:527–544`: nested loop in `ompi_group_compare`

## Scan Date
2026-03-29
