#11115: Rewrite cached_method in Cython
---------------------------+------------------------------------------------
Reporter: SimonKing | Owner: jason
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-4.7
Component: misc | Keywords: category cython cache
Work_issues: | Upstream: N/A
Reviewer: | Author: Simon King
Merged: | Dependencies:
---------------------------+------------------------------------------------
Comment(by nbruin):
Just to make sure that the CPU cache effect is real, I tried a little
example
{{{
%cython
cpdef test(int nelts,int spacing,int repetitions):
cdef int i,j,r
cdef int *L
cdef int k
L=<int*>malloc(sizeof(int)*nelts*spacing)
for r in xrange(repetitions):
k=0
for j in xrange(nelts):
L[k]=L[k]+1
k += spacing
free(L)
}}}
The following program times incrementing memory cells {{{2^30}}} times,
while varying the number of cells (nelts) and their spacing in memory
(spacing).
{{{
for j in xrange(0,9):
for i in xrange(1,29-j):
tstart=os.times()[0]
test(2**i,2**j,2**(30-i))
tstop=os.times()[0]
print [i,j,30-i,tstop-tstart]
}}}
The results are striking. Execution times vary by more than a factor 20
and one can see very definite thresholds where the execution time jumps.
An excerpt from the output:
{{{
[1, 0, 29, 1.8100000000000001]
[2, 0, 28, 1.5999999999999996]
[3, 0, 27, 1.4800000000000004]
[4, 0, 26, 1.7299999999999995]
[5, 0, 25, 1.5400000000000009]
[6, 0, 24, 1.4599999999999991]
[7, 0, 23, 1.4100000000000001]
[8, 0, 22, 1.3800000000000008]
[9, 0, 21, 1.3699999999999992]
...
[16, 0, 14, 1.3399999999999999]
[17, 0, 13, 1.3399999999999999]
[18, 0, 12, 2.1700000000000017]
[19, 0, 11, 2.6799999999999997]
[20, 0, 10, 2.7299999999999969]
[21, 0, 9, 2.740000000000002]
...
[28, 0, 2, 2.8500000000000014]
[9, 1, 21, 1.3599999999999994]
...
[16, 1, 14, 1.3499999999999943]
[17, 1, 13, 2.9500000000000028]
[18, 1, 12, 5.1700000000000017]
[19, 1, 11, 5.2199999999999989]
[12, 2, 18, 1.3599999999999852]
[13, 2, 17, 1.539999999999992]
[14, 2, 16, 1.5500000000000114]
[15, 2, 15, 1.539999999999992]
[16, 2, 14, 4.8200000000000216]
[17, 2, 13, 9.2099999999999795]
[11, 3, 19, 1.3500000000000227]
[12, 3, 18, 3.2199999999999704]
[13, 3, 17, 3.2200000000000273]
[14, 3, 16, 3.2199999999999704]
[15, 3, 15, 8.7700000000000387]
[16, 3, 14, 17.019999999999982]
[10, 4, 20, 1.3700000000000045]
[11, 4, 19, 6.1399999999999864]
[12, 4, 18, 6.1400000000000432]
[13, 4, 17, 6.1499999999999773]
[14, 4, 16, 15.779999999999973]
[15, 4, 15, 32.220000000000027]
[16, 4, 14, 33.379999999999995]
[17, 4, 13, 33.879999999999995]
[18, 4, 12, 34.210000000000036]
[19, 4, 11, 34.439999999999941]
[9, 5, 21, 1.3799999999999955]
[10, 5, 20, 5.1399999999999864]
[11, 5, 19, 5.1599999999999682]
[12, 5, 18, 5.0099999999999909]
[13, 5, 17, 14.540000000000077]
[14, 5, 16, 31.549999999999955]
[15, 5, 15, 32.299999999999955]
[7, 6, 23, 1.3999999999998636]
[8, 6, 22, 1.4100000000000819]
[9, 6, 21, 5.3800000000001091]
[10, 6, 20, 5.3899999999998727]
[11, 6, 19, 5.3900000000001]
[12, 6, 18, 14.480000000000018]
[13, 6, 17, 31.399999999999864]
[6, 7, 24, 1.4399999999998272]
[7, 7, 23, 1.4800000000000182]
[8, 7, 22, 5.4300000000000637]
[9, 7, 21, 5.4100000000000819]
[10, 7, 20, 5.3999999999998636]
[11, 7, 19, 14.960000000000036]
[12, 7, 18, 31.470000000000027]
[13, 7, 17, 33.029999999999973]
[14, 7, 16, 33.600000000000136]
[5, 8, 25, 1.5399999999999636]
[6, 8, 24, 1.6100000000001273]
[7, 8, 23, 6.0899999999999181]
[8, 8, 22, 5.8699999999998909]
[9, 8, 21, 5.7300000000000182]
[10, 8, 20, 22.1700000000003]
[11, 8, 19, 41.649999999999636]
[12, 8, 18, 64.5300000000002]
[13, 8, 17, 69.190000000000055]
[14, 8, 16, 73.199999999999818]
[15, 8, 15, 74.820000000000164]
[16, 8, 14, 69.440000000000055]
[17, 8, 13, 69.579999999999927]
[18, 8, 12, 70.349999999999909]
[19, 8, 11, 69.730000000000018]
[20, 8, 10, 77.869999999999891]
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11115#comment:35>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
