數(shù)據(jù)壓縮算法：對(duì)于程序員來說，這項(xiàng)新技術(shù)特別實(shí)用

注：【 圖片來源：MIT CSAIL 所有者：MIT CSAIL 】

數(shù)據(jù)壓縮技術(shù)之一，就是通過消除冗余來釋放存儲(chǔ)容量，提高計(jì)算速度，或是帶來其他好處。

但是，在目前的計(jì)算機(jī)系統(tǒng)中，訪問主存的成本很大。因此，在存儲(chǔ)器中使用數(shù)據(jù)壓縮技術(shù)有助于減少提取數(shù)據(jù)的頻率和數(shù)量，提高設(shè)備的性能。

一般來說，現(xiàn)代設(shè)備以固定大小的塊（chunk）來進(jìn)行管理和傳輸數(shù)據(jù)，傳統(tǒng)的壓縮技術(shù)必須在這些塊上運(yùn)行。然而，軟件存儲(chǔ)數(shù)據(jù)并不使用固定大小的塊，而是使用對(duì)象（object），這種數(shù)據(jù)結(jié)構(gòu)可以容納各種類型的數(shù)據(jù)，它的規(guī)模的也可大可小。

因此，傳統(tǒng)的數(shù)據(jù)壓縮技術(shù)很難處理對(duì)象。

本周ACM國際編程語言和操作系統(tǒng)架構(gòu)支持會(huì)議上發(fā)表的一篇論文中，MIT的研究人員描述了第一種“跨存儲(chǔ)層次壓縮對(duì)象”的技術(shù)。這種技術(shù)可以降低內(nèi)存使用率，同時(shí)也可以提高性能和效率。

研究人員用改進(jìn)后的Java虛擬機(jī)做了實(shí)驗(yàn)，結(jié)果表明，與傳統(tǒng)壓縮方法相比，這種新技術(shù)可以多壓縮兩倍的數(shù)據(jù)，還減少了一半的內(nèi)存使用率。

CSAIL的研究生Po-An Tsai是這篇論文的第一作者，她表示，“我們?cè)噲D提出一種新的存儲(chǔ)層次結(jié)構(gòu)，能夠進(jìn)行對(duì)象壓縮，因?yàn)榇蟛糠脂F(xiàn)代編程語言都是以對(duì)象的形式管理數(shù)據(jù)的?！?/p>

合著者Daniel Sanchez是計(jì)算機(jī)科學(xué)和電子工程專業(yè)的教授，同時(shí)也是CSAIL的研究員，他補(bǔ)充道，“所有計(jì)算機(jī)系統(tǒng)都將從這項(xiàng)新技術(shù)中受益，程序的運(yùn)行將變得更快，因?yàn)椴辉偈苤朴趦?nèi)存帶寬?！?/p>

由于Java、Python和Go這些現(xiàn)代編程語言以對(duì)象的形式管理數(shù)據(jù)，所以對(duì)于程序員來說，這項(xiàng)新技術(shù)特別實(shí)用。在不久的將來，我們就會(huì)看到設(shè)備擁有更快的速度，或者能在同一時(shí)間運(yùn)行更多應(yīng)用程序。

傳統(tǒng)的結(jié)構(gòu)以塊的形式將數(shù)據(jù)存儲(chǔ)到緩存存儲(chǔ)器（Cache）中，最近受訪的塊會(huì)上升到這里（上圖黃色層），雖然這里空間小，但訪問速度快。而舊塊則會(huì)下降，最終回到主存（上圖藍(lán)色層）中。

雖然這種數(shù)據(jù)之間的調(diào)動(dòng)十分靈活，但成本也不低。

在數(shù)據(jù)調(diào)動(dòng)的過程中，如果目標(biāo)數(shù)據(jù)不再Cache中，Cache就要訪問主存，并大范圍搜索數(shù)據(jù)的地址。入下圖所示，Cache訪問主存并返回的時(shí)間大約是100~300個(gè)周期。耗時(shí)太長(zhǎng)，存在局限性。

Sanchez發(fā)現(xiàn)了傳統(tǒng)模式的局限性，他思考著，“既然現(xiàn)代編程語言中數(shù)據(jù)管理的單位是對(duì)象，那我們?yōu)槭裁床唤ㄒ粋€(gè)處理對(duì)象的存儲(chǔ)層次結(jié)構(gòu)呢？”

于是，研究人員在之前的傳統(tǒng)存儲(chǔ)層次結(jié)構(gòu)上進(jìn)行改進(jìn)，便于直接處理對(duì)象。

1.Hotpad/pad

在去年10月發(fā)表的一篇論文中，研究人員詳細(xì)介紹了一個(gè)名為Hotpad的系統(tǒng)，可以用來存儲(chǔ)對(duì)象。由于這個(gè)系統(tǒng)的各個(gè)層次之間關(guān)系緊密，也可稱為pad。

這整個(gè)結(jié)構(gòu)基于一個(gè)芯片存儲(chǔ)器，效率高且不需要進(jìn)行復(fù)雜的搜索，因?yàn)槌绦蚩梢灾苯右谜麄€(gè)pad所有對(duì)象的位置。新分配的，或最近引用的對(duì)象，以及它們指向的對(duì)象，都停留在速度最快的層次，以便快速訪問。

當(dāng)這個(gè)層被填滿時(shí)，系統(tǒng)就會(huì)開始“篩查”。篩查的過程會(huì)保留最近引用的對(duì)象，但較舊的對(duì)象會(huì)被下放到較慢的層，除此之外，系統(tǒng)還會(huì)刪除不再有用的對(duì)象，以釋放空間。隨后，每個(gè)對(duì)象的指針都會(huì)更新，指向新對(duì)象的位置。通過這種方式，程序訪問對(duì)象的成本比通過緩存層來搜索要低得多。

2.Zippad

研究人員還設(shè)計(jì)了一種名為Zippad的技術(shù)，利用Hotpad系統(tǒng)來壓縮對(duì)象。當(dāng)對(duì)象第一次在較快的層次啟動(dòng)時(shí)，它們會(huì)被解壓，但當(dāng)它們被下放時(shí)又會(huì)被壓縮。另一方面，跨級(jí)別的所有對(duì)象都指向那些壓縮的對(duì)象，這使得它們很容易恢復(fù)到更快的級(jí)別，并且比傳統(tǒng)技術(shù)下存儲(chǔ)得更緊湊。

3.基礎(chǔ)對(duì)象

與以前的技術(shù)相比，這種新技術(shù)還提供了更多的壓縮機(jī)會(huì)，因?yàn)橐郧暗募夹g(shù)僅限于在固定大小的塊中查找冗余。首先，該算法會(huì)選取幾個(gè)具有代表性的對(duì)象作為基礎(chǔ)對(duì)象。然后，只要有新對(duì)象加入，算法就會(huì)對(duì)比基礎(chǔ)對(duì)象和新對(duì)象，然后把它們的之間不同的數(shù)據(jù)存儲(chǔ)起來。

卡耐基梅隆大學(xué)電子和計(jì)算機(jī)工程助教Brandon Lucia十分贊賞這個(gè)新技術(shù)，因?yàn)樗镁幊陶Z言的特性，更好地進(jìn)行壓縮工作。他說：“這項(xiàng)工作的有趣之處在于，它利用對(duì)象的抽象性讓內(nèi)存壓縮更有效，從而使系統(tǒng)更快、更高效，具有新的計(jì)算機(jī)體系結(jié)構(gòu)特性?！?/p>

注：本文編譯自 MIT CSAIL，部分內(nèi)容來自網(wǎng)絡(luò)，由整合

版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。