Created
January 4, 2024 20:05
-
-
Save nikkolasg/bf95c516d2eef5bcfade7548b38990ba to your computer and use it in GitHub Desktop.
estimator of wall time & cpu time for recursive vs sequential approach
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
from sympy import * | |
# n = number of initial leaves | |
# u = number of updates in a block | |
# r = range of blocks | |
# d = depth of the storage trie | |
n, u, r, d = symbols('n u r d',positive=True) | |
# depth of the state trie | |
dstate = 10 | |
# time in s to prove a single MPT node with 16 children proofs | |
t_node = 13 | |
# time in s to prove from storage trie to state trie, in one go | |
t_state = 26 | |
# time in s to prove a deep 4 MPT proof | |
t_proof = 13 | |
# time to simply recurse over two proofs | |
t_recurse = 2 | |
def sum_tree(q, d): | |
return sum([q / 16**i for i in range(0..d)]) | |
class Recursive: | |
def wall_time(n,u,r,d): | |
one_block = t_node * d + t_state | |
# we can do all blocks in parallel (we actually preprocess them) | |
# the only additional time is the time to aggregate block level proofs | |
return one_block + t_recurse * log(r,2) | |
def cpu_time(n,u,r,d): | |
# there is at least t node to update, and then going up the path | |
# then proving to the state | |
# this is an upperbound as there will be less than | |
# TODO use sum_tree | |
one_block = u * t_node * d + t_state | |
return one_block * r + t_recurse * log(r,2) | |
class Sequential: | |
def wall_time(n,u,r,d): | |
# all proving of MPT proof in parallel + time to go to root | |
one_block = t_proof + t_recurse * log(n,2) + t_state | |
# proving in parallel + time to aggregate | |
return one_block + t_recurse * log(r,2) | |
def cpu_time(n,u,r,d): | |
one_block = t_proof * n + t_recurse * 2 * n + t_state | |
return one_block * r + t_recurse * log(r,2) | |
def prepare_params(): | |
params = [] | |
for n in [10,100,1000,10000]: | |
for up in [0.1,0.2]: | |
u = n * up | |
for r in [1,10,100,1000]: | |
for d in [4,5,6]: | |
params.append({ | |
'n':n, | |
'u':u, | |
'r':r, | |
'd':d, | |
}) | |
return params | |
def compare_walltime(params): | |
valid = [] | |
for p in params: | |
n,u,r,d = p['n'], p['u'], p['r'], p['d'] | |
rw = Recursive.wall_time(n,u,r,d) | |
sw = Sequential.wall_time(n,u,r,d) | |
# we can be a bit relaxed -> it's ok if we're 10% slower | |
if rw <= sw*1.1: | |
valid.append({'p':p,'rw':int(rw),'sw':int(sw), "ratio_rec/seq": float(rw/sw)}) | |
return valid | |
# solutions = solve(rw < sw,n) | |
# solutions = solve(rw - sw,n) | |
# print(solutions) | |
# s = solutions[0].subs(d,4) | |
# print(s) | |
def compare_cputime(params): | |
valid = [] | |
for p in params: | |
n,u,r,d = p['n'], p['u'], p['r'], p['d'] | |
rw = Recursive.cpu_time(n,u,r,d) | |
sw = Sequential.cpu_time(n,u,r,d) | |
if rw <= sw*1.1: | |
valid.append({'p':p,'rw':int(rw),'sw':int(sw), "ratio_rec/seq": float(rw/sw)}) | |
return valid | |
# rc = Recursive.cpu_time(n,u,r,d) | |
# sc = Sequential.cpu_time(n,u,r,d) | |
# solutions = solve(rc - sc,n) | |
# print(solutions) | |
# s = solutions[0].subs(d,4).subs(u,10) | |
# print(s) | |
import json | |
params = prepare_params() | |
res_wt = compare_walltime(params) | |
res_ct = compare_cputime(params) | |
res = { | |
"walltime": res_wt, | |
"cputime": res_ct, | |
} | |
print(json.dumps(res,indent=2)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment