PAC 自动代理配置的性能问题

用 PAC 也有一段时间了，Mac 上是 Shadowsocks 配置的 PAC，iPhone 上是 wifi 下配置的 PAC，服务器端使用 squid，每个 PAC 文件都将近 200kb，从一开始就担心他的性能，最近找到点资料，看来我的担心是多余的。

PAC 文件即 (Proxy auto-con­fig file)，实质上是一个 javascript 脚本。浏览器在连接互联网时会调用其中的 Find­Proxy­For­URL(url, host) 函数，并根据其返回值决定访问特定 url 时的代理设置。

高效匹配的算法

得益于 V8 引擎，手机、平板电脑、电脑处理 javascript 脚本的效率非常高。

处理 ip 段的时候，javascript 脚本可以使用二分搜索等方式降低时间复杂度到 O(logn)

处理域名的时候，javascript 可以使用 has­Own­Prop­erty 的方式将时间复杂度降低到 O(1)。

域名匹配的高效算法

进行高效域名匹配的关键在于使用 has­Own­Prop­erty 方法，这个方法以 O(1)的时间复杂度进行查找。

比较好的算法是从完整的域名开始匹配，随后逐级向上查找，即先尝试匹配”trans­late.google.com”，随后尝试匹配”google.com”，最后匹配”com”。

另外一种思路是从根域开始逐级向下查找，顺序与上面的算法相反。

虽然后者的性能比前者好（在处理白名单，让”cn”域名全部直连时，后者只需查找一次，前者需要循环多次），但是灵活性不如前者（后者无法处理只需要让子域名走代理的情况，北大的网络常常有这种奇异现象，比如 B 站处理登录验证的域名 ac­count.bili­bili.com 需要走代理，但是其他 B 站的域名都不需要走代理，在这种情况下，只能用前者处理）。

IP 段匹配的高效算法

AP­NIC 提供了各国的 IP 地址段信息，这些信息由 IP 地址段起始点和地址段长度组成，比如下面这一条记录：

apnic|CN|ipv4|101.0.0.0|1024|20110414|allocated

CN 代表中国，101.0.0.0 是地址段起始点，1024 是地址段长度。

最高效的算法是这样的：先用二分查找，找出比目标 IP 小的最大的地址段起始点，再求出目标 IP 与这个起始点的距离，最后比较这个距离与地址段长度即可。

IP 地址应当被转换为 10 进制保存，另外地址段长度均为 2 的幂次方，所以可以被转换为幂来保存，并且用右移代替简单的比较大小，最终的公式变为：

if (((目标 IP - 起始 IP) >> 幂次) === 0) {retrun True} else {return False}

所以 PAC 的性能没问题，大胆用吧，不过 PAC 只能代理 http/https 协议，邮件的 IMAP/SMTP 是不行的。不过实际使用中，squid 代理的 SMTP 确实不行，但是 Shadowsocks 代理的 SMTP 是可以的。