# UNDF: UNDF-2026-000000350
# artemis-0001: BindingsImpl routeFromCluster O(R×A) → O(R+A)

## Location
`artemis-server/src/main/java/org/apache/activemq/artemis/core/postoffice/impl/BindingsImpl.java`
Lines 630–664 (`routeFromCluster`)

## Severity
HIGH — called on every clustered message that requires selective ACK routing

## Description
`routeFromCluster` decodes two byte arrays: `ids` (all binding IDs to route to) and
`idsToAck` (subset that require ACK). It builds `idsToAckList` as an `ArrayList<Long>`,
then iterates over `ids` calling `idsToAckList.contains(bindingID)` for each entry.

For R route targets and A ACK targets, this is O(R×A). Since this method is called
on the hot message routing path in clustered deployments, it compounds per message.

## Root Cause
```java
private void routeFromCluster(final Message message, final RoutingContext context,
                               final byte[] ids) throws Exception {
    byte[] idsToAck = (byte[]) message.removeProperty(Message.HDR_ROUTE_TO_ACK_IDS);
    List<Long> idsToAckList = new ArrayList<>();          // ← ArrayList

    if (idsToAck != null) {
        ByteBuffer buff = ByteBuffer.wrap(idsToAck);
        while (buff.hasRemaining()) {
            idsToAckList.add(buff.getLong());             // populate O(A)
        }
    }

    ByteBuffer buff = ByteBuffer.wrap(ids);
    while (buff.hasRemaining()) {                         // O(R) loop
        long bindingID = buff.getLong();
        Binding binding = bindingsIdMap.get(bindingID);
        if (binding != null) {
            if (idsToAckList.contains(bindingID)) {      // O(A) scan → O(R×A) total
                binding.routeWithAck(message, context);
            } else {
                binding.route(message, context);
            }
        }
    }
}
```

## Fix
Use a `HashSet<Long>` instead of `ArrayList<Long>` for `idsToAckSet`:

```java
private void routeFromCluster(final Message message, final RoutingContext context,
                               final byte[] ids) throws Exception {
    byte[] idsToAck = (byte[]) message.removeProperty(Message.HDR_ROUTE_TO_ACK_IDS);
    Set<Long> idsToAckSet = new HashSet<>();              // ← HashSet

    if (idsToAck != null) {
        ByteBuffer buff = ByteBuffer.wrap(idsToAck);
        while (buff.hasRemaining()) {
            idsToAckSet.add(buff.getLong());              // populate O(A)
        }
    }

    ByteBuffer buff = ByteBuffer.wrap(ids);
    while (buff.hasRemaining()) {                         // O(R) loop
        long bindingID = buff.getLong();
        Binding binding = bindingsIdMap.get(bindingID);
        if (binding != null) {
            if (idsToAckSet.contains(bindingID)) {       // O(1) → O(R+A) total
                binding.routeWithAck(message, context);
            } else {
                binding.route(message, context);
            }
        }
    }
}
```

## Complexity
| | Before | After |
|---|---|---|
| routeFromCluster | O(R×A) | O(R+A) |

Where R=routing targets, A=ACK targets.
At R=100 bindings, A=50 ACKs: 5,000 ops per message → 150 ops (33x improvement).
Under sustained load of 10,000 msg/s this saves ~49.8M operations/second.

## Context
This is in the clustered message routing path — called when the broker receives a
message with `HDR_ROUTE_TO_ACK_IDS` set, routing to multiple queues where some
require acknowledgment. In large clustered deployments with many queues per address,
R and A can be large.
