diff options
| author | Simon MacMullen <simon@rabbitmq.com> | 2015-02-19 11:44:40 +0000 |
|---|---|---|
| committer | Simon MacMullen <simon@rabbitmq.com> | 2015-02-19 11:44:40 +0000 |
| commit | 1bc340d81faff82d4b415e34f20bc7990390e995 (patch) | |
| tree | 62d4acb63782d8412020ca8dcfa64372032498ea /src | |
| parent | b87d3447fd0e1d863eefe5bf1568306068737bf3 (diff) | |
| download | rabbitmq-server-git-1bc340d81faff82d4b415e34f20bc7990390e995.tar.gz | |
Fix O(n^2) time to ack / requeue multiple messages.
orddict:append/2 uses ++ internally to build the list in the correct
order, which is O(length). So it's O(n^2) to call it n times. Instead
let's build the list backwards then reverse it - O(n).
Diffstat (limited to 'src')
| -rw-r--r-- | src/rabbit_priority_queue.erl | 6 |
1 files changed, 4 insertions, 2 deletions
diff --git a/src/rabbit_priority_queue.erl b/src/rabbit_priority_queue.erl index 9ad5493a88..1d9522f613 100644 --- a/src/rabbit_priority_queue.erl +++ b/src/rabbit_priority_queue.erl @@ -547,9 +547,11 @@ add_maybe_infinity(A, B) -> A + B. partition_acktags(AckTags) -> partition_acktags(AckTags, orddict:new()). partition_acktags([], Partitioned) -> - Partitioned; + orddict:map(fun (_P, RevAckTags) -> + lists:reverse(RevAckTags) + end, Partitioned); partition_acktags([{P, AckTag} | Rest], Partitioned) -> - partition_acktags(Rest, orddict:append(P, AckTag, Partitioned)). + partition_acktags(Rest, rabbit_misc:orddict_cons(P, AckTag, Partitioned)). priority_on_acktags(P, AckTags) -> [case Tag of |