larsmans/seqlearn — pull request #6 by kmike (2013-08-07 16:04:49+00:00)
Title: rewrite _utils.count_trans in Cython

Some profiling results for StructuredPerceptron.fit (using a sparse X with 70k samples/60k features, y with 20 labels, before this PR):

```
228411 function calls (227111 primitive calls) in 29.378 seconds

Ordered by: internal time

ncalls tottime percall cumtime percall filename:lineno(function)
2442 15.957 0.007 15.976 0.007 _utils.py:10(count_trans)
1 8.533 8.533 29.373 29.373 perceptron.py:51(fit)
4967 2.242 0.000 2.242 0.000 {numpy.core.multiarray.zeros}
1300 0.755 0.001 0.755 0.001 {seqlearn._decode.viterbi.viterbi}
1300 0.485 0.000 0.485 0.000 {_csr.csr_matvecs}
1221 0.430 0.000 0.430 0.000 {_csc.csc_matvecs}
1300 0.175 0.000 0.175 0.000 {_csr.get_csr_submatrix}
2521 0.114 0.000 0.226 0.000 compressed.py:103(check_format)
2521 0.076 0.000 3.505 0.001 extmath.py:70(safe_sparse_dot)
2521 0.068 0.000 0.078 0.000 compressed.py:633(prune)
2521 0.048 0.000 3.212 0.001 compressed.py:272(_mul_multivector)
2521 0.043 0.000 0.322 0.000 compressed.py:22(__init__)
3900 0.035 0.000 0.047 0.000 sputils.py:95(isintlike)
```

Rewriting count_trans to Cython could give us 2x speedup in some scenarios (the same data, after this PR):

```
230905 function calls (229605 primitive calls) in 13.748 seconds

Ordered by: internal time

ncalls tottime percall cumtime percall filename:lineno(function)
1 8.778 8.778 13.745 13.745 perceptron.py:51(fit)
2525 2.264 0.001 2.264 0.001 {numpy.core.multiarray.zeros}
1300 0.793 0.001 0.793 0.001 {seqlearn._decode.viterbi.viterbi}
1300 0.504 0.000 0.504 0.000 {_csr.csr_matvecs}
1221 0.445 0.000 0.445 0.000 {_csc.csc_matvecs}
2521 0.115 0.000 0.233 0.000 compressed.py:103(check_format)
1300 0.086 0.000 0.086 0.000 {_csr.get_csr_submatrix}
2521 0.080 0.000 3.596 0.001 extmath.py:70(safe_sparse_dot)
2521 0.072 0.000 0.082 0.000 compressed.py:633(prune)
2521 0.049 0.000 3.291 0.001 compressed.py:272(_mul_multivector)
2521 0.043 0.000 0.331 0.000 compressed.py:22(__init__)
17569 0.042 0.000 0.042 0.000 {numpy.core.multiarray.array}
3900 0.036 0.000 0.047 0.000 sputils.py:95(isintlike)
2600/1300 0.032 0.000 0.416 0.000 csr.py:189(__getitem__)
2442 0.030 0.000 0.030 0.000 {seqlearn._utils_cython.count_trans}
```

I'm not sure the code is organized in a good way (_utils_cython.pyx), but anyways.