打开网易新闻 查看精彩图片
文本排版有个老毛病：找换行点得一个字符一个字符往前蹭，算完宽度超了再回头。O(n)的复杂度，长文档里每行都这么来一遍，再加上Canvas的measureText每次返回新对象，GC压力直接拉满。
打开网易新闻 查看精彩图片
有人把这个流程彻底拆了。做法是预跑一遍前缀和数组，把累积宽度存成Float64Array。之后任意子串宽度变成两次查表相减，O(1)搞定。找换行点转成「找最大的end使得前缀和不超过目标值」，数组单调递增，直接上二分搜索。
打开网易新闻 查看精彩图片
作者在自己的ZeroText引擎里落地了这个方案：1万次字符的文档，500行换行，传统做法要扫500万次字符。新方案一次线性建表，加500次二分搜索，每次约13步，总共6500次比较。
唯一的障碍是那个Float64Array的分配。作者用了arena池化策略：预申请8192长度的数组，cursor归零即重置，不触发GC。整套下来零分配、O(log n) per line。
作者在代码注释里写得很直白：「This is O(n) per line. For a 10,000-character document with 500 lines, you're touching every character at least once per layout.」——而优化后，同样的文档，CPU cycles直接砍到千分之一量级。
热门跟贴