线程同步机制小结 1 – Atomic Operation

线程同步机制有很多种,从概念上大概可以分为以下几种:

  1. Atomic Operation
  2. Mutex
  3. Spinlock
  4. Condition
  5. Read/Write Lock
  6. Semaphore

这些概念在不同的平台上有不同的实现,某些平台缺少某些概念,如 Java 在 1.5 前没有 Atomic Operation 和 Semaphore;某些平台将多个概念混合在一个 API 中,如 Win32 的 CriticalSection 混合了 Mutex 和 Spinlock;某些平台在这些概念的基础上又提出(构建)了一些新的概念。下面对每种概念在每个平台上的实现做一个总结。

1. Atomic Operation

所谓原子操作指的是不会被打断的操作,一般来说一个原子操作对应一个特殊的 CPU 指令。在所有的线程同步机制里原子操作是最迅速的,因为完全不需要加锁。原子操作是实现 Lock-Free 最重要的武器。原子操作中除了常见操作,如“加、减、与、或、非、赋值”操作等,常见的还有 Compare-and-Swap, Test-and-Set, Add/Sub-and-Get 等组合操作。

Java 5 里新加入的 Concurrent API 包含了一系列的 AtomicXXX 的类。实际上这些类只做了两件事情:1. 封装一个 volatile 修饰的变量来保证一般操作(加、减、赋值)是原子的;2. 通过调用系统相关的 API 来实现组合操作。Java 的 volatile 会保证对变量的操作是原子性的,这和 C/C++ 中的 volatile 有很大不同。

在 GCC 中原子操作需要通过特殊的内建函数来实现,参见:http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Atomic-Builtins.html

Microsoft 将原子操作叫做 Interlocked Operation,参见:http://msdn.microsoft.com/en-us/library/aa911383.aspx。.Net 里提供的 API 其实就是这些函数的简单封装,毕竟 CLR 的 Thread 就是 Win32 的 Thread。

C++ 0x 标准里也包括了一些列的 Atomic 操作,这里就不详细给出。

面试准 Senior Java Developer 的一种方法

最近看到了一个“程序员能力矩阵”,深感赞同,原文在这里:Programmer Competency Matrix ,另外 XGuru 同学的翻译在这里:[译文]程序员能力矩阵 Programmer Competency Matrix

回想一年前参加技术面试的经历,当时公司要招聘 Senior Java Developer 从每个项目叫了几个人去做技术面试(考官)。官方的硬要求是 3 年工作经验、CS相关专业毕业。在技术面试之前他们已经通过了技术和英语的笔试(我们是外企、英语为官方语言)。其中技术笔试题分为选择题和简答题,HR 的 MM 会把选择题的分算出来,也会给简答题一个大概的分数(毕竟天天看这几道题),遇到回答的太不寻常又头头是道的才会找工程师确认一下。其实这套题很简单,主要就是 Java 语言和标准库的一些内容,涉及到 EE 的东西不多(10%),对应到“矩阵”中基本都是 Level 1 的内容,很少有 Level 2 的内容,所以我觉得即使全答对也不并意味达到了 Senior 的程度,但同时我也并不要求面试者答满分。

HR 的标准是正确率 60% 以上就可以参加后一轮的面试,坦白说我觉得这个标准定的太低了,所以在面试开始前我会再看一遍他答的题,如果其中有致命错误(例如完全不知道 ArrayList 内部是用 array 实现的)就直接让 HR MM 回绝了。“矩阵”里列了很多东西,对于 Senior 我也有一个类似的标准,但在短时间的技术面试过程中很难对这么多方面进行判断,于是我个人制定了一个简单的方法,并相对一致的应用在每一次面试中。但让我遗憾的是通过这个测试的人很少……

我的方法很简单,我认为一个 Senior Developer 或有潜质成为 Senior Developer 的工程师应该至少具有以下素质:

1. 可以在有提示的情况下写出相对比较完美的代码。

2. 能够辨识出设计中的潜在问题,并提出改进方案。(这里面有一个潜在要求:理解他人设计和表达自己设计的能力)

3. 知识储备以及对于软件开发的热情与激情。

为什么是“有提示的情况下”,这里有两个原因:1. 因为“程序员不在纸上写程序”,面试中我们在纸上写程序,我会忽略书写错误,但对会引起编译错误的代码我会给出提示(但不会扣分)。2. 提倡但不要求程序员一开始就能想的尽善尽美,注重不断改进代码的能力。对于完美代码不同人有不同的认识,这里我希望看到:严谨的代码风格(包括对齐、命名、缩进……)、清晰的逻辑、适当的防御性验证、正确的错误处理、以及可行的性能优化。所有这些都可以通过下面这段简单的程序来考察:

我会要求面试者为下面这个类写一个 equals 函数(如果你有兴趣,不要看答案,来写写看):

class Money {
    float amount;
    String currency;
}

一般的面试者(3年以上经验)都能够至少顺利的写出以下代码(在实际面试中也遇到过完全不能写代码的,但大多数都写的比这个好一些):

public boolean equals(Money money) {
    if (this.currency == money.currency && this.amount == money.amount) {
        return true;
    } else {
        return false;
    }
}

如果有 IDE 的提示你会发现 equals 是 Override 来的,其参数类型应该是 Object。这里我会问面试者为什么参数类型是 Object 以及问什么不可以是 Money。这两个问题非常考量表达能力。

修改过的代码如下:

public boolean equals(Object obj) {
    Money money = (Money) obj;
    if (this.currency == money.currency && this.amount == money.amount) {
        return true;
    } else {
        return false;
    }
}

上面的代码没有对输入做适当的检测,如果传入的是非 Money 的对象程序会抛出异常,这里需要对参数类型作出判断:

public boolean equals(Object obj) {
    if (!(obj instanceof Money)) {
        return false;
    }
    Money money = (Money) obj;
    if (this.currency == money.currency && this.amount == money.amount) {
        return true;
    } else {
        return false;
    }
}

一般人的代码都会写到这个程度,但是这里面还有很大的空间,这时我会给出一点提示,比如“你觉得比较逻辑会不会有问题”,很多开发人员都会意识到需求其实还不清楚,比如 currency 是不是大小写敏感的?amount 比较的精度是多少?我没有在一开始就告诉面试者所有的要求,是因为用户不可能在一开始就把所有的需求想清楚,程序员要有发现潜在问题的能力。

...
    if (this.currency.equals(money.currency) && Math.abs(this.amount - money.currency) < LIMIT) {
...

到了这里,程序的正确性算是足够了,性能上还有提升的余地,但很多面试者基本上都想不出来了。比如:如果传入的参数是对象本身则不需要作任何判断直接返回 true;如果 Money 类是 final 的则可以用 getClass() 替代 instanceof 获得更高的性能;另外,别忘了复写 equals 的同时必须要复写 hashCode

代码写到这里算是差不多了,如果基础好上面的过程很快,然后我们可以就这个类的设计进行讨论,比如:这个设计有什么不好?应该怎么设计?如果引入汇率怎么办?

最后我都会惯例性的问两个问题:最近有在看什么软件技术的书/文章/网站?那本(或几本)技术书籍对你最有帮助?通过这两个我希望知道面试者是否有足够的学习兴趣和对软件开发的热情,以及面试者的技术储备、知识结构是怎样的。在面试中我发现大多数的面试者只看过很少的编程书籍,但几乎所有人都看过 Think in Java。另外还有一个很诚实的面试者告诉我“最近在看一个 Java 程序员面试的视频教程”。

真正有经验的开发人员可能会觉得上面的面试过于简单,但根据我的经验,即使标准降低到如此程度我们也很难招到合格的人,对此我也很无奈。刚刚开始作技术面试的时候,我问的问题主要是集中在算法数据结构等方面,但是后来上面反应问的过难(如果 hash table 算难的话),无奈只能降低标准。

DVCS 的修改 与 CVCS 的版本

软件行业有一句名言:“任何事情都可以通过引入一个额外的间接层而解决”。使用传统的集中式的版本控制系统如 Subversion、CVS 的时候我们经常遇到一个问题:当我们要完成一个较大的功能或者是要在现有开发以外一些新的尝试时,一方面我们不希望过早的提交这些未完成的(甚至是永远不会完成的)代码,以免影响到其他的开发人员;另一方面,我们又需要一个版本控制工具来纪录修改历史以及同步多个开发人员的代码。在 SVN 等工具中我们一般是做出一个新的 branch,然后在这个新的 branch 上工作。然而有过经验的人都知道,真正的麻烦在于当我们完成工作准备将代码与主分支(trunk)合并的时候,大量的 Merge 工作会然我们头痛不已。换句说这里面没有了持续集成。

以 Git, Bazzar, Mercurial 等为代表的“分布式版本控制系统(DVCS – Distributed Version Control System)”在传统版本控制系统的基础上增加了一个存储在本地的 Repository。现在开发人员可以随时将自己的修改提交到本地的 Repository 里,不用担心会影响到其他开发人员,也不会丢失自己的修改记录。更酷的是,开发人员之间可以随时 Pull 对方的代码,而不需要中央服务器的参与,也可以随时将中服务器上的最新修改合并到本地 Repository (这两者本质上是一样的)。当开发完成的时候开发人员可以将所有本地 Repository 的记录提交给中央服务器。由于具有随时同步 branch 的能力,我们可以很容易的持续集成,一遍开发新的代码一遍不断的将其他开发人员最新修改合并到本地,这样大大减少了最后与主代码库合并的工作量。

概念上看 DVCS 关注的是修改本身(changeset),而传统的版本控制关注的是“由修改而产生的版本”(revision)。所以 DVCS 更符合开发的事实情况。

我们的团队里每两周会有一个正式的 Build,这个 Build 会被 QA 拿去做成品测试、也有可能拿出来给客户(Boss)做演示。在 Build 构建完成之后、发布之前会有一个基本测试(BVT)来验证这个 Build 是否可用,如果没有通过则需要修改并重打 Build。这个过程有时候会很长,有时一连几天都不得不到一个合格的 Build。在这段期间使 Build 失败的那个开发人员(不知道是哪个倒霉的孩子)会竭尽所能 Fix 问题,在这期间为了不引入新的问题(另一个倒霉的孩子),其他开发人员被禁止提交代码。这样做的结果是,每隔两周就有那么几天,那些(好运的、大多数的)开发人员被迫在互联网上游荡。因为“程序员不在不能提交代码的情况下写代码”。其实使用新的 DVCS 可以从根本上解决这个问题。

这里有一些 Mercurial 相关的联接:

你决不应该做的事情 Big Rewrite

Big Rewrite 是指在大量的重写已经存在/运行很久的代码。

Joel On Software 上有一篇文章 Things You Should Never Do, Part I 讲的是 Big Rewrite 的坏处,里面说到程序员像建筑师,初到一个地方就想把那里铲平了重盖。相信大家都有这样的经验,进入一个新项目一段时间后,我们都会发现其中的种种问题,如代码风格不统一,代码难以阅读,二义性,性能低下,充斥着各种各样的补丁……。每当这种时候我们都有冲动通过重写将所有这些问题解决,但是我们应该抑制这样的冲动!因为:

代码质量并不等同于产品质量:一个经过长时间多人次维护的代码,一定充斥着各种各样的补丁。各种各样的修改使得原有的无辜的代码变得复杂难懂。但是这样的程序却是能够工作的程序,大量的 Fix 保证了程序能够在各种 Case 下工作。重写整个模块意味着你可能需要重新 Fix 那些已经 Fix 过的问题,如果 Fix 过多,你的下一任还会重写他。即使要重写,也必须要在重写前仔细研究旧有模块曾经修改过的问题,如果你不能在一开始就处理这些问题,那重写没有意义。

Big Rewrite 需要长时间的开发,甚至可能会导致丢失已有客户,你需要确定你是否有足够的资本来做这件事。在重写中失败的被砍掉的项目比比皆是。这肯定是一个痛苦的开发过程,远不像想象中的那么有创造的快感。

Big Rewrite 之后的代码不一定比前者好,重写代码的人不一定比前人优秀、有经验,最初写代码的那些人都已经离开或者升职了。提出 Big Rewrite 的人往往是优秀具有过剩的自信的年轻人,但这不绝对。当然如果所有代码都是你自己写的,那就重写吧(如果所有代码都是你自己写的你还会考虑重写么?),John Carmack 曾一遍遍的重写 Game Engine,不过天知道他重用了自己多少代码。

下面两篇文章可以作为参考:

你是在重新发明轮子么?

在当今的软件行业内“重新发明轮子(Reinventing the Wheel)”已经向当年的 goto 一样人人喊打了。论坛里但凡有人问基础一点的问题,如:“如何把 Unicode 的字符串转换成大写”,就会引起大量的讨伐。要是有人自己实现了一个 String 类那更是不可救药了。过之而不及,“重新发明轮子”确实坏处多多,但是在某些场合确有必要(后面会提到),而且很多时候重新发明的并不是轮子

Reinventing the Wheel 是指重新解决某些别人已经很好的解决过的问题,判断是否是在重新发明轮子,需要考察两个方面:1. 这个问题是否有高质量的、标准的解决方案。2. 你的问题与别人解决过的问题是否一致,或是否存在可接受的转化。我们的项目里有一个典型的例子,某 C 程序员在用 Java 实现一个模块时因为对 Java 标准库的不熟悉,自己实现了一个 HashTable。重新发明轮子的大多数理由都是这样,要么是不知道有标准实现,要么是对标准实现不够了解(信任)。

但并不是每次重写都是重新发明轮子!试着回答这样一个问题:Linus 写 Linux 是重新发明轮子么?Linus 编写 Linux 的初衷是在他的 386 上没有一个可用的 OS。所谓“轮子”,必须满足两个条件。首先是客观方面:要足够的健壮,最好是标准实现。其次从主观上讲,必须适合于你的问题域。MINIX 不是轮子因为不够健壮,DOS 也不是轮子因为不够用。

我现在所在的项目里有一部分处理 TIFF 的代码,09 我们进行了重写。初看来我们重新发明了两次轮子!

首先,为什么不用标准的 TIFF 库?这是因为所有的 TIFF 库都不满足我们的需求。我们知道 TIFF 中有很多中压缩算法,不同的 Page Description Language 如 PDF, PS, PCL, AFP 也各自支持不同的压缩算法,比如 CCITT G4 俗称 Group4 是 TIFF 和 PDF 中常见的压缩算法。当我们将一个巨大的 TIFF 放到 PDF 中时最简单的做法就是取出 Group4 的数据,不解压缩,直接拷贝到 PDF 中。现有的标准 TIFF 库并不允许我们这么做,通过他我们只能先解压缩、再压缩,对于大的图片这是很不经济的。所以这里标准 TIFF 库并不是我们的轮子。

其次,为什么要重写?原有代码只能工作于很有限的几种情况,事实上我们的原有代码只能处理 Group4 一种压缩方式,还不支持分段处理。另外代码也很不稳定,遗留的 Bug 比 Fixed 的多,这是我们重写的一个重要依据。现在的新代码才有资格成为轮子。

再试着回答这样两个问题:为什么所有的 C++ 框架都实现了自己的 String 类?为什 ICU 要定义自己的 String 类?

在 TopLanguage 里看到过一种对重新发明轮子行为的诠释:“好装13,求甚解”。 我一直不知道这句话里的“好”是应该读三声、理解成 Convenient,还是读四声、理解成 Like。对于“求甚解”这一点,在学习中还是应该提倡的,毕竟在泳池里学游泳效果还是比在泳池边上学好一点。Wikipedia 的 Reinventing the wheel 条目里也有这样一句:

At the same time, however, “reinventing the wheel” is an important tool in the instruction of complex ideas.

所以如果你的目的是纯学习,就放心大胆的重新发明轮子吧!注意是纯学习,不是在工作中学习,更不要把学习的成果(轮子)放到产品里。

只有当你没有办法获得轮子的时候,(无可奈何的)重新发明轮子才是允许的。绝大多数情况下,这是一个法律、商业、或政治问题,而不是一个技术问题。比如你的商业程序中的一个重要功能需要一个以 GPL 发布的库,引入这个库需要你的程序也以 GPL 发布,而这是你无法接受的。工作中还遇到过因为某些商业和政治原因要求程序纯 Java 的。

很多时候我们重新发明轮子只是因为不知道轮子已经存在了,传说 Google 内部要求员工在编写基础代码之前先用内部的搜索引擎寻找相似功能的代码,这种 Policy 是值得借鉴的。

最近 Mike Taylor 的一篇文章 Whatever Happened to Programming? 在软件行业内引起轩然大波,Slashdot、Reddit等网站纷纷转载。在文章中作者大呼“I want to make things, not just glue things together.”,并且引用 Knuth 的话:

There’s the change that I’m really worried about: that the way a lot of programming goes today isn’t any fun because it’s just plugging in magic incantations — combine somebody else’s software and start it up. It doesn’t have much creativity. I’m worried that it’s becoming too boring because you don’t have a chance to do anything much new. Your kick comes out of seeing fun results coming out of the machine, but not the kind of kick that I always got by creating something new. The kick now is after you’ve done your boring work then all of a sudden you get a great image. But the work didn’t used to be boring.

许多人都错误的将作者何这篇文章理解成“重新发明轮子”或“重写”的拥护者,在作者的第二篇文章:Whatever happened to programming, redux: it may not be as bad as all that 中,作者清楚的表达了对使用既有库的看法,并不是说绝对不能用既有库,但很多时候重用既有库并不是理想中的那么的完美和方便。

总之,我们应该怀疑自己是否是在重新发明轮子,但不应该被“伪轮子”或者“重新发明轮子”的思想限制住。

Java GUI 框架中的多线程

大多数的 GUI 框架都不是线程安全的,即修改 UI 或者从 UI 中获取数据的方法都必须执行在 UI 线程中。UI 线程的主要任务就是事件的分发和执行(绘图可以看作是绘图事件的执行),所以 UI 线程也叫做 Event-Dispatching Thread。在 Thread and Swing 里有这样一个规则:

Once a Swing component has been realized, all code that might affect or depend on the state of that component should be executed in the event-dispatching thread.

对于 Swing 来说 UI 线程并不是主线程(main 方法所在线程),这点与 SWT 不同,SWT 的 UI 线程是创建 Display 的线程,或者说建立消息循环的线程。Swing 组件的 Realize 实际上就是其 UI 线程的启动。启动 UI 线程的方法有三种:setVisible(true)、不赞成使用的 show()、以及 pack()

如果要在 UI 线程以外访问 UI 必须通过 SwingUtilities 的两个方法: invokeLater(Runnable run) 或者 invokeAndWait(Runnable run)

SWT 提供了相似的方法 Display.syncExecDisplay.asyncExec

Font Rending 的 Hint 机制对排版的影响

在设计一种 Font 时,设计者使用的是一个抽象的单位,叫做 EM,来源于大写 M 的宽度(通常英文字体中大写 M 的宽度最大)。EM 即不同于在屏幕显示时用的像素(Pixel)也不同于打印时用的点(Point; 1/72 inch),他是一种相对单位,随着字体和字号的不同变化。通常对于一个 12 号的字体一个 EM 的长度等于 12pt。

实际设计时会将 EM 分成更小的单位,一般成为 EM Unit,TrueType 中一般是 2048 Units = 1 EM,Type1 中一般是 1000 Unit = 1EM。假设在我们设计的字体中字母 a 的宽度为 998 Units,如果我们用 12 号字显示它,我们得到的字宽为 12 * 998 / 2048 = 5.84765625 Point。如果我们将这个字打印到纸上,在 2000 dpi 的打印机上我们需要放置 5.84765625 / 72 * 2000 = 162.434895833 个 Dot(可以将 Dot 理解成墨滴)。而实际上我们不可能得到 0.43 个 Dot,我们只能用 162 个点来描述字母 a。如果我们将同样的一个字母显示在屏幕上,一般来说屏幕多为 72dpi 或 96dpi,以 96dpi 为例也字母 a 需要 5.84765625 / 72 * 96 = 7.796875 个像素来显示,实际上我们得到的是 8 个。在排版时我们需要根据一个字符的宽度来计算下一个字符的位置,这里的问题是:由于输出设备的限制我们永远也不可能将字母放在理论中的位置,设备的分辨率越低结果偏差的越大。反锯齿能够在一定程度上缓解这个问题,但不总是能的到好的结果。

另外在字体渲染时有时候会出现这样的问题,字母 H 的两个竖笔画不一样粗,这通常跟字母在屏幕上的位置有关,为了解决类似的问题,字体设计时都会提供一些额外的信息来根据输出设备的分辨率调整笔画。这就是 Hint 机制,或者叫 Grid-Fitting。由于 Hint 的存在,同一个字母在不同的设备上输出会有不同的宽度,这对排版有很大影响。所见即所得的排版要求我们在屏幕和纸上有相同的排版结果。如果我们按照理论值排版,在屏幕上我们可能会看到不美观的输出,参见截图。如果我们按照屏幕 Fitting 值排版则不能够最大化的利用字体设计师的工作,他们仔细调整过的字宽不能在纸上还原。

下图是个程序示例(Java),展示了不同的渲染方式会得到不同的字体宽度和不同的渲染结果。图中左右半部分分别是没有使用反锯齿(左)和使用反锯齿(右)的效果,而图中上下半部分分别是使用整数坐标(上)和使用分数坐标(下)的效果。

在图上可以看出使用分数坐标的 M 具有不一致的间距。所有的这些都对实现“所见即所得”的排版软件带来了很大困难,在 FreeType 的主页上有一些有关的文章,参见这里。其中提出了两种解决方案:

There are two ways to achieve this: either use the scaled and unhinted glyph metrics when laying out text both in the rendering and printing processes, or simply use whatever metrics you want and store them with the text in order to get sure they are printed the same on all devices (the latter being probably the best solution, as it also enables font substitution without breaking text layouts).

为了确定主流排版/字处理软件是如何解决这个问题的,我使用同样的基准文档(Tahoma 12pt 大写 M)做了测试。在 MS Word 2007 & MS Word 2003 中的结果如下:

可以看出 MS Word 的渲染结果也有不一致的间距,另外每个 M 字符都完全相同,这意味着 MS Word 是将一个字符渲染出来,然后不断的贴图。这也是常见的做法,优点是速度快,不需要在每个位置重复渲染。

在 Adobe InDesign 中以高质量显示的结果如下:

可以看出 InDesign 的渲染结果也有不一致的间距,但是明显 Adobe 具有更好的反锯齿算法,视觉上很难发现不同,但放大后还是能够看得比较清楚。另外 InDesign 的每个 M 字符都不相同,也就是说 InDesign 是对每个字符单独进行渲染,难怪效果会好。

结论

1. 使用设备无关的(高精度的)方式进行排版.

2. 显示效果不好时,使用每个字符单独渲染的策略.

3. 有些时候需要根据输出设备的限制进行 Grid Fitting,比如在 AFP 中对字符的位置/宽度有很大限制.

Text Editor 的 Piece Table 结构

Charles Crowley 在 Data Structures for Text Sequences 中描述了一种用于存储和编辑文本的数据结构 Piece Table。这种结构被大多数 Professional 的文本编辑器/字处理器所使用。另一种广为应用的(更简单)的数据结构是 Gap,最初被用在 Emacs 中,现在的 Scintilla,Java Swing Text Field 等文本编辑组建都使用这种结构。Charles Crowley 的文章中有详细的关于这两种结构的性能比较。

在处理大型文档的时候,“Piece Table + 缓存优化的 ItemAt 操作”的性能要高于“Gap”结构。开源字处理软件 AbiWord 就使用了这种结构。在 AbiWord 开发者的博客上有一个将 Piece Table 所有操作都提高到 O(log n) 的方法,参见 Improving the AbiWord’s Piece TableAbiWord 的开发计划里也有相应 Speed Up Piece Table 的计划。这里的优化方法是将本来用 Linked List 存储的 Piece 以 Red-Black Tree 代替,由此将 ItemAt 操作提高到 O(log n)。

Piece Table 的结构由几部分组成:

1. Sequence:

Sequence 是整个数据结构的接口,用户程序唯一的访问方式。逻辑上 Sequence 由一系列 Item 组成。Item 是存储和操作的最基本单元,在文本编辑器中可以与 Character 对应。Sequence 所能提供的操作与 List 相同,包括:Insert, Delete, Replace, ItemAt, Undo/Redo 等。物理上 Sequence 并不直接存储 Item(Item 存储在最后一层 Buffer 中),Sequence 存储的是一系列的 Piece Descriptor。每个 Piece Descriptor 指向了一个 Piece。

Sequence 和 Piece Table 是等价词。Sequence 用来讨论逻辑结构(接口)而 Piece Table 用来说明物理结构(实现)。

2. Piece:

Piece 是一组连续的 Item。这里的连续有两层意义,逻辑上连续和物理上连续。简单说 Item Index in Sequence 的连续是逻辑连续,而 Item Offset in Buffer 的连续是物理连续。Piece 中的 Items 既是逻辑连续又是物理连续。有些文章里将 Piece Descriptor 称为 Piece,而将 Piece 称为 Span。Piece 的成员包括:指向 Buffer 的指针,在 Buffer 中的 Offset,以及长度 Length. 每次添加操作都会增加一个新的 Piece,根据情况有可能将旧的 Piece 拆分成两个。每次删除操作也会相应的 Piece 删除或拆分。

3. Buffer:

Buffer 是真正存储 Item 的地方。在 Charles Crowley 的文章中 Piece Table 仅仅包括两个 Buffer,一个存储整个被编辑的文件,另一个存储添加的字符(被删除的字符也保留在 Buffer 中,可用于 Undo/Redo)。第一个 Buffer 是 Fixed Length 的,而第二个 Buffer 是 Append Only 的。试作中我们可以使用多种方法优化这两种 Buffer。

可以看出对于 Sequence (Piece Table) 所有的添加删除操作本身都是 O(1),与 Linked List 相同。但其访问操作(ItemAt)是 O(k),这里 k 为 Piece 的数量。这是由于我们使用 List 或 Array 存储 Piece Descriptor。我们也注意到所有的添加删除操作都需要先找到相应的 Piece,而这个操作也是 O(k) 的,这时我们可以简单的将最近一次访问的 Piece 缓存起来来大幅度提高性能。这也是 AbiWord 的做法。对于 O(k) 的操作我们可以尽可能的减少 k (Piece 的数量),最简单的方法是避免每个字符插入操作都产生一个 Piece,将一系列连续的插入删除操作产生一个 Piece。

更高级的优化技术是将 List 结构的 Piece Table 转换为 Red-Black Tree 结构。每个 Tree Node 包含:一个 Piece,其左分支的所有 Piece 的 Length (注意与 Index in Sequence 不同)。

Text Editor 有关概念

Text Model 存储文本以及相应属性的模型,主要有两种不同的实现策略:树形结构和平面结构。树形结构类似 Dom,可以很好的表现结构化文档,但是比较复杂。平面结构相对简单的多,大多数的编辑器(e.g. Emacs),字处理器(e.g. AbiWord, OpenOffice)都用的是平面结构。

Text Model Coords 用来在 Text Model 中定位的坐标系。对于树形结构的 Text Model 其定位方式为节点链接(或指向节点的路径 e.g. XPath)以及节点内偏移值。对于平面结构则仅仅是一个索引值。

Text Presentation 展示文本的模型,一般分别为 Block, Line, Run …

Text Presentation Coords 用来在 Text Presentation 中定位的坐标系,其值通常为 (x,y)。Text Editor 必须能够在 Text Model Coords 和 Text Presentation Coords 之间变换。例如将鼠标点击(x,y)对应到 Text Model 中的某个字符/元素。

Text Editor Design 资料整理

Design and Implementation of a Win32 Text Editor

The Craft of Text Editing, or Emacs for the Modern World, by Craig A. Finseth. PDF Here!

Data Structures for Text Sequences, by Charles Crowley. PDF Here!

ned – Text Editor of the Future

AbiWord Developement

Improving the AbiWord’s Piece Table

Data Structures in the Andrew Text Editor (Scintilla using this)