Software / code / prosody
Changeset
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 |
| parents | 13135:3fd24e1945b0 |
| children | 13137:b417a49cc31b |
| files | plugins/mod_storage_internal.lua |
| diffstat | 1 files changed, 55 insertions(+), 8 deletions(-) [+] |
line wrap: on
line diff
--- a/plugins/mod_storage_internal.lua Wed May 12 01:25:44 2021 +0200 +++ b/plugins/mod_storage_internal.lua Wed May 12 01:32:03 2021 +0200 @@ -122,6 +122,31 @@ return key; end +local function binary_search(haystack, test, min, max) + if min == nil then + min = 1; + end + if max == nil then + max = #haystack; + end + + local floor = math.floor; + while min < max do + local mid = floor((max + min) / 2); + + local result = test(haystack[mid]); + if result < 0 then + max = mid; + elseif result > 0 then + min = mid + 1; + else + return mid, haystack[mid]; + end + end + + return min, nil; +end + function archive:find(username, query) local list, err = datamanager.list_open(username, host, self.store); if not list then @@ -171,16 +196,38 @@ end, iter); end if query.start then - iter = it.filter(function(item) - local when = item.when or datetime.parse(item.attr.stamp); - return when >= query.start; - end, iter); + if not query.reverse then + local wi, exact = binary_search(list, function(item) + local when = item.when or datetime.parse(item.attr.stamp); + return query.start - when; + end); + if exact then + i = wi - 1; + elseif wi then + i = wi; + end + else + iter = it.filter(function(item) + local when = item.when or datetime.parse(item.attr.stamp); + return when >= query.start; + end, iter); + end end if query["end"] then - iter = it.filter(function(item) - local when = item.when or datetime.parse(item.attr.stamp); - return when <= query["end"]; - end, iter); + if query.reverse then + local wi = binary_search(list, function(item) + local when = item.when or datetime.parse(item.attr.stamp); + return query["end"] - when; + end); + if wi then + i = wi + 1; + end + else + iter = it.filter(function(item) + local when = item.when or datetime.parse(item.attr.stamp); + return when <= query["end"]; + end, iter); + end end if query.after then local found = false;
