Performance of sequenceT & sequenceS

[pbadenski]

🐛 Bug report

In general we're very happy with fp-ts performance, but recently we've noticed small problems with sequenceT and specifically the curried function. It's not a huge problem - but a noticeable one and it would be nice if it could be fixed.

Reproducible example

fp-ts generic curried of 1 and 2 arguments + a handrolled curried of 2 arguments for reference.

https://stackblitz.com/edit/fp-ts-curried-performance-jc38ka?file=index.js

curried(1) x 4,532,421 ops/sec ±1.45% (65 runs sampled)

curried(2) x 2,342,792 ops/sec ±0.88% (65 runs sampled)

curried2 handrolled x 34,394,850 ops/sec ±1.55% (62 runs sampled)

Suggested solution(s)

1. (approx 1 order of magnitude, 5-10 x times speed up) Replace acc.concat([x]) with a faster implementation of concat:

const fastConcat = <T>(a: T[], b: T) => {
  const result = Array(a.length + 1);

  for (let i = 0; i < a.length; i++) {
    result[i] = a[i];
  }
  result[a.length] = b;
  return result;
};

2. (solid 1 order of magnitude, 10-50 x times speed up) Handroll the first N (5?) curried implementations, ie.

function curried2<T>(f: Function) {
  return function (x1: T) {
    return function (x2: T) {
      return f(x1, x2);
    };
  }
}

*) alternatively first N implementations could be autogenerated, although this might be a controversial suggestion:
const f = Function("f", `return ${range(1, N).map(n => `x${n}`).join(" => ")} => f(${range(1, N).map(n => `x${n}`).join(" + ")})`);

Your environment

Software	Version(s)
fp-ts	2.5.3
TypeScript	3.9.3

[pbadenski]

Amazing stuff, thank you!

[gcanti]

@pbadenski thanks to you for the report / suggestion 👍