Ĉi tiu artikolo jam estas la dua en la temo de altrapida datumkunpremo. La unua artikolo priskribis kompresoron funkciantan kun rapideco de 10 GB/sec. po procesorkerno (minimuma kunpremo, RTT-Min).
Ĉi tiu kompresoro jam estis efektivigita en la ekipaĵo de krimmedicinaj duplikatoj por altrapida kunpremado de stokaj amaskomunikiloj kaj plifortigi la forton de kriptografio; ĝi ankaŭ povas esti uzata por kunpremi bildojn de virtualaj maŝinoj kaj RAM interŝanĝi dosierojn dum konservado de ili sur altrapida. SSD-diskoj.
La unua artikolo ankaŭ anoncis la disvolviĝon de kunprema algoritmo por kunpremado de rezervaj kopioj de diskoj de diskoj kaj SSD (meza kunpremo, RTT-Mid) kun signife plibonigitaj parametroj de datumpremo. Nuntempe ĉi tiu kompresoro estas tute preta kaj ĉi tiu artikolo temas pri ĝi.
Kompresoro kiu efektivigas la RTT-Mid-algoritmon disponigas kunpremadproporcion kompareblan al normaj arkivistoj kiel ekzemple WinRar, 7-Zip, funkcianta en altrapida reĝimo. Samtempe, ĝia operacia rapideco estas almenaŭ grandordo pli alta.
La rapideco de pakado/malpakado de datumoj estas kritika parametro, kiu determinas la amplekson de apliko de kunpremaj teknologioj. Estas neverŝajne, ke iu pensus kunpremi terabajton da datumoj je rapideco de 10-15 Megabajtoj je sekundo (tio estas ĝuste la rapideco de arkivistoj en norma kunprema reĝimo), ĉar ĝi bezonus preskaŭ dudek horojn kun plena procesoro-ŝarĝo. .
Aliflanke, la sama terabajto povas esti kopiita je rapidoj de la ordo de 2-3 Gigabajtoj je sekundo en proksimume dek minutoj.
Tial, kunpremado de grand-volumenaj informoj estas grava se ĝi estas farita kun rapideco ne pli malalta ol la rapideco de reala enigo/produktaĵo. Por modernaj sistemoj tio estas almenaŭ 100 Megabajtoj je sekundo.
Modernaj kompresoroj povas produkti tiajn rapidecojn nur en "rapida" reĝimo. Ĝuste en ĉi tiu nuna reĝimo ni komparos la RTT-Mid-algoritmon kun tradiciaj kompresoroj.
Kompara testado de nova kunpremadalgoritmo
La RTT-Mid-kompresoro funkciis kiel parto de la testprogramo. En vera "funkcianta" aplikaĵo ĝi funkcias multe pli rapide, ĝi uzas multfadenadon saĝe kaj uzas "normalan" kompililon, ne C#.
Ĉar la kompresoroj uzitaj en la kompara testo estas konstruitaj sur malsamaj principoj kaj malsamaj specoj de datumoj kunpremas malsame, por la objektiveco de la testo, la metodo de mezurado de la "averaĝa temperaturo en la hospitalo" estis uzata...
Sektora post sektora rubodosiero de logika disko kun la Windows 10 operaciumo estis kreita; ĉi tio estas la plej natura miksaĵo de diversaj datumstrukturoj efektive disponeblaj en ĉiu komputilo. Kunpremado de ĉi tiu dosiero permesos al vi kompari la rapidecon kaj gradon de kunpremo de la nova algoritmo kun la plej altnivelaj kompresoroj uzataj en modernaj arkivistoj.
Jen la dumpdosiero:
La rubdosiero estis kunpremita per PTT-Mid, 7-zip, kaj WinRar kompresoroj. La WinRar kaj 7-zipa kompresoro estis agordita al maksimuma rapideco.
Kompresoro funkcianta 7-zip:
Ĝi ŝarĝas la procesoron je 100%, dum la averaĝa rapido de legado de la originala rubejo estas ĉirkaŭ 60 MegaBytes/sek.
Kompresoro funkcianta winrar:
La situacio estas simila, la procesoro-ŝarĝo estas preskaŭ 100%, la averaĝa forĵeta legado-rapido estas ĉirkaŭ 125 Megabajtoj/sek.
Kiel en la antaŭa kazo, la rapideco de la arkivisto estas limigita de la kapabloj de la procesoro.
La kompresora testa programo nun funkcias RTT-Meza:
La ekrankopio montras, ke la procesoro estas ŝarĝita je 50% kaj estas neaktiva la reston de la tempo, ĉar estas nenie por alŝuti la kunpremitajn datumojn. La disko de alŝuto de datumoj (Disko 0) estas preskaŭ plene ŝargita. La rapideco de legado de datumoj (Disko 1) multe varias, sed averaĝe pli ol 200 MegaBytes/sek.
La rapideco de la kompresoro estas limigita en ĉi tiu kazo per la kapablo skribi kunpremitajn datumojn al Disko 0.
Nun la kunprema proporcio de la rezultaj arkivoj:
Videblas, ke la RTT-Mid-kompresoro faris la plej bonan laboron de kunpremado; la arkivo kiun ĝi kreis estis 1,3 GigaBytes pli malgranda ol la WinRar-arkivo kaj 2,1 GigaBytes pli malgranda ol la 7z-arkivo.
Tempo pasigita por krei la arkivon:
- 7-zip - 26 minutoj 10 sekundoj;
- WinRar - 17 minutoj 40 sekundoj;
- RTT-Meza - 7 minutoj 30 sekundoj.
Tiel, eĉ testa, ne-optimumigita programo, uzante la RTT-Mid-algoritmon, povis krei arkivon pli ol dufoje kaj duono pli rapide, dum la arkivo montriĝis signife pli malgranda ol tiu de siaj konkurantoj...
Tiuj, kiuj ne kredas la ekrankopiojn, povas mem kontroli ilian aŭtentikecon. La testprogramo haveblas ĉe , elŝutu kaj kontrolu.
Sed nur ĉe procesoroj kun AVX-2-subteno, sen subteno por ĉi tiuj instrukcioj la kompresoro ne funkcias, kaj ne testas la algoritmon sur pli malnovaj AMD-procesoroj, ili estas malrapidaj rilate ekzekuti AVX-instrukciojn...
Kunprema metodo uzata
La algoritmo uzas metodon por indeksado de ripetaj tekstofragmentoj en bajta granulareco. Ĉi tiu kunprema metodo estas konata delonge, sed ne estis uzata ĉar la kongrua operacio estis tre multekosta laŭ la necesaj rimedoj kaj postulis multe pli da tempo ol konstrui vortaron. Do la RTT-Mid-algoritmo estas klasika ekzemplo de moviĝado "reen al la estonteco"...
La PTT-kompresoro uzas unikan altrapidan kongruan serĉan skanilon, kiu ebligas al ni akceli la kunpreman procezon. Memfarita skanilo, jen "mia ĉarmo...", "ĝi estas sufiĉe multekosta, ĉar ĝi estas tute manfarita" (skribita en asemblero).
La kongrua serĉskanilo estas farita laŭ dunivela probabla skemo: unue, la ĉeesto de "signo" de matĉo estas skanita, kaj nur post kiam la "signo" estas identigita en ĉi tiu loko, la procedo por detekti realan matĉon. estas komencita.
La kongrua fenestro havas neantaŭvideblan grandecon, depende de la grado da entropio en la prilaborita datumbloko. Por tute hazardaj (nekunpremeblaj) datumoj ĝi havas grandecon de megabajtoj, por datumoj kun ripetoj ĝi estas ĉiam pli granda ol megabajto.
Sed multaj modernaj datumformatoj estas nekunpremeblaj kaj funkciigado de rimedo-intensa skanilo tra ili estas senutila kaj malŝparema, do la skanilo uzas du funkciajn reĝimojn. Unue, sekcioj de la fontoteksto kun eblaj ripetoj estas serĉataj; ĉi tiu operacio ankaŭ estas efektivigita per probabla metodo kaj estas farita tre rapide (kun rapideco de 4-6 GigaBytes/sek). La areoj kun eblaj matĉoj tiam estas prilaboritaj per la ĉefa skanilo.
Indeksa kunpremo ne estas tre efika, vi devas anstataŭigi duplikatajn fragmentojn per indeksoj, kaj la indeksa tabelo signife reduktas la kunpremadon.
Por pliigi la kunpremoproporcion, ne nur kompletaj kongruoj de bajtaj ĉenoj estas indeksitaj, sed ankaŭ partaj, kiam la ĉeno enhavas kongruajn kaj nekongruajn bajtojn. Por fari tion, la indeksa formato inkluzivas kongruan maskon, kiu indikas la kongruajn bajtojn de du blokoj. Por eĉ pli granda kunpremado, indeksado estas uzata por supermeti plurajn parte kongruajn blokojn al la nuna bloko.
Ĉio ĉi ebligis akiri en la PTT-Mid-kompresoro kunpremoproporcion kompareblan al kompresoroj faritaj per la vortara metodo, sed laborantaj multe pli rapide.
Rapido de la nova kunprema algoritmo
Se la kompresoro funkcias kun ekskluziva uzo de kaŝmemoro (4 Megabajtoj estas bezonataj per fadeno), tiam la operacia rapideco varias de 700-2000 Megabajtoj/sek. per procesorkerno, depende de la speco de datenoj estanta kunpremita kaj dependas malmulte de la funkciiga frekvenco de la procesoro.
Kun multfadena efektivigo de la kompresoro, efika skaleblo estas determinita de la grandeco de la trianivela kaŝmemoro. Ekzemple, havante 9 Megabajtojn da kaŝmemoro "surŝipe", ne utilas lanĉi pli ol du kunpremajn fadenojn; la rapideco ne pliiĝos pro tio. Sed kun kaŝmemoro de 20 Megabajtoj, vi jam povas ruli kvin kunpremajn fadenojn.
Ankaŭ, la latenco de la RAM fariĝas grava parametro, kiu determinas la rapidecon de la kompresoro. La algoritmo uzas hazardan aliron al la OP, iuj el kiuj ne eniras la kaŝmemoron (ĉirkaŭ 10%) kaj ĝi devas malakcepti, atendante datumojn de la OP, kio reduktas la rapidecon de operacio.
Signife influas la rapidecon de la kompresoro kaj la funkciadon de la datuma enigo/eliga sistemo. Petoj al la OP de I/O blokpetoj por datumoj de la CPU, kiu ankaŭ reduktas la kunpremadrapidecon. Ĉi tiu problemo estas signifa por tekokomputiloj kaj labortabloj; por serviloj ĝi estas malpli signifa pro pli progresinta sistema busa alirkontrolunuo kaj plurkanala RAM.
Ĉie en la teksto en la artikolo ni parolas pri kunpremado; malkunpremo restas ekster la amplekso de ĉi tiu artikolo ĉar "ĉio estas kovrita per ĉokolado". Malkunpremo estas multe pli rapida kaj estas limigita per I/O-rapideco. Unu fizika kerno en unu fadeno facile disponigas malpakajn rapidojn de 3-4 GB/sec.
Ĉi tio estas pro la foresto de kongrua serĉa operacio dum la malkunprema procezo, kiu "manĝas" la ĉefajn rimedojn de la procesoro kaj kaŝmemoro dum kunpremado.
Fidindeco de kunpremita datumstokado
Kiel la nomo de la tuta klaso de programaro, kiu uzas datumkunpremadon (arkivilojn), sugestas, ili estas desegnitaj por longdaŭra konservado de informoj, ne dum jaroj, sed dum jarcentoj kaj jarmiloj...
Dum stokado, stokado-komunikiloj perdas iujn datumojn, jen ekzemplo:
Ĉi tiu "analoga" informportilo estas miljara, kelkaj fragmentoj estas perditaj, sed ĝenerale la informoj estas "legeblaj"...
Neniu el la respondecaj fabrikistoj de modernaj ciferecaj datumstokaj sistemoj kaj ciferecaj amaskomunikiloj por ili provizas garantiojn pri kompleta datuma sekureco dum pli ol 75 jaroj.
Kaj ĉi tio estas problemo, sed prokrastita problemo, niaj posteuloj solvos ĝin...
Ciferecaj datumsistemoj povas perdi datumojn ne nur post 75 jaroj, eraroj en datumoj povas aperi iam ajn, eĉ dum sia registrado, ili provas minimumigi ĉi tiujn distordojn uzante redundon kaj korektante ilin per eraraj korektaj sistemoj. Redundaj kaj korektaj sistemoj ne ĉiam povas restarigi perditajn informojn, kaj se ili faras, ne estas garantio, ke la restarigo operacio estis ĝuste kompletigita.
Kaj ĉi tio ankaŭ estas granda problemo, sed ne prokrastita, sed aktuala.
Modernaj kompresoroj uzataj por arkivado de ciferecaj datumoj estas konstruitaj sur diversaj modifoj de la vortara metodo, kaj por tiaj arkivoj la perdo de informo estos mortiga okazaĵo; ekzistas eĉ establita termino por tia situacio - "rompita" arkivo. ...
La malalta fidindeco de stokado de informoj en arkivoj kun vortarkunpremo estas rilata al la strukturo de la kunpremitaj datenoj. La informoj en tia arkivo ne enhavas la fonttekston, la nombroj da enskriboj en la vortaro estas konservitaj tie, kaj la vortaro mem estas dinamike modifita per la nuna kunpremita teksto. Se arkivfragmento estas perdita aŭ koruptita, ĉiuj postaj arkivenskriboj ne povas esti identigitaj nek per la enhavo nek per la longo de la enskribo en la vortaro, ĉar estas ne klare al kio la vortara enirnumero respondas.
Estas neeble restarigi informojn de tia "rompita" arkivo.
La RTT-algoritmo baziĝas sur pli fidinda metodo de stokado de kunpremitaj datumoj. Ĝi uzas la indeksan metodon de kontado por ripetado de fragmentoj. Ĉi tiu aliro al kunpremado ebligas al vi minimumigi la konsekvencojn de distordo de informoj sur la stokado, kaj en multaj kazoj aŭtomate korekti distordojn, kiuj estiĝis dum informa stokado.
Ĉi tio estas pro la fakto, ke la arkiva dosiero en la kazo de indeksa kunpremado enhavas du kampojn:
- fonta tekstokampo kun ripetaj sekcioj forigitaj de ĝi;
- indeksa kampo.
La indeksa kampo, kiu estas kritika por informreakiro, ne estas granda en grandeco kaj povas esti duobligita por fidinda datumstokado. Tial, eĉ se fragmento de la fontoteksto aŭ indeksa tabelo estas perdita, ĉiuj aliaj informoj estos restarigitaj sen problemoj, kiel en la bildo kun "analoga" stokado.
Malavantaĝoj de la algoritmo
Ne estas avantaĝoj sen malavantaĝoj. La indeksa kunprema metodo ne kunpremas mallongajn ripetantajn sekvencojn. Ĉi tio estas pro la limigoj de la indeksa metodo. Indeksoj estas almenaŭ 3 bajtoj en grandeco kaj povas esti ĝis 12 bajtoj en grandeco. Se oni renkontas ripeton kun pli malgranda grandeco ol la indekso priskribanta ĝin, tiam ĝi ne estas konsiderata, kiom ajn ofte tiaj ripetoj estas detektitaj en la kunpremita dosiero.
La tradicia vortara kunpremadmetodo efike kunpremas multoblajn ripetojn de mallonga longo kaj tial atingas pli altan kunpremadproporcion ol indekspremado. Vere, tio estas atingita pro la alta ŝarĝo sur la centra procesoro; por ke la vortara metodo komencu kunpremi datumojn pli efike ol la indeksa metodo, ĝi devas redukti la datumtraktadrapidecon al 10-20 megabajtoj je sekundo sur reala. komputikaj instalaĵoj kun plena CPU-ŝarĝo.
Tiaj malaltaj rapidecoj estas neakcepteblaj por modernaj datumstokaj sistemoj kaj estas de pli "akademia" intereso ol praktika.
La grado de informa kunpremo estos signife pliigita en la sekva modifo de la RTT-algoritmo (RTT-Max), kiu jam estas evoluinta.
Do, kiel ĉiam, daŭrigota...
fonto: www.habr.com