Public Member Functions | |
Line () | |
void | add (const unsigned int col_num) |
template<typename ForwardIterator > | |
void | add_entries (ForwardIterator begin, ForwardIterator end, const bool indices_are_sorted) |
void | flush_cache () const |
Public Attributes | |
std::vector< unsigned int > | entries |
unsigned int | cache [cache_size] |
unsigned int | cache_entries |
Static Private Attributes | |
static const unsigned int | cache_size = 8 |
Store some data for each row describing which entries of this row are nonzero. Data is organized as follows: if an entry is added to a row, it is first added to the cache variable, irrespective of whether an entry with same column number has already been added. Only if the cache is full do we flush it by removing duplicates, removing entries that are already stored in the entries
array, sorting everything, and merging the two arrays.
The reasoning behind this scheme is that memory allocation is expensive, and we only want to do it when really necessary. Previously (in deal.II versions up to 5.0), we used to store the column indices inside a std::set, but this would allocate 20 bytes each time we added an entry. (A std::set based class has later been revived in form of the CompressedSetSparsityPattern class, as this turned out to be more efficient for hp finite element programs such as step-27). Using the present scheme, we only need to allocate memory once for every 8 added entries, and we waste a lot less memory by not using a balanced tree for storing column indices.
Since some functions that are const
need to access the data of this object, but need to flush caches before, the flush_cache() function is marked const, and the data members are marked mutable
.
A small testseries about the size of the cache showed that the run time of a small program just testing the compressed sparsity pattern element insertion routine ran for 3.6 seconds with a cache size of 8, and 4.2 seconds with a cache size of 16. We deem even smaller cache sizes undesirable, since they lead to more memory allocations, while larger cache sizes lead to waste of memory. The original version of this class, with one std::set per row took 8.2 seconds on the same program.
CompressedSparsityPattern::Line::Line | ( | ) | [inline] |
Constructor.
Add the given column number to this line.
References cache, cache_entries, cache_size, and flush_cache().
void CompressedSparsityPattern::Line::add_entries | ( | ForwardIterator | begin, | |
ForwardIterator | end, | |||
const bool | indices_are_sorted | |||
) | [inline] |
Add the columns specified by the iterator range to this line.
void CompressedSparsityPattern::Line::flush_cache | ( | ) | const |
const unsigned int CompressedSparsityPattern::Line::cache_size = 8 [static, private] |
Size of the cache.
Referenced by add().
std::vector<unsigned int> CompressedSparsityPattern::Line::entries [mutable] |
Storage for the column indices of this row, unless they are still in the cache. This array is always kept sorted.
Number of entries in the cache.
Referenced by add().