具体的优化技巧

Jon Bentley在1982年的作品“编写高效程序”将程序优化视为一个工程问题:基准。分析。提高。校验。迭代。他的一些技巧现在由编译器自动完成。程序员的工作是使用编译器无法做到的转换。

本书的摘要如下:

在考虑对程序进行更改时，有两个基本选项:你可以更改数据，也可以更改代码。

改变你的数据意味着增加或改变你正在处理的数据的表示。从性能角度来看，其中一些最终会改变与数据结构的不同方面相关的O()。

增加数据结构的想法:

额外字段:例如，存储链接列表的大小，而不是在询问时迭代。或者将经常需要的其他节点的指针存储到多个搜索中(例如，双向链接列表中的“向后”链接以进行删除O(1))。当你需要的数据便于存储并保持最新时，这些更改很有用。
额外的搜索索引:大多数数据结构都是为单一类型的查询而设计的。如果你需要两种不同的查询类型，对数据进行额外的“查看”可能会有很大的改进。例如，[] struct，由ID引用，但有时是string - > map [string] id(或* struct)
有关元素的额外信息:例如布隆过滤器。这些数据结构必须小而快，以免压倒其余的数据结构。
如果查询很昂贵，请添加一个缓存。我们都熟悉memcache，但还有进程内缓存。

TODO:“缓存”可能不是键值对，只是指向你工作的地方。这可以像“搜索手指”一样简单

这些都是数据结构层面“做更少工作”的明确例子。他们都花费空间。大多数情况下，如果你针对CPU进行优化，程序将使用更多的内存。这是经典的时空交易

如果你的程序使用太多的内存，也可以换个方式。减少空间使用量以换取更多计算。而不是存储的东西，每次计算它们。你还可以压缩内存中的数据，并在需要时随时对其进行解压缩。

小内存软件是一本网上可获取的书籍，涵盖了减少程序使用内存空间的技术。虽然它最初是针对嵌入式开发人员编写的，但这些想法适用于处理大量数据的现代硬件的程序。

重新排列你的数据
消除结构填充。删除额外的字段。使用较小的数据类型
更改为较慢的数据结构
较简单的数据结构通常具有较低的内存要求。例如，从一个指针重的树结构转向使用切片和线性搜索。
为你的数据定制压缩格式
[]字节（snappy，gzip，lz4），浮点数（go-tsz），整数（delta，xor + huffman）大量的压缩资源。你需要检查数据还是可以保持压缩？你需要随机访问还是只有流媒体？压缩具有额外索引的块。如果不是在进程中，而是写入磁盘，那么迁移或添加/删除字段呢？你现在正在处理raw []字节而不是很好的结构化Go类型。

我们稍后会详细讨论数据布局。

现代计算机和存储器层次结构使空间/时间的权衡不太明确。查找表很容易在内存中“远离”(因此访问成本很高)，使得每次需要时重新计算一次值都会更快。

这也意味着基准测试通常会显示由于缓存争用而导致生产系统无法实现的改进(例如，查找表在基准测试期间位于处理器缓存中，但在真实系统中使用时总是会被“真实数据”冲刷。哈希表实际上直接解决了这个问题，比较了满足和无约束的处理器缓存上的性能。参见Jump Hash paper论文中的图4和图5。

TODO:如何模拟满足的缓存，显示增量成本

另一个要考虑的方面是数据传输时间。通常，网络和磁盘访问非常缓慢，因此能够加载压缩块的速度将比获取数据后解压缩数据所需的额外CPU时间快得多。一如既往，基准。二进制格式通常比文本格式更小且更快解析，但代价是不再是人类可读的格式。

对于数据传输，转移到一个不那么有趣的协议，或者增加API以允许部分查询。例如，增量查询而不是每次都被迫获取整个数据集。