//===========================================================================
/*!
*
*
* \brief Efficient quadratic matrix cache
*
*
* \par
*
*
*
* \author T. Glasmachers
* \date 2007-2012
*
*
* \par Copyright 1995-2017 Shark Development Team
*
*
* This file is part of Shark.
*
*
* Shark is free software: you can redistribute it and/or modify
* it under the terms of the GNU Lesser General Public License as published
* by the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* Shark is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with Shark. If not, see .
*
*/
//===========================================================================
#ifndef SHARK_LINALG_CACHEDMATRIX_H
#define SHARK_LINALG_CACHEDMATRIX_H
#include
#include
#include
#include
#include
namespace shark {
///
/// \brief Efficient quadratic matrix cache
///
/// \par
/// The access operations of the CachedMatrix class
/// are specially tuned towards the iterative solution
/// of quadratic programs resulting in sparse solutions.
///
/// \par
/// 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:
///
/// \par
/// 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.
///
/// \par
/// 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.
///
/// \par
/// 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:
///
/// \par
/// 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.
///
/// \par
/// 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.
///
/// \par
/// 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).
///
template
class CachedMatrix
{
public:
typedef typename Matrix::QpFloatType QpFloatType;
/// Constructor
/// \param base Matrix to cache
/// \param cachesize Main memory to use as a kernel cache, in QpFloatTypes. Default is 256MB if QpFloatType is float, 512 if double.
CachedMatrix(Matrix* base, std::size_t cachesize = 0x4000000)
: mep_baseMatrix(base), m_cache( base->size(),cachesize ){}
/// \brief 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.
/// \param k the index of the row
/// \param start the index of the first element in the range
/// \param end the index of the last element in the range
/// \param storage the external storage. must be big enough capable to hold the range
void row(std::size_t k, std::size_t start,std::size_t end, QpFloatType* storage) const{
SIZE_CHECK(start <= end);
SIZE_CHECK(end <= size());
std::size_t cached= m_cache.lineLength(k);
if ( start < cached)//copy already available data into the temporary storage
{
QpFloatType const* line = m_cache.getLinePointer(k);
std::copy(line + start, line+cached, storage);
}
//evaluate the remaining entries
mep_baseMatrix->row(k,cached,end,storage+(cached-start));
}
/// \brief Return a subset of a matrix row
///
/// \par
/// This method returns an array of QpFloatType with at least
/// the entries in the interval [begin, end[ filled in.
///
/// \param k matrix row
/// \param start first column to be filled in
/// \param end last column to be filled in +1
QpFloatType* row(std::size_t k, std::size_t start, std::size_t end){
(void)start;//unused
//Save amount of entries already cached
std::size_t cached= m_cache.lineLength(k);
//create or extend cache line
QpFloatType* line = m_cache.getCacheLine(k,end);
if (end > cached)//compute entries not already cached
mep_baseMatrix->row(k,cached,end,line+cached);
return line;
}
/// return a single matrix entry
QpFloatType operator () (std::size_t i, std::size_t j) const{
return entry(i, j);
}
/// return a single matrix entry
QpFloatType entry(std::size_t i, std::size_t j) const{
return mep_baseMatrix->entry(i, j);
}
///
/// \brief Swap the rows i and j and the columns i and j
///
/// \par
/// 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.
///
/// \param i first row/column index
/// \param j second row/column index
///
void flipColumnsAndRows(std::size_t i, std::size_t j)
{
if(i == j)
return;
if (i > j)
std::swap(i,j);
// exchange all cache row entries
for (std::size_t k = 0; k < size(); k++)
{
std::size_t length = m_cache.lineLength(k);
if(length <= i) continue;
QpFloatType* line = m_cache.getLinePointer(k);//do not affect caching
if (j < length)
std::swap(line[i], line[j]);
else // only one element is available from the cache
line[i] = mep_baseMatrix->entry(k, j);
}
m_cache.swapLineIndices(i,j);
mep_baseMatrix->flipColumnsAndRows(i, j);
}
/// return the size of the quadratic matrix
std::size_t size() const
{ return mep_baseMatrix->size(); }
/// return the size of the kernel cache (in "number of QpFloatType-s")
std::size_t getMaxCacheSize() const
{ return m_cache.maxSize(); }
/// get currently used size of kernel cache (in "number of QpFloatType-s")
std::size_t getCacheSize() const
{ return m_cache.size(); }
/// get length of one specific currently cached row
std::size_t getCacheRowSize(std::size_t k) const
{ return m_cache.lineLength(k); }
bool isCached(std::size_t k) const
{ return m_cache.isCached(k); }
///\brief Restrict the cached part of the matrix to the upper left nxn sub-matrix
void setMaxCachedIndex(std::size_t n){
SIZE_CHECK(n <=size());
//truncate lines which are too long
//~ m_cache.restrictLineSize(n);//todo: we can do that better, only resize if the memory is actually needed
//~ for(std::size_t i = 0; i != n; ++i){
//~ if(m_cache.lineLength(i) > n)
//~ m_cache.resizeLine(i,n);
//~ }
for(std::size_t i = n; i != size(); ++i){//mark the lines for deletion which are not needed anymore
m_cache.markLineForDeletion(i);
}
}
/// completely clear/purge the kernel cache
void clear()
{ m_cache.clear(); }
protected:
Matrix* mep_baseMatrix; ///< matrix to be cached
LRUCache m_cache; ///< cache of the matrix lines
};
}
#endif