聚合国内IT技术精华文章,分享IT技术精华,帮助IT从业人士成长

RmlUI 的 style 缓存

2022-07-28 19:55 浏览: 385288 次 我要评论(0 条) 字号:

我们的游戏引擎的 GameUI 使用的 RmlUI 。我的想法是用成熟的 CSS 来描述 UI 的呈现,借鉴 web 前端开发的方法来制作游戏的 UI 。

但我不想嵌入太复杂的 Web 渲染引擎,而且游戏的需求也会有所不同,所以我选择了轻量的 RmlUI 。同时,为了和游戏的开发语言一致,我们使用 Lua 而不是 javascript 来控制 CSS 。

在使用 RmlUI 的过程中,一开始我们尽量和上游保持一致,修复了不少 Bug ,并合并到了上游。后来发现我们有很多需求和上游不同,需要大刀阔斧的做一些改动,所以就 fork 了一个自己的分支。

最重要的两个改动是:第一,完全实现了 Lua Binding ,因为原有的实现非常低效和复杂,很多接口设计不合理。做大规模的接口变化必须破坏向前兼容,这是我们 fork 分支的主要动机。

第二,废弃了 RmlUI 自己实现的排版模块,换成了 Facebook 维护的 Yoga

迁移到自己的分支上后,我们陆续对 RmlUI 的代码进行了不少重构。

最近,发现了 RmlUI 原有的一个 Bug ,有时修改了一个 css 节点属性后,会影响另一个不相干的节点的属性。仔细研究后,判断这是它固有的设计失误造成的。

我们知道,css 非常灵活,每个节点的属性都可以被很多数据源影响。如果我们不做任何优化,推导一个节点上的属性会是一个相当昂贵的操作。所以,必须对其做一些缓存。

而 RmlUI 的属性缓存算法有一些设计问题,它是根据节点的 C++ 对象指针做缓存索引的。这势必会因为对象的删除重建所影响。(因为内存指针的值有可能重复)且这部分代码实现的非常繁杂,我思考后觉得重新设计和实现会更好。


首先定义问题:

每个节点的属性表其实是一个 kv 对的数组。其中 k 是一个 enum ,范围不大(小于 100 种)且不会重复;v 是一个对象。而这个对象一定可以从文本序列化而来(因为源头的数据都是用文本书写的)。

这些属性表是由若干属性表合成的。合成方式有两种,从预定义的类型中继承以及从 DOM 的父节点继承。后者会受属性是否可以继承所影响,哪些属性可以从父节点继承是一开始就确定好不会改变的。

每个节点最终的属性表会以一种特定的次序从若干属性表合成而来。

如果我们把属性表看作一个对象,那么合成表 A 和 表 B 就能视为 A * B ,其中 * 是合成操作。每个节点上的表都可以看作是一串数据表连续合成操作的结果 A * B * C ....

如果我们要做缓存,就应该缓存任意两个表 A * B 的结果,即可提高性能。


我们可以把属性表分成两类,一类是元素数据表,一类是两张表的合成结果。对于前一类表,由使用者来维护其生命期,而后者可以完全由缓存模块管理。因为一旦缓存失效,使用者都可以想办法重建它们。

我用 64bit ID 来指代属性表(其中奇数用来指代数据表,偶数用来指代合成表),如果数据表被释放,或合成表从缓存中消失,ID 不会回收,这样,我们很容易知道哪些 ID 还是有效的,哪些已经无效。

至于属性表的内容,可以额外再做一层 Cache ,对它们 Interning 。相同内容的属性表内部其实指向同一份数据。

对于合成表,一开始只用记住引用的是哪两张表,合成操作可以推迟到最后的求值之前。如果有源头表改变,那么需要清理之前的合成结果。


我在实现以上想法的时候,专门思考了内部的数据结构该如何设计更好。其中有点意思的是关于合成表的 Cache 的结构。

所有的合成表都是由 Cache 管理的,用户不复杂它们的生命期。即,如果你计算 A * B = C ,那么 C 的生命期是不用自己管理,但做(弱)引用。既然是 Cache 管理,就有失效的时候。因为每个节点上的表都是一系列表联合作用的结果,所以当结果失效后,用户直接把合成过程重新做一遍即可。这个过程可能很长,我们需要尽量 Cache 中间变量。

合成表首先应由一个 LRU 队列所管理。我直接使用了一个固定大小(4095)的数组,内部用双向链表串起来。这样,对任何一张表求职,都可以方便的把它调整到队列的最前面。

然后,我们需要两种途径快速索引 LRU 队列中的对象。从 ID 索引,以及从两个 ID 的组合索引。即,如果 A * B = C 计算过,那么从 (A, B) 可以快速索引到已经创建过的对象 C 。

每张索引表我采用一个 8191 大小的数组作 hash 表。它的大小比 Cache 大一倍,所以几乎不应该碰撞。但碰撞从理论上无法避免,在解决碰撞冲突上,我的设计比较特殊,既不是开散列表,也不算闭散列表。

我用 64bit 为一个 slot 的大小。因为原始数据是 4095 ,也就是 12 bits ,这个 slot 可以放下 5 个索引值,也就是说,理论上,最多可以碰撞 5 次。如果某个 hash 值真的碰撞了 5 次(非常罕见),那么就需要遍历整个 LRU 队列查找是否有第 6 个值。

附代码:https://github.com/cloudwu/stylecache



网友评论已有0条评论, 我也要评论

发表评论

*

* (保密)

Ctrl+Enter 快捷回复