0001 classdef StoreDB < handle_light 0002 % The StoreDB class is a handle class to manage caching in Manopt. 0003 % 0004 % To create an object, call: storedb = StoreDB(); 0005 % Alternatively, call: storedb = StoreDB(storedepth); to instruct 0006 % the database to keep at most storedepth stores in its history. 0007 % (Note that clean up only happens when purge() is called). 0008 % 0009 % The storedb object is passed by reference: when it is passed to a 0010 % function as an input, and that function modifies it, the original 0011 % object is modified. 0012 0013 % This file is part of Manopt: www.manopt.org. 0014 % Original author: Nicolas Boumal, April 3, 2015. 0015 % Contributors: 0016 % Change log: 0017 % 0018 % Aug. 2, 2018 (NB) 0019 % Purge now selects based on time since last access, whether read or 0020 % write. It used to select based on last write. This should allow to 0021 % set a smaller value of storedepth for trustregions (in particular). 0022 % Also added StoreDB.remove(key) which allows to specifically remove 0023 % the store associated to a key. This can be used by a solver when it 0024 % is reasonably certain that the memory associated to a certain key 0025 % is no longer needed (for example, when a step was rejected in 0026 % trustregions or in a line-search algorithm.) Proper usage of this 0027 % feature should allow to set a small value for storedepth. 0028 % Furthermore, getNewKey() now places an empty store at the created 0029 % key. As a result, it is no longer legitimate to call storedb.get on 0030 % an unknown key: this now issues a warning, which should help debug. 0031 % The function removefirstifdifferent(key1, key2) only removes key1 0032 % if it is different from key2, which is helpful when an iteration 0033 % may have failed to move to a distinct point. 0034 0035 % TODO : protect get/setWithShared calls: limit to one, and forbid access 0036 % to shared memory while it has not been returned. 0037 % Do think of the applyStatsFun case : calls a getWithShared, does 0038 % not need a setWithShared. I think for statsfun there should be a 0039 % method "forfeitWithShared". 0040 0041 properties(Access = public) 0042 0043 % This memory is meant to be shared at all times. Users can modify 0044 % this at will. It is the same for all points x. 0045 shared = struct(); 0046 0047 % This memory is used by the toolbox for, e.g., automatic caching 0048 % and book keeping. Users should not overwrite this. It is the 0049 % same for all points x. 0050 internal = struct(); 0051 0052 % When calling purge(), only a certain number of stores will be 0053 % kept in 'history'. This parameter fixes that number. The most 0054 % recently modified stores are kept. Set to inf to keep all stores. 0055 storedepth = inf; 0056 0057 end 0058 0059 properties(Access = private) 0060 0061 % This structure holds separate memories for individual points. 0062 % Use get and set to interact with this. The field name 'shared' is 0063 % reserved, for use with get/setWithShared. 0064 history = struct(); 0065 0066 % This internal counter is used to obtain unique key's for points. 0067 counter = uint32(0); 0068 0069 % This internal counter is used to time calls to 'set', and hence 0070 % keep track of which stores in 'history' were last updated. 0071 timer = uint32(0); 0072 0073 end 0074 0075 0076 methods(Access = public) 0077 0078 % Constructor 0079 function storedb = StoreDB(storedepth) 0080 if nargin >= 1 0081 storedb.storedepth = storedepth; 0082 end 0083 end 0084 0085 % Returns the store associated to a given key. 0086 % If the key is unknown, issues a warning and returns empty store. 0087 function store = get(storedb, key) 0088 if isfield(storedb.history, key) 0089 % Update access timer. 0090 storedb.history.(key).lastaccess__ = storedb.timer; 0091 % Extract the store. 0092 store = storedb.history.(key); 0093 else 0094 store = struct(); 0095 store.lastaccess__ = storedb.timer; 0096 msg = 'Called storedb.get for a store with unknown key.'; 0097 % If the queried key is less than the counter, it must have 0098 % been a valid key at some point. Inform the user that it 0099 % may have been purged (or removed) prematurely. 0100 if str2double(key(2:end)) < storedb.counter 0101 msg = [msg, ' It seems that key was purged or removed.']; 0102 end 0103 msg = [msg, ' Returned an empty structure.']; 0104 warning('manopt:storedb:get', msg); 0105 end 0106 storedb.timer = storedb.timer + 1; 0107 end 0108 0109 % Same as get, but adds the shared memory in store.shared. 0110 function store = getWithShared(storedb, key) 0111 store = storedb.get(key); 0112 store.shared = storedb.shared; 0113 end 0114 0115 % Save the given store at the given key. If no key is provided, a 0116 % new key is generated for this store (i.e., it is assumed this 0117 % store pertains to a new point). The key is returned in all cases. 0118 % A field 'lastaccess__' is added/updated in the store structure, 0119 % keeping track of the last time that store was accessed. 0120 function key = set(storedb, store, key) 0121 if nargin < 3 0122 key = getNewKey(storedb); 0123 end 0124 store.lastaccess__ = storedb.timer; 0125 storedb.timer = storedb.timer + 1; 0126 storedb.history.(key) = store; 0127 end 0128 0129 % Same as set, but extracts the shared memory and saves it. 0130 % The stored store will still have a 'shared' field, but empty. 0131 function key = setWithShared(storedb, store, key) 0132 storedb.shared = store.shared; 0133 store.shared = []; 0134 key = storedb.set(store, key); 0135 end 0136 0137 % Erases a store from memory, identified by key. 0138 % If the key is unknown, issues a warning. 0139 function remove(storedb, key) 0140 if isfield(storedb.history, key) 0141 storedb.history = rmfield(storedb.history, key); 0142 else 0143 warning('manopt:storedb:remove', ... 0144 ['Attempted to remove store with unknown key.\n' ... 0145 'Perhaps it was purged? Try postponing purge().']); 0146 end 0147 end 0148 0149 % Erases store at key1 if it is different from key2. 0150 function removefirstifdifferent(storedb, key1, key2) 0151 if ~strcmp(key1, key2) 0152 storedb.remove(key1); 0153 end 0154 end 0155 0156 % Generates a unique key and returns it. This should be called 0157 % everytime a new point is generated / stored. Keys are valid field 0158 % names for structures. After this call, an empty store is added in 0159 % the cache at the newly generated key. It has minimal priority 0160 % vis-à-vis storedb.purge(). 0161 function key = getNewKey(storedb) 0162 key = sprintf('z%d', storedb.counter); 0163 storedb.counter = storedb.counter + 1; 0164 % If we attempt to storedb.remove(key) or storedb.get(key) on 0165 % this newly created key before anything is stored there, we 0166 % will get a warning. Since there are legitimate scenarios for 0167 % this to happen, we place an empty store at the new key 0168 % immediately. Its last-access flag is set to 0 so it would be 0169 % the first to be purged (unless it was later accessed.) 0170 emptystore = struct(); 0171 emptystore.lastaccess__ = 0; 0172 storedb.history.(key) = emptystore; 0173 end 0174 0175 % Clear entries in storedb.history to limit memory usage. 0176 function purge(storedb) 0177 0178 if isinf(storedb.storedepth) 0179 return; 0180 end 0181 0182 if storedb.storedepth <= 0 0183 storedb.history = struct(); 0184 return; 0185 end 0186 0187 % Get list of field names (keys). 0188 keys = fieldnames(storedb.history); 0189 nkeys = length(keys); 0190 0191 % If we need to remove some of the elements in the database, 0192 if nkeys > storedb.storedepth 0193 0194 % Get the last-access counter of each element: 0195 % A higher number means it was accessed more recently. 0196 % Both read and write operations are considered 'access'. 0197 lastaccess = zeros(nkeys, 1, class(storedb.timer)); 0198 for i = 1 : nkeys 0199 lastaccess(i) = storedb.history.(keys{i}).lastaccess__; 0200 end 0201 0202 % Sort the counters and determine the threshold above which 0203 % the field needs to be removed. 0204 sortlastaccess = sort(lastaccess, 1, 'descend'); 0205 minlastaccess = sortlastaccess(storedb.storedepth); 0206 0207 % Remove all fields that are too old. 0208 storedb.history = rmfield(storedb.history, ... 0209 keys(lastaccess < minlastaccess)); 0210 end 0211 0212 end % end of purge() 0213 0214 end 0215 0216 end