Compare commits
21 Commits
| Author | SHA1 | Date | |
|---|---|---|---|
| ded6ca546f | |||
| b5b96c05ed | |||
| c79033b749 | |||
| 1119295238 | |||
| 9c07970943 | |||
| 0832865952 | |||
| e0b2c0ea54 | |||
| cf060adbfd | |||
| 63fe8a766d | |||
| b5a0a729e6 | |||
| b26dd47aef | |||
| b55e6bfd53 | |||
| dbb06f6ee4 | |||
| 906c664a65 | |||
| 6a6b589ba0 | |||
| b5d1e53902 | |||
| 9e96d74f6a | |||
| a8908908df | |||
| 6291a35bb9 | |||
| a69a4a5894 | |||
| 4c3414072b |
@@ -61,6 +61,13 @@ Per test file, current build model:
|
|||||||
| `cc` test .c → .o | 0.02s |
|
| `cc` test .c → .o | 0.02s |
|
||||||
| link | 0.02s |
|
| link | 0.02s |
|
||||||
|
|
||||||
|
> **STALE as of el #132 — re-measured 2026-08-16.** The `test_compiler` figure below was
|
||||||
|
> *entirely* the `strlen`-per-character quadratic, now fixed. Re-measured on the same host:
|
||||||
|
> **3.58s → 0.03s (119x)**, and the 422 KB compiler concatenation likewise compiles in 0.03s.
|
||||||
|
> The table is retained only as the historical record that motivated the gate. The remaining
|
||||||
|
> per-file cost is the redundant `el_runtime.c` rebuild, which §9's compile-once architecture
|
||||||
|
> addresses.
|
||||||
|
|
||||||
Per-file `elc` time across the existing suite:
|
Per-file `elc` time across the existing suite:
|
||||||
|
|
||||||
| File | Bytes | elc time |
|
| File | Bytes | elc time |
|
||||||
@@ -416,6 +423,48 @@ Wall-clock needs statistics. **Allocation counts do not.** They are perfectly de
|
|||||||
> a level. That is why the gate fits a curve across a sweep instead of comparing one number to a
|
> a level. That is why the gate fits a curve across a sweep instead of comparing one number to a
|
||||||
> threshold.
|
> threshold.
|
||||||
|
|
||||||
|
> **Second correction, same day — THE ALLOCATION GATE ALONE WOULD HAVE MISSED THE REAL BUG.**
|
||||||
|
>
|
||||||
|
> el #132 found the actual elc quadratic: `strlen()` called inside `str_char_code()` and
|
||||||
|
> `str_slice()`, so the lexer rescanned the remaining input on every character. Pure CPU.
|
||||||
|
> **Zero allocation.** `str_char_code` is a bounds check and an index — it allocates nothing.
|
||||||
|
>
|
||||||
|
> Measured on three controlled specimens (`lang/.work/fitprobe.el`), growth ratio per doubling of
|
||||||
|
> n across n = 200/400/800/1600:
|
||||||
|
>
|
||||||
|
> | specimen | allocs | bytes | time | what it proves |
|
||||||
|
> |---|---|---|---|---|
|
||||||
|
> | `linear` — one alloc per item | 2.00 2.00 2.00 → **O(n)** | 2.16 2.07 2.23 → **O(n)** | 0.83 2.00 2.05 → **O(n)** | clean baseline |
|
||||||
|
> | `accum` — rebuilds accumulator | 2.00 2.00 2.00 → **O(n)** | 3.97 3.99 3.99 → **O(n²)** | noisy | count misses, **bytes catches** |
|
||||||
|
> | `compute` — n scans over n chars | 0 → **FLAT** | 0 → **FLAT** | 3.93 4.01 3.96 → **O(n²)** | **both alloc signals blind; only time catches** |
|
||||||
|
>
|
||||||
|
> `compute` is el #132's shape exactly. A gate fitting only allocation count and bytes classifies
|
||||||
|
> it as FLAT and passes it. **The gate as originally specified would not have caught the defect it
|
||||||
|
> was created for.**
|
||||||
|
>
|
||||||
|
> Therefore the gate fits **THREE** signals and fails if ANY exceeds its declared curve:
|
||||||
|
>
|
||||||
|
> ```
|
||||||
|
> bench "elc_compile" over n in [...] expect time O(n) allocs O(n) bytes O(n) { ... }
|
||||||
|
> ```
|
||||||
|
>
|
||||||
|
> - **allocs (count)** — deterministic, zero-noise. Catches per-item allocation growth.
|
||||||
|
> - **allocs (bytes)** — deterministic, zero-noise. Catches accumulator-rebuild quadratics that
|
||||||
|
> count cannot see.
|
||||||
|
> - **time** — noisy, needs the sweep and statistics. The ONLY signal that sees pure-compute
|
||||||
|
> complexity regressions. Gate on the fitted *exponent*, never on absolute duration, so CI
|
||||||
|
> hardware variance scales the coefficient and leaves the classification intact.
|
||||||
|
>
|
||||||
|
> The deterministic signals remain preferable where they apply — they need no statistics and are
|
||||||
|
> correct on the first run. They are simply not sufficient.
|
||||||
|
>
|
||||||
|
> **`black_box` is mandatory, and consuming the result is NOT enough.** The first version of
|
||||||
|
> `compute` accumulated `total + 1` in a nested loop and reported **0 µs at every n** while
|
||||||
|
> returning a numerically correct n². Clang recognised the idiom and closed the loop to a
|
||||||
|
> multiply. Feeding the result into output did not prevent it. Only making the inner operation an
|
||||||
|
> opaque external call restored the real curve. A benchmark harness that trusts the user to defeat
|
||||||
|
> the optimiser will silently measure nothing — and report success while doing it.
|
||||||
|
|
||||||
Instrument the runtime with allocation counters and fit *those* against n instead of time:
|
Instrument the runtime with allocation counters and fit *those* against n instead of time:
|
||||||
|
|
||||||
```el
|
```el
|
||||||
|
|||||||
+26
-1
@@ -288,6 +288,27 @@ fn route_create_node(method: String, path: String, body: String) -> String {
|
|||||||
salience, importance, confidence,
|
salience, importance, confidence,
|
||||||
tier, tags
|
tier, tags
|
||||||
)
|
)
|
||||||
|
// GEOMETRY INGEST (2026-08-16 self-review): this route accepted an "emb"
|
||||||
|
// field, returned 200 with a fresh id, and stored NOTHING — engram_node_full
|
||||||
|
// has no vector parameter, so the caller's geometry was silently discarded
|
||||||
|
// and the node came back emb_dim=None / embedded:false. Measured live while
|
||||||
|
// trying to admit a voice signal. The consequence was structural, not
|
||||||
|
// cosmetic: text was the only entry medium, so any non-text modality had to
|
||||||
|
// be DESCRIBED in prose and what we then reasoned over was the geometry of
|
||||||
|
// the description, not of the signal.
|
||||||
|
//
|
||||||
|
// "emb" is little-endian float32 hex (dim*8 chars) — the encoding the
|
||||||
|
// perception vessel's /voice/embed already emits, so a realizer's output
|
||||||
|
// moves in with no float-array round trip. "dim" defaults to the vector's
|
||||||
|
// implied width. Off-dimension vectors are stored but not inserted into the
|
||||||
|
// resident index (its build loop filters on emb_dim), so a modality vector
|
||||||
|
// is durable and addressable without perturbing the canonical index.
|
||||||
|
let emb_hex: String = json_get_string(body, "emb")
|
||||||
|
let emb_set: Int = if str_eq(emb_hex, "") { 0 } else {
|
||||||
|
let dim_raw: String = json_get_raw(body, "dim")
|
||||||
|
let dim: Int = if str_eq(dim_raw, "") { str_len(emb_hex) / 8 } else { json_get_int(body, "dim") }
|
||||||
|
engram_node_set_emb(id, emb_hex, dim)
|
||||||
|
}
|
||||||
let saved: Int = persist_node(id)
|
let saved: Int = persist_node(id)
|
||||||
// ORPHAN PREVENTION (ENGRAM_AUTOCONNECT): connect the fresh node to its
|
// ORPHAN PREVENTION (ENGRAM_AUTOCONNECT): connect the fresh node to its
|
||||||
// nearest embedded neighbors so it never enters the graph edgeless.
|
// nearest embedded neighbors so it never enters the graph edgeless.
|
||||||
@@ -298,7 +319,11 @@ fn route_create_node(method: String, path: String, body: String) -> String {
|
|||||||
if added > 0 { let sv2: Int = persist_edges_since(ec0) }
|
if added > 0 { let sv2: Int = persist_edges_since(ec0) }
|
||||||
added
|
added
|
||||||
} else { 0 }
|
} else { 0 }
|
||||||
"{\"id\":\"" + id + "\",\"content\":\"" + content + "\",\"node_type\":\"" + node_type + "\",\"connected\":" + int_to_str(connected) + "}"
|
// Report whether the supplied geometry actually landed. The old response
|
||||||
|
// was success-shaped regardless — 200 with an id while the vector was
|
||||||
|
// discarded — which is how the drop went unnoticed. A caller can now
|
||||||
|
// assert on emb_set instead of trusting the status code.
|
||||||
|
"{\"id\":\"" + id + "\",\"content\":\"" + content + "\",\"node_type\":\"" + node_type + "\",\"connected\":" + int_to_str(connected) + ",\"emb_set\":" + int_to_str(emb_set) + "}"
|
||||||
}
|
}
|
||||||
|
|
||||||
fn route_get_node(method: String, path: String, body: String) -> String {
|
fn route_get_node(method: String, path: String, body: String) -> String {
|
||||||
|
|||||||
@@ -862,10 +862,23 @@ fn cg_expr(expr: Map<String, Any>) -> String {
|
|||||||
// arithmetic BinOp (or vice-versa). Without this check the
|
// arithmetic BinOp (or vice-versa). Without this check the
|
||||||
// fallthrough to str_eq produces str_eq(int_value, int_value)
|
// fallthrough to str_eq produces str_eq(int_value, int_value)
|
||||||
// which reads the integer as a char* and segfaults.
|
// which reads the integer as a char* and segfaults.
|
||||||
|
// EITHER side provably Int is enough. Requiring BOTH meant a call
|
||||||
|
// whose return type codegen cannot infer poisoned the operator:
|
||||||
|
// getint(5) == a -> str_eq(getint(5), a)
|
||||||
|
// even with `a` declared Int. str_eq then reads an integer as a
|
||||||
|
// char* and segfaults. Only an integer LITERAL on one side forced
|
||||||
|
// the numeric form, so the bug was invisible in the common case.
|
||||||
|
//
|
||||||
|
// Loosening to OR is strictly safer: when one side is a known Int,
|
||||||
|
// str_eq is always wrong (it dereferences that int), while numeric
|
||||||
|
// comparison is at worst a wrong answer on an already ill-typed
|
||||||
|
// program. When neither side is Int nothing changes, so string
|
||||||
|
// comparison is untouched.
|
||||||
if is_int_expr(left) {
|
if is_int_expr(left) {
|
||||||
if is_int_expr(right) {
|
return "(" + left_c + " == " + right_c + ")"
|
||||||
return "(" + left_c + " == " + right_c + ")"
|
}
|
||||||
}
|
if is_int_expr(right) {
|
||||||
|
return "(" + left_c + " == " + right_c + ")"
|
||||||
}
|
}
|
||||||
// Float literal or negative float literal: use plain == (bit-equal
|
// Float literal or negative float literal: use plain == (bit-equal
|
||||||
// el_val_t comparison). This handles `r0 == 3.0`, `neg == -3.0`, etc.
|
// el_val_t comparison). This handles `r0 == 3.0`, `neg == -3.0`, etc.
|
||||||
@@ -921,10 +934,12 @@ fn cg_expr(expr: Map<String, Any>) -> String {
|
|||||||
}
|
}
|
||||||
// Same mixed Ident/BinOp fix as EqEq: use is_int_expr to detect
|
// Same mixed Ident/BinOp fix as EqEq: use is_int_expr to detect
|
||||||
// integer-typed operands before falling through to !str_eq.
|
// integer-typed operands before falling through to !str_eq.
|
||||||
|
// Either side Int is enough — see the EqEq note above.
|
||||||
if is_int_expr(left) {
|
if is_int_expr(left) {
|
||||||
if is_int_expr(right) {
|
return "(" + left_c + " != " + right_c + ")"
|
||||||
return "(" + left_c + " != " + right_c + ")"
|
}
|
||||||
}
|
if is_int_expr(right) {
|
||||||
|
return "(" + left_c + " != " + right_c + ")"
|
||||||
}
|
}
|
||||||
// Float-typed operands use plain != (bit-equal comparison).
|
// Float-typed operands use plain != (bit-equal comparison).
|
||||||
if is_float_expr(left) {
|
if is_float_expr(left) {
|
||||||
@@ -1495,6 +1510,11 @@ fn cg_stmt(stmt: Map<String, Any>, indent: String, declared: [String]) -> [Strin
|
|||||||
if str_eq(ltype, "Int") {
|
if str_eq(ltype, "Int") {
|
||||||
add_int_name(name)
|
add_int_name(name)
|
||||||
}
|
}
|
||||||
|
// Same as params: Bool is an int in the value model. Without this a
|
||||||
|
// `let ok: Bool = ...` compared to another Bool lowered to str_eq.
|
||||||
|
if str_eq(ltype, "Bool") {
|
||||||
|
add_int_name(name)
|
||||||
|
}
|
||||||
if str_eq(ltype, "Float") {
|
if str_eq(ltype, "Float") {
|
||||||
add_float_name(name)
|
add_float_name(name)
|
||||||
}
|
}
|
||||||
@@ -2887,6 +2907,7 @@ fn builtin_arity(name: String) -> Int {
|
|||||||
if str_eq(name, "el_alloc_count") { return 0 }
|
if str_eq(name, "el_alloc_count") { return 0 }
|
||||||
if str_eq(name, "el_alloc_bytes") { return 0 }
|
if str_eq(name, "el_alloc_bytes") { return 0 }
|
||||||
if str_eq(name, "el_peak_rss") { return 0 }
|
if str_eq(name, "el_peak_rss") { return 0 }
|
||||||
|
if str_eq(name, "el_black_box") { return 1 }
|
||||||
if str_eq(name, "engram_neighbors_json") { return 3 }
|
if str_eq(name, "engram_neighbors_json") { return 3 }
|
||||||
if str_eq(name, "engram_activate_json") { return 2 }
|
if str_eq(name, "engram_activate_json") { return 2 }
|
||||||
if str_eq(name, "engram_stats_json") { return 0 }
|
if str_eq(name, "engram_stats_json") { return 0 }
|
||||||
@@ -3112,6 +3133,15 @@ fn build_int_names_for_params(params: [Map<String, Any>]) -> Bool {
|
|||||||
if str_eq(ptype, "Int") {
|
if str_eq(ptype, "Int") {
|
||||||
add_int_name(pname)
|
add_int_name(pname)
|
||||||
}
|
}
|
||||||
|
// Bool is an integer in the value model (type_to_c maps Bool -> "int";
|
||||||
|
// el_runtime.h: "Bool -> el_val_t (0 = false, nonzero = true)"), but
|
||||||
|
// Bool names were registered nowhere. So `cond == want` between two
|
||||||
|
// Bool params fell through to str_eq and dereferenced 0 or 1 as a
|
||||||
|
// char* — an immediate segfault. Track them as int-like, which is what
|
||||||
|
// they are.
|
||||||
|
if str_eq(ptype, "Bool") {
|
||||||
|
add_int_name(pname)
|
||||||
|
}
|
||||||
if str_eq(ptype, "Float") {
|
if str_eq(ptype, "Float") {
|
||||||
add_float_name(pname)
|
add_float_name(pname)
|
||||||
}
|
}
|
||||||
|
|||||||
@@ -419,6 +419,22 @@ fn resolve_imports(src_path: String) -> String {
|
|||||||
if !str_eq(already, "") { return "" }
|
if !str_eq(already, "") { return "" }
|
||||||
state_set(seen_key, "1")
|
state_set(seen_key, "1")
|
||||||
|
|
||||||
|
// A missing file must be a hard error, never an empty string.
|
||||||
|
//
|
||||||
|
// fs_read returns "" both for "file is empty" and "file does not exist", and
|
||||||
|
// this function used the value without distinguishing them. So a broken
|
||||||
|
// import path — a typo, a moved file, a relative path resolved from the
|
||||||
|
// wrong working directory — compiled CLEANLY: exit 0, empty stderr, and a
|
||||||
|
// program silently missing everything it imported. Observed 2026-08-15:
|
||||||
|
// eleven consecutive "successful" compiles that had included no runtime at
|
||||||
|
// all, and a wrong conclusion drawn from them before anyone noticed.
|
||||||
|
//
|
||||||
|
// Missing dependency, confident success. fs_exists separates the two cases,
|
||||||
|
// so a genuinely empty file still resolves to "" and is fine.
|
||||||
|
if !fs_exists(src_path) {
|
||||||
|
println("elc: cannot resolve import: " + src_path)
|
||||||
|
exit_program(1)
|
||||||
|
}
|
||||||
let source: String = fs_read(src_path)
|
let source: String = fs_read(src_path)
|
||||||
let dir: String = dirname_of(src_path)
|
let dir: String = dirname_of(src_path)
|
||||||
let lines: [String] = str_split(source, "\n")
|
let lines: [String] = str_split(source, "\n")
|
||||||
|
|||||||
+187
-4
@@ -476,12 +476,14 @@ typedef struct {
|
|||||||
static ElList* list_alloc(int64_t cap) {
|
static ElList* list_alloc(int64_t cap) {
|
||||||
if (cap < 4) cap = 4;
|
if (cap < 4) cap = 4;
|
||||||
ElList* lst = malloc(sizeof(ElList));
|
ElList* lst = malloc(sizeof(ElList));
|
||||||
|
_el_alloc_count++; _el_alloc_bytes += sizeof(ElList);
|
||||||
if (!lst) { fputs("el_runtime: out of memory\n", stderr); exit(1); }
|
if (!lst) { fputs("el_runtime: out of memory\n", stderr); exit(1); }
|
||||||
lst->hdr.magic = EL_MAGIC_LIST;
|
lst->hdr.magic = EL_MAGIC_LIST;
|
||||||
lst->hdr.refcount = 1;
|
lst->hdr.refcount = 1;
|
||||||
lst->length = 0;
|
lst->length = 0;
|
||||||
lst->capacity = cap;
|
lst->capacity = cap;
|
||||||
lst->elems = malloc((size_t)cap * sizeof(el_val_t));
|
lst->elems = malloc((size_t)cap * sizeof(el_val_t));
|
||||||
|
_el_alloc_count++; _el_alloc_bytes += (size_t)cap * sizeof(el_val_t);
|
||||||
if (!lst->elems) { fputs("el_runtime: out of memory\n", stderr); exit(1); }
|
if (!lst->elems) { fputs("el_runtime: out of memory\n", stderr); exit(1); }
|
||||||
return lst;
|
return lst;
|
||||||
}
|
}
|
||||||
@@ -531,6 +533,7 @@ el_val_t el_list_append(el_val_t listv, el_val_t elem) {
|
|||||||
if (old->length >= old->capacity) {
|
if (old->length >= old->capacity) {
|
||||||
int64_t new_cap = old->capacity > 0 ? old->capacity * 2 : 4;
|
int64_t new_cap = old->capacity > 0 ? old->capacity * 2 : 4;
|
||||||
el_val_t* grown = realloc(old->elems, (size_t)new_cap * sizeof(el_val_t));
|
el_val_t* grown = realloc(old->elems, (size_t)new_cap * sizeof(el_val_t));
|
||||||
|
_el_alloc_count++; _el_alloc_bytes += (size_t)new_cap * sizeof(el_val_t);
|
||||||
if (!grown) { fputs("el_runtime: out of memory\n", stderr); exit(1); }
|
if (!grown) { fputs("el_runtime: out of memory\n", stderr); exit(1); }
|
||||||
old->elems = grown;
|
old->elems = grown;
|
||||||
old->capacity = new_cap;
|
old->capacity = new_cap;
|
||||||
@@ -543,12 +546,14 @@ el_val_t el_list_append(el_val_t listv, el_val_t elem) {
|
|||||||
int64_t new_cap = old->length + 1;
|
int64_t new_cap = old->length + 1;
|
||||||
if (new_cap < 4) new_cap = 4;
|
if (new_cap < 4) new_cap = 4;
|
||||||
ElList* fresh = malloc(sizeof(ElList));
|
ElList* fresh = malloc(sizeof(ElList));
|
||||||
|
_el_alloc_count++; _el_alloc_bytes += sizeof(ElList);
|
||||||
if (!fresh) { fputs("el_runtime: out of memory\n", stderr); exit(1); }
|
if (!fresh) { fputs("el_runtime: out of memory\n", stderr); exit(1); }
|
||||||
fresh->hdr.magic = EL_MAGIC_LIST;
|
fresh->hdr.magic = EL_MAGIC_LIST;
|
||||||
fresh->hdr.refcount = 1;
|
fresh->hdr.refcount = 1;
|
||||||
fresh->length = old->length + 1;
|
fresh->length = old->length + 1;
|
||||||
fresh->capacity = new_cap;
|
fresh->capacity = new_cap;
|
||||||
fresh->elems = malloc((size_t)new_cap * sizeof(el_val_t));
|
fresh->elems = malloc((size_t)new_cap * sizeof(el_val_t));
|
||||||
|
_el_alloc_count++; _el_alloc_bytes += (size_t)new_cap * sizeof(el_val_t);
|
||||||
if (!fresh->elems) { fputs("el_runtime: out of memory\n", stderr); exit(1); }
|
if (!fresh->elems) { fputs("el_runtime: out of memory\n", stderr); exit(1); }
|
||||||
if (old->length > 0) {
|
if (old->length > 0) {
|
||||||
memcpy(fresh->elems, old->elems, (size_t)old->length * sizeof(el_val_t));
|
memcpy(fresh->elems, old->elems, (size_t)old->length * sizeof(el_val_t));
|
||||||
@@ -570,12 +575,14 @@ el_val_t el_list_clone(el_val_t listv) {
|
|||||||
if (cap < old->length) cap = old->length;
|
if (cap < old->length) cap = old->length;
|
||||||
if (cap < 4) cap = 4;
|
if (cap < 4) cap = 4;
|
||||||
ElList* fresh = malloc(sizeof(ElList));
|
ElList* fresh = malloc(sizeof(ElList));
|
||||||
|
_el_alloc_count++; _el_alloc_bytes += sizeof(ElList);
|
||||||
if (!fresh) { fputs("el_runtime: out of memory\n", stderr); exit(1); }
|
if (!fresh) { fputs("el_runtime: out of memory\n", stderr); exit(1); }
|
||||||
fresh->hdr.magic = EL_MAGIC_LIST;
|
fresh->hdr.magic = EL_MAGIC_LIST;
|
||||||
fresh->hdr.refcount = 1;
|
fresh->hdr.refcount = 1;
|
||||||
fresh->length = old->length;
|
fresh->length = old->length;
|
||||||
fresh->capacity = cap;
|
fresh->capacity = cap;
|
||||||
fresh->elems = malloc((size_t)cap * sizeof(el_val_t));
|
fresh->elems = malloc((size_t)cap * sizeof(el_val_t));
|
||||||
|
_el_alloc_count++; _el_alloc_bytes += (size_t)cap * sizeof(el_val_t);
|
||||||
if (!fresh->elems) { fputs("el_runtime: out of memory\n", stderr); exit(1); }
|
if (!fresh->elems) { fputs("el_runtime: out of memory\n", stderr); exit(1); }
|
||||||
if (old->length > 0) {
|
if (old->length > 0) {
|
||||||
memcpy(fresh->elems, old->elems, (size_t)old->length * sizeof(el_val_t));
|
memcpy(fresh->elems, old->elems, (size_t)old->length * sizeof(el_val_t));
|
||||||
@@ -596,6 +603,7 @@ typedef struct {
|
|||||||
static ElMap* map_alloc(int64_t cap) {
|
static ElMap* map_alloc(int64_t cap) {
|
||||||
if (cap < 4) cap = 4;
|
if (cap < 4) cap = 4;
|
||||||
ElMap* m = malloc(sizeof(ElMap));
|
ElMap* m = malloc(sizeof(ElMap));
|
||||||
|
_el_alloc_count++; _el_alloc_bytes += sizeof(ElMap);
|
||||||
if (!m) { fputs("el_runtime: out of memory\n", stderr); exit(1); }
|
if (!m) { fputs("el_runtime: out of memory\n", stderr); exit(1); }
|
||||||
m->hdr.magic = EL_MAGIC_MAP;
|
m->hdr.magic = EL_MAGIC_MAP;
|
||||||
m->hdr.refcount = 1;
|
m->hdr.refcount = 1;
|
||||||
@@ -671,6 +679,7 @@ el_val_t el_map_set(el_val_t mapv, el_val_t keyv, el_val_t value) {
|
|||||||
int64_t new_cap = m->count + 1;
|
int64_t new_cap = m->count + 1;
|
||||||
if (new_cap < 4) new_cap = 4;
|
if (new_cap < 4) new_cap = 4;
|
||||||
ElMap* fresh = malloc(sizeof(ElMap));
|
ElMap* fresh = malloc(sizeof(ElMap));
|
||||||
|
_el_alloc_count++; _el_alloc_bytes += sizeof(ElMap);
|
||||||
if (!fresh) { fputs("el_runtime: out of memory\n", stderr); exit(1); }
|
if (!fresh) { fputs("el_runtime: out of memory\n", stderr); exit(1); }
|
||||||
fresh->hdr.magic = EL_MAGIC_MAP;
|
fresh->hdr.magic = EL_MAGIC_MAP;
|
||||||
fresh->hdr.refcount = 1;
|
fresh->hdr.refcount = 1;
|
||||||
@@ -5159,10 +5168,23 @@ el_val_t state_get(el_val_t key) {
|
|||||||
if (!k) return el_wrap_str(el_strdup(""));
|
if (!k) return el_wrap_str(el_strdup(""));
|
||||||
pthread_mutex_lock(&_state_mu);
|
pthread_mutex_lock(&_state_mu);
|
||||||
StateEntry* e = state_find(k);
|
StateEntry* e = state_find(k);
|
||||||
char* result = el_strdup_persist(e ? e->value : "");
|
/* ONE arena-tracked copy, taken under the lock.
|
||||||
|
*
|
||||||
|
* This used to make TWO copies: an el_strdup_persist temporary, then an
|
||||||
|
* arena-tracked copy of that temporary. The persistent one was never
|
||||||
|
* returned and never freed — el_strdup_persist bypasses the arena by
|
||||||
|
* design ("state_set, engram internals"), so arena-pop could not reclaim
|
||||||
|
* it. Every state_get therefore leaked its full value string, permanently.
|
||||||
|
*
|
||||||
|
* The soul's awareness loop has 68 state_get call sites and ticks every
|
||||||
|
* 200ms; measured leak was ~1.1 MB per tick, about 19 GB/hour. It went
|
||||||
|
* unnoticed for as long as the soul restarted often enough to mask it.
|
||||||
|
*
|
||||||
|
* el_strdup tracks into the thread-local arena, which touches no shared
|
||||||
|
* state, so doing it under _state_mu is safe and removes the need for the
|
||||||
|
* temporary entirely. */
|
||||||
|
char* copy = el_strdup(e ? e->value : "");
|
||||||
pthread_mutex_unlock(&_state_mu);
|
pthread_mutex_unlock(&_state_mu);
|
||||||
/* wrap in arena-tracked copy for the caller's request lifetime */
|
|
||||||
char* copy = el_strdup(result);
|
|
||||||
return el_wrap_str(copy);
|
return el_wrap_str(copy);
|
||||||
}
|
}
|
||||||
|
|
||||||
@@ -8485,6 +8507,80 @@ el_val_t engram_node_count(void) {
|
|||||||
return (el_val_t)engram_get()->node_count;
|
return (el_val_t)engram_get()->node_count;
|
||||||
}
|
}
|
||||||
|
|
||||||
|
/* engram_node_set_emb — attach GEOMETRY to an existing node.
|
||||||
|
*
|
||||||
|
* WHY THIS EXISTS (2026-08-16). Until now no ingest path could carry a
|
||||||
|
* vector. engram_node / engram_node_full / engram_node_layered take text
|
||||||
|
* only, and the sole way a node acquired an embedding was
|
||||||
|
* engram_embed_backfill DERIVING one from n->content. That made text the
|
||||||
|
* mandatory entry medium: any non-text modality (audio, image, sensor)
|
||||||
|
* had to be described in prose first, and the geometry we then reasoned
|
||||||
|
* over was the geometry OF THE DESCRIPTION, not of the signal. Measured
|
||||||
|
* consequence: POST /api/nodes accepted an "emb" field, returned 200 with
|
||||||
|
* a fresh id, and stored emb_dim=None / embedded:false — the vector was
|
||||||
|
* silently discarded because no parameter existed to receive it.
|
||||||
|
*
|
||||||
|
* `hex` is little-endian float32, the encoding the perception vessel's
|
||||||
|
* /voice/embed already emits, so a realizer's output moves in without a
|
||||||
|
* JSON float-array round trip. Length must be exactly dim*8 hex chars.
|
||||||
|
*
|
||||||
|
* DIMENSION POLICY: dim need NOT equal the canonical text-embedding dim.
|
||||||
|
* A modality vector of a different width is stored and is simply not
|
||||||
|
* inserted into the resident HNSW index, whose build loop already filters
|
||||||
|
* on `n->emb_dim == dim`. So off-dimension geometry is durable and
|
||||||
|
* addressable without perturbing the canonical index.
|
||||||
|
*
|
||||||
|
* Setting emb also makes the node ineligible for embed_backfill (which
|
||||||
|
* only fills nodes with no emb), so a realizer's vector is never
|
||||||
|
* overwritten by a text-derived one.
|
||||||
|
*
|
||||||
|
* Returns 1 on success, 0 on unknown id / malformed hex / bad dim. */
|
||||||
|
el_val_t engram_node_set_emb(el_val_t id, el_val_t hex, el_val_t dim) {
|
||||||
|
const char* sid = EL_CSTR(id);
|
||||||
|
const char* sh = EL_CSTR(hex);
|
||||||
|
int32_t d = (int32_t)(int64_t)dim;
|
||||||
|
/* Bound the allocation. No max-dim constant existed because no caller
|
||||||
|
* could supply a dim before this function; 8192 is generous for any
|
||||||
|
* realizer (canonical text embeddings are 768, MFCC voice stats 64)
|
||||||
|
* while keeping a malformed `dim` from requesting an unbounded malloc. */
|
||||||
|
if (!sid || !*sid || !sh || d <= 0 || d > 8192) return (el_val_t)0;
|
||||||
|
|
||||||
|
size_t need = (size_t)d * 8u; /* 4 bytes → 8 hex chars per float */
|
||||||
|
if (strlen(sh) != need) return (el_val_t)0;
|
||||||
|
|
||||||
|
EngramNode* n = engram_find_node(sid);
|
||||||
|
if (!n) return (el_val_t)0;
|
||||||
|
|
||||||
|
float* v = (float*)malloc(sizeof(float) * (size_t)d);
|
||||||
|
if (!v) return (el_val_t)0;
|
||||||
|
|
||||||
|
for (int32_t i = 0; i < d; i++) {
|
||||||
|
uint32_t w = 0;
|
||||||
|
for (int k = 0; k < 8; k++) {
|
||||||
|
char c = sh[(size_t)i * 8u + (size_t)k];
|
||||||
|
uint32_t nib;
|
||||||
|
if (c >= '0' && c <= '9') nib = (uint32_t)(c - '0');
|
||||||
|
else if (c >= 'a' && c <= 'f') nib = (uint32_t)(c - 'a' + 10);
|
||||||
|
else if (c >= 'A' && c <= 'F') nib = (uint32_t)(c - 'A' + 10);
|
||||||
|
else { free(v); return (el_val_t)0; }
|
||||||
|
w = (w << 4) | nib;
|
||||||
|
}
|
||||||
|
/* Hex is emitted little-endian byte order; rebuild the word. */
|
||||||
|
uint32_t le = ((w & 0x000000FFu) << 24) | ((w & 0x0000FF00u) << 8) |
|
||||||
|
((w & 0x00FF0000u) >> 8) | ((w & 0xFF000000u) >> 24);
|
||||||
|
float f;
|
||||||
|
memcpy(&f, &le, sizeof(f));
|
||||||
|
v[i] = f;
|
||||||
|
}
|
||||||
|
|
||||||
|
free(n->emb);
|
||||||
|
n->emb = v;
|
||||||
|
n->emb_dim = d;
|
||||||
|
n->updated_at = engram_now_ms();
|
||||||
|
if (engram_store_enabled()) eg_store_put_node(n);
|
||||||
|
return (el_val_t)1;
|
||||||
|
}
|
||||||
|
|
||||||
/* ── Telemetry retention ────────────────────────────────────────────────────
|
/* ── Telemetry retention ────────────────────────────────────────────────────
|
||||||
* (2026-07-16 self-review) InternalStateEvent nodes are append-only telemetry
|
* (2026-07-16 self-review) InternalStateEvent nodes are append-only telemetry
|
||||||
* (heartbeat, curiosity_scan, engram_sync) written ~3/min by the awareness
|
* (heartbeat, curiosity_scan, engram_sync) written ~3/min by the awareness
|
||||||
@@ -11280,6 +11376,15 @@ static void engram_emit_node_json(JsonBuf* b, const EngramNode* n, int include_e
|
|||||||
snprintf(tmp, sizeof(tmp), ",\"wm_anchor\":%g", n->wm_anchor); jb_puts(b, tmp);
|
snprintf(tmp, sizeof(tmp), ",\"wm_anchor\":%g", n->wm_anchor); jb_puts(b, tmp);
|
||||||
snprintf(tmp, sizeof(tmp), ",\"base_level\":%g",
|
snprintf(tmp, sizeof(tmp), ",\"base_level\":%g",
|
||||||
engram_bll_base_level(n, engram_now_ms())); jb_puts(b, tmp);
|
engram_bll_base_level(n, engram_now_ms())); jb_puts(b, tmp);
|
||||||
|
/* GEOMETRY VISIBILITY (2026-08-16 self-review): the node document never
|
||||||
|
* said whether the node carried a vector, so a read-back could not tell
|
||||||
|
* "has geometry" from "text only". Not cosmetic — it is exactly how a
|
||||||
|
* real ingest drop and a mere reporting gap became indistinguishable,
|
||||||
|
* and I misdiagnosed one as the other for an hour. Always emit the width
|
||||||
|
* and the boolean; the vector itself stays behind include_emb since it
|
||||||
|
* is large and most callers do not want it inline. */
|
||||||
|
snprintf(tmp, sizeof(tmp), ",\"emb_dim\":%d,\"embedded\":%s",
|
||||||
|
(int)n->emb_dim, (n->emb && n->emb_dim > 0) ? "true" : "false"); jb_puts(b, tmp);
|
||||||
/* Base-level access history: chronological (oldest→newest) compact
|
/* Base-level access history: chronological (oldest→newest) compact
|
||||||
* string. Loaders replay it through engram_bll_record_access; absent
|
* string. Loaders replay it through engram_bll_record_access; absent
|
||||||
* field = empty ring (optimized-form fallback). (2026-07-22) */
|
* field = empty ring (optimized-form fallback). (2026-07-22) */
|
||||||
@@ -13670,7 +13775,65 @@ el_val_t engram_think_json(el_val_t seeds, el_val_t faculty) {
|
|||||||
if (!g) return eg_geo_err("geometry unavailable");
|
if (!g) return eg_geo_err("geometry unavailable");
|
||||||
CogStance st; cog_stance_init(&st, NULL, EL_CSTR(faculty), g->hub_id, NULL, g);
|
CogStance st; cog_stance_init(&st, NULL, EL_CSTR(faculty), g->hub_id, NULL, g);
|
||||||
GeoGradient grad;
|
GeoGradient grad;
|
||||||
if (engram_think(g, NULL, &st, &grad) != 0) { cog_stance_free(&st); engram_geo_free(g); return eg_geo_err("think failed"); }
|
|
||||||
|
/* ANCHOR THE READ (2026-08-16 self-review). This passed NULL, and NULL is
|
||||||
|
* not "no opinion" — engram_think re-origins at `anchor ? anchor :
|
||||||
|
* region->centroid`, so NULL means "read from the centroid", and the
|
||||||
|
* centroid is the ONE point where the gradient is zero by construction:
|
||||||
|
* r = x - centroid = 0, so every axis projection is 0, grad is 0, and
|
||||||
|
* direction takes the "at rest" branch. Measured consequence: EVERY
|
||||||
|
* faculty — reason, abduce, induce, plan, analogize — returned an
|
||||||
|
* identical null result, differing only in its label:
|
||||||
|
* {"direction":[0,0,...],"spread":0,"magnitude":1,"confidence":0.5}
|
||||||
|
* magnitude 1 is membership evaluated at the centroid, spread 0 is its
|
||||||
|
* distance to itself, and confidence 0.5 is the stance fallback. The
|
||||||
|
* geometry was never the problem — /api/drift computes real values
|
||||||
|
* (centroid_sep 0.104, core_disp 0.045) over the very same 87 members.
|
||||||
|
* Neuron could not think because the read was always taken from the
|
||||||
|
* region's own centre.
|
||||||
|
*
|
||||||
|
* The seeds choose WHICH region; they must also supply the VANTAGE it is
|
||||||
|
* read from. Anchor at the first resolvable embedded seed — the same seed
|
||||||
|
* eg_geo_build_desc infers `dim` from, so the two never disagree. A single
|
||||||
|
* seed still yields a real gradient because the descriptor expands to the
|
||||||
|
* seed's neighbourhood (87 members for the self anchor), so the seed's own
|
||||||
|
* position is distinct from the neighbourhood centroid.
|
||||||
|
*
|
||||||
|
* COPY the vector, never borrow it: g->nodes is realloc'd in place on
|
||||||
|
* append, so a borrowed EngramNode* is a dangling pointer across any
|
||||||
|
* concurrent write. 768 floats is 3 KB. */
|
||||||
|
float* anchor = NULL;
|
||||||
|
{
|
||||||
|
EngramStore* eg = engram_get();
|
||||||
|
const char* csv = EL_CSTR(seeds);
|
||||||
|
if (eg && csv) {
|
||||||
|
const char* p = csv;
|
||||||
|
while (*p && !anchor) {
|
||||||
|
while (*p == ' ' || *p == ',') p++;
|
||||||
|
const char* s = p;
|
||||||
|
while (*p && *p != ',') p++;
|
||||||
|
const char* e = p; while (e > s && e[-1] == ' ') e--;
|
||||||
|
if (e > s) {
|
||||||
|
char* id = strndup(s, (size_t)(e - s));
|
||||||
|
if (id) {
|
||||||
|
int64_t idx = engram_find_node_index(id);
|
||||||
|
if (idx >= 0 && idx < eg->node_count) {
|
||||||
|
EngramNode* n = &eg->nodes[idx];
|
||||||
|
if (n->emb && n->emb_dim == g->dim) {
|
||||||
|
anchor = malloc(sizeof(float) * (size_t)g->dim);
|
||||||
|
if (anchor) memcpy(anchor, n->emb,
|
||||||
|
sizeof(float) * (size_t)g->dim);
|
||||||
|
}
|
||||||
|
}
|
||||||
|
free(id);
|
||||||
|
}
|
||||||
|
}
|
||||||
|
}
|
||||||
|
}
|
||||||
|
}
|
||||||
|
|
||||||
|
if (engram_think(g, anchor, &st, &grad) != 0) { free(anchor); cog_stance_free(&st); engram_geo_free(g); return eg_geo_err("think failed"); }
|
||||||
|
free(anchor);
|
||||||
JsonBuf b; jb_init(&b); char t[256];
|
JsonBuf b; jb_init(&b); char t[256];
|
||||||
snprintf(t, sizeof t, "{\"faculty\":\"%s\",\"n_support\":%d,\"magnitude\":%.6g,\"spread\":%.6g,\"confidence\":%.6g,\"dim\":%d",
|
snprintf(t, sizeof t, "{\"faculty\":\"%s\",\"n_support\":%d,\"magnitude\":%.6g,\"spread\":%.6g,\"confidence\":%.6g,\"dim\":%d",
|
||||||
EL_CSTR(faculty), grad.n_support, grad.magnitude, grad.spread, grad.confidence, grad.dim);
|
EL_CSTR(faculty), grad.n_support, grad.magnitude, grad.spread, grad.confidence, grad.dim);
|
||||||
@@ -18513,6 +18676,26 @@ el_val_t engram_pool_stats_json(void) {
|
|||||||
el_val_t el_alloc_count(void) { return (el_val_t)(int64_t)_el_alloc_count; }
|
el_val_t el_alloc_count(void) { return (el_val_t)(int64_t)_el_alloc_count; }
|
||||||
el_val_t el_alloc_bytes(void) { return (el_val_t)(int64_t)_el_alloc_bytes; }
|
el_val_t el_alloc_bytes(void) { return (el_val_t)(int64_t)_el_alloc_bytes; }
|
||||||
|
|
||||||
|
/* el_black_box — optimisation barrier for benchmark bodies.
|
||||||
|
*
|
||||||
|
* WHY THIS IS NOT OPTIONAL. A benchmark whose result is unused is dead code,
|
||||||
|
* and CONSUMING THE RESULT IS NOT SUFFICIENT: clang recognises loop idioms and
|
||||||
|
* closes them to arithmetic. A nested `total = total + 1` loop measured at
|
||||||
|
* 0 microseconds for every n while returning a numerically correct n*n --
|
||||||
|
* the answer was right and the work never happened.
|
||||||
|
*
|
||||||
|
* That is the same failure shape as a test that never ran reporting pass. The
|
||||||
|
* harness must own the barrier rather than trusting the benchmark author to
|
||||||
|
* defeat the optimiser.
|
||||||
|
*
|
||||||
|
* The constraint "+r" forces the value through a register the compiler must
|
||||||
|
* treat as both read and written by opaque code; the "memory" clobber stops
|
||||||
|
* loads and stores being reordered across it or elided. Emits no instructions. */
|
||||||
|
el_val_t el_black_box(el_val_t v) {
|
||||||
|
__asm__ __volatile__("" : "+r"(v) : : "memory");
|
||||||
|
return v;
|
||||||
|
}
|
||||||
|
|
||||||
el_val_t el_peak_rss(void) {
|
el_val_t el_peak_rss(void) {
|
||||||
struct rusage ru;
|
struct rusage ru;
|
||||||
if (getrusage(RUSAGE_SELF, &ru) != 0) return (el_val_t)0;
|
if (getrusage(RUSAGE_SELF, &ru) != 0) return (el_val_t)0;
|
||||||
|
|||||||
@@ -613,6 +613,11 @@ void engram_strengthen(el_val_t node_id);
|
|||||||
void engram_forget(el_val_t node_id);
|
void engram_forget(el_val_t node_id);
|
||||||
el_val_t engram_prune_telemetry(el_val_t older_than_ms);
|
el_val_t engram_prune_telemetry(el_val_t older_than_ms);
|
||||||
el_val_t engram_node_count(void);
|
el_val_t engram_node_count(void);
|
||||||
|
/* Attach geometry to an existing node. `hex` is little-endian float32,
|
||||||
|
* exactly dim*8 hex chars — the encoding realizers already emit. Lets a
|
||||||
|
* non-text modality enter as geometry instead of being described in prose
|
||||||
|
* and embedded as its description. Returns 1 on success, 0 otherwise. */
|
||||||
|
el_val_t engram_node_set_emb(el_val_t id, el_val_t hex, el_val_t dim);
|
||||||
el_val_t engram_search(el_val_t query, el_val_t limit);
|
el_val_t engram_search(el_val_t query, el_val_t limit);
|
||||||
el_val_t engram_scan_nodes(el_val_t limit, el_val_t offset);
|
el_val_t engram_scan_nodes(el_val_t limit, el_val_t offset);
|
||||||
void engram_connect(el_val_t from_id, el_val_t to_id, el_val_t weight, el_val_t relation);
|
void engram_connect(el_val_t from_id, el_val_t to_id, el_val_t weight, el_val_t relation);
|
||||||
@@ -1022,6 +1027,7 @@ el_val_t el_mem_check(void);
|
|||||||
el_val_t el_alloc_count(void);
|
el_val_t el_alloc_count(void);
|
||||||
el_val_t el_alloc_bytes(void);
|
el_val_t el_alloc_bytes(void);
|
||||||
el_val_t el_peak_rss(void);
|
el_val_t el_peak_rss(void);
|
||||||
|
el_val_t el_black_box(el_val_t v);
|
||||||
|
|
||||||
/* Semantic retrieval surface. NOT interchangeable with engram_search_json,
|
/* Semantic retrieval surface. NOT interchangeable with engram_search_json,
|
||||||
* which is lexical by design — see the note at the definition. */
|
* which is lexical by design — see the note at the definition. */
|
||||||
|
|||||||
@@ -0,0 +1,256 @@
|
|||||||
|
// runtime/elbench.el — growth-curve classifier and complexity gate.
|
||||||
|
//
|
||||||
|
// Given a geometric sweep of input sizes and the measurements taken at each,
|
||||||
|
// classify the growth curve and decide whether it violates a declared bound.
|
||||||
|
//
|
||||||
|
// ── Why this exists ──────────────────────────────────────────────────────────
|
||||||
|
//
|
||||||
|
// Constant-factor regressions are annoying. Complexity regressions are outages.
|
||||||
|
// An O(n) lookup inside an O(n) loop is invisible at n=100 in a unit test and
|
||||||
|
// catastrophic at n=100000 in production. el #132 was exactly that: a strlen()
|
||||||
|
// inside a per-character accessor, quadratic, shipped for months.
|
||||||
|
//
|
||||||
|
// ── THREE signals, not one ───────────────────────────────────────────────────
|
||||||
|
//
|
||||||
|
// The gate fits time AND allocation-count AND allocation-bytes, and fails if
|
||||||
|
// ANY of them exceeds its declared curve. This is not belt-and-braces; each
|
||||||
|
// signal is blind to a real defect class the others catch:
|
||||||
|
//
|
||||||
|
// * A copy-on-write accumulator rebuilding its buffer allocates ONCE per
|
||||||
|
// iteration — count is exactly linear — while bytes go quadratic.
|
||||||
|
// Count alone passes it.
|
||||||
|
// * el #132's strlen-per-character is pure CPU and allocates NOTHING.
|
||||||
|
// Both allocation signals read FLAT. Only time catches it.
|
||||||
|
//
|
||||||
|
// The deterministic signals (count, bytes) are preferable where they apply:
|
||||||
|
// no statistics, correct on the first run, machine-independent. They are
|
||||||
|
// simply not sufficient.
|
||||||
|
//
|
||||||
|
// ── SCOPE LIMIT — read this before trusting a flat curve ─────────────────────
|
||||||
|
//
|
||||||
|
// The allocation counters track EL-LEVEL allocation only: strings, ElList and
|
||||||
|
// ElMap bodies, their backing arrays, copy-on-write clones, and the realloc
|
||||||
|
// growth path. malloc inside engram_*.c and inside libcurl is NOT counted.
|
||||||
|
//
|
||||||
|
// A flat allocation curve over a workload dominated by engram or HTTP calls is
|
||||||
|
// therefore NOT evidence of anything. It means "no El-level allocation growth",
|
||||||
|
// not "no allocation growth". Gate El-level complexity with this; do not read
|
||||||
|
// third-party memory behaviour into it.
|
||||||
|
//
|
||||||
|
// ── Classification method ────────────────────────────────────────────────────
|
||||||
|
//
|
||||||
|
// Sizes must form a geometric sweep (each n double the last). On such a sweep
|
||||||
|
// the ratio between consecutive measurements IS the growth exponent, directly:
|
||||||
|
//
|
||||||
|
// O(1) -> 1.0 O(log n) -> ~1.1 O(n) -> 2.0
|
||||||
|
// O(n log n) -> ~2.2 O(n^2) -> 4.0 O(n^3) -> 8.0
|
||||||
|
//
|
||||||
|
// DEVIATION FROM DESIGN.md 6.2, stated plainly: that section specified Google
|
||||||
|
// Benchmark's one-parameter least-squares fit over candidate curves. This uses
|
||||||
|
// consecutive ratios instead. The sweep is mandated geometric either way, and
|
||||||
|
// on a geometric sweep ratios are directly interpretable and need no floating
|
||||||
|
// point. The cost is weaker separation between O(n) and O(n log n), which is
|
||||||
|
// reported honestly as an ambiguous band rather than guessed at. Least-squares
|
||||||
|
// remains the better answer if that band ever needs to be resolved.
|
||||||
|
//
|
||||||
|
// All arithmetic is fixed-point, scaled by 1000 ("milli-ratio"), so a ratio of
|
||||||
|
// 2.0 is 2000. El values are int64; this avoids float-in-list handling.
|
||||||
|
|
||||||
|
// Curve identifiers. Ordered by growth — the ordering IS the comparison used
|
||||||
|
// by the gate, so an index comparison decides "worse than declared".
|
||||||
|
// 0 = O(1) 1 = O(log n) 2 = O(n) 3 = O(n log n) 4 = O(n^2) 5 = O(n^3)
|
||||||
|
|
||||||
|
fn elb_curve_name(c: Int) -> String {
|
||||||
|
if c == 0 { return "O(1)" }
|
||||||
|
if c == 1 { return "O(log n)" }
|
||||||
|
if c == 2 { return "O(n)" }
|
||||||
|
if c == 3 { return "O(n log n)" }
|
||||||
|
if c == 4 { return "O(n^2)" }
|
||||||
|
if c == 5 { return "O(n^3)" }
|
||||||
|
return "O(?)"
|
||||||
|
}
|
||||||
|
|
||||||
|
fn elb_curve_from_name(s: String) -> Int {
|
||||||
|
if str_eq(s, "O(1)") { return 0 }
|
||||||
|
if str_eq(s, "O(log n)") { return 1 }
|
||||||
|
if str_eq(s, "O(n)") { return 2 }
|
||||||
|
if str_eq(s, "O(n log n)") { return 3 }
|
||||||
|
if str_eq(s, "O(n^2)") { return 4 }
|
||||||
|
if str_eq(s, "O(n^3)") { return 5 }
|
||||||
|
return -1
|
||||||
|
}
|
||||||
|
|
||||||
|
// elb_classify_ratio — map a milli-ratio-per-doubling onto a curve.
|
||||||
|
//
|
||||||
|
// Bands are deliberately wide at the top (a quadratic measured at 3.4x is
|
||||||
|
// still a quadratic) and deliberately overlap-averse at the bottom, where a
|
||||||
|
// misclassification between O(1) and O(log n) matters least.
|
||||||
|
fn elb_classify_ratio(milli: Int) -> Int {
|
||||||
|
if milli < 1300 { return 0 }
|
||||||
|
if milli < 1700 { return 1 }
|
||||||
|
if milli < 2400 { return 2 }
|
||||||
|
if milli < 3200 { return 3 }
|
||||||
|
if milli < 6000 { return 4 }
|
||||||
|
return 5
|
||||||
|
}
|
||||||
|
|
||||||
|
// elb_ratio — milli-ratio between two consecutive measurements.
|
||||||
|
// Returns -1 when the earlier measurement is zero (ratio undefined).
|
||||||
|
fn elb_ratio(prev: Int, cur: Int) -> Int {
|
||||||
|
if prev <= 0 { return -1 }
|
||||||
|
return (cur * 1000) / prev
|
||||||
|
}
|
||||||
|
|
||||||
|
// ── The measurement floor ────────────────────────────────────────────────────
|
||||||
|
//
|
||||||
|
// A benchmark whose largest measurement is at or near zero has not been
|
||||||
|
// measured. Reporting it as O(1) would be a confident answer with nothing
|
||||||
|
// behind it — the same failure as a test that never ran reporting pass, and
|
||||||
|
// exactly what happened when clang closed a nested loop to a multiply and the
|
||||||
|
// harness read 0 microseconds at every n.
|
||||||
|
//
|
||||||
|
// So: REFUSE. Never classify below the floor.
|
||||||
|
fn elb_below_floor(vals: [Int], floor: Int) -> Bool {
|
||||||
|
let n: Int = native_list_len(vals)
|
||||||
|
let i: Int = 0
|
||||||
|
let mx: Int = 0
|
||||||
|
while i < n {
|
||||||
|
let v: Int = native_list_get(vals, i)
|
||||||
|
if v > mx { let mx = v }
|
||||||
|
let i = i + 1
|
||||||
|
}
|
||||||
|
if mx < floor { return true }
|
||||||
|
return false
|
||||||
|
}
|
||||||
|
|
||||||
|
// elb_implausibly_flat — a measurement that does not move across a sweep whose
|
||||||
|
// input grew by 8x or more is not a flat curve, it is a broken measurement.
|
||||||
|
// Genuine O(1) work still shows noise; a hard-flat series means the work was
|
||||||
|
// optimised away, the timer has insufficient resolution, or the benchmark body
|
||||||
|
// never executed.
|
||||||
|
fn elb_implausibly_flat(vals: [Int]) -> Bool {
|
||||||
|
let n: Int = native_list_len(vals)
|
||||||
|
if n < 3 { return false }
|
||||||
|
let first: Int = native_list_get(vals, 0)
|
||||||
|
let last: Int = native_list_get(vals, n - 1)
|
||||||
|
if first == 0 {
|
||||||
|
if last == 0 { return true }
|
||||||
|
return false
|
||||||
|
}
|
||||||
|
let r: Int = (last * 1000) / first
|
||||||
|
if r < 1100 { return true }
|
||||||
|
return false
|
||||||
|
}
|
||||||
|
|
||||||
|
// elb_spread_ok — do the consecutive ratios agree with each other?
|
||||||
|
//
|
||||||
|
// This is the ratio-method analogue of a normalised-RMS threshold. If the
|
||||||
|
// doublings disagree wildly the data is noise, a cache cliff, or a phase
|
||||||
|
// change, and the honest report is INDETERMINATE rather than a classification.
|
||||||
|
// Applies to the ASYMPTOTIC TAIL only — the last three ratios.
|
||||||
|
//
|
||||||
|
// The small-n end of any sweep is dominated by fixed overhead, cold caches and
|
||||||
|
// branch predictors that have not warmed. Measured on a genuinely linear
|
||||||
|
// character scan, the ratios ran 3.37, 2.92, 1.76, 1.65: the head looks
|
||||||
|
// quadratic, the tail is the truth. Checking spread across the whole sweep
|
||||||
|
// therefore rejects correct data. A complexity bound is an asymptotic claim, so
|
||||||
|
// it is judged on the asymptotic region — the same reason a benchmark harness
|
||||||
|
// discards warmup rather than averaging it in.
|
||||||
|
fn elb_spread_ok(ratios: [Int]) -> Bool {
|
||||||
|
let total: Int = native_list_len(ratios)
|
||||||
|
if total < 2 { return true }
|
||||||
|
let start: Int = total - 3
|
||||||
|
if start < 0 { let start = 0 }
|
||||||
|
let n: Int = total
|
||||||
|
let lo: Int = 999999
|
||||||
|
let hi: Int = 0
|
||||||
|
let i: Int = start
|
||||||
|
while i < n {
|
||||||
|
let r: Int = native_list_get(ratios, i)
|
||||||
|
if r >= 0 {
|
||||||
|
if r < lo { let lo = r }
|
||||||
|
if r > hi { let hi = r }
|
||||||
|
}
|
||||||
|
let i = i + 1
|
||||||
|
}
|
||||||
|
if lo <= 0 { return false }
|
||||||
|
// Reject when the widest ratio is more than 2.2x the narrowest. That is
|
||||||
|
// enough slack for real timing noise and tight enough to separate a clean
|
||||||
|
// 2.0 series from a clean 4.0 series.
|
||||||
|
if (hi * 1000) / lo > 2200 { return false }
|
||||||
|
return true
|
||||||
|
}
|
||||||
|
|
||||||
|
// elb_ratios — consecutive milli-ratios across the sweep.
|
||||||
|
fn elb_ratios(vals: [Int]) -> [Int] {
|
||||||
|
let out: [Int] = native_list_empty()
|
||||||
|
let n: Int = native_list_len(vals)
|
||||||
|
let i: Int = 1
|
||||||
|
while i < n {
|
||||||
|
let out = native_list_append(out,
|
||||||
|
elb_ratio(native_list_get(vals, i - 1), native_list_get(vals, i)))
|
||||||
|
let i = i + 1
|
||||||
|
}
|
||||||
|
return out
|
||||||
|
}
|
||||||
|
|
||||||
|
// elb_mean_tail_ratio — mean of the LAST TWO ratios.
|
||||||
|
//
|
||||||
|
// The tail is used deliberately: asymptotic behaviour is what a complexity
|
||||||
|
// bound claims, and the small-n end of any sweep is dominated by fixed
|
||||||
|
// overhead. This is the same reason a benchmark harness discards warmup.
|
||||||
|
fn elb_mean_tail_ratio(ratios: [Int]) -> Int {
|
||||||
|
let n: Int = native_list_len(ratios)
|
||||||
|
if n == 0 { return -1 }
|
||||||
|
if n == 1 { return native_list_get(ratios, 0) }
|
||||||
|
let a: Int = native_list_get(ratios, n - 1)
|
||||||
|
let b: Int = native_list_get(ratios, n - 2)
|
||||||
|
if a < 0 { return b }
|
||||||
|
if b < 0 { return a }
|
||||||
|
return (a + b) / 2
|
||||||
|
}
|
||||||
|
|
||||||
|
// ── Verdicts ─────────────────────────────────────────────────────────────────
|
||||||
|
//
|
||||||
|
// 0 PASS measured curve is at or below the declared bound
|
||||||
|
// 1 FAIL measured curve is strictly worse than declared
|
||||||
|
// 2 INDETERMINATE ratios disagree; data is noise or a phase change
|
||||||
|
// 3 REFUSED below the measurement floor, or implausibly flat
|
||||||
|
// 4 BETTER measured strictly better than declared (warn, not fail)
|
||||||
|
|
||||||
|
fn elb_verdict_name(v: Int) -> String {
|
||||||
|
if v == 0 { return "PASS" }
|
||||||
|
if v == 1 { return "FAIL" }
|
||||||
|
if v == 2 { return "INDETERMINATE" }
|
||||||
|
if v == 3 { return "REFUSED" }
|
||||||
|
if v == 4 { return "BETTER" }
|
||||||
|
return "?"
|
||||||
|
}
|
||||||
|
|
||||||
|
// elb_gate — classify one signal against its declared bound.
|
||||||
|
//
|
||||||
|
// vals measurements, one per sweep point, in sweep order
|
||||||
|
// expect declared curve index (see elb_curve_name)
|
||||||
|
// floor minimum largest-measurement below which we refuse to classify
|
||||||
|
fn elb_gate(vals: [Int], expect: Int, floor: Int) -> Int {
|
||||||
|
if elb_below_floor(vals, floor) { return 3 }
|
||||||
|
if elb_implausibly_flat(vals) { return 3 }
|
||||||
|
let ratios: [Int] = elb_ratios(vals)
|
||||||
|
if !elb_spread_ok(ratios) { return 2 }
|
||||||
|
let m: Int = elb_mean_tail_ratio(ratios)
|
||||||
|
if m < 0 { return 2 }
|
||||||
|
let got: Int = elb_classify_ratio(m)
|
||||||
|
if got > expect { return 1 }
|
||||||
|
if got < expect { return 4 }
|
||||||
|
return 0
|
||||||
|
}
|
||||||
|
|
||||||
|
// elb_measured_curve — the classified curve for a signal, or -1 if unclassifiable.
|
||||||
|
fn elb_measured_curve(vals: [Int], floor: Int) -> Int {
|
||||||
|
if elb_below_floor(vals, floor) { return -1 }
|
||||||
|
if elb_implausibly_flat(vals) { return -1 }
|
||||||
|
let ratios: [Int] = elb_ratios(vals)
|
||||||
|
let m: Int = elb_mean_tail_ratio(ratios)
|
||||||
|
if m < 0 { return -1 }
|
||||||
|
return elb_classify_ratio(m)
|
||||||
|
}
|
||||||
@@ -0,0 +1,91 @@
|
|||||||
|
// fitprobe.el — controlled growth-curve specimens for validating the complexity fitter.
|
||||||
|
//
|
||||||
|
// Three deliberately-shaped workloads. None depends on a real defect existing,
|
||||||
|
// which is the point: the fitter must be provable against KNOWN curves.
|
||||||
|
//
|
||||||
|
// linear — one allocation per item. count O(n), bytes O(n), time O(n)
|
||||||
|
// accum — rebuilds its accumulator. count O(n), bytes O(n^2), time O(n^2)
|
||||||
|
// compute — nested arithmetic, no alloc. count O(1), bytes O(1), time O(n^2)
|
||||||
|
//
|
||||||
|
// `compute` is the specimen that matters. It is the shape of el #132
|
||||||
|
// (strlen-per-character inside str_char_code): pure CPU, zero allocation.
|
||||||
|
// An allocation-only gate is structurally blind to it.
|
||||||
|
//
|
||||||
|
// No imports — uses runtime builtins directly so nothing collides.
|
||||||
|
|
||||||
|
fn work_linear(n: Int) -> Int {
|
||||||
|
let parts: [String] = native_list_empty()
|
||||||
|
let i: Int = 0
|
||||||
|
while i < n {
|
||||||
|
let parts = native_list_append(parts, int_to_str(i))
|
||||||
|
let i = i + 1
|
||||||
|
}
|
||||||
|
return native_list_len(parts)
|
||||||
|
}
|
||||||
|
|
||||||
|
fn work_accum(n: Int) -> Int {
|
||||||
|
let acc: String = ""
|
||||||
|
let i: Int = 0
|
||||||
|
while i < n {
|
||||||
|
let acc = acc + "x"
|
||||||
|
let i = i + 1
|
||||||
|
}
|
||||||
|
return str_len(acc)
|
||||||
|
}
|
||||||
|
|
||||||
|
fn work_compute(n: Int) -> Int {
|
||||||
|
// str_char_code is an opaque external call, so the C optimiser cannot
|
||||||
|
// reduce this nest to a closed form the way it does with `total + 1`.
|
||||||
|
// This is the exact shape of el #132: n scans over n characters, pure
|
||||||
|
// CPU, ZERO allocation.
|
||||||
|
let s: String = "abcdefghij"
|
||||||
|
let total: Int = 0
|
||||||
|
let i: Int = 0
|
||||||
|
while i < n {
|
||||||
|
let j: Int = 0
|
||||||
|
while j < n {
|
||||||
|
let total = total + str_char_code(s, 0)
|
||||||
|
let j = j + 1
|
||||||
|
}
|
||||||
|
let i = i + 1
|
||||||
|
}
|
||||||
|
return total
|
||||||
|
}
|
||||||
|
|
||||||
|
fn run_one(mode: String, n: Int) {
|
||||||
|
let c0: Int = el_alloc_count()
|
||||||
|
let b0: Int = el_alloc_bytes()
|
||||||
|
let t0: Int = el_now_instant()
|
||||||
|
|
||||||
|
let r: Int = 0
|
||||||
|
if str_eq(mode, "linear") { let r = work_linear(n) }
|
||||||
|
if str_eq(mode, "accum") { let r = work_accum(n) }
|
||||||
|
if str_eq(mode, "compute") { let r = work_compute(n) }
|
||||||
|
|
||||||
|
let t1: Int = el_now_instant()
|
||||||
|
let c1: Int = el_alloc_count()
|
||||||
|
let b1: Int = el_alloc_bytes()
|
||||||
|
|
||||||
|
println(mode + "\t" + int_to_str(n)
|
||||||
|
+ "\t" + int_to_str(c1 - c0)
|
||||||
|
+ "\t" + int_to_str(b1 - b0)
|
||||||
|
+ "\t" + int_to_str((t1 - t0) / 1000)
|
||||||
|
+ "\t" + int_to_str(r))
|
||||||
|
return
|
||||||
|
}
|
||||||
|
|
||||||
|
fn sweep(mode: String) {
|
||||||
|
run_one(mode, 200)
|
||||||
|
run_one(mode, 400)
|
||||||
|
run_one(mode, 800)
|
||||||
|
run_one(mode, 1600)
|
||||||
|
return
|
||||||
|
}
|
||||||
|
|
||||||
|
fn main() -> Int {
|
||||||
|
println("mode\tn\tallocs\tbytes\tusec\tsink")
|
||||||
|
sweep("linear")
|
||||||
|
sweep("accum")
|
||||||
|
sweep("compute")
|
||||||
|
return 0
|
||||||
|
}
|
||||||
@@ -0,0 +1,111 @@
|
|||||||
|
import "../../runtime/eltest.el"
|
||||||
|
import "../../runtime/elbench.el"
|
||||||
|
|
||||||
|
// test_elbench.el — proves the growth-curve classifier against KNOWN curves.
|
||||||
|
//
|
||||||
|
// Every series below is real measured data from lang/tests/bench/fitprobe.el
|
||||||
|
// on a geometric sweep n = 200/400/800/1600. The classifier must be provable
|
||||||
|
// without depending on a live defect existing, which is the whole point of
|
||||||
|
// keeping controlled specimens.
|
||||||
|
|
||||||
|
fn _s4(a: Int, b: Int, c: Int, d: Int) -> [Int] {
|
||||||
|
let l: [Int] = native_list_empty()
|
||||||
|
let l = native_list_append(l, a)
|
||||||
|
let l = native_list_append(l, b)
|
||||||
|
let l = native_list_append(l, c)
|
||||||
|
let l = native_list_append(l, d)
|
||||||
|
return l
|
||||||
|
}
|
||||||
|
|
||||||
|
test "classifies a linear allocation series as O(n)" {
|
||||||
|
// fitprobe `linear`, allocation count
|
||||||
|
let v = _s4(208, 409, 810, 1611)
|
||||||
|
assert elb_measured_curve(v, 10) == 2, "linear allocs should classify O(n)"
|
||||||
|
}
|
||||||
|
|
||||||
|
test "classifies a linear byte series as O(n)" {
|
||||||
|
// fitprobe `linear`, allocation bytes
|
||||||
|
let v = _s4(4786, 9682, 19474, 39658)
|
||||||
|
assert elb_measured_curve(v, 10) == 2, "linear bytes should classify O(n)"
|
||||||
|
}
|
||||||
|
|
||||||
|
test "classifies a quadratic byte series as O(n^2)" {
|
||||||
|
// fitprobe `accum`, allocation bytes -- the accumulator-rebuild shape
|
||||||
|
let v = _s4(20300, 80600, 321200, 1282400)
|
||||||
|
assert elb_measured_curve(v, 10) == 4, "accum bytes should classify O(n^2)"
|
||||||
|
}
|
||||||
|
|
||||||
|
test "accumulator count is linear -- proves count alone misses it" {
|
||||||
|
// Same run as above. The COUNT is exactly linear while bytes are
|
||||||
|
// quadratic. A count-only gate passes this defect clean.
|
||||||
|
let v = _s4(200, 400, 800, 1600)
|
||||||
|
assert elb_measured_curve(v, 10) == 2, "accum count classifies O(n)"
|
||||||
|
assert elb_gate(v, 2, 10) == 0, "count-only gate PASSES the quadratic"
|
||||||
|
}
|
||||||
|
|
||||||
|
test "classifies a quadratic time series as O(n^2)" {
|
||||||
|
// fitprobe `compute` -- el #132's shape: n scans over n characters
|
||||||
|
let v = _s4(67, 205, 818, 3268)
|
||||||
|
assert elb_measured_curve(v, 10) == 4, "compute time should classify O(n^2)"
|
||||||
|
}
|
||||||
|
|
||||||
|
test "REFUSES an all-zero series instead of calling it O(1)" {
|
||||||
|
// fitprobe `compute` allocation count. Pure CPU, allocates nothing.
|
||||||
|
// Reporting O(1) here would be a confident answer with nothing behind it.
|
||||||
|
let v = _s4(0, 0, 0, 0)
|
||||||
|
assert elb_gate(v, 2, 10) == 3, "all-zero series must be REFUSED"
|
||||||
|
assert elb_measured_curve(v, 10) < 0, "unclassifiable returns -1"
|
||||||
|
}
|
||||||
|
|
||||||
|
test "REFUSES an implausibly flat series" {
|
||||||
|
// The shape produced when clang closes a loop to a multiply: a real
|
||||||
|
// answer, no work done, no movement across an 8x input range.
|
||||||
|
let v = _s4(1000, 1001, 1002, 1003)
|
||||||
|
assert elb_gate(v, 2, 10) == 3, "hard-flat series must be REFUSED"
|
||||||
|
}
|
||||||
|
|
||||||
|
test "gate FAILS a quadratic declared as linear" {
|
||||||
|
let v = _s4(20300, 80600, 321200, 1282400)
|
||||||
|
assert elb_gate(v, 2, 10) == 1, "O(n^2) measured vs O(n) declared must FAIL"
|
||||||
|
}
|
||||||
|
|
||||||
|
test "gate PASSES a linear series declared as linear" {
|
||||||
|
let v = _s4(208, 409, 810, 1611)
|
||||||
|
assert elb_gate(v, 2, 10) == 0, "O(n) measured vs O(n) declared must PASS"
|
||||||
|
}
|
||||||
|
|
||||||
|
test "gate reports BETTER when measured beats the declared bound" {
|
||||||
|
let v = _s4(208, 409, 810, 1611)
|
||||||
|
assert elb_gate(v, 4, 10) == 4, "O(n) measured vs O(n^2) declared is BETTER"
|
||||||
|
}
|
||||||
|
|
||||||
|
test "gate reports INDETERMINATE on disagreeing ratios" {
|
||||||
|
// fitprobe `linear` WALL TIME at these sizes: 26/19/43/78 microseconds.
|
||||||
|
// Ratios 0.73, 2.26, 1.81 disagree well past the noise threshold. The
|
||||||
|
// honest answer is "cannot tell", not a classification -- this is exactly
|
||||||
|
// why benchmarks need auto-scaled iteration counts rather than one shot.
|
||||||
|
let v = _s4(26, 19, 43, 78)
|
||||||
|
assert elb_gate(v, 2, 10) == 2, "disagreeing ratios must be INDETERMINATE"
|
||||||
|
}
|
||||||
|
|
||||||
|
test "black_box is a real barrier and returns its input" {
|
||||||
|
assert el_black_box(42) == 42, "black_box is value-preserving"
|
||||||
|
let s: Int = 0
|
||||||
|
let i: Int = 0
|
||||||
|
while i < 100 {
|
||||||
|
// Bind the call before using it in arithmetic: `x + call(...)`
|
||||||
|
// lowers to el_str_concat() on integers. Same inference defect
|
||||||
|
// as `call(...) == y` lowering to str_eq().
|
||||||
|
let bx: Int = el_black_box(1)
|
||||||
|
let s = s + bx
|
||||||
|
let i = i + 1
|
||||||
|
}
|
||||||
|
assert s == 100, "black_box does not disturb the computation"
|
||||||
|
}
|
||||||
|
|
||||||
|
test "curve names round-trip" {
|
||||||
|
assert elb_curve_from_name("O(n)") == 2, "O(n) parses"
|
||||||
|
assert elb_curve_from_name("O(n^2)") == 4, "O(n^2) parses"
|
||||||
|
assert str_eq(elb_curve_name(4), "O(n^2)"), "O(n^2) renders"
|
||||||
|
assert elb_curve_from_name("O(nonsense)") < 0, "unknown curve is -1"
|
||||||
|
}
|
||||||
@@ -0,0 +1,178 @@
|
|||||||
|
import "../../runtime/eltest.el"
|
||||||
|
import "../../runtime/elbench.el"
|
||||||
|
|
||||||
|
// test_lexer_scaling.el — THE ARMED GATE.
|
||||||
|
//
|
||||||
|
// This is the regression test that would have caught el #132.
|
||||||
|
//
|
||||||
|
// #132 was a strlen() inside str_char_code() and str_slice(). The lexer walks
|
||||||
|
// source one character at a time, so every character access rescanned the whole
|
||||||
|
// remaining input: O(n) per character over n characters = O(n^2). It shipped for
|
||||||
|
// months. It was found by a geometric sweep, not by reading code.
|
||||||
|
//
|
||||||
|
// So this test IS a geometric sweep. It scans a string of length n, character by
|
||||||
|
// character, at four doubling sizes, and asserts the cost is linear. If anyone
|
||||||
|
// reintroduces a per-character rescan — in str_char_code, in str_slice, in any
|
||||||
|
// accessor the lexer leans on — the measured curve becomes O(n^2) and this fails.
|
||||||
|
//
|
||||||
|
// The value is in it being ARMED, not in it currently failing. It passes today
|
||||||
|
// because #132 is fixed. That is the correct state for a regression gate.
|
||||||
|
//
|
||||||
|
// Note the deliberate `let c: Int = str_char_code(...)` binding in the scan loop.
|
||||||
|
// Inlining it as `total + str_char_code(s, i)` lowers to el_str_concat() on
|
||||||
|
// integers — the Plus arm of the operator-typing family, still open at the time
|
||||||
|
// of writing. Binding first is the safe form.
|
||||||
|
|
||||||
|
// _mk_string — build a string of length >= n by DOUBLING.
|
||||||
|
//
|
||||||
|
// Deliberately not `s = s + "x"` n times: that is itself quadratic in bytes and
|
||||||
|
// would contaminate the very measurement this test exists to take. Doubling
|
||||||
|
// allocates ~2n total.
|
||||||
|
fn _mk_string(n: Int) -> String {
|
||||||
|
let s: String = "abcdefgh"
|
||||||
|
while str_len(s) < n {
|
||||||
|
let s = s + s
|
||||||
|
}
|
||||||
|
return s
|
||||||
|
}
|
||||||
|
|
||||||
|
// _scan — walk the string one character at a time, REPS times.
|
||||||
|
//
|
||||||
|
// This is the lexer's access pattern reduced to its essential shape. The
|
||||||
|
// repetitions lift the measurement clear of timer resolution; without them the
|
||||||
|
// smaller sizes land in noise and the classifier correctly reports
|
||||||
|
// INDETERMINATE rather than guessing.
|
||||||
|
fn _scan(s: String, n: Int, reps: Int) -> Int {
|
||||||
|
let total: Int = 0
|
||||||
|
let r: Int = 0
|
||||||
|
while r < reps {
|
||||||
|
let i: Int = 0
|
||||||
|
while i < n {
|
||||||
|
let c: Int = str_char_code(s, i)
|
||||||
|
let total = total + c
|
||||||
|
let i = i + 1
|
||||||
|
}
|
||||||
|
let r = r + 1
|
||||||
|
}
|
||||||
|
return total
|
||||||
|
}
|
||||||
|
|
||||||
|
// _measure_scan — microseconds for a full scan sweep point.
|
||||||
|
fn _measure_scan(n: Int, reps: Int) -> Int {
|
||||||
|
let s: String = _mk_string(n)
|
||||||
|
// WARMUP, discarded. Without it the small-n end of the sweep is dominated
|
||||||
|
// by cold caches and reads as superlinear on genuinely linear work --
|
||||||
|
// measured ratios 3.37 2.92 1.76 1.65 on exactly this workload.
|
||||||
|
let w: Int = _scan(s, n, 2)
|
||||||
|
let wj: Int = el_black_box(w)
|
||||||
|
let t0: Int = el_now_instant()
|
||||||
|
let got: Int = _scan(s, n, reps)
|
||||||
|
let t1: Int = el_now_instant()
|
||||||
|
// Feed the result through the barrier so the scan cannot be elided.
|
||||||
|
let sink: Int = el_black_box(got)
|
||||||
|
if sink == 0 { println("") }
|
||||||
|
return (t1 - t0) / 1000
|
||||||
|
}
|
||||||
|
|
||||||
|
fn _series4(a: Int, b: Int, c: Int, d: Int) -> [Int] {
|
||||||
|
let l: [Int] = native_list_empty()
|
||||||
|
let l = native_list_append(l, a)
|
||||||
|
let l = native_list_append(l, b)
|
||||||
|
let l = native_list_append(l, c)
|
||||||
|
let l = native_list_append(l, d)
|
||||||
|
return l
|
||||||
|
}
|
||||||
|
|
||||||
|
test "character scan is LINEAR in time -- regression gate for el #132" {
|
||||||
|
let reps: Int = 40
|
||||||
|
let t1: Int = _measure_scan(16384, reps)
|
||||||
|
let t2: Int = _measure_scan(32768, reps)
|
||||||
|
let t3: Int = _measure_scan(65536, reps)
|
||||||
|
let t4: Int = _measure_scan(131072, reps)
|
||||||
|
let series: [Int] = _series4(t1, t2, t3, t4)
|
||||||
|
|
||||||
|
let verdict: Int = elb_gate(series, 2, 50)
|
||||||
|
let measured: Int = elb_measured_curve(series, 50)
|
||||||
|
|
||||||
|
// Report the actual numbers regardless of outcome. A gate that fires
|
||||||
|
// without showing its evidence is just an assertion.
|
||||||
|
println(" scan us: " + int_to_str(t1) + " " + int_to_str(t2) + " "
|
||||||
|
+ int_to_str(t3) + " " + int_to_str(t4)
|
||||||
|
+ " -> " + elb_curve_name(measured) + " [" + elb_verdict_name(verdict) + "]")
|
||||||
|
|
||||||
|
// PASS (0) or BETTER (4) are both acceptable. FAIL (1) means someone
|
||||||
|
// reintroduced superlinear per-character cost. REFUSED (3) or
|
||||||
|
// INDETERMINATE (2) mean the measurement is untrustworthy -- which is
|
||||||
|
// also a failure of this test, deliberately: a gate that cannot measure
|
||||||
|
// must not report success.
|
||||||
|
assert verdict == 0 || verdict == 4, "character scan must measure O(n) or better"
|
||||||
|
}
|
||||||
|
|
||||||
|
test "string building by doubling stays linear in allocated bytes" {
|
||||||
|
let b1: Int = el_alloc_bytes()
|
||||||
|
let s1: String = _mk_string(8192)
|
||||||
|
let b2: Int = el_alloc_bytes()
|
||||||
|
let s2: String = _mk_string(16384)
|
||||||
|
let b3: Int = el_alloc_bytes()
|
||||||
|
let s3: String = _mk_string(32768)
|
||||||
|
let b4: Int = el_alloc_bytes()
|
||||||
|
let s4: String = _mk_string(65536)
|
||||||
|
let b5: Int = el_alloc_bytes()
|
||||||
|
|
||||||
|
let series: [Int] = _series4(b2 - b1, b3 - b2, b4 - b3, b5 - b4)
|
||||||
|
let verdict: Int = elb_gate(series, 2, 1000)
|
||||||
|
let measured: Int = elb_measured_curve(series, 1000)
|
||||||
|
println(" bytes: " + int_to_str(b2 - b1) + " " + int_to_str(b3 - b2) + " "
|
||||||
|
+ int_to_str(b4 - b3) + " " + int_to_str(b5 - b4)
|
||||||
|
+ " -> " + elb_curve_name(measured) + " [" + elb_verdict_name(verdict) + "]")
|
||||||
|
|
||||||
|
assert verdict == 0 || verdict == 4, "doubling build must be O(n) in bytes"
|
||||||
|
assert str_len(s4) >= 65536, "final string reached the requested size"
|
||||||
|
}
|
||||||
|
|
||||||
|
// _scan_quadratic — a DELIBERATELY quadratic scan: for each position, rescan
|
||||||
|
// from the start. This is precisely what el #132 did — strlen() from offset 0
|
||||||
|
// on every character access — reproduced here so the gate can be proven to
|
||||||
|
// FIRE, not merely to pass on healthy code. An unproven gate is decoration.
|
||||||
|
fn _scan_quadratic(s: String, n: Int) -> Int {
|
||||||
|
let total: Int = 0
|
||||||
|
let i: Int = 0
|
||||||
|
while i < n {
|
||||||
|
let j: Int = 0
|
||||||
|
while j < i {
|
||||||
|
let c: Int = str_char_code(s, j)
|
||||||
|
let total = total + c
|
||||||
|
let j = j + 1
|
||||||
|
}
|
||||||
|
let i = i + 1
|
||||||
|
}
|
||||||
|
return total
|
||||||
|
}
|
||||||
|
|
||||||
|
fn _measure_quadratic(n: Int) -> Int {
|
||||||
|
let s: String = _mk_string(n)
|
||||||
|
let w: Int = _scan_quadratic(s, 64)
|
||||||
|
let wj: Int = el_black_box(w)
|
||||||
|
let t0: Int = el_now_instant()
|
||||||
|
let got: Int = _scan_quadratic(s, n)
|
||||||
|
let t1: Int = el_now_instant()
|
||||||
|
let sink: Int = el_black_box(got)
|
||||||
|
return (t1 - t0) / 1000
|
||||||
|
}
|
||||||
|
|
||||||
|
test "the gate FIRES on a live quadratic scan -- proves it is armed" {
|
||||||
|
let q1: Int = _measure_quadratic(1024)
|
||||||
|
let q2: Int = _measure_quadratic(2048)
|
||||||
|
let q3: Int = _measure_quadratic(4096)
|
||||||
|
let q4: Int = _measure_quadratic(8192)
|
||||||
|
let series: [Int] = _series4(q1, q2, q3, q4)
|
||||||
|
|
||||||
|
let verdict: Int = elb_gate(series, 2, 50)
|
||||||
|
let measured: Int = elb_measured_curve(series, 50)
|
||||||
|
println(" quad us: " + int_to_str(q1) + " " + int_to_str(q2) + " "
|
||||||
|
+ int_to_str(q3) + " " + int_to_str(q4)
|
||||||
|
+ " -> " + elb_curve_name(measured) + " [" + elb_verdict_name(verdict) + "]")
|
||||||
|
|
||||||
|
assert measured == 4, "a rescan-from-zero workload must classify O(n^2)"
|
||||||
|
assert verdict == 1, "declared O(n) against measured O(n^2) must FAIL the gate"
|
||||||
|
}
|
||||||
@@ -0,0 +1,28 @@
|
|||||||
|
fn getstr(x: String) -> String { return x }
|
||||||
|
fn getint(x: Int) -> Int { return x }
|
||||||
|
fn ok(label: String) -> Void { println("ok " + label) }
|
||||||
|
fn bad(label: String) -> Void { println("FAIL " + label) }
|
||||||
|
|
||||||
|
let s1: String = "hello"
|
||||||
|
let s2: String = "hello"
|
||||||
|
let s3: String = "world"
|
||||||
|
let i1: Int = 5
|
||||||
|
let i2: Int = 5
|
||||||
|
let i3: Int = 9
|
||||||
|
|
||||||
|
if "abc" == "abc" { ok("str literal eq") } else { bad("str literal eq") }
|
||||||
|
if "abc" == "xyz" { bad("str literal ne") } else { ok("str literal ne") }
|
||||||
|
if s1 == s2 { ok("str var eq") } else { bad("str var eq") }
|
||||||
|
if s1 == s3 { bad("str var ne") } else { ok("str var ne") }
|
||||||
|
if getstr("hi") == "hi" { ok("str call vs literal") } else { bad("str call vs literal") }
|
||||||
|
if s1 == getstr("hello") { ok("str var vs call") } else { bad("str var vs call") }
|
||||||
|
if s1 == getstr("nope") { bad("str var vs call ne") } else { ok("str var vs call ne") }
|
||||||
|
if i1 == i2 { ok("int var eq") } else { bad("int var eq") }
|
||||||
|
if i1 == i3 { bad("int var ne") } else { ok("int var ne") }
|
||||||
|
if getint(5) == i1 { ok("int call vs var") } else { bad("int call vs var") }
|
||||||
|
if getint(9) == i1 { bad("int call vs var ne") } else { ok("int call vs var ne") }
|
||||||
|
if s1 != s3 { ok("str NOTEQ") } else { bad("str NOTEQ") }
|
||||||
|
if s1 != s2 { bad("str NOTEQ same") } else { ok("str NOTEQ same") }
|
||||||
|
if i1 != i3 { ok("int NOTEQ") } else { bad("int NOTEQ") }
|
||||||
|
if getint(9) != i1 { ok("int call NOTEQ") } else { bad("int call NOTEQ") }
|
||||||
|
println("done")
|
||||||
Reference in New Issue
Block a user