Senang menyambut Anda. Hampir satu tahun telah berlalu sejak artikel terakhir dipublikasikan dan kami siap untuk memberi tahu Anda apa yang terjadi pada algoritma itu sendiri dan bagaimana delta coding terlibat.
Entri
Setelah publikasi artikel tentang peningkatan algoritma Broo, kami dihadapkan dengan hambatan dalam meningkatkan tingkat kompresi dan kinerja, yaitu, tidak mungkin untuk meningkatkan tingkat kompresi tanpa mempengaruhi kecepatan dekompresi dan sebaliknya. Saya akan segera melakukan reservasi, perbaikan dilakukan tanpa mengurangi karakteristik algoritma lainnya, tetapi perubahan ini tidak signifikan, kami akan menulis tentang perubahan ini nanti. Jadi, setelah itu, kami memikirkan di mana kami bisa menerapkan keahlian dan pengetahuan kami yang terakumulasi dalam arah yang sama. Dan pilihan jatuh pada pengkodean delta .
Apa itu delta coding?
Delta encoding ( Eng. Delta encoding) - cara mewakili data dalam bentuk perbedaan ( delta ) antara data serial dan bukan data itu sendiri.
Dalam praktiknya, jika algoritma kompresi memungkinkan Anda mengurangi ukuran file dan menyimpan atau meneruskannya tanpa ketergantungan pada file lain, maka algoritma pengkodean delta memungkinkan Anda untuk membangun tambalan (perbedaan) dengan ukuran lebih kecil berdasarkan pada dua file (kumpulan data) dan menerapkan tambalan untuk file tersebut ( kumpulan data) 1 - dapatkan file (kumpulan data) 2 .
Aplikasi yang paling umum untuk pengkodean delta adalah memperbarui aplikasi di ponsel dan PC Anda. Alih-alih mengunduh aplikasi sepenuhnya dan kemudian mengganti file, tambalan yang jauh lebih kecil dibuat (tergantung pada jumlah perubahan), yang memungkinkan Anda mengunduh pembaruan lebih cepat, dan kecepatan penerapan tambalan secara langsung memengaruhi kecepatan pembaruan aplikasi itu sendiri.
Jika Anda tahu di mana lagi pengkodean delta digunakan, maka tulis di komentar.
Tentang perubahan pada algoritma Broo
Seperti yang kami katakan, ada beberapa di antaranya:
- Dukungan tambahan untuk file berukuran 2 ^ 64 untuk x64 dan 2 ^ 32 untuk x32.
- Rasio kompresi yang ditingkatkan.
Perubahan ini masih dalam tahap eksperimen dan debugging. Masalah utama - setelah menambahkan dukungan untuk file besar, kecepatan dekompresi turun 20%, yang tidak dapat diterima bagi kami. Jadi kami masih mencari solusi.
Di bawah ini kami hanya menyediakan satu tabel perbandingan dari versi algoritma yang lama, yang eksperimental, dan beberapa level zstd. File xml dari artikel sebelumnya .
Prosesor: Intel i7-7700HQ
Memori: DDR4-2400
| Nama Algoritma | Kecepatan pengepakan | Kecepatan dekompresi | Ukuran File Terkompresi, Bytes | % asli |
|---|
| memcpy | 17460 MB / s | 17194 MB / s | 5345280 | 100.00 |
| zstd 1.3.1 -6 | 141 MB / s | 1311 MB / s | 585810 | 10.96 |
| broo 1.2 | 11 MB / s | 1905 MB / s | 606838 | 11.35 |
| zstd 1.3.1 -5 | 196 MB / s | 1207 MB / s | 619510 | 11.59 |
| zstd 1.3.1 -4 | 357 MB / s | 1214 MB / s | 637587 | 11,93 |
| zstd 1.3.1 -3 | 366 MB / s | 1220 MB / s | 639073 | 11.96 |
| broo 1.1 | 14 MB / s | 2005 MB / s | 643084 | 12,03 |
| zstd 1.3.1 -2 | 394 MB / s | 1108 MB / s | 690508 | 12,92 |
| zstd 1.3.1 -1 | 479 MB / s | 1213 MB / s | 703093 | 13.15 |
Seperti banyak algoritma, kecepatan tergantung pada prosesor, seperti yang dapat kita lihat dalam tabel, kecepatan dekompresi lebih dari 1,5 kali lebih cepat daripada zstd tingkat pertama, pada prosesor Intel i7-7700HQ. Sementara pada Intel i3-550 lama, kecepatan dekompresi kira-kira sama dengan kecepatan dekompresi zstd, Anda dapat melihat tabel perbandingan di sini .
Ini menunjukkan bahwa Anda dapat melakukan integrasi yang lebih ketat dengan masing-masing prosesor. Tergantung pada spesifikasi tugas.
Delta Coding dan Broo
Seperti yang Anda duga, kami mengembangkan algoritma pengkodean delta kami sendiri dan memberinya nama DBroo (Delta Broo).
Karakteristik dan fitur utama:
- Dukungan untuk ukuran file 2 ^ 64 untuk x64 dan 2 ^ 32 untuk x32.
- Bekerja dengan data biner.
- Modifikasi sebagian dari file referensi yang menerapkan patch diizinkan.
Ada solusi siap pakai seperti diff, bsdiff, xdelta dan lainnya. Tujuannya adalah untuk menemukan yang terbaik (sekaligus terjangkau) dalam arah ini dan bersaing dengannya. Xdelta3 ternyata menjadi pesaing utama dengan cara eksperimental murni. Ini memberikan kompresi yang baik dan kecepatan aplikasi patch yang cukup cepat. Xdelta3 juga digunakan untuk pembaruan CyanogenMod (sekarang LineageOS ).
Sekarang mari kita lihat tabel perbandingan DBroo dan Xdelta3. Sebagai file referensi, "xml" digunakan, dan sebagai file baru, sama tetapi dimodifikasi secara acak.
| Nama Algoritma | Kecepatan pembuatan tambalan | Kecepatan aplikasi tambalan | Ukuran tambalan, byte | % dari aslinya |
|---|
| memcpy | 18052 MB / s | 18665 MB / s | 5326823 | 100.00 |
| Xdelta3 -9 + lzma | 5,40 MB / s | 306 MB / s | 106542 | 2,00 |
| Xdelta3 -6 + lzma | 20 MB / s | 310 MB / s | 121916 | 2.28 |
| DBroo 1.0 | 7,40 MB / s | 1600.00 MB / s | 123052 | 2.31 |
| Xdelta3 -9 | 7,00 MB / s | 688,24 MB / s | 179732 | 3.37 |
| Xdelta3 -6 | 36,71 MB / s | 694.09 MB / s | 201681 | 3.78 |
| Xdelta3 -3 | 59,22 MB / s | 637,43 MB / s | 237218 | 4.45 |
| Xdelta3 -2 | 72,73 MB / s | 582.75 MB / s | 279223 | 5.24 |
| Xdelta3 -1 | 81,43 MB / s | 540.53 MB / s | 478824 | 8.9 |
PS
Pengembangan hanya diberikan kepada produk-produk yang memiliki permintaan di pasar. Karena itu, kami menyambut komentar Anda. Kami juga membuat saluran telegram .
Terima kasih