一般來說程式通常會被期待有優雅的結構化.物件化,有時候是基於可讀跟維護的需求,有時候是風格問題,但以我所知,一層又一層的結構化.物件化雖然對軟體設計.規劃和維護有幫助,但需要高速與效率處理時,結構化與物件化往往是不利的,雖然現在硬體快速,不同往年,不太需要錙銖計較,但如果真的遇到效能瓶頸,還是需要打破風格與慣例問題,特別是模擬器需要大量的計算,在某些部分的處理會是關鍵,每種語言的最佳化作法,可能跟語言或是編譯器.直譯器有些不同,但很多時候卻也是相通的,底下的一些經驗分享是以C#為主,但別語言或許也可通用(需要測試).
1.迴圈開展 :
這也是破壞結構優化處理速度的一個方式,通常跟畫面的輸出有關係,因為遊戲畫面是一個二微陣列,常常需要處理兩層式迴圈 ( for x 與 for y ) , 如果把一層展開,直接用hard code的方式 copy paste下去,效率提昇會非常非常多,展開兩層的方式如果再一定數量內 (tile 8x8共 64次上算尚可接受),效率會提升更多.
2.method開展 :
method的往返需要處理stack的push pop,以及數值傳遞,這些都需要花上處理的時間,而且所佔是相當高的,如果是存取頻繁的method,並且也只出現在幾個少數地方,而且method內的code並不多,可以考慮把method的內容提出,直接寫,不要再多一層method結構包覆.
3.不要使用語言提供的高階的物件 :
方便歸方便,但絕對是效能殺手,能夠避免用到就避免用到,另外一定要用到像是Bitmap,在set pixel 與 get pixel 也一定要用特殊方法去存取
參考 http://www.vcskicks.com/fast-image-processing.php
其實上面的優化還是不太夠, Color 這物件也要避免使用才對.
總之效能優化這事情,常常會跟優雅風格.結構化.物件化產生衝突,一般來說開發初期還是得注意到結構問題,但開發完成後如遇到瓶頸,就需要特殊手段來處理.
上面1.2.3都用過stopwatch測試過,差異非常大.
http://www.dotnetperls.com/optimization 這篇也是可以參考的一文.
其實模擬器需要處理的狀況,比較相似於編解碼器撰寫,C#的效能以現在的硬體條件來說,絕對可以處理過往比較舊的遊戲主機模擬(以我個人推測包括PS1,GBA本身,和它們之前主機都是OK的),只是在一些部分需要注意一下,過度層層結構化.物件化加上使用一堆高階的語言物件,會掛掉.
PS.VisualStudo編譯時開啟Optimize Code選項是基本常識了,另外在debug模式下執行也會降低效率,實測以非debug模式為主.
這篇只是初略寫,以後有更多心得和整理會繼續更新.
2015年1月26日 星期一
任天堂紅白機模擬器
任天堂紅白機 1983 年日本推出 , GameBoy 1989年推出,照理來說任天堂的硬體技術和複雜度應該會比較低,撰寫模擬器或許會比起寫GameBoy的簡單些,但事實並不是這樣.
也的確,任天堂紅白機除了因為有彩色輸出視訊的能力,因此跟GameBoy相比色彩的部分是進階一點點(也只有一點點,幾乎可以說是大同小異),其他的部分都簡單很多,特殊佔存器的數量少上不少,問題就是因為紅白機的構造簡單,換來是很多複雜的硬體處理規則,我覺得最主要有兩點是在撰寫紅白機模擬器相當棘手的部分(記憶體相關的問題與 ppu timing )
1.任天堂記憶體的部分映射規則很多,處理需要細心和了解夠透徹,另外Mapper種類繁多,如果有心要提高支援度,支援起來不是件小事情,記憶體映射又跟顯示的處理問題綁在一起.
2.任天堂因為CPU跟PPU兩塊是各自獨立的部分,視為兩個處理器,中間CPU透過記憶體佔存器溝通PPU,來讀寫PPU記憶體,這中間有滿複雜的規則.
3.因為ppu 跟 cpu獨自運作, timing處理起來反來比起GB更複雜,特別是FC的PPU運作方式,要把它timing的規則搞懂需要花點苦工和看你的悟性.
綜合以上,相比下撰寫GB模擬器還算是簡單一點的任務.
在 timing 跟 記憶體的問題處理上,最後我還是決定採用部分 poring 人家專案的方式來達成,以我現在的能力沒辦法在短時間內處理得很好和完全正確.
也的確,任天堂紅白機除了因為有彩色輸出視訊的能力,因此跟GameBoy相比色彩的部分是進階一點點(也只有一點點,幾乎可以說是大同小異),其他的部分都簡單很多,特殊佔存器的數量少上不少,問題就是因為紅白機的構造簡單,換來是很多複雜的硬體處理規則,我覺得最主要有兩點是在撰寫紅白機模擬器相當棘手的部分(記憶體相關的問題與 ppu timing )
1.任天堂記憶體的部分映射規則很多,處理需要細心和了解夠透徹,另外Mapper種類繁多,如果有心要提高支援度,支援起來不是件小事情,記憶體映射又跟顯示的處理問題綁在一起.
2.任天堂因為CPU跟PPU兩塊是各自獨立的部分,視為兩個處理器,中間CPU透過記憶體佔存器溝通PPU,來讀寫PPU記憶體,這中間有滿複雜的規則.
3.因為ppu 跟 cpu獨自運作, timing處理起來反來比起GB更複雜,特別是FC的PPU運作方式,要把它timing的規則搞懂需要花點苦工和看你的悟性.
綜合以上,相比下撰寫GB模擬器還算是簡單一點的任務.
在 timing 跟 記憶體的問題處理上,最後我還是決定採用部分 poring 人家專案的方式來達成,以我現在的能力沒辦法在短時間內處理得很好和完全正確.
2015年1月25日 星期日
談 tile 計算效率的優化處理
tile 在遊戲資料中可以視為是一個 8x8 pixels 的單位元素 (當然也可能有更大的組成) , 可以視為是一個組成畫面區塊的最基本要素,在任天堂紅白機或是GameBoy中一個 title 由兩個 16 Byte 的資料組成, 從兩個 16byte 的資料要處理解碼出 title 在遊戲主機中用的是硬體 pipline 設計去處理 , 因此雖然一個 tile 有 64個 pixel ,在硬體處理之下也僅只是一件一個步驟的事情 , 但由軟體模擬去處理可就不是這樣,算是相當耗費計算的工作 ( 64 * n 次動作 ),但通常來說 title 變動的頻率極低 , 多數是在換關卡等等之類的況下, 才會有tile 資料變動 , 因此多數會使用cache的技巧,也就是說 tile table(這些title會存放記錄在一個連續的記憶體區域,稱tile table ,但每台遊戲主機在稱呼上多少有著不同,但觀念是差不多的) 計算過一次 記錄下來結果, 之後除非再異動, 不然不會每次整個table都重算一次,這是一種cach的等級,比較進階的甚至會再細部到只處理table中某個位置tile的變動.
1.每次畫面存取 , 全部 table 裡的全部title重算一次 (loading最重,通常會造成嚴重效率問題)
2.每次畫面存取, 除非 table裡面的某些資料有異動,才會整個將table重算一次
3.每次畫面存取,僅只更新table裡面有異動的 title 部分.
(優化到啥程度,看各家本領,有時候優化過頭沒處理好,還會漏掉....)
通常一個還算能跑的模擬器,最少要達成 第二步驟的優化,除此外像是background title map也會進行cache優化 (簡稱BG MAP,一個二維陣列,每個位置紀錄放置哪個title來呈現出遊戲背景畫面).
如果以上聽模模糊糊,沒關係,再多看一些相關資料,就會通了.
上面是針對 tile cache的優化,但解 title 本身的計算處理優化又是另一個議題.
這邊我先假設讀者已經知道解 title 的方法 (也許以後再另行篇章撰寫),通常最少會有3曾迴圈
第一層迴圈 : 處理每個 tile , 好比說 title 有 256 個 , 迴圈就從 0 ~ 255
第二層迴圈 : tile的每一行 ,共有 8 行
第三層迴圈 : tile 的每一行中的每一個 pixel , 每行共 8個 pixel
我原本有想過說,tile算過後, table更新後,即使是最佳化的cache , 還是得針對有異動過的位置重算,如果算完能夠記錄住,直接搬移過來放置,不是就ok了? (話先說再前頭,這想法失敗)
每個 title 由 32 byte 組,共64bits,如果能建立一個索引關係,豈不是每次table更新,只要更新索引就好?
其實問題點就是這索引機制的設計,32BYTE 共 64bits,如果用 array 資料結構來 index ,這 64bits的資料量非常可怕 , 2^64 ,後來採用 C# 的 dictionary, key 就是由 64bits的 title 資料而來,value則是解出的 title 2維 pixles , 測試起來由於使用到比較進階複雜的資料結構物件,雖然免於重複計算,但光是建立索引的 key 和 從 dictionary 去撈取 value,本身就比解一個title的標準動作費時不少...... orz... 如果不靠 dictionary 物件呢? 自己建立特殊的資料結構 ? 想了又想....最主要的問題還是在於光是要生成這個 key 和建立mapping索引關係,到撈取資料,本身就有不少計算量,並沒有佔到便宜.....
原先的想法更單純,把所有 8x8 的可能性窮舉法算出來, 後來算一算後才知道不實際....
那靠多核心計算來當平行處理呢? 更慘....並不是任何計算處理靠平行和多核就一定能吃香,因為本身會有很多context switch , 這個會占用一定的時間,如果相對於計算任務來說, context switch 本身就超過計算時間,那並不划算,實測結果把 第三層 for 迴圈改成 平行處理的寫法下去,更慢..... orz.....
最後有明顯效果提升的,但也不是新花招的,大概就是迴圈展開這招,速度是提升,當然會多一點code的量,簡單來說就是把第三層的迴圈移除掉,直接把相同的code copy/paste 上 8次,並且將一些可以事先算好的東西先算好,出來的結果速度快了原來非常非常多倍......
這技巧是用空間換時間,並且事先把一些能夠前置處理掉的計算事先算好,少掉那些計算與每次回圈的counet判斷和 jump 的時間,效率就提升很多 , 至於把第二層環圈也移除掉呢 ? 效率會再提升多少,我不清楚,但的確也可以嘗試.... 不過就變成多了最少64倍的程使碼量就是,反正copy paste也不會太久.
結果最後還是繞回一個傳統.常見的老方法才是正解.
ps.如果有更好的技巧或是想法也歡迎分享
1.每次畫面存取 , 全部 table 裡的全部title重算一次 (loading最重,通常會造成嚴重效率問題)
2.每次畫面存取, 除非 table裡面的某些資料有異動,才會整個將table重算一次
3.每次畫面存取,僅只更新table裡面有異動的 title 部分.
(優化到啥程度,看各家本領,有時候優化過頭沒處理好,還會漏掉....)
通常一個還算能跑的模擬器,最少要達成 第二步驟的優化,除此外像是background title map也會進行cache優化 (簡稱BG MAP,一個二維陣列,每個位置紀錄放置哪個title來呈現出遊戲背景畫面).
如果以上聽模模糊糊,沒關係,再多看一些相關資料,就會通了.
上面是針對 tile cache的優化,但解 title 本身的計算處理優化又是另一個議題.
這邊我先假設讀者已經知道解 title 的方法 (也許以後再另行篇章撰寫),通常最少會有3曾迴圈
第一層迴圈 : 處理每個 tile , 好比說 title 有 256 個 , 迴圈就從 0 ~ 255
第二層迴圈 : tile的每一行 ,共有 8 行
第三層迴圈 : tile 的每一行中的每一個 pixel , 每行共 8個 pixel
我原本有想過說,tile算過後, table更新後,即使是最佳化的cache , 還是得針對有異動過的位置重算,如果算完能夠記錄住,直接搬移過來放置,不是就ok了? (話先說再前頭,這想法失敗)
每個 title 由 32 byte 組,共64bits,如果能建立一個索引關係,豈不是每次table更新,只要更新索引就好?
其實問題點就是這索引機制的設計,32BYTE 共 64bits,如果用 array 資料結構來 index ,這 64bits的資料量非常可怕 , 2^64 ,後來採用 C# 的 dictionary, key 就是由 64bits的 title 資料而來,value則是解出的 title 2維 pixles , 測試起來由於使用到比較進階複雜的資料結構物件,雖然免於重複計算,但光是建立索引的 key 和 從 dictionary 去撈取 value,本身就比解一個title的標準動作費時不少...... orz... 如果不靠 dictionary 物件呢? 自己建立特殊的資料結構 ? 想了又想....最主要的問題還是在於光是要生成這個 key 和建立mapping索引關係,到撈取資料,本身就有不少計算量,並沒有佔到便宜.....
原先的想法更單純,把所有 8x8 的可能性窮舉法算出來, 後來算一算後才知道不實際....
那靠多核心計算來當平行處理呢? 更慘....並不是任何計算處理靠平行和多核就一定能吃香,因為本身會有很多context switch , 這個會占用一定的時間,如果相對於計算任務來說, context switch 本身就超過計算時間,那並不划算,實測結果把 第三層 for 迴圈改成 平行處理的寫法下去,更慢..... orz.....
最後有明顯效果提升的,但也不是新花招的,大概就是迴圈展開這招,速度是提升,當然會多一點code的量,簡單來說就是把第三層的迴圈移除掉,直接把相同的code copy/paste 上 8次,並且將一些可以事先算好的東西先算好,出來的結果速度快了原來非常非常多倍......
這技巧是用空間換時間,並且事先把一些能夠前置處理掉的計算事先算好,少掉那些計算與每次回圈的counet判斷和 jump 的時間,效率就提升很多 , 至於把第二層環圈也移除掉呢 ? 效率會再提升多少,我不清楚,但的確也可以嘗試.... 不過就變成多了最少64倍的程使碼量就是,反正copy paste也不會太久.
結果最後還是繞回一個傳統.常見的老方法才是正解.
ps.如果有更好的技巧或是想法也歡迎分享
2015年1月14日 星期三
mirror memory
所謂的 mirror memory 在很多地方都看得到,簡單來說這種memory的特性是映射另一區域的記憶體 ,也就是說不論你是讀或是寫入某個記憶體,如果它是mirrir記憶體,那你同時也會寫入到另一個address的內容,至於為何會設計成這樣,背後應該有滿多設計上的考量因素,但細節我不是很了解,所以就不多揣測.
這邊要談的是 mirror memory 在模擬程式上的處理,看過一些處理方式.
1. 多 copy 一份到別位置 (寫入時候需要多偏移計算.指定和寫入的動作 ).
2. 透過計算,對應同一個address內容 ( read 時候需要多一個計算 ).
3. 事先將對應關係計算出來,寫入到table內 (read的時候和write需要經過各需要一次查詢動作)
哪個好壞? 這邊很難斷定,看用啥角度(追求效能? code的簡短? 結構化? ).看狀況(是寫入多還是讀取多,把cost高的放到比較少的運作去,但這得看實際狀況才知道).
我個人其實是比較喜歡 2 & 3 ,但每個人想法不同,這邊就看每個人自己的想法.
這邊要談的是 mirror memory 在模擬程式上的處理,看過一些處理方式.
1. 多 copy 一份到別位置 (寫入時候需要多偏移計算.指定和寫入的動作 ).
2. 透過計算,對應同一個address內容 ( read 時候需要多一個計算 ).
3. 事先將對應關係計算出來,寫入到table內 (read的時候和write需要經過各需要一次查詢動作)
哪個好壞? 這邊很難斷定,看用啥角度(追求效能? code的簡短? 結構化? ).看狀況(是寫入多還是讀取多,把cost高的放到比較少的運作去,但這得看實際狀況才知道).
我個人其實是比較喜歡 2 & 3 ,但每個人想法不同,這邊就看每個人自己的想法.
2015年1月6日 星期二
所謂的 illegal (unofficial) code
illegal 英文中是非法的.不合規定的意思,在這邊所謂的 illegal code 並沒有嚴重到所謂非法的涵義,而是指這個CPU操作瑪並沒有在官方技術文件上列出(所以也叫unofficial code),通常因為有一些不確定性,不是很建議使用,但可能有某些遊戲就正好使用到,因此illegal code的實作對於相容性有幫助,不過一般來說會用到的是少數,模擬器撰寫初期可以先省略不談.
至於為何會有這種 illegal code ? 有很多可能,以8 bit cpu來說,最少就可以有 256個操作碼(如果使用延伸碼可以更多,像z80中就可以用 0xCB 來當擴展, 其後面可以再加子操作碼), 並不是每一個 可能編碼的數字都有使用到,有些可能是為了編譯器留一手(純屬個人猜測).有些可能是為了未來預留.有些可能有某些不穩定的特性.有些會造成運作crash ,總之諸如此類的因素,沒有被列到官方文件中記載.
附帶一提的是,像是GameBoy用z80並不算是標準的z80,而紅白機用的6502也並不算是標準的6502,但大體上可以說是大同小異,只是在其中要特別注意到某些功能可能已經被移除.某些opcode的功能可能已經有變,這種差異性影響程度會更甚於illegal code有無被完整實作.
6502 opcode官方列出151個,但如果再加上illegal code,則有240多個,少掉的那幾個連illegal code可能也不算,會導致cpu 運作癱瘓(這種我覺得連illegal code都稱不上),這幾個是連實作都沒必要,而這些沒被官方列出來的opcode中很多的功能僅止是占用記憶體.時間與NOP而已.
PS.但因為公開測試ROM中,指令集測試連 illegal code都一起併入,為求測試完整性,因此我在實作中還是將非官方的部分實作進去.
訂閱：
文章 (Atom)
