The original address: xuzx. Making. IO / 2020/05/23 /…
What is incremental update
As APP continues to be updated iteratively with business requirements, with more and more functions (complex), the volume of APK package will become larger and larger, resulting in more bandwidth and download waiting time for each client upgrade and update operation. Therefore, it is necessary to seek some better update schemes.
Generally speaking, incremental update refers to the binary differential comparison between a new VERSION OF APK package and an old version of APK package to generate a smaller incremental package and then send it to the client for download and update. Incremental update is relative to full update. The process is shown in Figure 1.
Incremental updates can reduce traffic costs and reduce client upgrade time.
Figure 1 Incremental update process
Comparison of incremental update schemes
There are many incremental update solutions on the web, such as BSDiff, Xdelta, Courgette, etc. Since Courgette does not work with Android APK updates, it will not be compared here. Table 1 below is a comparison of the former two schemes.
| Compare the item | BSDiff | Xdelta3 |
|---|---|---|
| Open source company/author | Colin Percival | Joshua MacDonald |
| Open Source License | BSD | Apache 2.0 (version 3.x) |
| Current Version | 4.3 (Version used in current research) | 3.1.0 (Version used in current research) |
| Open Source project address | The project address | The project address |
| Coding format | – | VCDIFF (RFC 3284) |
| Diff Dynamic library size (.dll) | Around 300 KB | Around 300 KB |
| Patch dynamic library size (.so) | Around 250 KB | Around 350 KB |
| Supported file size | Max. 2 ^ 61-1B | – |
| Differential subcontracting compression algorithm | bzip2 | Huffman and LZMA |
| Compression level adjustment | x | Square root |
| The patch package is compressed twice | x | Square root |
| Window resizing | x | Square root |
| Learning cost assessment | higher | high |
| Integration difficulty | In the | In the |
| documentation | general | less |
| Using the heat | More (wechat, QQ, Douyin) | rare |
Table 1 Framework comparison (Note: [-] : unknown; [√] : indicates support. [×] : not supported)
Contrast test
Environment configuration
- Differential generation environment: Windows 10(64-bit), CPU I5-6500 (3.2ghz), RAM 16GB
- Differential synthesis environment: SamSung SM-P583, Android 7.0, RAM 3GB
- Differential tools: BSDiff(4.3) and Xdelta(3.1.0) generated by the MinGW 32-bit compiler
Note: The differential generation phase is usually operated on the server side, while the differential synthesis phase is usually operated on the mobile side.
Test Group 1 (APK around 15M)
The Flipboard redboard is selected as the test object, and the versions are 4.3.12 (14.5MB) and 4.3.13 (14.6MB) respectively. The test comparison data is shown as follows.
FIG. 2 Comparison of APK time around 15M
| BSDiff | Xdelta3 | |
|---|---|---|
| Differential generation time | 19235ms | 1867ms |
| CPU usage is generated differentially | 29% | 10% |
| Differential generation memory usage | From 88 to 132 MB | From 203 to 209 MB |
| Differential patch size | 5.64 MB | 5.7 MB |
| Differential synthesis time | 3941ms | 271ms |
| Differential synthesis CPU usage | 12% | 1% ~ 8.8% |
| Differential synthesis memory usage | 32.8 MB | 28.4 MB |
Table 2 EXPERIMENTAL results of APK at around 15M
Test Group 2 (around 100M APK)
Wechat is selected as the test object, with versions 6.7.3 (75.5MB) and 7.0.3 (104MB) respectively. The test comparison data is shown below.
FIG. 3 Comparison of APK time around 100M
| BSDiff | Xdelta3 | |
|---|---|---|
| Differential generation time | 375472ms | 36517ms |
| CPU usage is generated differentially | 29% | 29% |
| Differential generation memory usage | From 480 to 681 MB | From 201 to 212 MB |
| Differential patch size | 76.5 MB | 76.4 MB |
| Differential synthesis time | 48539ms | 2915ms |
| Differential synthesis CPU usage | 12% | 1% ~ 12% |
| Differential synthesis memory usage | 81.3 ~ 186.4 MB | 94.3 MB |
Table 3 Results of APK experimental data at around 100M
Test Group 3 (500M APK or so)
Here, the king of Chaos is selected as the test object, with versions 1.6.8.25 (532MB) and 1.6.12.26 (560MB) respectively. The test comparison data is shown below.
Figure 4 comparison of APK time around 500M
| BSDiff | Xdelta3 | |
|---|---|---|
| Differential generation time | x | 68538ms |
| CPU usage is generated differentially | x | 30% |
| Differential generation memory usage | x | From 203 to 212 MB |
| Differential patch size | x | 144MB |
| Differential synthesis time | x | 14443ms |
| Differential synthesis CPU usage | x | 1% ~ 12% |
| Differential synthesis memory usage | x | 82.7 ~ 87.5 MB |
Table 4 Experimental results of APK around 500M
Test Group 4 (around 1.8GB APK)
Here, the game package PubG is selected as the test object, versions of which are 0.13.5(1.79GB) and 0.14.5 (1.86GB) respectively. The test comparison data is shown below.
FIG. 5 APK time comparison around 1.8g
| BSDiff | Xdelta3 | |
|---|---|---|
| Differential generation time | x | 514286ms |
| CPU usage is generated differentially | x | 31% |
| Differential generation memory usage | x | From 203 to 212 MB |
| Differential patch size | x | 0.99 GB |
| Differential synthesis time | x | 117527ms |
| Differential synthesis CPU usage | x | 1% ~ 12% |
| Differential synthesis memory usage | x | 83.7 ~ 94.9 MB |
Table 5 Experimental results of APK around 1.8G
Note: The data are from the average of 5 experiments
conclusion
From the previous several groups of test experiments combined with relevant source code, we can draw the following conclusions:
1) In terms of difference time, Xdelta3 is better than BSDiff in difference generation and difference synthesis, and the difference between the two is about 10 times. The difference synthesis is better than the difference generation.
2) From the aspect of memory consumption, with the increase of APK package size, BSDiff memory will double, but Xdelta3 is stable within a certain range;
3) When the APK package reaches a certain size, BSDiff(32-bit compiler) will have differential failure. It can be analyzed from the source code of C that a large number of dynamic memory space application is caused by the difference, which is also the main reason for the large memory occupied, but Xdelta can still difference;
4) In addition, BSDiff needs to read the old and new files into memory to form a string dictionary, sort (qsufsort), search (search) and so on, and generate the diffString and extra String blocks. Finally, the incremental package (patch) was generated by bzip2 compression. Meanwhile, it was found that the difference comparison operations such as sorting and searching took half of the time with the bzip2 compression generation operations. Xdelta3 uses the correlation window algorithm to block old and new files into memory, and generates incremental packages by comparing the differences.
5) It should be noted that the incremental packets generated by the two reinforcement packets cannot be combined with the unreinforcement packets;
6) Xdelta 3.1.1 is slightly optimized in terms of time consumption and memory compared with 3.1.0;
7) In addition, it is found that the Xdelta executable generated by different compilers has a related influence on the differential generation time. For example, the mingW-W64 compiler and CL compiler generate the execution file, and the time of the differential generation operation is about half different (the former is better).
Tips: This article is the blogger’s original article, if found in the article, welcome criticism and correction, thank you for your support!