Geek_Ling

摘要： 開篇上一篇博文對緩存的思考——提高命中率詳細介紹了高速緩存的組織結構，并通過實例說詳細明了cpu從高速緩存中取數據的過程，對于緩存的工作機制應該有了清晰的認識。這篇博文就來簡單討論以下對于緩存在實際開發(fā)中的應用，這里將告訴你如何讓你的程序充分利用該緩存，即如何編寫高速緩存友好的代碼。提示：如果高速緩存的運行機制還沒有清晰的認識，請參照前面文章。注1：關于文中提到的局部性的相關知識參照：局部性原理淺析——良好代碼的基本素質注2：這是一個系列的文章，收錄在程序性能優(yōu)化注3：文章知識有些地方不容易理解，所以用心才能看完噢。“用空間換時間”在搞算法的時候經常能聽到這種說法，算法研究中通常要考慮算法的時 閱讀全文

摘要： 開篇編寫高效的程序并不只在于算法的精巧，還應該考慮到計算機內部的組織結構，cpu微指令的執(zhí)行，緩存的組織和工作原理等。好的算法在實際中不見得有高效率，如果完全沒有考慮緩存、微指令實現的話。前兩篇博文局部性原理淺析介紹了程序的局部性原理，如何寫出局部性良好代碼。提高程序性能、何為緩存討論了存儲器層次結構，計算機內部的存儲結構、緩存的概念，簡單的介紹了緩存的工作機制。建議先閱讀前兩篇博文，雖然他們之間聯(lián)系不大，在前面也有一些對本文的鋪墊。而且，這是一個系列的文章。旨在優(yōu)化程序性能。這篇博文主要介紹的是緩存的組織、工作原理。撥開迷霧，讓你更加清晰的認識緩存。通用緩存結構回顧在提高程序性能、何為緩存中 閱讀全文

摘要： 開篇上一篇博文局部性原理淺析——良好代碼的基本素質中對程序局部性有了一個簡單的介紹。基本上已經知道了如何編寫有良好局部性的代碼。但是為什么有良好局部性的代碼就能有良好的運行效率，這個問題將在這篇博文中給出解答。至于存儲器內部的組織實現，將在下篇文章中敘述。存儲器層次結構我們知道，計算機里的存儲器有:硬盤、主存、高速緩存（其中又有一級高速緩存、二級高速緩存等等）、在往上就是寄存器。存儲器在計算機內部的組織方式如下圖所示：相信上圖大家并不陌生。wiki對The memory hierarchy 的介紹的時候也有此圖。我們發(fā)現，越往上，存儲器的容量越小、成本越高、速度越快。為什么會出現這樣的結構呢？ 閱讀全文

摘要： 開篇一個優(yōu)秀的程序、優(yōu)美的代碼，一般都具有良好的局部性。簡潔、高效是每個程序員的追求。了解程序的局部性，能編寫出更高效的代碼。因為有良好局部性的程序能更好的利用緩存。不過這方面的只是將在以后的文章中介紹。這篇文章就簡單的介紹以下程序的局部性原理。什么是局部性局部性通常有兩種形式：時間局部性(temporal locality)時間局部性指的是：被引用過一次的存儲器位置在未來會被多次引用（通常在循環(huán)中）。空間局部性(spatial locality)如果一個存儲器的位置被引用，那么將來他附近的位置也會被引用。（這樣說過于理論了些，在下面的論述中會有例子說明）數據引用局部性例子是最好說明問題的途徑 閱讀全文

摘要： 網上有很多關于程序員必讀的書單，感覺都不是很有代表性。今天無意看到了一篇總結還算不錯的書單。和園友們分享。以下書單中提到的書看過一部分，給我的感覺是經典就是經典。讀過之后確實得到了很多東西，它們都潛在的影響著我。透過書更能感受到的是一種思想，理性，透過經典，能得到質的升華。另如果園友有好書、何不一起分享進步以下是原文：哪本書是對程序員最有影響、每個程序員都該閱讀的書？國外知名網站stackoverflow上有一個問題調查：哪本書是對程序員最有影響、每個程序員都該閱讀的書？，這個調查已歷時兩年，目前為止吸引了153,432人訪問，讀者共推薦出了478本書(還在增加)，其中最火的一本書《Code 閱讀全文

摘要： 開篇相信有過編碼經驗的人都知道，程序的正常運行，只是最基本的要求。更多的，還要考慮程序的性能，運行效率，組織結構，和重用性等等。今天將簡單的討論一下如何優(yōu)化程序性能。要寫出高效的程序，可能多數初學者想到的是在程序中用合適的算法和數據結構。這確實是一中提高程序性能的主要方法。而這里要討論的是另一種方法，也是很多人都忽略但確實很重要的方法。也是我們這篇文章的主題：如何編寫出編譯器能有效優(yōu)化的源代碼。編譯器優(yōu)化的局限性沒有萬能的東西，編譯器也一樣。現代編譯器都會對源代碼進行優(yōu)化，以提高程序的性能。比如linux下的GCC編譯器就能控制優(yōu)化的等級，優(yōu)化等級高，對應的程序性能好。對于給定的代碼，編譯器并 閱讀全文

摘要： 開篇這篇文章介紹找最短路徑的一種算法，它的字我比較喜歡:啟發(fā)式搜索。標題上寫的是翻譯，只是覺得原文講解的思路很清晰。這篇文章整體構思和原文相差不多，只是有些地方有小的改動，我想的是用更容易理解的方式、更簡潔的把A*算法的思想呈現出來。文章中出現的詞openlist，closelist我覺得用原文會更好故沒有翻譯，在文中會有解釋。原文地址http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/a-pathfinding-for-beginners-r2003各位也可以直接參考原文。網上關于A*算法的文章還 閱讀全文

摘要： 上一篇對死鎖的思考【1】介紹了什么是死鎖，對于每種類型一個資源和多個資源的檢測，這里會介紹一下如何從死鎖中恢復死鎖的避免死鎖的預防說明：這不是一篇專業(yè)性的文章，只是力求讓讀者能理解、知道什么是死鎖。如果想要更具體深入的知識還需要查閱相關文獻。從死鎖中恢復搶占性恢復從字面上看，搶占性恢復就是強制把已經被占有的資源強制拿過來，分配給需要他的進程，而達到解除死鎖的目的。在不通知持有資源進程的情況下，將資源強制占用，用完后又還給進程，這和資源本身的特性有關。即有的資源是不可搶占的。比如說一個正在刻錄光盤的光驅，在它完成之前是不可搶占的。回滾技術簡單的說，就是再檢測到死鎖的時候設法回到還沒發(fā)生死鎖的狀態(tài) 閱讀全文

摘要： 開篇死鎖是操作系統(tǒng)中的重要概念，和操作系統(tǒng)中的其他重要概念一樣，對它的正確理解將幫助你寫出更加高效、優(yōu)秀的程序。這里沒有晦澀的定義，只有易懂的描述和生動的例子。相信你看了之后會有所收獲。什么是死鎖簡單的說，死鎖就是電腦里的硬件資源或者軟件資源不夠用了。為什么會有這種情況呢？比如說A占有資源m，請求資源n。B占有資源n請求資源m。進程A和B都會因為請求不到自己的資源而睡眠。下面將進一步介紹。更形象的描述-死鎖建模：為了能對死鎖進行更好的分析，我們?yōu)樗梨i建模。就是用一個有向圖來表示進程和資源的使用情況，圓形節(jié)點表示進程，方形節(jié)點表示資源。資源指向進程的邊表示該進程占有該資源，進程指向資源表示進程請 閱讀全文

摘要： 圖是一種常見的數據結構，深度優(yōu)先和廣度優(yōu)先搜索都是常用的算法，這篇博文先介紹深度優(yōu)先搜索。和往常一樣的，我會用樸實的語言來介紹它，所以只要認真看一定能理解。開始會先介紹下圖的表示方法，如果已經掌握了大可跳過。圖的表示要表示一個圖G(V,E)有兩種常見的表示方法，鄰接矩陣和鄰接表。這兩種方法可用于有向圖和無向圖。對于稀疏圖，常用鄰接表表示，它占用的空間|E|要小于|V|*|V|。鄰接表：圖G(V,E)的鄰接表表示由一個包含V列表的數組Adj組成，其中的每個列表對應于V中的一個頂點，對于v中的任意一個點u，靈界表Adj[u]包含所有滿足條件(u,v)屬于E的點v，也就是Adj[u]中包含所有和u相 閱讀全文