abstraction_bindings.py (10062B)
1 #!/usr/bin/env python3 2 """Attribute stable let/abstraction costs using exact-tree model and nonnumeric probes.""" 3 import argparse 4 import hashlib 5 import json 6 import platform 7 import random 8 import statistics 9 from pathlib import Path 10 11 from float_multiply import Runner,sha 12 from base_workloads import encode as nat 13 from http_headers import LEAF,TRUE,pair,tree_list,expect 14 from bundle_dag import Intern,read 15 from abstraction_binding_model import Model,programs,source 16 17 ROOT=Path(__file__).resolve().parent.parent 18 HELPERS='''!export * 19 triage leaf stem fork = t (t leaf stem) fork 20 choose yes no value = triage no (_ : yes) (_ _ : yes) value 21 negate x = choose t (t t) x 22 both a b = choose b t a 23 either a b = choose (t t) b a 24 head x = triage t (_ : t) (a _ : a) x 25 tail x = triage t (_ : t) (_ b : b) x 26 map f xs = triage t (_ : t) (a b : t (f a) (map f b)) xs 27 copy xs = triage t (_ : t) (a b : t (t a) (copy b)) xs 28 loop x = loop x 29 ''' 30 31 32 def main(): 33 p=argparse.ArgumentParser(description=__doc__) 34 p.add_argument('tricu',type=Path) 35 p.add_argument('--directory',type=Path,required=True) 36 p.add_argument('--repeats',type=int,default=5) 37 args=p.parse_args() 38 if not 3<=args.repeats<=10:p.error('repeats 3..10') 39 root=args.directory.resolve();root.mkdir(parents=True,exist_ok=False) 40 runner=Runner(args.tricu,root,600,memory_mib=2048) 41 body=HELPERS 42 exprs=programs() 43 for name,expr in exprs.items():body+=name+' = '+source(expr)+'\n' 44 for name in exprs: 45 if name.startswith('adder'):continue 46 if name.startswith(('single','branch','constructor')): 47 body+=f'run{name} xs = map (p : {name} (head p) (tail p)) xs\n' 48 else:body+=f'run{name} xs = map {name} xs\n' 49 # An unselected branch must ignore its closed divergent value. A pair's 50 # first projection must not force a diverging second field. 51 for role in ['Bound','Inline']: 52 body+=f'unusedDemand{role} x = unused{role} (t t)\n' 53 body+=f'unselectedDemand{role} x = closedBranch{role} t\n' 54 body+=f'selectedDemand{role} x = closedBranch{role} (t t)\n' 55 body+=f'branchDemand{role} x = head (branch{role} (t t) t)\n' 56 body+=f'invokeClosure{role} x = (closure{role} x) t\n' 57 body+='etaExpandedApplied x = (etaExpanded t) x\netaContractedApplied x = (etaContracted t) x\n' 58 path=root/'driver.tri';path.write_text(body) 59 report=dict(complete=False,runtime_sha256=sha(args.tricu),compiler_sha256=sha(ROOT/'bootstrap/build-stable.arboricx'), 60 harness_sha256=sha(Path(__file__)),model_sha256=sha(ROOT/'test/abstraction_binding_model.py'), 61 runner_dependency_sha256=sha(ROOT/'test/float_multiply.py'),source_sha256=sha(path),platform=platform.platform(), 62 model=[],demand=[],samples=[],summaries=[]) 63 try: 64 tool=runner.imported(ROOT/'bootstrap/build-stable.arboricx','compiler') 65 bundle=root/'bindings.arboricx' 66 runner.run('compile',['compile','--file',path,'--toolchain',tool,'--tool-store',runner.store, 67 '--store',runner.store,'--output',bundle,'--compile-timeout','240'],270) 68 pin=runner.imported(bundle,'bindings');report['bundle_sha256']=sha(bundle) 69 _,_,nodes,exports,_=read(bundle) 70 intern=Intern();ids=intern.graph(nodes) 71 globals={name:ids[i] for name,i in exports.items()} 72 for name,expr in exprs.items(): 73 model=Model(intern,globals) 74 result=model.compile(expr) 75 if result!=globals[name]:raise AssertionError(('model tree differs',name)) 76 seen,todo=set(),[result] 77 while todo: 78 i=todo.pop() 79 if i not in seen:seen.add(i);todo.extend(intern.nodes[i][1:]) 80 report['model'].append(dict(name=name,exact_tree_match=True,reachable_dag_nodes=len(seen), 81 counters=dict(model.stats),binders=model.brackets)) 82 def run(label,name,raw,wanted,measure=False): 83 arg=root/(label+'.input.tree');arg.write_bytes(raw) 84 actual=runner.invoke(label,pin,name,['--arg-tree-file',arg]+(['--profile-full-result'] if measure else [])) 85 expect(actual,wanted,label) 86 if not measure:return 87 points={v['profile']:v for line in (root/(label+'.log')).read_text().splitlines() 88 if line.startswith('{') for v in [json.loads(line)]} 89 before,after=points['invoke-begin-1'],points['force-end-1'] 90 return dict(wall_ns=after['wall_ns']-before['wall_ns'],allocated_bytes=after['allocated_bytes']-before['allocated_bytes']) 91 for role in ['Bound','Inline']: 92 for name,wanted in [('unusedDemand',TRUE),('unselectedDemand',LEAF),('branchDemand',TRUE)]: 93 run('demand-'+name+role,name+role,LEAF,wanted) 94 report['demand'].append(dict(name=name+role,outcome='expected-result')) 95 name='selectedDemand'+role 96 try: 97 run('demand-'+name,name,LEAF,LEAF) 98 raise AssertionError('selected divergent branch returned') 99 except RuntimeError as error: 100 if str(error)!='wall-time guard exceeded':raise 101 report['demand'].append(dict(name=name,outcome='timeout',seconds=3)) 102 # Eta-equivalent applications need not have the same inspectable tree. 103 eta_results={} 104 for name in ['etaExpanded','etaContracted']: 105 model=Model(intern,globals) 106 value=model.tree_apply(globals[name],model.leaf) 107 output=bytearray();todo=[value] 108 while todo: 109 node=intern.nodes[todo.pop()];output.append(node[0]);todo.extend(reversed(node[1:])) 110 run('eta-tree-'+name,name,LEAF,bytes(output)) 111 run('eta-apply-'+name,name+'Applied',TRUE,b'\1'+TRUE) 112 eta_results[name]=dict(root_tag=output[0],tree_sha256=hashlib.sha256(output).hexdigest()) 113 assert eta_results['etaExpanded']['root_tag']!=eta_results['etaContracted']['root_tag'] 114 report['eta_control']=eta_results 115 # Do not assume beta substitution preserves returned-function observations. 116 # Inline closure construction has a finite exact-tree oracle. The bound 117 # closure contains a shared computation; rendering forces it. 118 model=Model(intern,globals) 119 finite=model.tree_apply(globals['closureInline'],model.leaf) 120 output=bytearray();todo=[finite] 121 while todo: 122 node=intern.nodes[todo.pop()];output.append(node[0]);todo.extend(reversed(node[1:])) 123 run('demand-closureInline','closureInline',LEAF,bytes(output)) 124 report['demand'].append(dict(name='closureInline',outcome='expected-finite-function-tree', 125 tree_sha256=hashlib.sha256(output).hexdigest(),tree_bytes=len(output))) 126 for name in ['closureBound','invokeClosureBound','invokeClosureInline']: 127 try: 128 run('demand-'+name,name,LEAF,LEAF) 129 raise AssertionError('expected closed-computation demand did not occur') 130 except RuntimeError as error: 131 if str(error)!='wall-time guard exceeded':raise 132 report['demand'].append(dict(name=name,outcome='timeout',seconds=3)) 133 for role in ['Bound','Inline']: 134 for a in range(2): 135 for b in range(2): 136 for c in range(2): 137 argv=[] 138 for i,n in enumerate([a,b,c]): 139 arg=root/f'adder-{i}.tree';arg.write_bytes(TRUE if n else LEAF) 140 argv += ['--arg-tree-file',arg] 141 total=a+b+c 142 expect(runner.invoke(f'adder-{role}-{a}{b}{c}',pin,'adder'+role,argv), 143 pair(TRUE if total%2 else LEAF,TRUE if total>=2 else LEAF),'adder') 144 report['adder_truth_table_cases']=16 145 schedule=[] 146 # All four Boolean combinations, repeated at two batch sizes. 147 for size in [128,1024]: 148 values=[(bool(i%2),bool((i//2)%2)) for i in range(size)] 149 raw=tree_list([pair(TRUE if f else LEAF,TRUE if x else LEAF) for f,x in values]) 150 for group in ['single','branch','constructor']: 151 out=[] 152 for f,x in values: 153 v=TRUE if x else LEAF 154 z=(b'\1'+v) if group=='constructor' else (LEAF if x else TRUE) 155 out.append(pair(z,v) if group=='single' or f else pair(v,z)) 156 for role in ['Bound','Inline']: 157 schedule.append((group,size,'run'+group+role,raw,tree_list(out))) 158 for size in [16,128,512]: 159 # Full duplicated output, so both copies are genuinely demanded. 160 xs=nat(list(range(size))) 161 copied=tree_list([b'\1'+nat(n) for n in range(size)]) 162 for role in ['Bound','Inline']: 163 schedule.append(('shared',size,'shared'+role,xs,pair(copied,copied))) 164 rng=random.Random(4096) 165 for repeat in range(args.repeats): 166 rng.shuffle(schedule) 167 for group,size,name,raw,wanted in schedule: 168 sample=run(f'{group}-{size}-{name}-{repeat}',name,raw,wanted,True) 169 report['samples'].append(dict(group=group,size=size,name=name,repeat=repeat,warmup=repeat==0,**sample)) 170 for group,size,name,_,_ in sorted(schedule): 171 rows=[s for s in report['samples'] if s['group']==group and s['size']==size and s['name']==name and not s['warmup']] 172 row=dict(group=group,size=size,name=name) 173 for key in ['wall_ns','allocated_bytes']: 174 row[key]=statistics.median(s[key] for s in rows) 175 row[key+'_min']=min(s[key] for s in rows);row[key+'_max']=max(s[key] for s in rows) 176 report['summaries'].append(row);print(json.dumps(row),flush=True) 177 report['complete']=True 178 finally:(root/'report.json').write_text(json.dumps(report,indent=2)+'\n') 179 180 181 if __name__=='__main__':main()