Modul:Sandlådan/SM5POR/Cache: Skillnad mellan sidversioner
SM5POR (Diskussion | Bidrag) Ingen redigeringssammanfattning |
SM5POR (Diskussion | Bidrag) Ingen redigeringssammanfattning |
||
Rad 505: | Rad 505: | ||
s = "" |
s = "" |
||
end |
end |
||
t[i] = statrow(aentry.args, aentry, string. |
t[i] = statrow(aentry.args, aentry, string.format("%10s" .. s, aentry.result)) |
||
end |
end |
||
end |
end |
Versionen från 24 februari 2023 kl. 12.22
Dokumentation [visa] [redigera] [historik] [rensa sidcachen]
|
This page documents the development version of the Cache module. Since it is intended for an international audience, it is written in English, even as the development currently takes place on Swedish Wikipedia. |
Introduction
This module implements generic caching of repeated Lua function calls made using identical arguments. For this mechanism to be meaningful, the function called must be guaranteed not to produce different results for the same arguments within a short period of time, say by making the result partially dependent on a random number generator or a value read from an external communications device or service that does not come with a corresponding guarantee. It is the responsibility of the user of the Cache module to verify that any function or service called satisfies these stability criteria.
Basic concepts
Performance optimization
The cache system performs internal book-keeping in order to obtain performance data to optimize its own behavior. Specifically, the information indicated below as being collected per object category relate to categories lsted at the end. is recorded and updated as function calls are made via the cache system.
- Temporary records, retained only during the function call, deleted after use
- Timestamp at the receipt of each function call
- Timestamp at the return of each function call
- Number of calls made, by category
- CPU time spent on function calls, by category
- Wall clock time spent waiting for the call to return, by category
- Maximum amount of memory used during function call, by category
Object categories
There are three category levels:
- Totals for the cache system, arithmetic sums of the next level categories
- Aggregate data for each function, arithmetic sum of the next level categories
- Aggregate data for each permutation of argument size
The size of each positional argument to the function is calculated in the following way:
- The size of each supplied argument is determined, in bits
- Binary classes are defined as powers of powers of two. The argument is assigned to the smallest binary class it will fit in;
- Class 0, pow(2, pow(2, 0)): 2 bits, 4 values (a single DNA nucleic acid, one or A, C, G or T)
- Class 1, pow(2, pow(2, 1)): 4 bits, 16 values (a hex digit display, 0-9 and A-F)
- Class 2, pow(2, pow(2, 2)): 16 bits, 65,536 values (a Z80 PC or 2-byte register)
- Class 3, pow(2, pow(2, 3)): 256 bits (a typical URL)
- Class 4, pow(2, pow(2, 4)): 65536 bits, 8 KB (a compact SVG image file)
- Class 5, pow(2, pow(2, 5)): 4294967296 bits, 500 MB (all the software you need)
- Class 6, pow(2, pow(2, 6)): 18446744073709551616 bits (the total DNA of the entire human population)
- Class 7, pow(2, pow(2, 7)): 340282366920938463463374607431768211456 bits
It is highly doubtful that we will ever need to consider a computer system with a total memory capacity reaching class 7, even theoretically, while class 6 (minimum size 1 exabyte) should be at least within the realm of possibility. For practical purposes though, the cache system is unlikely to deal with function arguments larger than class 5 (which starts at half a gigabyte, meaybe a video clip).
This essentially means each argument will belong to one of seven classes (class 0-6). Given the number of arguments in a function call, this will translate to pow(7, N) for N arguments:
- 0 arguments: pow(7, 0): 1
- 1 arguments: pow(7, 1): 7
- 2 arguments: pow(7, 2): 49
- 3 arguments: pow(7, 3): 343
- 4 arguments: pow(7, 4): 2401
- 5 arguments: pow(7, 5): 16807
In reality, we may be dealing with less than 100 different function argument categories. heavily concentrated towards the smaller arguments. We'll see from the statistics how it plays out.
Execution time
As the primary reason for the use of caching in the first place tends to be the desire to avoid long execution times, it is of crucial importance that the caching mechanism doesn't actually increase execution times due to convoluted calling routines and evaluation methods.
Memory usage
Since the caching mechanism uses memory storage to save execution time, and memory also is a limited resource, memory usage must be monitored so that the module can find the optimal caching strategy dynamically as the application workload changes.
Self maintenance
Security
Technical reference
Exported functions
call
cache.call( age, f, ... )
Calls the function f
with the remaining arguments to the call, or obtain the result from a recent call involving the same function and arguments, depending on the age
of that result as well as other circumstances. In the following, only calls to the same function with identical arguments are considered.
- There is no earlier result stored, and no recent call made pending a result.
- Register the call and pass it on to function
f
.
- Register the call and pass it on to function
- There is no earlier result stored, but another call was requested less than
age
seconds ago.- Register the new call, and put it on hold pending the result from the previous call.
- No value, whether pending or already returned and stored, was requested less than
age
seconds ago.- Register the new call, and pass it on to function
f
.
- Register the new call, and pass it on to function
- The most recent value returned was requested less than
age
seconds ago.- Let the caller return with the stored value.
Example
local result = cache.call( 86400, primeFactors, n ) -- Use cached value if less than one day old.
control
cache.control( cmd, opt )
Performs control command cmd
to the cache system, with respect to optional parameter opt
(when provided, if command is applicable to it).
Commands
cmdClear
- Clear the cache from all stored results pertaining to the function
opt
, if provided. If no function is given, clear the entire cache system (unless this operation has been disabled for security reasons). cmdMemLimit
- Set the maximum amount of memory that may be allocated for the cache system to
opt
bytes. When this limit is reached, begin purging old stored results that are unlikely to be used again before they expire.
Example
local result = cache.control( cache.cmdClear, primeFactors ) -- Clear cache from old factorizations.
statistics
cache.statistics( f )
Retrieve statistics regarding the performance of the cache with respect to the function f
. If argument f
is nil
or not given, the statistics returned pertain to all cached functions in aggregate.
Example
local result = cache.statistics( f )
License
The software module described here, as well as this documentation, is available under CC0 (effectively public domain). To avoid confusion and duplicated work due to multiple forks or versions being distributed simultaneously, you are still both welcome and encouraged to contact the author to discuss potential coordination or cooperation.
Copyright © 2023 Anders Andersson |
local diag = require("Modul:Sandlådan/SM5POR/Diag")
local addmem = function(v, mem)
if v.maxmem then
v.maxmem = v.maxmem + mem
else
v.maxmem = mem
end
end
local addtime = function(v, time)
v.wclk = v.wclk + time
end
local idhook = {}
local globaltest = function()
local nt = {}
local nu = {}
local t
local u
for k, v in pairs(_G) do
t = type(k)
u = type(v)
if nt[t] then
nt[t] = nt[t] + 1
else
nt[t] = 1
end
if nu[u] then
nu[u] = nu[u] + 1
else
nu[u] = 1
end
end
end
local hashtest = function()
local hl = mw.hash.listAlgorithms()
local hv = {}
local c
local n
local m = 0
local tn = {}
local tn2 = {}
local st = "Llanfairpwyllgwyngyllgogeryllllwyrndroblochllantysiliogogogosh"
for k, ha in pairs(hl) do
c = mw.hash.hashValue(ha, st)
n = #c
if tn[n] then
tn[n][#tn[n]+1] = ha
else
tn[n] = {ha}
end
if n > m then
m = n
end
end
for k, v in pairs(tn) do
tn2[#tn2+1] = k
end
hv = {#hl, #tn2, m, #tn[m], tn2}
return diag.var("hashv", hv)
end
local varid = function(v, tl)
local sf = idhook[type(v)]
return mw.hash.hashValue("md5", sf(v, tl))
end
local idnil = function(v, tl)
return "nil"
end
local idnumber = function(v, tl)
return tostring(v)
end
local idstring = function(v, tl)
return '"' .. v .. '"'
end
local idboolean = function(v, tl)
return tostring(v)
end
local idtable = function(v, tl)
local r
local s = {}
local id = tl[v]
local i = 0
if id then
r = "tl" .. tostring(id)
else
tl[#tl+1] = v
for k, w in pairs(v) do
s[#s+1] = varid(k, tl)
s[#s+1] = varid(w, tl)
end
r = table.concat(s)
end
return r
end
local idfunction = function(v, tl)
return tostring(v)
end
idhook["nil"] = idnil
idhook["number"] = idnumber
idhook["string"] = idstring
idhook["boolean"] = idboolean
idhook["table"] = idtable
idhook["function"] = idfunction
local sizehook = {}
local varsize = function(v, tl)
local sf = sizehook[type(v)]
return sf(v, tl)
end
local sizenil = function(v, tl)
return 1
end
local sizenumber = function(v, tl)
local n = math.abs(v)
local c = 0
local p = 1
while p < v do
c = c + 1
p = 2 * p
end
return c
end
local sizestring = function(v, tl)
return 2 + #v * 8
end
local sizeboolean = function(v, tl)
return 1
end
local sizetable = function(v, tl)
local s = 2
local k
local w
for k, w in pairs(v) do
s = s + 2 + varsize(k, tl) + varsize(w, tl)
end
return s
end
local sizefunction = function(v, tl)
return 1
end
sizehook["nil"] = sizenil
sizehook["number"] = sizenumber
sizehook["string"] = sizestring
sizehook["boolean"] = sizeboolean
sizehook["table"] = sizetable
sizehook["function"] = sizefunction
local szclass = function(n)
local c = 0
local p = 2
while p < n do
c = c + 1
p = p * p
end
return c
end
local argsize = function(args)
local k
local v
local s = {}
for k, v in pairs(args) do
s[k] = varsize(v)
end
return s
end
local mapclass = function(asz)
local k
local v
local s = {}
for k, v in pairs(asz) do
s[k] = szclass(v)
end
return s
end
local classid = function(s)
local prime = {2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59}
local id = 1
for k = 1, #s do
id = id * math.pow(prime[k], s[k]+1)
end
return id
end
local sumsize = function(sizes)
local k
local v
local s = 0
for k, v in pairs(sizes) do
s = s + v
end
return s
end
local objcatactions = function(header)
if header then
return {"Calls", "Reads"}
else
return {"calls", "reads"}
end
end
local objcatcolumns = function(key)
local col = {header={"Count", "Changes", "Repeats", "Time", "CPU"},
label={"count", "changes", "repeats", "wclk", "cpu"},
scale={1, 1, 1, 1, 1000},
format={nil, nil, nil, nil, "% 5.1f"}}
return col[key]
end
local objcatzero = function(s, a, c)
for i, v in pairs(a) do
for j, w in pairs(c) do
s[v][w] = 0
end
end
end
local actionzero = function(s)
local columns = objcatcolumns("label")
local actions = objcatactions(false)
s.calls = {}
s.reads = {}
objcatzero(s, actions, columns)
end
local objzero = function(s)
s.a = {b=2, c=3}
s.d = {b=2, c=3}
s.e = {}
s.e[s.a] = 17
s.e[s.d] = 42
s.time = os.time()
s.functions = {}
s.colhd = {}
s.colhd.actions = objcatactions(true)
s.colhd.columns = objcatcolumns("header")
actionzero(s)
s.maxmem = 0
end
local regfunction = function(stat, f)
local fentry = stat.functions[f]
if not fentry then
fentry = {}
fentry.args = {}
fentry.acls = {}
actionzero(fentry)
fentry.maxmem = 0
stat.functions[f] = fentry
end
return fentry
end
local regacls = function(fentry, acls, mem)
local id = classid(acls)
local centry = fentry.acls[id]
if not centry then
centry = {}
centry.acls = acls
centry.args = {}
actionzero(centry)
centry.maxmem = 0
fentry.acls[id] = centry
end
addmem(centry, mem)
addmem(fentry, mem)
addmem(stat, mem)
return centry
end
local regargs = function(fentry, args)
local id = varid(args, {})
local aentry = fentry.args[id]
local asz
local mem
if not aentry then
asz = argsize(args)
mem = sumsize(asz)
rmem = 0
aentry = {}
aentry.args = args
aentry.maxmem = mem
aentry.latest = 0
aentry.centry = regacls(fentry, mapclass(asz), mem)
actionzero(aentry)
aentry.centry.args[id] = aentry
fentry.args[id] = aentry
end
return aentry
end
local catadd = function(action, repeated, tdelta, cpu)
action.count = action.count + 1
if repeated then
action.repeats = action.repeats + 1
else
action.changes = action.changes + 1
end
action.wclk = action.wclk + tdelta
action.cpu = action.cpu + cpu
end
local condadd = function(cached, cat, repeated, tdelta, cpu)
if cached then
catadd(cat.reads, repeated, tdelta, cpu)
else
catadd(cat.calls, repeated, tdelta, cpu)
end
end
local statadd = function(cached, repeated, fentry, aentry, t0, t1, cpu)
aentry.last = t0
local tdelta = t1-t0
condadd(cached, stat, repeated, tdelta, cpu)
condadd(cached, fentry, repeated, tdelta, cpu)
condadd(cached, aentry.centry, repeated, tdelta, cpu)
condadd(cached, aentry, repeated, tdelta, cpu)
end
if not stat then
stat = {}
objzero(stat)
end
local cache = {}
--- Exported functions
cache.call = function(age, f, ...)
local t0 = os.time()
local c0 = os.clock()
local fentry = regfunction(stat, f)
local aentry = regargs(fentry, {...})
local cached = aentry.calls.count > 0 and t0 < aentry.latest + age
local repeated = true
local r
local rid
local rmem
if cached then
r = aentry.result
else
r = f(...)
rid = varid(r, {})
repeated = aentry.calls.count > 0 and rid == aentry.rid
if not repeated then
aentry.result = r
aentry.rid = rid
rmem = varsize(r)
if aentry.rmem then
if rmem > aentry.rmem then
aentry.rmem = rmem
end
else
aentry.rmem = rmem
end
end
end
-- local mem = aentry.maxmem + aentry.rmem
aentry.latest = t0
local c1 = os.clock()
local t1 = os.time()
statadd(cached, repeated, fentry, aentry, t0, t1, c1-c0)
return r
end
cache.cmdClear = 0
cache.control = function(cmd, opt)
return 0
end
cache.statistics = function(ag)
return stat
end
local stathd = function(hd, object, opt)
local crhdr = {}
local t = {}
local c = {}
local r = {}
t[1] = {}
t[2] = {}
c[1] = {}
r[1] = {}
local i = 0
local j = 0
i = i + 1
if hd then
t[1][i] = hd
else
t[1][i] = ""
end
r[1][i] = 2
for b, v in pairs(object.colhd.actions) do
i = i + 1
t[1][i] = v
c[1][i] = #object.colhd.columns
for d, w in pairs(object.colhd.columns) do
j = j + 1
t[2][j] = w
end
end
i = i + 1
t[1][i] = "Memory"
r[1][i] = 2
i = i + 1
if opt then
t[1][i] = opt
else
t[1][i] = ""
end
r[1][i] = 2
crhdr.data = t
crhdr.cols = c
crhdr.rows = r
return crhdr
end
local condformat = function(v, s, f)
if f then
r = string.format(f, s * v)
else
r = s * v
end
return r
end
local statrow = function(hd, rec, result)
local crtbl = {}
crtbl.data = {}
crtbl.cols = {}
crtbl.rows = {}
local ocs = objcatcolumns("scale")
local ocf = objcatcolumns("format")
local i = 1
if hd then
if type(hd) == "table" then
crtbl.data[i] = diag.lualist(hd)
else
crtbl.data[i] = hd
end
else
crtbl.data[i] = ""
end
for b, v in pairs({rec.calls, rec.reads}) do
for d, w in pairs({v.count, v.changes, v.repeats, v.wclk, v.cpu}) do
i = i + 1
crtbl.data[i] = condformat(w, ocs[d], ocf[d])
end
end
i = i + 1
crtbl.data[i] = rec.maxmem
i = i + 1
if result then
crtbl.data[i] = diag.var(nil, result)
else
crtbl.data[i] = ""
end
return crtbl
end
cache.tabulate = function(stat)
local crhdr = stathd("Object", stat, "Result")
local t = {}
local crtbl = {}
crtbl.data = {}
crtbl.cols = {}
crtbl.rows = {}
local i = 1
t[i] = statrow("Total", stat, nil)
for f, fentry in pairs(stat.functions) do
i = i + 1
t[i] = statrow("", fentry, nil)
for cid, centry in pairs(fentry.acls) do
i = i + 1
t[i] = statrow(centry.acls, centry, id)
if centry.args then
for aid, aentry in pairs(centry.args) do
i = i + 1
if #aentry.result > 10 then
s = "... "
else
s = ""
end
t[i] = statrow(aentry.args, aentry, string.format("%10s" .. s, aentry.result))
end
end
end
end
for k, v in pairs(t) do
crtbl.data[k] = v.data
crtbl.cols[k] = v.cols
crtbl.rows[k] = v.rows
end
return diag.htmltable(crhdr, crtbl)
-- return diag.varlim("op", 3, cache)
end
return cache