有更多的分配內存減慢操作？

Question

我讀了一本書叫做實時渲染和在光線球體交集算法的優化使用球體的半徑平方，所以筆者說：

標量R2（方半徑）可以被計算一次並存儲在球體的數據結構中，以試圖獲得進一步的效率。在 實踐中，這樣的「優化」可能會更慢，因爲訪問更多的內存是算法性能的主要因素。

怎麼會這樣效率不高？ r2值將在函數的本地範圍內訪問一次，這可能比明確地計算r2 = r * r慢嗎？

我甚至不知道慢操作價值accessment或者實際上具有存儲在內存中的數據。

Answer 1

你真的應該基準，但作者可能考慮的是CPU cache。有時（通常，但並非總是）重複的緩存未命中（或錯誤的branch prediction）會使您的程序變慢。

通常，當（super-scalar，pipelined）處理器缺少緩存（所以L3高速緩存未命中）從您的RAM棒讀取數據的角度來看，它可能會失去幾百個週期（納秒），這是足夠的時間來進行數百次算術運算（在寄存器內或L1高速緩存內部）。 因此，可能發生的是一個memoizing簡單計算可能不值得-同時（例如，由於具有較大的結構可能需要更多的存儲器帶寬和更高速緩存未命中）。

但邪在細節，則需要基準（和事情可能會在不同計算機上的不同，例如在你的筆記本電腦和運行相同 Linux操作系統在我的桌面上，用同樣編譯器和相同的二進制可執行），當然與optimizations的編譯器中啓用（如g++ -Wall -O2 -march=native與GCC ...）。

你會通過computer architecture看書學習更多。

上teach yourself programming in ten years閱讀這個漂亮的發人深省的頁面。它還給出了一張的表格，用於典型PC（它已在別處借用）的各種操作的大概時間。

Answer 2

我記得在此之前。這是不是很久以前，我仍然瞭解這一點。我會嘗試提供一個非正式的答案來補充已經很精確的答案。

對我特別的幫助是這兩個環節：

• http://lwn.net/Articles/250967/
• http://realtimecollisiondetection.net/pubs/GDC03_Ericson_Memory_Optimization.ppt

的最快途徑上手，雖然是搶自己一個體面的分析器可以打破您的代碼庫中涉及分析會話的每個小部分的執行時間。接下來，當您在更困難的熱點地區工作時，您不會遇到明顯的算法瓶頸，請開始深入測量緩存未命中和分支預測錯誤。

然後，獲得這些熱點爲什麼存在的知識，儘管有一個相當優化的算法，以及如何處理它們開始變得相當自動化 - 您將發現自己追逐熱點的信息。

存儲器層次結構

然而，簡單地說，計算機體系結構有一個存儲層次，從小型，快速，昂貴的內存大，速度慢，價格低廉的內存。它從一塊非常緩慢的大容量硬盤跨越DRAM，例如4千字節塊，然後一直延伸到由64字節高速緩存行組成的CPU高速緩存分層結構，並一直進入一個小小的寄存器，可能僅僅是8個字節（64位）。這個小小的寄存器是大部分操作執行的地方。

一旦執行操作並計算結果，通常結果必須以它們的方式備份此內存層次結構，以便它們可以持久保存，同時爲新內存區域上的新操作騰出空間。

爲了快速做到這一點，硬件通常設計爲從相當大的塊中較大但較慢的內存中獲取內存。例如，像硬盤這樣的輔助存儲設備比DRAM慢得多，所以計算機在內存中的頁面大小例如是4千字節塊。假設即使您立即請求了一個8字節（64位塊），您也可能會訪問周圍內存區域的數據。因此，內存以對齊的4千字節塊分頁到DRAM中，例如，假設（或「希望」）程序員將訪問以下指令集中的大量塊。

從DRAM到CPU緩存的應用程序也是同樣的。 CPU高速緩存比DRAM快得多，因此計算機傾向於將內存從DRAM以相當大的塊（通常爲64字節對齊的高速緩存行）從DRAM中取出到CPU高速緩存中。硬件設計者的假設/預測/希望再一次證明，在驅逐之前，您將利用該塊。

這種類型的進程再次從CPU緩存重新註冊（甚至比CPU緩存更快），從較慢的內存轉移到對齊的少數幾個更快的內存中（儘管這次只有很少的幾個）。

速度

這麼多軟件的速度最終是由內存訪問瓶頸。它需要一個非常優化的內存佈局，或者對一小塊內存進行非常多的計算，實際上是算術的瓶頸，而不是將數據從較慢到較快形式的內存傳輸的過程。您可以在真實世界的基準測試中看到這一點，在這些基準測試中，使用AVX指令可以提高主要由浮點運算組成的實際運算速度45％。當AVX指令比標量版快8倍時，爲什麼只有45％？拋開可能會插入AVX指令的潛在編譯器優化，其中很大一部分與內存有關。計算機可以非常快速地進行算術運算，但它們只能儘快完成，因爲它們可以在內存中加載到速度更快但內存少的形式（例如寄存器）中。

從軟件工程的角度來看，如果您可以使您的數據更小，連續，適當地與寄存器，緩存行和/或頁面的大小對齊並以塊連續訪問，那麼它會有很大的幫助。硬件設計人員在這裏進行的許多假設和優化都支持類似數組的順序訪問模式，在這種模式下，您正在訪問相鄰的內存區域，同時以更快的形式緩存，然後將其從快速形式的內存中逐出以騰出空間用於其他記憶區域的其他操作。

這怎麼會不高效？ r2值將在 函數的局部範圍內被訪問一次，這可能比明確地慢嗎？calcalclarting r2 = r * r？

如果它存儲在函數的本地範圍內，那麼它很可能會存儲並保存在寄存器中。作者特別提到的是將r^2的數據作爲記憶形式保存在一個球體中。

在這種情況下，正在處理的每個球體的大小都會增加，因此更少的球體會潛在地適應這些更快的內存塊。它也可能會拋開球體的對齊，並導致您遇到單個球體橫跨兩條對齊的緩存線的情形，這可能會以這種方式在性能上受到打擊。

您可以看到與查找表類似的趨勢。 LUT通常會降低績效並導致令人失望的結果，特別是如果它們相當大。我們最終交易減少算術增加內存訪問，內存訪問往往更快成爲瓶頸。

所以它非常違反直覺，這遠非專家的答案，但機器的工作方式和它認爲的「昂貴的工作」與我們傾向於自然想到的方式有很大的不同。開始對這些事情發展直覺的最好方法是防止出現更多的前瞻性瓶頸，而不是現在處理事務，而不是事後處理，而是開始分析很多事情。在這一點上，你會開始獲得某種程度的直覺，認爲什麼樣的數據結構是緩存友好的，哪些不是（連接結構缺乏連續的分配器，例如），雖然很多這些仍然不可避免地被發現事後看來。即使英特爾的開發人員也使用分析器來處理他們的代碼，因爲硬件的複雜性已經增加到很難準確預測它將要做什麼，而不是事後用事後分析器來實現它。

所以我的建議是試圖消除人們認爲「少工作」的東西，從內存訪問和參考位置的角度更多地考慮它。另外這是一個很好的入門鏈接：

https://en.wikipedia.org/wiki/Locality_of_reference

Answer 3

這是衆所周知的空間/時間權衡。不要只考慮一個球體，而要考慮很多球體。

template<typename T> struct sphere 
{ 
    T posx,posy; 
    T r; 
    T r2; 

template<typename T> static sphere<T> create(T posx, T posy, T r); 
} 

這意味着你存儲額外的幾個字節每一次。爲了做你的計算，這將不得不從內存中獲取。顯然，當有一些雷射線發生時，這不是問題。雖然在真實場景中你會有許多領域。你可以通過縮小它來獲得。