6.7 KiB
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:
/* 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:
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)
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) comparisonsompi_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
+ /* 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 inompi_group_translate_ranksompi/group/group.c:464–484: nested loop inompi_group_intersectionompi/group/group.c:629–640: nested loop inompi_group_overlapompi/group/group.c:527–544: nested loop inompi_group_compare
Scan Date
2026-03-29