I figured out why 8 tables is optimal on this machine. The L1 cache is 128kb and at 2048x2048, 8 Gray tables with k = 5 fits exactly in half the cache, which is probably optimal.
Bill. On 19 May, 02:00, Martin Albrecht <[EMAIL PROTECTED]> wrote: > On Monday 19 May 2008, Bill Hart wrote: > > > > > Well, apparently there are speed gains right up to 8 Gray tables, > > though I really have no idea why that is. > > > Here are the new times: > > > Magma Old New > > > 10000x10000: > > 2.940s 3.13s 2.32s > > > 16384x16384: > > 9.250s 12.96s 9.17s > > > 20000x20000: > > 16.57s 22.43s 16.49s > > > 32000x32000: > > 59.1s 90.2s 81.6s 65.7s > > > So now we beat Magma all the way up to 20000x20000. > > > I'll put the adjusted code in the directory: > > >http://sage.math.washington.edu/home/wbhart/m4ri3gray/ > > > in just a moment. I also found a memory leak in my code which I fixed. > > > Bill. > > Cool, I'll take a look tomorrow. It seems we're closing in on the classical > algorithm though. Although, you don't seem to decrease k anymore. > > As for the copying and 2^14 vs. 10^4: Maybe the extra rows/columns cost too > many cycles. I'll try valgrind/callgrind/cachegrind on the code to see if > that is true. Also maybe for 2^14 x 2^14 the submatrices are nicely aligned > on cache lines. I'm widely speculating here. > > Martin > > -- > name: Martin Albrecht > _pgp:http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99 > _www:http://www.informatik.uni-bremen.de/~malb > _jab: [EMAIL PROTECTED] --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
