perf: optimize performance of the DoubleLinkedList get by wfk007 · Pull Request #1220 · rrweb-io/rrweb

wfk007 · 2023-05-06T10:32:51Z

benchmark-dom-mutation.html

almost the same

- before average: 142.6 
+ after average: 138.9

before:

┌─────────┬────────────────────────────┬───────────────────────────────┬─────────────────────┬───────┬──────────┬────────────────────────────────────────────────────┐
    │ (index) │           title            │             html              │        eval         │ times │ duration │                     durations                      │
    ├─────────┼────────────────────────────┼───────────────────────────────┼─────────────────────┼───────┼──────────┼────────────────────────────────────────────────────┤
    │    0    │ 'create 1000x10 DOM nodes' │ 'benchmark-dom-mutation.html' │ 'window.workload()' │  10   │  142.6   │ '141, 138, 158, 136, 132, 174, 124, 126, 145, 152' │
    └─────────┴────────────────────────────┴───────────────────────────────┴─────────────────────┴───────┴──────────┴────────────────────────────────────────────────────┘

after:

┌─────────┬────────────────────────────┬───────────────────────────────┬─────────────────────┬───────┬──────────┬────────────────────────────────────────────────────┐
    │ (index) │           title            │             html              │        eval         │ times │ duration │                     durations                      │
    ├─────────┼────────────────────────────┼───────────────────────────────┼─────────────────────┼───────┼──────────┼────────────────────────────────────────────────────┤
    │    0    │ 'create 1000x10 DOM nodes' │ 'benchmark-dom-mutation.html' │ 'window.workload()' │  10   │  138.9   │ '139, 134, 151, 134, 133, 137, 168, 131, 131, 131' │
    └─────────┴────────────────────────────┴───────────────────────────────┴─────────────────────┴───────┴──────────┴────────────────────────────────────────────────────┘

benchmark-dom-mutation-add-and-remove.html

almost the same

- before average: 233.8
+ after average: 225.4

before:

┌─────────┬─────────────────────────────────────────────────────────┬──────────────────────────────────────────────┬─────────────────────┬───────┬──────────┬────────────────────────────────────────────────────┐
    │ (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   │  233.8   │ '228, 252, 236, 222, 234, 205, 224, 302, 203, 232' │
    └─────────┴─────────────────────────────────────────────────────────┴──────────────────────────────────────────────┴─────────────────────┴───────┴──────────┴────────────────────────────────────────────────────┘

after:

┌─────────┬─────────────────────────────────────────────────────────┬──────────────────────────────────────────────┬─────────────────────┬───────┬──────────┬────────────────────────────────────────────────────┐
    │ (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   │  225.4   │ '211, 236, 255, 250, 242, 208, 223, 244, 183, 202' │
    └─────────┴─────────────────────────────────────────────────────────┴──────────────────────────────────────────────┴─────────────────────┴───────┴──────────┴────────────────────────────────────────────────────┘

benchmark-dom-mutation-multiple-descendant-add.html

almost the same

- before average: 66.4
+ after average: 58

before:

┌─────────┬──────────────────────────────────────────────────────────────────┬───────────────────────────────────────────────────────┬─────────────────────┬───────┬──────────┬──────────────────────┐
    │ (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   │   66.4   │ '67, 67, 63, 65, 70' │
    └─────────┴──────────────────────────────────────────────────────────────────┴───────────────────────────────────────────────────────┴─────────────────────┴───────┴──────────┴──────────────────────┘

after:

┌─────────┬──────────────────────────────────────────────────────────────────┬───────────────────────────────────────────────────────┬─────────────────────┬───────┬──────────┬──────────────────────┐
    │ (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   │    58    │ '60, 60, 56, 58, 56' │
    └─────────┴──────────────────────────────────────────────────────────────────┴───────────────────────────────────────────────────────┴─────────────────────┴───────┴──────────┴──────────────────────┘

benchmark-dom-mutation-add-and-move.html

decrease by about 86.11%

- before average: 1625.4
+ after average: 225.8

before:

┌─────────┬───────────────────────────────────────────────────────┬────────────────────────────────────────────┬─────────────────────┬───────┬──────────┬────────────────────────────────┐
    │ (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   │  1625.4  │ '1692, 1298, 2176, 1006, 1955' │
    └─────────┴───────────────────────────────────────────────────────┴────────────────────────────────────────────┴─────────────────────┴───────┴──────────┴────────────────────────────────┘

after:

┌─────────┬───────────────────────────────────────────────────────┬────────────────────────────────────────────┬─────────────────────┬───────┬──────────┬───────────────────────────┐
    │ (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   │  225.8   │ '235, 212, 256, 216, 210' │
    └─────────┴───────────────────────────────────────────────────────┴────────────────────────────────────────────┴─────────────────────┴───────┴──────────┴───────────────────────────┘

changeset-bot · 2023-05-06T10:32:54Z

🦋 Changeset detected

Latest commit: d4e1a64

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

YunFeng0817

Looks really great!

charliegracie · 2023-05-12T13:16:17Z

Hi.

Recently we were looking into the same issue it seems. I was just about to open a PR when I noticed yours. We came up with a pretty similar change in the end. The one difference is that instead of building the array of DoubleLinkedListNode elements we added a tail node to the current linked list. The change to the DoubleLinkedList is pretty trivial and then you can just walk the list backwards without having to find the last node by fetching tail each time.

I could share a diff if you are interested.

wfk007 · 2023-05-15T02:21:30Z

@charliegracie Sure, I am really really interested in your change and it seems more elegant than this.

wfk007 · 2023-05-16T12:22:54Z

@YunFeng0817 @charliegracie I updated this PR with the tail pointer scheme and updated the benchmark tests.

According to the last benchmark test(benchmark-dom-mutation-add-and-move.html), the performance increased by about 86.11%, and it works well in other benchmark tests too.

Could your please help me review this change at your convenience?

YunFeng0817

@charliegracie Could you please also take a look at this? Is this similar to your solution?

* perf: optimize performance of the DoubleLinkedList get * fix: delete addedNodeIndexArr

wfk007 mentioned this pull request May 6, 2023

Perf: optimize the performance of processMutations #1187

Closed

YunFeng0817 approved these changes May 7, 2023

View reviewed changes

perf: optimize performance of the DoubleLinkedList get

80ceb0e

wfk007 force-pushed the perf/rrweb-record-linkedList-get branch from 4464146 to 80ceb0e Compare May 15, 2023 12:24

fix: delete addedNodeIndexArr

d4e1a64

YunFeng0817 approved these changes May 16, 2023

View reviewed changes

YunFeng0817 merged commit a1ec9a2 into rrweb-io:master May 22, 2023

This was referenced May 22, 2023

Version Packages (alpha) #1216

Merged

Version Packages (alpha) wfk007/rrweb#1

Open

This was referenced Jun 14, 2023

Version Packages (alpha) QuentinLowe/rrweb#1

Open

Version Packages (alpha) getsentry/rrweb#90

Closed

This was referenced Jul 6, 2023

add sentry v1 tests getsentry/rrweb#93

Closed

feat mask all text pr getsentry/rrweb#94

Closed

feat add custom attribute transform getsentry/rrweb#96

Closed

billyvg mentioned this pull request Jul 17, 2023

feat pass element to maskTextFn getsentry/rrweb#99

Closed

eoghanmurray pushed a commit to eoghanmurray/rrweb that referenced this pull request Jul 27, 2023

perf: optimize performance of the DoubleLinkedList get (rrweb-io#1220)

50bcf66

* perf: optimize performance of the DoubleLinkedList get * fix: delete addedNodeIndexArr

eoghanmurray pushed a commit to eoghanmurray/rrweb that referenced this pull request Jul 27, 2023

perf: optimize performance of the DoubleLinkedList get (rrweb-io#1220)

0ae888b

* perf: optimize performance of the DoubleLinkedList get * fix: delete addedNodeIndexArr

eoghanmurray pushed a commit to eoghanmurray/rrweb that referenced this pull request Jul 27, 2023

perf: optimize performance of the DoubleLinkedList get (rrweb-io#1220)

48b5f7b

* perf: optimize performance of the DoubleLinkedList get * fix: delete addedNodeIndexArr

eoghanmurray pushed a commit to eoghanmurray/rrweb that referenced this pull request Aug 3, 2023

perf: optimize performance of the DoubleLinkedList get (rrweb-io#1220)

a32e53e

* perf: optimize performance of the DoubleLinkedList get * fix: delete addedNodeIndexArr

eoghanmurray pushed a commit to eoghanmurray/rrweb that referenced this pull request Aug 8, 2023

perf: optimize performance of the DoubleLinkedList get (rrweb-io#1220)

320b6f4

* perf: optimize performance of the DoubleLinkedList get * fix: delete addedNodeIndexArr

eoghanmurray pushed a commit to eoghanmurray/rrweb that referenced this pull request Aug 8, 2023

perf: optimize performance of the DoubleLinkedList get (rrweb-io#1220)

3f6a67e

* perf: optimize performance of the DoubleLinkedList get * fix: delete addedNodeIndexArr

wfk007 mentioned this pull request Dec 13, 2023

fix(perf): benchmark processMutations/addList worst case performance #1300

Draft

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

perf: optimize performance of the DoubleLinkedList get#1220

perf: optimize performance of the DoubleLinkedList get#1220
YunFeng0817 merged 2 commits intorrweb-io:masterfrom
wfk007:perf/rrweb-record-linkedList-get

wfk007 commented May 6, 2023 •

edited

Loading

Uh oh!

changeset-bot bot commented May 6, 2023 •

edited

Loading

Uh oh!

YunFeng0817 left a comment

Uh oh!

charliegracie commented May 12, 2023

Uh oh!

wfk007 commented May 15, 2023

Uh oh!

wfk007 commented May 16, 2023

Uh oh!

YunFeng0817 left a comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

Uh oh!

Conversation

wfk007 commented May 6, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

benchmark-dom-mutation.html

benchmark-dom-mutation-add-and-remove.html

benchmark-dom-mutation-multiple-descendant-add.html

benchmark-dom-mutation-add-and-move.html

Uh oh!

changeset-bot bot commented May 6, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

🦋 Changeset detected

Uh oh!

YunFeng0817 left a comment

Choose a reason for hiding this comment

Uh oh!

charliegracie commented May 12, 2023

Uh oh!

wfk007 commented May 15, 2023

Uh oh!

wfk007 commented May 16, 2023

Uh oh!

YunFeng0817 left a comment

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

wfk007 commented May 6, 2023 •

edited

Loading

changeset-bot bot commented May 6, 2023 •

edited

Loading