使用 Github 的时候，你有没有见过下面的提示？
$ git clone https://github.com/torvalds/linux Cloning into 'linux'... remote: Counting objects: 4350078, done. remote: Compressing objects: 100% (4677/4677), done. Receiving objects: 4% (191786/4350078), 78.19 MiB | 8.70 MiB/s
这段提示说，远程代码库一共有4350078个对象需要克隆。
这就叫"清点对象"（counting objects），Github需要实时计算出来，需要克隆的对象总数。
这个过程非常慢，根据Github的披露，像Linux kernel这样巨大的库，清点一次需要8分钟！也就是说，发出git clone命令后，会干等八分钟，然后才会开始真正的数据传输。这当然是无法忍受的。Github团队一直想解决这个问题。
后来，他们终于发现了一种新的算法，现在清点一次只要3毫秒！
为了理解这个算法，你必须先知道，什么是Git的对象。简单说，对象就是文件，最重要的对象有三种。
- 快照对象（Commit）
- 目录对象（Directory）
- 文件对象（File）
每次提交代码的时候，会生成一个commit对象，里面有对应的当前"目录对象"的名字。"目录对象"保存了代码根目录所含有的子目录和文件信息。每一个子目录就是另一个"目录对象"，每一个文件则是"文件对象"，里面是具体的文件内容。
所以，"清点对象"就是清点各种commit、目录、文件等。git clone和git fetch操作都需要清点对象，因为需要知道，到底下载哪些对象文件。
清点对象的原始算法如下。
- 列出本地所有分支最新的一个commit
- 列出远程所有分支最新的一个commit
- 两者进行比较，只要有不同，就意味着分支发生变动
- 每一个发生变动的commit，都清点其中具体变动的子目录和文件
- 追溯到当前commit的父节点，重复第四步，直至本地与远程的历史一致为止
- 加总所有需要变动的对象
上面的过程说明，"清点对象"是一个文件遍历算法，变动的对象会被一一清点到，这就意味着大量的文件读操作。对于大型代码库来说，这个过程非常慢。
Github团队想到的新算法，是建立一个Bitmap索引，即为每一个commit生成一个二进制值。
打开本地Github仓库的.git/objects/pack/目录，你会看到一个索引文件和一个数据文件，它们就是Bitmap。简单说，这两个文件索引了当前代码库的所有对象，然后使用一个二进制值代表这些对象。有多少个对象，这个二进制值就有多少位。它的第n位，就代表数据文件里面的第n个对象。
每个commit都会有一个对应的二进制值，表示当前快照包含的所有对象。这些对象对应的二进制位都为1，其他二进制位都为0。
这样做的好处是，不用读取commit对象，只要读取这个二进制值，就会知道当前commit包含了哪些节点。更妙的是，两个二进制值只要做一次XOR运算，就会知道哪些位（即哪些对象）发生了变动。而且，因为新的对象总是添加到现有二进制位的后面，所以只要读取多出来的那些位，就知道当前commit比上一次commit多出了哪些对象。
这样一来，"清点对象"就变成了二进制值的比较运算，因此速度极快。进一步的介绍，请参看官方文档《Bitmap的解释》，《Bitmap的格式》。
目前，Github的生产环境已经部署了这套算法，用户再也不用为了清点对象，而苦苦等待了。而且，Github团队还把它合并进了Git，这意味着，从此所有Git实现都可以使用Bitmap功能了，因此将来肯定还会有更多好玩的用法出现。
（完）
小胡子哥 说：
简单说就是把一个在线运算编程一个离线运算，并且选用了效率最高的二进制处理。
2015年9月30日 15:05 | # | 引用
Min 说：
原理懂了，就像windows里的缩略图索引文件一样，这个Bitmap文件就是闲时有备急时用嘛。话说峰哥的网速真杠杠的：8.70 MiB/s
2015年9月30日 20:45 | # | 引用
Lyeec 说：
这是最新的技术么? 意味着想要使用这个新的技术的话,需要更新git?
2015年9月30日 21:16 | # | 引用
Wop 说：
请教一下：文中流程图用的是什么软件作的？
2015年10月 1日 17:54 | # | 引用
SINeWang 说：
我猜是53 Paper
2015年10月 4日 11:07 | # | 引用
石樱灯笼 说：
github还真是良心
2015年10月 4日 16:48 | # | 引用
微博档案 说：
但是老版本的git没有这个功能，就没有这个Bitmap文件，就没有办法比对，那么老版本的性能依然不好？
2015年10月 5日 13:33 | # | 引用
Kris 说：
我也很想知道这篇博客的配图是用什么做的？
2015年10月 6日 16:46 | # | 引用
axiaoxin 说：
配图引用自：http://githubengineering.com/counting-objects/
2015年10月 8日 13:51 | # | 引用
Johnny 说：
Git 2.0+ release 就有了。
另外，counting object 应该算是集成进Git的功能，而非GitHub的（只不过是由GitHub的人实现），所以标题建议改成：Git的清点对象算法。
2015年10月10日 22:35 | # | 引用
Johnny 说：
>>The bitmap-index patchset [2] finally shipped in the much anticipated Git 2.0 release, and now Git network operations from most major Git hosts are enjoying the overhaul.
bitmap patch 集成进Git 2.0，count object 也应该是Git而非GitHub的功能（只不过由GitHub的人实现），所以建议标题改为：Git的对象清点算法
2015年10月10日 22:40 | # | 引用
jqk6 说：
GitHub是好，但是就是在国内访问速度太慢，有什么好办法，可以速度变快些呢？
2015年10月13日 21:51 | # | 引用
贾硕 说：
老师写文，也不标引用了？
2015年10月19日 13:16 | # | 引用
haozibi 说：
编程珠玑中的bitmap。。。
2015年10月19日 13:38 | # | 引用
HACK21 说：
每个commit都会有一个对应的二进制值，表示当前快照包含的所有对象。这些对象对应的二进制位都为1，其他二进制位都为0。
请问快照里面除了对象以外还有什么？不是所有都是对象吗？
2015年10月21日 08:53 | # | 引用
游客 说：
想请教一下小书签的问题http://www.ruanyifeng.com/blog/2011/06/a_guide_for_writing_bookmarklet.html
怎么用书签获取网页源码 用alert弹出
2015年10月23日 22:46 | # | 引用
zhangbobell 说：
下面这行代码应该能满足你的要求：
javascript:(function(){var x;if(window.XMLHttpRequest){x=new XMLHttpRequest();}else{x=new ActiveXObject("Microsoft.XMLHTTP");}x.onreadystatechange=function() {if(this.readyState===4) {alert(this.responseText);}};x.open('GET',location.href,true);x.send()}) ();2016年1月12日 10:38 | # | 引用
路人路人 说：
其实这个算法是为了方便的计算 可达性(reachable) 的。
对于给定的commit，如果packfile里第n位的对象是可达的，则bitmap里的第n位就是1，否则就是0
可以参考楼主最后贴的官方文档的解析。
2016年10月29日 09:00 | # | 引用