Investigate performance issues with deep cloning

[masaeedu]

@danielo515 provided this testcase in the gitter:

const S = require("sanctuary")
const users = require("./users.json")

const getName = S.prop("name")

const result = S.map(getName)(users)
console.log(result)

A repo to play around with this case is available here.

From my unscientific testing on Linux, I observe that for a user list of a million users, running the code with typechecking disabled finishes in under a second, whereas with typechecking enabled it keeps running past a minute (I eventually gave up waiting and aborted). This is quite a noticeable difference.

After profiling it with node's builtin --prof and --prof-process options, one culprit that pops up is the updateTypeVarMap function. Here's what the processed profiler output looks like:

  18468   68.0%  Builtin: CloneFastJSArray
  18468  100.0%    Builtin: ArrayPrototypeSlice
  18468  100.0%      LazyCompile: *updateTypeVarMap /mnt/data/depot/git/sanctuary_profiling/node_modules/sanctuary-def/index.js:1019:28
  18468  100.0%        LazyCompile: *satisfactoryTypes /mnt/data/depot/git/sanctuary_profiling/node_modules/sanctuary-def/index.js:1105:29
  18461  100.0%          LazyCompile: *<anonymous> /mnt/data/depot/git/sanctuary_profiling/node_modules/sanctuary-def/index.js:1183:43
  18451   99.9%            LazyCompile: *Right$prototype$chain /mnt/data/depot/git/sanctuary_profiling/node_modules/sanctuary-either/index.js:430:33

This function uses slice heavily in order to perform a deep clone of one of the arguments it is passed. After bypassing the logic for doing the deep cloning (which of course is incorrect, but just to estimate the impact) we see that processing a list of 20K users takes ~2s instead of ~20s. There are other culprits pointed out by the profiling output that bear investigation, but this is a good first area for improvement.

There's many approaches that could be used to optimize the deep cloning logic. Examples include:

• rewriting the logic to do copy-on-write
• using an immutable data structure library (which would internally take care of CoW)

Other ideas welcome.

[davidchambers]

Thank you very much, @masaeedu!

[masaeedu]

Note that my tests were run with Node JS (specifically version 10.6.0). Results may not be representative for other runtimes like the browser (or even for other Node JS versions).