Solrex | 边际效应 - 杨文博的个人博客 - 页码 2

Google Search 淘气三千问: Q6

Q6: Google 为站点设计了哪些特征？

在 Google ContentWarehouse API 中有很多字段以 nsr 开头，有人说它代表 Neural Search Ranking，我觉得这种说法不对，因为 nsrDataProto 字段的注释是 Stripped site-level signals：

GoogleApi.ContentWarehouse.V1.Model.PerDocData

* nsrDataProto (type: GoogleApi.ContentWarehouse.V1.Model.QualityNsrNsrData.t, default: nil) - Stripped site-level signals, not present in the explicit nsr_* fields, nor compressed_quality_signals.

说明 NSR 应该是站点信号，考虑到 QualityNsrNsrData 中还有一个 nsr 字段，我猜测应该是 New Site Rank，或者 Normalized Site Rank。也许这个字段以前只是一个简单的代表站点质量的信号，后来扩展成了一系列信号的组合，但是沿用了 nsr 这个前缀。

其中字段注释非常简单，这里我尝试把他们汇编并且扩展解读一下，看看 Google 的站点特征体系都包括哪些。

首先要解释一点，Nsr 虽然是站点信号，但是它的信号汇聚粒度并不全是站点范围，而是有个 sitechunk 的概念。我猜测 sitechunk 可能会代表一个子域，或者一个比较关键的路径前缀，比如一个网站有新闻、博客或者论坛，那就会有不同的 sitechunk。这样允许 Google 针对同一个域名下的不同的频道、标签做不同的分析。所以下面讨论到所有的站点信号，都应该理解成是 sitechunk 信号。

在 QualityNsrNsrData 中，有以下这些特征：

smallPersonalSite：为个人博客小站提权的分数。我一直觉得谷歌对博客网站很友好，果然在站点特征体系中有专门的提权打分。
siteAutopilotScore：如果一个网站的内容都是自动生成的，它会被称为是一个 Autopilot Website。这个分数是描述这个站点下所有页面自动生成方面评分的一个汇总值。
isVideoFocusedSite：如果站点有超过一半的页面是视频播放页面，而且它又不是一些知名的视频网站，那么这个特征就是 true。
ugcScore：与上面分数相似，可能是这个站点每个页面是否为 UGC 内容的评分的一个汇总值。
videoScore：与 ugcScore 相似，可能是这个站点每个页面是否为视频播放页的评分的汇总。
shoppingScore：与 ugcScore 相似，可能是这个站点每个页面是否为商品购买页的评分的汇总。
localityScore: 与 ugcScore 相似，可能是这个站点每个页面是否为 LBS 服务页的评分的汇总，不过这里提到了一个叫做 LocalAuthority 的模块/策略，希望以后能弄懂它。
articleScoreV2: 与 ugcScore 相似，可能是这个站点每个页面是否为文章页的评分的汇总。
healthScore: 与 ugcScore 相似，可能是这个站点每个页面是否为医疗健康页的评分的汇总。
ymylNewsV2Score：无注释，YMYL 是 Your Money Your Life 的缩写，这里可能是指这个站点每个页面是否为敏感（健康、金融相关的）新闻页的评分的汇总。
clutterScore: 判断站点是否加载了很多乱七八糟的内容，比如加载了很多不同来源的广告之类。
clutterScores: 带版本的 clutterScore。
racterScores: 站点级别 AGC 分类打分；
titlematchScore：大概是这个网站每个网页的标题，能匹配上多少 Google Query 的一个综合评分；
siteQualityStddevs: 站点质量标准差，从名字判断，可能来自于站点所有网页的站点质量得分的统计。从这些方差指标可以看出，Google 很在乎站点内容的一致性，可能对页面质量参差不齐的站点有打压。
chromeInTotal：站点级别的 Chrome 访问量；
impressions：站点在 Google 搜索结果中的展现次数；
chardEncoded: 有人说 chard 代表 CHrome AveRage Duration，站点平均停留时间，我本来猜测可能是 CHrome Average Returning Days，或者 CHrome Average Retention Data。核心就是我觉得这是一个留存指标，留存比时长更能体现网站的受欢迎程度。但注释中又说它是 site quality predictor based on content，所以也许我的理解是错的，也许 c 是 Content？但是 hard 是什么，我实在猜不出来了。
chardVariance：站点（首页） chard 的方差。
chardScoreEncoded: 站点中所有页面的 chard 得分；
chardScoreVariance：站点所有页面 chard 得分的方差。
nsrVariance: 站点首页 nsr 与站点所有页面质量均值的差；
siteQualityStddev: 站点所有页面质量的方差，与 nsrVariance 不同，它衡量的是页面之间的方差；
tofu: 与 chard 一样，都是基于 content 算出来的一个得分。tofu 是豆腐块的意思，在网页里可能代表了页面内有多少个豆腐块区域，或者有多少个豆腐块广告。
pnavClicks：PNAV 大概是指 Primary Navigation，即站点的主要导航链接。这个值是对主要导航链接点击数的一个分母，可能在某个地方记录了这个站点每个导航链接的点击数，这样就能算出来哪些导航更受欢迎，也许是用在搜索结果页中展示站点的关键导航上；
pnav: 一个分位值，可能是主要导航链接占页面链接数比例？
vlq: 视频低质量模型的打分，猜测 LQ 代表 Low Quality。
vlqNsr: 针对低质量视频站点设计的一个额外的 nsr 打分，有可能是为了避免这些站点 nsr 得分过低，导致一些用户需求不满足（例如某类视频）。
siteLinkOut: 这个站点所有外链的平均得分；
siteLinkIn: 这个站点所有内链（反向链入的页面）的平均得分；
siteChunkSource: sitechunk 来源，可能是记录怎么分的 chunk;
spambrainLavcScores：这个没有注释，看起来是 Google 有一个 spambrain，会给站点一个 Lavc 分数，应该表示网站是否有 spam 行为的打分；
sitePr：站点的 PageRank。
nsr: 也许是最原始的 Normalized Site Rank，用一个分值代表站点质量。
versionedData: 实验版本的 nsr 值，当算法升级后 nsr 计算逻辑与以前不同时，先拿它用来做实验；
priorAdjustedNsr: 先验调整 nsr，用于判断当前站点的 nsr 在它所属的 slice 里比平均 nsr 高还是低；
ketoVersionedData: 带版本的 keto 数据，包括站点得分和站点得分在所有站点中的分位值。keto 可能代表了一个策略，含义未知。
nsrOverrideBid: 用来干预 nsr，当它的值提供并且大于 0.001 时，直接覆盖掉 nsr。也就是说可以通过人工干预调高或者调低某个站点的 nsr。
nsrEpoch: nsr 最早的获取时间；
siteChunk: nsr 对应的主 sitechunk，即分析出来的 sitechunk 对应的文档 URL；但文档中提到在一些稀有情况下，它可能基于网页中的一个标记。我猜测像一些 Single Page Application，URL 全部使用 # 页内标记，这种情况下只能使用页内标记来标记 sitechunk。
secondarySiteChunk: nsr 对应的二级 sitechunk，如果存在的话，划分比 sitechunk 粒度更细。
i18nBucket: 属于哪（几）种语言，这是一个 int 值，也许会是一个 bitmap，可以把站点放入多个语言桶中。
language: 站点的语言，暂不清楚与 i18nBucket 的差异，因为它也是一个 int 值。
isCovidLocalAuthority: 是否为 Covid 本地官方网站，也许是在疫情期间对官方网站消息的提权；
isElectionAuthority: 是否为（美国）选举相关的官方网站；
directFrac: 无注释，我猜测是 Chrome 输入 URL 直接访问的 PV 占所有访问量的占比。
site2vecEmbedding: 看起来像是将上面的每个站点 nsr 特征，综合起来表达成了一个稀疏的 embedding，可能是 one-hot 编码那种，也可能是稀疏模型编码；
site2vecEmbeddingEncoded：这里是一个压缩版本的 embedding，主要用于 SuperRoot。
nsrdataFromFallbackPatternKey: 如果为真，代表以上的 nsr 特征都来自于其它站点；
url：站点的 URL；
host: 站点的域名或者主机名；
clusterId：站点所属站群的 ID，被一个叫做 Tundra 的生态项目所使用，这个项目在文档中也出现过多次，希望后面能弄清楚它的含义。站群一般是指页面互相之间有链接的一批站点，会被用来做 SEO 提升 pagerank，看起来 Google 对这种行为是有识别的。
clusterUplift: 与上面提到的 Tundra 项目有关，主要看站群是不是小站，是不是本地站，可能是用于站点的提、降权；
metadata: 记录了一些在不同系统里查找 nsr 数据的 key，或者一些数据的生成时间。

Google Search 淘气三千问：Q1～Q5

前言

两个多月前（2024年5月27日），Google 的一份名为 GoogleApi.ContentWarehouse 的 API 文档受到 SEO 圈的关注，由于这份文档的内容和 Google Search 副总裁 Pandu Nayak 在 2023 年美国司法部（DOJ）起诉 Google 的案件中的证词和 Google 的一些专利高度一致，因此其真实性被广泛认可。

后续有媒体称 Google 发言人回应了文档泄露的问题（没有承认、也没有否认）：

A Google spokesperson sent us the following statement:

“We would caution against making inaccurate assumptions about Search based on out-of-context, outdated, or incomplete information. We’ve shared extensive information about how Search works and the types of factors that our systems weigh, while also working to protect the integrity of our results from manipulation.”

此前大部分讨论仅限于猜测 API 文档中的各种信号在排名算法中的作用，以及对谷歌是否在排名算法上欺骗了大家。很少人意识到，这篇 2500 页的文档可以作为以往 Google 公开论文的补充，一本叫做《如何构建一个世界级（成功的）搜索引擎》的武功秘籍撕下来的几页。

而偏偏我对这本武功秘籍非常好奇，试图在这几页上再加一些批注，就有了《Google Search 淘气三千问》这个系列。这个系列会有几篇文章，我不知道，主要看我能想到多少问题。

为什么叫“淘气三千问”这个名字？可以把它看成是一种传承吧，懂的都懂，不懂的也不影响阅读。

为避免误导读者，这个系列所有的回答里，来自公开信息的我都会标注来源，没有标注来源的，你可以认为是 inaccurate assumptions about Search based on out-of-context, outdated, or incomplete information。当未来有了更新的信息，我有可能回到博客来更新这些 assumptions（公众号文章无法更新）。

如果你有新信息可以给我，或者纠正文中的错误，欢迎评论或者到公众号“边际效应”私信，谢谢！

Q1: Google 的索引分了几层（Tier）？依据什么？

Google 在 2012 年的论文《Indexing the World Wide Web: The Journey So Far 》中提到产业实践中大规模索引都是会分成多个桶（tier），一般按照更新频率来分：

The way we have described search indices so far makes a huge assumption: there will be a single unified index of the entire web. If this assumption was to be held, every single time we re-crawled and re-indexed a small set of fast-changing pages, we would have to re-compress every posting list for the web and push out a new web index. Re-compressing the entire index is not only time consuming, it is downright wasteful. Why can we not have multiple indices -- bucketed by rate of refreshing? We can and that is what is standard industry practice. Three commonly used buckets are:

1. The large, rarely-refreshing pages index
2. The small, ever-refreshing pages index
3. The dynamic real-time/news pages index

...

Another feature that can be built into such a multi-tiered index structure is a waterfall approach. Pages discovered in one tier can be passed down to the next tier over time.

在 Google ContentWarehouse API 里有这样一段：

GoogleApi.ContentWarehouse.V1.Model.PerDocData

* scaledSelectionTierRank (type: integer(), default: nil) - Selection tier rank is a language normalized score ranging from 0-32767 over the serving tier (Base, Zeppelins, Landfills) for this document. This is converted back to fractional position within the index tier by scaled_selection_tier_rank/32767.

可以看到，Google 仍然是把索引分了 3 层，现在我们有了它们的名字，分别是：Base（基础）、Zeppelins（飞艇）和 Landfills（垃圾填埋场）。在每一层之内，scaledSelectionTierRank 这一归一化分数决定了它所在位置的分位数。分位数最大值是 32767，猜测也许是 Google 在索引存储里只给它留了 15 bits（2^15=32768）。

但从索引分层的名字来看，这三层并不（全）是按照时效性分的，至少第三层，看着是按照文档质量分的。因为你把文档放到“垃圾填埋场”中，大概率因为它的质量较差而不是不再更新。那么 scaledSelectionTierRank 也许就代表了层内的文档质量等级。

网友 avanua 对这三层的命名提供了一个解读，我觉得非常合理，因为我一直困惑第二层为什么叫做 Zeppelins：

我觉得 Tier 命名和质量无关，可能只是用来描绘更新频率：
Zeppelins 在气流中起起伏伏
Base
Landfills 几乎不会再翻动，上下层叠关系是固定的

Q2: Tier 内的 scaledSelectionTierRank 有什么作用？

在《Indexing the World Wide Web: The Journey So Far》中提到，在倒排拉链中最好按照文档实际的影响力对文档列表进行排序。如果仅仅是这样，那么只需要知道文档 0 比文档 10000 更重要即可，那么额外记录一个打分的目的，其实是可以让这个分数参与排序过程。文档在某个 Query 下的得分，是文档影响力得分乘以文档在 Query-term 下的权重。

Since it made sense to order the posting lists by decreasing term frequency, it makes even more sense to order them by their actual impact. Then all that remains is to multiply each posting value by the respective query term weight, and then rank the documents. Storing pre-computed floating-point document scores is not a good idea, however, since they cannot be compressed as well as integers. Also, unlike repeated frequencies, we can no longer cluster exact scores together. In order to retain compression, the impact scores are quantized instead, storing one of a small number of distinct values in the index.

从上文中有理由认为，scaledSelectionTierRank 就是文中提到的量化以后的文档影响力得分，量化就是将其归一化到 32768 个分档之中。

Q3: Google 搜索系统主要分成几个部分？

通过 API 和其它公开文档，目前我能够分析出来的搜索系统组成部分有以下这些。随着阅读的深入，可能还会有新的部分加进来。

爬虫系统：Trawler

在 Google ContentWarehouse API 中有一系列 API 以 Trawler 为前缀，并且从上下文中看出来 Trawler 是一个实体系统并且有一个研发团队。

GoogleApi.ContentWarehouse.V1.Model.TrawlerCrawlTimes
GoogleApi.ContentWarehouse.V1.Model.TrawlerFetchReplyData
GoogleApi.ContentWarehouse.V1.Model.TrawlerHostBucketData

* TotalCapacityQps (type: number(), default: nil) - The following four fields attempt to make things simpler for clients to estimate available capacity. They are not populated yet as of 2013/08/21. Even after they are populated, they may change. So talk to trawler-dev@ before you use the fields. Total qps for this hostid

去重系统：WebMirror

在 Google ContentWarehouse API 里有这样一段：

GoogleApi.ContentWarehouse.V1.Model.CompositeDocAlternateName

Alternate names are some urls that we would like to associate with documents in addition to canonicals. Sometimes we may want to serve these alternatenames instead of canonicals. Alternames in CompositeDoc should come from WebMirror pipeline.

每个 CompositeDoc 都有一些替代的 URL，这些 URL 来自 WebMirror 流水线，那么 WebMirror 应该是识别重复文档的一套系统。

离线索引构建系统：Segindexer + Alexandria

在 Google ContentWarehouse API 里有这样一段：

GoogleApi.ContentWarehouse.V1.Model.AnchorsAnchor

* sourceType (type: integer(), default: nil) - ... In the docjoins built by the indexing pipeline (Alexandria), ...

所以 Alexandria 应该是建库系统。而 Segindexer 和 Alexandria 曾经并行出现过：

GoogleApi.ContentWarehouse.V1.Model.ClassifierPornClassifierData

* imageBasedDetectionDone (type: boolean(), default: nil) - Records whether the image linker is run already. This is only used for Alexandria but NOT for Segindexer.

考虑到关键的表示原始文档内容的 compositedoc.proto 在 Segindexer 目录下：

GoogleApi.ContentWarehouse.V1.Model.NlpSaftDocument

* bylineDate (type: String.t, default: nil) - Document's byline date, if available: this is the date that will be shown in the snippets in web search results. It is stored as the number of seconds since epoch. See segindexer/compositedoc.proto

从名字和上述信息有理由怀疑 Segindexer 是在 Alexandria 之前，决定了索引分层，或者分 vertical 的一个分类模块。

在线索引服务系统：Mustang 和 TeraGoogle

在《Indexing the World Wide Web: The Journey So Far》中我们知道，TeraGoogle 是 Google 在 2005 年实现的一套 large disk-based index 服务系统。而在 Google ContentWarehouse API 里有这样一段：

GoogleApi.ContentWarehouse.V1.Model.CompressedQualitySignals

A message containing per doc signals that are compressed and included in Mustang and TeraGoogle.

这里将 Mustang 和 TeraGoogle 并列，有理由认为 Mustang 是 2005 年之后 Google 开发的一套替代或者部分替代 TeraGoogle 的在线索引服务系统。

实时索引服务系统：Hivemind（muppet）

在 Realtime Boost 这篇文档中有一张图，揭示了一个新网页进入索引的过程，其中实时索引的系统叫做 Hivemind。但 Hivemind 应该是个集群名，实际的索引系统方案可能是叫做 muppet。因为在 RealtimeBoost Events - DesignDoc 这篇文档中也提到了一个用 muppet 支持的系统，叫做 ModelT，这是一个索引实时事件的索引系统。

实时索引的建库系统可能与非实时索引不同，叫做 Union。

查询汇聚系统：SuperRoot

在 Google ContentWarehouse API 中多次出现 SuperRoot 这一模块，而在 Jeff Dean 2009 年 WSDM 的《Challenges in Building Large-Scale Information Retrieval Systems》分享第 64 页，SuperRoot 被描述为聚合 Web、Images、Local、News、Video、Blogs 和 Books 所有检索子系统的汇聚模块，这个定位也许没有变。

Query 改写模块：QRewrite

在 RealtimeBoost Events - DesignDoc 这篇文档中说：

Currently in production RealtimeBoostServlet runs in QRewrite detects spikes on news documents published that match the SQuery (including syns). It does so by issuing one or two RPCs to Realtime-Hivemind.

The RealtimeBoostResponse containing the Spike is sent down to Superroot in the QRewrite response and it is currently used by a few Search features (such as TopStories) to trigger faster and rank fresher documents for queries that are spiking for a given news event.

所以 QRewrite 是会被 SuperRoot 调用的一个 Query 改写模块，它会将用户实际发起的搜索 Query 改写成 SQuery，S 可能是代表 Superroot。而到真正发起检索时，会进一步转成检索 Query，比如发给 muppet 的 Query 叫做 MQuery。

摘要模块：SnippetBrain

在 Google ContentWarehouse API 里有这样一段：

GoogleApi.ContentWarehouse.V1.Model.MustangReposWwwSnippetsSnippetsRanklabFeatures

* displaySnippet (type: GoogleApi.ContentWarehouse.V1.Model.QualityPreviewRanklabSnippet.t, default: nil) - Snippet features for the final chosen snippet. This field is firstly populated by Muppet, and then overwriten by Superroot if SnippetBrain is triggered.

看起来 SnippetBrain 是一个可选的摘要生成模块。

入口服务：GWS

Google Web Server，这个大家都知道，还有 Wikipedia 词条。

Q4: TeraGoogle 是怎样一套系统？

根据论文《Indexing the World Wide Web: The Journey So Far》和专利《US7536408B2: Phrase-based indexing in an information retrieval system》，TeraGoogle 应该有以下几个属性：

Disk-based Index：索引存储在磁盘上，在需要的时候读入到内存中，而且往往不需要全部读入，针对重要的文档有一些优化；
Phrase-based Indexing：构建索引的时候不仅仅有 term 索引，还会建设多 term 的短语索引，这样索引库里会有更多的倒排链；
Document-Partitioned Index：将索引分 Shard 的时候，按照文档进行分片，即同一批文档的所有拉链放在同一个 Shard 上，这样每个 Shard 上有所有的拉链，查询在一个节点内即可完成。在论文中只对比了 Document-Partitioned 和 Term-Partitioned 二者的差异，在 Jeff Dean 2009 年 WSDM 的《Challenges in Building Large-Scale Information Retrieval Systems》分享第 17 页确认了 Google 的选择。

Q5: Google 的文档是什么概念？

从 Google ContentWarehouse API 里：

GoogleApi.ContentWarehouse.V1.Model.CompositeDoc
Protocol record used for collecting together all information about a document.

可以看到 CompositeDoc 是在系统里非常重要的概念，它定义了一个文档的所有信息。在它的所有字段中我们发现，url 又是一个可选的字段，这也就是说，文档并不一定需要是一个网页。像 localinfo，看起来就像是一个 POI 信息。也就是说在 Google 的系统里，不一定只有网页索引，可能每个 POI 点、图片、商品也是一种文档，所以它使用 CompositeDoc (复合文档) 而不是 WebPage 作为整个系统里对文档的刻画。

估值最高的 AI 搜索独角兽 Perplexity 使用倒排索引做 RAG

3 月份我曾写了一篇博客《在 LLM 时代我们是否还需要倒排索引？》，探讨了在向量数据库崛起的情况下倒排索引仍然存在的价值。

也许仍然有人对传统搜索技术弃如敝履，但前几天我正好看到一个 Lex Fridman 对 Perplexity CEO Aravind Srinivas 的采访，他表示 Perplexity 仍然使用（可能不是仅使用）倒排索引和 BM25 传统算法进行全网搜索。作为估值 30 亿美元的 AI 搜索独角兽公司，在全网搜索上却也选择了倒排索引，而且访谈中非常强调倒排的重要性，这应该算是印证了我的观点吧。

他的这些思考对我也有一些启发，为了保持互联网的记忆，我将这些相关节选的原文和翻译记录如下：

Aravind Srinivas 2024年6月20日采访节选

这个 Podcast 有 3 个小时，可以从 2:03:52 开始看。

Lex Fridman (02:03:52)

这是一个通过（将内容）嵌入到某种向量空间实现的完全的机器学习系统吗？
Is that a fully machine learning system with embedding into some kind of vector space?

Aravind Srinivas (02:03:57)

它并不是纯粹的向量空间。并不是说内容一旦被获取，就会有某种 BERT 模型在所有内容上运行并将其放入一个巨大的向量数据库中进行检索。
It’s not purely vector space. It’s not like once the content is fetched, there is some BERT model that runs on all of it and puts it into a big, gigantic vector database which you retrieve from.

这并不是那样的，因为将网页的所有知识打包到一个向量空间表示中是非常困难的。首先，向量嵌入在处理文本时并没有想象中的那么神奇。理解一个文档是否与一个特定检索词相关非常困难。它应该是与检索词中的人物有关，还是与检索词中的特定事件有关，更或者它是基于对检索词更深层次的理解，使得检索词可以应用到另外一个人物，他也需要被检索到？什么才是（向量）表示应该捕捉的内容？大家可能会不断争论。而让这些向量嵌入具有不同维度，彼此解耦并捕捉不同语义是非常困难的。
It’s not like that, because packing all the knowledge about a webpage into one vector space representation is very, very difficult. First of all, vector embeddings are not magically working for text. It’s very hard to understand what’s a relevant document to a particular query. Should it be about the individual in the query or should it be about the specific event in the query or should it be at a deeper level about the meaning of that query, such that the same meaning applying to a different individual should also be retrieved? You can keep arguing. What should a representation really capture? And it’s very hard to make these vector embeddings have different dimensions, be disentangled from each other, and capturing different semantics.

顺便说一句，这只是排序部分的内容。还有索引部分——假设你有一些处理后的 URL，排序模块会基于你提问的检索词，从索引中召回相关的文档和一些打分。这就是为什么，当你的索引中有数十亿个页面，而你只需要前 K 个结果时，你必须依赖近似算法来获取这些前 K 个结果。
This is the ranking part, by the way. There’s the indexing part, assuming you have a post-process version for URL, and then there’s a ranking part that, depending on the query you ask, fetches the relevant documents from the index and some kind of score. And that’s where, when you have billions of pages in your index and you only want the top K, you have to rely on approximate algorithms to get you the top K.

Lex Fridman (02:05:25)

所以这就是排序，但是将页面转换为可以存储在向量数据库中的内容，这一步似乎非常困难。
So that’s the ranking, but that step of converting a page into something that could be stored in a vector database, it just seems really difficult.

Aravind Srinivas (02:05:38)

它并不必须全存在向量数据库中。你可以使用其他数据结构和其他形式的传统检索。有一种算法叫做 BM25，它正是为此设计的，是 TF-IDF 的一个更复杂的版本。TF-IDF 是词频乘以逆文档频率，是一种非常老派的信息检索系统，实际上即使在今天也仍然非常有效。BM25 是它的一个更复杂的版本，仍然在许多排名中击败大多数嵌入。当 OpenAI 发布他们的嵌入时，围绕它有一些争议，因为在许多检索基准测试中，它甚至没有击败 BM25，这并不是因为他们做得不好，而是因为 BM25 太好了。这就是为什么仅靠纯粹的嵌入和向量空间并不能解决搜索问题。你需要传统的基于词项的检索，你需要某种基于 NGram 的检索。
It doesn’t always have to be stored entirely in vector databases. There are other data structures you can use and other forms of traditional retrieval that you can use. There is an algorithm called BM25 precisely for this, which is a more sophisticated version of TF-IDF. TF-IDF is term frequency times inverse document frequency, a very old-school information retrieval system that just works actually really well even today. And BM25 is a more sophisticated version of that, that is still beating most embeddings on ranking. When OpenAI released their embeddings, there was some controversy around it because it wasn’t even beating BM25 on many retrieval benchmarks, not because they didn’t do a good job. BM25 is so good. So this is why just pure embeddings and vector spaces are not going to solve the search problem. You need the traditional term-based retrieval. You need some kind of NGram-based retrieval.

Aravind Srinivas 2023年12月14日采访节选

其实在去年 Unsupervised Learning 的 Jacob Ephron 采访 Aravind Srinivas 时，他也有过类似的表述，但是没有像最新一次采访那样强调倒排的重要性。这个 Podcast 也很长，可以从 28:08 开始看。

Aravind Srinivas (28:08)

很多人认为，既然我们在网页搜索的 RAG 方面如此擅长，那么 Perplexity 就能轻松搞定内部搜索。不，这是完全不同的两回事。
A lot of people think that because we are so good at RAG for web search, Perplexity will just nail internal search. No, it's two completely different entities.

Google Drive 的搜索之所以糟糕是有原因的。你可能会想，Google作为网页搜索的王者，怎么会这么差劲？他们之所以差劲，是因为索引机制完全不同，需要训练的嵌入模型也完全不同。这不仅仅是嵌入模型的问题，还包括你如何对页面进行摘要、如何进行文本召回——如何使用传统的基于TF-IDF的倒排索引来构建弹性索引，这些都大不相同。
There is a reason why search on Google Drive sucks. Like would you expect Google the king of web search to be so bad? They're bad because of a reason that the indexing is so different, the embeddings that you got to train are so different. Not just the embeddings, but even the way you snippet a page, your text retrieval——the elastic index that you're building with traditional TF-IDF based inverted indexes are so different.

所以需要某家公司专注于这种场景，就像我们专注于网页搜索场景一样。RAG 是一项非常艰巨的任务，在生成式 AI 之外还有很多工作需要完成。这不仅仅是训练一个大型的嵌入模型就能解决的问题。
That you need a company to just obsessively focus on that use case. Just like how we are obsessively focused on the web search use case. So RAG is going to be pretty hard and there's a lot of work that needs to be done outside of generative AI. It's not just training a large embedding model and you're done.

我记得当 OpenAI 发布嵌入 API 时，Sam Altman（OpenAI的CEO）在推特上说，下一个万亿公司可能只需要接入这个 API 就可以建立起来。这虽然是一种很好的营销方式，但事实并非如此。他当时说的是一万亿美元。所以，当听到有人声称他们已经解决了 RAG 问题时，我会非常谨慎。他们可能只是在某个场景下做得很好。
I remember like when OpenAI releases embedding API, Sam Altman tweeted the next 1 trillion company can just plug into this API and be built. That's not true. It's a good way to market it. But that's not true at all. Sorry, he said 1 trillion dollars. So I think that's why I would be very careful when somebody makes claims that they've solve RAG. They probably can do it really well for one use case.

此外，在排名中还有很多其他因素需要考虑，才能使答案真正出色。即使 LLM 最终决定了哪些链接用于答案，你也不能仅仅将一些垃圾信息放入 prompt 中，就指望它能神奇地只选择最相关的链接，并在答案中给出引用。
You know and also there are so many more things to handle in the ranking. That'll make the answer really good. Cuz even though the LLMs are finally the ones that are taking which links to use for the answer, it's not like you can just dump garbage into the prompt and it'll just be magically so good that it'll only take the top most relevant links in the answer and give you the citations with them.

事实上，你向这些长上下文模型提供的信息越多，最终出现幻觉的可能性就越大。因此，你实际上需要在检索模块上投入大量工作，不仅仅是嵌入向量，在索引、嵌入向量和排序上都要投入。排序也应该包含很多除了向量内积之外的其他信号，具体是哪些信号事实上取决于你的场景。
In fact the more information you throw at these really long context models, the more chances that you have a hallucination at the end. So you actually have to do a lot of work in the retrieval component, not just the embeddings, the indexing, the embeddings and the ranking. Ranking should also have a lot of signals outside of just the vector dot products. And then what is those signals are really depend on your use case.

分析（在2024年8月）

从以上不同时期 Aravind 的公开披露的信息分析，几乎可以说 Perplexity 在当前时间点，在召回阶段主要（如果不是全部的话）依赖倒排索引，在排序阶段会用到嵌入向量和其它信号，并且他们很重视除了嵌入向量之外的其它信号。

LLM 推理优化 Prefix Caching 及其实现

Prefix Caching

上文中提到，Prompt 计算（Prefill 阶段）和生成阶段的计算特性很不相同。为避免重复计算，所有框架的 prefill 阶段主要作用就是给迭代的生成阶段准备 KV Cache。但这些 KV Cache 仅仅是为单次生成式请求服务的，那很自然的一种想法就是，KV Cache 能不能跨请求复用？

在某些场景下，多次请求的 Prompt 可能会共享同一个前缀（Prefix），比如拟人 Agent 的人物设定，文档阅读理解时的文档内容等。这些情况下，很多请求的前缀的 KV Cache 计算的结果是相同的，像一般互联网服务的请求缓存一样，可以被缓存起来，给下一个请求复用。

限制

但 KV Cache 跟其它服务缓存不一样的地方是，它太大了，以至于（目前）很难通过 Redis/Memcache 这种分布式缓存服务存取。比如对 13B LLM 模型来说，在 FP16 精度下单 token 的 KV Cache 大约是 1MB，假设要缓存的前缀有 500 个 token（大约800多个汉字），那就是 500MB。一般来说，我们不会每次请求去从分布式系统里读取/传输 500MB 的缓存，甚至都不会每次请求从内存往显存中拷贝 500MB 的缓存，所以大部分情况下，prefix cache 都会放在显存里。

这也就意味着，如果你想命中 prefix cache，必须把相同 prefix 的请求发到同一张 GPU卡上才行。

实现

由于不是普遍需求，加上前面说的限制，prefix caching 作为一个加速特性，不是很受关注，一般也不是默认开启的。各框架的实现和配置略有差异，这里简单做下记录，便于回顾。

刚开始 vLLM 的实现是给 generate 接口增加一个 prefix_pos 参数，通过 prefix_pos 输入参数为每个请求指定 prefix 长度，为 prefix 建一个带淘汰的哈希缓存。后来觉得这样做使用上不够便利，升级成了自动前缀缓存，即将 prompt 的 kv cache 分成 block，然后为 block 建设 LRU 缓存机制，这样就不必在接口上使用 prefix_pos 指定哪部分是 prefix 了。自动前缀缓存功能默认是不开启的，开启的配置项为 --enable-prefix-caching 。

TensorRT-LLM 与 vLLM 后来的实现类似，也是实现了 block kv cache，配置项是 enableBlockReuse，默认也是不开启的。代码未开源，无法看到实现。

Lmdeploy 的 Python 和 TurboMind C++ 版本的 prefix caching 功能都已经有了 PR，但现在（20240425）看还没有合入主干。有意思的是它没有使用 hash block 对应 token_id 子串的所有 token_id 前缀然后组成哈希表的方式，而是用 hash 当前 block 对应的 token_id 子串然后组成 trie 树的缓存管理结构。默认的参数名与 vLLM 相同，也叫做 --enable-prefix-caching。

HuggingFace TGI 现在看起来还没实现 Prefix Caching 功能。

Prompt Caching

除了 Prefix Caching 这种比较直观的工程优化，现在也有一些研究在看 Prompt 的其它缓存机制。比如设计一种机制让 prompt 模块化，不仅可以复用 prefix，还能复用中间的部分；或者通过 query 的相似性复用其它 query 的 prompt。

但目前看实现上都过于复杂，比如第一种要求模型使用不连续的 poition_id，这样就可以插入 token，但这种方式对 attention 的计算机制有一定的影响，难以说明它对效果的影响。

LLM 推理优化 Continuous Batching 及其实现

原理

Continuous Batching 是 LLM 推理优化的一项技术，作为这篇文章的知识背景不再赘述，目前流传最广的参考资料是这篇：《How continuous batching enables 23x throughput in LLM inference while reducing p50 latency》。它也有中文翻译，感兴趣可以搜一下，先看看。

虽然这篇资料介绍了它的主要原理，尤其是这张简单易懂的图，但是实现与原理是存在差异的，因为工程实现要解决很多现实问题。

(Re)scheduling 开销

如原文所说，Continuous batching 还有个别名，叫做：batching with iteration-level scheduling，这里的 iteration 就是指一次 decode 计算。也就是说在每次 decode 的迭代过程中，做 batch 的调度调整。

但调度本身不是无代价的，它可能涉及到接收和处理新的输入请求，重新组织输入数据的形状，甚至各种状态的重新初始化，这些都需要消耗 CPU 时间。这也就意味着在这段时间里，GPU 是闲着的，GPU 没有得到充分利用。

所以在实现时，程序并不会真的每个 iteration 都做 scheduling，目前看到有两种做法：

合理间隔调度。比如每 16 次 decode 计算后，检查一下是否有新的输入，以及是否有空闲的槽位，然后对 batch 做一次调度调整。这能够显著降低调度的开销（TGI、lmdeploy、vLLM）。
排队比例调度。比如当前 batch 中有 10 个请求的 decode 正在进行，而排队中有 12 个请求，超过了排队比例 1.2，那么就启动一次调度调整（TGI）。

KV Cache 重读

如果真的像图中那样，每个生成 Token 的 decode iteration 与一个 prompt token 的计算对齐，那 KV Cache 的利用就会很糟糕。因为它们需要在 Global Memory 与 Shared Memory 之间反复搬运，而且每次搬进来以后只被使用一次。

这本质上是 prefill 阶段（prompt 计算）与生成阶段的计算特性不同导致的，prefill 阶段并不适合 one-by-one 的 token 计算。

所以在实现时，程序并不会真的做 prefill 和生成的 token 对齐调度。目前看到的调度方法有三种：

在重调度时，如果有新的请求进来，那么将新请求的 prefill 计算和要进行的 decode 计算做合并（Orca、vLLM-prev）。
在重调度时，如果有新的请求进来，那么先对新的请求做 prefill 计算，然后再合并所有进行中的请求做 decode 计算（TGI、vLLM、lmdeploy）。
先根据 decode 耗时估算出来每次 decode 同时能做 prefill 的 token 数量，在重调度时，如果有新的请求进来，对新请求的 prefill 按照上面的估算进行分块，然后将分块的 prefill 和其它请求的 decode 计算融合在一起，一定程度上减少了 KV Cache 重读的次数，又避免先做 prefill 计算带来的 Token 生成延时增加（Sarathi-Serve+vLLM）。

可调优能力

LLM 推理服务往往用于生产环境，而生产环境面临的情况是复杂多样的。

对于做阅读理解的应用来说，Prompt 可能会非常长，但生成的内容可能会非常短，开发人员可能会更追求吞吐；
对于聊天应用来说，Prompt 可能较短，生成的内容也不会太长，开发人员可能会更追求延迟；
对于创作类应用来说，Prompt 可能很短，生成的内容会更长，开发人员可能会更追求首 Token 延迟。

对 Continuous Batching 实现来说，就要求它调度策略尽量清晰，并且参数可调。所以更灵活的实现，未来可能会更受欢迎。

Logits of API-Protected LLMs Leak Proprietary Information

看到一篇挺有意思的论文，大开脑洞，没想到还能这么玩，做一下粗读的笔记。

论文

标题：《Logits of API-Protected LLMs Leak Proprietary Information》，链接： https://arxiv.org/pdf/2403.09539.pdf 。

假设条件

典型 LLM 需要将最后一个 Transformer 块输出的嵌入向量转成要输出的 Token，这一步往往通过一个线性变换加 softmax 获取那个最大概率的 tokenid。

线性变换的权重是一个 vocabulary size * hidden size 的矩阵，比如 llama2-7B 的词表大小是 32000，hidden size 是 4096，那么线性变换权重矩阵的尺寸就是 32000x4096。这个矩阵再与 4096x1 的嵌入向量相乘，得到的就是 32000x1 的 logits 向量，其中每一个元素对应着一个词表中的 token 作为最终输出的概率。

上面这只是假设，也许 GPT 使用的是一个非线性变换，那论文内容可能就不成立了。

数学原理

这个线性变换将一个 4096 维的向量映射到了一个 32000 维的向量，从线性代数的角度来看，这是一个低维向高维的映射，所以它肯定不是一个满射（onto mapping）。也就是说，这个映射的像空间（image）只是 32000 维实数空间的一个子空间（subspace），而且这个像空间的秩（rank）最多是 4096。

这意味着可以找到不多于 4096 个线性无关的基向量（basis），使得这个像空间的每一个元素都能表示为这些基向量的线性组合。假设能采集到 4096 个线性无关的输出 logits，那这些 logits 就构成了像空间的一组基向量。

反过来想，如果你不知道 LLM 的 hidden size，那么你可以通过采集足够多的输出 logits，以保证有足够多的线性无关的向量。然后对矩阵进行奇异值分解（singular value decomposition），可以通过非 0 的奇异值个数推导出矩阵的秩。这个秩应该接近于模型的 hidden size。

逆向恢复 logits

遗憾的是，很多模型的 API 并没有输出完整的 logits 矩阵，但幸运的是，OpenAI 的 API 支持输出最多 top 5 个 token 的 logprobs，并且支持 logit_bias 干预 token 的输出。那就给了反复通过 API 调用来逆向恢复 logits 向量的可能。

但是具体方法我没看，粗读嘛，知道能做到就行了，有用到的时候再看吧。还有另一篇文章《Stealing Part of a Production Language Model》分析了在没有 logit_bias 甚至没有 logprobs 时该如何恢复 logits，我也没看，记录下链接 https://arxiv.org/pdf/2403.06634.pdf 。

无法输出的 Token

这篇论文还介绍了很多其它应用，太长没有看。比较有意思的一个引用是，在将嵌入向量映射到 logits 的过程中，如果一个 token 的嵌入向量在其它 token 的嵌入向量组成的凸包的内部，它就永远不可能被输出。扫了一眼引用的论文，证明没看懂，大致意思是 softmax 权重矩阵的低秩特性导致了可能输出 token 的排列在线性变换后不会出现在子空间里？实话说我感觉不像是很严谨的数学证明。。。

怎么用向量指令计算多个元素尾部 0 的个数？

大家都知道 gcc 提供了__builtin_ctz 这种内建函数计算整数尾部 0 的个数，它在大部分情况下会转译成 CPU 的内建指令，比如 x86 平台上的 tzcnt 指令。

但如果你想同时计算多个元素尾部 0 的个数，就会发现有些指令集，比如 SSE/AVX，并没有提供类似的向量指令。而这种指令有时候在写向量化代码时又是需要的，我自己针对 8-bits 单字节整数做了一些粗糙的实现，如果你通过搜索引擎来到这里，希望对你能有所帮助。

函数功能

输入一个整数向量（16 或者 32 个 uint8），返回一个同类型整数向量，其中输出的每一个整数表示对应位置输入整数末尾 0 的个数。

SSE 版本

#include <smmintrin.h>
__m128i tzcnt_epi8(__m128i a) {
    __m128i ctz_table = _mm_setr_epi8(
        4, 0, 1, 0, 2, 0, 1, 0,
        3, 0, 1, 0, 2, 0, 1, 0
    );
    __m128i shuffle_mask = _mm_set1_epi8(0x0F);
    __m128i v_4 = _mm_set1_epi8(0x4);
    __m128i a_low = _mm_and_si128(a, shuffle_mask);
    __m128i ctz_low = _mm_shuffle_epi8(ctz_table, a_low);
    __m128i a_high = _mm_and_si128(_mm_srli_epi16(a, 4), shuffle_mask);
    __m128i ctz_high = _mm_shuffle_epi8(ctz_table, a_high);
    ctz_high = _mm_and_si128(ctz_high, _mm_cmpeq_epi8(ctz_low, v_4));
    return _mm_add_epi8(ctz_low, ctz_high);
}

AVX 版本

#include <immintrin.h>
__m256i tzcnt_epi8(__m256i a) {
    __m256i ctz_table = _mm256_setr_epi8(
        4, 0, 1, 0, 2, 0, 1, 0,
        3, 0, 1, 0, 2, 0, 1, 0,
        4, 0, 1, 0, 2, 0, 1, 0,
        3, 0, 1, 0, 2, 0, 1, 0
    );
    __m256i shuffle_mask = _mm256_set1_epi8(0x0F);
    __m256i v_4 = _mm256_set1_epi8(0x4);
    __m256i a_low = _mm256_and_si256(a, shuffle_mask);
    __m256i ctz_low = _mm256_shuffle_epi8(ctz_table, a_low);
    __m256i a_high = _mm256_and_si256(_mm256_srli_epi16(a, 4), shuffle_mask);
    __m256i ctz_high = _mm256_shuffle_epi8(ctz_table, a_high);
    ctz_high = _mm256_and_si256(ctz_high, _mm256_cmpeq_epi8(ctz_low, v_4));
    return _mm256_add_epi8(ctz_low, ctz_high);
}

NEON 版本

#include <arm_neon.h>
uint8x16_t vctzq_u8(uint8x16_t a) {
    return vclzq_u8(vrbitq_u8(a));
}

在 LLM 时代我们是否还需要倒排索引？

近些年，EBR（基于文本嵌入向量的召回）的强大语义召回能力让基于属性索引的传统倒排索引技术黯然失色，即使对专业搜索引擎来说，EBR 的应用也是越来越广泛 [1,2,3] 。尤其在 LLM（大语言模型）激起的 RAG（检索增强生成）技术框架下，大部分人似乎已经忘记了倒排索引，向量数据库成为 RAG 的标配。

但在 LLM 时代倒排索引真的没有用武之地了吗？我尝试列一下自己的思考。

Embedding 向量缺少 ground truth，但是倒排有。你无法通过直接观察或者测量，来明确一个向量指代的一段文本是否一定包含某些信息。但是如果这段文本在某个 term 的倒排拉链里，你可以从一定程度上明确这段文本包含了一些相关信息。
term 命中也是一种 attention。在训练模型时，我们总是希望 LLM 能关注到 context 中应该关注的信息，而忽略其它无关内容。那跟用户问题或者指令中某些 term 相关的内容，应该需要更多的关注。其实也可以类比人类肉眼的信息查找，人们也总是会扫到某些关键词，然后再仔细阅读它的上下文篇章。
不基于倒排做召回，仍可以用倒排做粗筛。倒排作为一种可以查询 term 命中的高效结构，对 EBR 也许可以起到补充作用。例如对于某些 EBR 效果不够理想，误召回概率较高的场景下，对得分比较低的文档用命中信息作一次粗筛，能显著提升送给模型的 context 质量，也能减少对 LLM 计算资源的浪费。
term 命中的位置信息和权重不再重要。对于 LLM 来说，它会自行关注到 context 中需要关注的信息，不再需要位置信息或者权重来指示文本中哪些部分更重要。也就是说，倒排只需要解答 term 在文本中是否出现的问题，而不需要回答出现几次、在哪里出现的问题。
也许倒排不再用 term，而是 token。term 依赖于切词，有一定的语义含义，term 集合空间一般有百万甚至千万的量级。但现在 LLM 大部分使用 BPE（Byte-Pair Encoding）分词器，token 集合空间只有几万到十几万的量级。使用 token 将显著减少倒排链的数量而优化其性能，但 token 存在没有归一化、分词边界不对齐的问题，是否可用还有待验证。

参考

[1] Guo, Ruiqi, et al. "Accelerating large-scale inference with anisotropic vector quantization." International Conference on Machine Learning. PMLR, 2020

[2] Huang, Jui-Ting, et al. "Embedding-based retrieval in facebook search." Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2020.

[3] Liu, Yiding, et al. "Pre-trained language model for web-scale retrieval in baidu search." Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. 2021.

配置 dcgmi 遇到的问题

dcgmi 是 Nvidia datacenter-gpu-manager 的命令行程序，可以用来采集 GPU 各类子资源的利用率数据，揭示的数据比 nvidia-smi 更详细，也更便于对接监控系统（比如 Prometheus）。这次我主要想用它来看模型训练过程中的 NVLink 带宽使用情况。

在一个已经完成 Nvidia 训练环境配置的服务器上安装 dcgmi，主要有以下几步：

1. 如果服务器上有 NVSwitch，比如 A100/800，或者部分 V100，需要先安装 nvidia-fabric-manager，注意 nvidia-fabric-manager 的版本要和 GPU 驱动版本严格一致，包括小版本号（nvidia-smi 显示的驱动版本）。

2. 如果服务器上有 NVSwitch，还需要安装 libnvidia-nscq，版本也要和驱动严格一致。

3. 安装 datacenter-gpu-manager。

4. 启用并启动 nvidia-fabricmanager 服务，注意服务名(nvidia-fabricmanager)、包名(nvidia-fabric-manager)和进程名(nv-fabricmanager)的区别。根据启动成功与否，可检查 /var/log/fabricmanager.log 中的错误信息。

systemctl enable nvidia-fabricmanager
systemctl start nvidia-fabricmanager

5. 启用并启动 nvidia-dcgm服务，注意包名(datacenter-gpu-manager)、服务名(nvidia-dcgm)和实际命令/进程名(nv-hostengine)的区别。根据启动成功与否，可检查 /var/log/nv-hostengine.log 中的错误信息。

systemctl enable nvidia-dcgm
systemctl start nvidia-dcgm

但是整套配置下来，我还是遇到了不少问题，有些是配置问题，有些是文档未明确说明的问题。甚至我找到 Nvidia 的售后工程师咨询，他们都没法给我答案，后来还是我自己摸索出来了，做个记录。

1. nvidia-dcgm 服务启动成功，但又没完全成功

启动服务时候没有报错，但是执行监控命令时出错，其实启动的时候 /var/log/nv-hostengine.log 就已经出现无法加载 nscq 库的错误，只不过没影响服务的启动。因为 nscq 是对 nvswitch 的查询，用户如果不需要查询 nvswitch 的数据，可以接受这个错误。

ERROR [13862:13862] [[NvSwitch]] Could not load NSCQ. dlwrap_attach ret: Can not access a needed shared library (-79): If this system has NvSwitches, please ensure that the package libnvidia-nscq is installed on your system and that the service user has permissions to access it. [/workspaces/dcgm-rel_dcgm_3_3-postmerge/modules/nvswitch/DcgmNvSwitchManager.cpp:798] [DcgmNs::DcgmNvSwitchManager::AttachToNscq]
ERROR [13862:13862] [[NvSwitch]] AttachToNscq() returned -25 [/workspaces/dcgm-rel_dcgm_3_3-postmerge/modules/nvswitch/DcgmNvSwitchManager.cpp:632] [DcgmNs::DcgmNvSwitchManager::Init]
ERROR [13862:13862] [[NvSwitch]] Could not initialize switch manager. Ret: DCGM library could not be found [/workspaces/dcgm-rel_dcgm_3_3-postmerge/modules/nvswitch/DcgmModuleNvSwitch.cpp:34] [DcgmNs::DcgmModuleNvSwitch::DcgmModuleNvSwitch]

虽然我已经安装了 libnvidia-nscq 库，但 nv-hostengine 就是找不到 NSCQ 对应 so。我在这个问题上困扰了很久，Nvidia 的工程师也没法给我解释原因，只是一遍一遍地让我去看文档，甚至重装系统。

我觉得他的建议不靠谱，后来还是自己找到了原因，那就是 datacenter-gpu-manager 对 libnvidia-nscq 也有隐式的版本依赖。虽然在文档和包依赖中完全没有体现这种依赖关系，但我通过降级 datacenter-gpu-manager 到与 libnvidia-nscq 时间上更接近的版本解决了这个找不到 so 的问题。

之所以想到去尝试降级版本，还是因为 Nvidia 各种环境和驱动版本的强绑定，让我免不了去怀疑一下这个。

2. 查询部分指标 DCGM_FI_PROF_* 时出错

在执行 dcgmi dmon -e 449,1011,1012 时，命令行显示如下错误：

Error setting watches. Result: The third-party Profiling module returned an unrecoverable error

查看 /var/log/nv-hostengine.log，有如下错误日志：

ERROR [225876:233276] [[Profiling]] [ProfModule][PerfWorks] Got status 1 from NVPW_DCGM_PeriodicSampler_BeginSession() on deviceIndex 0 [/workspaces/dcgm-rel_dcgm_2_3-post
merge/dcgm_private/modules/profiling/DcgmLopGpu.cpp:351] [DcgmLopGpu::BeginSession]
ERROR [225876:233276] [[Profiling]] EnableMetrics returned -37 The third-party Profiling module returned an unrecoverable error [/workspaces/dcgm-rel_dcgm_2_3-postmerge/dc
gm_private/modules/profiling/DcgmModuleProfiling.cpp:2461] [DcgmNs::Modules::Profiling::DcgmModuleProfiling::ReconfigureLopGpu]
ERROR [225876:233276] [[Profiling]] Unable to reconfigure LOP metric watches for GpuId {0} [/workspaces/dcgm-rel_dcgm_2_3-postmerge/dcgm_private/modules/profiling/DcgmModu
leProfiling.cpp:2545] [DcgmNs::Modules::Profiling::DcgmModuleProfiling::ChangeWatchState]

导致这个错误的原因是对于这些 Profile 指标（1001-1014 ），NV 的 Profiler 对每个硬件使用了一个唯一锁。当你启动了超过 1 个的 nv-hostengine （包括内建的），比如使用 NCGM-Exporter 容器时，已经启动了一个内建的 nv-hostengine，然后又在主机上又启动了一个 nv-hostengine 服务，在访问这些指标时，就会出现这种访问失败。解决方案就是一台服务器仅启动一个 nv-hostengine 服务，然后所有的客户端都用本地或者远程的方式去访问它（5555 端口）。

这类问题在云场景下可能更常见，因为云服务商可能已经在租用的 GPU 服务器上部署了 DCGM 监控，你再去部署就可能遇到硬件锁的问题。

3. DCGM_FI_DEV_NVLINK_BANDWIDTH_TOTAL 的单位

我最早看到这个指标是在 NCGM-Exporter 的输出指标中，但是无论是文档、配置文件还是输出接口中，都没有写明这个指标的单位和计算逻辑。我问 Nvidia 的售后工程师，他告诉我这个指标的单位是 B/s，LoL！

后来仔细查 NCGM 的文档，发现 NCGM-Exporter 的所有指标其实都源自 NCGM 的接口，但还是没看到这个指标的单位和计算逻辑。

最后使用 dcgmi dmon -e 449,1011,1012 做了一下对比，才发现其输出头中有个不起眼的 MB 字样：

#Entity   NBWLT                       NVLTX                       NVLRX
ID       MB/

我做了一下数字的校验，基本可以明确 DCGM_FI_DEV_NVLINK_BANDWIDTH_TOTAL[449] 约等于 (DCGM_FI_PROF_NVLINK_TX_BYTES[1011] + DCGM_FI_PROF_NVLINK_RX_BYTES[1012]) / 1048576，所以单位应该是 MB/s 。

4. NCGM-Exporter 的采集延迟和精度

用 docker 跑 NCGM-Exporter 镜像时，发现指标的输出非常慢，输出的值看起来也很奇怪。后来自己构建了一下，研究了一下命令行参数，才发现默认采集的周期是 30s 一次。这种采样精度下，输出的指标值能准确才怪了。正常 dcgmi 采样的频率是 1s 一次，最低可以配置到 100ms 一次。NCGM-Exporter 有命令行参数可以调整这个采样频率，但需要你自己用修改 Dockerfile 去重建镜像。或者可以考虑启动的时候将启动脚本映射到外部文件？没尝试。

GPT-2 Tokenizer 效率观察

对基于 Transformer 结构的 LLM （大语言模型）来说，模型的输入输出都是 Token（词元）。一段输入文本，首先要经过 Tokenizer（分词器）切分成 Token 再输入给模型。

不同的 Tokenizer 会把文本按不同的边界切分，那一段文本到底会被切成几个 Token 就体现了 Tokenizer 本身的效率，这本身也是信息论的讨论范畴。不过今天不做理论分析，也不介绍 Tokenizer 的训练算法，就看下 GPT-2 和 GPT-3 Tokenizer 的实际分词效率（GPT-2 和 GPT-3 使用的是同样的 Tokenizer）。

用 GPT-2 Tokenizer 编码一段中文

from transformers import GPT2Tokenizer

tokenizer = GPT2Tokenizer.from_pretrained('gpt2')
input_str = '不同的 Tokenizer 会把文本按不同的边界切分，那一段文本到底会被切成几个 Token 就体现了 Tokenizer 本身的效率，这本身也是信息论的讨论范畴。'
tokenids = tokenizer(input_str)['input_ids']
raw_tokens = tokenizer.convert_ids_to_tokens(tokenids)
token_strs = [tokenizer.convert_tokens_to_string([token]) for token in raw_tokens]
print(len(input_str), len(tokenids), tokenids, token_strs)

82 121 [38834, 28938, 234, 21410, 29130, 7509, 220, 27670, 248, 162, 232, 232, 23877, 229, 17312, 105, 162, 234, 231, 38834, 28938, 234, 21410, 164, 122, 117, 45911, 234, 26344, 229, 26344, 228, 171, 120, 234, 165, 224, 96, 31660, 162, 106, 113, 23877, 229, 17312, 105, 26344, 108, 41753, 243, 27670, 248, 164, 95, 104, 26344, 229, 22755, 238, 49035, 254, 10310, 103, 29130, 10263, 108, 109, 19526, 241, 163, 236, 108, 12859, 228, 29130, 7509, 42164, 105, 164, 118, 104, 21410, 46763, 230, 163, 236, 229, 171, 120, 234, 32573, 247, 17312, 105, 164, 118, 104, 20046, 253, 42468, 46479, 94, 162, 223, 107, 164, 106, 118, 21410, 164, 106, 101, 164, 106, 118, 164, 234, 225, 45911, 112, 16764] ['不', '�', '�', '的', ' Token', 'izer', ' ', '�', '�', '�', '�', '�', '�', '�', '�', '�', '�', '�', '�', '不', '�', '�', '的', '�', '�', '�', '�', '�', '�', '�', '�', '�', '�', '�', '�', '�', '�', '�', '一', '�', '�', '�', '�', '�', '�', '�', '�', '�', '�', '�', '�', '�', '�', '�', '�', '�', '�', '�', '�', '�', '�', '�', '�', ' Token', ' �', '�', '�', '�', '�', '�', '�', '�', '�', '�', ' Token', 'izer', ' �', '�', '�', '�', '�', '的', '�', '�', '�', '�', '�', '�', '�', '�', '�', '�', '�', '�', '�', '�', '�', '�', '�', '是', '�', '�', '�', '�', '�', '�', '�', '�', '的', '�', '�', '�', '�', '�', '�', '�', '�', '�', '�', '�', '。']

输入的中英文夹杂的字符串长度为 82 个字符，其中有 6 个空格，23 个英文字符（3个单词），3个标点符号，50 个汉字字符。最终编码出来的 tokenids 长度是 121 个 Token，仔细检查可以看到，大部分汉字被编码成两个 Token，英文则是按照 subword 级别进行了编码。由此可见，GPT-2 Tokenizer 编码中文的效率是很低的。

GPT-2 Tokenizer 词典中包含中文的 Token 数量

import re
tokens = [tokenizer.convert_tokens_to_string([key]) for key in tokenizer.get_vocab()]
cn_tokens = [t for t in tokens if re.search(u'[\u4e00-\u9fff]', t)]
cn_tokens.sort(key=len, reverse=True)
print(len(tokens), len(cn_tokens), cn_tokens)

50257 51 [' 裏覚醒', ' 裏�', '��士', '龍喚士', ' 裏�', '龍契士', '��極', ' 裏', '龍�', '�醒', '覚醒', 'の魔', '�士', '龍�', ' 神', '龍', '神', '士', '魔', '的', '人', '天', '王', '一', '大', '装', '田', '子', '戦', '生', '者', '不', '姫', '中', '上', '闘', '是', '女', '方', '作', '黒', '之', '使', '光', '代', '版', '三', '五', '武', '将', '機']

对 GPT-2 Tokenizer 词典中的 Token 进行分析，可以看到：在数量为 50257 大小的词典中，只有 51 个 Token 包含常见的中文字符。上一节中出现的“是”、“的”、“不”也在其中，但是大家随便一想就能想到的，常见的“你”、“我”、“他”并不在内。这些数据印证了它对中文分词的效率低下。

GPT-2 Tokenizer 词典中包含英文的 Token 数量

en_tokens = [t for t in tokens if re.search(u'[A-Za-z]', t)]
en_tokens.sort(key=len, reverse=True)
print(len(en_tokens), en_tokens[:10])

46949 ['rawdownloadcloneembedreportprint', 'BuyableInstoreAndOnline', 'cloneembedreportprint', ' RandomRedditorWithNo', ' telecommunications', ' disproportionately', ' guiActiveUnfocused', 'channelAvailability', ' Telecommunications', ' externalToEVAOnly']

但是针对英文字符进行统计，可以看到在数量为 50257 大小的词典中，有 46949 个 Token 包含 26 个英文字母。由于数量太多，这里仅输出了长度排前 10 的英文 Token。

从 Tokenizer 词典中不同语言字符的分布，我们可以验证 GPT-3 论文 “Language Models are Few-Shot Learners” 中提到的这句话：

... This could be a weakness due to reusing the byte-level BPE tokenizer of GPT-2 which was developed for an almost entirely English training dataset.

GPT-2 Tokenizer 词典中最长的 Token 是什么

tokens.sort(key=len, reverse=True)
print(len(tokens), tokens[:10])

50257 [' =================================================================', ' ----------------------------------------------------------------', '----------------------------------------------------------------', '................................................................', '================================================================', '________________________________________________________________', 'ÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂÃÂ', '--------------------------------------------------------', '------------------------------------------------', ' =================================']

可以看到，最长的 Token 居然是一些连续的标记，看起来像是论坛上的分割线。在“Natural Language Processing with Transformers” 一书中说，这可能是由于 GPT-2 的词典是用以 Reddit 为核心的语料训练的。

Codex Tokenizer 提升代码处理效率的 Trick

上面讲到 Tokenizer 效率对最终生成 Token 序列大小的影响，如果只关注最终的模型效果，可能并不在意中间过程的效率问题。

但从一个小点可以看到 OpenAI 还是很重视 Tokenizer 效率的。在训练 Codex 时，它在 50257 的词典之外新增了 23 个 Token，分别编码了：[2个连续空格, 3个连续空格, ..., 23个连续空格]。

大家都知道，代码中有很多锁进和对齐，如果每个空格都编码成一个 Token，训练和推理的效率就会极低；如果像常规语言模型那样忽视更多连续的空格，又会导致生成的代码不可读，甚至对 Python 这样的语言来说代码完全不可理解。所以 OpenAI 专门修改了 Tokenizer 的词典，提升了对连续空格的编码效率。

在中文数据集上训练的 Tokenizer 表现如何？

同样使用第一节的代码，我们换一个在中文数据集上训练的 Tokenizer，效果会如何呢？我随便在 HuggingFace 上找了一个模型 HuiHuang/gpt3-base-zh，使用它的 Tokenizer 对那段话进行重新分词。

from transformers import BertTokenizerFast

tokenizer = BertTokenizerFast.from_pretrained("HuiHuang/gpt3-base-zh")
input_str = '不同的 Tokenizer 会把文本按不同的边界切分，那一段文本到底会被切成几个 Token 就体现了 Tokenizer 本身的效率，这本身也是信息论的讨论范畴。'
tokenids = tokenizer(input_str)['input_ids']
raw_tokens = tokenizer.convert_ids_to_tokens(tokenids)
token_strs = [tokenizer.convert_tokens_to_string([token]) for token in raw_tokens]
print(len(input_str), len(tokenids), tokenids, token_strs)

82 65 [2, 215, 1750, 10574, 22090, 24330, 23635, 21748, 484, 5460, 6225, 6646, 5587, 215, 1750, 10574, 17027, 10262, 1233, 1232, 21124, 17261, 202, 7807, 6225, 6646, 1274, 4447, 484, 15221, 1233, 5338, 1194, 244, 22090, 24330, 3835, 541, 9850, 336, 22090, 24330, 23635, 21748, 6646, 16757, 10574, 6162, 9809, 21124, 17059, 6646, 16757, 297, 6393, 683, 4921, 16004, 10574, 15986, 16004, 13773, 10302, 160, 3] ['[CLS]', '不', '同', '的', 'to', '##ken', '##ize', '##r', '会', '把', '文', '本', '按', '不', '同', '的', '边', '界', '切', '分', '，', '那', '一', '段', '文', '本', '到', '底', '会', '被', '切', '成', '几', '个', 'to', '##ken', '就', '体', '现', '了', 'to', '##ken', '##ize', '##r', '本', '身', '的', '效', '率', '，', '这', '本', '身', '也', '是', '信', '息', '论', '的', '讨', '论', '范', '畴', '。', '[SEP]']

可以看到，82 个字符的输入被分成了 63 个 Token（除去[CLS]和[SEP]），比 GPT-2 Tokenizer 的分词数量 121 几乎少了一半。这就是 Tokenizer 训练数据集对分词效率的影响。

Tokenizer 的效率意味着什么

在以前，Tokenizer 的效率只是算法工程师们关注的话题。但是现在，LLM 逐渐成为云服务，Token 成为 API 调用的基本收费单元。例如：OpenAI gpt-3.5-turbo 的收费标准是 $0.002/1K tokens。

在这种情况下，Tokenizer 的效率就意味着成本。这意味着使用中文调用 OpenAI 的 chatGPT API，假设单 Token 成本一样的话，每次调用的实际成本可能是调用国内类似 chatGPT 云服务的 2 倍以上。

GPT-4 的 Bits Per Word 指标是什么意思

最近人人都在聊 ChatGPT，这里聊点儿更底层的技术细节。上周 OpenAI 发布了 GPT-4，里面有一张图引起了我的兴趣。在 OpenAI 内部的 Codebase 上，他们准确预测了 next word prediction 误差随着计算规模增加的下降曲线。让我感兴趣的不是这个曲线，而是这个曲线纵轴使用的指标：Bits Per Word (BPW)。

乍一看我以为这是信息论里的概念，Bits Per Word 可能是指在某种语言里表达一个词所需要的最小位数，比如用于压缩时，这意味着压缩比的理论上限。但仔细看下指标接近 1.2 BPW，虽说英文字母的 Bits Per Character (BPC) 大约也在 1.2 左右，我不太相信单词的 BPW 能降到 1.2 这个规模。

后来才了解到，Bits Per Character (BPC) / Bits Per Word (BPW) 是 NLP 任务中对语言模型的评估指标之一。这些评估指标的详细解释可以先阅读这篇文章《Evaluation Metrics for Language Modeling》，但是我感觉这篇文章的说明在理论和应用之间跳过了一些环节，下面我以我的理解补全一下这些环节。推测的内容以黑字标出，如有谬误，欢迎指正。

原始 BPW 定义

The entropy is a statistical parameter which measures, in a certain sense, how much information is produced on the average for each letter of a text in the language. If the language is translated into binary digits (0 or 1) in the most efficient way, the entropy $H$ is the average number of binary digits required per letter of the original language.

以上，是香农在《Prediction and Entropy of Printed English》一文中对语言的熵的定义。可以看到，语言的熵 $H$ 其实就是 BPC (Bits Per Character) 的均值。但我们一般不会报告某个字符有几个 bits，因而通常所说的 BPC，就是整个语言(数据集)的平均 BPC，所以可以理解为语言的熵 $H$ 就是 BPC。

但是在原始论文中，香农是用字符来建模的语言的熵，当用单词来建模语言时，语言的熵 $H$ 就是 BPW (Bits Per Word)。

用 BPW 表示交叉熵

对于生成式语言模型来说，它的目标就是从样本中学习到一个分布 $Q$，使这个分布尽量接近语言的经验分布 $P$。交叉熵 $H(P, Q)$ 经常被用来衡量这种接近程度，

\[H(P, Q) = H(P) + D_{KL}(P \Vert Q) \]

根据《Evaluation》一文，交叉熵的两个因子用信息论的角度来理解：

$H(P)$: 就是 $P$ 的熵，即使用为分布 $P$ 优化的编码器编码 $P$ 中所有可能出现的字符的平均位数；

$D_{KL}(P \Vert Q)$: 使用为分布 $Q$ 优化的编码器编码 $P$ 中所有可能出现的字符，所需要的平均额外位数；

与原始 BPC/BPW 的定义相同，如果用 $BPC/BPW(P, Q)$ 表示交叉熵 $H(P, Q)$，那么它意思应该是使用为分布 $Q$ 优化的编码器编码 $P$ 中所有可能出现的字符/单词所需要的平均位数。

上面这点理解，与知乎上一篇文章《一文搞懂Language Modeling三大评估标准》存在 diff（飘红部分）：

也就是说BPC/BPW是cross-entropy对句子长度的平均，我们可以很容易地得出它的信息论含义：
基于预测的Q序列来编码P序列所需要的额外bit数在句子长度上的平均，也就是平均每一个字母/单词需要额外的bit数。

下面这一节，可能能解释 diff 的由来。

用 BPW 表示损失指标

但是在评估一个语言模型时，我们并不是评估模型输出的整个分布，而是评估模型的输出跟实际样本的不同。拿 GPT-2 模型来说，它是拿模型输出的预测下一个 Token 的 logits 与 label （样本中真实的下一个 Token）计算交叉熵：

The output from the decoder is passed to a language modeling head, which performs a linear transformation to convert the hidden states into logits. The label is the next token in the sequence, which are created by shifting the logits to the right by one. The cross-entropy loss is calculated between the shifted logits and the labels to output the next most likely token.

logits 是一个 $Q(x)$ 的向量，表示下一个 Token 是 $x$ 的概率；

label 表示样本中下一个 Token 是什么，它是一个 $P(x)$ 的向量，但只有 x = 下一个 Token 时为 1，其它位置为 0，那么：

\[H(P) = -\sum_{x}P(x)\log{P(x)} = 0\]

从信息论也好理解，在计算损失时样本 $P$ 是一个确定性分布，确定性分布的熵应该为 0。那么在计算交叉熵损失的场景下：

\[H(P, Q) = H(P) + D_{KL}(P \Vert Q) = 0 + D_{KL}(P \Vert Q)\]

可以看到，这时候交叉熵等于相关熵，那么 $BPC/BPW(P, Q)$ 也就是 $D_{KL}(P \Vert Q)$，或者更精确地说，是在数据集样本上平均的 $D_{KL}(P \Vert Q)$。那么在评估一个语言模型的场景下，把 BPC/BPW 损失指标的信息学含义解释成：“使用为分布 $Q$ 优化的编码器编码 $P$ 中所有可能出现的字符/单词所需要的平均额外位数”，也是合理的了。

GPT-4 的 BPW 指标

从 GPT-4 给出的指标来看，它的 BPW 指标只有 1.26 左右。除了信息论编码的概念，这代表什么意思呢？

这里我引入《Evaluation》一文中提到的另一个指标 Perplexity (PPL) 困惑度和一个有趣的比喻。考虑到：

\[PPL(P, Q) = 2^{H(P, Q)} = 2^{BPW(P, Q)} = 2^{1.26} \approx 2.4\]

那么 GPT-4 语言模型的效果相当于：在给定的数据集上，提供一个样本的前缀串后，GPT-4 会制作一个包含下一个 Token 的 2.4 面的新骰子，然后掷骰子来预测下一个 Token 是什么。

2022 年 12 月

昨天儿子问我：“蒙古是什么样的？内蒙古是什么样的？”我说：“内蒙古咱们今年不是去过吗？”他说：“哦，感觉也不怎么样，不比咱们小区好多少！（我们住的是一个老破小区）”

然后我想仔细想想上次内蒙都去过哪几个地方，忽然觉得有些地名已经想不起来了——这才仅仅四个月。翻开博客看了看，有些事情还是记一下比较好。

12 月从居家办公开始，第一次感觉情况有些变化，是 2022 年 12 月 3 日，居家办公的一个周末。我骑电动车带娃去公园玩，发现周围四个核酸点全都关门了，仅存的一个排起了长队。虽然 12 月 3 日中午有个辟谣：“网传北京市明天起全面放开为不实消息。”但我觉得从动作上来看，肯定是要放开了。

但我这时候还没想起来囤药，因为我觉得再不济医院总不会没药，去医院开药还能走医保、商保。后来知道，这想法天真了。

5 号本来也是居家，但是 4 号公司发了一个模棱两可的通知，把原来要求 24 小时核酸改成了 48 小时核酸。然后考虑到晚上有个直属领导的月度会，侧面了解了下说领导一直都没居家，想了想还是去公司了。

正上着班，媳妇说家里被封单元了。晚上开完会回到家，先去超市买了些蔬菜，孩子喜欢吃的面包，拎着袋子进楼。门口有两个值班，问我进去就不能出来了，我说好。本来想再去买点药的，下班实在太晚，怕超市关门了就没去。

5 号夜里，赶紧京东下单了抗原检测试剂、芬必得、感冒药。事实上已经晚了，下完单都没法显示送达时间（这时候不知道外卖送药啥样，应该试试，忘了）。我看了下同事的情况，有的 12 月 2 日下单的芬必得也一直没发货。

实际上抗原是 12 月 9 日送到的，感冒药是 12 月 13 日送到的。因为我阳的比较晚，这俩还是起了作用的。但芬必得是 1 月 1 日送到的，这就没毛用了，都阳康了。家里还有两瓶美林，也没那么着急，但我还是在 12 日托儿子同学家长帮忙买了瓶杂牌的布洛芬缓释胶囊，50元/盒，19 日光远给了我两盒布洛芬缓释片。

6 号封控一天，做了一次上门核酸，7 号就解封了。然后我就又开始正常上班，就开始了相当魔幻的两周，看着周围的人成片地被感染，看着医院急诊被挤满，看着海淀医院药房挂出通知“布洛芬、感冒药都没有货”，看着美团外卖里的所有药房都下线不在营业时间，看着大家在各种群里抢购抗原、抢购布洛芬。

我不怕被感染，但我想感染得晚一点，因为我家里药都没备齐。所以我在公司里极为谨慎，回到工位就酒精湿巾擦手，全天戴口罩，中午在工位吃饭。

我媳妇单位比较奇葩，政策天天变。她先居家了几天，又因为是部门内少数自驾上班的，多值了几天班，然后又居家几天。前面防护得也挺好的，但是在 20 日周二她还是开始咳嗽了。刚开始测是阴性，22 日周四测出来是阳性。她一直也没发烧，所以刚开始也没用药，后来痰多后用了一些抗生素。

然后我就释然了，该来的总会来的。24 日是周六，我带俩孩子出去中关村广场公园转了一圈，我说赶在阳之前晒一次太阳。果不其然，当天晚上女儿就开始发烧，最高烧到 39 度，后来用美林降温，很有效果。第二天圣诞节周日，女儿白天蔫了一会儿，又用了次美林，晚上看着就退烧了。

27 日周二下午，我妈说午饭全吐了，我想大概率阳了。回家测了一下抗原，本来还担心测不出来，结果直接就是两条杠。她也没烧，刚开始也没用药，只是喝补液盐水补充电解质。

有人开玩笑说新冠是一个仁义的病毒，一家总会留一个人做饭。那就是我了，本来周末已经做了两天饭，现在早餐也得我做了。

结果没两天，周三下午我就开始咳嗽，周四 29 日早上做完早饭吃完，我觉得体温不太对，量了下超过 37 度，还是测下抗原吧。也是两条杠，那就躺平居家吧。

也不知道是我用的抗原更精准，还是我洗棉签时候搓得比较狠。除了我媳妇，我家都是刚有症状就能测出来阳性。有些同事都烧了两天了才测出来阳性，我这刚开始发烧就已经阳了。

这个病毒发作起来的确挺快，早上起床觉得温度还正常，上午11点多已经 39 度晕在床上了。吃了一片同事匀给我的布洛芬缓释片，好像没顶什么用，在床上继续晕。晕的时候我一直在想：“现在到底几度了/到底啥时候发挥药效啊/胳膊露在外面居然还不太冷/半天没看手机了，有没有同事找我审批/不会耽误了元旦上线的什么运营活动吧/去他娘的，我实在没力气看手机”。

一直晕到下午 2 点多还是 39 度，我觉得这药不行，硬让我儿子拿来美林，我自己倒了 10 ml 灌下去了。我媳妇还念叨我，你不能这么吃药，这么吃药会过量，赶紧把美林拿走了。我心里其实计算过，10ml 是 200mg，缓释片也是 200mg，而且距离吃缓释片已经 3 小时了。我自认为没啥问题，但没啥力气跟她争辩，反正已经喝了。

美林效果是真好，没过半小时，发了一身汗，温度降到了 38 度。不知道是原研药的功劳，还是混悬剂的功劳，起效就是比国产杂牌布洛芬缓释片强。一遇到抢购脱销，连这些平时卖不动的杂牌布洛芬都涨价卖，甚至想买还得找渠道。

能站起来了，也能看手机了，赶紧处理了一下如流消息和各种审批，然后再躺下。后来没有再烧到那么高，也没用退烧药，吃了两天有退烧成分的快克。一方面能把持续的低烧压下去一些，一方面压一压咳嗽，让我晕一点儿休息得好。第二天也就这么晕乎乎地过去了。

第三天周六，也是 12 月 31 日，躺在床上看朋友圈各种年终总结，辞旧迎新，实在没什么兴致参与。但起来发现不烧了，就是头略微还有点儿晕，又躺了一上午。到下午觉得精神还不错，周末不能就这么过去，就趁着最暖和的时段带着全家去海淀公园玩了会儿冰。

2022 年 12 月，就这么凑凑合合地过去了。

北京—内蒙赤峰克什克腾旗1800公里自驾游

暑假前看水木“自驾游”版对新疆的讨论十分火热，再加上看到 B 站“徐云流浪中国”到了新疆，原计划是约着几个要好的朋友到新疆自驾一圈。后来因为种种原因吧，集体出游未能成行，甚至全家出游的计划也未能成行。因为媳妇单位对出京严格管控，出京要经过总部的审批，其实就是不希望员工给单位添麻烦。

于是就选择了水木“自驾游”版的另一个目的地——内蒙古赤峰市克什克腾旗，自驾游版主 Borrego 人称“波姐”，在 2018、2019 年整理了多篇非常完善的克旗自驾攻略，发表在了自驾游版和公众号《老司机撸自驾游里》，比如《克什克腾旗完全介绍之自驾路线篇》。

我本想照着波姐的攻略逆时针走个北京到克旗的环线：北京—锡林郭勒盟太仆寺旗—赤峰克旗—承德塞罕坝—北京。但出发当天孩子有个比赛，下午三点才能走，另外感觉这样行程里会有多个地市，会增加遇到疫情的概率，所以就临时设计了一个只路经承德和赤峰两个地级市的行程方案，下面是行程全图：

整个行程 5 天半，总里程 1872 公里，车上时间 39 个小时。

7月30日北京—承德 214km 3小时

因为下午三点多才能出发，第一天没法走太远，所以第一站定在了承德。很多年前参观过避暑山庄，也是人山人海，这次只是想把承德作为中转站。搜索中发现承德市区的豪华酒店并不算很贵，就按有泳池筛选最后选了元宝山假日酒店，想着起码能带娃游游泳。

订完酒店才发现旁边就是承德的《鼎盛王朝康熙大典》实景演出所在地，很可惜当晚的票已经售空了。不过这个演出门口有一条很好的步行街，有不少美食，还有灯光喷泉表演，在步行街走走体验也不错。

7月31日承德—乌兰布统 250km 5小时

本来第二天想去塞罕坝，结果发现乌兰布统并不远，就直接跳过了，计划回程的时候再走塞罕坝（最终还是错过了）。贪图于酒店的设施，上午游了次泳，到元宝山吃了午饭才出发往乌兰布统，没成想居然开了五个小时。

我是从承围高速然后转棋塞线进的塞罕坝，可能因为是周日下午，反方向很多返城的车，导致很难超车，一路速度并不快。棋塞线沿途的风景感觉也比较一般，路两侧都是带围栏的树林，从路上往外看不到啥。而且中间儿子腹痛拉肚子，停了几次车。

走到河北内蒙交界处就开始堵车了，堵了两公里。一个原因是交界处有个景区，沿途像集市一样车流比较乱，另一个是要查看核酸报告。但是进入内蒙届，景色和塞罕坝就迥然不同，一眼望去是连绵起伏的草原，不再有树木遮挡视线。

这天我犯了个错误，傍晚 5 点到酒店以后，气候非常宜人，我只在镇上（乌兰布统苏木）逛了一会儿，没有立即去景区里玩。主要因为没有做功课，不知道乌兰布统景区的收费模式。因为乌兰布统在几个月前才改了收费方式，百度、小红书搜到的都是错的，只有抖音上一个人讲明白了：乌兰布统不再沿路设卡，不过在旅游区内还是圈了几个成片的小景区，在小景区的入口查通票，通票有效期三天。所以我完全可以当天晚上去景区里转一圈，第二天继续玩。

还有一点儿个人经验是：在携程上只能买到 120 元的成人全票，在“克旗文旅公司—乌兰布统景区”公众号里可以买到老人和儿童的半价票，这样就可以刷身份证开车直接入园，不用当场排队去买票了。小景区的入口也有多个，离镇上最近的百草敖包最堵，堵车时可以绕行其它入口进景区。

但不得不吐槽的是，乌兰布统的酒店真坑啊，真是除了大一无是处。基本上拿携程预订价除以 3，相当于它的真实水平。建议去克旗旅游的同志们，能预定品牌连锁还是预定品牌连锁。

我只在乌兰布统住了一晚多兰假日酒店，面盆下水坏的、WiFi 坏的、沙发坏的、电视倒是有台，全是雪花和噪音，卫生间的卫生也不行。后面两天再也不提前预定酒店了，实地查看后还是住了两晚经棚的汉庭。汉庭的房间很小，但是卫生程度和设施还是秒杀这些非连锁酒店。

还有就是“乌兰布统之夜”，晚上 9 点多开始，噼里啪啦的烟花一直放到 11 点多，差不多 10 点是最高峰。也是功课没做好，不知道有这节目，反正也吵得睡不着，要知道倒不如去看看了……

8月1日乌兰布统—景区—经棚（克旗县城）200km 11小时

酒店没早餐，门口的早餐摊一屉小笼包 20 块钱，比北京都贵。走远点儿有一些卖油条的，两块钱一根，价钱还算合理。

这一天大部分时间都在乌兰布统几个小景区里转，核心的问题就是太晒了，让我很后悔没有昨天傍晚入场。欧式风情区里还可以，距离也不是很远，开车走走停停，还算比较惬意。爬了下影视基地那个木栈道，本来挺后悔的，爬着很累，上面亭子里全是飞蚁，也没法休息。但后来看照片，还真属在木栈道上拍的风景比较漂亮。

早上 8 点却又晒又热，从木栈道上下来，我们就决定，只下车观景，不走路或者爬山了。

再说一下骑马。景区里骑马统一价是 100 元/次，如果抱着孩子骑要加 20 元。但是骑马的组织非常混乱，跟菜市场似的，我们在马场里等了半小时才坐到马上，但没想到后面仍然坑爹。一个师傅牵着两到三匹马，互相之间各种蹭，走到一半停下了，也不让下马，问大家要不要跑马，跑一次 200 元。说白了跟旅游购物一个意思，没人花钱大家就都别走了，有人花钱大家都得等着。断断续续有四五个人去跑了马（其实也就不大一圈，10分钟左右），在大太阳底下坐马上等了半个多小时才回去。我抱着女儿坐一匹马，马鞍前后非常窄，还不想挤着孩子，坐了一个多小时很不舒服。

回程问了才知道，100元/次的钱是景区收了，跑马的钱才是这些牵马的师傅挣的。很合理对吧？再也不体验了。

公主湖景区和欧式风情区不在一起，而且隔着老远，有 20 公里左右，路又烂，把我都开疑惑了。中间找了块草坪跟娃一起玩小滑翔机，玩得非常开心。开到了公主湖旁边，发现又得在停车场停完车走进去，直接调头就走。为什么说又？因为将军泡子也是这情况，停车的地方离湖边老远了，得花钱骑马或者自己走进去，这么热的天，还是放弃了。

在乌兰布统景区转到下午3点，开车距离大概八九十公里吧，觉得也审美疲劳了，也不想在乌兰布统住酒店了，就沿着“经乌线（经棚—乌兰布统）”往经棚开了。经乌线前半段景色非常不错，也被标记了“中国北疆风景大道”，从盘山路上有高度的地方俯瞰草原丘陵，很美。

因为一直在景区转，中午没有正式的午餐，在几棵树底下停了一会儿（草原上找个荫凉地儿太难了），吃了些零食。晚上在经棚找了个蒙餐馆，我觉得味道还行，儿子觉得蒙古奶茶好喝。

克什克腾旗人民医院有核酸检测，单人单管是 24 小时的，晚上去做了个核酸。

回到酒店发现，虽然抹了防晒霜（儿童版的），胳膊还是被晒红了，这是晒伤的前兆，赶紧用冷水冲洗。应该主要是玩小滑翔机时候晒伤的，儿子也被晒红了，只有女儿穿的纱长袖，没有大影响。

8月2日经棚—阿斯哈图石林—达里湖—经棚 356km 9小时

鉴于昨天的暴晒体验，我们一致决定尽量开车游玩，不去深入走景区了。所以石林景区没打算进去，主要是方便导航路线。这样走基本上能走全“热阿线（热水镇—阿斯哈图石林）”和“达达线（达青宝拉格牧场—达里诺尔湖）”。

从热水镇往阿斯哈图石林方向走，前半段比较平凡，中段经过黄岗梁（大兴安岭最高峰，海拔2034米）前后，有点儿类似于“经乌线”中段的风光，就是从有盘山公路的高处俯瞰草原。

我个人最喜欢的，是后半段，大概距离阿斯哈图石林 40 多公里开始。前面走过的很多路都是弯弯曲曲，这里开始有长段的接近笔直但是有较大起伏的公路，有点儿新疆自驾游照片里那种一望无垠的感觉。路的两侧都是牧民的草场，远处是起伏的丘陵，非常让人心旷神怡。

走到这里总结出一个经验，在克旗比较美丽的自驾游路段，前后在路边或者路上总会印着“中国北疆风景大道”的标语。但是克旗的公路有一个缺点，就是缺少观景台（跟北京山区道路相比），所以虽说禁止游客在路上停车，但是在车少的路段还是很多人直接停在路上。

热阿线终点是阿斯哈图石林南门，但是在南门前一公里的位置有个分岔路，可以走到阿斯哈图石林西门，据说是最近新修的南门和西门的连接线。所以我就从那里直接转向西门去走达达线了。

达达线就少了热阿线后段那种笔直大道的风景，大多数是弯弯曲曲的。达达线也是阿斯哈图石林西门往外这几十公里风景最优美，而且公路和牧场的落差不大。牧民的草场有围栏不能进，但是围栏外面还是有一些草地，应该属于公路养护区，看到一些游客直接停车扎营。

过了巴彦查干苏木，达达线转向正南，风景就有些乏善可陈了。草原还是草原，但是不再有起伏，和平原差不多。

去往达里湖南岸的路是真的坑爹，路况很差各种炮弹坑，路还很窄，错车只能开到马路边上。还有一些鸡贼的车不往马路边上开，导致每次会车都要做一次心理交锋：你不让我也不让，看谁能挺到最后。多少年没开过这种烂路了，而且还长，有十几公里，抖得人身心俱疲。也是再也不来的体验。

到南岸没有进景区，按照攻略跟着碧海银沙景区门口岔路拦车的人，20 块钱带你找了个湖边进去。但是感觉仍然被坑了。带你进去的时候说里面是自己家开的农家乐，可以在湖边吃饭住宿，结果往里带了五六公里，还是个很荒凉的湖边，没有房子。往里走的时候发现，如果自己沿岔路开进去，多的是 10 块钱就带你到湖边的地方，而且离景区大门还更近一些。

但必须得承认的是，作为内蒙第二大咸水湖，达里湖还是很壮观的。而且沙滩很大，沙子的确是银色的，有很多候鸟，有的鸟看起来很像海鸥。如果有时间的话，可以尝试在湖边住一住，玩玩沙子散散步，感觉应该不错。

本来想在达里湖找个有特色的酒店住一晚，鉴于乌兰布统的经验，没有提前订。让我儿子参观了一下价位最高的将军府蒙古包，他觉得还是更喜欢现代化的汉庭，于是只能再回经棚。

这一天玩下来已经有些累了，也不知道去哪里好，直接回家吧又觉得不甘心。随便找了找发现玉龙沙湖看起来也不错，于是决定第二天去玉龙沙湖。

8月3日经棚—西拉木伦峡谷—玉龙沙湖（翁牛特旗） 333km 6小时

西拉木伦河（西拉沐沦河）是非常长非常宽的一条河，发源于克什克腾旗。所谓的西拉木伦峡谷，是西拉木伦上游的河谷，它是一个很宽的河谷，沿峡谷的公路也并不是在谷底，有上有下，有的在峡谷外侧的高原上。总得来说，不太值得一去，和达里湖情况一样，路况太差，风景不如延庆的百里画廊。“经乌线”上有一个西拉木图峡谷驿站，也就是一个公路休息区，从驿站上远眺一下峡谷，可能是角度最好的地方了。

从克旗开往玉龙沙湖的丹锡高速（丹东—锡林浩特），车是真的稀少，路况也非常好。从经棚西面上了高速以后，差不多五六十公里的路上，只有我一辆车。丹锡高速这段就是沿着蜿蜒的西拉木伦河行进，一路上会看到西拉木伦河1号桥，2号桥，3号桥……

我们预定了玉龙沙湖的集装箱酒店。这个酒店有两种房型，三个位置。木屋房型在大湖边，但是离大湖很远，其实门口望出去是沼泽地，没啥风景；集装箱房型在小湖边，对岸就是沙山，风景比较好；但是集装箱房型也有临湖和不临湖的两排，个人感觉临湖的视角更棒。

房间里苍蝇很多，我们提前在克旗的超市里买了雷达喷雾……先封闭喷了一下房间才入住，后来还是有苍蝇从门口进来，就直接用喷雾喷一下一会儿就挂了。

我们在临湖的阳台上搭了个帐篷，白天虽然很晒，晚上的气候非常宜人。帐篷有纱帐，没有苍蝇，我带两个娃开着露营灯在帐篷里玩到了九点多才回房间睡觉。

8月4日玉龙沙湖—北京 524km 8.5小时

本来准备上午热的时候去泡温泉，结果第一次去忘带温泉票了不让进（温泉位置很远，摆渡车要坐 15 分钟），第二次去说设备故障，还不知道啥时候能修好。去前台闹了一下，才知道是有大人物来视察，要提前排练，所以温泉不接客。很生气，但懒得跟他们纠缠了，拿温泉票退了点儿钱走人。

最后说一下，玉龙沙湖集装箱酒店的早餐自助餐真差，连汉庭的早餐都不如。这地方大概也不会来第二次了。

10点多出发回京，下午2点多到京承高速司马台进京检查站，然后就是漫长的堵车，两个多小时才过检查站。在太师屯服务区疲惫地吃了点儿饭，服务区空调还没开，热得一身汗。

吃完饭一出门，黑云压顶，在京承高速密云段一直狂风暴雨，甚至看不清路。结果开到五环，只下了一丢丢小雨。

儿子给的虎年春节红包

除夕夜里，儿子把一个红包放到了我的衣柜里。大年初一我给儿子发完红包，发现了它。这是我今年收到的唯一一个红包，用彩纸给我写了一段话“爸爸：zhù 你 xīn nián kuài lè 万 shī rú yì”，还画了个笑脸。

不过红包里只有 7 元钱，不知道是什么寓意。我猜测这是他手里现金中的所有的 1 元钱……

但是，我的傻儿子没有给他妈妈发红包，所以他妈看到这个红包，有点儿生气！

用 ARM NEON 实现 _mm_movemask_epi8 的几种方法

背景

上一篇文章中描述了一种使用 SIMD 指令进行并行查找的 B16 哈希表，我让它支持 ARM 时遇到了一些指令集兼容的问题，对这个问题小小地探索了一下。

SSE2 指令集提供了 _mm_movemask_epi8 (pmovmskb) 指令，作用是取所有 8 bit 操作数最高 bit，然后把它们存储到返回值里。对包含 16 个 8 bit 数的 128 bit 输入，取得高位 16 个 bit，存入 32 位的返回值里，并且将返回值的高位置 0。

但是在 ARM 的指令集中，没有这条指令，只能想其它办法替代。

已有实现

通过搜索，找到这个 StackOverflow 问题的回答，里面提到了四种实现方法，我整理了一下接口，分列如下：

// Yves Daoust 的回答 (7 votes): 与 _mm_movemask_epi8 略有不符，要求输入的每个 8 bits 全 0 或全 1
inline uint32_t vmovemask_u8_YvesDaoust(uint8x16_t a) {
    const uint8_t __attribute__ ((aligned (16))) _Powers[16]=
        { 1, 2, 4, 8, 16, 32, 64, 128, 1, 2, 4, 8, 16, 32, 64, 128 };
    // Set the powers of 2 (do it once for all, if applicable)
    uint8x16_t Powers= vld1q_u8(_Powers);
    // Compute the mask from the input
    uint64x2_t Mask= vpaddlq_u32(vpaddlq_u16(vpaddlq_u8(vandq_u8(a, Powers))));
    // Get the resulting bytes
    uint32_t Output;
    vst1q_lane_u8((uint8_t*)&Output + 0, (uint8x16_t)Mask, 0);
    vst1q_lane_u8((uint8_t*)&Output + 1, (uint8x16_t)Mask, 8);
    return Output;
}

// David 对 Yves Daoust 回答最后三行进行了一些改进
inline uint32_t vmovemask_u8_David(uint8x16_t a) {
    const uint8_t __attribute__ ((aligned (16))) _Powers[16]=
        { 1, 2, 4, 8, 16, 32, 64, 128, 1, 2, 4, 8, 16, 32, 64, 128 };
    // Set the powers of 2 (do it once for all, if applicable)
    uint8x16_t Powers= vld1q_u8(_Powers);
    // Compute the mask from the input
    uint64x2_t Mask= vpaddlq_u32(vpaddlq_u16(vpaddlq_u8(vandq_u8(a, Powers))));
    // Get the resulting bytes
    uint32_t Output = vgetq_lane_u64(Mask, 0) + (vgetq_lane_u64(Mask, 1) << 8);
    return Output;
}

// EasyasPi 的回答（4 votes): 标准实现了 _mm_movemask_epi8，被 simde 库采纳，link:
// https://github.com/simd-everywhere/simde/blob/master/simde/x86/sse2.h
inline uint32_t vmovemask_u8_EasyasPi(uint8x16_t input)
{
    // Example input (half scale):
    // 0x89 FF 1D C0 00 10 99 33
    // Shift out everything but the sign bits
    // 0x01 01 00 01 00 00 01 00
    uint16x8_t high_bits = vreinterpretq_u16_u8(vshrq_n_u8(input, 7));
    // Merge the even lanes together with vsra. The '??' bytes are garbage.
    // vsri could also be used, but it is slightly slower on aarch64.
    // 0x??03 ??02 ??00 ??01
    uint32x4_t paired16 = vreinterpretq_u32_u16(vsraq_n_u16(high_bits, high_bits, 7));
    // Repeat with wider lanes.
    // 0x??????0B ??????04
    uint64x2_t paired32 = vreinterpretq_u64_u32(vsraq_n_u32(paired16, paired16, 14));
    // 0x??????????????4B
    uint8x16_t paired64 = vreinterpretq_u8_u64(vsraq_n_u64(paired32, paired32, 28));
    // Extract the low 8 bits from each lane and join.
    // 0x4B
    return vgetq_lane_u8(paired64, 0) | ((uint32_t)vgetq_lane_u8(paired64, 8) << 8);
}

// inspirit 的回答 (1 vote): 标准实现了 _mm_movemask_epi8，但分了上下半边，指令很多
inline uint32_t vmovemask_u8_inspirit(uint8x16_t input)
{
    const int8_t __attribute__ ((aligned (16))) xr[8] = {-7,-6,-5,-4,-3,-2,-1,0};
    uint8x8_t mask_and = vdup_n_u8(0x80);
    int8x8_t mask_shift = vld1_s8(xr);

    uint8x8_t lo = vget_low_u8(input);
    uint8x8_t hi = vget_high_u8(input);

    lo = vand_u8(lo, mask_and);
    lo = vshl_u8(lo, mask_shift);

    hi = vand_u8(hi, mask_and);
    hi = vshl_u8(hi, mask_shift);

    lo = vpadd_u8(lo,lo);
    lo = vpadd_u8(lo,lo);
    lo = vpadd_u8(lo,lo);

    hi = vpadd_u8(hi,hi);
    hi = vpadd_u8(hi,hi);
    hi = vpadd_u8(hi,hi);

    return ((hi[0] << 8) | (lo[0] & 0xFF));
}

我的实现

看到上面这几个方法，我就在想，有没有可能找到一种更高效的实现，用更少的 ARM 指令实现这个功能？经过一段时间的思考，我想到了下面这种方法，我感觉这（可能）是指令数最少的一种实现了。

但这个方法和 YvesDaoust 的方法一样，假设每个 8 bits 都是全 0 或者全 1，这在处理向量比较指令（vceq*, vcgt* 等）结果时是可用的，但在其它场景下未必可用。

 // （可能是）指令数最少的实现，要求输入的每个 8 bits 全 0 或全 1
inline uint32_t vmovemask_u8_solrex(uint8x16_t a) {
    // 先取出相邻两个 uint8 的中间 2 bits，1 bit 属于高 uint8，1 bit 属于低 uint8
    uint16x8_t MASK =  vdupq_n_u16(0x180);
    uint16x8_t a_masked = vandq_u16(vreinterpretq_u16_u8(a), MASK);
    // 再将这 8 个 2 bits 按照不同的偏移进行 SHIFT，使得它们加一起能表示最终的 mask
    const int16_t __attribute__ ((aligned (16))) SHIFT_ARR[8]= {-7, -5, -3, -1, 1, 3, 5, 7};
    int16x8_t SHIFT = vld1q_s16(SHIFT_ARR);
    uint16x8_t a_shifted = vshlq_u16(a_masked, SHIFT);
    // 最后把这 8 个数字加起来
    return vaddvq_u16(a_shifted);
}

性能测试

我非常好奇新方法性能如何，所以我对以上几种方法都进行了 benchmark，然后发现结果跟我想的有点不一样：

方法	重复处理单变量	按序处理数组
`vmovemask_u8_YvesDaoust()`	`536us`	`531us`
`vmovemask_u8_David()`	`189us`	`208us`
`vmovemask_u8_EasyasPi()`	`92us`	`340us`
`vmovemask_u8_inspirit()`	`286us`	`389us`
`vmovemask_u8_solrex()`	`137us`	`166us`

表1：内联函数调用，重复 10 万次

分析

重复处理单变量场景下，对一个固定的 uint8x16_t 变量重复计算 movemask，然后把结果累加起来（避免被优化）。这时候，vmovemask_u8_EasyasPi()胜出。这可能是因为 EasyasPi 的方法只有数值计算，没有寄存器 load，而往往 load/store 指令的耗时是比较长的。

按序处理数组场景下，对一个 10 万个元素数组的每个元素计算 movemask，然后把结果累加起来（避免被优化）。这时候，vmovemask_u8_solrex() 胜出。这可能是因为新方法里的 load 操作与数组元素的 load 操作形成了一定的流水线效果，load 的开销被抵消后，指令数少的性能优势就体现出来了。

从与 _mm_movemask_epi8 接口的一致性来说，还是 EasyasPi 给的实现更合适，所以 simde 库在替换 x86 intrinsics 时也用了这个实现。但探索一下不同的实现，还是能让人对向量指令设计和选择更多一些理解。

最后说回哈希表里 SIMD 并行比较的实现，其实 Facebook F14 里的实现更高效，并没有受 movemask 的思路限制，感兴趣的同学可以自己钻研一下。

2025年12月30日刷新

前两天在知乎上有同学评论了另一种实现，我又重新 benchmark 了一下。可能由于我之前的测试环境是 Mac 下的 ARM Docker，指令的执行效率太低，在新版 MBP 的 M3 芯片上执行时的结论和之前有显著不同。

WebAssembly 实现：

 inline uint32_t vmovemask_u8_webasm(uint8x16_t a) {
    static const uint8x16_t mask = {1, 2, 4, 8, 16, 32, 64, 128, 1, 2, 4, 8, 16, 32, 64, 128};
    uint8x16_t masked = vandq_u8(mask, (uint8x16_t)vshrq_n_s8(a, 7));
    uint8x16_t maskedhi = vextq_u8(masked, masked, 8);
    return vaddvq_u16((uint16x8_t)vzip1q_u8(masked, maskedhi));
}

由于我以前的性能测试代码已不可考，所以我重写了一遍 benchmark 代码，并提交到 github：solrex/demo/cppdemo/arm_movemask_epi8.cpp，在我的 MacBook Pro M3 芯片下测试结果如下：

方法	重复处理单变量	按序处理数组
vmovemask_u8_YvesDaoust()	0.76ns	0.76ns
vmovemask_u8_David()	0.78ns	0.76ns
vmovemask_u8_EasyasPi()	0.77ns	0.76ns
vmovemask_u8_inspirit()	1.03ns	1.02ns
vmovemask_u8_solrex()	0.77ns	0.75ns
vmovemask_u8_webasm()	0.75ns	0.74ns

表2：内联函数调用 100万次

从这个性能测试结果来看，好像使用哪种实现区别已经不大了。那就别计较了，还是使用与 _mm_movemask_epi8 语义完全一致的实现吧，例如 vmovemask_u8_EasyasPi 或者 vmovemask_u8_webasm。

趣谈哈希表优化：从规避 Hash 冲突到利用 Hash 冲突

本文首发于“百度架构师”公众号：https://mp.weixin.qq.com/s/oeuExiW3DYQnBG8HvDgBAg

1 背景

哈希表是一种查找性能非常优异的数据结构，它在计算机系统中存在着广泛的应用。尽管哈希表理论上的查找时间复杂度是 O(1)，但不同的哈希表在实现上仍然存在巨大的性能差异，因而工程师们对更优秀哈希数据结构的探索也从未停止。

1.1 哈希表设计的核心

从计算机理论上来说，哈希表就是一个可以通过哈希函数将 Key 映射到 Value 存储位置的数据结构。那么哈希表设计的核心就是两点：

怎样提升将 Key 映射到 Value 存储位置的效率？
怎样降低存储数据结构的空间开销？

由于存储空间开销也是设计时的一个核心控制点，在受限于有限的空间情况下，哈希函数的映射算法就存在着非常高的概率将不同的 Key 映射到同一个存储位置，也就是哈希冲突。大部分哈希表设计的区别，就在于它如何处理哈希冲突。

当遇到哈希冲突时，有几种常见的解决方案：开放寻址法、拉链法、二次哈希法。但是下面我们介绍两种有趣的、不常见的解决思路，并且引出一个我们新的实现方案 - B16 哈希表。

2 规避哈希冲突

传统哈希表对哈希冲突的处理会增加额外的分支跳转和内存访问，这会让流水线式的 CPU 指令处理效率变差。那么肯定就有人考虑，怎么能完全规避哈希冲突？所以就有了这样一种函数，那就是完美哈希函数（perfect hash function）。

完美哈希函数可以将一个 Key 集合无冲突地映射到一个整数集合中。如果这个目标整数集合的大小与输入集合相同，那么它可以被称为最小完美哈希函数。

完美哈希函数的设计往往非常精巧。例如 CMPH （http://cmph.sourceforge.net/）函数库提供的 CDZ 完美哈希函数，利用了数学上的无环随机 3-部超图概念。CDZ 通过 3 个不同的 Hash 函数将每个 Key 随机映射到 3-部超图的一个超边，如果该超图通过无环检测，再将每个 Key 映射到超图的一个顶点上，然后通过一个精心设计的与超图顶点数相同的辅助数组取得 Key 最终对应的存储下标。

完美哈希函数听起来很优雅，但事实上也有着实用性上的一些缺陷：

完美哈希函数往往仅能作用在限定集合上，即所有可能的 Key 都属于一个超集，它无法处理没见过的 Key；
完美哈希函数的构造有一定的复杂度，而且存在失败的概率；
完美哈希函数与密码学上的哈希函数不同，它往往不是一个简单的数学函数，而是数据结构+算法组成的一个功能函数，它也有存储空间开销、访问开销和额外的分支跳转开销；

但是在指定的场景下，例如只读的场景、集合确定的场景（例如：汉字集合），完美哈希函数可能会取得非常好的表现。

3 利用哈希冲突

即便不使用完美哈希函数，很多哈希表也会刻意控制哈希冲突的概率。最简单的办法是通过控制 Load Factor 控制哈希表的空间开销，使哈希表的桶数组保留足够的空洞以容纳新增的 Key。Load Factor 像是控制哈希表效率的一个超参数，一般来说，Load Factor 越小，空间浪费越大，哈希表性能也越好。

但近年来一些新技术的出现让我们看到了解决哈希冲突的另一种可能，那就是充分利用哈希冲突。

3.1 SIMD 指令

SIMD 是单指令多数据流（Single Instruction Multiple Data）的缩写。这类指令可以使用一条指令操作多个数据，例如这些年非常火的 GPU，就是通过超大规模的 SIMD 计算引擎实现对神经网络计算的加速。

目前的主流 CPU 处理器已经有了丰富的 SIMD 指令集支持。例如大家可接触到的 X86 CPU 大部分都已经支持了 SSE4.2 和 AVX 指令集，ARM CPU 也有 Neon 指令集。但科学计算以外的大部分应用程序，对 SIMD 指令的应用还都不太充分。

3.2 F14 哈希表

Facebook 在 Folly 库中开源的 F14 哈希表有个非常精巧的设计，那就是将 Key 映射到块，然后在块里使用 SIMD 指令进行高效过滤。因为分块的数量比传统的分桶要更小，这相当于人为增加了哈希冲突，然后在块中用 SIMD 指令再解决冲突。具体的做法是这样的：

通过哈希函数对 Key 计算出两个哈希码：H1 和 H2, 其中 H1 用来确定 Key 映射到的块，H2 只有 8 bits，用来在块内进行过滤；
每个块里最多存放 14 个元素，块头有 16 个字节。块头的前 14 个字节，存放的是 14 个元素对应的 H2，第 15 字节是控制字节，主要记录该块里有多少个元素是从上一个块溢出的，第 16 字节是越界计数器，主要记录如果该块空间足够大，应该会被放置多少个元素。
在插入时，当 Key 映射到的块中 14 个位置还有空时，就直接插入；当块已经满时，就增加越界计数器，尝试插入下一个块中；
在查询时，通过待查找 Key 计算得到 H1 和 H2。通过 H1 对块数取模确定其所属的块后，首先读取块头，通过 SIMD 指令并行比较 H2 与 14 个元素的 H2s 是否相同。如果有相同的 H2，那么再比对 Key 是否相同以确定最终结果；否则根据块头的第 16 字节判断是否还需要比对下一个块。

F14 为了充分利用 SIMD 指令的并行度，在块内使用了 H2 这种 8 bits 的哈希值。因为一个 128 bits 宽度的 SIMD 指令可以进行最多 16 个 8 bits 整数的并行比较。虽然 8 bits 哈希值的理论冲突概率 1/256 并不低，但也相当于有 255/256 的可能性省去了逐个 Key 对比的开销，使哈希表能够容忍更高的冲突概率。

4 B16 哈希表

不考虑分块内部的设计，F14 本质上是一个开放寻址的哈希表。每个块头的第 15、16 字节被用于开放寻址的控制策略，只剩 14 个字节留给哈希码，也因而被命名为 F14。

那么我们考虑能不能从另一个角度出发，使用拉链法来组织分块。由于省去了控制信息，每个分块中可以放置 16 个元素，我们把它命名为 B16。

4.1 B16 哈希数据结构

图 1：B16 哈希表数据结构（3元素示例）

上图所示就是用每个分块 3 个元素展示的 B16 哈希表的数据结构。中间绿色的是常见的 BUCKET 数组，存放的是每个分桶中 CHUNK 拉链的头指针。右侧的每个 CHUNK 与 F14 相比，少了控制字节，多了指向下一个 CHUNK 的 next 指针。

B16 也是通过哈希函数对 Key 计算出两个哈希码：H1 和 H2。例如 “Lemon” 的两个哈希码是 0x24EB 和 0x24，使用 H1 的高位作为 H2 一般来说足够了。

在插入时，通过 H1 对桶大小取模计算 Key 所在的分桶，例如 "Lemon" 所在的分桶是 0x24EB mod 3 = 1。然后在 1 号分桶的分块拉链中找到第一个空位，将 Key 对应的 H2 和元素写入该分块。当分块拉链不存在，或者已经装满时，为拉链创建一个新的分块用于装载插入的元素。

在查找时，先通过 H1 找到对应的分桶拉链，然后对每个块进行基于 SIMD 指令的 H2 对比。将每个块的块头 16 字节加载到 128 bits 寄存器中，里面包含了 16 个 H2'，把 H2 也重复展开到 128 bits 寄存器中，通过 SIMD 指令进行 16 路同时比对。如果都不同，那就对比下一个块；如果存在相同的 H2，就继续对比对应元素的 Key 是否与查找的 Key 相同。直到遍历完整条拉链，或者找到对应的元素。

在删除时，首先查找到对应的元素，然后用块拉链最尾部的元素覆盖掉对应的元素即可。

当然，B16 哈希表每个块的元素个数可以根据 SIMD 指令的宽度进行灵活调整，例如使用 256 bits 宽度指令可以选择 32 元素的块大小。但影响哈希表性能的不仅仅是查找算法，内存访问的速度和连续性也非常重要。控制块大小在 16 以内在大多数情况下能充分利用 x86 CPU 的 cache line，是一个较优的选择。

普通的拉链式哈希表，拉链的每个节点都只有一个元素。B16 这种分块式拉链法，每个节点包含 16 个元素，这会造成很多空洞。为了使空洞尽可能的少，我们就必须增加哈希冲突的概率，也就是尽量地缩小 BUCKET 数组的大小。我们经过试验发现，当 Load Factor 在 11-13 之间时，B16 的整体性能表现最好。其实这也相当于把原来存在于 BUCKET 数组中的空洞，转移到了 CHUNK 拉链中，还省去了普通拉链式每个节点的 next 指针开销。

4.2 B16Compact 哈希数据结构

为了进一步压榨哈希表的存储空间，我们还设计了 B16 的只读紧凑数据结构，如下图所示：

图 2：B16Compact 哈希表数据结构（3元素示例）

B16Compact 对哈希表结构做了极致的压缩。

首先它省去了 CHUNK 中的 next 指针，把所有的 CHUNK 合并到了一个数组中，并且补上了所有的 CHUNK 空洞。例如【图 1】中 BUCKET[1] 的拉链中本来有 4 个元素，包含 Banana 和 Lemon，其中头两个元素被补到了【图 2】的 CHUNK[0] 中。以此类推，除 CHUNK 数组中最后一个 CHUNK 外，所有的 CHUNK 均是满的。

然后它省去了 BUCKET 中指向 CHUNK 拉链的指针，只保留了一个指向原拉链中第一个元素所在 CHUNK 的数组下标。例如【图 1】中 BUCKET[1] 的拉链第一个元素被补到了【图 2】的BUCKET[0] 中，那么新的 BUCKET[1] 中仅存储了 0 这个下标。

最后增加了一个 tail BUCKET，记录 CHUNK 数组中最后一个 CHUNK 的下标。

经过这样的处理以后，原来每个 BUCKET 拉链中的元素在新的数据结构中依然是连续的，每个 BUCKET 依然指向第一个包含其元素的 CHUNK 块，通过下一个 BUCKET 中的下标依然可以知道最后一个包含其元素的 CHUNK 块。不同的是，每个 CHUNK 块中可能会包含多个 BUCKET 拉链的元素。虽然可能要查找的 CHUNK 变多了，但由于每个 CHUNK 都可以通过 SIMD 指令进行快速筛选，对整体查找性能的影响相对较小。

这个只读哈希表只支持查找，查找的过程跟原来差异不大。以 Lemon 为例，首先通过 H1=24EB 找到对应的分桶 1，获得分桶对应拉链的起始 CHUNK 下标为 0，结束 CHUNK 下标为 1。使用与 B16 同样的算法在 CHUNK[0] 中查找，未找到 Lemon，然后继续查找 CHUNK[1]，找到对应的元素。

B16Compact 的理论额外存储开销可以通过下式算得：

其中，n 是只读哈希表的元素个数。

当 n 取 100 万，Load Factor 取 13 时，B16Compact 哈希表的理论额外存储开销是 9.23 bits/key，即存储每个 key 所支出的额外开销只有 1 个字节多一点。这几乎可以媲美一些最小完美哈希函数了，而且不会出现构建失败的情况。

B16Compact 数据结构仅包含两个数组，BUCKET 数组和 CHUNK 数组，也就意味着它的序列化和反序列化可以做到极简。由于 BUCKET 中存储的是数组下标，用户甚至不需要将哈希表整个加载到内存中，使用文件偏移即可进行基于外存的哈希查找，对于巨大的哈希表来说可以有效节省内存。

5 实验

5.1 实验设定

实验使用的哈希表的 Key 和 Value 类型均取 uint64_t，Key、Value 对的输入数组由随机数生成器预先生成。哈希表均使用元素个数进行初始化，即插入过程中不需要再 rehash。

插入性能：通过 N 个元素的逐一插入总耗时除以 N 获得，单位是 ns/key；
查询性能：通过对随机的 Key 查询 20 万次（全命中） + 对随机的 Value 查询 20 万次（有可能不命中）获得总耗时除以 40 万获得，单位是 ns/key；
存储空间：通过总分配空间除以哈希表大小获得，单位是 bytes/key。对于总分配空间来说，F14 和 B16 均有对应的接口函数可直接获取，unordered_map 通过以下公式获取：

// 拉链节点总大小
umap.size() * (sizeof(uint64_t) + sizeof(std::pair<uint64_t, uint64_t>) + sizeof (void*)) 
// bucket 总大小
+ umap.bucket_count() * sizeof (void *)
// 控制元素大小
+ 3 * sizeof(void*) + sizeof(size_t);

Folly 库使用 -mavx -O2 编译，Load Factor 使用默认参数；B16 使用 -mavx -O2 编译，Load Factor 设定为 13；unordered_map 使用 Ubuntu 系统自带版本，Load Factor 使用默认参数。

测试服务器是一台 4 核 8G 的 CentOS 7u5 虚拟机，CPU 是 Intel(R) Xeon(R) Gold 6148 @ 2.40GHz，程序在 Ubuntu 20.04.1 LTS Docker 中编译执行。

5.2 实验数据

图 3：插入性能对比

上图中折线所示为 unordered_map、F14ValueMap 和 B16ValueMap 的插入性能对比，不同的柱子显示了不同哈希表的存储开销。

可以看到 B16 哈希表在存储开销明显小于 unordered_map 的情况下，仍然提供了显著优于 unordered_map 的插入性能。

由于 F14 哈希表对 Load Factor 的自动寻优策略不同，在不同哈希表大小下 F14 的存储空间开销存在一定波动，但 B16 的存储开销整体仍优于 F14。B16 的插入性能在 100 万 Key 以下时优于 F14，但是在 1000 万 Key 时劣于 F14，可能是因为当数据量较大时 B16 拉链式内存访问的局部性比 F14 差一些。

图 4：查找性能对比

上图中折线所示为 unordered_map、F14ValueMap、B16ValueMap 和 B16Compact 的查找性能对比，不同的柱子显示了不同哈希表的存储开销。

可以看到 B16、B16Compact 哈希表在存储开销明显小于 unordered_map 的情况下，仍然提供了显著优于 unordered_map 的查找性能。

B16 与 F14 哈希表的查找性能对比与插入性能类似，在 100 万 Key 以下时明显优于 F14，但在 1000 万时略劣于 F14。

值得注意的是 B16Compact 哈希表的表现。由于实验哈希表的 Key 和 Value 类型均取 uint64_t，存储 Key, Value 对本身就需要消耗 16 字节的空间，而 B16Compact 哈希表对不同大小的哈希表以稳定的约 17.31 bytes/key 进行存储，这意味着哈希结构里为每个 Key 仅额外花费了 1.31 个字节。之所以没有达到 9.23 bits/key 的理论开销，是因为我们的 BUCKET 数组没有使用 bitpack 方式进行极致压缩（这可能会影响性能），而是使用了 uint32_t。

6 总结

本文中我们从哈希表设计的核心出发，介绍了两种有趣的、不算“常见”的哈希冲突解决方法：完美哈希函数和基于 SIMD 指令的 F14 哈希表。

在 F14 的启发下，我们设计了 B16 哈希表，使用了更容易理解的数据结构，使得增、删、查的实现逻辑更为简单。实验表明在一些场景下 B16 的存储开销和性能比 F14 还要好。

为追求极致的存储空间优化，我们对 B16 哈希表进行紧致压缩，设计了几乎可以媲美最小完美哈希函数的 B16Compact 哈希表。B16Compact 哈希表的存储开销显著低于 F14 哈希表（介于40%-60%之间），但却提供了颇有竞争力的查询性能。这在内存紧张的场合，例如嵌入式设备或者手机上，可以发挥很大的作用。

新的哈希表设计表明 SIMD 指令的并行化处理能力的有效应用能大幅度提升哈希表对哈希冲突的容忍能力，进而提升查询的速度，并且能帮助哈希表进行极致的存储空间压缩。这让哈希表的设计思路从尽量规避哈希冲突，转向了利用合适的哈希冲突概率来优化计算和存储效率。

使 Netron 支持 PaddlePaddle 模型子图显示

先介绍一下什么是 PaddlePaddle 的模型子图。一般的神经网络都可以表示成一张由算子组成的计算图，但是对一些较为复杂的神经网络，可能会存在一些条件分支。PaddlePaddle 在构建这种条件分支的网络时，会把分支内的计算图单独保存成一张子图。

具体到 PaddlePaddle 的内部数据结构时，每个子图就是 Program 内的一个 Block。这个 Block 内包含该子图的所有中间变量，op 算子和参数等。

目前 PaddlePaddle 的模型可视化主要是依赖 Netron，包括 PadddlePaddle 提供的 VisualDL 工具里内嵌的也是 Netron。

我最近在研究 PaddlePaddle 模型优化的时候，发现 VisualDL 完全不支持子图的可视化。我稍微研究了一下 Netron 的代码，想把子图的可视化给加上。但没想到的是，其实 Netron 本身已经做了 PaddlePaddle 子图结构的解析，只是代码上存在一点儿 bug，导致子图无法被选择出来。

我就修复了一下这个 BUG，提交了一个 PR: https://github.com/lutzroeder/netron/pull/588 。希望对 PaddlePaddle 的用户能有所帮助。

只是 Netron 项目的 Owner lutzroeder 有些奇怪。他不是直接接受这个 PR，而是自己做一些修改后提交一个新的 commit 引用了这个 PR，不知道出于什么目的。这个习惯会让人很难分析出来对 PaddlePaddle 模型解析代码感兴趣的人都是谁，对于维护并不便利。

北医三院眼科就医看病手术攻略

长草了好久，这次发个在医院排队时写的东西。

这已经是我在北医三院眼科耗掉的第四个完整的上午！鉴于医生也很辛苦，我也不想怪罪他们，只好在无聊的等待中总结一点点经验，好让看到的人有所准备。

攻略 1：北医三院已经取消人工挂号，建议通过微信挂号，三日内预约并不难。院内收费支付宝和微信都支持，线上支付很方便。

攻略 2：较确定的眼病不必挂专家号，因为专家号慢而且不一定负责手术。我母亲是确诊的翼状胬肉，希望在北医三院做手术所以挂了个专家号。但是18号整整等了三个小时，到了医生却说他不负责这种手术，给安排了其他主治医生。三院的主治大部分也都是北大医学院毕业的，水平都不差。

攻略 3：术前检查比较耗时，为保证半天内约上，挂号一定要靠前。要是挂的号靠后，那就到现场看看不行就退了改天。

攻略 4：眼科手术分门诊手术和日间手术两种，可提前跟医生说明。日间手术算住院（但不占床位），手续繁琐一点，但保险报销比例高点（外地医保只支持住院）。

攻略 5：在北京常住的外地医保患者，可以提前通过当地医保部门申请医保异地安置。住院时可以拿外地医保卡办手续，支持出院直接结算，不用再拿材料报销。这件事要感谢政府信息化的提升。

攻略 6：北医三院眼科要求手术日 7:45 到医院办理手续，但实际上手术排期不会这么早，所以不必这么早到。目测医生按手术耗时排期，像是倒睫，翼状胬肉切除这种耗时较长的手术，往往被安排到上午最后。我母亲两眼分开做的，第一次 11 点进手术室，第二次 13 点进手术室，基本上都是最后一个手术，生生干等了两个上午。

攻略 7：带大几百的现金。眼科有些耗材不算手术材料，但能缓解疼痛，比如绷带镜。这些耗材是院内商店卖，不走医院处方和收费系统，只收现金。

攻略 8：手术后一定记得跟医生要病历本，如果护士忘了给，就可能要跑几个地方去找，特别耽误时间。

攻略 9：北医三院眼科分两个部分，一个是五官楼眼科，一个是眼视光中心，分布在门诊大楼两侧。复诊、拆线一定要问清楚要不要挂号，挂哪里的号，不然到时挂错了护士会让你退号重挂。我们就因为重挂当日号，拆线时也变成了当日最后一个，从 8 点等到 12 点。

攻略 10：不要侥幸，不要着急。专家号超过 10，复诊号超过 20，普通号超过 80，大概率要排队 2 小时，尤其有些专家 9 点才出诊。所以来早了没用，好好安排时间。太靠后的号不如退了改天，不然检查和治疗做不完，可能要再请假。目测下午比上午人少点，但下午专家也少，酌情安排吧。

攻略 11：北医三院停车场分两个队，能上立体停车楼的小型车队短一点儿，SUV、B 级 C 级车只能停地面的队非常长。非机动车道的队是地面车位，右侧机动车道的队是立体车位。医院停车场便宜，5 元一小时，但是 8 点以后就不要奢望进北医三院停车场了。医院一公里内摄像头管理的路边停车有空位，塔院西街第一小时 6 元，之后 9 元；花园路第一小时 10 元，之后 15 元。周边也有一些商店院里能停，每小时 12 元。塔院小区内停车以前 5 元一小时，最近涨到了 8 元一小时。

感慨一下，虽然我被耗了 4 个完整的上午，但医生也一样动手术到下午 2 点，看门诊到下午 1 点，并不能抱怨医生什么。

只是如果医院信息能更透明一些，信息化程度能更高一些，就医的体验也能更好一些。比如手术明明被安排到最后，就不要让人大清早就过来；排队的时候给大家一个预期等待时间，在线能查到排队情况，患者也不必在这干等。

写完了，还在等！小病还是少来知名三甲医院，太遭罪！

基于 SIMD 指令的 PFOR-DELTA 解压和查找

PFOR-DELTA 是一种经典的有序整数数列压缩算法，被广泛使用在搜索、推荐引擎的倒排索引和召回队列压缩中。PFOR-DELTA 的具体算法这里就不展开了，不了解的同学可以参考它的原始论文《Super-Scalar RAM-CPU Cache Compression》或者做一些搜索工作。

朴素的 PFOR-DELTA 解压主要是逐个对 frame 中的 bitpack 整数进行解压，对朴素 PFOR-DELTA 的优化主要包括对齐的内存访问（aligned memory access, 先按4/8字节偏移读取，然后再移位取得 bitpack）和循环展开（loop unrolling, 由每次循环解压一个整数转成每次循环解压 N 个整数以减少分支判断和访存次数）。通用的 PFOR-DELTA 函数库，往往采取这两种优化方法。

本文主要介绍在目前的先进 CPU 架构下，如何利用 SIMD 指令（如 SSE, AVX）加速 PFOR-DELTA 解压和查找。中文互联网上与之相关的有一篇阿里搜索和推荐团队的文章《索引压缩算法New PForDelta简介以及使用SIMD技术的优化》，但该文章缺乏算法细节且其收益表明对 SIMD 指令的应用并不高效。与该文类似，为简化计，下文主要以不带异常段的 PFOR-DELTA 为例来说明算法细节。

基于 SIMD 的 bit unpacking

PFOR-DELTA 的每个分块中，都是以固定位宽压缩的整数。例如小于 32 的整数，都可以用 5 位来存储，相比于原来的 32 位存储，大大减少了数据的存储空间。但是在使用的时候，我们又必须将压缩的数展开到 32 位，才能进计算和比较操作，将一个数从压缩的位宽展开到使用的位宽，叫做 bit unpacking。

对单独一个 bitpack 的整数来说，展开是非常容易的，通过简单的移位、AND 操作即可完成。但是 SIMD 指令主要提升的是并行化，考虑到 frame 宽度不同，存在各种对齐问题，如何同时进行多个数的 bit unpacking 并不是一件非常直观的事。

下面以 frame 宽度为 9，即每个整数用 9 bit 表示，来详细说明基于现代 CPU 广泛支持的 128位 SIMD 指令的 bit unpacking 算法。256/512 位的 SIMD 算法可依此推演。

如上图所示，如果我们从数组开头加载 128 bit 的数据，其中将会包括 14 个完整的 9 bit 整数，以及多读的 2 个 bit。

为了将每个 9 bit 展开成 32 bit，在只有 128 位寄存器的情况下，我们只能 4 个 4 个地展开。首先需要将头 4 个 9 bit 整数移动到寄存器 32 位偏移的位置。Intel 提供了 _mm_shuffle_epi8 intrinsic 可以根据重整参数重新排布 128 位寄存器的内容，但可惜的是它最小粒度只能按 byte 重整，这也就意味着我们必须将 9 bit 整数所在的整个 2 byte 移动到 32 位偏移的位置。对应的代码是：

// 考虑到 litten endian，实际上 shufkey 内容为：
// 00018080 01028080 02038080 03048080
__m128i shufkey = {0x8080020180800100, 0x8080040380800302};
v = _mm_shuffle_epi8(v, shufkey);

这时候，128 位寄存器中的每个 32 位槽位中都包含一个 9 bit 整数，但可惜的是它都包含了前后数字的一些冗余 bit。下面这张图，说明了如何用 SIMD 指令消除这些冗余 bit。

前面说过，对一个整数做 unpack 可以完全用移位和 AND mask 来实现，对多个整数依然如此。但由于各槽位中 9 bit 整数的对齐不同，移位 bit 数也不同。例如：第一个槽位右移 0 位，第二个槽位右移 2 位，第三个操作右移 2 位，第四个槽位右移 3 位。

可是 SSE 的移位指令只能支持各槽位同等位数的移位，无法支持这样各槽位不同位数的移位。我们不得不用代价更高昂的其它指令来实现分槽位不同移位，先用基于 2 次幂的向量乘法实现左移对齐 9 bit 整数，然后再统一右移，统一 mask。不使用 2 次幂除法的原因是除法的成本更高。对应到代码是：

// 通过向量乘法实现各 DW 槽位中 9 bit 整数左移对齐。当然参数可以换成常数。
v = _mm_mullo_epi32(v, _mm_set_epi32(8, 4, 2, 1));
// 所有 DW 右移 3 位
v = _mm_srli_epi32(3);
// 通过 and mask 掉 9 bit 之外多余的 bit。当然参数可以换成常数。
v = _mm_and_si128(v, _mm_set1_epi32(0x1ff));

这样，我们就实现了 9 bit 整数的 unpacking。上述算法具备通用性，对于其它的 frame 宽度，只是 shuffle、移位、乘法、mask 的参数不同，处理过程并无区别。

认真的读者可能会有疑问：第一张图为什么做了两遍 shuffle？这是考虑到了奇数位 bit packing 的特殊性。

对于偶数位（2，4，6，8）的 bit packing，一次解压 4 个整数，解压的位宽是可以被 8 整除的，所以每次解压都可以从字节边界开始，所有算法参数都相同；对于奇数位（3, 5, 7, 9），一次解压 4 个整数，解压的位宽是不能被 8 整除的，所以第二轮解压不能从字节边界开始，第二轮解压的算法参数与第一轮不同。但解压 8 个整数后，位宽就对齐到字节边界了。所以说：frame 位宽为偶数的 SIMD unpacking，循环 block 可以是 4*位宽；但 frame 位宽为奇数的 SIMD unpacking，循环 block 只能是 8*位宽。如果 AVX 指令可用，可以使用 256 位的 SIMD 指令，能大大缓解这个问题。

不失其一般性，可以看到我们只用了 4 条 SIMD 计算指令，就完成了 4 个整数的 bit unpacking，其效率较逐一 unpacking 高了很多，并且可以推及到 256 位和 512 位的情形得到更高加速比。

本节内容主要参考了论文《SIMD-Scan: Ultra Fast in-Memory Table Scan using on-Chip Vector Processing Units》。

基于 SIMD 的 delta 计算

在 PFOR-DELTA 算法中，每个整数其实是 delta，需要把所有前序的整数加起来才是真正所要的数据。参考上节，我们虽然解压出来了 {v0, v1, v2, v3}，但实际上需要的却是 {v0, v0+v1, v0+v1+v2, v0+v1+v2+v3}。

将 __m128i 转成一个数组，然后再循环相加是比较简单的思路。但我们也可以直接用三条 SIMD 指令来实现 delta 计算：

// {v0, v1, v2, v3} + {0, 0, v0, v1} = {v0, v1, v0+v2, v1+v3}
v = _mm_add_epi32(_mm_slli_si128(v, 8), v);
// {v0, v1, v0+v2, v1+v3} + {0, v0, v1, v0+v2} = {v0, v0+v1, v0+v1+v2, v0+v1+v2+v3} 
v = _mm_add_epi32(_mm_slli_si128(v, 4), v);
// {v0, v0+v1, v0+v1+v2, v0+v1+v2+v3} + {acc3, acc3, acc3, acc3}
acc = _mm_add_epi32(v, _mm_shuffle_epi32(acc, 0xff));

同样，不失一般性，这种错位相加的方法完全可以推广到 8 维整数向量的 delta 计算，可以推广到 256 位和 512 位的情形得到更高的加速比。

本节内容主要参考了论文《SIMD Compression and the Intersection of Sorted Integers》。

基于 SIMD 的查找比较

对 PFOR-DELTA 解压完成之后对有序数组，如果想找到某个整数的位置，我们还需要逐个进行比较。这种比较，也可以用 SIMD 指令完成：

// 初始化一次
__m128i key = _mm_set1_epi32(v_to_find);
// 向量比较
v = _mm_cmplt_epi32(key, acc);
// 比较结果处理
int res = _mm_movemask_epi8(v);
if (res != 0) {
  index += __builtin_ctz(res) >> 2;
} else {
  index += 4;
}

总结

综上，本文描述了完全使用 SIMD 指令进行 PFOR-DELTA 解压和查找的详细算法，给出了在 SSE 指令集下的具体代码，并且可以推广到更高的数据宽度下。至于优化的收益，将根据基线实现的不同存在差异，感兴趣的读者可以自行实现比较一下。

此外，上文的实现主要着眼通用性，针对特定的小宽度整数，其实可以使用更小的计算粒度以增大并行度。对性能有苛求的读者可自行研究。

ABTest 平台设计 - 流量分布问题

通过前三篇文章，大家可以了解到一个基本的 ABTest 平台架构建设的要点，看起来构建起一个生产环境可用的 ABTest 平台难度不大。但如果想把这个平台做得更强大，还有很多细节地方要注意。下面举两个常见的细节问题。

跨层分桶不完全正交

理论上来讲，如果每层分桶都是采取的独立不相关的 hash 算法，那么层和层之间的流量应该是完全正交且服从均匀分布的。举个例子：如果每层分 10 个桶，那么第二层的 1 号桶内，应该有第一层每个桶里的 1/10 的用户。

但从实际上来讲，很多情况下我们使用的 hash 算法没有那么地“强”，会导致分桶没那么地随机和均匀。比如几年前非常流行的 MurmurHash，也被 SipHash 的作者找到了攻击的方法，他们更推荐使用更强的 SipHash / HighwayHash。

还有就是均匀分布仅仅是统计意义上的期望，而不是实际的效果。比如我们有 1-10 十个数，用 hash 算法一定能保证把它们分到 10 个桶里，每个桶里 1 个数吗？

只不过大多时候，在统计意义上能保证基本的均匀，对大部分产品来说也够用了。

对于一些强迫症公司，或者用户数还没有达到统计意义上可分又开始早早做 ABTest 的公司，或者从数据观察的确存在较大的实验间干涉的公司，可能会做这样的一个事，人工构造层间正交分桶。

具体做法是这样的：先用 hash 算法（或其它抽样算法）将用户分成桶数的平方个最小流量单元，然后再选取这些流量单元组成每个分层。比如要构造 2 层，每层 3 个分桶的用户分层，先将用户分为 3*3 个流量单元，那么两层就可以这样构造：

Layer 1: [1, 2, 3] [4, 5, 6] [7, 8, 9]
Layer 2: [1, 4, 7] [2, 5, 8] [3, 6, 9]

可以看到第二层的每一个桶，都包含第一层里所有桶的 1/3 用户。通过精巧地构造来实现层间的正交分桶，可以有效地降低层间实验互相干涉的情况。

发版造成指标波动

当实验本身受到 APP 版本一定影响的时候，AB 分组可能会由于升级节奏不同，导致 AB 指标波动完全不可比。

举一个例子：如果新版本使用时长会上升 10%，正常情况下实验分组 A 比分组 B 使用时长上升 3%。那么如果分组 A 用户升级新版本占比 30%，分组 B 用户升级新版本占比 70%，结果会是怎样呢？

分组 A：70*1.03 + 30*1.1*1.03 = 106.09
分组 B：30 + 70*1.1 =  107

分组 A 反而比分组 B 的数据更差！当然，这里为了效果，举的例子比较极端。实际的情况可能是在发版收敛期间，ABTest 的指标波动较大。

而且升级动作本身对活跃用户和非活跃用户有一定的筛选作用，产生的行为和数据也是有偏的，很难有完美的解决办法。避开发版收敛时段，或者对数据进行多维的分析和组织，也许有一定帮助。

结语

按照我以前的风格，这本应是一篇文章。但在信息快消时代，我发现自己也没耐心读长文了，所以就拆成一个系列发布了。

这篇文章主要从平台建设的角度出发，讨论了一些平台设计中要考虑到的关键功能点，希望能对读者有所助益。至于如何科学地进行 ABTest 实验设计和效果分析，不是我擅长的部分，就不再后续展开了。

Q6: Google 为站点设计了哪些特征？

前言

Q1: Google 的索引分了几层（Tier）？依据什么？

Q2: Tier 内的 scaledSelectionTierRank 有什么作用？

Q3: Google 搜索系统主要分成几个部分？

爬虫系统：Trawler

去重系统：WebMirror

离线索引构建系统：Segindexer + Alexandria

在线索引服务系统：Mustang 和 TeraGoogle

实时索引服务系统：Hivemind（muppet）

查询汇聚系统：SuperRoot

Query 改写模块：QRewrite

摘要模块：SnippetBrain

入口服务：GWS

Q4: TeraGoogle 是怎样一套系统？

Q5: Google 的文档是什么概念？

Aravind Srinivas 2024年6月20日采访节选

Lex Fridman (02:03:52)

Aravind Srinivas (02:03:57)

Lex Fridman (02:05:25)

Aravind Srinivas (02:05:38)

Aravind Srinivas 2023年12月14日采访节选

Aravind Srinivas (28:08)

分析（在2024年8月）

Prefix Caching

限制

实现

Prompt Caching

原理

(Re)scheduling 开销

KV Cache 重读

可调优能力

论文

假设条件

数学原理

逆向恢复 logits

无法输出的 Token

函数功能

SSE 版本

AVX 版本

NEON 版本

参考

1. nvidia-dcgm 服务启动成功，但又没完全成功

2. 查询部分指标 DCGM_FI_PROF_* 时出错

3. DCGM_FI_DEV_NVLINK_BANDWIDTH_TOTAL 的单位

4. NCGM-Exporter 的采集延迟和精度

用 GPT-2 Tokenizer 编码一段中文

GPT-2 Tokenizer 词典中包含中文的 Token 数量

GPT-2 Tokenizer 词典中包含英文的 Token 数量

GPT-2 Tokenizer 词典中最长的 Token 是什么

Codex Tokenizer 提升代码处理效率的 Trick

在中文数据集上训练的 Tokenizer 表现如何？

Tokenizer 的效率意味着什么

原始 BPW 定义

用 BPW 表示交叉熵

用 BPW 表示损失指标

GPT-4 的 BPW 指标

7月30日 北京—承德 214km 3小时

7月31日 承德—乌兰布统 250km 5小时

8月1日 乌兰布统—景区—经棚（克旗县城）200km 11小时

8月2日 经棚—阿斯哈图石林—达里湖—经棚 356km 9小时

8月3日 经棚—西拉木伦峡谷—玉龙沙湖（翁牛特旗） 333km 6小时

8月4日 玉龙沙湖—北京 524km 8.5小时

背景

已有实现

我的实现

性能测试

分析

2025年12月30日刷新

1 背景

1.1 哈希表设计的核心

2 规避哈希冲突

3 利用哈希冲突

3.1 SIMD 指令

3.2 F14 哈希表

4 B16 哈希表

4.1 B16 哈希数据结构

4.2 B16Compact 哈希数据结构

5 实验

5.1 实验设定

7月30日北京—承德 214km 3小时

7月31日承德—乌兰布统 250km 5小时

8月1日乌兰布统—景区—经棚（克旗县城）200km 11小时

8月2日经棚—阿斯哈图石林—达里湖—经棚 356km 9小时

8月3日经棚—西拉木伦峡谷—玉龙沙湖（翁牛特旗） 333km 6小时

8月4日玉龙沙湖—北京 524km 8.5小时