运用 Github 的时分，你有没有见过下面的提示？

$gitclonehttps://github.com/torvalds/linux
Cloninginto'linux'...
remote:Countingobjects:4350078,done.
remote:Compressingobjects:100%(4677/4677),done.
Receivingobjects:4%(191786/4350078),78.19MiB|8.70MiB/s

这段提示说，长途代码库一共有4350078个目标需求克隆。

这就叫”清点目标”（counting objects），Github需求实时计算出来，需求克隆的目标总数。

这个进程十分慢，依据Github的发表，像Linux kernel这样巨大的库，清点一次需求8分钟！也便是说，宣布git clone指令后，会干等八分钟，然后才会开端真实的数据传输。这当然是无法忍受的。Github团队一向想处理这个问题。

后来，他们总算发现了一种新的算法，现在清点一次只需3毫秒！

为了了解这个算法，你必须先知道，什么是Git的目标。简单说，目标便是文件，最重要的目标有三种。

• 快照目标（Commit）

• 目录目标（Directory）

• 文件目标（File）

每次提交代码的时分，会生成一个commit目标，里边有对应的当时”目录目标”的姓名。”目录目标”保存了代码根目录所含有的子目录和文件信息。每一个子目录便是另一个”目录目标”，每一个文件则是”文件目标”，里边是详细的文件内容。

所以，”清点目标”便是清点各种commit、目录、文件等。git clone和git fetch操作都需求清点目标，由于需求知道，究竟下载哪些目标文件。

清点目标的原始算法如下。

1. 列出本地一切分支***的一个commit

2. 列出长途一切分支***的一个commit

3. 两者进行比较，只需有不同，就意味着分支产生变化

4. 每一个产生变化的commit，都清点其间详细变化的子目录和文件

5. 追溯到当时commit的父节点，重复第四步，直至本地与长途的前史共同停止

6. 加总一切需求变化的目标

上面的进程阐明，”清点目标”是一个文件遍历算法，变化的目标会被逐个清点到，这就意味着很多的文件读操作。关于大型代码库来说，这个进程十分慢。

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功用了，因而将来必定还会有更多好玩的用法呈现。