在内存中表示格式化文本的最佳方式？ 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