Array read / modify performance issue

[lanyusan]

🐛 Bug report

I need to pick an optics lib for a project. I continued to evaluate optics libs and narrowed down to 3:

• optics-ts
• partial.lenses
• monocle-ts

I ran another round of performance test on array and found out monocle-ts' array read / modify by prism predicate is slow compared to the others. Modify is especially slow.

Did my benchmark code do something wrong or monocle-ts' array read / modify by Prism predicate needs some optimization?

Here is the result and code:

result

  prism into array
    ✓ optics-ts (69ms)
    ✓ monocle-ts (223ms)
    ✓ partial.lenses (7ms)
  prism modify array
    ✓ optics-ts (222ms)
    ✓ monocle-ts (34769ms)
    ✓ partial.lenses (344ms)

code for Jest

import * as O from 'optics-ts'

import { fromTraversable, Lens, Prism } from 'monocle-ts'
import { some } from 'fp-ts/lib/Option'

import * as L from 'partial.lenses'

import { array } from 'fp-ts/lib/Array'

const size = 5000
const mid = Math.floor(size / 2)
const id = 'id-' + mid
const name = 'Luke-' + mid
const nameModified = 'Luke-' + mid + '-modified'

const makeNames = () => {
  const arr = []
  for (let i = 0; i < size; i++)
    arr.push({
      id: 'id-' + i,
      name: 'Luke-' + i,
    })

  return arr
}

const data = {
  a: {
    b: {
      c: { d: { e: 'hello' } },
    },
  },

  m: {
    n: {
      names: makeNames(),
    },
  },
}

const run = (fn: () => any) => {
  for (let i = 0; i < repeat; i++) fn()
}

const repeat = 1000 //50000

describe('prism into array', () => {
  it('optics-ts', () => {
    const optics = O.optic<any>()
      .path(['m', 'n', 'names'])
      .elems()
      .when((name: any) => name.id === id)
    let r = undefined
    const fn = () => (r = O.preview(optics)(data))
    run(fn)
    expect(r).toEqual({ id, name })
  })

  it('monocle-ts', () => {
    const getChildPrism = (id: string) =>
      Prism.fromPredicate((child: any) => child.id === id)
    const childTraversal = fromTraversable(array)<any>()

    const optics = Lens.fromPath<any>()(['m', 'n', 'names'])
      .composeTraversal(childTraversal)
      .composePrism(getChildPrism(id))
      .asFold()

    let r = undefined
    const fn = () => (r = optics.headOption(data))
    run(fn)
    expect(r).toEqual(some({ id, name }))
  })

  it('partial.lenses', () => {
    const optics = L.compose(
      L.prop('m'),
      L.prop('n'),
      L.prop('names'),
      L.find((name: any) => name.id === id),
      L.valueOr(undefined)
    )
    let r = undefined
    const fn = () => (r = L.get(optics, data))
    run(fn)
    expect(r).toEqual({ id, name })
  })

})

describe('prism modify array', () => {
  it('optics-ts', () => {
    const optics = O.optic<any>()
      .path(['m', 'n', 'names'])
      .elems()
      .when((name: any) => name.id === id)
    let r = undefined
    const fn = () =>
      (r = O.modify(optics)((s: any) => ({ ...s, name: nameModified }))(data))
    run(fn)

    let w = O.preview(optics)(r)
    expect(w).toEqual({ id, name: nameModified })
  })

  it('monocle-ts', () => {
    const getChildPrism = (id: string) =>
      Prism.fromPredicate((child: any) => child.id === id)
    const childTraversal = fromTraversable(array)<any>()

    const optics = Lens.fromPath<any>()(['m', 'n', 'names'])
      .composeTraversal(childTraversal)
      .composePrism(getChildPrism(id))

    let r = undefined
    const fn = () =>
      (r = optics.modify((s) => ({ ...s, name: nameModified }))(data))
    run(fn)
    let w = optics.asFold().headOption(r)

    expect(w).toEqual(some({ id, name: nameModified }))
  })

  it('partial.lenses', () => {
    const optics = L.compose(
      L.prop('m'),
      L.prop('n'),
      L.prop('names'),
      L.find((name: any) => name.id === id)
    )
    let r = undefined
    const fn = () =>
      (r = L.modify(optics, (s: any) => ({ ...s, name: nameModified }), data))
    run(fn)

    let w = L.get(optics, r)
    expect(w).toEqual({ id, name: nameModified })
  })

})

Your environment

Which versions of monocle-ts are affected by this issue? Did this work in previous versions of monocle-ts?

Software	Version(s)
monocle-ts	2.1.0
fp-ts	2.5.4
TypeScript	3.8

[Lonli-Lokli]

@gcanti have you looked into this? Write perf is still bad (32sec)

[gcanti]

@Lonli-Lokli added a benchmark for starters

[Lonli-Lokli]

Can you add optics-ts to benchmark as well?

[gcanti]

this is the only optimization I can think of.

optics-ts tests added (not sure what this means though)