nx_mrshuffle.nx
buildroot/runtime/nx_mrshuffle.nx
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
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
structs
| none |
consts
| 11 | const MR_MAGIC_4294967296: i64 = 4294967296 |
| 12 | const MR_MAGIC_1103515245: i64 = 1103515245 |
| 13 | const MR_MAGIC_12345: i64 = 12345 |
| 14 | const MR_MAGIC_1000000: i64 = 1000000 |
| 16 | const MR_MAXR: i64 = 64 |
| 17 | const MR_OUT: i64 = 8192 |
| 18 | const MR_ZERO: i64 = 48 |
| 19 | const MR_HASHK: i64 = 2654435761 // Knuth multiplicative hash constant (odd) |
| 20 | const MR_MASK: i64 = 0x7fffffffffffffff |
functions
| 22 | func mr_hash(k: i64) -> i64 called by 1: mr_reducer |
| 29 | func mr_reducer(k: i64, R: i64) -> i64 { return mr_hash(k) % R } |
| 35 | func mr_groupby_shuffle(frame: *u8, keyci: i64, valci: i64, R: i64, out_sums: *i64) -> i64 |
| 94 | func 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 |
| 95 | func mr_num(out: *u8, o: i64, v: i64) -> i64 |
| 107 | func 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 |
| 109 | func mr_demo(nrows: i64, K: i64, R: i64, out: *u8) -> i64 called by 1: main calls 7: sys_mmapcf_encoded_bytescf_encodesys_mmap_sharedmr_groupby_shufflemr_raw+1 |
| 156 | func main(argc: i64, argv: *i64) -> i64 |