quantopian/zipline — pull request #111 by wesm (2013-03-22 01:50:39+00:00)
Title: ENH: use array and pandas operations to speed up risk computations

A few changes to start a conversation about performance in the performance and risk analytics in zipline.

I started with the pair trading example. Here's on `master` before the PR:

```
In [2]: %time results = pairtrade.run(data)
[2013-03-22 01:35] INFO: Performance: Simulated 2268 trading days out of 2268.
[2013-03-22 01:35] INFO: Performance: first open: 1993-01-04 14:30:00+00:00
[2013-03-22 01:35] INFO: Performance: last close: 2001-12-31 21:00:00+00:00
CPU times: user 30.32 s, sys: 0.14 s, total: 30.46 s
Wall time: 30.52 s
```

and after

```
In [2]: %time results = pairtrade.run(data)
[2013-03-22 01:33] INFO: Performance: Simulated 2268 trading days out of 2268.
[2013-03-22 01:33] INFO: Performance: first open: 1993-01-04 14:30:00+00:00
[2013-03-22 01:33] INFO: Performance: last close: 2001-12-31 21:00:00+00:00
CPU times: user 22.03 s, sys: 0.21 s, total: 22.23 s
Wall time: 22.24 s
```

Here's what the cProfile summary looks like right now:

```
7556356 function calls (7433722 primitive calls) in 26.211 seconds

Ordered by: cumulative time

ncalls tottime percall cumtime percall filename:lineno(function)
1 0.013 0.013 26.211 26.211 :1()
1 0.002 0.002 26.199 26.199 algorithm.py:156(run)
2270 0.002 0.000 25.646 0.011 tradesimulation.py:108(simulate)
2270 0.037 0.000 25.644 0.011 tradesimulation.py:233(transform)
1 0.000 0.000 11.634 11.634 performance.py:329(handle_simulation_end)
1 0.000 0.000 11.603 11.603 risk.py:680(__init__)
4 0.016 0.004 11.603 2.901 risk.py:726(periods_in_range)
414 1.809 0.004 11.582 0.028 risk.py:99(__init__)
2269 0.017 0.000 9.761 0.004 performance.py:203(transform)
4536 0.099 0.000 8.986 0.002 performance.py:239(process_event)
2268 0.040 0.000 8.755 0.004 performance.py:277(handle_market_close)
828 2.252 0.003 8.292 0.010 risk.py:208(calculate_period_returns)
2268 0.077 0.000 8.039 0.004 risk.py:466(update)
4536 4.282 0.001 4.282 0.001 risk.py:594(calculate_period_returns)
2268 0.007 0.000 4.173 0.002 tradesimulation.py:305(simulate_snapshot)
2268 0.016 0.000 4.161 0.002 :66(handle_data)
2268 0.115 0.000 3.836 0.002 utils.py:406(handle_data)
872 2.343 0.003 2.828 0.003 index.py:569(isin)
123316/123294 2.690 0.000 2.691 0.000 {numpy.core.multiarray.array}
2268 0.016 0.000 2.514 0.001 utils.py:554(get_transform_value)
22 0.001 0.000 2.393 0.109 utils.py:505(get_data)
66 0.000 0.000 2.365 0.036 panel.py:217(__init__)
66 0.003 0.000 2.364 0.036 panel.py:240(_init_data)
44 0.041 0.001 2.361 0.054 panel.py:274(_init_dict)
2553/2552 0.045 0.000 1.864 0.001 index.py:146(__new__)
3773 0.054 0.000 1.859 0.000 series.py:390(__new__)
15126 0.166 0.000 1.554 0.000 index.py:88(__new__)
6755 0.029 0.000 1.509 0.000 frame.py:347(__init__)
56823 0.046 0.000 1.507 0.000 index.py:2610(_ensure_index)
2682 0.045 0.000 1.392 0.001 risk.py:268(calculate_beta)
13317 0.073 0.000 1.243 0.000 fromnumeric.py:32(_wrapit)
2200 0.025 0.000 1.152 0.001 frame.py:476(_init_dict)
2682 0.051 0.000 1.125 0.000 risk.py:337(choose_treasury)
7532 0.045 0.000 1.120 0.000 fromnumeric.py:2377(std)
2223 0.018 0.000 1.073 0.000 frame.py:5381(_arrays_to_mgr)
2268 0.028 0.000 1.060 0.000 utils.py:225(update)
86006/85984 0.085 0.000 1.048 0.000 numeric.py:167(asarray)
286 0.299 0.001 1.026 0.004 collections.py:103(keys)
5364 0.031 0.000 1.010 0.000 risk.py:223(calculate_volatility)
828 0.008 0.000 1.007 0.001 index.py:1264(normalize)
896 0.016 0.000 0.995 0.001 tools.py:51(to_datetime)
896 0.013 0.000 0.975 0.001 tools.py:72(_convert_f)
2288 0.011 0.000 0.890 0.000 frame.py:2527(reindex)
895 0.867 0.001 0.877 0.001 {pandas.tslib.datetime_to_datetime64}
2703 0.011 0.000 0.870 0.000 shape_base.py:177(vstack)
```

To start making more progress on improving performance, several things probably should start happening:

1) Most of the risk and performance analytics need to get moved to Cython. Internal functions not exposed to end users should all be cdef'd

2) Time stamps should probably all be represented as `int64` values corresponding to the equivalent `datetime64` format used in pandas. You can find loads of support code for converting back and forth in `pandas/tslib.pyx` and supporting C files. This really isn't as awful as it sounds-- a few helper functions internally and you're in business.

3) No more lists for accumulating results. You should just adapt the approach that I use in `pandas/hashtable.pyx` of a simple Cython vector class which works very similarly to a C++ STL vector (doubles the size whenever it exceeds the length). Here is what one looks like:

```
cdef class Float64Vector:

cdef:
size_t n, m
ndarray ao
float64_t *data

def __cinit__(self):
self.n = 0
self.m = _INIT_VEC_CAP
self.ao = np.empty(_INIT_VEC_CAP, dtype=np.float64)
self.data = self.ao.data

def __len__(self):
return self.n

def to_array(self):
self.ao.resize(self.n)
return self.ao

cdef inline append(self, float64_t x):
if self.n == self.m:
self.m = self.m * 2
self.ao.resize(self.m)
self.data = self.ao.data

self.data[self.n] = x
self.n += 1
```

I would recommend adding an alternate method to `to_array` that does not resize the array and simply returns a view up through the last appended element (just use python slicing. you can also use `PyArray_SimpleNewFromData`).

4) The risk module should be refactored as the iterative risk report approach is very slow-- object construction and general Python interpreter overhead is dogging you bad, especially this method:

```
def periods_in_range(self, months_per, start, end):
one_day = datetime.timedelta(days=1)
ends = []
cur_start = start.replace(day=1)

# in edge cases (all sids filtered out, start/end are adjacent)
# a test will not generate any returns data
if len(self.algorithm_returns) == 0:
return ends

#ensure that we have an end at the end of a calendar month, in case
#the return series ends mid-month...
the_end = advance_by_months(end.replace(day=1), 1) - one_day
while True:
cur_end = advance_by_months(cur_start, months_per) - one_day
if(cur_end > the_end):
break
cur_period_metrics = RiskMetricsBatch(
start_date=cur_start,
end_date=cur_end,
returns=self.algorithm_returns
)

ends.append(cur_period_metrics)
cur_start = advance_by_months(cur_start, 1)

return ends
```

Anyway, general conclusion: more NumPy, more vectorization, more Cython, fewer object instantiations, fewer `datetime.datetime` objects. Since a lot of these things are internal implementation details