code wiki / (root) / nx_mrshuffle.nx

nx_mrshuffle.nx

buildroot/runtime/nx_mrshuffle.nx

7517 B170 linesdepth 3pulls 3 transitivereach 1 importersview sourcekind tool
docsdependenciesstructsconstsfunctions

about

nx_mrshuffle.nx -- the real MapReduce SHUFFLE (closes distributed-compute's shuffle-exchange gap). The hard, distinctive part of distributed group-by/join is the SHUFFLE: repartition rows by a hash of the key so that every row for a given key lands at exactly ONE reducer, and each reducer sees ALL rows for its keys -- then reducers aggregate independently and their union is the answer. This is the canonical COUNTING shuffle (count per reducer -> prefix-sum to contiguous offsets -> place), so it is O(n) not the O(n*R) broadcast-filter shortcut, and the reduce phase runs in REAL parallel (one forked process per reducer, over a shared exchange). From the first byte up: fork + shared mmap + wait4, no frameworks. Composes the zero-copy nx_colframe. license_tier: ORIGINAL No hardware writes (Rule 26).

dependencies 2 imports · 1 importers

nx_syscalls.nx nx_colframe.nx nx_mrshuffle.nx nx_mrshuffle_gate.nx

imports: nx_syscalls.nxnx_colframe.nx

imported by: nx_mrshuffle_gate.nx

call flow from main pre-order; caps 40 nodes / depth 6 declared; ↻ = already shown

main sys_mmap mr_atoi mr_demo sys_mmap ↻ cf_encoded_bytes cf_slen cf_align8 cf_encode cf_align8 ↻ sys_mmap_shared mr_groupby_shuffle cf_nrows cf_col cf_data_off sys_mmap ↻ mr_reducer mr_hash sys_mmap_shared ↻ sys_fork sys_exit sys_wait4 mr_raw mr_num sys_mmap ↻ sys_write

structs

none

consts

11const MR_MAGIC_4294967296: i64 = 4294967296
12const MR_MAGIC_1103515245: i64 = 1103515245
13const MR_MAGIC_12345: i64 = 12345
14const MR_MAGIC_1000000: i64 = 1000000
16const MR_MAXR: i64 = 64
17const MR_OUT: i64 = 8192
18const MR_ZERO: i64 = 48
19const MR_HASHK: i64 = 2654435761 // Knuth multiplicative hash constant (odd)
20const MR_MASK: i64 = 0x7fffffffffffffff

functions

22func mr_hash(k: i64) -> i64
called by 1: mr_reducer
29func mr_reducer(k: i64, R: i64) -> i64 { return mr_hash(k) % R }
called by 2: mr_groupby_shufflemain calls 1: mr_hash
35func mr_groupby_shuffle(frame: *u8, keyci: i64, valci: i64, R: i64, out_sums: *i64) -> i64
94func mr_raw(out: *u8, o: i64, s: *u8) -> i64 { var i: i64 = 0; while s[i] != (0 as u8) { out[o] = s[i]; o = o + 1; i = i + 1 } return o }
called by 1: mr_demo
95func mr_num(out: *u8, o: i64, v: i64) -> i64
called by 1: mr_demo calls 1: sys_mmap
107func mr_atoi(s: *u8) -> i64 { var v: i64 = 0; var i: i64 = 0; var go: i64 = 1; while go == 1 { let c: i64 = s[i] as i64; if c < 48 { go = 0 } else { if c > 57 { go = 0 } else { v = v * 10 + (c - 48); i = i + 1 } } } return v }
called by 1: main
109func mr_demo(nrows: i64, K: i64, R: i64, out: *u8) -> i64
156func main(argc: i64, argv: *i64) -> i64