perf(mutation): refactor parent removed detection to iterative procedure

[JonasBa]

While looking at some profiles on an adjacent PR, I noticed that we were spending a lot of time inside isParentRemoved.

I added a benchmark to cover a new deep tree test.

Largest change is on the deep tree benchmark I added which went from 475.5 to 377.4ms, the rest looks more or less the same.

Before

console.log
  ┌─────────┬────────────────────────────────┬───────┬──────────┬────────────────────┐
  │ (index) │             title              │ times │ duration │     durations      │
  ├─────────┼────────────────────────────────┼───────┼──────────┼────────────────────┤
  │    0    │ 'append 70 x 70 x 70 elements' │   3   │   1283   │ '1287, 1342, 1220' │
  └─────────┴────────────────────────────────┴───────┴──────────┴────────────────────┘

  at test/benchmark/replay-fast-forward.test.ts:139:17

console.log
  ┌─────────┬────────────────────────────────────────────────┬───────┬──────────┬─────────────────┐
  │ (index) │                     title                      │ times │ duration │    durations    │
  ├─────────┼────────────────────────────────────────────────┼───────┼──────────┼─────────────────┤
  │    0    │ 'append 1000 elements and reverse their order' │   3   │   206    │ '211, 205, 202' │
  └─────────┴────────────────────────────────────────────────┴───────┴──────────┴─────────────────┘

  at test/benchmark/replay-fast-forward.test.ts:139:17

console.log
  ┌─────────┬─────────────────────────────────────────────┬───────┬────────────────────┬────────────────────┐
  │ (index) │                    title                    │ times │      duration      │     durations      │
  ├─────────┼─────────────────────────────────────────────┼───────┼────────────────────┼────────────────────┤
  │    0    │ 'real events recorded on bugs.chromium.org' │   3   │ 1719.3333333333333 │ '1714, 1755, 1689' │
  └─────────┴─────────────────────────────────────────────┴───────┴────────────────────┴────────────────────┘

console.log ┌─────────┬────────────────────────────────────────────────────────┬───────────────────────────────────────────┬─────────────────────┬───────┬──────────┬────────────────────────────────────────────────────┐ │ (index) │ title │ html │ eval │ times │ duration │ durations │ ├─────────┼────────────────────────────────────────────────────────┼───────────────────────────────────────────┼─────────────────────┼───────┼──────────┼────────────────────────────────────────────────────┤ │ 0 │ 'create 1000x 1 DOM nodes with deeply nested children' │ 'benchmark-dom-mutation-deep-nested.html' │ 'window.workload()' │ 10 │ 475.5 │ '481, 461, 488, 477, 470, 514, 449, 471, 472, 472' │ └─────────┴────────────────────────────────────────────────────────┴───────────────────────────────────────────┴─────────────────────┴───────┴──────────┴────────────────────────────────────────────────────┘

  at test/benchmark/dom-mutation.test.ts:194:15

console.log
  profile:  /Users/jonasbadalic/code/rrweb/packages/rrweb/temp/profile-2024-05-30T22:52:53.804Z.json

  at test/benchmark/dom-mutation.test.ts:201:15

console.log
  ┌─────────┬────────────────────────────┬───────────────────────────────┬─────────────────────┬───────┬──────────┬──────────────────────────────────────────┐
  │ (index) │           title            │             html              │        eval         │ times │ duration │                durations                 │
  ├─────────┼────────────────────────────┼───────────────────────────────┼─────────────────────┼───────┼──────────┼──────────────────────────────────────────┤
  │    0    │ 'create 1000x10 DOM nodes' │ 'benchmark-dom-mutation.html' │ 'window.workload()' │  10   │   63.7   │ '66, 67, 65, 63, 63, 64, 63, 62, 62, 62' │
  └─────────┴────────────────────────────┴───────────────────────────────┴─────────────────────┴───────┴──────────┴──────────────────────────────────────────┘

  at test/benchmark/dom-mutation.test.ts:194:15

console.log
  profile:  /Users/jonasbadalic/code/rrweb/packages/rrweb/temp/profile-2024-05-30T22:53:05.559Z.json

  at test/benchmark/dom-mutation.test.ts:201:15

console.log
  ┌─────────┬─────────────────────────────────────────────────────────┬──────────────────────────────────────────────┬─────────────────────┬───────┬──────────┬─────────────────────────────────────────────┐
  │ (index) │                          title                          │                     html                     │        eval         │ times │ duration │                  durations                  │
  ├─────────┼─────────────────────────────────────────────────────────┼──────────────────────────────────────────────┼─────────────────────┼───────┼──────────┼─────────────────────────────────────────────┤
  │    0    │ 'create 1000x10x2 DOM nodes and remove a bunch of them' │ 'benchmark-dom-mutation-add-and-remove.html' │ 'window.workload()' │  10   │    99    │ '100, 97, 99, 110, 91, 92, 113, 97, 96, 95' │
  └─────────┴─────────────────────────────────────────────────────────┴──────────────────────────────────────────────┴─────────────────────┴───────┴──────────┴─────────────────────────────────────────────┘

  at test/benchmark/dom-mutation.test.ts:194:15

console.log
  profile:  /Users/jonasbadalic/code/rrweb/packages/rrweb/temp/profile-2024-05-30T22:53:09.485Z.json

  at test/benchmark/dom-mutation.test.ts:201:15

console.log
  ┌─────────┬──────────────────────────────────────────────────────────────────┬───────────────────────────────────────────────────────┬─────────────────────┬───────┬──────────┬──────────────────────┐
  │ (index) │                              title                               │                         html                          │        eval         │ times │ duration │      durations       │
  ├─────────┼──────────────────────────────────────────────────────────────────┼───────────────────────────────────────────────────────┼─────────────────────┼───────┼──────────┼──────────────────────┤
  │    0    │ 'create 1000 DOM nodes and append into its previous looped node' │ 'benchmark-dom-mutation-multiple-descendant-add.html' │ 'window.workload()' │   5   │   28.2   │ '27, 29, 28, 29, 28' │
  └─────────┴──────────────────────────────────────────────────────────────────┴───────────────────────────────────────────────────────┴─────────────────────┴───────┴──────────┴──────────────────────┘

  at test/benchmark/dom-mutation.test.ts:194:15

console.log
  profile:  /Users/jonasbadalic/code/rrweb/packages/rrweb/temp/profile-2024-05-30T22:53:14.021Z.json

  at test/benchmark/dom-mutation.test.ts:201:15

console.log
  ┌─────────┬───────────────────────────────────────────────────────┬────────────────────────────────────────────┬─────────────────────┬───────┬──────────┬───────────────────────────┐
  │ (index) │                         title                         │                    html                    │        eval         │ times │ duration │         durations         │
  ├─────────┼───────────────────────────────────────────────────────┼────────────────────────────────────────────┼─────────────────────┼───────┼──────────┼───────────────────────────┤
  │    0    │ 'create 10000 DOM nodes and move it to new container' │ 'benchmark-dom-mutation-add-and-move.html' │ 'window.workload()' │   5   │  105.6   │ '102, 117, 105, 104, 100' │
  └─────────┴───────────────────────────────────────────────────────┴────────────────────────────────────────────┴─────────────────────┴───────┴──────────┴───────────────────────────┘

  at test/benchmark/dom-mutation.test.ts:194:15

console.log
  profile:  /Users/jonasbadalic/code/rrweb/packages/rrweb/temp/profile-2024-05-30T22:53:16.499Z.json

  at test/benchmark/dom-mutation.test.ts:201:15

console.log
  ┌─────────┬────────────────────────────────────────┬──────────────────────────────────────────┬─────────────────────┬───────┬──────────┬──────────────────────────────────────────┐
  │ (index) │                 title                  │                   html                   │        eval         │ times │ duration │                durations                 │
  ├─────────┼────────────────────────────────────────┼──────────────────────────────────────────┼─────────────────────┼───────┼──────────┼──────────────────────────────────────────┤
  │    0    │ 'modify attributes on 10000 DOM nodes' │ 'benchmark-dom-mutation-attributes.html' │ 'window.workload()' │  10   │   22.4   │ '22, 22, 23, 23, 21, 26, 18, 20, 29, 20' │
  └─────────┴────────────────────────────────────────┴──────────────────────────────────────────┴─────────────────────┴───────┴──────────┴──────────────────────────────────────────┘

  at test/benchmark/dom-mutation.test.ts:194:15

After console.log ┌─────────┬────────────────────────────────┬───────┬────────────────────┬────────────────────┐ │ (index) │ title │ times │ duration │ durations │ ├─────────┼────────────────────────────────┼───────┼────────────────────┼────────────────────┤ │ 0 │ 'append 70 x 70 x 70 elements' │ 3 │ 1320.3333333333333 │ '1366, 1299, 1296' │ └─────────┴────────────────────────────────┴───────┴────────────────────┴────────────────────┘

  at test/benchmark/replay-fast-forward.test.ts:139:17

console.log
  ┌─────────┬────────────────────────────────────────────────┬───────┬────────────────────┬─────────────────┐
  │ (index) │                     title                      │ times │      duration      │    durations    │
  ├─────────┼────────────────────────────────────────────────┼───────┼────────────────────┼─────────────────┤
  │    0    │ 'append 1000 elements and reverse their order' │   3   │ 206.66666666666666 │ '205, 205, 210' │
  └─────────┴────────────────────────────────────────────────┴───────┴────────────────────┴─────────────────┘

  at test/benchmark/replay-fast-forward.test.ts:139:17

console.log
  ┌─────────┬─────────────────────────────────────────────┬───────┬────────────────────┬────────────────────┐
  │ (index) │                    title                    │ times │      duration      │     durations      │
  ├─────────┼─────────────────────────────────────────────┼───────┼────────────────────┼────────────────────┤
  │    0    │ 'real events recorded on bugs.chromium.org' │   3   │ 1741.6666666666667 │ '1787, 1716, 1722' │
  └─────────┴─────────────────────────────────────────────┴───────┴────────────────────┴────────────────────┘

  at test/benchmark/replay-fast-forward.test.ts:139:17

console.log ┌─────────┬────────────────────────────────────────────────────────┬───────────────────────────────────────────┬─────────────────────┬───────┬──────────┬────────────────────────────────────────────────────┐ │ (index) │ title │ html │ eval │ times │ duration │ durations │ ├─────────┼────────────────────────────────────────────────────────┼───────────────────────────────────────────┼─────────────────────┼───────┼──────────┼────────────────────────────────────────────────────┤ │ 0 │ 'create 1000x 1 DOM nodes with deeply nested children' │ 'benchmark-dom-mutation-deep-nested.html' │ 'window.workload()' │ 10 │ 377.4 │ '385, 369, 398, 366, 373, 369, 376, 410, 359, 369' │ └─────────┴────────────────────────────────────────────────────────┴───────────────────────────────────────────┴─────────────────────┴───────┴──────────┴────────────────────────────────────────────────────┘

  at test/benchmark/dom-mutation.test.ts:194:15

console.log
  profile:  /Users/jonasbadalic/code/rrweb/packages/rrweb/temp/profile-2024-05-30T22:55:02.488Z.json

  at test/benchmark/dom-mutation.test.ts:201:15

console.log
  ┌─────────┬────────────────────────────┬───────────────────────────────┬─────────────────────┬───────┬──────────┬──────────────────────────────────────────┐
  │ (index) │           title            │             html              │        eval         │ times │ duration │                durations                 │
  ├─────────┼────────────────────────────┼───────────────────────────────┼─────────────────────┼───────┼──────────┼──────────────────────────────────────────┤
  │    0    │ 'create 1000x10 DOM nodes' │ 'benchmark-dom-mutation.html' │ 'window.workload()' │  10   │   65.2   │ '69, 67, 65, 64, 64, 64, 62, 65, 67, 65' │
  └─────────┴────────────────────────────┴───────────────────────────────┴─────────────────────┴───────┴──────────┴──────────────────────────────────────────┘

  at test/benchmark/dom-mutation.test.ts:194:15

console.log
  profile:  /Users/jonasbadalic/code/rrweb/packages/rrweb/temp/profile-2024-05-30T22:55:12.615Z.json

  at test/benchmark/dom-mutation.test.ts:201:15

console.log
  ┌─────────┬─────────────────────────────────────────────────────────┬──────────────────────────────────────────────┬─────────────────────┬───────┬──────────┬───────────────────────────────────────────────┐
  │ (index) │                          title                          │                     html                     │        eval         │ times │ duration │                   durations                   │
  ├─────────┼─────────────────────────────────────────────────────────┼──────────────────────────────────────────────┼─────────────────────┼───────┼──────────┼───────────────────────────────────────────────┤
  │    0    │ 'create 1000x10x2 DOM nodes and remove a bunch of them' │ 'benchmark-dom-mutation-add-and-remove.html' │ 'window.workload()' │  10   │  103.6   │ '97, 104, 99, 121, 100, 107, 117, 99, 95, 97' │
  └─────────┴─────────────────────────────────────────────────────────┴──────────────────────────────────────────────┴─────────────────────┴───────┴──────────┴───────────────────────────────────────────────┘

  at test/benchmark/dom-mutation.test.ts:194:15

console.log
  profile:  /Users/jonasbadalic/code/rrweb/packages/rrweb/temp/profile-2024-05-30T22:55:16.543Z.json

  at test/benchmark/dom-mutation.test.ts:201:15

console.log
  ┌─────────┬──────────────────────────────────────────────────────────────────┬───────────────────────────────────────────────────────┬─────────────────────┬───────┬──────────┬──────────────────────┐
  │ (index) │                              title                               │                         html                          │        eval         │ times │ duration │      durations       │
  ├─────────┼──────────────────────────────────────────────────────────────────┼───────────────────────────────────────────────────────┼─────────────────────┼───────┼──────────┼──────────────────────┤
  │    0    │ 'create 1000 DOM nodes and append into its previous looped node' │ 'benchmark-dom-mutation-multiple-descendant-add.html' │ 'window.workload()' │   5   │   28.2   │ '27, 30, 28, 28, 28' │
  └─────────┴──────────────────────────────────────────────────────────────────┴───────────────────────────────────────────────────────┴─────────────────────┴───────┴──────────┴──────────────────────┘

  at test/benchmark/dom-mutation.test.ts:194:15

console.log
  profile:  /Users/jonasbadalic/code/rrweb/packages/rrweb/temp/profile-2024-05-30T22:55:21.232Z.json

  at test/benchmark/dom-mutation.test.ts:201:15

console.log
  ┌─────────┬───────────────────────────────────────────────────────┬────────────────────────────────────────────┬─────────────────────┬───────┬──────────┬───────────────────────────┐
  │ (index) │                         title                         │                    html                    │        eval         │ times │ duration │         durations         │
  ├─────────┼───────────────────────────────────────────────────────┼────────────────────────────────────────────┼─────────────────────┼───────┼──────────┼───────────────────────────┤
  │    0    │ 'create 10000 DOM nodes and move it to new container' │ 'benchmark-dom-mutation-add-and-move.html' │ 'window.workload()' │   5   │  106.2   │ '107, 117, 102, 103, 102' │
  └─────────┴───────────────────────────────────────────────────────┴────────────────────────────────────────────┴─────────────────────┴───────┴──────────┴───────────────────────────┘

  at test/benchmark/dom-mutation.test.ts:194:15

console.log
  profile:  /Users/jonasbadalic/code/rrweb/packages/rrweb/temp/profile-2024-05-30T22:55:23.714Z.json

  at test/benchmark/dom-mutation.test.ts:201:15

console.log
  ┌─────────┬────────────────────────────────────────┬──────────────────────────────────────────┬─────────────────────┬───────┬──────────┬──────────────────────────────────────────┐
  │ (index) │                 title                  │                   html                   │        eval         │ times │ duration │                durations                 │
  ├─────────┼────────────────────────────────────────┼──────────────────────────────────────────┼─────────────────────┼───────┼──────────┼──────────────────────────────────────────┤
  │    0    │ 'modify attributes on 10000 DOM nodes' │ 'benchmark-dom-mutation-attributes.html' │ 'window.workload()' │  10   │   23.5   │ '22, 30, 21, 23, 32, 20, 23, 18, 20, 26' │
  └─────────┴────────────────────────────────────────┴──────────────────────────────────────────┴─────────────────────┴───────┴──────────┴──────────────────────────────────────────┘

  at test/benchmark/dom-mutation.test.ts:194:15

console.log

[changeset-bot[bot]]

🦋 Changeset detected

Latest commit: 57ed19c1137f7f2d0fc4ee42695df97bdd505dae

The changes in this PR will be included in the next version bump.

This PR includes changesets to release 8 packages

| Name | Type | | -------------------- | ----- | | rrweb | Patch | | rrweb-snapshot | Patch | | rrdom | Patch | | rrdom-nodejs | Patch | | rrweb-player | Patch | | @rrweb/types | Patch | | @rrweb/web-extension | Patch | | rrvideo | Patch |

Not sure what this means? Click here to learn what changesets are.

Click here if you're a maintainer who wants to add another changeset to this PR

[Juice10]

Good catch Jonas, could you add a changeset, then I'll merge it

[JonasBa]

@Juice10 sounds good, I just added the patch changeset. Let me know if there is anything else I can do

[JonasBa]

I think there is something up with gh ci, that check if failing on a network timeout

[JonasBa]

@Juice10 Mind restarting CI here, I cant seem to be able to trigger it (unless you want me to push an empty commit here)

[Juice10]

@JonasBa sure!