軟件測試中的Java列表對象的性能分析和測試

軟件測試中的Java列表對象的性能分析和測試

SDK提供了有序集合接口java.util.List的幾種實(shí)現，其中三種最為人們熟知的是Vector、ArrayList和LinkedList。有關(guān)這些List類(lèi)的性能差別是一個(gè)經(jīng)常被問(wèn)及的問(wèn)題。在這篇文章中，我要探討的就是LinkedList和Vector/ArrayList之間的性能差異。

�牐牉槿�面分析這些類(lèi)之間的性能差異，我們必須知道它們的實(shí)現方法。因此，接下來(lái)我首先從性能的角度出發(fā)，簡(jiǎn)要介紹這些類(lèi)的實(shí)現特點(diǎn)。

一、Vector和ArrayList的實(shí)現

�牐燰ector和ArrayList都帶有一個(gè)底層的Object[]數組，這個(gè)Object[]數組用來(lái)保存元素。通過(guò)索引訪(fǎng)問(wèn)元素時(shí)，只需簡(jiǎn)單地通過(guò)索引訪(fǎng)問(wèn)內部數組的元素：

�爟炔繑到M可以大于Vector/ArrayList對象擁有元素的數量，兩者的差值作為剩余空間，;便實(shí)現快速添加新元素。有了剩余空間，添加元素變得非常簡(jiǎn)單，只需把新的元素保存到內部數組中的一個(gè)空余的位置，然后為新的空余位置增加索引值：

�牥言�素插入集合中任意指定的位置（而不是集合的末尾）略微復雜一點(diǎn)：插入點(diǎn)之上的所有數組元素都必須向前移動(dòng)一個(gè)位置，然后才能進(jìn)行賦值：

�犑Ｓ嗫臻g被用光時(shí)，如果需要加入更多的元素，Vector/ArrayList對象必須用一個(gè)更大的新數組替換其內部Object[]數組，把所有的數組元素復制到新的數組。根據SDK版本的不同，新的數組要比原來(lái)的大50%或者100%（下面顯示的代碼把數組擴大100%）：

�燰ector類(lèi)和ArrayList類(lèi)的主要不同之處在于同步。除了兩個(gè)只用于串行化的方法，沒(méi)有一個(gè)ArrayList的方法具有同步執行的能力；相反，Vector的大多數方法具有同步能力，或直接或間接。因此，Vector是線(xiàn)程安全的，但ArrayList不是。這使得ArrayList要比Vector快速。對于一些最新的JVM，兩個(gè)類(lèi)在速度上的差異可以忽略不計：嚴格地說(shuō)，對于這些JVM，這兩個(gè)類(lèi)在速度上的差異小于比較這些類(lèi)性能的測試所顯示的時(shí)間差異。

�牐犕ㄟ^(guò)索引訪(fǎng)問(wèn)和更新元素時(shí)，Vector和ArrayList的實(shí)現有著(zhù)卓越的性能，因為不存在除范圍檢查之外的其他開(kāi)銷(xiāo)。除非內部數組空間耗盡必須進(jìn)行擴展，否則，向列表的末尾添加元素或者從列表的末尾刪除元素時(shí)，都同樣有著(zhù)優(yōu)秀的性能。插入元素和刪除元素總是要進(jìn)行數組復制（當數組先必須進(jìn)行擴展時(shí)，需要兩次復制）。被復制元素的數量和[size-index]成比例，即和插入/刪除點(diǎn)到集合中最后索引位置之間的距離成比例。對于插入操作，把元素插入到集合最前面（索引0）時(shí)性能最差，插入到集合最后面時(shí)（最后一個(gè)現有元素之后）時(shí)性能最好。隨著(zhù)集合規模的增大，數組復制的開(kāi)銷(xiāo)也迅速增加，因為每次插入操作必須復制的元素數量增加了。

二、LinkedList的實(shí)現

�牐燣inkedList通過(guò)一個(gè)雙向鏈接的節點(diǎn)列表實(shí)現。要通過(guò)索引訪(fǎng)問(wèn)元素，你必須查找所有節點(diǎn)，直至找到目標節點(diǎn)：

把元素插入列表很簡(jiǎn)單：找到指定索引的節點(diǎn)，然后緊靠該節點(diǎn)之前插入一個(gè)新節點(diǎn)：

�牼�(xiàn)程安全的LinkedList和其他集合
�牐犎绻�要從Java SDK得到一個(gè)線(xiàn)程安全的LinkedList，你可以利用一個(gè)同步封裝器從Collections.synchronizedList(List)得到一個(gè)。然而，使用同步封裝器相當于加入了一個(gè)間接層，它會(huì )帶來(lái)昂貴的性能代價(jià)。當封裝器把調用傳遞給被封裝的方法時(shí)，每一個(gè)方法都需要增加一次額外的方法調用，經(jīng)過(guò)同步封裝器封裝的方法會(huì )比未經(jīng)封裝的方法慢二到三倍。對于象搜索之類(lèi)的復雜操作，這種間接調用所帶來(lái)的開(kāi)銷(xiāo)不是很突出；但對于比較簡(jiǎn)單的方法，比如訪(fǎng)問(wèn)功能或者更新功能，這種開(kāi)銷(xiāo)可能對性能造成嚴重的影響。

�牐犨@意味著(zhù)，和Vector相比，經(jīng)過(guò)同步封裝的LinkedList在性能上處于顯著(zhù)的劣勢，因為Vector不需要為了線(xiàn)程安全而進(jìn)行任何額外的間接調用。如果你想要有一個(gè)線(xiàn)程安全的LinkedList，你可以復制LinkedList類(lèi)并讓幾個(gè)必要的方法同步，這樣你可以得到一個(gè)速度更快的實(shí)現。對于所有其它集合類(lèi)，這一點(diǎn)都同樣有效：只有List和Map具有高效的線(xiàn)程安全實(shí)現（分別是Vector和Hashtable類(lèi)）。有趣的是，這兩個(gè)高效的線(xiàn)程安全類(lèi)的存在只是為了向后兼容，而不是出于性能上的考慮。

�牐爩τ谕ㄟ^(guò)索引訪(fǎng)問(wèn)和更新元素，LinkedList實(shí)現的性能開(kāi)銷(xiāo)略大一點(diǎn)，因為訪(fǎng)問(wèn)任意一個(gè)索引都要求跨越多個(gè)節點(diǎn)。插入元素時(shí)除了有跨越多個(gè)節點(diǎn)的性能開(kāi)銷(xiāo)之外，還要有另外一個(gè)開(kāi)銷(xiāo)，即創(chuàng )建節點(diǎn)對象的開(kāi)銷(xiāo)。在優(yōu)勢方面，LinkedList實(shí)現的插入和刪除操作沒(méi)有其他開(kāi)銷(xiāo)，因此，插入-刪除開(kāi)銷(xiāo)幾乎完全依賴(lài)于插入-刪除點(diǎn)離集合末尾的遠近。

三、性能測試

�牐犨@些類(lèi)有許多不同的功能可以進(jìn)行測試。LinkedList應用比較頻繁，因為人們認為它在隨機插入和刪除操作時(shí)具有較好的性能。所以，下面我分析的重點(diǎn)將是插入操作的性能，即，構造集合。我測試并比較了LinkedList和ArrayList，因為這兩者都是非同步的。

�牐牪迦氩僮鞯乃俣戎饕�由集合的大小和元素插入的位置決定。當插入點(diǎn)的位置在集合的兩端和中間時(shí)，最差的插入性能和最好的插入性能都有機會(huì )出現。因此，我選擇了三個(gè)插入位置（集合的開(kāi)頭、末尾和中間），三種典型的集合大�。褐械龋�100個(gè)元素），大型（10,000個(gè)元素），超大型（1,000,000個(gè)元素）。

�牐犜诒疚牡臏y試中，我使用的是JAVA SDK 1.2.0和1.3.0系列的SUN JVM。此外，我還用HOTSPOT JVM 2.0進(jìn)行了測試，這個(gè)版本可以在1.3.0 SDK找到。在下面的表格中，各個(gè)測量得到的時(shí)間都以其中一次SDK 1.2 VM上的測試時(shí)間（表格中顯示為100%的單元）為基準顯示。測試期間使用了默認的JVM配置，即啟用了JIT編譯，因此對于所有JVM，堆空間都必須進(jìn)行擴展，以避免內存溢出錯誤。表格中記錄的時(shí)間是多次測試的平均時(shí)間。為了避免垃圾收集的影響，在各次測試之間我強制進(jìn)行了完全的內存清理（參見(jiàn)測試源代碼了解詳情）。磁盤(pán)監測確保磁盤(pán)分頁(yè)不會(huì )在測試過(guò)程中出現（任何測試，如果它顯示出嚴重的磁盤(pán)分頁(yè)操作，則被丟棄）。所有顯示出數秒應答時(shí)間的速度太慢的測試都重復進(jìn)行，直至記錄到一個(gè)明顯合理的時(shí)間。

�爩τ谝幠］^小的集合，ArrayList和LinkedList的性能很接近。當元素插入到集合的末尾時(shí)，即追加元素時(shí)，ArrayList的性能出現了突變。然而，追加元素是ArrayList特別為其優(yōu)化的一個(gè)操作：如果你只想要一個(gè)固定大小的靜態(tài)集合，Java數組（例如Object[]）比任何集合對象都具有更好的性能。除了追加操作，測量得到的時(shí)間數據差別不是很大，它們反映了各個(gè)JVM的優(yōu)化程度，而不是其他什么東西。

�牐犂�如，對于把元素插入到集合的開(kāi)始位置來(lái)說(shuō)（表1的前兩行），HotSpot 2.0 JVM加LinkedList具有最好的性能（85.3%），處于第二位的是 1.2 JVM加ArrayList（100%）。這兩個(gè)結果顯示出，1.2中簡(jiǎn)單的JIT編譯器在執行迭代和復制數組等簡(jiǎn)單的操作時(shí)具有很高的效率。在HotSpot中復雜的JVM加上優(yōu)化的編譯器能夠改進(jìn)復雜操作的性能，比如對象創(chuàng )建（創(chuàng )建LinkedList節點(diǎn)），并能夠利用代碼內嵌（code-inlining）的優(yōu)勢。1.3 JVM的結果似乎顯示出，在簡(jiǎn)單操作方面它的性能有著(zhù)很大的不足，這一點(diǎn)很可能在以后的JVM版本中得到改進(jìn)。

�牐犜谶@里我特別進(jìn)行測試的是ArrayList相對于LinkedList的另一個(gè)優(yōu)點(diǎn)，即預先確定集合大小的能力。具體地說(shuō)，創(chuàng )建ArrayList的時(shí)候允許指定一個(gè)具體的大�。ɡ�如，在測試中ArrayList可以創(chuàng )建為擁有100個(gè)元素的容量），從而避免所有隨著(zhù)元素增多而增加集合規模的開(kāi)銷(xiāo)。表1括號中的數字顯示了預先確定集合大小時(shí)性能的提高程度。LinkedList（直到 SDK 1.3）不能預先確定大小。

�牐牬送�，ArrayList只生成少量的需要進(jìn)行垃圾收集的對象，即，用來(lái)保存元素的內部數組對象，以及每次ArrayList容量不足需要進(jìn)行擴展時(shí)創(chuàng )建的附加內部數組對象。LinkedList不管可能出現的任何刪除操作，都為每一個(gè)插入操作生成一個(gè)節點(diǎn)對象。因此，LinkedList會(huì )給垃圾收集器帶來(lái)相當多的工作�？紤]到這些因素，對于任何中小規模的集合，我會(huì )選擇使用ArrayList而不是LinkedList。

�牨�2顯示了大規模集合的測試結果�？梢钥吹�，在出現大規模插入操作的時(shí)候，我們開(kāi)始遭遇嚴厲的性能懲罰。正如我們前面分析類(lèi)的實(shí)現所得到的結果，對于LinkedList來(lái)說(shuō)最差的情形出現在把元素插入到集合中間時(shí)。另外我們還可以看到，與使用ArrayList時(shí)把元素插入到集合開(kāi)頭的最差性能相比，使用LinkedList時(shí)把元素插入到集合中間的性能更差一些。和這兩種性能最差的情況相比，把元素插入到ArrayList中間的性能顯然要好得多。

�牐牽偟乜磥�(lái)，ArrayList再一次在大多數情形下表現出更好的性能，包括根據索引把元素插入到隨機位置的情形。如果你總是要把元素插入到集合中靠前的位置，LinkedList具有更好的性能；然而，此時(shí)你可以利用一個(gè)反向的ArrayList得到更好的性能，即，使用一個(gè)專(zhuān)用的實(shí)現，或者通過(guò)[size -index]映射翻轉索引在集合中的位置。

�牨�3顯示了超大集合的測試結果，從該表可以得出的結論與表2非常相似。然而，表3強調的是，超大集合要求數據、集合類(lèi)型、數據處理算法之間的恰到好處的配合

文章來(lái)源于領(lǐng)測軟件測試網(wǎng) http://kjueaiud.com/

TAG: java JAVA Java 對象 列表 軟件測試 性能分析