地球人如果程序員還算是人的話）對字符串處理都不陌生，不管是低級語言還是高級語言，都離不開對字符串的處理，而常用的開發工具都對字符處操作提供了盡可能詳盡的幫助，標准Ｃ中的各種字符串函數strcpy、strcmp和strcat……），C++標准庫中提供了功能更強大的string，而微軟的MFC中提供的CString更是強大至極，是否還有理由寫自己的字符串處理類？幸福的程序員都是相似的，你們完全可以在已存在的各種類庫中選擇，而我這年邁的老程序員卻非常不幸，因為我有太多的理由要寫自己的字符串處理類……表面看是為了終極優化，其實歸根結底是因為我是屌絲，因為我很窮，因為我沒有錢購買更多更好的服務器。
先交待一下背景，本人某年革月某日突然對搜索引擎技術發生了深厚的興趣，對於愛玩技術的我來說，這股激情湧來已難於抑制，向老婆大人匯報了我的思想動態，強烈要求提供資金支持。老婆大人向來對我的這種玩勁不支持不提倡不反對，在她看來我玩技術是比打麻將更高雅一點的娛樂而已，男人嘛，總得有一點不良愛好。所以這次她大方了一點，大筆一揮批了一萬元“賭資”。一萬元的資金，包括購買服務器和服務器托管等，而服務器托管費用一年至少要七千多吧？那服務器的價格只能是兩千多了我不知道比普通PC還要廉價的服務器是否還能叫服務器）。而對於一個完整的搜索引擎來說，大體上需要幾個大模塊：數據抓取、數據分析、中文分詞、創建索引、信息去重、信息自動聚類、大數據存儲、數據壓縮和解壓縮、查詢和排序、WEB頁面生成、WEB服務器……如果你對這些的計算量還沒有概念的話，我可以告訴你，某公司對幾十萬個商品進行自動聚類計算，需要采用兩台服務器跑三天……所有這些工作我都得在一台最低端的“山寨服務器”上實時完成，這無異於要把大象裝進冰箱，不管元芳怎麼看，采用常規思路恐怕是行不通了，唯有優化並且往死命裡優化，才有可能殺出生機。 對於搜索引擎的整個工作來說，從數據抓取、數據分析、中文分詞、WEB頁面拼裝等都是對字符串在操作，可以說90%以上的時間都與字符串操作有關，所以除了框架上的設計要有講究之外，字符串的處理效率直接影響到搜索引擎的整體性能。那得回答兩個問題：現成的字符串類在效率方面怎麼樣？是否還有可優化的空間？經本人對各種字符串類做了詳盡研究後發現，現成的字符串類在性能方面雖然表現不錯，但僅僅只是不錯而已，還有非常大的優化空間。下面結合我的具體應用慢慢道來。 一、對於服務器來說，內存管理是最重要的事情之一 對於搜索引擎服務來說，各種數據，特別是字符串的構造、拉接、清空、子串代替、提取子串、重置長度等等特別頻繁，對內存分配和釋放操作幾乎每一毫秒都在發生，這會有什麼嗎？本人曾在新浪微博中提過一個說法“一個混沌的系統如何能夠自然而然地達到有序？這是不可能發生的事情，在非人工干預的情況下，所有事情的發展都是從有序到混沌的過程。對於長時間連續運行的服務器系統來說，內存資源不停地申請和釋放交替進行，不可避免地形成內存碎片。意識到這一點你成不了大牛，但沒有意識到這一點就連牛B都吹不響。” 當你意識到內存碎片對服務器的影響裡，首先想到的是內存池。不錯，一個設計優良的內存池可以減少內存碎片，同時也大大提升了性能。話說咱們的字符串類，首要考慮的問題就是與內存池技術的結合了。如何搞呢？很多現成的字符串類都提供定制內存管理的接口網上已有很多這方面的資料，如有興趣可以搜索），字符串類也必須有這個。由於搜索引擎的工作機制，各線程都是獨立工作的，很少有線程間的互訪問題。所以字符串對象的所有操作都是在一個線程內進行，那麼在內存池的設計中為了性能的原因而采用“無鎖編程”技術是相當容易的，邊內存的申請和釋放都不應使用系統的new和delete因為這兩個操作是有鎖的），而改用私有堆的方式。這雖與字符串的性能有很大關系，但畢竟是內存管理方面的內容，以後有空再詳細聊了，先此打住。 二、支持寫時拷貝技術是提升性能的基本 寫時拷貝是什麼東西？寫時拷貝的英文縮寫COW (copy-on-write)， 簡單來說就是在復制一個對象的時候並不是真正的把原先的對象復制到內存的另外一個位置上，而是在新對象的內存映射表中設置一個指針，指向源對象的位置，並把那塊內存內部做只讀標志。這樣，在對新的對象執行讀操作的時候，內存數據不發生任何變動，直接執行讀操作；而在對新的對象執行寫操作有變化）時，才將真正的對象復制到新的內存地址中，並修改新對象的內存映射表指向這個新的位置，並在新的內存位置上執行寫操作。 這種寫時拷貝的技術在操作系統底層是普通存在的，比如在同一個系統中運行多個進程，將多進程中同樣的對象數據）在物理存儲其中只有一個物理存儲空間，而當其中的某一個進程試圖對該區域進行寫操作時，內核就會在物理存儲器中開辟一個新的物理頁面,將需要寫的區域內容復制到新的物理頁面中，然後對新的物理頁面進行寫操作。這時就是實現了對不同進程的操作而不會產生影響其他的進程，同時也節省了很多的物理存儲器。字符串雖然與操作系統不在同一層級，但也有其共有的原理。在各函數中，免不了以字符串對象為參數或作為返回值的，還有在大量的字符串運算場合中，寫時拷貝技術將大大減少不必要的內存申請、釋放、拷貝等。 在我所能找到的字符串類中，基本上可以分成三種，一是有的庫提供的字符串類竟沒有支持寫時復制；二是有支持寫時復制的，但為了線程安全而采用了鎖技術，造成性能慢得象老牛；三、也有支持寫時復制技術而不采用鎖的，但在內存管理接口竟是全局的，無法支持“無鎖編程”。我一直記得前面說過的，前提是已擁有基於私有堆的無鎖的高效的內存池，如果咱們的字符串類沒有利用這一成果，那是自宮行為。 三、優化格式化函數 字符串的格式化操作幾乎是無所不在，有小的操作，比如整數、浮點數、日期、時間等轉字符串形式。而大的操作，比如在生成WEB頁面時需要往模板中按格式填入真實數據。在傳統的字符串處理類中比如MFC帶的CString）提供了Format和AppendFormat兩個方法，在應用時會發現性能低下，經分析發現好家伙，這兩個函數在內部潛伏了CPU大鳄：GetFormattedLengt。這是干什麼的呢？就是在真正格式化之前先計算所需要存儲區的長度的， 這個函數相當的費時間。我采用空間換時間的理念，為Format和AppendFormat兩個方法增加估計長度參數，在外部調用前就先估計其長度一般都是比實現可能長度還要大很多，雖然有可能造成空間的小浪費，但得到性能的回報也是值得的），這樣在內部真實執行格式化時不需要再計算，性能直接提升一倍多。 四、優化“+=”操作 別告訴我你沒有見過字符串的“+=”操作，字符串的拼接操作比街上的美女還要多，如果你采用“Str1 = Str1 + Str2”的形式而不是“Str1 += Str2”的形式來拼接，這無異於讓美女放棄優雅與你吐口水玩。 雖然由於有寫時拷貝技術的支持，“Str1 = Str1 + Str2”形式的操作雖不優雅但在性能上也並不差得太多，而畢竟是有“相加”和“賦值”兩個操作在裡面，給後續優化帶來了困難。對於WEB服務器來說，拼接一個幾十K甚至幾百K的WEB頁面是分分秒秒的事情。而傳統的字符串類對此並沒有做什麼特別的處理，頻繁而連續的“+=”操作造成內存不斷地被申請、釋放、拷貝。針對這種應用場景，我采用了兩個策略，一個是上面提到的“空間換時間”策略，在開始就對字符串對象分配足夠大的內存。二是因為“足夠大”是不好評估的，為了避免太頻繁的大內存移動操作， 我對“+=”操作搞了一點點策略性的優化，也就是先用小內存塊列表保存新加進來的數據而不是立即拼接到原來的字符串後面，在達到一定規模或者需要進行其它操作時才一次性地分配內存並完成真正的拼接過程。在應用環境下進行實測發現，性能提高了一個數量級。 五、針對小數據字符串做特殊處理 在購物搜索中，小數據字符串象星星一樣遍布各地，這些家伙個頭不大但數量繁多，比如達百萬級的關鍵詞和達千萬級的用戶查詢短語，如果都使用上面所說的“空間換時間”理念，那浪費的內存空間會讓你死得很難看打個比方，這就象你買房子多花那麼千兒八百的那無所謂了，如果你每天吃飯都多花千兒八百的，就等著你老婆砍你吧）。對於小數據的情況，一方面是內存分配時的成長粒度要上，要斤斤計較，另一方面在內存池的處理上也要對小內存的分配和釋放做策略上的調整。 這說起來好象挺簡單的，在實施過程中比較折磨人，沒有固定的模式，全是經驗模型。 以上就是比較接近常規方式的字符串處理類的優化過程，在實際應用中的效果相當令人滿意。有興趣的朋友可以看看本人的作品絕非產品）谷殼購物搜索。 之所以說以上的優化都是接近常規的方式，是因為本人還瘋狂地創建了“零內存”字符串類，以幾乎不增加內存的方式對大量字符串數據做各種處理，比如為了提高搜索性能而對關鍵字創建搜索樹等。既然是非常規方式，那也也只適用於特定應用場景。本文出自 “藍蜂” 博客，請務必保留此出處http://bluebee.blog.51cto.com/661175/1033101
