shark::CachedMatrix< Matrix > Class Template Reference

Efficient quadratic matrix cache. More...

#include <shark/LinAlg/CachedMatrix.h>

Public Types

typedef Matrix::QpFloatType QpFloatType
 

Public Member Functions

 CachedMatrix (Matrix *base, std::size_t cachesize=0x4000000)
 
void row (std::size_t k, std::size_t start, std::size_t end, QpFloatType *storage) const
 Copies the range [start,end) of the k-th row of the matrix in external storage. More...
 
QpFloatTyperow (std::size_t k, std::size_t start, std::size_t end)
 Return a subset of a matrix row. More...
 
QpFloatType operator() (std::size_t i, std::size_t j) const
 return a single matrix entry More...
 
QpFloatType entry (std::size_t i, std::size_t j) const
 return a single matrix entry More...
 
void flipColumnsAndRows (std::size_t i, std::size_t j)
 Swap the rows i and j and the columns i and j. More...
 
std::size_t size () const
 return the size of the quadratic matrix More...
 
std::size_t getMaxCacheSize () const
 return the size of the kernel cache (in "number of QpFloatType-s") More...
 
std::size_t getCacheSize () const
 get currently used size of kernel cache (in "number of QpFloatType-s") More...
 
std::size_t getCacheRowSize (std::size_t k) const
 get length of one specific currently cached row More...
 
bool isCached (std::size_t k) const
 
void setMaxCachedIndex (std::size_t n)
 Restrict the cached part of the matrix to the upper left nxn sub-matrix. More...
 
void clear ()
 completely clear/purge the kernel cache More...
 

Protected Attributes

Matrix * mep_baseMatrix
 matrix to be cached More...
 
LRUCache< QpFloatTypem_cache
 cache of the matrix lines More...
 

Detailed Description

template<class Matrix>
class shark::CachedMatrix< Matrix >

Efficient quadratic matrix cache.

The access operations of the CachedMatrix class are specially tuned towards the iterative solution of quadratic programs resulting in sparse solutions.
The kernel cache is probably one of the most intricate or mind-twisting parts of Shark. In order to fully understand it, reading the source code is essential and this description naturally not sufficient. However, the general ideas are as follows:
A CachedMatrix owns a pointer to a regular (non-cached) kernel matrix, the exact type of which is a template parameter. Through it, the actions of requesting an entry and propagating column-/row-flips are carried out. Even though a CachedMatrix offers some methods also offered by the general KernelMatrix, note that it does not inherit from it in order to offer greater flexibility.
The CachedMatrix defines a struct tCacheEntry, which represents one row of varying length of a stored kernel matrix. The structure aggregates a pointer to the kernel values (stored as values of type CacheType); the number of stored values; and the indices of the next older and newer cache entries. The latter two indices pertain to the fact that the CachedMatrix maintains two different "orders" of the examples: one related to location in memory, and the other related to last usage time, see below. During the lifetime of a CachedMatrix, it will hold a vector of the length of the number of examples of tCacheEntry: one entry for each example. When an example has no kernel values in the cache, its tCacheEntry.length will be 0, its tCacheEntry.data will be NULL, and its older and newer variables will be SHARK_CACHEDMATRIX_NULL_REFERENCE. Otherwise, the entries take their corresponding meaningful values. In particular for tCacheEntry.data, memory is dynamically allocated via malloc, reallocated via realloc, and freed via free as fit.
A basic operation the CachedMatrix must support is throwing away old stored values to make room for new values, because it is very common that not all values fit into memory (otherwise, consider the PrecomputedMatrix class). When a new row is requested via row(..), but no room to store it, row(..) has two options for making space:
First option: first, the row method checks if the member index m_truncationColumnIndex is lower than the overall number of examples. If so, it goes through all existing rows and shortens them to a length of m_truncationColumnIndex. Through this shortening, memory becomes available. In other words, m_truncationColumnIndex can be used to indicate to the CachedMatrix that every row longer than m_truncationColumnIndex can be clipped at the end. By default, m_truncationColumnIndex is equal to the number of examples and not changed by the CachedMatrix, so no clipping will occur if the CachedMatrix is left to its own devices. However, m_truncationColumnIndex can be set from externally via setTruncationIndex(..) [this might be done after a shrinking event, for example]. Now imagine a situation where the cache is full, and the possibility exists to free some memory by truncating longer cache rows to length m_truncationColumnIndex. As soon as enough rows have been clipped for a new row to fit in, the CachedMatrix computes the new row and passes back control. Most likely, the next time a new, uncached row is requested, more rows will have to get clipped. In order not to start checking if rows can be clipped from the very first row over again, the member variable m_truncationRowIndex internally stores where the chopping-procedure left off the last time. When a new row is requested and it's time to clear out old entries, it will start looking for choppable rows at this index to save time. In general, any chopping would happen via cacheResize(..) internally.
Second option: if all rows have been chopped of at the end, or if this has never been an option (due to all rows being shorter or equal to m_truncationColumnIndex anyways), entire rows will get discarded as the second option. This will probably be the more common case. In general, row deletions will happen via cacheDelete(..) internally. The CachedMatrix itself only resorts to a very simple heuristic in order to determine which rows to throw away to make room for new ones. Namely, the CachedMatrix keeps track of the "age" or "oldness" of all cached rows. This happens via the so-to-speak factually doubly-linked list of indices in the tCacheEntry.older/newer entries, plus two class members m_cacheNewest and m_cacheOldest, which point to the beginning and end of this list. When row(..) wants to delete a cached row, it always does so on the row with index m_cacheOldest, and this index is then set to the next oldest row. Likewise, whenever a new row is requested, m_cacheNewest is set to point to that one. In order to allow for smarter heuristics, external classes may intervene with the deletion order via the methods cacheRedeclareOldest and cacheRedeclareNewest, which move an example to be deleted next or as late as possible, respectively.
Two more drastic possibilites to influence the cache behaviour are cacheRowResize and cacheRowRelease, which both directly resize (e.g., chop off) cached row values or even discard the row altogether. In general however, it is preferred that the external application only indicate preferences for deletion, because it will usually not have information on the fullness of the cache (although this functionality could easily be added).

Definition at line 157 of file CachedMatrix.h.

Member Typedef Documentation

◆ QpFloatType

template<class Matrix>
typedef Matrix::QpFloatType shark::CachedMatrix< Matrix >::QpFloatType

Definition at line 160 of file CachedMatrix.h.

Constructor & Destructor Documentation

◆ CachedMatrix()

template<class Matrix>
shark::CachedMatrix< Matrix >::CachedMatrix ( Matrix *  base,
std::size_t  cachesize = 0x4000000 
)
inline

Constructor

Parameters
baseMatrix to cache
cachesizeMain memory to use as a kernel cache, in QpFloatTypes. Default is 256MB if QpFloatType is float, 512 if double.

Definition at line 165 of file CachedMatrix.h.

Member Function Documentation

◆ clear()

template<class Matrix>
void shark::CachedMatrix< Matrix >::clear ( )
inline

completely clear/purge the kernel cache

Definition at line 287 of file CachedMatrix.h.

References shark::LRUCache< T >::clear(), and shark::CachedMatrix< Matrix >::m_cache.

◆ entry()

template<class Matrix>
QpFloatType shark::CachedMatrix< Matrix >::entry ( std::size_t  i,
std::size_t  j 
) const
inline

return a single matrix entry

Definition at line 214 of file CachedMatrix.h.

References shark::CachedMatrix< Matrix >::mep_baseMatrix.

Referenced by shark::CachedMatrix< Matrix >::operator()().

◆ flipColumnsAndRows()

template<class Matrix>
void shark::CachedMatrix< Matrix >::flipColumnsAndRows ( std::size_t  i,
std::size_t  j 
)
inline

Swap the rows i and j and the columns i and j.

It may be advantageous for caching to reorganize the column order. In order to keep symmetric matrices symmetric the rows are swapped, too. This corresponds to swapping the corresponding variables.
Parameters
ifirst row/column index
jsecond row/column index

Definition at line 230 of file CachedMatrix.h.

References shark::LRUCache< T >::getLinePointer(), shark::LRUCache< T >::lineLength(), shark::CachedMatrix< Matrix >::m_cache, shark::CachedMatrix< Matrix >::mep_baseMatrix, shark::CachedMatrix< Matrix >::size(), shark::swap(), and shark::LRUCache< T >::swapLineIndices().

◆ getCacheRowSize()

template<class Matrix>
std::size_t shark::CachedMatrix< Matrix >::getCacheRowSize ( std::size_t  k) const
inline

get length of one specific currently cached row

Definition at line 265 of file CachedMatrix.h.

References shark::LRUCache< T >::lineLength(), and shark::CachedMatrix< Matrix >::m_cache.

◆ getCacheSize()

template<class Matrix>
std::size_t shark::CachedMatrix< Matrix >::getCacheSize ( ) const
inline

get currently used size of kernel cache (in "number of QpFloatType-s")

Definition at line 261 of file CachedMatrix.h.

References shark::CachedMatrix< Matrix >::m_cache, and shark::LRUCache< T >::size().

◆ getMaxCacheSize()

template<class Matrix>
std::size_t shark::CachedMatrix< Matrix >::getMaxCacheSize ( ) const
inline

return the size of the kernel cache (in "number of QpFloatType-s")

Definition at line 257 of file CachedMatrix.h.

References shark::CachedMatrix< Matrix >::m_cache, and shark::LRUCache< T >::maxSize().

◆ isCached()

template<class Matrix>
bool shark::CachedMatrix< Matrix >::isCached ( std::size_t  k) const
inline

◆ operator()()

template<class Matrix>
QpFloatType shark::CachedMatrix< Matrix >::operator() ( std::size_t  i,
std::size_t  j 
) const
inline

return a single matrix entry

Definition at line 209 of file CachedMatrix.h.

References shark::CachedMatrix< Matrix >::entry().

◆ row() [1/2]

template<class Matrix>
void shark::CachedMatrix< Matrix >::row ( std::size_t  k,
std::size_t  start,
std::size_t  end,
QpFloatType storage 
) const
inline

Copies the range [start,end) of the k-th row of the matrix in external storage.

This call regards the access to the line as out-of-order, thus the cache is not influenced.

Parameters
kthe index of the row
startthe index of the first element in the range
endthe index of the last element in the range
storagethe external storage. must be big enough capable to hold the range

Definition at line 175 of file CachedMatrix.h.

References shark::LRUCache< T >::getLinePointer(), shark::LRUCache< T >::lineLength(), shark::CachedMatrix< Matrix >::m_cache, shark::CachedMatrix< Matrix >::mep_baseMatrix, shark::CachedMatrix< Matrix >::size(), and SIZE_CHECK.

◆ row() [2/2]

template<class Matrix>
QpFloatType* shark::CachedMatrix< Matrix >::row ( std::size_t  k,
std::size_t  start,
std::size_t  end 
)
inline

Return a subset of a matrix row.

This method returns an array of QpFloatType with at least the entries in the interval [begin, end[ filled in.
Parameters
kmatrix row
startfirst column to be filled in
endlast column to be filled in +1

Definition at line 197 of file CachedMatrix.h.

References shark::LRUCache< T >::getCacheLine(), shark::LRUCache< T >::lineLength(), shark::CachedMatrix< Matrix >::m_cache, and shark::CachedMatrix< Matrix >::mep_baseMatrix.

◆ setMaxCachedIndex()

template<class Matrix>
void shark::CachedMatrix< Matrix >::setMaxCachedIndex ( std::size_t  n)
inline

Restrict the cached part of the matrix to the upper left nxn sub-matrix.

Definition at line 272 of file CachedMatrix.h.

References shark::CachedMatrix< Matrix >::m_cache, shark::LRUCache< T >::markLineForDeletion(), shark::CachedMatrix< Matrix >::size(), and SIZE_CHECK.

◆ size()

template<class Matrix>
std::size_t shark::CachedMatrix< Matrix >::size ( ) const
inline

Member Data Documentation

◆ m_cache

◆ mep_baseMatrix

template<class Matrix>
Matrix* shark::CachedMatrix< Matrix >::mep_baseMatrix
protected

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