Node.js / Bend - Bitonic Sort Comparison

bitonic_sort_comparison.md

Bend:

def gen(d, x):
  switch d:
    case 0:
      return x
    case _:
      return (gen(d-1, x * 2 + 1), gen(d-1, x * 2))

def sum(d, t):
  switch d:
    case 0:
      return t
    case _:
      (t.a, t.b) = t
      return sum(d-1, t.a) + sum(d-1, t.b)

def swap(s, a, b):
  switch s:
    case 0:
      return (a,b)
    case _:
      return (b,a)

def warp(d, s, a, b):
  switch d:
    case 0:
      return swap(s ^ (a > b), a, b)
    case _:
      (a.a,a.b) = a
      (b.a,b.b) = b
      (A.a,A.b) = warp(d-1, s, a.a, b.a)
      (B.a,B.b) = warp(d-1, s, a.b, b.b)
      return ((A.a,B.a),(A.b,B.b))

def flow(d, s, t):
  switch d:
    case 0:
      return t
    case _:
      (t.a, t.b) = t
      return down(d, s, warp(d-1, s, t.a, t.b))

def down(d,s,t):
  switch d:
    case 0:
      return t
    case _:
      (t.a, t.b) = t
      return (flow(d-1, s, t.a), flow(d-1, s, t.b))

def sort(d, s, t):
  switch d:
    case 0:
      return t
    case _:
      (t.a, t.b) = t
      return flow(d, s, (sort(d-1, 0, t.a), sort(d-1, 1, t.b)))

def main:
  return sum(20, sort(20, 0, gen(20, 0)))

Node.js:

function gen(d, x) {
  switch (d) {
    case 0:
      return x % 0x1000000;
    default:
      return [gen(d - 1, x * 2 + 1), gen(d - 1, x * 2)];
  }
}

function sum(d, t) {
  switch (d) {
    case 0:
      return t;
    default:
      let [a, b] = t;
      return (sum(d - 1, a) + sum(d - 1, b)) % 0x1000000;
  }
}

function swap(s, a, b) {
  switch (s) {
    case 0:
      return [a, b];
    default:
      return [b, a];
  }
}

function warp(d, s, a, b) {
  switch (d) {
    case 0:
      return swap(s ^ (a > b ? 1 : 0), a, b);
    default:
      let [aa, ab] = a;
      let [ba, bb] = b;
      let [Aa, Ab] = warp(d - 1, s, aa, ba);
      let [Ba, Bb] = warp(d - 1, s, ab, bb);
      return [[Aa, Ba], [Ab, Bb]];
  }
}

function flow(d, s, t) {
  switch (d) {
    case 0:
      return t;
    default:
      let [a, b] = t;
      return down(d, s, warp(d - 1, s, a, b));
  }
}

function down(d, s, t) {
  switch (d) {
    case 0:
      return t;
    default:
      let [a, b] = t;
      return [flow(d - 1, s, a), flow(d - 1, s, b)];
  }
}

function sort(d, s, t) {
  switch (d) {
    case 0:
      return t;
    default:
      let [a, b] = t;
      return flow(d, s, [sort(d - 1, 0, a), sort(d - 1, 1, b)]);
  }
}

function main() {
  return sum(20, sort(20, 0, gen(20, 0)));
}

console.log(main());

Results:

Node.js: 3.59 seconds (Apple M3 Max)

$ time node bitonic_sort.js
16252928
node bitonic_sort.js  6.29s user 0.83s system 197% cpu 3.598 total

Bend: 0.58 seconds (RTX 4090)

$ time bend run-cu bitonic_sort.bend -s

Running...
Result: 16252928
- ITRS: 6138934989
- LEAK: 261654029
- TIME: 0.58s
- MIPS: 10656.93

real	0m0,621s
user	0m0,521s
sys	0m0,076s