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.

QpFloatType *	row (std::size_t k, std::size_t start, std::size_t end)
	Return a subset of a matrix row.

QpFloatType	operator() (std::size_t i, std::size_t j) const
	return a single matrix entry

QpFloatType	entry (std::size_t i, std::size_t j) const
	return a single matrix entry

void	flipColumnsAndRows (std::size_t i, std::size_t j)
	Swap the rows i and j and the columns i and j.

std::size_t	size () const
	return the size of the quadratic matrix

std::size_t	getMaxCacheSize () const
	return the size of the kernel cache (in "number of QpFloatType-s")

std::size_t	getCacheSize () const
	get currently used size of kernel cache (in "number of QpFloatType-s")

std::size_t	getCacheRowSize (std::size_t k) const
	get length of one specific currently cached row

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.

void	clear ()
	completely clear/purge the kernel cache

Protected Attributes
Matrix *	mep_baseMatrix
	matrix to be cached

LRUCache< QpFloatType >	m_cache
	cache of the matrix lines

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

base	Matrix to cache
cachesize	Main 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

i	first row/column index
j	second 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(), 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

Definition at line 268 of file CachedMatrix.h.

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

◆ 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 >

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

k	matrix row
start	first column to be filled in
end	last 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.

◆ row() [2/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

k	the index of the row
start	the index of the first element in the range
end	the index of the last element in the range
storage	the 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.

◆ 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

return the size of the quadratic matrix

Definition at line 253 of file CachedMatrix.h.

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

Referenced by shark::CachedMatrix< Matrix >::flipColumnsAndRows(), shark::CachedMatrix< Matrix >::row(), and shark::CachedMatrix< Matrix >::setMaxCachedIndex().

Member Data Documentation

◆ m_cache

template<class Matrix >

LRUCache<QpFloatType> shark::CachedMatrix< Matrix >::m_cache

protected

cache of the matrix lines

Definition at line 293 of file CachedMatrix.h.

Referenced by shark::CachedMatrix< Matrix >::clear(), shark::CachedMatrix< Matrix >::flipColumnsAndRows(), shark::CachedMatrix< Matrix >::getCacheRowSize(), shark::CachedMatrix< Matrix >::getCacheSize(), shark::CachedMatrix< Matrix >::getMaxCacheSize(), shark::CachedMatrix< Matrix >::isCached(), shark::CachedMatrix< Matrix >::row(), shark::CachedMatrix< Matrix >::row(), and shark::CachedMatrix< Matrix >::setMaxCachedIndex().

◆ mep_baseMatrix

template<class Matrix >

Matrix* shark::CachedMatrix< Matrix >::mep_baseMatrix

protected

matrix to be cached

Definition at line 291 of file CachedMatrix.h.

Referenced by shark::CachedMatrix< Matrix >::entry(), shark::CachedMatrix< Matrix >::flipColumnsAndRows(), shark::CachedMatrix< Matrix >::row(), shark::CachedMatrix< Matrix >::row(), and shark::CachedMatrix< Matrix >::size().

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

include/shark/LinAlg/CachedMatrix.h

Public Types

Public Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ QpFloatType

Constructor & Destructor Documentation

◆ CachedMatrix()

Member Function Documentation

◆ clear()

◆ entry()

◆ flipColumnsAndRows()

◆ getCacheRowSize()

◆ getCacheSize()

◆ getMaxCacheSize()

◆ isCached()

◆ operator()()

◆ row() [1/2]

◆ row() [2/2]

◆ setMaxCachedIndex()

◆ size()

Member Data Documentation

◆ m_cache

◆ mep_baseMatrix