git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH] diff-delta: bound hash list length to avoid O(m*n) behavior

From
Linus Torvalds <torvalds@osdl.org>
Date
Mar 4, 2006, 06:21 UTC
Message-ID
<Pine.LNX.4.64.0603032217470.22647@g5.osdl.org>
In-Reply-To
<7vfylzx7t3.fsf@assigned-by-dhcp.cox.net>
On Fri, 3 Mar 2006, Junio C Hamano wrote:
Show 9 quoted lines
> 
> 	The first round.  The set of objects packed were from
> today's Linus tip (everything down to epoch v2.6.12-rc2), 193309
> objects in total, on my Duron 750 with slow disks.
> 
> 	real		user		sys		bytes		savings
> master	11m17.121s	10m23.280s	0m47.290s       109045599	N/A
> nico	25m37.058s	23m0.770s       2m20.460s	104401392	4.25%
> jc	24m12.072s	21m45.120s	2m16.400s	104409761	4.25%
Ouch.

Btw, it's often worth using /usr/bin/time instead of the bash built-in time. Why? Because /usr/bin/time reports one absolutely _hugely_ important number (maybe more important than almost any of the other numbers in there).

Which one? It's the "minor pagefaults". That's a very good approximation of memory usage overhead.

We've already had one person report that they ran out of memory when packing. So memory usage is actually a problem.

Anyway, it looks like the 16-byte window is the way to go, even regardless of any memory use issue.

		Linus
Previous: Nicolas Pitre
Message 10 of 10 in “diff-delta: bound hash list length to avoid O(m*n) behavior”
  1. diff-delta: bound hash list length to avoid O(m*n) behaviorNicolas Pitre, Feb 28, 2006
  2. Junio C HamanoFeb 28, 2006
  3. Junio C HamanoFeb 28, 2006
  4. Nicolas PitreFeb 28, 2006
  5. Junio C HamanoMar 1, 2006
  6. Nicolas PitreMar 1, 2006
  7. Junio C HamanoMar 4, 2006
  8. Junio C HamanoMar 4, 2006
  9. Nicolas PitreMar 4, 2006
  10. Linus TorvaldsMar 4, 2006

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.