在使用Github的时候，你有没有看到下面的提示？$gitclonehttps://github.com/torvalds/linuxCloninginto'linux'...remote:Countingobjects:4350078,done.remote:Compressingobjects:100%(4677/4677),done.Receivingobjects:4%(191786/4350078),78.19MiB|8.70MiB/s此提示表示远程代码库中共有4350078个对象需要克隆。这称为“计数对象”。Github需要实时计算需要克隆的对象总数。这个过程非常缓慢。根据Github的披露，像Linux内核这样庞大的库，查起来需要8分钟！换句话说，在发出gitclone命令后，它会等待八分钟，然后才会开始真正的数据传输。这当然是不能容忍的。Github团队一直在努力解决这个问题。后来他们终于发现了一种新的算法，现在算一次只需要3毫秒！为了理解这个算法，你必须首先知道什么是Git对象。简单的说对象就是一个文件，最重要的对象有3个。快照对象（Commit）目录对象（Directory）文件对象（File）每提交一次代码，都会产生一个提交对象，其中包含当前对应的“目录对象”的名称。“目录对象”保存了代码根目录下包含的子目录和文件信息。每个子目录都是另一个“目录对象”，每个文件都是一个“文件对象”，包含了具体的文件内容。因此，“清点对象”就是清点各种commit、目录、文件等。gitclone和gitfetch操作都需要清点对象，因为它们需要知道要下载哪些对象文件。清点对象的原始算法如下。列出所有本地分支的一个commit***列出所有远程分支的一个commit***比较两者，只要有差异，就说明该分支发生了变化每一次变化的commit，统计具体变化的子目录和文件回溯到当前提交的父节点，重复第四步，直到本地和远程历史一致。对所有需要改变的对象，总结上面的过程描述。“Inventoryobjects”是一种文件遍历算法，变化的对象会一个一个地统计，这意味着很多文件读取操作。对于大型代码库，这个过程非常缓慢。Github团队想到的新算法是建立一个Bitmap索引，它为每个提交生成一个二进制值。打开本地Github仓库的.git/objects/pack/目录，会看到一个索引文件和一个数据文件，都是Bitmaps。简单的说，这两个文件索引了当前代码库中的所有对象，然后用一个二进制值来表示这些对象。在这个二进制值中有多少个对象就有多少位。它的第n位表示数据文件中的第n个对象。每个提交都会有一个对应的二进制值，代表当前快照中包含的所有对象。这些对象对应的二进制位全为1，其他二进制位全为0。这样做的好处是不用读commit对象，只读二进制值，就知道哪些节点是包含在当前提交中。更好的是，只要对两个二进制值进行异或运算就可以知道哪些位（即哪些对象）发生了变化。而且，因为新的对象总是添加在现有的二进制位之后，只要你读取额外的位，你就会知道哪些对象在当前提交中比在上次提交中多。这样“清除对象”就变成了二进制值的比较操作，所以速度极快。进一步介绍请参考官方文档《Bitmap的解释》、《Bitmap的格式》。目前该算法已经部署在Github的生产环境中，用户再也不用苦苦等待统计对象了。而且Github团队也将其合并到Git中，也就是说以后所有的Git实现都可以使用Bitmap功能，以后肯定会有更多有趣的用法。
