Testing compiled array functions in JS

README.md

Picked up an old experiment which is so far somewhat promising

Background

I love the sugar of using map/filter/reduce type functions on arrays, but the old-school owner of a 286 machine is bothered by the implied nested loops they incur

The experiment was simply:

at least filter and map should be able to be compiled into a single loop A. would the potential improvements of this be worthwhile? B. would they even remotely compete with compiled native bytecode equivalents?

This does that, and the answer to both of the above seems to be a resounding "yes"

So what?

I dunno - if you're implementing this stuff in an interpreter or compiler, then maybe try this approach instead?

ie. Consider them as syntactic sugar for further processing, rather than consumable implementation

Show me the money

Behold: https://jsperf.com/combined-array-functions

repl_code.js

const MAP = 0
const FILTER = 1

/**
 * Really hokey implementation of an Array wrapper which hoards procedures
 * for later application rather than immediately executing them
 *
 * Also includes a compiler
 */
class Arr  {
  constructor(...args) {
    this.value = args
    this.actions = []
  }
  map(fn) {
    this.actions.push([
      MAP,
      fn
    ])
    return this
  }
  filter(fn) {
    this.actions.push([
      FILTER,
      fn
    ])
    return this
  }
  push(v) {
    this.value.push(v)
  }
  
  /**
   * Takes our set of actions and compiles them into a single loop
   *
   * Performance benefits increase with the _number of procedures applied_ rather 
   * more than array size
   *
   * The returned function can be called with a single array and will spit out a new one
   */
  compile() {
    let funcs = this.actions.map( ([kind, fn], idx) => {
      return `const func_${idx} = ${fn.toString()}`
    })
    let parts = this.actions.map( ([kind, fn], idx) => {

      switch (kind) {
        case MAP: return `val = func_${idx}(val)`
        case FILTER: return `if (!func_${idx}(val)) return`
      }
    })
    let funcBody = `
  let output = []
  ${funcs.join('\n')}
  Array.prototype.forEach.call(arr, (val, idx) => {
    ${parts.join('\n')}
    output.push(val)
  })
  return output
  `

    return new Function('arr', funcBody)
  }
  
  /**
   * Applies all the lazily hoarded procedures in one swoop
   *
   * This doesn't perform that well when interpreted, in fact quite poorly
   * However in a native implementation may still fare better than
   * the regular approach.
   *
   * Compiled (see above) seems to be the way to go if it's available
   */
  apply() {
    let output = new Arr()
    Array.prototype.forEach.call(this.value, (v, idx) => {
      let result = v
      let keep = true
      this.actions.every( ([kind, fn]) => {
        switch (kind) {
          case MAP: result = fn(result, idx); break
          case FILTER: 
            keep = fn(result);
            if (!keep) return false
            break
        }
        return true
      })
      if (keep) {
        output.push(result)
      }
    })
    return output
  }
}

const parse = v => parseInt(v, 10)
const isValid = v => v !== null && v == v
const isOdd = v => v % 2 === 1
const mul = v => v * 3.14159265
const square = v => v * v
const round = v => ~~v

let regular = [null,
  'hi',
  1,
  2,
  3,
  4,
  '249'
]
let x = new Arr(...regular)

let xResult = x
  .map(parse)
  .filter(isValid)
  .filter(isOdd)
  .map(mul)
  .map(square)
  .map(round)
  .filter(isOdd)
  .apply()

let regularResult = regular
  .map(parse)
  .filter(isValid)
  .filter(isOdd)
  .map(mul)
  .map(square)
  .map(round)
  .filter(isOdd)

let compiled = x.compile()

let compiledResult = compiled(regular)

console.log({
  xResult,
  regularResult,
  compiledResult,
})

/** Output

{ xResult: Arr { value: [ 9, 611925 ], actions: [] },
  regularResult: [ 9, 611925 ],
  compiledResult: [ 9, 611925 ] }

*/