在內存中表示格式化文本的最佳方式？ C++

Question

我正在編寫一個基本的文本編輯器，它實際上是一個編輯控制框，我想爲我的主程序編寫代碼，數值和表達式。

我現在正在做的方式是將字符串提供給編輯控件。在編輯控件中，我有一個類將字符串分解爲「字形」，如單詞，數字，換行符，製表符，格式標記等。字形例如包含表示文字和字符的短整型字符尾隨空白的數量。這些字形還包含繪製文本和計算換行時所需的信息。

例如文本行「我的名字是卡爾」就等於字形的鏈表是這樣的： NewLineGlyph→WordGlyph（「我的」，1個空格）→WordGlyph（「名」，1個空格）→WordGlyph（ 「是」，1個空格）→WordGlyph（「Karl」，0空格）→NULL。

因此，不是將字符串作爲連續的字符串（或WCHAR）存儲在內存中，而是以小塊存儲，並且可能會有很多小的分配和釋放。

我的問題是;這樣做時，我應該關心堆碎片嗎？你有任何提示使其更高效嗎？或者完全不同的做法呢？ :)

PS。我在Win7上使用C++。

Answer 1

你應該關心碎片嗎？答案可能取決於您的文檔的大小（例如單詞數量），編輯將發生多少以及編輯的性質。您所概述的方法對於可以「解析」文檔一次的靜態（只讀）文檔而言可能是合理的，但我想像一下，爲了保持數據結構，需要在幕後進行大量工作在用戶正在進行任意編輯時處於正確的狀態。另外，你必須決定什麼是「單詞」，哪一個不一定是明顯/一致的。例如，「勤奮」一個字或兩個字？如果它是一個，這是否意味着你永遠不會用連字符換行？或者，考慮「單詞」不適合單行的情況。在這種情況下，你會簡單地截斷，還是想強制跨越這個單詞？

我的建議是存儲文本作爲一個塊，並且存儲線分別打破（如偏移到文本塊），則因爲每個有變化所需的時間重新計算換行。如果您關心碎片並儘量減少分配/釋放次數，則可以分配固定大小的塊，然後自行管理這些塊內的內存。這是我在過去所做的那樣：

• 文本存儲爲字符塊，但不具有對整個文檔的單個連續塊，我認爲，總是分配塊的鏈表4KB（即，4K單字節字符或2K WCHAR）。換句話說，文本被存儲爲數組的鏈表，其中每個數組被分配到一個常量大小。

• 每個塊跟蹤多少空間（即，字符）的分類之內的塊中使用/。

• 當插入一個或多個字符，如果在當前塊的空間，我可以簡單的是塊（不需要分配/解除分配）內移動存儲器。如果沒有空間是在當前塊中可用的，但空間相鄰塊可用，則再次我可以只轉移存在的塊之間的存儲器（不需要分配/解除分配）。如果兩個塊都已滿，只有這樣才能分配一個新的4KB塊並添加到鏈表中的適當位置。

• 刪除一個或多個字符時，我只需要移動內存（最多4KB）而不是整個文檔文本。我也可能不得不釋放和刪除任何變得完全空白的塊。

• 我也做了一些「垃圾回收」，在適當的時候合併可用空間。這很簡單，需要將字符從一個塊移動到另一個塊，以便某些塊變空並可以刪除。

從OS和/或運行時庫的角度來看，所有的分配的/ dellocations具有相同的尺寸（4KB），所以沒有碎片。而且，由於我管理內存的內容，我可以通過移動內存內容來消除浪費的空間，從而避免分配空間內的碎片。另一個好處是可以最大限度地減少alloc/dealloc調用的數量，這可能是性能問題，具體取決於您使用的分配器。所以，這是對速度和尺寸的優化 - 發生多少次？ :-)

Answer 2

我不擔心堆碎片;現代堆管理員在處理這個問題上非常擅長。

雖然我可能會擔心數據的局部性不佳。將每個字形作爲鏈接列表中的獨立分配（尤其是像std :: list這樣的非侵入式列表），任何通過文檔的傳遞都將以非緩存友好的方式在整個內存中跳轉。

文字編輯比他們初看起來更難。有用於表示文本塊和結構化文檔的專門數據結構的批次。它們各自針對不同類型的操作進行優化。我建議尋找他們的解釋，然後考慮你最需要做的操作類型。

本文是舊的，但它有很多很好的信息：http://www.cs.unm.edu/~crowley/papers/sds.pdf