celery/celery — pull request #1587 by nott (2013-10-22 10:19:48+00:00)
Title: Improve performance of ResultSet.join_native

I've been testing chords with lots of tasks (10K and more) inside recently, using RabbitMQ as a broker and Redis as a backend.

It works fine, but there is one bottleneck: ResultSet.join_native
Current ResultSet.join_native implementation
```
def join_native(self, timeout=None, propagate=True,
interval=0.5, callback=None):
results = self.results
acc = None if callback else [None for _ in range(len(self))]
for task_id, meta in self.iter_native(timeout, interval):
value = meta['result']
if propagate and meta['status'] in states.PROPAGATE_STATES:
raise value
if callback:
callback(task_id, value)
else:
acc[results.index(task_id)] = value
return acc
```
In essential it's:
```
results = self.results
acc = None if callback else [None for _ in range(len(self))]
for task_id, meta in self.iter_native(timeout, interval):
acc[results.index(task_id)] = value
return acc
```

results and acc are lists with corresponding items at the same positions.
The problem is the call to results.index, which is slow (we have O(n**2) here).
We can have O(n log(n)) here using dict as a reverse index

Some tests for the proposed approach:
```
from datetime import datetime
import random
import uuid

def old_func(results, shuffled):
acc = [None for _ in range(len(results))]
for task_id in shuffled:
acc[results.index(task_id)] = task_id
return acc

def new_func(results, shuffled):
results_index = dict((task_id, i) for i, task_id in enumerate(results))
acc = [None for _ in range(len(results))]
for task_id in shuffled:
acc[results_index[task_id]] = task_id
return acc

def timeme(n):
print '\n', n
results = [uuid.uuid4() for _ in xrange(n)]
shuffled = results[:]
random.shuffle(shuffled)

print 'old'
print datetime.now()
old_res = old_func(results, shuffled)
print datetime.now()

print 'new'
print datetime.now()
new_res = new_func(results, shuffled)
print datetime.now()

assert new_res == old_res

timeme(1000)
timeme(10000)
timeme(20000)
```
it produces:
```
1000
old
2013-10-22 12:40:53.281995
2013-10-22 12:40:54.306828
new
2013-10-22 12:40:54.307054
2013-10-22 12:40:54.310805

10000
old
2013-10-22 12:40:55.287551
2013-10-22 12:42:40.444442
new
2013-10-22 12:42:40.444692
2013-10-22 12:42:40.487685

20000
old
2013-10-22 12:42:42.506325
2013-10-22 12:49:32.609796
new
2013-10-22 12:49:32.609983
2013-10-22 12:49:32.703904
```

The only side effect is Exception type if something goes wrong (KeyError for dict instead of ValueError for results.index), but it must be fine.

Sorry for lots of text :)