funkia/list compatibility? about ts-belt

[paldepind]

Hi @redbar0n. Thanks for the question. From what I can see above the benchmarks only test map, filter, and reduce. These operations are not the most interesting to benchmark as they all are going to have O(n) complexity and for such operations arrays and cons-lists/singly-linked lists are going to be the fastest due to lower constants.

Compared to arrays you get performance benefits with operations where it's possible to achieve an improvement in complexity due to the efficient immutable data structure that List implements. For instance prepend, append, concat, splitAt, insertAt, take, etc. are going to be much faster for large sizes than arrays.

You can see this, for instance, in the insert benchmark. Ramda is slightly faster for small arrays but quickly becomes much slower than List. This is because inserting an element in an array requires copying the entire array. So inserting one element in a 1000 element long array causes all the 1000 elements to be copied into a new array. List on the other hand uses structural sharing to avoid most copying and will have to copy only log_32(1000) ≈ 2 elements.

[mobily]

thanks for the detailed explanation @paldepind 🚀 to sum up:

• ts-belt is compatible with funkia/list
• use funkia/list if you want to achieve high performance when dealing with really large lists, for instance: adding at the head, getting the tail, splitting will be faster, but if you need to randomly access an item funkia/list will be slower

[mobily]

hey @redbar0n 👋

Could ts-belt be used with https://github.com/funkia/list?

yes, you can use the list package with ts-belt

import { pipe, N } from '@mobily/ts-belt' 
import * as L from 'list/curried'

const value = pipe(
  L.list(0, 1, 2, 3, 4, 5),
  L.filter(n => n % 2 === 0),
  L.map(N.multiply(3)),
  L.reduce(N.succ, 0),
)

Would like to see a comparison with ts-belt for the operations they share, like map

I have added here https://github.com/mobily/ts-belt/blob/master/benchmarks/complex/map-filter-reduce.js a new benchmark (combination of Ramda + List)

const {
  makeBenchmark,
  addTsBelt,
  addLodashFp,
  addRambda,
  addRamda,
  addRemeda,
  addList,
} = require('../utils')
const { A } = require('../..')

const L = require('list')

const input = A.range(0, 1000)
const listInput = L.from(input)

const mapFn = x => x * 2
const filterFn = x => x > 1000
const reduceFn = (acc, x) => {
  return acc + x
}

module.exports = makeBenchmark(
  'map → filter → reduce',
  addTsBelt(tsBelt => {
    const { A, pipe } = tsBelt

    return [
      () => {
        return pipe(
          input,
          A.map(mapFn),
          A.filter(filterFn),
          A.reduce(0, reduceFn),
        )
      },
    ]
  }),
  // ⬇️ here
  addList(({ L, pipe }) => {
    return [
      () => {
        return pipe(
          L.map(mapFn),
          L.filter(filterFn),
          L.reduce(reduceFn, 0),
        )(listInput)
      },
    ]
  }),
  addRemeda(remeda => {
    const { pipe, map, filter, reduce } = remeda

    return [
      () => {
        return pipe(input, map(mapFn), filter(filterFn), reduce(reduceFn, 0))
      },
    ]
  }),
  addRamda(ramda => {
    const { pipe, map, filter, reduce } = ramda

    return [
      () => {
        return pipe(map(mapFn), filter(filterFn), reduce(reduceFn, 0))(input)
      },
    ]
  }),
  addRambda(rambda => {
    const { pipe, map, filter, reduce } = rambda

    return [
      () => {
        return pipe(map(mapFn), filter(filterFn), reduce(reduceFn, 0))(input)
      },
    ]
  }),
  addLodashFp(_ => {
    return [
      () => {
        return _.pipe(
          _.map(mapFn),
          _.filter(filterFn),
          _.reduce(reduceFn, 0),
        )(input)
      },
    ]
  }),
)

the benchmark results:

• ./complex/map-filter-reduce.js:

  • map → filter → reduce ......

    ✔  @mobily/ts-belt  165,994.15  ops/sec  ±1.87%  (93 runs)  fastest
    ✔  list              40,080.47  ops/sec  ±6.67%  (84 runs)  -75.85%
    ✔  remeda            11,547.66  ops/sec  ±6.04%  (76 runs)  -93.04%
    ✔  ramda             73,015.38  ops/sec  ±0.51%  (97 runs)  -56.01%
    ✔  rambda           162,945.52  ops/sec  ±1.04%  (93 runs)   -1.84%
    ✔  lodash/fp         51,945.39  ops/sec  ±1.13%  (91 runs)  -68.71%

    ➔ Fastest is @mobily/ts-belt

For a single function call (L.map(fn, listInput)), list is as fast as rambda and ts-belt.

Maybe ts-belt could even benefit from integrating List?

hm, I don't see any benefits, could you provide more details on this topic, please? 🤔 ReScript has List module as well, but AFAIK it's recommended to use it only in specific cases

[redbar0n]

I have added funkia/list to the benchmark suites

awesome! I would rename it to "funkia/list + ramda", since it's using the ramda pipe.

according to the benchmark results I posted above, I'm not quite sure if there are any performance improvements

That's weird.. since List's own benchmarks show tremendous performance improvements over Ramda... Maybe @paldepind could explain?

at this point, I don't see any benefits from integrating list in ts-belt

ok, if using funkia/list with ts-belt doesn't mean any performance improvement like I speculated it would, then it is probably not worth the effort.

[redbar0n]

3. If ts-belt integrated List, then the integration could even be seamless to the user...:

// inside ts-belt:
L.from(["foo", "bar"]); //=> L.list("foo", "bar");
L.toArray(L.list("foo", "bar")); //=> ["foo", "bar"];

So the user could use normal JS arrays. I'm sure the under-the-hood conversion could be done only for arrays of a certain size, but then I imagine the performance improvements could be substantial.

[redbar0n]

Awesome! Thanks! See my latest post above with the details on how ts-belt potentially could benefit from List.

I'm not sure the Ramda benchmark there used the Ramda+List integration.

Maybe you could try this?

addRamda(ramda => {
  const { pipe } = ramda

  return [
    () => {
      return pipe(L.map(mapFn), L.filter(filterFn), L.reduce(reduceFn, 0))(input)
    },
  ]
}),

[mobily]

I'm not sure the Ramda benchmark there used the Ramda+List integration.

ok, I have added funkia/list to the benchmark suites here d3fd667, the latest results:

• ./complex/map-filter-reduce.js:

  • map → filter → reduce ......

    ✔  @mobily/ts-belt  174,023.56  ops/sec  ±0.86%  (93 runs)  fastest
    ✔  remeda            11,695.48  ops/sec  ±6.84%  (75 runs)  -93.28%
    ✔  funkia/list       45,204.73  ops/sec  ±0.91%  (93 runs)  -74.02%
    ✔  ramda             72,785.93  ops/sec  ±0.98%  (96 runs)  -58.17%
    ✔  rambda           158,251.33  ops/sec  ±2.22%  (92 runs)   -9.06%
    ✔  lodash/fp         52,515.78  ops/sec  ±1.05%  (93 runs)  -69.82%

    ➔ Fastest is @mobily/ts-belt

• ./simple/map.js:

  • map (single function call)......

    ✔  @mobily/ts-belt  43,157,266.75  ops/sec  ±1.17%  (92 runs)   -0.18%
    ✔  remeda            1,282,522.25  ops/sec  ±3.24%  (89 runs)  -97.03%
    ✔  funkia/list      34,602,277.96  ops/sec  ±0.67%  (87 runs)  -19.97%
    ✔  ramda             9,827,114.05  ops/sec  ±1.59%  (90 runs)  -77.27%
    ✔  rambda           43,235,021.20  ops/sec  ±1.26%  (92 runs)  fastest
    ✔  lodash/fp         5,964,570.88  ops/sec  ±4.18%  (87 runs)  -86.20%

    ➔ Fastest is rambda,@mobily/ts-belt

  • map (function call inside `pipe`)......

    ✔  @mobily/ts-belt  19,831,428.87  ops/sec  ±1.36%  (88 runs)  fastest
    ✔  remeda            1,132,954.38  ops/sec  ±1.09%  (94 runs)  -94.29%
    ✔  funkia/list       1,260,673.37  ops/sec  ±0.95%  (91 runs)  -93.64%
    ✔  ramda               950,027.59  ops/sec  ±3.65%  (95 runs)  -95.21%
    ✔  rambda           14,286,562.71  ops/sec  ±1.05%  (92 runs)  -27.96%
    ✔  lodash/fp           318,886.17  ops/sec  ±4.16%  (89 runs)  -98.39%

    ➔ Fastest is @mobily/ts-belt

[mobily]

@redbar0n according to the benchmark results I posted above, I'm not quite sure if there are any performance improvements (by the way, you can run benchmarks locally: https://mobily.github.io/ts-belt/benchmarks/introduction#how-to-run-benchmarks)

ts-belt has been built with TypeScript in mind, all Array utility functions return read-only arrays, and avoiding mutations and using read-only arrays is a recommended approach (although a user may want to mutate them, they probably will be doing this intentionally)

anyway, you can still use list in ts-belt (types are correctly inferred in pipe) and at this point, I don't see any benefits from integrating list in ts-belt

let me know what you think 😊