Re: [ublas] matrix row/column iterate

Subject: Re: [ublas] matrix row/column iterate
From: Nasos Iliopoulos (nasos_i_at_[hidden])
Date: 2010-07-09 08:31:05

Phillipp,

1. If your question refers to whether you should use iterators, or indexing, it is mostly a matter of taste. The indexing operation i*size_j+j, compiles to only one operation (multiply-add) in any sensible compiler so there is no penalty from using it. In any case for algebraic legacy reasons I prefer indexing over iterators, although iterators may give you better generality and some cleaner assembly code (if you care about that). I think that some tests in the past indicated that indexing was in fact faster than iterators, but I can't justify it atm.

2. If you refer to the trasversing order:
If your matrix is row_major (default), then the inner loop should be over the columns (i.e. the second index). That is because when the loop is executed, data is transfered in blocks from the main memory to the CPU's local cache and since you have a block there, you want to do all the possible operations on it before you are done with it (and it is send back to the main memory). Now if the matrix is small enough to fit in the cache (say up to 2MB in practice), this will not be a problem.

If you don't do that, you may end transfering big blocks to the local memory, to operate only on a few elements, and then do that again to grub the rest of them, a huge waste of resources.

See for example:
http://en.wikipedia.org/wiki/Locality_of_reference
http://blogs.microsoft.co.il/blogs/pavely/archive/2009/06/22/cache-locality-for-performance.aspx

As a matter of fact there are a few cache locality optimizations that can be done in ublas (provided also that we have a better traits system). 

3. You may want to use ublas' proxies, that are light weight and avoid copying the elements:
http://www.boost.org/doc/libs/1_43_0/libs/numeric/ublas/doc/matrix_proxy.htm#matrix_row

Best
Nasos

> From: philipp.kraus_at_[hidden]
> To: ublas_at_[hidden]
> Date: Fri, 9 Jul 2010 12:26:56 +0200
> Subject: [ublas] matrix row/column iterate
> 
> Hello,
> 
> I must iterator over a ublas::matrix along rows or columns, but the  
> matrix are very large and not sparse.
> Which way is the fastest to iterate along the rows and columns with  
> extract the row / column vector?
> 
> Thanks
> 
> Phil
> _______________________________________________
> ublas mailing list
> ublas_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/ublas
> Sent to: nasos_i_at_[hidden]
                                               
_________________________________________________________________
Hotmail has tools for the New Busy. Search, chat and e-mail from your inbox.
http://www.windowslive.com/campaign/thenewbusy?ocid=PID28326::T:WLMTAGL:ON:WL:en-US:WM_HMP:042010_1