Michael It may be useful to split your computation in L2-sized chunks. I.e. if you want to sum over all quadratic forms with |d| < X, instead of doing the computation for the whole interval, split the interval in smaller pieces. But not too small, since the innermost loop would be too small/empty.
In general, I would expect that pieces of size O(sqrt(X)) would be close to optimal, since this balances the memory usage of each computation with a nontrivial innermost loop so the overhead from the second innermost loop is not important. With today's L2-caches you may be able to use 10^5 or 10^6 chunks, which may be around optimal (just try different sizes of intervals around X to see which size gives you better throughput overall). In addition, doing things this way makes it easy to parallelize. Of course, my intuition is more about *definite* ternary quadratic forms, but something similar may be useful. BTW, there's the trick of iterating over forms with even b in one computation and odd b in another computation, which reduces the size of your intervals by a factor of 4, but you're probably using this one already. Gonzalo On Sat, May 16, 2009 at 7:08 PM, Michael <[email protected]> wrote: > > I have a very naive question. I am playing around with binary > quadratic forms and have a large array of values. I loop through a,b,c > and, for each triple, compute some quantity that depends on a,b,c. > Then, in the inner most c loop, I wish to increment value[d], where > d=4ac-b^2, by that quantity. > > I am finding that the step > > value[d]+= quantity; > > is taking way too long, presumably because, as c increments by 1, > d=4ac-b^2, increments by a large amount, 4a, so the way that the array > is read into the cache in chunks of consecutive array entries, is > useless here. > > Is there a way in c or c++ to control what parts of an array get read > into cache. For example can > I ***efficiently*** read/manipulate equally spaced entries (spaced > apart by 4a) of my value array into cache rather than the default > consecutive entries. > > Any tips would be greatly appreciated. > > > > > --~--~---------~--~----~------------~-------~--~----~ 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-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
