Duff's device, part 2: copying within an array. Benchmark from lazutkin.com. Run: npm install && npm run bench

README.md

Copying within an array: hand-written loops vs Array#copyWithin

Benchmark from lazutkin.com, the companion to Duff's device, part 2: copying within an array, which follows Duff's device in JavaScript.

The first post copied one array into another; its benchmark is in a separate gist. This one copies a range within one array, which is Array#copyWithin's domain, so the built-in and the hand-written loops race on equal terms.

The files

• copy-within.js — the four contenders on a packed array: the simple loop, duff-device-1 (unrolled by ten plus a switch for the remainder), duff-device-3 (one loop, the switch decides how much of the block runs) and Array#copyWithin. All copy the same 127 elements from the front half of a 255-element array into the back half; the ranges do not overlap.
• copy-within-holey.js — the same copyWithin call on a packed array and on a holey one with identical contents.
• simple-loop-holey.js — the control for the file above: the same packed-vs-holey question asked of the simple loop.

Running it

npm install
npm run bench            # the four contenders
npm run bench:holey      # copyWithin, packed vs holey
npm run bench:control    # the simple loop, packed vs holey
npm run bench:deno       # the four contenders under Deno
npm run bench:bun        # the four contenders under Bun

The harness is nano-bench; its Concepts page explains how the confidence intervals and the significance tests are computed. Defaults are 100 samples of 50 ms per function.

The work is CPU-bound, so run one process at a time and one machine at a time. Results move with the engine, the engine version and the CPU, so a number from a single box says nothing on its own.

copy-within-holey.js

// Does the elements kind change the cost of Array#copyWithin? The same
// call on two arrays with the same contents: one built packed
// (Array.from), one built holey (new Array(n), then filled; V8 keeps the
// HOLEY kind after filling). One question: packed vs holey.

const LEN = 127;
const SRC = 0;
const DST = 128;

export const packed = Array.from({length: DST + LEN}, (_, i) => i);
export const holey = new Array(DST + LEN);
for (let i = 0; i < holey.length; ++i) holey[i] = i;

export default {
  'copy-within-packed': n => {
    for (let i = 0; i < n; ++i) {
      packed.copyWithin(DST, SRC, SRC + LEN);
    }
  },
  'copy-within-holey': n => {
    for (let i = 0; i < n; ++i) {
      holey.copyWithin(DST, SRC, SRC + LEN);
    }
  }
};

copy-within.js

// Same-array copy of a section: hand-written loops vs Array#copyWithin.
// Companion to loop.js (the two-array benchmark of the first post).
// One question: which technique, on a packed array.

const LEN = 127; // elements copied, as in loop.js
const SRC = 0;
const DST = 128; // forward and non-overlapping

export const data = Array.from({length: DST + LEN}, (_, i) => i);

export default {
  'simple-loop': n => {
    for (let i = 0; i < n; ++i) {
      for (let j = 0; j < LEN; ++j) {
        data[DST + j] = data[SRC + j];
      }
    }
  },
  'duff-device-3': n => {
    for (let i = 0; i < n; ++i) {
      for (let j = 0; j < LEN; j += 10) {
        switch (LEN - j) {
          default: data[DST + j + 9] = data[SRC + j + 9];
          case 9: data[DST + j + 8] = data[SRC + j + 8];
          case 8: data[DST + j + 7] = data[SRC + j + 7];
          case 7: data[DST + j + 6] = data[SRC + j + 6];
          case 6: data[DST + j + 5] = data[SRC + j + 5];
          case 5: data[DST + j + 4] = data[SRC + j + 4];
          case 4: data[DST + j + 3] = data[SRC + j + 3];
          case 3: data[DST + j + 2] = data[SRC + j + 2];
          case 2: data[DST + j + 1] = data[SRC + j + 1];
          case 1: data[DST + j] = data[SRC + j];
          case 0: break;
        }
      }
    }
  },
  'duff-device-1': n => {
    for (let i = 0; i < n; ++i) {
      let j = 0;
      for (; j + 10 <= LEN; j += 10) {
        data[DST + j] = data[SRC + j];
        data[DST + j + 1] = data[SRC + j + 1];
        data[DST + j + 2] = data[SRC + j + 2];
        data[DST + j + 3] = data[SRC + j + 3];
        data[DST + j + 4] = data[SRC + j + 4];
        data[DST + j + 5] = data[SRC + j + 5];
        data[DST + j + 6] = data[SRC + j + 6];
        data[DST + j + 7] = data[SRC + j + 7];
        data[DST + j + 8] = data[SRC + j + 8];
        data[DST + j + 9] = data[SRC + j + 9];
      }
      switch (LEN - j) {
        case 9: data[DST + j + 8] = data[SRC + j + 8];
        case 8: data[DST + j + 7] = data[SRC + j + 7];
        case 7: data[DST + j + 6] = data[SRC + j + 6];
        case 6: data[DST + j + 5] = data[SRC + j + 5];
        case 5: data[DST + j + 4] = data[SRC + j + 4];
        case 4: data[DST + j + 3] = data[SRC + j + 3];
        case 3: data[DST + j + 2] = data[SRC + j + 2];
        case 2: data[DST + j + 1] = data[SRC + j + 1];
        case 1: data[DST + j] = data[SRC + j];
      }
    }
  },
  'copy-within': n => {
    for (let i = 0; i < n; ++i) {
      data.copyWithin(DST, SRC, SRC + LEN);
    }
  }
};

package.json

{
  "name": "copy-within-bench",
  "private": true,
  "type": "module",
  "scripts": {
    "bench": "nano-bench copy-within.js",
    "bench:holey": "nano-bench copy-within-holey.js",
    "bench:control": "nano-bench simple-loop-holey.js",
    "bench:deno": "deno run -A `nano-bench --self` copy-within.js",
    "bench:bun": "bun run `nano-bench --self` copy-within.js"
  },
  "devDependencies": {
    "nano-benchmark": "^1.2.0"
  }
}

simple-loop-holey.js

// Control for copy-within-holey.js: the same packed-vs-holey question
// asked of the simple loop, so a holey penalty on copyWithin can be told
// from a holey penalty on element access in general.

const LEN = 127;
const SRC = 0;
const DST = 128;

export const packed = Array.from({length: DST + LEN}, (_, i) => i);
export const holey = new Array(DST + LEN);
for (let i = 0; i < holey.length; ++i) holey[i] = i;

export default {
  'simple-loop-packed': n => {
    for (let i = 0; i < n; ++i) {
      for (let j = 0; j < LEN; ++j) {
        packed[DST + j] = packed[SRC + j];
      }
    }
  },
  'simple-loop-holey': n => {
    for (let i = 0; i < n; ++i) {
      for (let j = 0; j < LEN; ++j) {
        holey[DST + j] = holey[SRC + j];
      }
    }
  }
};