Is it a good idea to use vector> to form a matrix class for high performance scientific computing code?
If the answer is no. Why? Thanks
It's a bad idea because vector needs to allocate as many objects in space as there are rows in your matrix. Allocation is expensive, but primarily it is a bad idea because the data of your matrix now exists in a number of arrays scattered around memory, rather than all in one place where the processor cache can easily access it.
It's also a wasteful storage format: std::vector stores two pointers, one to the beginning of the array and one to the end because the length of the array is flexible. On the other hand, for this to be a proper matrix, the lengths of all rows must be the same and so it would be sufficient to store the number of columns only once, rather than letting each row store its length independently.
No, use one of the free available linear algebra libraries. A discussion about different libraries can be found here: Recommendations for a usable, fast C++ matrix library?
In addition to the reasons Wolfgang mentioned, if you use a
Is it really such a bad thing?
@Wolfgang: Depending on the size of the dense matrix, two additional pointer per row might be negligable. Concerning scattered data one could think of using a custom allocator that makes sure that the vectors are in contiguous memory. As long as memory is not recycled even the standard allocator will us contiguous memory with a two pointer size gap.
@Geoff: If you are doing random access and use just one array you still have to calculate the index. Might not be faster.
So let us do a small test:
And now using one array:
On my system there is now clear winner (Compiler gcc 4.7 with -O3)
time vectormatrix prints:
We also see, that as long as the standard allocator does not recycle freed memory, the data is contiguous. (Of course after some deallocations there is no guarantee for this.)
time arraymatrix prints: