Nakala hii tayari ni ya pili katika mada ya ukandamizaji wa data ya kasi. Kifungu cha kwanza kilielezea compressor inayofanya kazi kwa kasi ya 10 GB / sec. kwa msingi wa processor (compression ya chini, RTT-Min).
Compressor hii tayari imetekelezwa katika vifaa vya nakala za uchunguzi wa kisayansi kwa ukandamizaji wa kasi wa utupaji wa vyombo vya habari vya uhifadhi na kuongeza nguvu ya kriptografia; inaweza pia kutumika kukandamiza picha za mashine za kawaida na faili za kubadilishana RAM wakati wa kuzihifadhi kwa kasi ya juu. Viendeshi vya SSD.
Nakala ya kwanza pia ilitangaza ukuzaji wa algorithm ya ukandamizaji wa kubana nakala za chelezo za anatoa za diski za HDD na SSD (ukandamizaji wa kati, RTT-Mid) na vigezo vya ukandamizaji wa data vilivyoboreshwa sana. Kwa sasa, compressor hii iko tayari kabisa na makala hii ni kuhusu hilo.
Compressor inayotumia algoriti ya RTT-Mid hutoa uwiano wa mbano unaolinganishwa na kumbukumbu za kawaida kama vile WinRar, 7-Zip, zinazofanya kazi katika hali ya kasi ya juu. Wakati huo huo, kasi yake ya uendeshaji ni angalau amri ya ukubwa wa juu.
Kasi ya kufunga/kufungua data ni kigezo muhimu kinachoamua upeo wa matumizi ya teknolojia za ukandamizaji. Haiwezekani kwamba mtu yeyote angefikiria kushinikiza terabyte ya data kwa kasi ya MegaBytes 10-15 kwa sekunde (hii ndio kasi ya kumbukumbu katika hali ya kawaida ya ukandamizaji), kwa sababu inaweza kuchukua karibu masaa ishirini na mzigo kamili wa processor. .
Kwa upande mwingine, terabyte sawa inaweza kunakiliwa kwa kasi ya utaratibu wa 2-3Gigabytes kwa pili katika dakika kumi.
Kwa hiyo, ukandamizaji wa habari ya kiasi kikubwa ni muhimu ikiwa unafanywa kwa kasi isiyo ya chini kuliko kasi ya pembejeo / pato halisi. Kwa mifumo ya kisasa hii ni angalau Megabytes 100 kwa sekunde.
Compressors za kisasa zinaweza kutoa kasi kama hizo tu katika hali ya "haraka". Ni katika hali hii ya sasa kwamba tutalinganisha algorithm ya RTT-Mid na compressors za jadi.
Jaribio la kulinganisha la algoriti mpya ya mbano
Compressor ya RTT-Mid ilifanya kazi kama sehemu ya programu ya majaribio. Katika programu halisi ya "kazi" inafanya kazi kwa kasi zaidi, hutumia multithreading kwa busara na hutumia compiler "kawaida", si C #.
Kwa kuwa compressors zinazotumiwa katika mtihani wa kulinganisha zimejengwa kwa kanuni tofauti na aina tofauti za data compress tofauti, kwa lengo la mtihani, njia ya kupima "joto la wastani katika hospitali" ilitumiwa ...
Faili ya utupaji ya sekta kwa sekta ya diski yenye mantiki yenye mfumo wa uendeshaji wa Windows 10 iliundwa; huu ni mchanganyiko wa asili zaidi wa miundo mbalimbali ya data inayopatikana kwenye kila kompyuta. Kufinyiza faili hii kutakuruhusu kulinganisha kasi na kiwango cha ukandamizaji wa algorithm mpya na vibonyezo vya hali ya juu zaidi vinavyotumiwa katika hifadhi za kisasa.
Hapa kuna faili ya kutupa:
Faili ya kutupa ilibanwa kwa kutumia compressor za PTT-Mid, 7-zip na WinRar. WinRar na compressor 7-zip zimewekwa kwa kasi ya juu.
Compressor inayoendesha 7-zip:
Inapakia processor kwa 100%, wakati kasi ya wastani ya kusoma dampo asili ni karibu MegaBytes 60 kwa sekunde.
Compressor inayoendesha Winrar:
Hali ni sawa, mzigo wa processor ni karibu 100%, kasi ya wastani ya kusoma dampo ni kuhusu Megabytes 125 / sec.
Kama katika kesi ya awali, kasi ya archiver ni mdogo na uwezo wa processor.
Programu ya majaribio ya kujazia sasa inaendeshwa RTT-Katikati:
Picha ya skrini inaonyesha kuwa kichakataji kimepakiwa kwa 50% na hakifanyi kitu wakati wote, kwa sababu hakuna mahali pa kupakia data iliyobanwa. Diski ya upakiaji wa data (Disk 0) inakaribia kupakiwa kikamilifu. Kasi ya kusoma data (Disk 1) inatofautiana sana, lakini kwa wastani zaidi ya MegaBytes 200 kwa sekunde.
Kasi ya compressor ni mdogo katika kesi hii na uwezo wa kuandika data iliyoshinikwa kwa Disk 0.
Sasa uwiano wa compression wa kumbukumbu zinazosababisha:
Inaweza kuonekana kuwa kikandamizaji cha RTT-Mid kilifanya kazi bora zaidi ya ukandamizaji; kumbukumbu iliyounda ilikuwa ndogo ya GigaBytes 1,3 kuliko kumbukumbu ya WinRar na GigaBytes 2,1 ndogo kuliko kumbukumbu ya 7z.
Muda uliotumika kuunda kumbukumbu:
- 7-zip - dakika 26 sekunde 10;
- WinRar - dakika 17 sekunde 40;
- RTT-Mid - dakika 7 sekunde 30.
Kwa hivyo, hata jaribio, programu isiyoboreshwa, kwa kutumia algorithm ya RTT-Mid, iliweza kuunda kumbukumbu zaidi ya mara mbili na nusu haraka, wakati kumbukumbu iligeuka kuwa ndogo sana kuliko ile ya washindani wake ...
Wale ambao hawaamini viwambo wanaweza kuangalia uhalisi wao wenyewe. Mpango wa majaribio unapatikana kwa , pakua na uangalie.
Lakini tu kwa wasindikaji walio na usaidizi wa AVX-2, bila msaada wa maagizo haya compressor haifanyi kazi, na usijaribu algorithm kwenye wasindikaji wa zamani wa AMD, ni polepole katika suala la utekelezaji wa maagizo ya AVX ...
Njia ya kukandamiza iliyotumiwa
Kanuni hutumia mbinu ya kuorodhesha vipande vya maandishi vinavyorudiwa katika faharasa katika uzito wa baiti. Njia hii ya ukandamizaji imejulikana kwa muda mrefu, lakini haikutumiwa kwa sababu operesheni ya kulinganisha ilikuwa ghali sana kwa suala la rasilimali muhimu na ilihitaji muda zaidi kuliko kujenga kamusi. Kwa hivyo algorithm ya RTT-Mid ni mfano mzuri wa kusonga "kurudi kwa siku zijazo" ...
Compressor ya PTT hutumia kichanganuzi cha kipekee cha utafutaji wa mechi ya kasi, ambayo hutuwezesha kuharakisha mchakato wa kubana. Scanner ya kujitegemea, hii ni "charm yangu ...", "ni ghali kabisa, kwa sababu imefanywa kabisa kwa mikono" (imeandikwa katika mkusanyiko).
Scanner ya utafutaji wa mechi inafanywa kulingana na mpango wa uwezekano wa ngazi mbili: kwanza, uwepo wa "ishara" ya mechi ni scanned, na tu baada ya "ishara" kutambuliwa mahali hapa, utaratibu wa kuchunguza mechi halisi. imeanza.
Dirisha la utafutaji la mechi lina ukubwa usiotabirika, kulingana na kiwango cha entropy katika kizuizi cha data kilichochakatwa. Kwa data ya nasibu kabisa (isiyoshinikizwa) ina ukubwa wa megabytes, kwa data yenye marudio daima ni kubwa kuliko megabyte.
Lakini fomati nyingi za kisasa za data hazibadiliki na kuendesha kichanganuzi kinachotumia rasilimali nyingi kwa njia hiyo haina maana na ni ubadhirifu, kwa hivyo skana hutumia njia mbili za uendeshaji. Kwanza, sehemu za matini chanzi zenye marudio yanayowezekana hutafutwa; operesheni hii pia inafanywa kwa kutumia mbinu ya uwezekano na inafanywa haraka sana (kwa kasi ya 4-6 GigaBytes/sek). Maeneo yaliyo na mechi zinazowezekana huchakatwa na skana kuu.
Ukandamizaji wa index sio mzuri sana, lazima ubadilishe vipande vilivyorudiwa na fahirisi, na safu ya faharisi inapunguza kwa kiasi kikubwa uwiano wa ukandamizaji.
Ili kuongeza uwiano wa ukandamizaji, sio tu mechi kamili za kamba za byte zimeorodheshwa, lakini pia zile za sehemu, wakati kamba ina byte zinazofanana na zisizofaa. Ili kufanya hivyo, muundo wa index ni pamoja na uwanja wa mask ya mechi ambayo inaonyesha byte zinazofanana za vitalu viwili. Kwa mgandamizo mkubwa zaidi, kuorodhesha hutumiwa kuweka vizuizi kadhaa vinavyolingana kwa sehemu kwenye kizuizi cha sasa.
Yote hii ilifanya iwezekane kupata katika compressor ya PTT-Mid uwiano wa compression kulinganishwa na compressors iliyofanywa kwa njia ya kamusi, lakini inafanya kazi kwa kasi zaidi.
Kasi ya algorithm mpya ya ukandamizaji
Ikiwa compressor inafanya kazi kwa matumizi ya kipekee ya kumbukumbu ya kache (Megabytes 4 zinahitajika kwa kila thread), basi kasi ya uendeshaji ni kati ya Megabytes 700-2000 kwa sekunde. kwa msingi wa processor, kulingana na aina ya data inayobanwa na inategemea kidogo juu ya mzunguko wa uendeshaji wa processor.
Kwa utekelezaji wa nyuzi nyingi za compressor, scalability yenye ufanisi imedhamiriwa na ukubwa wa cache ya ngazi ya tatu. Kwa mfano, kuwa na MegaBytes 9 za kumbukumbu ya kache "kwenye bodi", hakuna maana katika kuzindua nyuzi zaidi ya mbili za kushinikiza; kasi haitaongezeka kutoka kwa hili. Lakini ukiwa na akiba ya Megabytes 20, unaweza tayari kuendesha nyuzi tano za ukandamizaji.
Pia, latency ya RAM inakuwa parameter muhimu ambayo huamua kasi ya compressor. Algorithm hutumia ufikiaji wa nasibu kwa OP, ambayo zingine haziingii kwenye kumbukumbu ya kache (karibu 10%) na lazima ifanye kazi, ikingojea data kutoka kwa OP, ambayo inapunguza kasi ya operesheni.
Inathiri kwa kiasi kikubwa kasi ya compressor na uendeshaji wa mfumo wa pembejeo / pato la data. Maombi kwa OP kutoka kwa maombi ya kuzuia I/O ya data kutoka kwa CPU, ambayo pia hupunguza kasi ya mbano. Tatizo hili ni muhimu kwa kompyuta za mezani na kompyuta za mezani; kwa seva sio muhimu kwa sababu ya kitengo cha juu zaidi cha kudhibiti ufikiaji wa basi na RAM ya chaneli nyingi.
Katika maandishi yote kwenye kifungu tunazungumza juu ya ukandamizaji; mtengano unabaki nje ya wigo wa nakala hii kwani "kila kitu kimefunikwa kwa chokoleti". Utengano ni haraka sana na unazuiliwa na kasi ya I/O. Msingi mmoja wa kimwili katika thread moja hutoa kwa urahisi kasi ya upakiaji ya GB 3-4 kwa sekunde.
Hii ni kutokana na kutokuwepo kwa operesheni ya utafutaji wa mechi wakati wa mchakato wa kupungua, ambayo "hula" rasilimali kuu za processor na kumbukumbu ya cache wakati wa ukandamizaji.
Kuegemea kwa hifadhi ya data iliyobanwa
Kama jina la darasa zima la programu zinazotumia ukandamizaji wa data (wahifadhi kumbukumbu) zinavyoonyesha, zimeundwa kwa uhifadhi wa muda mrefu wa habari, sio kwa miaka, lakini kwa karne na milenia...
Wakati wa kuhifadhi, midia ya uhifadhi hupoteza baadhi ya data, hapa kuna mfano:
Mtoa habari huyu wa "analog" ana umri wa miaka elfu, vipande vingine vimepotea, lakini kwa ujumla habari hiyo "inasomeka" ...
Hakuna hata mmoja wa watengenezaji wanaowajibika wa mifumo ya kisasa ya kuhifadhi data ya dijiti na vyombo vya habari vya dijiti vinavyotoa hakikisho la usalama kamili wa data kwa zaidi ya miaka 75.
Na hili ni shida, lakini shida iliyoahirishwa, vizazi vyetu vitatatua ...
Mifumo ya uhifadhi wa data ya dijiti inaweza kupoteza data sio tu baada ya miaka 75, makosa katika data yanaweza kuonekana wakati wowote, hata wakati wa kurekodi kwao, wanajaribu kupunguza upotovu huu kwa kutumia redundancy na kusahihisha kwa mifumo ya kurekebisha makosa. Mifumo ya urekebishaji na urekebishaji haiwezi kila wakati kurejesha habari iliyopotea, na ikiwa inafanya hivyo, hakuna uhakika kwamba operesheni ya kurejesha ilikamilishwa kwa usahihi.
Na hili pia ni shida kubwa, lakini sio iliyoahirishwa, lakini ya sasa.
Compressors za kisasa zinazotumiwa kuhifadhi data ya dijiti zimejengwa juu ya marekebisho anuwai ya njia ya kamusi, na kwa kumbukumbu kama hizo upotezaji wa kipande cha habari itakuwa tukio mbaya; kuna hata neno lililowekwa kwa hali kama hiyo - kumbukumbu "iliyovunjika". ...
Kuegemea kidogo kwa kuhifadhi habari katika kumbukumbu kwa mfinyazo wa kamusi kunahusishwa na muundo wa data iliyobanwa. Taarifa katika kumbukumbu kama hiyo haina maandishi chanzo, nambari za maingizo katika kamusi huhifadhiwa hapo, na kamusi yenyewe inabadilishwa kwa nguvu na maandishi ya sasa yaliyobanwa. Ikiwa kipande cha kumbukumbu kitapotea au kupotoshwa, maingizo yote yanayofuata ya kumbukumbu hayawezi kutambuliwa ama kwa maudhui au kwa urefu wa ingizo katika kamusi, kwa kuwa haijulikani nambari ya ingizo la kamusi inalingana na nini.
Haiwezekani kurejesha habari kutoka kwa kumbukumbu "iliyovunjika" kama hiyo.
Algorithm ya RTT inategemea njia ya kuaminika zaidi ya kuhifadhi data iliyoshinikizwa. Inatumia njia ya faharisi ya uhasibu kwa kurudia vipande. Njia hii ya ukandamizaji hukuruhusu kupunguza matokeo ya upotoshaji wa habari kwenye njia ya uhifadhi, na katika hali nyingi upotoshaji sahihi wa moja kwa moja uliotokea wakati wa kuhifadhi habari.
Hii ni kwa sababu ya ukweli kwamba faili ya kumbukumbu katika kesi ya compression ya index ina sehemu mbili:
- uwanja wa maandishi wa chanzo na sehemu za kurudia zimeondolewa kutoka kwake;
- uga wa index.
Sehemu ya faharasa, ambayo ni muhimu kwa urejeshaji taarifa, si kubwa kwa ukubwa na inaweza kunakiliwa kwa hifadhi ya data inayotegemewa. Kwa hivyo, hata ikiwa kipande cha maandishi ya chanzo au safu ya faharisi imepotea, habari zingine zote zitarejeshwa bila shida, kama kwenye picha na uhifadhi wa "analog".
Hasara za algorithm
Hakuna faida bila hasara. Njia ya ukandamizaji wa faharisi haibana mfuatano mfupi wa kurudia. Hii ni kutokana na mapungufu ya njia ya index. Faharasa ni angalau baiti 3 kwa ukubwa na inaweza kuwa hadi baiti 12 kwa ukubwa. Ikiwa kurudia kunakabiliwa na ukubwa mdogo kuliko index inayoelezea, basi haijazingatiwa, bila kujali mara ngapi marudio hayo yanagunduliwa kwenye faili iliyoshinikizwa.
Mbinu ya ukandamizaji wa jadi wa kamusi inabana kwa ufanisi marudio mengi ya urefu mfupi na kwa hivyo kufikia uwiano wa juu wa mbano kuliko mgandamizo wa faharasa. Ukweli, hii inafanikiwa kwa sababu ya mzigo mkubwa kwenye kichakataji cha kati; ili njia ya kamusi ianze kubana data kwa ufanisi zaidi kuliko njia ya faharisi, lazima ipunguze kasi ya usindikaji wa data hadi megabytes 10-20 kwa sekunde kwenye hali halisi. usakinishaji wa kompyuta na mzigo kamili wa CPU.
Kasi hiyo ya chini haikubaliki kwa mifumo ya kisasa ya kuhifadhi data na ina maslahi zaidi ya "kielimu" kuliko vitendo.
Kiwango cha ukandamizaji wa habari kitaongezeka kwa kiasi kikubwa katika urekebishaji unaofuata wa algorithm ya RTT (RTT-Max), ambayo tayari iko katika maendeleo.
Kwa hivyo, kama kawaida, itaendelea ...
Chanzo: mapenzi.com