sizeof

最近实现一个 cache 系统, 要求对 cache 的大小做限制. 但是 JavaScript 没有 sizeof 函数, 咋整? 只能自己实现一个了, js 里:

事实上, ecmaScript 只对 number/string 做了规范, 至于其他类型占用多少内存空间, 无从得知. 我们只能毛估估做个假设吧:

在这些假设的前提下, 找出 string 占用的内存大小是关键的一步, 这就要求搞清楚 utf-16 的编码机制, 扯到 utf 的编码, 就不能绕开字符集 Unicode 了.

Unicode 字符集

字符集是表示字符的一个集合, 比如 ascii/gb2312/big5/unicode 等, 其中 ascii 字符集只包含拉丁字母/常见的标点符号/以及一些控制字符. gb2312 是简体中文的字符集, 除了是 ascii 的超集之外, 还包含了众多的汉字. big5是包含繁体中文的一个字符集合, 用于台湾地区.

如果我们只有 gb2312 字符集, 那将无法显示繁体中文(准确地说, 是计算机无法知道某些二进制表示什么字符. 知道->显示的过程, 还需要字形的配合), 反之亦然. 所以我们的操作系统一般都预置了很多种字符集, 以显示地球上的不同文字. Unicode 是一个超大的字符集, 包含了地球上所以的文字/表情/以及符号. 如果所以人都使用 unicode, 那么计算机里只要装一份字符集就好.

Unicode 把每 2^16 个字符分一个集合, 称为一个平面(plane), 目前一个有 17 个平面. 所以 Unicode 一共可以表示 1114112 个字符, 每个字符都有自己的序号, 从0-1114112, 称之为码点(codepoint), 目前只用了不到 14 万的字符(link). 第一个平面称为基本平面(BMP: Basic Multilingual Plane), 常见的字符都在这个平面, 其他平面也有自己的名称, 如图:

{% asset_img unicode_planes.png %}

字符编码

在多种字符集并行存在的情况下, 如果地球上某处有人给你发了一份文件, 计算机如何知道该用哪种字符集来显示呢?

首先, 字符是人类的符号, 计算机只能认识0/1. 所以对于一个文件, 计算机采用什么字符显示, 那要看这个文件的二进制表示是什么, 不同的字符集有不同的二进制表示, 知道了文件的二进制表示情况, 大概就知道了它用什么字符集.

而字符集到二进制的过程, 称为 encoding, 即字符编码.

ANSI 编码

对于 ASCII 字符集来说, 由于它只有 128 个字符, 所以 7 bit 就能够表示完全了. 但是 ANSI 编码还是用了一个字节来表示一个ascii字符, 因为计算机寻址/指令等原因, 2 的幂次方的数据处理起来更高效. 所以 ascii 编码就相当简单, 每个字节的最高位全是 0. 计算机打开一份文本, 看到所有的字节都是 0 开头, 就用 ascii 字符显示吧, 八九不离十.

UTF-32 编码

unicode 也可以按照这个模式进行编码, 因为 2^21 就能表示完全该字符集中的字符, 用 21 bit 比特就够了, 三个字节24bit绰绰有余. 但如前文提到的, 计算机更合适处理 2 的幂次方的数据, 所以用4个字节对一个 unicode 字符进行编码(如果还想不通, 可以看看我们的计算机体系, 从 8 位计算机, 到 16 位, 32 位. 64位, 为啥没有24位,40位,48位?). 这种 unicode 的编码称为 utf-32 编码, 够简单粗暴但不完美. 采用这种编码的文件, 即使是全部由 ascii 字符组成, 占用的空间是用 ascii 编码的4倍.

所以 utf-32 编码没有被广泛使用.

UTF-16 编码

unicode 还有一个 utf-16 的编码方法, 它不完全定长. 考虑到:

这样可行吗? 还不行, 如果四个字节摆在计算机面前, 那么该解读为2个基本平面的符号还是1个其他平面的符号, 计算机才不会后悔莫及呢? 它没办法解读. 所以聪明的人想到了一个办法:

如果能做到, 那么计算机看到4个字节的时候, 两个字节两个字节地看:

问题变成了: 怎么做这个映射?

和相反的操作一起, 构成了 utf-16 的编码方法, 其中 D800-DBFF 称为 high surrogate, DC00-DFFF 称为 low surrogate, 如图:

{% asset_img bmp.png %}

山寨的可变编码: UTF-B

UTF-16 的编码方法以及比 utf-32 节省很多空间了, 对于纯 ascii 组成的文本来说, 空间占用少了 50%. 但还是不够省. 拉丁文本的占用空间如果能跟 ascii 编码一样就好了, 可能吗? 我们试着构造一个山寨的 UTF-8 编码, 按照华强北的命名规律, 我们的编码方式应该叫 UTF-B

UTF-B 是变长的编码, 一个字符可能用一个字符表示, 也可能用多个字符表示. 因为长度不固定, 所以需要告诉计算机: 当前读到的字节是单独的一个字符, 还是字符的某一部分, 它的其他部分在哪里. 尝试设计如下:

ascii 字符128个, 一个字节就可以表示了. 而且它的最高的bit位是0. 我们灵光一现(别管怎么灵光的好吧): 是不是可以用最高位做文章呢?:

这样有个问题, 一个字节的高位是 11, 那它是可能是2-3个字节的开始, 这就有歧义了. 改进一下, 用 0 把他们区分开:

这么搞貌似没问题了. 后续的这几个字节需要做格式上的规范吗? 文件并不是只能从头开始读的, 如果从文件中间的某个字节开始读, 如果读到的字节是 1100 1010, 那么这个字节一定表示和后续的两个字节组成一个码点吗?

不一定, 它还可能是组成码点的某个中间字节! 为了区分一个字节是火车头还是火车中间车厢, 还需要约定一下: 其他车厢不准长得跟火车头一样! 要不你们统一以 1110 开始吧...到了这一步, 计算机随便读到一个字节, 都能分辨出这个字节的作用了. 现在规则变成了:

这样表示的话还有一部分码点没办法表示, 所以再加一条规则: 四个字节表示一个码点. 非火车头的车厢统一以 11110 开始吧:

就算我们用了1-4个字节表示码点, 还是没能把所有的码点表示完全, 以上编码能表示的码点总数还不到 2^15 个: 2^7 + 2^9 + 2^11 + 2^13 < 2^13 x4 = 2^15. 原因在于, 非火车头的车厢作为载荷的主体, 浪费了太多 bit 来表示他们的身份, 把这部分bit和火车头对调一下, 降低火车头的有效载荷提高整体的有效载荷:

如此我们确定了基本的编码规则, 但还有一些细节需要处理:

UTF-B 的编解码算法

确定了所有的编码规则, 我们确定编码过程, 对于某个码点 c, encode(c):

解码过程, decode(bytes):

如果 const bytes = encode(c) 那么有 c === decode(bytes), 反之亦然

找个具体的例子, 以汉字'你'为例. 编码过程如下:

与之相反的解码过程, 对于三个字节的数据 0xE49BA0:

这么看的话, 我们的 UTF-B 编码应该很完美了. 看看我们实现的和正宗的 UTF-8 一不一样.

查看汉字'ni'的 UTF-8 编码: echo '你' | hexdump, 得到

0000000 e4 bd a0 0a
0000004

最后一个字节是结束符, '你'的 UTF-8 编码为: e4 bd a0, 二进制为: 1110 0100 10 111101 10 100000

除了 hexdump, 也可以用 unibits 来查看字符的编码结果:

{% asset_img unibits.png %}

跟我们的实现有所出入, 看看他的实现.

UTF-8 编码

{% asset_img utf-8.png %}

在真正的 UTF-8 编码里, 汉字'你' 的编码过程如下:

解码过程如下:

我们的 UTF-B 编码和它的区别在于: 为了尽可能多的用尽可能少的字节表示码点, 多了一步偏移量的操作.

表示的码点数目是对的上的, 但是我目前不清楚他们为什么不用满所有的有效 bit? 比如两字节, 2^11 的空间里只使用了后半部分的 1920 个.

可能是为了节省计算吧? (知道原因的读者一定要留言告诉我!)

题外话: Little endian / Big endian / BOM

对于多字节的编码方式, 不同的字节顺序有不同的二进制编码结果. 比如'你'的码点用 32 bit 来表示的话是: 00000000 00000000 01001111 01100000

{% asset_img wiki_be_le.png %}

所以多个字节的编码, 其实都要确定字节序, UTF-32BE/UTF-32LE, UTF-16BE/UTF-16LE:

{% asset_img be_le.png %}

所以计算机知道一个文件的编码还不够, 它还要知道这个编码是 LE 还是 BE. 聪明的人想到一个办法, 在一个文件的前几个字节把这些信息告诉计算机, 这些字节称为 Byte Order Marks (BOM):

{% asset_img BOM.png %}

说好的 sizeof 去哪了

为了 sizeof, 还得再聊聊 UCS-2 编码, UCS-2 编码是一个已经废弃的编码(或者说已经被合并到 UTF-16), 它用两个字节表示码点, 所以只能表示 Unicode 中的基本平面的码点. 按照这篇文章, 很多 JavaScript 引擎, 应该都是用 UTF-16 对字符串进行编码, 但对外的接口却表现得他们是用 USC-2 一样. 比如字符串str = 'a😀', 它明明是两个字符, 码点分别是 0x0061 和 0x1F600, 但是 str.length === 3 // true, 因为笑脸是基本平面以外的码点, 被映射到了 surrogate , 一共占用4个字符, 也就是 2x16. 规范里规定的字符是 16 bit, 好了, 长度是 3 无疑.

不仅 String.length, 大部分字符串的 API 都可能和你预期的结果不一致. 如果一致, 那说明字符串里的字符都是基本平面里的. ES6虽然可以使用 for (let char of str) {} 来正确循环字符串, 但 str.length 为了保持兼容, 还是一个"不准确"的结果, 所以求长度, 只能曲线救国用 Array.from(str).length

话说回来, str.length 的这个特性, 反而让 sizeof 变得简单. 还是以 str = 'a😀' 为例, 如果是 str.length 返回 2, 那么我们还得一个个去判断字符的码点, 基本平面内的码点占用两个字节, 其他平面占用4个字节. 但是 str.length 返回了 3 , 因为它忠于规范(string 是 16bit), 所以 str 的内存占用是 length * 2byte = 16bit*3 = 6 byte.

// fixme: 一下方法如果处理存在环形结构的数据(比如双向链表), 会无法结束导致栈溢出
// fixme: 还很不精确

function sizeof (item) {
  let totalSize = 0
  const helper = (item) => {
    if (Number.isNaN(item) || item === null || item === undefined ) return 1
    if (typeof item === 'number') return 8
    if (typeof item === 'boolean') return 1
    if (typeof item === 'string') return item.length * 2
    if (typeof item === 'function') return item.toString().length * 2
    if (typeof item === 'symbol') return item.toString().length * 2
    if (Object.prototype.toString.call(item) === '[object Map]') {
      return helper(Array.from(item.entries()))
    }
    if (Object.prototype.toString.call(item) === '[object Array]') {
      return item.reduce((sum, cur) => sum + helper(cur), 0)
    }

    return helper(Object.entries(item))
  }
  totalSize += helper(item)
  return totalSize
}