pack-objects: improve path grouping heuristics.

This trivial patch not only simplifies the name hashing, it actually
improves packing for both git and the kernel.

The git archive pack shrinks from 6824090->6622627 bytes (a 3%
improvement), and the kernel pack shrinks from 108756213 to 108219021 (a
mere 0.5% improvement, but still, it's an improvement from making the
hashing much simpler!)

We just create a 32-bit hash, where we "age" previous characters by two
bits, so the last characters in a filename count most. So when we then
compare the hashes in the sort routine, filenames that end the same way
sort the same way.

It takes the subdirectory into account (unless the filename is > 16
characters), but files with the same name within the same subdirectory
will obviously sort closer than files in different subdirectories.

And, incidentally (which is why I tried the hash change in the first
place, of course) builtin-rev-list.c will sort fairly close to rev-list.c.

And no, it's not a "good hash" in the sense of being secure or unique, but
that's not what we're looking for. The whole "hash" thing is misnamed
here. It's not so much a hash as a "sorting number".

[jc: rolled in simplification for computing the sorting number
 computation for thin pack base objects]

Signed-off-by: Linus Torvalds <torvalds@osdl.org>
Signed-off-by: Junio C Hamano <junkio@cox.net>
1 file changed
tree: 6e6e2b4c332fd37e27c404b180a3efe9cce8feda
  1. arm/
  2. compat/
  3. contrib/
  4. Documentation/
  5. mozilla-sha1/
  6. ppc/
  7. t/
  8. templates/
  9. xdiff/
  10. .gitignore
  11. base85.c
  12. blame.c
  13. blob.c
  14. blob.h
  15. builtin-add.c
  16. builtin-apply.c
  17. builtin-cat-file.c
  18. builtin-check-ref-format.c
  19. builtin-commit-tree.c
  20. builtin-count.c
  21. builtin-diff-files.c
  22. builtin-diff-index.c
  23. builtin-diff-stages.c
  24. builtin-diff-tree.c
  25. builtin-diff.c
  26. builtin-grep.c
  27. builtin-help.c
  28. builtin-init-db.c
  29. builtin-log.c
  30. builtin-ls-files.c
  31. builtin-ls-tree.c
  32. builtin-push.c
  33. builtin-read-tree.c
  34. builtin-rev-list.c
  35. builtin-rev-parse.c
  36. builtin-rm.c
  37. builtin-show-branch.c
  38. builtin-tar-tree.c
  39. builtin-upload-tar.c
  40. builtin.h
  41. cache-tree.c
  42. cache-tree.h
  43. cache.h
  44. checkout-index.c
  45. clone-pack.c
  46. combine-diff.c
  47. commit.c
  48. commit.h
  49. config.c
  50. connect.c
  51. convert-objects.c
  52. copy.c
  53. COPYING
  54. csum-file.c
  55. csum-file.h
  56. ctype.c
  57. daemon.c
  58. date.c
  59. delta.h
  60. describe.c
  61. diff-delta.c
  62. diff-lib.c
  63. diff.c
  64. diff.h
  65. diffcore-break.c
  66. diffcore-delta.c
  67. diffcore-order.c
  68. diffcore-pickaxe.c
  69. diffcore-rename.c
  70. diffcore.h
  71. dir.c
  72. dir.h
  73. dump-cache-tree.c
  74. entry.c
  75. environment.c
  76. exec_cmd.c
  77. exec_cmd.h
  78. fetch-clone.c
  79. fetch-pack.c
  80. fetch.c
  81. fetch.h
  82. fsck-objects.c
  83. generate-cmdlist.sh
  84. get-tar-commit-id.c
  85. git-am.sh
  86. git-annotate.perl
  87. git-applymbox.sh
  88. git-applypatch.sh
  89. git-archimport.perl
  90. git-bisect.sh
  91. git-branch.sh
  92. git-checkout.sh
  93. git-cherry.sh
  94. git-clean.sh
  95. git-clone.sh
  96. git-commit.sh
  97. git-compat-util.h
  98. git-cvsexportcommit.perl
  99. git-cvsimport.perl
  100. git-cvsserver.perl
  101. git-fetch.sh
  102. git-fmt-merge-msg.perl
  103. git-lost-found.sh
  104. git-ls-remote.sh
  105. git-merge-octopus.sh
  106. git-merge-one-file.sh
  107. git-merge-ours.sh
  108. git-merge-recursive.py
  109. git-merge-resolve.sh
  110. git-merge-stupid.sh
  111. git-merge.sh
  112. git-mv.perl
  113. git-parse-remote.sh
  114. git-prune.sh
  115. git-pull.sh
  116. git-push.sh
  117. git-quiltimport.sh
  118. git-rebase.sh
  119. git-relink.perl
  120. git-repack.sh
  121. git-request-pull.sh
  122. git-rerere.perl
  123. git-reset.sh
  124. git-resolve.sh
  125. git-revert.sh
  126. git-send-email.perl
  127. git-sh-setup.sh
  128. git-shortlog.perl
  129. git-svnimport.perl
  130. git-tag.sh
  131. git-verify-tag.sh
  132. GIT-VERSION-GEN
  133. git.c
  134. git.spec.in
  135. gitk
  136. gitMergeCommon.py
  137. hash-object.c
  138. http-fetch.c
  139. http-push.c
  140. http.c
  141. http.h
  142. ident.c
  143. imap-send.c
  144. index-pack.c
  145. index.c
  146. INSTALL
  147. local-fetch.c
  148. log-tree.c
  149. log-tree.h
  150. mailinfo.c
  151. mailsplit.c
  152. Makefile
  153. merge-base.c
  154. merge-index.c
  155. merge-tree.c
  156. mktag.c
  157. mktree.c
  158. name-rev.c
  159. object.c
  160. object.h
  161. pack-check.c
  162. pack-objects.c
  163. pack-redundant.c
  164. pack.h
  165. pager.c
  166. patch-delta.c
  167. patch-id.c
  168. path.c
  169. peek-remote.c
  170. pkt-line.c
  171. pkt-line.h
  172. prune-packed.c
  173. quote.c
  174. quote.h
  175. read-cache.c
  176. README
  177. receive-pack.c
  178. refs.c
  179. refs.h
  180. repo-config.c
  181. revision.c
  182. revision.h
  183. rsh.c
  184. rsh.h
  185. run-command.c
  186. run-command.h
  187. send-pack.c
  188. server-info.c
  189. setup.c
  190. sha1_file.c
  191. sha1_name.c
  192. shell.c
  193. show-index.c
  194. ssh-fetch.c
  195. ssh-pull.c
  196. ssh-push.c
  197. ssh-upload.c
  198. strbuf.c
  199. strbuf.h
  200. stripspace.c
  201. symbolic-ref.c
  202. tag.c
  203. tag.h
  204. tar.h
  205. test-date.c
  206. test-delta.c
  207. tree-diff.c
  208. tree-walk.c
  209. tree-walk.h
  210. tree.c
  211. tree.h
  212. unpack-file.c
  213. unpack-objects.c
  214. update-index.c
  215. update-ref.c
  216. update-server-info.c
  217. upload-pack.c
  218. usage.c
  219. var.c
  220. verify-pack.c
  221. write-tree.c
  222. xdiff-interface.c
  223. xdiff-interface.h