Struct PertaroExpert243

Source

#[repr(transparent)]
pub struct PertaroExpert243(pub Word256);

Expand description

Zero-cost view over Word256: the payload as a 5-tier micro-expert.

Tuple Fields§

§0: Word256

Implementations§

Source §

impl PertaroExpert243

Source

pub const fn seed(&self) -> u64

The seed: the word’s hash field.

Examples found in repository ?

examples/quick_start.rs (line 30)

5fn main() {
6    // 1. A 256-byte word with a seed, a parent link, and in-band sentinels.
7    let mut raw = Word256 {
8        hash: 0xcbf2_9ce4_8422_2325,
9        parent: 0,
10        trits: [0u8; 244],
11    };
12
13    // Address leaf [1, 0, 2, 1, 2] in the 5-tier ternary trie (each tier in 0..3).
14    let target_leaf = PertaroExpert243::trie_index([1, 0, 2, 1, 2]);
15    raw.trits[target_leaf] = 42; // residual override: +42 mod 243
16
17    // Stamp a defeated branch with an in-band Tombstone (245).
18    let defeated_leaf = PertaroExpert243::trie_index([2, 2, 0, 1, 0]);
19    raw.trits[defeated_leaf] = Sentinel::Tombstone as u8;
20
21    // Mark the root horizon sentinel at trits[243].
22    raw.trits[ROOT_SENTINEL] = Sentinel::NullNode as u8;
23
24    // 2. Wrap in the zero-cost view and materialize.
25    let expert = PertaroExpert243(raw);
26    let materialized: Word256 = expert.materialize();
27
28    assert!(materialized.trits[target_leaf] < MAX_PACKED);
29    assert_eq!(materialized.trits[defeated_leaf], Sentinel::Tombstone as u8);
30    assert_eq!(materialized.hash, expert.seed());
31
32    // 3. Reground the winning Tier-5 leaf (0..243) into a fresh seed.
33    let next_seed = expert.reground_seed(target_leaf as u8, Sentinel::BusIndirect);
34    assert_ne!(next_seed, expert.seed());
35
36    println!("leaf {target_leaf} -> {}", materialized.trits[target_leaf]);
37    println!("next seed {next_seed:#018x}");
38}

Source

pub const fn parent(&self) -> u32

The lineage link.

Source

pub const fn root_sentinel_byte(&self) -> u8

The raw root sentinel byte at payload index 243.

Source

pub const fn root_sentinel(&self) -> Option<Sentinel>

The active phase, or None if the root byte is a coordinate.

Source

pub const fn leaves(&self) -> &[u8; 243]

The 243 raw leaf bytes: deltas 0..243 or in-band sentinels.

Source

pub const fn trie_index(path: [u8; 5]) -> usize

Leaf index 0..243 of a 5-tier ternary path. Every tier must be in 0..3; anything else is a panic, because the path is the address.

Examples found in repository ?

examples/quick_start.rs (line 14)

5fn main() {
6    // 1. A 256-byte word with a seed, a parent link, and in-band sentinels.
7    let mut raw = Word256 {
8        hash: 0xcbf2_9ce4_8422_2325,
9        parent: 0,
10        trits: [0u8; 244],
11    };
12
13    // Address leaf [1, 0, 2, 1, 2] in the 5-tier ternary trie (each tier in 0..3).
14    let target_leaf = PertaroExpert243::trie_index([1, 0, 2, 1, 2]);
15    raw.trits[target_leaf] = 42; // residual override: +42 mod 243
16
17    // Stamp a defeated branch with an in-band Tombstone (245).
18    let defeated_leaf = PertaroExpert243::trie_index([2, 2, 0, 1, 0]);
19    raw.trits[defeated_leaf] = Sentinel::Tombstone as u8;
20
21    // Mark the root horizon sentinel at trits[243].
22    raw.trits[ROOT_SENTINEL] = Sentinel::NullNode as u8;
23
24    // 2. Wrap in the zero-cost view and materialize.
25    let expert = PertaroExpert243(raw);
26    let materialized: Word256 = expert.materialize();
27
28    assert!(materialized.trits[target_leaf] < MAX_PACKED);
29    assert_eq!(materialized.trits[defeated_leaf], Sentinel::Tombstone as u8);
30    assert_eq!(materialized.hash, expert.seed());
31
32    // 3. Reground the winning Tier-5 leaf (0..243) into a fresh seed.
33    let next_seed = expert.reground_seed(target_leaf as u8, Sentinel::BusIndirect);
34    assert_ne!(next_seed, expert.seed());
35
36    println!("leaf {target_leaf} -> {}", materialized.trits[target_leaf]);
37    println!("next seed {next_seed:#018x}");
38}

Source

pub const fn default_field(seed: u64, out: &mut [u8; 243])

Fill out with 243 uniform Z_243 digits from the seed’s xorshift64 stream by radix-243 extraction with word rejection. A zero seed is replaced by FNV1A64_BASIS so the stream is never the zero fixed point.

Source

pub const fn materialize(&self) -> Word256

Materialize the expert: header and root byte copied verbatim, each leaf resolved as (base + delta) mod 243, or by its in-band sentinel (NullNode keeps the base; every other sentinel propagates as-is).

Examples found in repository ?

examples/quick_start.rs (line 26)

5fn main() {
6    // 1. A 256-byte word with a seed, a parent link, and in-band sentinels.
7    let mut raw = Word256 {
8        hash: 0xcbf2_9ce4_8422_2325,
9        parent: 0,
10        trits: [0u8; 244],
11    };
12
13    // Address leaf [1, 0, 2, 1, 2] in the 5-tier ternary trie (each tier in 0..3).
14    let target_leaf = PertaroExpert243::trie_index([1, 0, 2, 1, 2]);
15    raw.trits[target_leaf] = 42; // residual override: +42 mod 243
16
17    // Stamp a defeated branch with an in-band Tombstone (245).
18    let defeated_leaf = PertaroExpert243::trie_index([2, 2, 0, 1, 0]);
19    raw.trits[defeated_leaf] = Sentinel::Tombstone as u8;
20
21    // Mark the root horizon sentinel at trits[243].
22    raw.trits[ROOT_SENTINEL] = Sentinel::NullNode as u8;
23
24    // 2. Wrap in the zero-cost view and materialize.
25    let expert = PertaroExpert243(raw);
26    let materialized: Word256 = expert.materialize();
27
28    assert!(materialized.trits[target_leaf] < MAX_PACKED);
29    assert_eq!(materialized.trits[defeated_leaf], Sentinel::Tombstone as u8);
30    assert_eq!(materialized.hash, expert.seed());
31
32    // 3. Reground the winning Tier-5 leaf (0..243) into a fresh seed.
33    let next_seed = expert.reground_seed(target_leaf as u8, Sentinel::BusIndirect);
34    assert_ne!(next_seed, expert.seed());
35
36    println!("leaf {target_leaf} -> {}", materialized.trits[target_leaf]);
37    println!("next seed {next_seed:#018x}");
38}

Source

pub const fn reground_seed(&self, winner: u8, next: Sentinel) -> u64

Reground at the Tier-5 boundary: fold the seed, the winning leaf (0..243) and the next phase through FNV-1a, then one xorshift64 step. A winner at or above 243 is a panic: sentinels are not leaves.

Examples found in repository ?

examples/bench_pertaro.rs (line 38)

37fn touch(node: &mut PertaroExpert243, atom: u8) -> u64 {
38    let s = node.reground_seed(atom, Sentinel::BusIndirect);
39    node.0.hash = s;
40    s
41}
42
43/// Dependent chase: the next index comes from the word just touched, so every
44/// load waits for the previous one. This exposes load-to-use latency, which
45/// independent loads hide behind memory-level parallelism.
46fn chase_pass(arena: &mut [PertaroExpert243], passes: usize) -> f64 {
47    let n = arena.len();
48    let mut i = 0usize;
49    let mut acc = 0u64;
50    let t = Instant::now();
51    for _ in 0..passes {
52        for _ in 0..n {
53            let s = touch(&mut arena[i], (acc & 0xFF) as u8 % 243);
54            acc ^= s;
55            i = (s % n as u64) as usize;
56        }
57    }
58    black_box(acc);
59    t.elapsed().as_nanos() as f64 / (passes * n) as f64
60}
61
62fn random_pass(arena: &mut [PertaroExpert243], passes: usize) -> f64 {
63    let n = arena.len();
64    let mut rng = FNV1A64_BASIS;
65    let mut acc = 0u64;
66    let t = Instant::now();
67    for _ in 0..passes {
68        for _ in 0..n {
69            rng = xorshift64(rng);
70            let i = (rng % n as u64) as usize;
71            acc ^= touch(&mut arena[i], (rng >> 32) as u8 % 243);
72        }
73    }
74    black_box(acc);
75    t.elapsed().as_nanos() as f64 / (passes * n) as f64
76}
77
78fn main() {
79    const ITERS: usize = 100_000;
80    let expert = seeded_expert();
81
82    // 1. One word: materialize + two reduct passes + in-place tombstoning.
83    let t0 = Instant::now();
84    for _ in 0..ITERS {
85        let mut e = black_box(expert);
86        black_box(e.prune_frontier());
87    }
88    let ns_single = t0.elapsed().as_nanos() as f64 / ITERS as f64;
89
90    // 2. Tier-4 arena: expand, prune the 81 frontier nodes, reground.
91    let mut arena = Box::new(PertaroArena121 {
92        nodes: [expert; ARENA_NODES],
93    });
94    let arena_iters = 10_000usize;
95    let mut seed = FNV1A64_BASIS;
96    let t1 = Instant::now();
97    for step in 0..arena_iters {
98        arena.expand_from_root(seed, (step % 243) as u8, Sentinel::BusIndirect);
99        let mut winner = 0u8;
100        for node in arena.frontier_mut() {
101            if let Some(w) = node.prune_frontier().first_winner() {
102                winner = w;
103            }
104        }
105        seed = arena.nodes[ARENA_NODES - 1].reground_seed(winner, Sentinel::BusIndirect);
106        black_box(seed);
107    }
108    let ns_l1_node = t1.elapsed().as_nanos() as f64 / (arena_iters * ARENA_NODES) as f64;
109
110    // 3. Tier-6 flat bank, 1093 words, every node pruned: compute-bound control.
111    const TIER6_NODES: usize = 1093;
112    let mut bank = vec![expert; TIER6_NODES];
113    let spill_iters = 2_000usize;
114    let t2 = Instant::now();
115    for step in 0..spill_iters {
116        for (i, node) in bank.iter_mut().enumerate() {
117            node.0.hash = seed.wrapping_add(i as u64);
118            black_box(node.prune_frontier());
119        }
120        seed = seed.wrapping_add(step as u64);
121    }
122    let ns_spill_node = t2.elapsed().as_nanos() as f64 / (spill_iters * TIER6_NODES) as f64;
123
124    // 4. The cliff test: light random-order touches over growing working sets.
125    let sizes = [121usize, 364, 1093, 3280, 9841, 29524];
126    let mut cliff = Vec::new();
127    for &n in &sizes {
128        let mut a = vec![expert; n];
129        random_pass(&mut a, 2); // warm
130        let passes = (2_000_000 / n).max(20);
131        let independent = random_pass(&mut a, passes);
132        let dependent = chase_pass(&mut a, passes);
133        cliff.push((n, n * 256, independent, dependent));
134    }
135
136    println!("==============================================================");
137    println!(
138        " PERTARO LATENCY (Word256 = 256 B, Arena121 = {} B)",
139        ARENA_NODES * 256
140    );
141    println!("==============================================================");
142    println!("1. one word, materialize + reduct + prune : {ns_single:>8.1} ns");
143    println!("2. tier-4 arena, expand + 81 prunes       : {ns_l1_node:>8.1} ns/node");
144    println!("3. tier-6 bank, 1093 prunes (control)     : {ns_spill_node:>8.1} ns/node");
145    println!("4. light touch, by working set (tier-4 frontier starts at node {FRONTIER_START}):");
146    println!("     nodes      bytes   independent ns   dependent ns");
147    for (n, bytes, ind, dep) in cliff {
148        println!("   {n:>7} {bytes:>10} {ind:>14.2} {dep:>14.2}");
149    }
150    println!("   independent = random index from an RNG (loads overlap)");
151    println!("   dependent   = next index from the word just loaded (loads serialize)");
152    println!("==============================================================");
153}

More examples

Hide additional examples

examples/quick_start.rs (line 33)

5fn main() {
6    // 1. A 256-byte word with a seed, a parent link, and in-band sentinels.
7    let mut raw = Word256 {
8        hash: 0xcbf2_9ce4_8422_2325,
9        parent: 0,
10        trits: [0u8; 244],
11    };
12
13    // Address leaf [1, 0, 2, 1, 2] in the 5-tier ternary trie (each tier in 0..3).
14    let target_leaf = PertaroExpert243::trie_index([1, 0, 2, 1, 2]);
15    raw.trits[target_leaf] = 42; // residual override: +42 mod 243
16
17    // Stamp a defeated branch with an in-band Tombstone (245).
18    let defeated_leaf = PertaroExpert243::trie_index([2, 2, 0, 1, 0]);
19    raw.trits[defeated_leaf] = Sentinel::Tombstone as u8;
20
21    // Mark the root horizon sentinel at trits[243].
22    raw.trits[ROOT_SENTINEL] = Sentinel::NullNode as u8;
23
24    // 2. Wrap in the zero-cost view and materialize.
25    let expert = PertaroExpert243(raw);
26    let materialized: Word256 = expert.materialize();
27
28    assert!(materialized.trits[target_leaf] < MAX_PACKED);
29    assert_eq!(materialized.trits[defeated_leaf], Sentinel::Tombstone as u8);
30    assert_eq!(materialized.hash, expert.seed());
31
32    // 3. Reground the winning Tier-5 leaf (0..243) into a fresh seed.
33    let next_seed = expert.reground_seed(target_leaf as u8, Sentinel::BusIndirect);
34    assert_ne!(next_seed, expert.seed());
35
36    println!("leaf {target_leaf} -> {}", materialized.trits[target_leaf]);
37    println!("next seed {next_seed:#018x}");
38}

Source §

impl PertaroExpert243

Source

pub fn gl_reduct_consequences( &self, materialized: &Word256, s: &AnswerSetMask, ) -> AnswerSetMask

Consequences of the Gelfond-Lifschitz reduct of this expert’s program under candidate set s: Cn(P^S).

materialized must be materialize of this same expert; the raw word supplies the rule shape, the materialized word the rule body. Per leaf idx in 0..243:

raw or materialized Tombstone (245): integrity constraint, never derived;
raw NullNode (243): fact idx., always derived;
materialized value v < 243: rule idx :- not v., derived iff v is not in s;
any other sentinel: no rule, never derived.

Source

pub fn is_answer_set(&self, materialized: &Word256, s: &AnswerSetMask) -> bool

The exact stable-model test: Cn(P^S) == S.

Source

pub fn prune_frontier(&mut self) -> AnswerSetMask

Two-pass stratified pruning from the empty worldview: S1 = Cn(P^∅), then S2 = Cn(P^S1). Every coordinate leaf outside S2 is stamped Tombstone in place and S2 is returned.

This is an approximation, not the fixed point: S2 is a stable model only when is_answer_set says so. It is the bounded-cost pass the arena runs on every frontier node; the exact check is one call away for callers that need it.

Examples found in repository ?

examples/bench_pertaro.rs (line 86)

78fn main() {
79    const ITERS: usize = 100_000;
80    let expert = seeded_expert();
81
82    // 1. One word: materialize + two reduct passes + in-place tombstoning.
83    let t0 = Instant::now();
84    for _ in 0..ITERS {
85        let mut e = black_box(expert);
86        black_box(e.prune_frontier());
87    }
88    let ns_single = t0.elapsed().as_nanos() as f64 / ITERS as f64;
89
90    // 2. Tier-4 arena: expand, prune the 81 frontier nodes, reground.
91    let mut arena = Box::new(PertaroArena121 {
92        nodes: [expert; ARENA_NODES],
93    });
94    let arena_iters = 10_000usize;
95    let mut seed = FNV1A64_BASIS;
96    let t1 = Instant::now();
97    for step in 0..arena_iters {
98        arena.expand_from_root(seed, (step % 243) as u8, Sentinel::BusIndirect);
99        let mut winner = 0u8;
100        for node in arena.frontier_mut() {
101            if let Some(w) = node.prune_frontier().first_winner() {
102                winner = w;
103            }
104        }
105        seed = arena.nodes[ARENA_NODES - 1].reground_seed(winner, Sentinel::BusIndirect);
106        black_box(seed);
107    }
108    let ns_l1_node = t1.elapsed().as_nanos() as f64 / (arena_iters * ARENA_NODES) as f64;
109
110    // 3. Tier-6 flat bank, 1093 words, every node pruned: compute-bound control.
111    const TIER6_NODES: usize = 1093;
112    let mut bank = vec![expert; TIER6_NODES];
113    let spill_iters = 2_000usize;
114    let t2 = Instant::now();
115    for step in 0..spill_iters {
116        for (i, node) in bank.iter_mut().enumerate() {
117            node.0.hash = seed.wrapping_add(i as u64);
118            black_box(node.prune_frontier());
119        }
120        seed = seed.wrapping_add(step as u64);
121    }
122    let ns_spill_node = t2.elapsed().as_nanos() as f64 / (spill_iters * TIER6_NODES) as f64;
123
124    // 4. The cliff test: light random-order touches over growing working sets.
125    let sizes = [121usize, 364, 1093, 3280, 9841, 29524];
126    let mut cliff = Vec::new();
127    for &n in &sizes {
128        let mut a = vec![expert; n];
129        random_pass(&mut a, 2); // warm
130        let passes = (2_000_000 / n).max(20);
131        let independent = random_pass(&mut a, passes);
132        let dependent = chase_pass(&mut a, passes);
133        cliff.push((n, n * 256, independent, dependent));
134    }
135
136    println!("==============================================================");
137    println!(
138        " PERTARO LATENCY (Word256 = 256 B, Arena121 = {} B)",
139        ARENA_NODES * 256
140    );
141    println!("==============================================================");
142    println!("1. one word, materialize + reduct + prune : {ns_single:>8.1} ns");
143    println!("2. tier-4 arena, expand + 81 prunes       : {ns_l1_node:>8.1} ns/node");
144    println!("3. tier-6 bank, 1093 prunes (control)     : {ns_spill_node:>8.1} ns/node");
145    println!("4. light touch, by working set (tier-4 frontier starts at node {FRONTIER_START}):");
146    println!("     nodes      bytes   independent ns   dependent ns");
147    for (n, bytes, ind, dep) in cliff {
148        println!("   {n:>7} {bytes:>10} {ind:>14.2} {dep:>14.2}");
149    }
150    println!("   independent = random index from an RNG (loads overlap)");
151    println!("   dependent   = next index from the word just loaded (loads serialize)");
152    println!("==============================================================");
153}