prosody
396db0e7084f
plugins/mod_storage_internal.lua

Find changesets by keywords by author, files, the commit message, revision number or hash, or revset expression.

Software / code / prosody

Comparison

plugins/mod_storage_internal.lua @ 13136:396db0e7084f

mod_storage_internal: Use a binary search for time based ranges Iterating over an entire archive to find a few items in the far end from where iteration started is expensive, and probably more expensive with the lazy-loading of items added in the previous commit. Since we can now efficiently read items in random order, we can now use a binary search to find a better starting point for iteration.
author Kim Alvefur <zash@zash.se>
date Wed, 12 May 2021 01:32:03 +0200
parent 13135:3fd24e1945b0
child 13187:fe1229919070
comparison
equal deleted inserted replaced
13135:3fd24e1945b0 13136:396db0e7084f
120 if not ok then return ok, err; end 120 if not ok then return ok, err; end
121 archive_item_count_cache:set(cache_key, item_count+1); 121 archive_item_count_cache:set(cache_key, item_count+1);
122 return key; 122 return key;
123 end 123 end
124 124
125 local function binary_search(haystack, test, min, max)
126 if min == nil then
127 min = 1;
128 end
129 if max == nil then
130 max = #haystack;
131 end
132
133 local floor = math.floor;
134 while min < max do
135 local mid = floor((max + min) / 2);
136
137 local result = test(haystack[mid]);
138 if result < 0 then
139 max = mid;
140 elseif result > 0 then
141 min = mid + 1;
142 else
143 return mid, haystack[mid];
144 end
145 end
146
147 return min, nil;
148 end
149
125 function archive:find(username, query) 150 function archive:find(username, query)
126 local list, err = datamanager.list_open(username, host, self.store); 151 local list, err = datamanager.list_open(username, host, self.store);
127 if not list then 152 if not list then
128 if err then 153 if err then
129 return list, err; 154 return list, err;
169 iter = it.filter(function(item) 194 iter = it.filter(function(item)
170 return item.with == query.with; 195 return item.with == query.with;
171 end, iter); 196 end, iter);
172 end 197 end
173 if query.start then 198 if query.start then
174 iter = it.filter(function(item) 199 if not query.reverse then
175 local when = item.when or datetime.parse(item.attr.stamp); 200 local wi, exact = binary_search(list, function(item)
176 return when >= query.start; 201 local when = item.when or datetime.parse(item.attr.stamp);
177 end, iter); 202 return query.start - when;
203 end);
204 if exact then
205 i = wi - 1;
206 elseif wi then
207 i = wi;
208 end
209 else
210 iter = it.filter(function(item)
211 local when = item.when or datetime.parse(item.attr.stamp);
212 return when >= query.start;
213 end, iter);
214 end
178 end 215 end
179 if query["end"] then 216 if query["end"] then
180 iter = it.filter(function(item) 217 if query.reverse then
181 local when = item.when or datetime.parse(item.attr.stamp); 218 local wi = binary_search(list, function(item)
182 return when <= query["end"]; 219 local when = item.when or datetime.parse(item.attr.stamp);
183 end, iter); 220 return query["end"] - when;
221 end);
222 if wi then
223 i = wi + 1;
224 end
225 else
226 iter = it.filter(function(item)
227 local when = item.when or datetime.parse(item.attr.stamp);
228 return when <= query["end"];
229 end, iter);
230 end
184 end 231 end
185 if query.after then 232 if query.after then
186 local found = false; 233 local found = false;
187 iter = it.filter(function(item) 234 iter = it.filter(function(item)
188 local found_after = found; 235 local found_after = found;