Every call in recursion is slower and slower

[czerwinskilukasz1]

Consider the following program:

🦄 .editor
// Entering editor mode (^D to finish, ^C to cancel)
const f = fun(a) {
  if ((a/1000):equals(floor(a/1000))) {
    log(date(), a)
  }
  f(a+1)
}
f(0)

The first 1000 calls take 4 seconds, the 2nd 1000 calls take 9 seconds, the 3rd 1000 calls take 12 seconds, the 4th 1000 calls take 18 seconds, the 5th 1000 calls take 24 seconds, the 6th 1000 calls take 37 seconds, the 7th 1000 calls take 47 seconds, the 8th 1000 calls take 56 seconds, the 9th 1000 calls takes 67 seconds, 16x slower than the first 1000 calls.

The memory is not very high (670 MB of RAM), so memory is not an issue. I suspect the issue is caused by a total quadratic complexity of accessing the variable f() instead of a linear one (linear complexity instead of a constant one for a single access).

Raw output from the program:

Sat Jun 27 2020 19:33:13 GMT+0200 (Central European Summer Time) 0
Sat Jun 27 2020 19:33:17 GMT+0200 (Central European Summer Time) 1000
Sat Jun 27 2020 19:33:26 GMT+0200 (Central European Summer Time) 2000
Sat Jun 27 2020 19:33:38 GMT+0200 (Central European Summer Time) 3000
Sat Jun 27 2020 19:33:56 GMT+0200 (Central European Summer Time) 4000
Sat Jun 27 2020 19:34:20 GMT+0200 (Central European Summer Time) 5000
Sat Jun 27 2020 19:34:48 GMT+0200 (Central European Summer Time) 6000
Sat Jun 27 2020 19:35:25 GMT+0200 (Central European Summer Time) 7000
Sat Jun 27 2020 19:36:12 GMT+0200 (Central European Summer Time) 8000
Sat Jun 27 2020 19:37:08 GMT+0200 (Central European Summer Time) 9000
Sat Jun 27 2020 19:38:15 GMT+0200 (Central European Summer Time) 10000

[czerwinskilukasz1]

This also affects while.

[czerwinskilukasz1]

Side note:

Currently while works because of the issue with function scopes. When the issue is fixed, while will stop working.

const g = fun () { let a = 10 { a } }

let b = 55 while: { if (!condition) { return } codeBlock() }

const codeBlock = fun() { b }

[czerwinskilukasz1]

Related to #256

[czerwinskilukasz1]

Please note that using while, which uses function calls for each iteration, is not that slow and is not getting slower with each iteration:

while.ask:

let a = 0;
log(date(), a);
while (a < 10000000) {
  if ((a / 1000):equals(floor(a / 1000))) {
    log(date(), a);
  }
  a = a + 1;
}
log(date(), a);

Changes to cli.ts needed, add these lines above const options: Options = {:

const customResources = {
  date: resource({
    type: any,
    async compute(options, code, args) {
      return new Date().toString();
    },
  }),
};

const resources = { ...builtinResources, ...customResources };

and change steps to 10**12 in src/askvm/index.ts.

Result:

Thu Jul 02 2020 16:27:16 GMT+0200 (Central European Summer Time) 0
Thu Jul 02 2020 16:27:16 GMT+0200 (Central European Summer Time) 0
Thu Jul 02 2020 16:27:17 GMT+0200 (Central European Summer Time) 1000
Thu Jul 02 2020 16:27:19 GMT+0200 (Central European Summer Time) 2000
Thu Jul 02 2020 16:27:21 GMT+0200 (Central European Summer Time) 3000
Thu Jul 02 2020 16:27:22 GMT+0200 (Central European Summer Time) 4000
Thu Jul 02 2020 16:27:24 GMT+0200 (Central European Summer Time) 5000
Thu Jul 02 2020 16:27:26 GMT+0200 (Central European Summer Time) 6000
Thu Jul 02 2020 16:27:28 GMT+0200 (Central European Summer Time) 7000
Thu Jul 02 2020 16:27:29 GMT+0200 (Central European Summer Time) 8000
Thu Jul 02 2020 16:27:31 GMT+0200 (Central European Summer Time) 9000
Thu Jul 02 2020 16:27:33 GMT+0200 (Central European Summer Time) 10000
Thu Jul 02 2020 16:27:35 GMT+0200 (Central European Summer Time) 11000
Thu Jul 02 2020 16:27:37 GMT+0200 (Central European Summer Time) 12000
Thu Jul 02 2020 16:27:39 GMT+0200 (Central European Summer Time) 13000
Thu Jul 02 2020 16:27:41 GMT+0200 (Central European Summer Time) 14000
Thu Jul 02 2020 16:27:43 GMT+0200 (Central European Summer Time) 15000
Thu Jul 02 2020 16:27:44 GMT+0200 (Central European Summer Time) 16000
Thu Jul 02 2020 16:27:47 GMT+0200 (Central European Summer Time) 17000
Thu Jul 02 2020 16:27:48 GMT+0200 (Central European Summer Time) 18000
Thu Jul 02 2020 16:27:50 GMT+0200 (Central European Summer Time) 19000
Thu Jul 02 2020 16:27:52 GMT+0200 (Central European Summer Time) 20000
(...)

Every 1000 iterations takes roughly 1.8 seconds and doesn't increase over time.