Archive for the ‘Mac OS X’ Category

TRIPLE is More Than DOUBLE Plus One

2017/12/29

TRIPLE 与 DOUBLE 的问题

远在硬件加速的图形系统 ( graphics APIs ) 出现前,double-buffer 已经是流行的动画防闪烁技术,这个名称一直沿用到 OpenGL 之类硬件加速系统上的相似技术。而 Metal 之类低开销图形系统 ( low-overhead graphics APIs ) 的标准运行模式是 triple-buffer。同时看到这两个名称会引出几个问题:

  • 为什么低开销系统采用「triple」,而不是「double」或者「quad」?
  • 在代码里「triple」是如何体现的?
  • 和「double-buffer」相比,「triple」是仅仅多了一个 frame buffer 吗?

深入讨论前先统一几个术语,因为各个图形系统常用不同名称指代相近的概念。CPU-GPU 工作在 client-server 模式。图形系统的驱动 ( driver ) 负责发送 CPU 的 request 给 GPU。发送前 CPU 准备 request 数据的过程叫「encoding」。GPU 执行 request 的过程叫「rendering」。每个 request 携带少量的参数,如各种变换矩阵,叫 parameter buffer。存储 rendering 结果的区域叫 frame buffer。[1] [2] [3] 一个 frame encoding 开始到 rendering 结束这段时间称为「in-flight」状态。图 1 显示了 OpenGL 系统各个过程执行的时间顺序。

图 1  Single In-Flight Frame

为了简化同步机制,OpenGL 系统里一个 frame 的 encoding 要等前一个 frame 的 rendering 结束后才开始。任意时刻最多存在一个 in-flight。这样 CPU 和 GPU 都无法避免空闲等待的状态。如上图所示调用 glFlush() 或者 glutSwapBuffers() 导致 CPU 的 idle 时段。从 encoding 到 rendering 的延时会导致 GPU 的 idle 时段。以这张图为基础,我们讨论下面这个问题:

  • 如果利用 multi-buffer 机制,至少需要几个 buffer 才能缩短空闲时间?Double-buffer 可以吗?特别的,OpenGL 风格的 double-buffer 可以吗?更多的 buffer 有帮助吗,还是反而起负面作用? ( n-buffer 中的 n 取什么值合适?)

BUFFER 与空闲时间

设想一个「naïve solution」:如果有许多个 frame buffer,GPU rendering 时把不同的 frame 写到不同的 frame buffer 里,似乎可以按照图 2 的方式同时执行多个 in-flight 过程。

图 2  Naïve Multiple In-flight Frames

那么来看看这个方案「naïve」在何处。如果在 GPU-bound 应用 [4] 中放任 CPU 无限制地 encoding 下去,CPU 和 GPU 间的处理延时会越来越大。这种延时导致需要暂存的 rendering 结果没有上限。所以一个可行的方案必须有办法让 CPU 适度地停下来等 GPU,这样延时可以控制在常数范围,有限的 buffer 也可以被循环利用。低开销图形系统希望最终达到图 3 的状态,这时系统的处理延时为 d frames,最多有 d+1 个 in-flight。GPU 达到满负荷,同时与 CPU 的延时始终保持在合理范围。

图 3  低开销图形系统的稳定状态

要做到这点,低开销图形系统需要跟踪有多少 frames 处于 in-flight 状态。Metal 利用 command buffer 实现这个机制,其它低开销系统也有类似概念。OpenGL 系统没有类似概念,只能通过调用 glFlush() 或 glutSwapBuffers() 让 CPU 等待 GPU 运行完所有的 requests (图 1)。即使有 multi-buffer,仅支持单个 in-flight 的图形系统只能消除闪烁,并不能减少等待时间。

第二个问题是,parameter buffer 在 encoding 过程中被 CPU 写入,在 rendering 过程中被 GPU 读出。当多个 frame 处于 in-flight 状态时,必须为它们分别分配 parameter buffer,不能重用。否则后来的 encoding 会破坏前面 rendering 过程读出数据。OpenGL 采用的 uniform 方式限制了由同一 shader 处理的所有 frames 共享同一个 parameter buffer。回到之前的问题:「OpenGL 风格的 double-buffer 可以吗?」—— 一般意义上的 double-buffer「有可能」降低空闲等待时间,但是 OpenGL 风格的并不能,因为缺乏跟踪 in-flight 机制和相应的 parameter buffer 分配机制。

SHOW ME THE CODE

现在具体看一下「跟踪 in-flight 状态」的机制在基于 Metal 的代码里的具体实现。下面的两段 code 从 Nuo Model Viewer 的 in-flight 处理简化而来。


// setup n-buffer, n is 3 in most cases

const unsigned int kInFlightBufferCount = n;

...

// in app initialization, _displaySemaphore was
// initialized with re-entry maximal number
// "kInFlightCount"

_displaySemaphore =
    dispatch_semaphore_create(kInFlightBufferCount);

代码段 1  初始化

代码段 1 是应用在初始化时设置变量。常量 kInFlightBufferCount 作为  _displaySemaphore 的初始化参数决定了 in-flight 的最大数,也就是 n-buffer 运行模式的 n。


dispatch_semaphore_wait(_displaySemaphore,
                        DISPATCH_TIME_FOREVER);
id<MTLCommandBuffer> commandBuffer = ...

_inFlightIndex = (_inFlightIndex + 1) % kInFlightCount;

// encoding on the command buffer on the
// "_inFlightIndex"th buffer
...

[commandBuffer commit];
[commandBuffer addCompletedHandler:^
    (id<MTLCommandBuffer> commandBuffer)
    {
        ...
        dispatch_semaphore_signal(_displaySemaphore);
    }];

代码段 2  In-flight 处理

代码段 2 是每个 frame 处理 in-flight 的逻辑。其中 semaphore_wait 和 semaphore_signal 定义的 critical region 正好符合图 3 所示的 in-flight 过程。和传统教科书基于 PV 操作的 critical region 相比,这个 region 有两个特殊性。第一,它不是严格的互斥访问,而是由 _displaySemaphore 指定重入的最大次数。第二,它的起始点和结束点不在同一段 sequential code 中,而是分别在 main thread 与 command buffer complete-handler 中。所以它不是控制不同 thread 的并发访问,而是用 GPU 通知来控制 main thread 的等待,以达到图 3 的效果。绝大多数情况下,Metal 系统的 _displaySemaphore 初始化参数为 3,即 triple-buffer。

其中第 5 行计算当前选择的 buffer 序号。因为运行在 n-buffer 模式,所以用 % 在 kInFlightBufferCount 个 buffer 里依次循环重用。第 11 行调用 commit,表示一个 frame 的所有 encoding 完全结束后才会发出 request 让 GPU 开始 rendering。图 2 和图 3 里那种 GPU 在一个 frame 的 CPU encoding 进行中就开始 rendering 的情况并不会在 Metal 系统中出现 [5]。如图 4 显示了允许三个 in-flight 时 Metal 系统的时序。可以看到由于 commit,延时比图 2 要长。

图 4  Metal 的初始时序

从这段代码也可以看出,Metal 的 n-buffer 中 n 可以任意取值。这是低开销图形系统的一般特点 —— 并不在 APIs 定义中硬性规定 n 的具体值。下面讨论 什么取值能最大地释放系统性能。

TRIPLE 和最优性能

上面的讨论中可以看到,_displaySemaphore 定义的重入次数决定了整个系统运行在 n-buffer 模式。现在讨论 n 的取值对性能的影响。当 n 设置为 5 时 ( quintuple-buffer ) 系统运行如图 5 所示。

图 5  Quintuple-Buffer 的时序

系统在第 10 个 frame 达到稳定状态,延时为四个 frame。除了延时增加之外,还必须准备五套 parameter buffer 和 frame buffer。因此 in-flight 过多有弊无利。如果采取相反的措施,降低 in-flight 个数是否可以减少延时?这时要注意到,在图 4 和图 5 中第一个 frame 的 encoding 和 rendering 之间的延时是 CPU-GPU 作为 client-server 系统的固有延时。从 Apple 文档中摘抄的图 6 大致描述了固有延时的构成。这里「Complete Frame …」可以粗略的看作上文的 rendering 过程。

 

图 6  CPU-GPU 固有延时

虽然 CPU-GPU 的固有延时并不能通过本篇讨论精确得出,但从图 6 和图 5 来考虑,不妨大致假设为每个 frame encoding 时长的 3/4。如果把 in-flight 最大数设置为 2,系统的时序如图 7 所示。

图 7  Metal 风格的 double-buffer 时序

由此可以看出,相对于 OpenGL 系统,Metal 风格的 double-buffer 可以减少一部分空闲等待时间,但是 CPU-GPU 的固有延时决定了 double-buffer 并不能完全消除所有的空闲等待。只有 kInFlightBufferCount 为 3 的 triple-buffer 模式才能达到图 3 和图 4 中 GPU 没有空闲等待的情况。

结论

最后总结一下篇头提出的所有问题。

为什么低开销系统采用「triple」,而不是「double」或者「quad」?

本篇并不能精确证明 triple 在任何情况下都是最优解。但可以分析出,过高的 in-flight 最大数会增加 rendering 延时,过低会导致 GPU 空闲等待。Triple 是针对一般情况的最佳设定。

在代码里「triple」是如何体现的?

通过规定可以重入三次的 semaphore。

和「double-buffer」相比,「triple」是仅仅多了一个 frame buffer 吗?

OpenGL 风格的 double-buffer 只涉及 frame buffer。 低开销图形系统的 triple-buffer 则涉及 frame buffer,parameter buffer 以及基于 semaphore 的 CPU-GPU 同步方式。更确切的说,triple-buffer 应该被称作 triple-in-flight

如果利用 multi-buffer 机制,至少需要几个 buffer 才能缩短空闲时间? Double-buffer 可以吗?特别的,OpenGL 风格的 double-buffer 可以吗?更多的 buffer 有帮助吗,还是反而起负面作用? ( n-buffer 中的 n 取什么值合适?)

采用基于 semaphore 的同步方式,多于一个 in-flight 的系统就可以缩短空闲时间。对于 GPU-bound 应用,通常三个 in-flight 能完全消除等待时间。OpenGL 没有跟踪 in-flight 的能力,其 double-buffer 只能消除闪烁。过多和过少的 in-flight 数目都对性能起负面作用。

脚注:

  1. 术语「encoding」来自于 Metal 系统。OpenGL 里并没有对应的名字。
  2. 术语「parameter buffer」在 OpenGL 里对应 uniform,在 Metal 里是作为 shader function parameter 的 buffer。
  3. 术语「frame buffer」来自于 OpenGL。在 Metal 里对应于用作 rendering target 的 texture。
  4. GPU rendering 的时间大于 CPU encoding 时间。本文只讨论这种情况,对于 CPU-bound 应用请作为读后思考。
  5. OpenGL 系统的 encoding 可以看作每个 request 立即被 commit,而不是一个 frame 的所有 requests 被一次 commit。

GPU 时代的 C-style 字符串 —— 再度绊倒

2017/10/14

写上一篇《GPU 时代的 C-style 字符串》时尽管反复求证,有一点还是搞错了。

Metal 的 fixed-function 部分缺省行为即执行 premultiplication。也就是说,在关闭 blending 时下面的 shader 代码,

会写入:float4(vert.rgb * vert.a, vert.a)

上面描述是错误的。事实是 Metal 的 fixed-function 缺省行为不执行 premultiplication,上面的 shader 代码例子原样写入 float4(vert.r, vert.g, vert.b, vert.a)

说来好笑,上篇 blog 写到一半时的草稿对 fixed-function 的解释本来是正确的。当时我还跑到隔壁的同事办公室大谈了一番。然后晚上 blog 结稿之前做实验晕了头,发布了错误结论,第二天早上又到同事办公室宏论一番。今天再次确认之后,只好第三次去同事那边订正。

所谓「结稿之前做实验」是这样的:Nuo Viewer Model 里有个新加的 screen-space render pass 在关闭 blending 的设置下产生一个 texture,之后其它 render pass 会用到它。我发现如果把它作为 un-premultiplied 形式处理(也就是说再「手工」乘一次 alpha 变成 premultiplied 形式)就会出现「黑边」。而且在 Metal debugger 的 texture viewer 里也看到 RGB 值似乎和 alpha 成正比。于是当晚在 blog 里宣布「Metal 的 fixed-function 部分缺省行为即执行 premultiplication」。

事实上我忽略了一件事:screen-space render pass 打开了 MSAA,在 fragment 边缘进行针对 fragment coverage 的 blending。这时的输出是:fragment 内部区域是 un-premultiplied 形式,边缘是针对 vert.a 和 coverage 的混合计算结果(前者 un-premultiplied,后者 premultiplied)。简而言之,错误的垃圾结果。经过这次教训,「GPU 强制采用 premultiplied 形式情况」的列表补全为:

  • On-screen 显示;
  • 会被 resample;
  • 开启 multi-sample anti-alias (MSAA);
  • (其它未知因素)……

总的来说,尽管 Metal 的 fixed-function 缺省行为不执行 premultiplication,程序员还是要老老实实的保证每一个 fragment shader 都输出 premultiplied 形式 —— 要么在 shader 代码里直接做,要么用 fixed-function blending 去做。否则碰到上面列表的任何一项就会产生垃圾结果。该乘法必须在写入 texture 之前做 —— 是为 pre-multiplication,而不能在 sample texture 的时候做,原因嘛,再看看上面关于 MSAA 的实验就清楚了。

虽然这是一篇更正,但是丝毫无损于上一篇的结论 ——「GPU 时代的 C-style 字符串」。

GPU 时代的 C-style 字符串

2017/10/12

更正 (2017-10-13):如果你依赖本文提供的关于 Metal 的信息,请务必阅读《GPU 时代的 C-style 字符串 —— 再度绊倒》对本文的更正。

由来

曾经有个问题征求答案 ——「计算机系统早期发展的先驱影响最大的决策失误是什么?」很多人赞同以 '\0' 结束的 C-style 字符串。随着计算机解决问题领域的扩展,新领域也会面对各自「早期发展先驱」带来的问题。或许每个时代都有自己的「C-style 字符串」问题。GPU 是过去二十年里「先驱」辈出的领域。从六七年前我的 team 开始接触基于 OpenGL 的产品,到今天自己写 renderer 一年有余,自己和身边的同事反复的被同一个问题绊倒。这个问题 —— alpha premultiplication 应该有资格被称为 GPU 时代的 C-style 字符串。

Alpha 的概念很容易理解。首先,有红绿蓝三原色 (R, G, B channels) 组成颜色。然后加上透明度 (alpha-channel)。透明度本身不会直接显示出来,因为显示器不是透明的,通常的场景也不会在无限远处「透明」。Alpha 是通过对「底色」的修改体现出来的 [1]。如果一个 pixel 颜色为 (r, g, b, a),底色为 (r’, g’, b’) (注意底色没有 alpha),最终结果是:

(r, g, b) * a + (r', g', b') * (1 - a)   [2]

一切概念都非常清晰完美!有那么好的事?C-style 字符串要登场了。

因为「先驱们」发现大多数应用的计算中 (r, g, b) * a 这个式子总是固定出现,并不会出现单独的 (r, g, b) 因子。于是先驱们决定原则上图片(特别是 GPU video memory 中的图片,即 texture)中不再存储最初的 (r, g, b, a),而是存储 (r*a, b*a, g*a, a),以预存储的方式节省乘法运算。这就是 alpha-premultiplied 形式。

到此为止,premultiplication 还只是某些优化情形下的推荐方式,并未上升到 C-style 字符串的影响力。但先驱们又决定,即然在众多时候都需要这个优化,今后 GPU 的 texture sampler,以及显卡的最终 on-screen 显示都假定 pixel 必须是 alpha-premultiplied 形式。

从此混乱开始了。当一个 render pass 的结果有可能被 resample 或者 on-screen 显示时,就必须储存成 premultiplied 形式。否则这个结果经过 GPU 的硬件处理就会产生错误。这导致了很多 shader 中不得不夹杂 premulplied 和 un-premultiplied 两种形式的数据。一份数据是不是 premultiplied 形式没有任何编译期或者运行期的类型信息说明,由于图形编程本身的特点,通过 debugging 来研究难度也很大。开发者只能从静态代码上下文推测。而且 premulitplication 操作可以或者在 fixed-function 部分设置,或者在 shader 中编写代码执行,更增大了通过上下文识别数据形式的难度。

Metal 的实现

说到这里具体谈谈 Metal 的实现。虽然从六七年前开始就被 alpha 相关问题不停绊倒,直到最近才在 Metal 上具体总结了一下。

Metal 的 fixed-function 部分缺省行为即执行 premultiplication。也就是说,在关闭 blending 时下面的 shader 代码,

会写入:float4(vert.rgb * vert.a, vert.a) 。这个行为并不对称,其逆操作 —— texture sampling 并不会自动 divided by alpha [3]。 这导致很多 shader 代码的操作不对称,必须查看 pipeline 的 fixed-function 参数才能理解,是降低 shader 代码清晰度的因素之一。

如果打开 fixed-function blending,写入的数据与 render target 的原有颜色有关。如果用纯黑色 (0, 0, 0, 0) clear 整个 color attachment,并如下设置 color attachment descriptor:

其结果和关闭 blending 的行为一致。上面的 MTLBlendFactorSourceAlpha 决定了对 render 结果执行 premultiplication。如果将其替换为 MTLBlendFactorOne,render 结果就是 un-premultiplied [4]。

未来

这么多年来,只要是显示或存储带透明度的图片,几乎没人能杜绝「黑边」的 bug [5]。而那些中间步骤的还藏有多少看上去不明显的透明度问题,不会有人知道。Premultiplication 绝对当之无愧作为「GPU 时代的 C-style 字符串」。如今在代码里看到越来越多的 std::string,也希望有一天 premultiplication 能从图形图像处理中完全消失。只是不知道当硬件性能充允的时候,已经积累的代码和习惯是否能允许剔除这个遗迹。

脚注:

  1. 如果你听过很多关于 Photoshop 的笑话,那么应该知道「透明底色」是棋盘格的颜色。
  2. 最终结果并没有 alpha-channel,因为为了描述简单没有考虑类似 Photoshop 中 blending group 的概念。归根结底,blending group 只是中间结果而不是最终显示。
  3. 相比之下,Metal 对 sRGB gamma encoded 数据会在 shader 输入输出时进行对称的 linear/delinear 变换。
  4. 当 texture 底色为 (0, 0, 0, 0) 的时候,图中最后两行对 color attachment 的设置并不会有什么作用。
  5. 通常是黑色高透明 pixel 忘记 premultiplication,或是浅色中等透明 pixel 过多进行 premultiplication。

恢复(到更高的)生产力

2017/07/24

任何一次生产环境的调整都是对生产力的打击。

六月初 WWDC 宣布 MacBook Pro 升级之后,决定照去年末计划升级用了四年多的 MacBook Pro 2012。回想起来,从第一次升级到 MacBook Pro 已经快八年了。每次升级都要磕磕绊绊一两周时间。所以四年应该是最短的更新周期,Apple Care 也是必须要买的。

当年买第一台的时候还特地等到 Snow Leopard 正式发布后才去 Apple Store,希望得到预装新 OS 的机器。结果欢乐地得到了 —— 预装 Leopard 的机器和 Snow Leopard 的光盘。

和以前相比这次升级的特殊性在于 hobby 开发转向了 GPU rendering 方面。从上古时期开始这就是兼容性的「玄学」领域。加上 Apple 刚刚推出 Metal for macOS 没多久,今年又急急忙忙拿出 Metal 2,这些对生产力的平滑输出都没有什么帮助。在新机器上配置好 Xcode 8.3.3 之后,发现我的 renderer 根本跑不起来。真是一个沉重的打击!接下来发现如果注释掉关于 shadow map 的代码可以勉强运行,这给了我虚假的希望,以为可以简单修改代码绕过问题。折腾了两天发现只要 shader 中 texture sampling 和分支组合到一定程度就出问题,根本没有简单的规避方法。时间在郁闷中虚耗了三天。最后我决定试一试 beta 版 macOS 上的 Metal 2。

之前从不在主力机器上安装 beta 软件,这次是被逼无奈。我甚至考虑如果还没有改观就退掉这台机器。好在装完 High Sierra beta 2 和 Xcode 9 beta 之后 renderer 能跑起来了。看来 Apple 人手吃紧,为了 beta 版的进度已经顾不上修复稳定版的问题了。不知道手握 MBP 2017 的人现在有多少像我一样被迫紧跟 beta 版动态。对于 Apple 来说我大概已被划入少数派用户了,macOS 开发就是小众,Metal 开发也是小众,Metal for macOS 就是小众的小众。

好景不长,反复观察一天发现只要系统休眠后,Metal 2 性能就会狂降。害得我不停 reboot 系统。几天后总算找到了基本「恢复」生产力到方法。在系统中始终运行一个 renderer app,休眠就不太会触发性能问题。似乎 High Sierra 的 GPU 管理在休眠状态判断上有问题,而保持一个运行状态的 Metal 2 app 可以让 GPU 管理绕过这个问题。

不要谈「正确性」

2016/09/29

很多程序员自嘲「数学不好」。反过来看就是在憧憬基于数学理论写就的程序一定完全正确。其实并非如此。比如说,简单的 parser 可以严格基于有限态自动机和 LL(n) 理论,但写过的人都知道调试起来并不简单,即便充分测试也不能达到 100% 正确。

mbe

另一个例子是 3D renderer。无论是物理真实的 ray tracing 还是简单的 phong model,renderer 就是数学公式的代码实现。最近用 Metal by Example 的例子作为起点写程序。一开始还运行得不错。直到加上摄像位置的变换之后,near/far 平面会切掉在 view volume 里的模型。一开始也没在意,给 near/far 参数随便加上个余量凑合用。混了两个星期后偶然想到 Metal by Example 用的 projection 和 OpenGL 的一模一样,而 Metal 的 depth 范围不同于 OpenGL [1] 。在 Twitter 上向作者确认之后果然是这个问题。Metal by Example 经过了 15 个月的开发,出版也有一年左右。但是这个基本问题一直没有被发现。

软件开发的现状略带讽刺 —— 严格依据数学理论的程序反而缺乏有效的工具来验证其正确性。但这里其实也没什么讽刺性,因为数学本身的理论正确性也并非自动获得。一个新证明的正确性必需要经过其他数学家的人工验证,有时需要历时几年,甚至在最后才发现证明中的错误。数学的正确性是依靠数学界的「社交活动」达成的 [2] 。正如测试是软件开发的「社交活动」。

那么,数学理论是不是对软件质量没有帮助呢?也对也不对。数学理论并不能直接保证正确性,无法帮助发现错误。但是一旦发现了错误,数学理论可以帮助更快的修复软件。当我们在一个复杂的 ad hoc if-else 分支群里发现错误行为之后,很难立刻理清修复方案。而面对上文的 projection 错误,立刻就可以修正错误的参数。我把这种特性称为「可修复性」。可修复性和「正确性」不是一个层面的问题。其实软件开发的很多 best pratice 并非追求「正确性」,而是去提高「可修复性」。例如提高代码的可读性,以及我以前讨论的 MVC 模式的局限和突破,都是追求「可修复性」。经常听到很多团队讨论开发流程和实践的时候以「正确性」作为争论的立脚点,讨论怎么做才能节约测试成本,这样就走偏了。

「可修复性」不是「正确性」。也没有办法直接降低测试成本。但是「可修复性」是软件的一个隐形 spec。当错误被发现的时候,「可修复性」将一切争论局限在实现层面,避免了在设计层面的争论,更不会出现 feature vs. bug 的可笑争吵。「可修复性」还避免了修改中无意引入新的 bug。就目前的软件开发现状,我认为没有任何编程行为能有效提高「正确性」,那些能产生正确代码的程序员也无非是把代码丢给测试团队之前,自己先系统测试一番。一切编程本身的实践,都应该围绕「可修复性」来讨论。一切针对「正确性」的讨论,都应该交给测试领域。

脚注:

  1. Metal 的 canonical view volume 是 2x2x1,它的 z-buffer 范围不超过 [0, 1] 。OpenGL 为 2x2x2 ,z-buffer 范围为 [-1, 1] 。
  2. 当然,类似 Coq 这样的形式验证工具说明有可能改变这样的现状,但是距离实现仍然有一定距离。

Program by Debug

2016/09/10

老手都知道「debugging」是书本很少涉及但是对生产力影响最大的编程手段。但在不断提高自身修养的过程中也听过大师告诫不要「program by debug」,令人时常前思后想不敢动手 coding 。反复调试时充满负罪感。

如果因为一句「不要 program by debug」就坚持敲代码之前要深思熟虑,那就是和自己过不去了。因为人并不擅长在不同层次进行通盘思考。花费很多精力思考的大计划在细节上必然充满逻辑漏洞。所以编程就是先让粗糙的代码在简单输入下勉强运行起来,然后这里紧一下「螺栓」,那里调一下「杠杆」,最终获得一个稳定的系统。所以恰恰就是要「program by debug」。如果重新思考这个问题,重点不在于是否让 debugger 成为 coding 的线索,而在于如何使用从 debugger 得到的信息,不应该用「头疼医头」的方式去修补问题,而是要从 debugger 暴漏出的现象扩展出一般化的问题,寻找一般化的解决方案。

大师的观点一定程度上和工具的发展程度有关。Debugging 是高度依赖工具的手段。工具永远有覆盖不到的地方,所以脱离 debuging 的慎重思考也总有不可替代的地位。不过工具发展之后,要让我们的头脑从工具成熟的领域中解放出来。

五六年前尝试学过 rendering ,还写过几篇《 OpenGL 随想 》,现在看来十分惭愧。除了熟悉基本概念之外,实际的练习都是浅尝辄止。那个时候我的印象是 GPU pipeline 的编程并不像大多数工程可以大量依靠 debugging 。今年公司给了去 SIGGRAPH 2016 的福利。为了不太辜负这次见闻,回来之后打算再进阶一次自己的 rendering 知识。总结一下前几次进阶夭折的原因,有一点在于只用下面这样的简单过程生成的模型。因为无聊而失去动力。所以我想这次要先花些力气让代码直接用上从网上下载的大量模型。

bqhwpgrcyaeokfr-png-large

具体的目标定为 Wavefront OBJ 格式的 viewer。本着 program by debug 的精神,从网上找了几个 OBJ loader 库,然后给它们分别写些简单的测试代码来 debug ,看它们产生的结果是否好理解。然后选中 tinyobjloader 加到 Metal by Example 的例子里直接开始编码。每次 debugging 暴漏的问题的时候,不能只是把当前出错的这一个 OBJ 文件的情况糊弄过去,而是要考虑类似情况如何反映在所有的 OBJ 文件里。用点合理猜测,偶尔去查相关的 OBJ 标准,程序就一步一步的稳定起来。最后把例子一步步的 refactor 成现在的 Nuo Model Viewer

Parsing model 的构建诠释了 program by debug 的作用,但是这毕竟不算 rendering 本身。和几年前相比,GPU debugging 的工具也丰富多了。例如 rendering order 就不用费力猜了。

2016-0908-modelviewer

Core Animation 初探

2012/08/17

尽管在产品中要实现不少动画效果,却还没用过 OS X 的 Core Animation。一方面是因为经常要考虑用一套 code base 兼顾 OS X 和 Windows 两个操作系统。另一方面是习惯了基于 MVC 的手工实现方法 —— 在 model 中加入描述过渡帧的变量,用 timer 定期修改变量并通知 view,view 根据变量绘制过渡帧。不过偶尔模糊地见闻一些对 Core Animation 的褒扬 —— 充分的利用 GPU,释放主线程的压力,iOS 的 graphics 完全转向 Core Animation 等等。所以最近终于抽空看了些 Core Animation 的资料 [1]。

真正阅读资料之前对简介 Core Animation 的优点一直有些疑问。我无法设想与手工 MVC 动画相比 Core Animation 如何进一步压榨 GPU 的效能。在手工 MVC 动画中,虽然控制中间过程的变量需要 CPU 计算,但是这种变量会被设计为最简形式。比如,实现旋转一个矩形的动画时 timer 修改的不会是矩形的四个顶点,而是在 model 中存储旋转角度的变量。在 view 绘制中间帧时,才会根据这个角度计算四个顶点。这时的计算并非主要由 CPU 承担,而是把旋转角度变为旋转矩阵,交给 GPU 担负各个顶点的计算。

Core Animation 文档再次印证了我的一个感觉。当你感觉一个东西表面上被宣称的优点不成立,那么这种感觉很可能是对的。如果这个东西仍然很流行,那么在宣传中肯定遗漏了这个东西的真正优点 [2],并且伴随着一些隐晦的妥协 [3]。Core Animation 的妥协在于,它并不能完全替代手工 MVC 方式的灵活性。手工 MVC 动画中 model 里描述过渡状态的变量和 view 根据这些变量计算显示过渡帧的过程可以自由定义,在 MVC 这一套原则下可以实现任何动画。Core Animation 仅仅实现了有限的预定义动画,如 layer 的旋转,透明度变化,颜色,位移。尽管 Core Animiation 预定义的动画属性相当多,而且有数种组合方式达到无限的组合结果,但是仍然不能覆盖理论上的任何动画。所以它的动画效果是「罐装 (canned)」的。

但「罐装」效果对灵活性的牺牲带来了在表面宣传中未提及的好处 —— transactional。即使是初学者也能很快的实现一个简单的手工 MVC 动画,但是一旦加入复杂的 transaction 要求,即使老手也很为难:如何处理在一个动画播放的过程中用户 cancel 或者 undo 一个操作,或者更加复杂,在动画过程中用户执行引发另一个动画的操作。这要求动画在任意阶段的回退,或者从一个动画效果无缝切换到另一个效果,并保证 view 最终总能正确呈现 model 的稳定状态。通过把动画效果限制在有限的「罐装」组合,Core Animation 在程序员无需干预的情况下自动实现 transaction [4]。

更重要的是,虽然理论上听起来「罐装」效果对灵活性的牺牲很可怕,实际上 99% 的应用只需要「罐装」效果,因此 Core Animation 作出的牺牲其实是几乎无代价的。当然,不排除由于 Core Animation 的流行,一些原本应该更有创意的动画的地方被用平庸的「罐装」效果来应付。但我认为这是很罕见的情形。而且,动画效果已经从早期的 eye candy  变成提供 UI 行为的 clueness 的普遍要素(比如,当前的 view 变化是因为图像旋转还是图像发生了变化 —— 前者显示为图像旋转而后者则是新旧图片的平移切换)。从少数 fancy 操作扩展到几乎所有 view 的变化。动画的一致性 (consistency) 和 least suprise 变得比创意更为重要。

如果抛开 Core Animation 出现的真实历史 (historical accuracy) 来设想一下一个类似 Core Animation 的库是如何在 Apple 这样的公司出现的。它应该不会是自上而下的需求,不会是为了 OS X 的市场而设计的 feature。相反,像 Apple 这样的公司会对内部产品的界面动画有一套详尽的关注细节的指导原则,最初必然是由程序员用手工 MVC 实现,只需要极少创意和极复杂的 transaction 处理。于是一段时间之后程序员们终于把动画效果「罐装」起来,此后原来的指导原则也几乎不再有提及的必要,因为几行代码就能自然地实现,反而是没有动画效果的操作显得不够自然了。这必然是从真实的痛苦中诞生的技术。

脚注:

  1. 看的是 OS X 版本,所以对 iOS 平台的描述仍然不尽明了。
  2. 比如很多场合人们宣称 GPU 的优势在于大规模并行。这当然会引来一些思维敏捷的初学者的疑问 —— 为什么 Intel 们不把 CPU 做得一样并行化。而 GPU 的威力真正来源是它把要处理的数据结构局限在异常简单而且可以完美对齐的方式,并且配以高速的内存总线。最直接的证据就是无论 OpenGL 还是 OpenCL,在可预见的未来都不会支持指针。
  3. 如上 GPU 对数据结构的妥协。
  4. 底层实现上,Core Animation 通过三套 layer tree 实现自己的 MVC 结构来实现 transaction。这同样是由于把问题局限于「罐装」效果才可能做到。Core Animation 自己的 mini-MVC 让 app 的 MVC 架构脱离了动画 transactional 的负担。

开发 Batch Crop

2012/07/16

从 6 月 8 日到今天有一个多月没更新 blog,以前从未拖过这么久。因为这段时间在开发我的第一个准备在 Mac App Store 上发布的应用 —— Batch Crop。前几天终于把 1.0 版提交给 Apple iTunes connect 等待审查(就我的习惯来说,这个应用应该叫 0.6 版,但是 Apple 不允许 beta 版进入 App Store)。目前页面中的截图是正在开发的新版本。

以前作为 one man team 开发软件的经历不是很多。这次经历感受匪浅,想写的东西也不少。无奈不断改进 Batch Crop 的工作完全占用了 day-job 和家庭之外的所有时间。这也让我开始非常敬佩那些既开发自己的产品又撰写 blog 的牛人们。

Text Field 与 Field Editor

2012/06/08

Cocoa 提供了两种文本编辑控件 [1]:NSTextViewNSTextField。从表面上看,前者比后者功能丰富,前者一般用作复杂的文字编辑,后者一般接受简单的数据输入。二者处理 Enter 和 Tab 键的行为不同。NSTextView 的方式和通常的编辑器相同:给编辑内容添加换行或者 tab 字符。
NSTextField 的方式则类似于其它非文本编辑的 Cocoa 控件:Enter 键触发 target action(缺省为终止编辑),Tab 键令焦点移到相邻的下一控件。

有瑕疵的世界观

如果根据表面现象粗浅地猜测,有这么几种可能:

  • 二者是实现完全不同的类,运行时没有协作;
  • NSTextView 是 NSTextField 的子类;
  • NSTextField 是 NSTextView 的封装,对外隐藏后者的高级功能。

实际上这三个猜测都是错误的。查看文档可以排除第二种。另外两种的真伪则要花些功夫来辩明。当然,很多应用界面仅需要 NSTextView 提供的缺省 rich-text 编辑功能以及把 NSTextField 作为简短数据输入方式,所以我们大可以采用第一种假设来开发 90% 的应用。但若需要精细调整文本编辑行为,采用有瑕疵的猜想像是用牛顿力学和以太的概念指导宇宙航行。

以太概念的抛弃

要了解两个类的关系,它们的命名可以作为切入点——其中的「field」是什么意思?在数据库记录、表格或文件格式中一段相对独立的数据经常被称为「field」,所以自然的猜想是 NSTextField 作为简单的数据输入方式其名称中的「field」源于此意。但是 field 还有「现场」、「场所」的意思。

其实在 Cocoa 中提供文本编辑功能的类只有 NSTextView
NSTextField 不是 NSTextView 的封装,它的作用是为实际承担编辑工作的 NSTextView 提供操作「场所」。其名称中「field」的意义不是表格或文件格式意义上的 field。当一个 NSTextField 控件不拥有焦点的时候,它只显示自己存储的文本值 [2],并不和 NSTextView 有任何关系。当它获得焦点时,其所在的窗口会把一个 NSTextView 控件置于其上,并将原来的 NSTextField 对象设置为该 NSTextView 对象的 delegate,真正获取焦点并且成为 first responder 的控件是 NSTextView 对象。在同一窗口中,置于所有 NSTextField 之上的是同一个 NSTextView 对象实例。因为只有一个控件能获得焦点,所以共享单一的 NSTextView 实例没有问题。这个唯一的实例称为「field editor」,即放置在 text field 上的 editor。

Field editor 由窗口负责创建和管理。开发者如果希望实现自己的 field editor,可以重写 (overried 或者 implement) 下面的函数之一:

  • NSWindowfieldEditor:forObject:
  • 窗口的 delegate 的 windowWillReturnFieldEditor:toObject:

在说明 field editor 机制如何导致对 Enter/Tab 的不同处理行为之前,先简单说明一下 Cocoa 对键盘事件的总体处理机制。下图截自《Cocoa Event Handling Guide》,Figure 1-5。

最后一步「Insert as character in view」对于 NSTextView 来说相当于接收到 keyDown: 消息。Enter/Tab 作为 key action 被路径中更早的模块截取 [3],即图中的「Send action message to first responder」。所以 Enter/Tab 事件不会向 field editor 发送 keyDown: 消息,而是分别发送 insertNewLine:insertTab: 消息。

现在回到 NSTextViewNSTextField 对 Enter/Tab 的不同处理。严格的说是非 field editor 的 NSTextView 对象和作为 field editor 的 NSTextView 对象的不同行为。 NSTextView 的 isFieldEditor 属性表示当前对象是否为 field editor。一切行为差异的秘密就在于 insertNewLine: 和 insertTab: 会根据 isFieldEditor 的返回值来决定控件的行为。

问题的解决

有了正确的世界观,就可以自由地对文本编辑行为作出调整。比如,如何让控件在接收到 Enter/Tab 事件的时候始终插入相应的字符而非终止编辑或者切换焦点?可以有以下方案:

  • 始终用 NSTextView,并且保证 isFieldEditor 属性返回 NO
  • 重写窗口 delegate 的
    windowWillReturnFieldEditor:toObject: ,返回 custom field editor。此方案需要创建两个新类:窗口 delegate 和 NSTextView 的子类。后者的 insertNewLine: 和 insertTab: 需要被改写。
  • 让处理 key action 的模块发送 insertNewLineIgnoringFieldEditor: 和
    insertTabIgnoringFieldEditor: 消息给 field editor,保证始终插入换行或 tab 字符。

下面详细说一下如何实现最后一个方案。处理 key action 的模块首先检查拥有焦点的 NSTextField 是否有 delegate。如果有的话会向其发送 control:textView:doCommandBySelector: 消息。重写此函数可以改变发送到 field editor 的消息 [4] [5]。

- (BOOL)control:(NSControl*)control textView:(NSTextView*)fieldEditor
                         doCommandBySelector:(SEL)commandSelector
{
    if (commandSelector == @selector(insertNewline:)) {
        [fieldEditor insertNewlineIgnoringFieldEditor:self];
        return YES;
    } else if (commandSelector == @selector(insertTab:)) {
        [fieldEditor insertTabIgnoringFieldEditor:self];
        return YES;
    }
    return NO;
}

脚注:

  1. 本文混用「控件」和「类」来表示 NSView 的子类。在强调该类的用户界面交互行为的时候偏向于使用「控件」。
  2. 实际上 Cocoa 中的静态 label 也是由 NSTextField 实现,只不过这时它没有获取焦点的能力,不作为 NSTextView 的「field」。
  3.  这个「更早的模块」是 Cocoa 的 key-binding manager。可以参见《Cocoa Event Handling Guide》的 Key Bindings 章节等。
  4. 用 debugger 在其中设置断点查看 call-stack 可以发现更多信息,比如关于 key-binding manager 的信息。
  5. 更多细节可以阅读《Editing Programming Guide》的 Working With Field Editor,以及《Technical Q&A 1454》。

空间化界面

2012/05/14

在论坛社区里有个问题每过段时间就会被提一次:是否有可能出现一种图形化编程方式能完成「传统」方式的所有任务,甚至取代后者的主流地位。知乎的 Rio 在回答中提出像 Lisp 这样语法超级简洁的语言也许可以通过图形化语法树的形式完成图形化编程。从更广的角度来说,自 Steve Jobs 访问 Xerox PARC 之后(甚至更早),软件设计者们一直在挑战一个难题:软件界面应该图形化到何种程度。Apple 在传统 Macintosh 中做到了图形化的极端,甚至去掉了键盘的方向键;在后期的系统以及 OS X 中则向相反方向回退:AppleScript 鼓励普通用户编写脚本,命令行的 Terminal 重新发挥作用。合适的边界在哪里,而编程又在边界的哪边?

问题维度

小学时学习实数用到数轴,中学时学习一元函数用到二维笛卡儿坐标的图形化。足够细心的人能用绘图法能够解决很多选择题。如果配合坐标纸,绘图甚至可以独立解答一部分平面解析几何的题目。更进一步,空间想象力和绘图功力不错的人可以用正交投影绘图来研究二元函数和立体几何。但投影绘图方式只能作为提供思路的辅助工具,无法起到一元函数和平面解析几何的绘图法那种独立解题的作用。作为研究问题的工具,图形化所能胜任的问题维度受限于工具介质的维度。而且这里的图形化严格说来应该称之为「空间化」。由于高维度的问题无法空间化,研究者必须直接操作逻辑符号。

计算机的显示器是二维的,即使它能用各种投影法来显示 3D 内容,指点设备 (pointing device,比如鼠标) 操作界面的方式仍是二维的。所以软件的界面受限于二维。当然,实际要更复杂一些。借助窗口,tab,分割线,甚至于更复杂的 dockable  palette 等等,软件界面是具有层次关系的一组二维空间。但是具有层次关系的二维空间组仍然不是三维空间。

适合图形化界面的问题,是在经过层次划分之后每个层次可以被自然地二维空间化的问题。比如文件管理,文字处理和排版。在 《The Mythical Man-Finger》 中,作者循序渐进的说明了简单的管理音乐文件的问题如何一步步复杂化到远远超越二维空间化的程度,最终必须由命令行来实现。比如「把 iTunes 中随机/最后播放/最常播放的 n 首歌曲同步到其它 app/device」。把这个问题拆借成单独的小问题,很容易分别图形化:

  • 按照随机/最后播放/最常播放排序 —— 排序的空间化;
  • 找到任意数量的歌曲 —— 数量的空间化;
  • 同步到 iPhone —— 位移的空间化。

由于每个问题单独空间化的意义不同,它们的界面往往是分开的。组合到一起成为复合需求之后则难以图形化。这也是为什么一些图形界面应用总体设计的不错,一到了 Import/Export 界面却变成很凌乱的对话框,反而不如像 AppleScript 这样的脚本化功能来的自然。

空间化作为呈现问题的一种方式,是将问题本身空间化,而非空间化问题的另一种表现方式。不能因为一个文字排版软件优美地编排了一个阐述四维空间问题的论文,就说这个软件成功的空间化了这个四维空间问题。同样, 把所有的 Import/Export 选项用下拉列表和 TextEdit 控件并列出来,固然也算可用的界面,但并不优于命令行方式。Rio 关于图形化 Lisp 语法树的设想,以及很多软件通过图形化流程图来尝试图形化编程的方式,都属于这种不成功的空间化。数轴不是把实数的十进制表示空间化,而是把实数本身空间化。二维坐标系不是把一维函数的公式空间化,而是把函数本身空间化。

目前用计算机处理多维度问题的方式主要要是定义一个多维的非空间化表示方式,然后再尽可能的用图形化界面来呈现这种方式。此时的图形化是为了呈现表现方式的符号而不是问题本身。今天我们有支持多 tab 和彩色字符的 Terminal;有支持语法高亮,括号匹配和 block 折叠的代码编辑器,它们是符号化图形界面而不是空间化界面。

空间化与符号化

回到最初的问题。既然早已存在高度图形化的代码编辑器,为什么「图形化编程」的问题会一再被提出?因为提问者和回答者都在潜意识里把「图形化」等同于「空间化」,直觉上对符号化的图形界面并不满意。但是缺乏「空间化/符号化」的分类思维又无法认识到空间化的局限。

为什么「空间化」如此深入人心?我只能猜想,在几百万年的进化中,人类的空间化记忆和认知对生存至关重要,这是人类最熟练的技能。

即使不考虑键盘和指点设备的输入带宽差异(幻想有某种神奇的指点设备能用键盘输入字符的速度操作空间化元素),把逻辑符号生硬的空间化也未必能提高效率。比如说,语法树这个逻辑概念中,每个节点的空间坐标其实是没有意义的。当然,在具体的教学例子和某位程序员的思考过程中,把某个语法树空间化是有用的。但是这更多的是特定例子(对初学者)的呈现和短时间自省的工具,而非一般的交流和存储方式。试想如果把成千上万的语法树空间化表示,光是调整节点的空间布局就需要无谓地耗费多少精力。在长期的知识表示和交流中,语法树的空间信息是正熵而非负熵。

逻辑符号标志着人类中的一部分超越了可能是自然进化赋予的空间化记忆和认知能力,数学(特别是超越三维的问题)和编程语言体现了直接在高维度思考的能力。每个人掌握这种能力的程度不一,有些程序员可以通过默想写出程序,而另一些则需要绘制大量用于自省的草图,。但是无论如何,空间化工具已经不足以解决高维度问题的过程中充当主要角色。人类和工具在相互影响,一方面工具尤其是软件在不断适应人类几百万年的空间化认知习惯,另一方面,能够驾驭高维逻辑工具的人在整个人类中的比重也应该越来越多。