Reference documentation for deal.II version 8.1.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Modules Pages
Public Member Functions | Public Attributes | Static Private Attributes | List of all members
CompressedSparsityPattern::Line Struct Reference

Public Member Functions

 Line ()
 
void add (const size_type 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< size_typeentries
 
size_type cache [cache_size]
 
unsigned int cache_entries
 

Static Private Attributes

static const unsigned int cache_size = 8
 

Detailed Description

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.

Definition at line 423 of file compressed_sparsity_pattern.h.

Constructor & Destructor Documentation

CompressedSparsityPattern::Line::Line ( )
inline

Constructor.

Definition at line 561 of file compressed_sparsity_pattern.h.

Member Function Documentation

void CompressedSparsityPattern::Line::add ( const size_type  col_num)
inline

Add the given column number to this line.

Definition at line 493 of file compressed_sparsity_pattern.h.

template<typename ForwardIterator >
void CompressedSparsityPattern::Line::add_entries ( ForwardIterator  begin,
ForwardIterator  end,
const bool  indices_are_sorted 
)

Add the columns specified by the iterator range to this line.

void CompressedSparsityPattern::Line::flush_cache ( ) const

Flush the cache my merging it with the entries array.

Member Data Documentation

const unsigned int CompressedSparsityPattern::Line::cache_size = 8
staticprivate

Size of the cache.

Definition at line 429 of file compressed_sparsity_pattern.h.

std::vector<size_type> 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.

Definition at line 438 of file compressed_sparsity_pattern.h.

size_type CompressedSparsityPattern::Line::cache[cache_size]
mutable

Cache of entries that have not yet been written to entries;

Definition at line 444 of file compressed_sparsity_pattern.h.

unsigned int CompressedSparsityPattern::Line::cache_entries
mutable

Number of entries in the cache.

Definition at line 449 of file compressed_sparsity_pattern.h.


The documentation for this struct was generated from the following file: