3

我正在编写一个基本的文本编辑器，它实际上是一个编辑控制框，我想在其中为我的主程序编写代码、数值和表达式。

我目前正在这样做的方式是将字符串输入到编辑控件中。在编辑控件中，我有一个类可以将字符串分解为“字形”，如单词、数字、换行符、制表符、格式标记等。例如，字形包含一个表示文字的字符串和一个短整数，表示尾随空格的数量。字形还包含绘制文本和计算换行时所需的信息。

例如，文本行“My name is Karl”将等于一个字形链接列表，如下所示：NewLineGlyph → WordGlyph (“My”, 1 个空格) → WordGlyph (“name”, 1 个空格) → WordGlyph(“is”, 1空白）→ WordGlyph（“Karl”，0 个空白）→ NULL。

因此，不是将字符串作为连续的字符块（或 WCHAR）存储在内存中，而是存储在小块中，并可能有大量的小分配和释放。

我的问题是；这样做时我应该关心堆碎片吗？您对提高效率有什么建议吗？还是完全不同的方式？:)

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

4

2 回答 2

2

你应该担心碎片化吗？答案可能取决于您的文档有多大（例如，字数），以及将进行多少编辑以及这些编辑的性质。您概述的方法对于静态（只读）文档可能是合理的，您可以在其中“解析”一次文档，但我想在幕后需要进行大量工作以保持您的数据结构在用户进行任意编辑时处于正确状态。此外，您必须确定“单词”是什么，这不一定在每种情况下都显而易见/一致。例如，“勤奋”是一个词还是两个？如果是一个，这是否意味着您永远不会在连字符处换行？或者，考虑一个“单词”不适合一行的情况。在这种情况下，

我的建议是将文本存储为一个块，并单独存储换行符（作为文本块的偏移量），然后在每次发生更改时根据需要重新计算换行符。如果您担心碎片化和最小化分配/解除分配的数量，您可以分配固定大小的块，然后自己管理这些块内的内存。这是我过去所做的：

  • 文本存储为一个字符块，但不是为整个文档使用一个连续的块，而是维护一个始终分配 4KB 的块的链接列表（即，4K 单字节字符或 2K WCHAR）。换句话说，文本存储为数组的链表，其中每个数组都分配给一个常量大小。

  • 每个块跟踪该块内使用/空闲的空间（即字符）。

  • 插入一个或多个字符时，如果当前块中有空间，我可以简单地在该块内移动内存（不需要分配/释放）。如果当前块中没有可用空间，但相邻块中有可用空间，那么我可以再次在现有块之间移动内存（不需要分配/释放）。如果两个块都满了，我才分配一个新的 4KB 块并添加到链表中的适当位置。

  • 删除一个或多个字符时，我只需要移动内存（最多 4KB）而不是整个文档文本。我可能还必须解除分配并删除任何完全为空的块。

  • 我还做一些“垃圾收集”以在适当的时候合并可用空间。这相当简单，涉及将字符从一个块移动到另一个块，以便某些块变为空并且可以删除。

从操作系统和/或运行时库的角度来看，所有的分配/删除都是相同的大小（4KB），所以没有碎片。由于我管理该内存的内容，因此我可以通过移动内存内容来消除浪费的空间，从而避免在分配的空间内出现碎片。另一个优点是它最大限度地减少了 alloc/dealloc 调用的数量，这可能是一个性能问题，具体取决于您使用的分配器。所以，这是对速度和大小的优化——这种情况多久发生一次？:-)

于 2011-09-02T19:30:59.270 回答
1

我不会担心堆碎片；现代堆管理器非常擅长处理这个问题。

不过，我可能会担心糟糕的数据局部性。将每个字形作为链表中的单独分配（尤其是像 std::list 这样的非侵入性列表），任何类型的文档传递都将以潜在的非缓存友好方式跳过整个内存。

文本编辑器比乍看起来更难。有很多专门的数据结构用于表示文本块和结构化文档。它们都针对不同类型的操作进行了优化。我建议搜索它们的解释，然后考虑您最需要执行的操作类型。

这篇论文很旧，但有很多很好的信息： http ://www.cs.unm.edu/~crowley/papers/sds.pdf

于 2011-09-02T19:49:59.500 回答