Shark machine learning library
Installation
Tutorials
Benchmarks
Documentation
Quick references
Class list
Global functions
include
shark
LinAlg
CachedMatrix.h
Go to the documentation of this file.
1
//===========================================================================
2
/*!
3
*
4
*
5
* \brief Efficient quadratic matrix cache
6
*
7
*
8
* \par
9
*
10
*
11
*
12
* \author T. Glasmachers
13
* \date 2007-2012
14
*
15
*
16
* \par Copyright 1995-2017 Shark Development Team
17
*
18
* <BR><HR>
19
* This file is part of Shark.
20
* <https://shark-ml.github.io/Shark/>
21
*
22
* Shark is free software: you can redistribute it and/or modify
23
* it under the terms of the GNU Lesser General Public License as published
24
* by the Free Software Foundation, either version 3 of the License, or
25
* (at your option) any later version.
26
*
27
* Shark is distributed in the hope that it will be useful,
28
* but WITHOUT ANY WARRANTY; without even the implied warranty of
29
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
30
* GNU Lesser General Public License for more details.
31
*
32
* You should have received a copy of the GNU Lesser General Public License
33
* along with Shark. If not, see <http://www.gnu.org/licenses/>.
34
*
35
*/
36
//===========================================================================
37
38
39
#ifndef SHARK_LINALG_CACHEDMATRIX_H
40
#define SHARK_LINALG_CACHEDMATRIX_H
41
42
#include <
shark/Data/Dataset.h
>
43
#include <
shark/LinAlg/Base.h
>
44
#include <
shark/LinAlg/LRUCache.h
>
45
46
#include <vector>
47
#include <cmath>
48
49
50
namespace
shark
{
51
52
53
///
54
/// \brief Efficient quadratic matrix cache
55
///
56
/// \par
57
/// The access operations of the CachedMatrix class
58
/// are specially tuned towards the iterative solution
59
/// of quadratic programs resulting in sparse solutions.
60
///
61
/// \par
62
/// The kernel cache is probably one of the most intricate
63
/// or mind-twisting parts of Shark. In order to fully understand
64
/// it, reading the source code is essential and this description
65
/// naturally not sufficient. However, the general ideas are as
66
/// follows:
67
///
68
/// \par
69
/// A CachedMatrix owns a pointer to a regular (non-cached)
70
/// kernel matrix, the exact type of which is a template
71
/// parameter. Through it, the actions of requesting an entry
72
/// and propagating column-/row-flips are carried out. Even
73
/// though a CachedMatrix offers some methods also offered
74
/// by the general KernelMatrix, note that it does not inherit
75
/// from it in order to offer greater flexibility.
76
///
77
/// \par
78
/// The CachedMatrix defines a struct tCacheEntry, which
79
/// represents one row of varying length of a stored kernel matrix.
80
/// The structure aggregates a pointer to the kernel values (stored
81
/// as values of type CacheType); the number of stored values; and
82
/// the indices of the next older and newer cache entries. The latter
83
/// two indices pertain to the fact that the CachedMatrix maintains
84
/// two different "orders" of the examples: one related to location
85
/// in memory, and the other related to last usage time, see below.
86
/// During the lifetime of a CachedMatrix, it will hold a vector of
87
/// the length of the number of examples of tCacheEntry: one entry
88
/// for each example. When an example has no kernel values in the cache,
89
/// its tCacheEntry.length will be 0, its tCacheEntry.data will be NULL,
90
/// and its older and newer variables will be SHARK_CACHEDMATRIX_NULL_REFERENCE.
91
/// Otherwise, the entries take their corresponding meaningful values.
92
/// In particular for tCacheEntry.data, memory is dynamically allocated
93
/// via malloc, reallocated via realloc, and freed via free as fit.
94
///
95
/// \par
96
/// A basic operation the CachedMatrix must support is throwing away
97
/// old stored values to make room for new values, because it is very
98
/// common that not all values fit into memory (otherwise, consider the
99
/// PrecomputedMatrix class). When a new row is requested via row(..),
100
/// but no room to store it, row(..) has two options for making space:
101
///
102
/// \par
103
/// First option: first, the row method checks if the member index
104
/// m_truncationColumnIndex is lower than the overall number of examples.
105
/// If so, it goes through all existing rows and shortens them to a length
106
/// of m_truncationColumnIndex. Through this shortening, memory becomes
107
/// available. In other words, m_truncationColumnIndex can be used to
108
/// indicate to the CachedMatrix that every row longer than
109
/// m_truncationColumnIndex can be clipped at the end. By default,
110
/// m_truncationColumnIndex is equal to the number of examples and not
111
/// changed by the CachedMatrix, so no clipping will occur if the
112
/// CachedMatrix is left to its own devices. However, m_truncationColumnIndex
113
/// can be set from externally via setTruncationIndex(..) [this might be
114
/// done after a shrinking event, for example]. Now imagine a situation
115
/// where the cache is full, and the possibility exists to free some
116
/// memory by truncating longer cache rows to length m_truncationColumnIndex.
117
/// As soon as enough rows have been clipped for a new row to fit in, the
118
/// CachedMatrix computes the new row and passes back control. Most likely,
119
/// the next time a new, uncached row is requested, more rows will have to
120
/// get clipped. In order not to start checking if rows can be clipped from
121
/// the very first row over again, the member variable m_truncationRowIndex
122
/// internally stores where the chopping-procedure left off the last time.
123
/// When a new row is requested and it's time to clear out old entries, it
124
/// will start looking for choppable rows at this index to save time. In
125
/// general, any chopping would happen via cacheResize(..) internally.
126
///
127
/// \par
128
/// Second option: if all rows have been chopped of at the end, or if this
129
/// has never been an option (due to all rows being shorter or equal to
130
/// m_truncationColumnIndex anyways), entire rows will get discarded as
131
/// the second option. This will probably be the more common case. In
132
/// general, row deletions will happen via cacheDelete(..) internally.
133
/// The CachedMatrix itself only resorts to a very simple heuristic in
134
/// order to determine which rows to throw away to make room for new ones.
135
/// Namely, the CachedMatrix keeps track of the "age" or "oldness" of all
136
/// cached rows. This happens via the so-to-speak factually doubly-linked
137
/// list of indices in the tCacheEntry.older/newer entries, plus two class
138
/// members m_cacheNewest and m_cacheOldest, which point to the beginning
139
/// and end of this list. When row(..) wants to delete a cached row, it
140
/// always does so on the row with index m_cacheOldest, and this index is
141
/// then set to the next oldest row. Likewise, whenever a new row is requested,
142
/// m_cacheNewest is set to point to that one. In order to allow for smarter
143
/// heuristics, external classes may intervene with the deletion order via
144
/// the methods cacheRedeclareOldest and cacheRedeclareNewest, which move
145
/// an example to be deleted next or as late as possible, respectively.
146
///
147
/// \par
148
/// Two more drastic possibilites to influence the cache behaviour are
149
/// cacheRowResize and cacheRowRelease, which both directly resize (e.g.,
150
/// chop off) cached row values or even discard the row altogether.
151
/// In general however, it is preferred that the external application
152
/// only indicate preferences for deletion, because it will usually not
153
/// have information on the fullness of the cache (although this functionality
154
/// could easily be added).
155
///
156
template
<
class
Matrix>
157
class
CachedMatrix
158
{
159
public
:
160
typedef
typename
Matrix::QpFloatType
QpFloatType
;
161
162
/// Constructor
163
/// \param base Matrix to cache
164
/// \param cachesize Main memory to use as a kernel cache, in QpFloatTypes. Default is 256MB if QpFloatType is float, 512 if double.
165
CachedMatrix
(Matrix* base, std::size_t cachesize = 0x4000000)
166
:
mep_baseMatrix
(base),
m_cache
( base->
size
(),cachesize ){}
167
168
/// \brief Copies the range [start,end) of the k-th row of the matrix in external storage
169
///
170
/// This call regards the access to the line as out-of-order, thus the cache is not influenced.
171
/// \param k the index of the row
172
/// \param start the index of the first element in the range
173
/// \param end the index of the last element in the range
174
/// \param storage the external storage. must be big enough capable to hold the range
175
void
row
(std::size_t k, std::size_t start,std::size_t end,
QpFloatType
* storage)
const
{
176
SIZE_CHECK
(start <= end);
177
SIZE_CHECK
(end <=
size
());
178
std::size_t cached=
m_cache
.
lineLength
(k);
179
if
( start < cached)
//copy already available data into the temporary storage
180
{
181
QpFloatType
const
* line =
m_cache
.
getLinePointer
(k);
182
std::copy(line + start, line+cached, storage);
183
}
184
//evaluate the remaining entries
185
mep_baseMatrix
->row(k,cached,end,storage+(cached-start));
186
}
187
188
/// \brief Return a subset of a matrix row
189
///
190
/// \par
191
/// This method returns an array of QpFloatType with at least
192
/// the entries in the interval [begin, end[ filled in.
193
///
194
/// \param k matrix row
195
/// \param start first column to be filled in
196
/// \param end last column to be filled in +1
197
QpFloatType
*
row
(std::size_t k, std::size_t start, std::size_t end){
198
(void)start;
//unused
199
//Save amount of entries already cached
200
std::size_t cached=
m_cache
.
lineLength
(k);
201
//create or extend cache line
202
QpFloatType
* line =
m_cache
.
getCacheLine
(k,end);
203
if
(end > cached)
//compute entries not already cached
204
mep_baseMatrix
->row(k,cached,end,line+cached);
205
return
line;
206
}
207
208
/// return a single matrix entry
209
QpFloatType
operator ()
(std::size_t i, std::size_t j)
const
{
210
return
entry
(i, j);
211
}
212
213
/// return a single matrix entry
214
QpFloatType
entry
(std::size_t i, std::size_t j)
const
{
215
return
mep_baseMatrix
->entry(i, j);
216
}
217
218
///
219
/// \brief Swap the rows i and j and the columns i and j
220
///
221
/// \par
222
/// It may be advantageous for caching to reorganize
223
/// the column order. In order to keep symmetric matrices
224
/// symmetric the rows are swapped, too. This corresponds
225
/// to swapping the corresponding variables.
226
///
227
/// \param i first row/column index
228
/// \param j second row/column index
229
///
230
void
flipColumnsAndRows
(std::size_t i, std::size_t j)
231
{
232
if
(i == j)
233
return
;
234
if
(i > j)
235
std::swap(i,j);
236
237
// exchange all cache row entries
238
for
(std::size_t k = 0; k <
size
(); k++)
239
{
240
std::size_t length =
m_cache
.
lineLength
(k);
241
if
(length <= i)
continue
;
242
QpFloatType
* line =
m_cache
.
getLinePointer
(k);
//do not affect caching
243
if
(j < length)
244
std::swap(line[i], line[j]);
245
else
// only one element is available from the cache
246
line[i] =
mep_baseMatrix
->entry(k, j);
247
}
248
m_cache
.
swapLineIndices
(i,j);
249
mep_baseMatrix
->flipColumnsAndRows(i, j);
250
}
251
252
/// return the size of the quadratic matrix
253
std::size_t
size
()
const
254
{
return
mep_baseMatrix
->size(); }
255
256
/// return the size of the kernel cache (in "number of QpFloatType-s")
257
std::size_t
getMaxCacheSize
()
const
258
{
return
m_cache
.
maxSize
(); }
259
260
/// get currently used size of kernel cache (in "number of QpFloatType-s")
261
std::size_t
getCacheSize
()
const
262
{
return
m_cache
.
size
(); }
263
264
/// get length of one specific currently cached row
265
std::size_t
getCacheRowSize
(std::size_t k)
const
266
{
return
m_cache
.
lineLength
(k); }
267
268
bool
isCached
(std::size_t k)
const
269
{
return
m_cache
.
isCached
(k); }
270
271
///\brief Restrict the cached part of the matrix to the upper left nxn sub-matrix
272
void
setMaxCachedIndex
(std::size_t n){
273
SIZE_CHECK
(n <=
size
());
274
275
//truncate lines which are too long
276
//~ m_cache.restrictLineSize(n);//todo: we can do that better, only resize if the memory is actually needed
277
//~ for(std::size_t i = 0; i != n; ++i){
278
//~ if(m_cache.lineLength(i) > n)
279
//~ m_cache.resizeLine(i,n);
280
//~ }
281
for
(std::size_t i = n; i !=
size
(); ++i){
//mark the lines for deletion which are not needed anymore
282
m_cache
.
markLineForDeletion
(i);
283
}
284
}
285
286
/// completely clear/purge the kernel cache
287
void
clear
()
288
{
m_cache
.
clear
(); }
289
290
protected
:
291
Matrix*
mep_baseMatrix
;
///< matrix to be cached
292
293
LRUCache<QpFloatType>
m_cache
;
///< cache of the matrix lines
294
};
295
296
}
297
#endif