Performance Analysis and Improvement of Yorkie #1
Description
Background
Yorkie has been added to the CRDT library benchmark tests. While the tests are currently set up to run, there are several areas that need further investigation and improvement.
Ref: https://codepair.yorkie.dev/chacha/67d904220c79e468f8b82e7f/share?token=gkxxyp
Tasks
- Identify the cause of Yorkie's high values in
encodeTime,docSize,memUsed,time,updateSize. The measurement values may have been incorrectly set, or the actual performance might be poor. Analysis and improvement for this issue are needed. - Implement
transactmethod of AbstractCrdt
Benchmark results
https://github.com/yorkie-team/crdt-benchmarks/actions/runs/13764918707/job/38489036517
- Performance of algorithms was tested by directly creating and applying changes, excluding server communication parts.
- Loro has competitive performance in
memUsedandparseTime, while Yjs has advantages inupdateSize,encodeTime, andbundle size.
| N = 6000 | yorkie | yorkie-lamport | yjs | ywasm | loro | automerge | diamond-types |
|---|---|---|---|---|---|---|---|
| Version | 0.0.0 | 0.0.0 | 13.6.24 | 0.17.4 | 0.10.1 | 2.2.8 | 1.0.2 |
| Bundle size | 262,673 bytes | 257,414 bytes | 69,909 bytes | 954,634 bytes | 1,043,345 bytes | 2,212,275 bytes | 268,316 bytes |
| Bundle size (gzipped) | 59,166 bytes | 57,991 bytes | 20,396 bytes | 286,711 bytes | 396,477 bytes | 741,913 bytes | 107,314 bytes |
| [B1.1] Append N characters (time) | 1,135 ms | 893 ms | 347 ms | 236 ms | 307 ms | 660 ms | 164 ms |
| [B1.1] Append N characters (avgUpdateSize) | 260 bytes | 141 bytes | 27 bytes | 27 bytes | 109 bytes | 125 bytes | 70 bytes |
| [B1.1] Append N characters (encodeTime) | 85 ms | 87 ms | 1 ms | 1 ms | 1 ms | 14 ms | 0 ms |
| [B1.1] Append N characters (docSize) | 168,139 bytes | 168,099 bytes | 6,031 bytes | 6,031 bytes | 6,162 bytes | 4,003 bytes | 6,095 bytes |
| [B1.1] Append N characters (memUsed) | 4.6 MB | 4.8 MB | 0 B | 0 B | 0 B | 0 B | 0 B |
| [B1.1] Append N characters (parseTime) | 119 ms | 117 ms | 40 ms | 34 ms | 37 ms | 113 ms | 40 ms |
| [B1.2] Insert string of length N (time) | 1 ms | 1 ms | 2 ms | 0 ms | 1 ms | 42 ms | skipped |
| [B1.2] Insert string of length N (avgUpdateSize) | 6,243 bytes | 6,127 bytes | 6,031 bytes | 6,031 bytes | 6,107 bytes | 6,209 bytes | skipped |
| [B1.2] Insert string of length N (encodeTime) | 1 ms | 1 ms | 0 ms | 0 ms | 0 ms | 6 ms | skipped |
| [B1.2] Insert string of length N (docSize) | 6,285 bytes | 6,247 bytes | 6,031 bytes | 6,031 bytes | 6,117 bytes | 3,979 bytes | skipped |
| [B1.2] Insert string of length N (memUsed) | 42.2 kB | 0 B | 42.4 kB | 352.5 kB | 17.9 kB | 7.6 kB | skipped |
| [B1.2] Insert string of length N (parseTime) | 62 ms | 59 ms | 44 ms | 40 ms | 42 ms | 61 ms | skipped |
| [B1.3] Prepend N characters (time) | 1,099 ms | 838 ms | 305 ms | 55 ms | 166 ms | 546 ms | 112 ms |
| [B1.3] Prepend N characters (avgUpdateSize) | 246 bytes | 127 bytes | 27 bytes | 27 bytes | 108 bytes | 120 bytes | 68 bytes |
| [B1.3] Prepend N characters (encodeTime) | 81 ms | 76 ms | 4 ms | 1 ms | 13 ms | 7 ms | 0 ms |
| [B1.3] Prepend N characters (docSize) | 168,139 bytes | 168,099 bytes | 6,041 bytes | 6,041 bytes | 12,125 bytes | 3,995 bytes | 12,093 bytes |
| [B1.3] Prepend N characters (memUsed) | 4.8 MB | 4.9 MB | 1 MB | 8.6 kB | 17.4 kB | 16.7 kB | 6.5 kB |
| [B1.3] Prepend N characters (parseTime) | 134 ms | 128 ms | 80 ms | 37 ms | 43 ms | 110 ms | 45 ms |
| [B1.4] Insert N characters at random positions (time) | 1,502 ms | 1,261 ms | 290 ms | 174 ms | 170 ms | 562 ms | 108 ms |
| [B1.4] Insert N characters at random positions (avgUpdateSize) | 260 bytes | 141 bytes | 29 bytes | 29 bytes | 109 bytes | 125 bytes | 69 bytes |
| [B1.4] Insert N characters at random positions (encodeTime) | 84 ms | 86 ms | 5 ms | 1 ms | 36 ms | 16 ms | 0 ms |
| [B1.4] Insert N characters at random positions (docSize) | 168,139 bytes | 168,099 bytes | 29,554 bytes | 29,554 bytes | 35,401 bytes | 24,750 bytes | 20,166 bytes |
| [B1.4] Insert N characters at random positions (memUsed) | 4.7 MB | 4.8 MB | 1.1 MB | 0 B | 1.3 kB | 0 B | 0 B |
| [B1.4] Insert N characters at random positions (parseTime) | 129 ms | 132 ms | 99 ms | 44 ms | 39 ms | 146 ms | 44 ms |
| [B1.5] Insert N words at random positions (time) | 1,873 ms | 1,585 ms | 341 ms | 376 ms | 171 ms | 984 ms | skipped |
| [B1.5] Insert N words at random positions (avgUpdateSize) | 266 bytes | 147 bytes | 36 bytes | 36 bytes | 117 bytes | 135 bytes | skipped |
| [B1.5] Insert N words at random positions (encodeTime) | 144 ms | 147 ms | 11 ms | 1 ms | 71 ms | 23 ms | skipped |
| [B1.5] Insert N words at random positions (docSize) | 323,370 bytes | 323,328 bytes | 87,924 bytes | 87,924 bytes | 94,524 bytes | 96,215 bytes | skipped |
| [B1.5] Insert N words at random positions (memUsed) | 8.4 MB | 8.6 MB | 2.3 MB | 592 B | 768 B | 22 kB | skipped |
| [B1.5] Insert N words at random positions (parseTime) | 183 ms | 184 ms | 85 ms | 46 ms | 44 ms | 226 ms | skipped |
| [B1.6] Insert string, then delete it (time) | 6 ms | 3 ms | 4 ms | 1 ms | 3 ms | 98 ms | skipped |
| [B1.6] Insert string, then delete it (avgUpdateSize) | 6,538 bytes | 6,306 bytes | 6,053 bytes | 6,053 bytes | 6,217 bytes | 6,351 bytes | skipped |
| [B1.6] Insert string, then delete it (encodeTime) | 1 ms | 1 ms | 0 ms | 0 ms | 0 ms | 7 ms | skipped |
| [B1.6] Insert string, then delete it (docSize) | 6,305 bytes | 6,267 bytes | 38 bytes | 38 bytes | 6,120 bytes | 3,999 bytes | skipped |
| [B1.6] Insert string, then delete it (memUsed) | 12.7 kB | 49.5 kB | 0 B | 0 B | 1.3 kB | 1.5 kB | skipped |
| [B2.4] Concurrently insert & delete (updateSize) | 3,717,392 bytes | 1,917,006 bytes | 139,517 bytes | 139,517 bytes | 163,564 bytes | 298,824 bytes | skipped |
| [B2.4] Concurrently insert & delete (encodeTime) | 328 ms | 505 ms | 12 ms | 11 ms | 257 ms | 67 ms | skipped |
| [B2.4] Concurrently insert & delete (docSize) | 710,914 bytes | 1,180,387 bytes | 279,172 bytes | 279,172 bytes | 289,595 bytes | 293,837 bytes | skipped |
| [B2.4] Concurrently insert & delete (memUsed) | 18.5 MB | 32.7 MB | 7.7 MB | 72 B | 3.1 kB | 82.4 kB | skipped |
| [B2.4] Concurrently insert & delete (parseTime) | 432 ms | 625 ms | 184 ms | 128 ms | 76 ms | 345 ms | skipped |
| [B3.1] 20√N clients concurrently set number in Map (time) | 2,760 ms | 50 ms | 85 ms | 158 ms | 65 ms | 1,671 ms | skipped |
| [B3.1] 20√N clients concurrently set number in Map (updateSize) | 361,900 bytes | 181,720 bytes | 49,173 bytes | 49,179 bytes | 161,636 bytes | 295,616 bytes | skipped |
| [B3.1] 20√N clients concurrently set number in Map (encodeTime) | 4 ms | 1 ms | 5 ms | 3 ms | 4 ms | 6 ms | skipped |
| [B3.1] 20√N clients concurrently set number in Map (docSize) | 46,484 bytes | 273 bytes | 32,225 bytes | 32,238 bytes | 21,505 bytes | 86,171 bytes | skipped |
| [B3.1] 20√N clients concurrently set number in Map (memUsed) | 0 B | 0 B | 597.4 kB | 0 B | 704 B | 0 B | skipped |
| [B3.1] 20√N clients concurrently set number in Map (parseTime) | 101 ms | 89 ms | 103 ms | 92 ms | 66 ms | 78 ms | skipped |
| [B3.2] 20√N clients concurrently set Object in Map (time) | 2,776 ms | 96 ms | 94 ms | 164 ms | 91 ms | 1,801 ms | skipped |
| [B3.2] 20√N clients concurrently set Object in Map (updateSize) | 585,630 bytes | 406,990 bytes | 85,083 bytes | 85,078 bytes | 200,630 bytes | 410,410 bytes | skipped |
| [B3.2] 20√N clients concurrently set Object in Map (encodeTime) | 4 ms | 0 ms | 4 ms | 2 ms | 18 ms | 29 ms | skipped |
| [B3.2] 20√N clients concurrently set Object in Map (docSize) | 46,605 bytes | 394 bytes | 32,243 bytes | 32,237 bytes | 40,650 bytes | 112,507 bytes | skipped |
| [B3.2] 20√N clients concurrently set Object in Map (memUsed) | 0 B | 0 B | 406 kB | 544 B | 536 B | 0 B | skipped |
| [B3.2] 20√N clients concurrently set Object in Map (parseTime) | 96 ms | 91 ms | 96 ms | 91 ms | 82 ms | 103 ms | skipped |
| [B3.3] 20√N clients concurrently set String in Map (time) | 2,755 ms | 51 ms | 98 ms | 122 ms | 105 ms | 3,623 ms | skipped |
| [B3.3] 20√N clients concurrently set String in Map (updateSize) | 8,138,900 bytes | 7,960,260 bytes | 7,826,235 bytes | 7,826,235 bytes | 7,940,240 bytes | 8,075,760 bytes | skipped |
| [B3.3] 20√N clients concurrently set String in Map (encodeTime) | 4 ms | 1 ms | 4 ms | 3 ms | 45 ms | 107 ms | skipped |
| [B3.3] 20√N clients concurrently set String in Map (docSize) | 52,647 bytes | 6,436 bytes | 36,844 bytes | 38,385 bytes | 7,799,809 bytes | 98,042 bytes | skipped |
| [B3.3] 20√N clients concurrently set String in Map (memUsed) | 0 B | 0 B | 15.8 kB | 152 B | 752 B | 0 B | skipped |
| [B3.3] 20√N clients concurrently set String in Map (parseTime) | 99 ms | 79 ms | 97 ms | 77 ms | 62 ms | 114 ms | skipped |
| [B3.4] 20√N clients concurrently insert text in Array (time) | 2,801 ms | 63 ms | 67 ms | 82 ms | 247 ms | 2,781 ms | skipped |
| [B3.4] 20√N clients concurrently insert text in Array (updateSize) | 380,810 bytes | 200,630 bytes | 52,749 bytes | 52,753 bytes | 166,750 bytes | 324,690 bytes | skipped |
| [B3.4] 20√N clients concurrently insert text in Array (encodeTime) | 31 ms | 31 ms | 2 ms | 1 ms | 8 ms | 12 ms | skipped |
| [B3.4] 20√N clients concurrently insert text in Array (docSize) | 97,686 bytes | 51,475 bytes | 26,594 bytes | 26,598 bytes | 31,079 bytes | 96,446 bytes | skipped |
| [B3.4] 20√N clients concurrently insert text in Array (memUsed) | 1.4 MB | 1.4 MB | 677.1 kB | 328 B | 504 B | 47.7 kB | skipped |
| [B3.4] 20√N clients concurrently insert text in Array (parseTime) | 134 ms | 108 ms | 87 ms | 52 ms | 46 ms | 59 ms | skipped |
| [B3.5] 20√N clients concurrently insert text (time) | 2,837 ms | 90 ms | 64 ms | 79 ms | 337 ms | 2,944 ms | 26 ms |
| [B3.5] 20√N clients concurrently insert text (updateSize) | 374,650 bytes | 194,470 bytes | 48,119 bytes | 48,118 bytes | 163,670 bytes | 310,340 bytes | 93,939 bytes |
| [B3.5] 20√N clients concurrently insert text (encodeTime) | 30 ms | 28 ms | 2 ms | 1 ms | 13 ms | 11 ms | 1 ms |
| [B3.5] 20√N clients concurrently insert text (docSize) | 91,526 bytes | 45,315 bytes | 24,295 bytes | 24,317 bytes | 29,772 bytes | 90,788 bytes | 37,933 bytes |
| [B3.5] 20√N clients concurrently insert text (memUsed) | 766.3 kB | 692 kB | 438.7 kB | 560 B | 736 B | 0 B | 0 B |
| [B3.5] 20√N clients concurrently insert text (parseTime) | 124 ms | 92 ms | 76 ms | 78 ms | 67 ms | 119 ms | 64 ms |
| [B4] Apply real-world editing dataset (time) | 40,505 ms | 35,416 ms | 4,787 ms | 32,504 ms | 3,067 ms | 14,712 ms | 1,601 ms |
| [B4] Apply real-world editing dataset (encodeTime) | 2,891 ms | 3,025 ms | 30 ms | 10 ms | 83 ms | 226 ms | 2 ms |
| [B4] Apply real-world editing dataset (docSize) | 6,975,086 bytes | 6,975,044 bytes | 159,929 bytes | 159,927 bytes | 258,228 bytes | 129,212 bytes | 109,005 bytes |
| [B4] Apply real-world editing dataset (parseTime) | 2,338 ms | 2,356 ms | 77 ms | 30 ms | 18 ms | 1,972 ms | 16 ms |
| [B4] Apply real-world editing dataset (memUsed) | 202.1 MB | 206.3 MB | 3.1 MB | 0 B | 0 B | 0 B | 0 B |
| [B4x100] Apply real-world editing dataset 100 times (time) | skipped | skipped | 489,790 ms | skipped | 294,604 ms | skipped | 166,993 ms |
| [B4x100] Apply real-world editing dataset 100 times (encodeTime) | skipped | skipped | 722 ms | skipped | 14,926 ms | skipped | 174 ms |
| [B4x100] Apply real-world editing dataset 100 times (docSize) | skipped | skipped | 15,989,245 bytes | skipped | 25,805,795 bytes | skipped | 10,807,135 bytes |
| [B4x100] Apply real-world editing dataset 100 times (parseTime) | skipped | skipped | 3,153 ms | skipped | 1,226 ms | skipped | 1,452 ms |
| [B4x100] Apply real-world editing dataset 100 times (memUsed) | skipped | skipped | 326.9 MB | skipped | 0 B | skipped | 0 B |