graphite-project/carbon — pull request #228 by pbberlin (2014-03-12 13:25:52+00:00)
Title: Optimized intersection of rollup job

Some metrics / nodes took > 15 minutes for processing.

There were over hundred thousand iterations over range(coarseArchive['retention']).

Each iteration looped the entire list of overflowDatapoints - containing thousands of entries.

Intention is to find intersections in time intervals.

I added a primitive optimization:
I compute the timestamp boundaries of overflowDatapoints before the big loop.
Then I check the boundaries for intersection before overflowDatapoints is iterated.

Now we can process ~3 nodes per Second.