estimator of wall time & cpu time for recursive vs sequential approach

estimator.py

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))