蚊章汇 - Simon Arneaud
type: channel
link: https://linuxcn.bwsl.wang/author/1292/
description: Simon Arneaud
items: Djinn：一个受 Jinja2 启发的代码生成器和模板语言
items: 将自己作为承包商而定价的基础原则
items: 扩展一个 GraphQL 网站
items: 现实中的应用程序是如何丢失数据？
items: 一次 Docker 镜像的逆向工程
items: 离开 Google：五年以来
items: 为什么排序的复杂度为 O(N log N)
items: 在软件部署中使用 strace 进行调试
items: 面向对象编程和根本状态
items: 为什么 const 无法让 C 代码跑得更快？

Djinn：一个受 Jinja2 启发的代码生成器和模板语言
type: item
date: 2022-07-04T18:17:00+08:00
description: 代码生成器是非常有用的工具。我有时使用 jinja2 的命令行版本来生成高度冗余的配置文件和其他文本文件，但它在转换数据方面功能有限。显然，Jinja2 的作者有不同的想法，而我想要类似于 列表推导 list comprehensions 或 D 语言的 可组合范围 composable range 算法之类的东西。我决定制作一个类似于 Jinja2 的工具，但让我可以通过使用范围算法转换数据来生成复杂的文件。这个想法非常简单：一个直接用 D 语言代码重写的模板语言。因为它 就是 D 语言，它可以支持 D 语言所能做的一切。我想要一个独立的代码生成器，但是由于 D 语言的 mixin 特性，同样的模板语言可以作为嵌入式模板语言工作（例如，Web 应用程序中的 HTML）。有关该技巧的更多信息，请参阅 这篇 关于在编译时使用 mixins 将 Brainfuck 转换为 D 和机器代码的文章。像往常一样，源码在 GitLab 上。这篇文章中的例子也可以在这里找到。Hello world 示例这是一个演示这个想法的例子：Hello [= retro("dlrow") ]! [: enum one = 1; :] 1 + 1 = [= one + one ] [= some_expression ] 类似于 Jinja2 中的 {{ some_expression }}，它在输出中呈现一个值。[: some_statement; :] 类似于 {% some_statement %} ，用于执行完整的代码语句。我更改了语法，因为 D 也大量使用花括号，并且将两者混合使模板难以阅读（还有一些特殊的非 D 指令，比如 include，它们被包裹在 [< 和 >] 中）。如果你将上面的内容保存到一个名为 hello.txt.dj 的文件中并运行 djinn 命令行工具，你会得到一个名为 hello.txt 的文件，其中包含你可能猜到的内容：Hello world! 1 + 1 = 2 如果你使用过 Jinja2，你可能想知道第二行发生了什么。Djinn 有一个简化格式化和空格处理的特殊规则：如果源代码行包含 [: 语句或 [< 指令但不包含任何非空格输出，则整行都会被忽略输出。空行则仍会原样呈现。生成数据好的，现在来讲一些更实用的东西：生成 CSV 数据。x,f(x) [: import std.mathspecial; foreach (x; iota(-1.0, 1.0, 0.1)) :] [= "%0.1f,%g", x, normalDistribution(x) ] 一个 [= 和 ] 对可以包含多个用逗号分隔的表达式。如果第一个表达式是一个由双引号包裹的字符串，则会被解释为 格式化字符串。下面是输出结果：x,f(x) -1.0,0.158655 -0.9,0.18406 -0.8,0.211855 -0.7,0.241964 -0.6,0.274253 -0.5,0.308538 -0.4,0.344578 -0.3,0.382089 -0.2,0.42074 -0.1,0.460172 0.0,0.5 0.1,0.539828 0.2,0.57926 0.3,0.617911 0.4,0.655422 0.5,0.691462 0.6,0.725747 0.7,0.758036 0.8,0.788145 0.9,0.81594 制作图片这个例子展示了一个图片的生成过程。经典的 Netpbm 图像库定义了一堆图像格式，其中一些是基于文本的。例如，这是一个 3 x 3 向量的图像：P2 # PGM 格式标识 3 3 # 宽和高 7 # 代表纯白色的值（0 代表黑色） 7 0 7 0 0 0 7 0 7 你可以将上述文本保存到名为 cross.pgm 之类的文件中，很多图像工具都知道如何解析它。下面是一些 Djinn 代码，它以相同的格式生成 Mandelbrot 集 分形：[: import std.complex; enum W = 640; enum H = 480; enum kMaxIter = 20; ubyte mb(uint x, uint y) { const c = complex(3.0 * (x - W / 1.5) / W, 2.0 * (y - H / 2.0) / H); auto z = complex(0.0); ubyte ret = kMaxIter; while (abs(z) <= 2 && --ret) z = z * z + c; return ret; } :] P2 [= W ] [= H ] [= kMaxIter ] [: foreach (y; 0..H) :] [= "%(…

将自己作为承包商而定价的基础原则
type: item
date: 2022-01-20T17:54:00+08:00
description: 我职业生涯的大部分时间都是自由职业者。有时候，我也会和一些想要辞掉全职工作去做一些承包或服务业务的人聊天。到目前为止，我们新手最常犯的错误就是为自己定价。以 这篇有用的博客文章为例，它分析了美国雇员与自由职业者的收入间的对比。据估计，在美国，作为一名自由职业者，你需要获得 14 万美元的收入，才能获得相当于 10 万美元的雇员薪酬。我记得当我第一次创业时，我发现这样的计算非常有用。而，有些人看到结果会想：“哎呀，如果我是自由职业者，我得赚 1.4 倍的钱。我真的能做到吗？”不，不，不，这种想法是落后的。如何给自己定价让我们举个例子。假设你是一名全职软件工程师，年收入 10 万美元，你正考虑转成承保。当你是自由职业者时候，你必须像做企业一样思考，因为这就是你的谋生方式。所以，你必须把所有的成本加起来，并计算出如何收回这些成本。电子表格的口碑很差（有一些很好的理由），但它们实际上非常有用，尤其是对这些东西（以及作为企业主要进行的许多其他计算）。第一个要加入统计的成本是那 10 万美元。如果这听起来很奇怪，那就是所谓的“机会成本”。你本可以继续工作以赚到 10 万美元；而没有赚到这 10 万美元，实际上是在规划业务时的一种成本。把这一费用和其他你实际使用的任何其它就业福利一起记下来。如果你的雇主提供工作日午餐，那就加上一年中每个工作日午餐的费用。如果你的雇主为员工提供健身软件的折扣，但你却没有使用该软件，那么不要将该福利作为机会成本。其他费用取决于你在做什么和你住在哪里。员工医疗保险在澳大利亚不像在美国那么重要。另一方面，强制性养老金支付（类似于美国的 401(K) 计划）是一个大问题。我有自己的公司，我的主要非工资成本是保险、会计/档案、法律（合同审查等）、债务催收和各种在线服务成本。如果你在计算一些耐用的东西（比如一张桌子），把成本除以你预计使用该东西的年数。总之，到目前为止，这基本上就是 Caleb 的博客文章中的内容，所以为了简单起见，我将假设同样的 10 万美元的名义工资和 14 万美元的等效业务成本。（当然，一切都要根据自己的情况进行调整。）现在你需要想办法收回这笔成本。澳大利亚一年大约有 255 个工作日，所以如果你能把它们全部外包出去，你每天要收取 550 美元（外加销售税）。在现实中，你不可能为一整年的工作计费。我采取了一种风险更高的方法，在我目前从事自营职业的过去 6 年里，我的平均回报率约为 60%-70%。埃森哲的年度财务报告 说他们的承包商的“利用率”大约为 90%，我想这意味着他们付费了 90% 的总工作日的费用。让我们假设你的工作适度，75% 的工作日都有付账。这意味着你可以在 255 天的 75%（即 191 天） 里收回了 14 万美元的成本，每天开出 730 美元的账单（加上销售税）。误区刚接触合同的人通常会对这样的数字做出反应，并会想，“见鬼？！这么高啊！”。这只是一个计算示例，但服务价格通常相当于你天真猜测的全职雇员工资的两倍或两倍以上。然而，这日薪是通过一个简单的计算得出的，那就是你需要收取多少钱才能获得相当于 10 万美元的工资。这是一回事。不这样想才是关键的错误。新的承包商往往还不敢确定，他们要求那么多，听起来是不是很贪婪？如果你的客户有考虑采购你，他们也在做大致相同的计算。“我可以付给 Gentle Blog Reader 每天 730 美元，只要我愿意，我也可以花大约 14 万美元雇佣一个我甚至不是每天都真正需要的全职雇员。”从雇主的角度来看，10 万美元的薪水实际上也不是 10 万美元。把价格建立在名义基本工资的基础上是没有意义的。即使你是在销售 B2C 产品，你的潜在竞争对手也不会降价，至少不会持续降价。为什么这很重要这个具体的例子是针对承包的，但这是商业经济学的一条基本规则：除非你正在尝试一些风险极高的高收入行为（我们知道 Pets.com 的结果），否则你需要计算出你的成本，并设定足够高的价格来弥补这些成本。一些人仍然对他们需要设定的价格感到不安，他们认为降低价格是合理的。也许他们会这样想:“我是个很好的人，如果我每天只收 400 美元，我的客户会更高兴。”问题是你得不到同样的客户。那些愿意为雇员支付 10 万美元年薪的客户，不会为承包商支付 400 美元一天来做同样的工作。相反，在实践中，你可能会得到一些好客户，他们只是没有每天 730 美元的预算，但同时你也会得到一大堆非常糟糕的客户。想想看。如果一个陌生人以 50 美元的价格卖给你一枚看起来很精美的钻戒，你会付钱吗？还是宁愿以正常价格买另一枚戒指？我要强调的是，我只是从 Caleb 的博客文章中提取了数据，而且一切都是相对的。用你自己的数字代替吧。在世界上大多数地区，每天 400 美元可能是一个令人难以置信的价格。然而，…

扩展一个 GraphQL 网站
type: item
date: 2021-11-14T19:34:20+08:00
description: 我通常会抽象地总结我为他人所做的工作（出于显而易见的原因），但是我被允许公开谈论一个网站：Vocal 。我去年为它做了一些 SRE 工作。实际上早在 2 月份，我就在 GraphQL 悉尼会议上做过一次演讲，不过这篇博客推迟了一点才发表。Vocal 是一个基于 GraphQL 的网站，它获得了人们的关注，然后就遇到了可扩展性问题，而我是来解决这个问题的。这篇文章会讲述我的工作。显然，如果你正在扩展一个 GraphQL 站点，你会发现这篇文章很有用，但其中大部分内容讲的都是当一个站点获得了足够的流量而出现的必须解决的技术问题。如果你对站点可扩展性有兴趣，你可能想先阅读 最近我发表的一系列关于可扩展性的文章。VocalVocal 是一个博客平台，内容包括日记、电影评论、文章评论、食谱、专业或业余摄影、美容和生活小贴士以及诗歌，当然，还有可爱的猫猫和狗狗照片。Vocal 的不同之处在于，它允许人们制作观众感兴趣的作品而获得报酬。作者的页面每次被浏览都可以获得一小笔钱，还能获得其他用户的捐赠。有很多专业人士在这个平台上展示他们的工作，但对于大多数普通用户来说，他们只是把 Vocal 当作一个兴趣爱好，碰巧还能赚些零花钱作为奖励。Vocal 是新泽西初创公司 Jerrick Media 的产品，更新：Jerrick Media 已经更名为 Creatd，在纳斯达克上市。2015 年，他们与 Thinkmill 合作一起开发，Thinkmill 是一家悉尼中型软件开发咨询公司，擅长 JavaScript、React 和 GraphQL 开发。剧透不幸的是，有人告诉我，由于法律原因，我不能提供具体的流量数字，但公开的信息可以说明。Alexa 对所有网站按照流量进行排名。这是我演讲中展示的 Alexa 排名图，从 2019 年 11 月到今年 2 月，Vocal 流量增长到全球排名第 5567 位。曲线增长变慢是正常的，因为它需要越来越多的流量来赢得每个位置。Vocal 现在排名 4900 名左右，显然还有很长的路要走，但对于一家初创公司来说，这一点也不寒酸。大多数初创公司都很乐意与 Vocal 互换排名。在网站升级后不久，Creatd 开展了一项营销活动，使流量翻了一番。在技术方面，我们要做的就是观察仪表盘上的上升的数字。自发布以来的 9 个月里，只有两个平台问题需要员工干预：3 月份每五年一次的 AWS RDS 证书轮换，以及一款应用推出时遇到的 Terraform 错误。作为一名 SRE，我很高兴看到 Vocal 不需要太多的平台工作来保持运行。更新：该系统也抗过了 2020 年的美国大选，没有任何意外。以下是本文技术内容的概述：技术和历史背景从 MongoDB 迁移到 Postgres部署基础设施的改造使应用程序兼容扩展措施让 HTTP 缓存发挥作用其他一些性能调整一些背景信息Thinkmill 使用 Next.js（一个基于 React 的 Web 框架）构建了一个网站，和 Keystone 在 MongoDB 前面提供的 GraphQL API 进行交互。Keystone 是一个基于 GraphQL 的无头 CMS 库：在 JavaScripy 中定义一个模式，将它与一些数据存储挂钩，并获得一个自动生成的 GraphQL API 用于数据访问。这是一个自由开源软件项目，由 Thinkmill 提供商业支持。Vocal V2Vocal 的第一版就受到了关注，它找到了一个喜欢它的用户群，并不断壮大，最终 Creatd 请求 Thinkmill 帮助开发 V2，并于去年 9 月成功推出。Creatd 员工避免了 第二个系统效应，他们一般都是根据用户的反馈进行改变，所以他们 主要是 UI 和功能更改，我就不赘述了。相反，我将讨论下我的工作内容：使新站点更加健壮和可扩展。声明：我很感谢能与 Creatd 以及 Thinkmill 在 Vocal 上的合作，并且他们允许我发表这个故事，但 我仍然是一名独立顾问，我写这篇文章没有报酬，甚至没有被要求写它，这仍然是我自己的个人博客。迁移数据库Thinkmill 在使用 MongoDB 时遇到了几个可扩展性问题，因此决定升级到 Keystone 5 以利用其新的 Postgres 支持。如果你从事技术工作的时间足够长，那你可能还记得 00 年代末的 “NOSQL” 营销，这可能听起来很有趣。NoSQL 的一个重要特点是，像 Postgres 这样的关系数据库（SQL）不像 MongoDB 这样“网站级规模”的 NoSQL 数据库那样具有可扩展性。从技术上将，这种说法是正确的，但 NoSQL 数据库的可扩展性来自它可以有效处理各种查询的折衷。简单的非关系数据库（如文档数据库和键值数据库）有其一席之地，…

现实中的应用程序是如何丢失数据？
type: item
date: 2021-07-20T14:27:45+08:00
description: 现代应用程序开发的一大优点是，像硬件故障或如何设置 RAID 这类问题是由云提供商操心的。优秀的云供应商不太可能丢失你的应用数据，所以有时我会被询问现在为什么还要备份？下面是一些现实世界的故事。故事之一第一个故事来自一个数据科学项目：它基本上是一个从正在进行的研究中来收集数据的庞大而复杂的管道，然后用各种不同的方式处理以满足一些尖端模型的需要。这个面向用户的应用程序还没有推出，但是一个由数据科学家和开发人员组成的团队已经为建立这个模型和它的数据集工作了好几个月。在项目中工作的人有他们自己的实验工作的开发环境。他们会在终端中做一些类似 export ENVIRONMENT=simonsdev 的事情，然后所有在终端上运行的软件都会在那个环境下运行，而不是在生产环境下。该团队迫切需要推出一个面向用户的应用程序，以便那些花钱的人能够从他们几个月的投资中真正看到一些回报。在一个星期六，一位工程师试图赶工一些工作。他在晚上很晚的时候做完了一个实验，决定收拾东西回家。他启动了一个清理脚本来删除他的开发环境中的所有内容，但奇怪的是，这比平时花费了更长的时间。这时他意识到，他已经忘记了哪个终端被配置为指向哪个环境。（LCTT 译注：意即删除了生产环境。）故事之二第二个故事来自于一个商业的网页和手机应用。后端有一个由一组工程师负责的微服务体系结构。这意味着部署需要协调，但是使用正式的发布过程和自动化简化了一些。新代码在准备好后会被审查并合并到主干中，并且高层开发人员通常会为每个微服务标记版本，然后自动部署到临时环境。临时环境中的版本会被定期收集到一个元版本中，在自动部署到生产环境之前，该版本会得到各个人的签署（这是一个合规环境）。有一天，一位开发人员正在开发一个复杂的功能，而其他开发该微服务的开发人员都同意将他们正在开发的代码提交到主干，也都知道它还不能被实际发布。长话短说，并不是团队中的每个人都收到了消息，而代码就进入了发布管道。更糟糕的是，那些实验性代码需要一种新的方式来表示用户配置文件数据，因此它有一个临时数据迁移，它在推出到生产环境时运行，损坏了所有的用户配置文件。故事之三第三个故事来自另一款网页应用。这个有一个更简单的架构：大部分代码在一个应用程序中，数据在数据库中。然而，这个应用程序也是在很大的截止日期压力下编写的。事实证明，在开发初期，当彻底更改的数据库架构很常见时，添加一项功能来检测此类更改并清理旧数据，这实际上对发布前的早期开发很有用，并且始终只是作为开发环境的临时功能。不幸的是，在匆忙构建应用的其余部分并推出时，我们忘记了这些代码。当然，直到有一天它在生产环境中被触发了。事后分析对于任何故障的事后分析，很容易忽视大局，最终将一切归咎于一些小细节。一个特例是发现某人犯了一些错误，然后责怪那个人。这些故事中的所有工程师实际上都是优秀的工程师（雇佣 SRE 顾问的公司不是那些在长期雇佣中偷工减料的公司），所以解雇他们，换掉他们并不能解决任何问题。即使你拥有 100 倍的开发人员，它仍然是有限的，所以在足够的复杂性和压力下，错误也会发生。最重要的解决方案是备份，无论你如何丢失数据（包括来自恶意软件，这是最近新闻中的一个热门话题），它都能帮助你。如果你无法容忍没有副本，就不要只有一个副本。故事之一的结局很糟糕：没有备份。该项目的六个月的数据收集白干了。顺便说一句，有些地方只保留一个每日快照作为备份，这个故事也是一个很好的例子，说明了这也会出错：如果数据丢失发生在星期六，并且你准备在星期一尝试恢复，那么一日备份就只能得到星期日的一个空数据备份。故事之二并不算好，但结果要好得多。备份是可用的，但数据迁移也是可逆的。不好的部分是发布是在推出前完成的，并且修复工作必须在生产站点关闭时进行编码。我讲这个故事的主要原因是为了提醒大家，备份并不仅仅是灾难性的数据丢失。部分数据损坏也会发生，而且可能会更加混乱。故事之三还好。尽管少量数据永久丢失，但大部分数据可以从备份中恢复。团队中的每个人都对没有标记极其明显的危险代码感到非常难过。我没有参与早期的开发，但我感觉很糟糕，因为恢复数据所需的时间比正常情况要长得多。如果有一个经过良好测试的恢复过程，我认为该站点应该在总共不到 15 分钟的时间内重新上线。但是第一次恢复没有成功，我不得不调试它为什么不能成功，然后重试。当一个生产站点宕机了，需要你重新启动它，每过 10 秒钟都感觉过了一个世纪。值得庆幸的是，老板们比某些人更能理解我们。他们实际上松了一口气，因为这一场可能使公司沉没的一次性灾难只导致了几分钟的数据丢失和不到一个小时的停机时间。在实践中，备份“成功”但恢复失败的情况极为普遍。很多时候，小型数据集上进行恢复测试是可以正常工作的，但在生产规模的大数据集上就会失败。当每个人都压力过大时，灾难最有可能发…

一次 Docker 镜像的逆向工程
type: item
date: 2021-04-02T05:55:31+08:00
description: 这要从一次咨询的失误说起：政府组织 A 让政府组织 B 开发一个 Web 应用程序。政府机构 B 把部分工作外包给某个人。后来，项目的托管和维护被外包给一家私人公司 C。C 公司发现，之前外包的人（已经离开很久了）构建了一个自定义的 Docker 镜像，并将其成为系统构建的依赖项，但这个人没有提交原始的 Dockerfile。C 公司有合同义务管理这个 Docker 镜像，可是他们他们没有源代码。C 公司偶尔叫我进去做各种工作，所以处理一些关于这个神秘 Docker 镜像的事情就成了我的工作。幸运的是，Docker 镜像的格式比想象的透明多了。虽然还需要做一些侦查工作，但只要解剖一个镜像文件，就能发现很多东西。例如，这里有一个 Prettier 代码格式化 的镜像可供快速浏览。首先，让 Docker 守护进程 daemon 拉取镜像，然后将镜像提取到文件中：docker pull tmknom/prettier:2.0.5 docker save tmknom/prettier:2.0.5 > prettier.tar 是的，该文件只是一个典型 tarball 格式的归档文件：$ tar xvf prettier.tar 6c37da2ee7de579a0bf5495df32ba3e7807b0a42e2a02779206d165f55f1ba70/ 6c37da2ee7de579a0bf5495df32ba3e7807b0a42e2a02779206d165f55f1ba70/VERSION 6c37da2ee7de579a0bf5495df32ba3e7807b0a42e2a02779206d165f55f1ba70/json 6c37da2ee7de579a0bf5495df32ba3e7807b0a42e2a02779206d165f55f1ba70/layer.tar 88f38be28f05f38dba94ce0c1328ebe2b963b65848ab96594f8172a9c3b0f25b.json a9cc4ace48cd792ef888ade20810f82f6c24aaf2436f30337a2a712cd054dc97/ a9cc4ace48cd792ef888ade20810f82f6c24aaf2436f30337a2a712cd054dc97/VERSION a9cc4ace48cd792ef888ade20810f82f6c24aaf2436f30337a2a712cd054dc97/json a9cc4ace48cd792ef888ade20810f82f6c24aaf2436f30337a2a712cd054dc97/layer.tar d4f612de5397f1fc91272cfbad245b89eac8fa4ad9f0fc10a40ffbb54a356cb4/ d4f612de5397f1fc91272cfbad245b89eac8fa4ad9f0fc10a40ffbb54a356cb4/VERSION d4f612de5397f1fc91272cfbad245b89eac8fa4ad9f0fc10a40ffbb54a356cb4/json d4f612de5397f1fc91272cfbad245b89eac8fa4ad9f0fc10a40ffbb54a356cb4/layer.tar manifest.json repositories 如你所见，Docker 在命名时经常使用 哈希 hash 。我们看看 manifest.json。它是以难以阅读的压缩 JSON 写的，不过 JSON 瑞士军刀 jq 可以很好地打印 JSON：$ jq . manifest.json [ { "Config": "88f38be28f05f38dba94ce0c1328ebe2b963b65848ab96594f8172a9c3b0f25b.json", "RepoTags": [ "tmknom/prettier:2.0.5" ], "Layers": [ "a9cc4ace48cd792ef888ade20810f82f6c24aaf2436f30337a2a712cd054dc97/layer.tar", "d4f612de5397f1fc91272cfbad245b89eac8fa4ad9f0fc10a40ffbb54a356cb4/layer.tar", "6c37da2ee7de579a0bf5495df32ba3e7807b0a42e2a02779206d165f55f1ba70/layer.tar" ] } ] 请注意，这三个 层 Layer 对应三个以哈希命名的目录。我们以后再看…

离开 Google：五年以来
type: item
date: 2020-09-15T07:11:32+08:00
description: 大约五年前的今天，我上交了 Google 员工证，然后走出了悉尼 Google 办公室，开启了一段自谋职业的崭新生活。我认为我应该详述一下这个故事，因为我通过阅读 Michael Lynch 的作品而收获颇丰。正如你所看到的，我仍然花费了几年时间才开始考虑写这篇文章，但是最终我告诉自己，倘若我不在五周年纪念日写它，我就永远也不会写了。这篇文章有点儿长，但是我希望它对那些对于在大型技术公司工作感兴趣的新开发人员或是想要离职的大型企业雇员能够有所帮助。我将谈谈我进入 Google，在 Google 工作和辞职的故事，以及之后我做了什么。如果你想了解更多的细节，可以随时询问，不过我已经有很多博文要写，所以不能保证有什么深入的内容。同样地，冒着显而易见的劳工风险：我已经有 5 年不在 Google 工作了，所以请不要以这个故事来作为当今 Google 或是 Google 雇员经历全貌的字面描述。但是，我认为其中的许多内容仍然与一般性的技术职业有关。通往 Google 的艰辛道路2005 年，我获得了第一份带薪的编程工作，是在当地的电力公司工作，把一些旧的 Pascal 代码用不同的编译器在不同的操作系统上运行。这基本上只是我为了挣外快而做的暑期工，同年我还刚刚开始攻读我数学和物理的学位。他们很高兴有一个本科生能够胜任这份工作。我被这些大人吓了一跳，因为他们不仅只是对我的编程爱好感兴趣，而且真的还会为此给我钱。直到 2007 年毕业以前，我一直在做类似的工作。我喜欢编程工作，而 Google 是一家从事着很酷的编程工作的很酷的公司，因此我申请了实习。 Google 的面试过程以困难而著称，所以我花了好几个星期时间练习了所有我在网上能够找到的 Google 面试题。我认为 13 年里面试流程并没有发生太大的变化 —— 我提交了简历，受邀参加了几轮电话面试，这些面试问的几乎都是算法问题（我记得有一个动态规划问题和一个分治几何问题）。我通过了最初的几轮面试，然后受邀前往悉尼接受了由 Google 的工程师们进行的为期一天的现场面试。我回到家里，等待 Google HR 的电话，这个过程漫长得像是有一辈子。我被拒绝了。对于我们收到的拒绝和失败感到难过很自然，因此我们并不会经常谈及它们。但是出于同样的原因，其他人也不会去谈论他们自己的失败，这只会使得情况变得更加糟糕。当我后来真的进入 Google 时，我觉得作为一个此前被拒绝过的人，我一定有哪里做得不对，但是有一天我和一群同事坐在一张桌子旁，开始交谈。那时候我才发现，实际上我身边的很多人都至少被拒绝过一次。我甚至都不是“最差的”。有个家伙开玩笑说，他肯定是因为 Google HR 厌倦了拒绝他才得以进来的。我说的也是一些相当厉害的工程师 —— 有些人负责着我一直在用的代码，而我打赌你也在用。进行面试的公司通常会为每个名额面试两名或更多的候选人。这意味着比起录用，会有更多的拒绝，所以一般面试参与者被拒绝的可能性要大于被录用。然而我们一直忘记了这一点。四个开发人员参加面试，一个被录用了，其他三个在社交媒体上抱怨这场面试是如何的漏洞百出，因为他们个人被拒绝了。当然，面试远非完美，但是我们需要停止如此个人化地谈论它。只要你能够找到问题所在并知道如何去改进自己，拒绝和失败就没有那么糟糕。Google 的面试主要针对算法，我在其中磕磕拌拌地摸索，但绝对没有能够脱颖而出。在被 Google 拒绝以后，我得到了两样东西，并进行了为期一年的休假。第一件东西是澳大利亚商务编号（ABN），我用它来提供数学与科学补习课程，以及技术工作合同。我获得的另一样东西是一张大学科技图书馆的借书证。我当时并不打算再次去参加 Google 的面试，但是那次的面试经历告诉我还有很多东西是我所不知道的。我就在图书馆开设课程给大家做辅导，并在期间阅读书籍。顺便说一句，有些人认为我为我的补习业务所做的所有这些财务工作和其他东西很奇怪，而大多数补习老师都只收现金。但是我学到了许多对我日后生活很有帮助的东西，所以我一点儿都不后悔。2009 年，我根据一个叫 Persi Diaconis 的魔术师转行为数学家的作品，进行了一个数学荣誉课程（也就是学士学位四年级）。计算机科学系让我选修他们的一个算法单元作为其中的一部分。就像我所说的那样，我本来并没有打算再去 Google 面试，但是让我快速地讲讲这是怎么发生的。我从高中就开始学习日语，因此在 2012 年，我决定尝试在东京生活。这基本上行得通，除了我犯了一个相当大的错误 —— 我没有任何日语方面的纸质资质证明，因此很难获得工作面试。最终，我的一个已经被 Google 录用的朋友建议我再试一次。与 Google 所有的办事处一样， Google 东京的官方商务语言是英语，因此他们不要求我具有日语资质…

为什么排序的复杂度为 O(N log N)
type: item
date: 2020-09-08T22:49:21+08:00
description: 基本上所有正而八经的算法教材都会解释像 快速排序 quicksort 和 堆排序 heapsort 这样的排序算法有多快，但并不需要复杂的数学就能证明你可以逐渐趋近的速度有多快。关于标记的一个严肃说明：大多数计算机专业的科学家使用大写字母 O 标记来指代“趋近，直到到达一个常数比例因子”，这与数学专业所指代的意义是有所区别的。这里我使用的大 O 标记的含义与计算机教材所指相同，但至少不会和其他数学符号混用。基于比较的排序先来看个特例，即每次比较两个值大小的算法（快速排序、堆排序，及其它通用排序算法）。这种思想后续可以扩展至所有排序算法。一个简单的最差情况下的计数角度假设有 4 个互不相等的数，且顺序随机，那么，可以通过只比较一对数字完成排序吗？显然不能，证明如下：根据定义，要对该数组排序，需要按照某种顺序重新排列数字。换句话说，你需要知道用哪种排列方式？有多少种可能的排列？第一个数字可以放在四个位置中的任意一个，第二个数字可以放在剩下三个位置中的任意一个，第三个数字可以放在剩下两个位置中的任意一个，最后一个数字只有剩下的一个位置可选。这样，共有 4×3×2×1=4!=24 种排列可供选择。通过一次比较大小，只能产生两种可能的结果。如果列出所有的排列，那么“从小到大”排序对应的可能是第 8 种排列，按“从大到小”排序对应的可能是第 24 种排列，但无法知道什么时候需要的是其它 22 种排列。通过 2 次比较，可以得到 2×2=4 种可能的结果，这仍然不够。只要比较的次数少于 5（对应 2 5 = 32 种输出），就无法完成 4 个随机次序的数字的排序。如果 W(N) 是最差情况下对 N 个不同元素进行排序所需要的比较次数，那么，两边取以 2 为底的对数，得：N! 的增长近似于 N N （参阅 Stirling 公式），那么，这就是最差情况下从输出计数的角度得出的 O(N log N) 上限。从信息论角度的平均状态的例子使用一些信息论知识，就可以从上面的讨论中得到一个更有力的结论。下面，使用排序算法作为信息传输的编码器：任取一个数，比如 15从 4 个数字的排列列表中查找第 15 种排列对这种排列运行排序算法，记录所有的“大”、“小”比较结果用二进制编码发送比较结果接收端重新逐步执行发送端的排序算法，需要的话可以引用发送端的比较结果现在接收端就可以知道发送端如何重新排列数字以按照需要排序，接收端可以对排列进行逆算，得到 4 个数字的初始顺序接收端在排列表中检索发送端的原始排列，指出发送端发送的是 15确实，这有点奇怪，但确实可以。这意味着排序算法遵循着与编码方案相同的定律，包括理论所证明的不存在通用的数据压缩算法。算法中每次比较发送 1 比特的比较结果编码数据，根据信息论，比较的次数至少是能表示所有数据的二进制位数。更技术语言点，平均所需的最小比较次数是输入数据的香农熵，以比特为单位。熵是衡量信息等不可预测量的数学度量。包含 N 个元素的数组，元素次序随机且无偏时的熵最大，其值为 log 2​ N! 个比特。这证明 O(N log N) 是一个基于比较的对任意输入排序的最优平均值。以上都是理论说法，那么实际的排序算法如何做比较的呢？下面是一个数组排序所需比较次数均值的图。我比较的是理论值与快速排序及 Ford-Johnson 合并插入排序 的表现。后者设计目的就是最小化比较次数（整体上没比快速排序快多少，因为生活中相对于最大限度减少比较次数，还有更重要的事情）。又因为 合并插入排序 merge-insertion sort 是在 1959 年提出的，它一直在调整，以减少了一些比较次数，但图示说明，它基本上达到了最优状态。一点点理论导出这么实用的结论，这感觉真棒！小结证明了：如果数组可以是任意顺序，在最坏情况下至少需要 O(N log N) 次比较。数组的平均比较次数最少是数组的熵，对随机输入而言，其值是 O(N log N) 。注意，第 2 个结论允许基于比较的算法优于 O(N log N)，前提是输入是低熵的（换言之，是部分可预测的）。如果输入包含很多有序的子序列，那么合并排序的性能接近 O(N)。如果在确定一个位之前，其输入是有序的，插入排序性能接近 O(N)。在最差情况下，以上算法的性能表现都不超出 O(N log N)。一般排序算法基于比较的排序在实践中是个有趣的特例，但从理论上讲，计算机的 CMP 指令与其它指令相比，并没有什么特别之处。在下面两条的基础上，前面两种情形都可以扩展至任意排序算法：大多数计算机指令有多于两个的输出，但输出的数量仍然是有限的。一条指令有限的输出意味着一条指令只能处理有限的熵。这给出了 O(N log N) 对应的指令下限。任何物理上可实现的计算机都只能在给定时间内执行有限数量的指令，所以算法的…

在软件部署中使用 strace 进行调试
type: item
date: 2019-12-12T21:05:25+08:00
description: 我的大部分工作都涉及到部署软件系统，这意味着我需要花费很多时间来解决以下问题：这个软件可以在原开发者的机器上工作，但是为什么不能在我这里运行？这个软件昨天可以在我的机器上工作，但是为什么今天就不行？这是一种调试的类型，但是与一般的软件调试有所不同。一般的调试通常只关心代码的逻辑，但是在软件部署中的调试关注的是程序的代码和它所在的运行环境之间的相互影响。即便问题的根源是代码的逻辑错误，但软件显然可以在别的机器上运行的事实意味着这类问题与运行环境密切相关。所以，在软件部署过程中，我没有使用传统的调试工具（例如 gdb），而是选择了其它工具进行调试。我最喜欢的用来解决“为什么这个软件无法在这台机器上运行？”这类问题的工具就是 strace。什么是 strace？strace 是一个用来“追踪系统调用”的工具。它主要是一个 Linux 工具，但是你也可以在其它系统上使用类似的工具（例如 DTrace 和 ktrace）。它的基本用法非常简单。只需要在 strace 后面跟上你需要运行的命令，它就会显示出该命令触发的所有系统调用（你可能需要先安装好 strace）：$ strace echo Hello ...Snip lots of stuff... write(1, "Hello\n", 6) = 6 close(1) = 0 close(2) = 0 exit_group(0) = ? +++ exited with 0 +++这些系统调用都是什么？它们就像是操作系统内核提供的 API。很久以前，软件拥有直接访问硬件的权限。如果软件需要在屏幕上显示一些东西，它将会与视频硬件的端口和内存映射寄存器纠缠不清。当多任务操作系统变得流行以后，这就导致了混乱的局面，因为不同的应用程序将“争夺”硬件，并且一个应用程序的错误可能致使其它应用程序崩溃，甚至导致整个系统崩溃。所以 CPU 开始支持多种不同的特权模式（或者称为“保护环”）。它们让操作系统内核在具有完全硬件访问权限的最高特权模式下运行，于此同时，其它在低特权模式下运行的应用程序必须通过向内核发起系统调用才能够与硬件进行交互。在二进制级别上，发起系统调用相比简单的函数调用有一些区别，但是大部分程序都使用标准库提供的封装函数。例如，POSIX C 标准库包含一个 write() 函数，该函数包含用于进行 write 系统调用的所有与硬件体系结构相关的代码。简单来说，一个应用程序与其环境（计算机系统）的交互都是通过系统调用来完成的。所以当软件在一台机器上可以工作但是在另一台机器无法工作的时候，追踪系统调用是一个很好的查错方法。具体地说，你可以通过追踪系统调用分析以下典型操作：控制台输入与输出 (IO)网络 IO文件系统访问以及文件 IO进程/线程生命周期管理原始内存管理访问特定的设备驱动什么时候可以使用 strace？理论上，strace 适用于任何用户空间程序，因为所有的用户空间程序都需要进行系统调用。strace 对于已编译的低级程序最有效果，但如果你可以避免运行时环境和解释器带来的大量额外输出，则仍然可以与 Python 等高级语言程序一起使用。当软件在一台机器上正常工作，但在另一台机器上却不能正常工作，同时抛出了有关文件、权限或者不能运行某某命令等模糊的错误信息时，strace 往往能大显身手。不幸的是，它不能诊断高等级的问题，例如数字证书验证错误等。这些问题通常需要组合使用 strace（有时候是 ltrace）和其它高级工具（例如使用 openssl 命令行工具调试数字证书错误）。本文中的示例基于独立的服务器，但是对系统调用的追踪通常也可以在更复杂的部署平台上完成，仅需要找到合适的工具。一个简单的例子假设你正在尝试运行一个叫做 foo 的服务器应用程序，但是发生了以下情况：$ foo Error opening configuration file: No such file or directory显然，它没有找到你已经写好的配置文件。之所以会发生这种情况，是因为包管理工具有时候在编译应用程序时指定了自定义的路径，所以你应当遵循特定发行版提供的安装指南。如果错误信息告诉你正确的配置文件应该在什么地方，你就可以在几秒钟内解决这个问题，但如果没有告诉你呢？你该如何找到正确的路径？如果你有权访问源代码，则可以通过阅读源代码来解决问题。这是一个好的备用计划，但不是最快的解决方案。你还可以使用类似 gdb 的单步调试器来观察程序的行为，但使用专门用于展示程序与系统环境交互作用的工具 strace 更加有效。一开始， strace 产生的大量输出可能会让你不知所措，幸好你可以忽略其中大部分的无用信息。我经常使用 -o 参数把输出的追踪结果保存到单独的文件里：$ strace -o /tmp…

面向对象编程和根本状态
type: item
date: 2019-10-31T15:00:00+08:00
description: 早在 2015 年，Brian Will 撰写了一篇有挑衅性的博客：面向对象编程：一个灾难故事。他随后发布了一个名为面向对象编程很糟糕的视频，该视频更加详细。我建议你花些时间观看视频，下面是我的一段总结：OOP 的柏拉图式理想是一堆相互解耦的对象，它们彼此之间发送无状态消息。没有人真的像这样制作软件，Brian 指出这甚至没有意义：对象需要知道向哪个对象发送消息，这意味着它们需要相互引用。该视频大部分讲述的是这样一个痛点：人们试图将对象耦合以实现控制流，同时假装它们是通过设计解耦的。总的来说，他的想法与我自己的 OOP 经验产生了共鸣：对象没有问题，但是我一直不满意的是面向对象建模程序控制流，并且试图使代码“正确地”面向对象似乎总是在创建不必要的复杂性。有一件事我认为他无法完全解释。他直截了当地说“封装没有作用”，但在脚注后面加上“在细粒度的代码级别”，并继续承认对象有时可以奏效，并且在库和文件级别封装是可以的。但是他没有确切解释为什么有时会奏效，有时却没有奏效，以及如何和在何处划清界限。有人可能会说这使他的 “OOP 不好”的说法有缺陷，但是我认为他的观点是正确的，并且可以在根本状态和偶发状态之间划清界限。如果你以前从未听说过“ 根本 essential ”和“ 偶发 accidental ”这两个术语的使用，那么你应该阅读 Fred Brooks 的经典文章《没有银弹》。（顺便说一句，他写了许多很棒的有关构建软件系统的文章。）我以前曾写过关于根本和偶发的复杂性的文章，这里有一个简短的摘要：软件是复杂的。部分原因是因为我们希望软件能够解决混乱的现实世界问题，因此我们将其称为“根本复杂性”。“偶发复杂性”是所有其它的复杂性，因为我们正尝试使用硅和金属来解决与硅和金属无关的问题。例如，对于大多数程序而言，用于内存管理或在内存与磁盘之间传输数据或解析文本格式的代码都是“偶发的复杂性”。假设你正在构建一个支持多个频道的聊天应用。消息可以随时到达任何频道。有些频道特别有趣，当有新消息传入时，用户希望得到通知。而其他频道静音：消息被存储，但用户不会受到打扰。你需要跟踪每个频道的用户首选设置。一种实现方法是在频道和频道设置之间使用 映射 map （也称为哈希表、字典或关联数组）。注意，映射是 Brian Will 所说的可以用作对象的抽象数据类型（ADT）。如果我们有一个调试器并查看内存中的映射对象，我们将看到什么？我们当然会找到频道 ID 和频道设置数据（或至少指向它们的指针）。但是我们还会找到其它数据。如果该映射是使用红黑树实现的，我们将看到带有红/黑标签和指向其他节点的指针的树节点对象。与频道相关的数据是根本状态，而树节点是偶发状态。不过，请注意以下几点：该映射有效地封装了它的偶发状态 —— 你可以用 AVL 树实现的另一个映射替换该映射，并且你的聊天程序仍然可以使用。另一方面，映射没有封装根本状态（仅使用 get() 和 set() 方法访问数据并不是封装）。事实上，映射与根本状态是尽可能不可知的，你可以使用基本相同的映射数据结构来存储与频道或通知无关的其他映射。这就是映射 ADT 如此成功的原因：它封装了偶发状态，并与根本状态解耦。如果你思考一下，Brian 用封装描述的问题就是尝试封装根本状态。其他描述的好处是封装偶发状态的好处。要使整个软件系统都达到这一理想状况相当困难，但扩展开来，我认为它看起来像这样：没有全局的可变状态封装了偶发状态（在对象或模块或以其他任何形式）无状态偶发复杂性封装在单独函数中，与数据解耦使用诸如依赖注入之类的技巧使输入和输出变得明确组件可由易于识别的位置完全拥有和控制其中有些违反了我很久以来的直觉。例如，如果你有一个数据库查询函数，如果数据库连接处理隐藏在该函数内部，并且唯一的参数是查询参数，那么接口会看起来会更简单。但是，当你使用这样的函数构建软件系统时，协调数据库的使用实际上变得更加复杂。组件不仅以自己的方式做事，而且还试图将自己所做的事情隐藏为“实现细节”。数据库查询需要数据库连接这一事实从来都不是实现细节。如果无法隐藏某些内容，那么显露它是更合理的。我对将面向对象编程和函数式编程放在对立的两极非常警惕，但我认为从函数式编程进入面向对象编程的另一极端是很有趣的：OOP 试图封装事物，包括无法封装的根本复杂性，而纯函数式编程往往会使事情变得明确，包括一些偶发复杂性。在大多数时候，这没什么问题，但有时候（比如在纯函数式语言中构建自我指称的数据结构）设计更多的是为了函数编程，而不是为了简便（这就是为什么 Haskell 包含了一些“ 逃生出口 escape hatches ”）。我之前写过一篇所谓“ 弱纯性 weak purity ”的中间立场。Brian 发现封装对更大规模有效，原因有几个。一个是，…

为什么 const 无法让 C 代码跑得更快？
type: item
date: 2019-09-15T02:16:34+08:00
description: 在几个月前的一篇文章里，我曾说过“有个一个流行的传言，const 有助于编译器优化 C 和 C++ 代码”。我觉得我需要解释一下，尤其是曾经我自己也以为这是显然对的。我将会用一些理论并构造一些例子来论证，然后在一个真实的代码库 Sqlite 上做一些实验和基准测试。一个简单的测试让我们从一个最简单、最明显的例子开始，以前认为这是一个 const 让 C 代码跑得更快的例子。首先，假设我们有如下两个函数声明：void func(int *x); void constFunc(const int *x);然后假设我们如下两份代码：void byArg(int *x) { printf("%d\n", *x); func(x); printf("%d\n", *x); } void constByArg(const int *x) { printf("%d\n", *x); constFunc(x); printf("%d\n", *x); }调用 printf() 时，CPU 会通过指针从 RAM 中取得 *x 的值。很显然，constByArg() 会稍微快一点，因为编译器知道 *x 是常量，因此不需要在调用 constFunc() 之后再次获取它的值。它仅是打印相同的东西。没问题吧？让我们来看下 GCC 在如下编译选项下生成的汇编代码：$ gcc -S -Wall -O3 test.c $ view test.s以下是函数 byArg() 的完整汇编代码：byArg: .LFB23: .cfi_startproc pushq %rbx .cfi_def_cfa_offset 16 .cfi_offset 3, -16 movl (%rdi), %edx movq %rdi, %rbx leaq .LC0(%rip), %rsi movl $1, %edi xorl %eax, %eax call __printf_chk@PLT movq %rbx, %rdi call func@PLT # constFoo 中唯一不同的指令 movl (%rbx), %edx leaq .LC0(%rip), %rsi xorl %eax, %eax movl $1, %edi popq %rbx .cfi_def_cfa_offset 8 jmp __printf_chk@PLT .cfi_endproc函数 byArg() 和函数 constByArg() 生成的汇编代码中唯一的不同之处是 constByArg() 有一句汇编代码 call constFunc@PLT，这正是源代码中的调用。关键字 const 本身并没有造成任何字面上的不同。好了，这是 GCC 的结果。或许我们需要一个更聪明的编译器。Clang 会有更好的表现吗？$ clang -S -Wall -O3 -emit-llvm test.c $ view test.ll这是 IR 代码（LCTT 译注：LLVM 的中间语言）。它比汇编代码更加紧凑，所以我可以把两个函数都导出来，让你可以看清楚我所说的“除了调用外，没有任何字面上的不同”是什么意思：; Function Attrs: nounwind uwtable define dso_local void @byArg(i32*) local_unnamed_addr #0 { %2 = load i32, i32* %0, align 4, !tbaa !2 %3 = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i64 0, i64 0), i32 %2) tail call void @func(i32* %0) #4 %4 = load i32, i32* %0, align 4, !tbaa !2 %5 = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i64 0, i64 0), i32 %4) ret void } ; Function Attrs: nounwind uwtable define dso_local void @constByArg(i32*) local_unnamed_addr #0 { %2 = load i32, i32* %0, align 4, !tbaa !2 %3 = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([4 x i8], [4 x …