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

Re: [RFC/PATCH 0/3] teach --histogram to diff

From
Shawn Pearce <spearce@spearce.org>
Date
Jul 12, 2011, 14:19 UTC
Message-ID
<CAJo=hJu5ubkzUyyPM0nqP+J9CU3hBtAHfuzaLSuN214Hux4qTA@mail.gmail.com>
In-Reply-To
<1310451027-15148-1-git-send-email-rctay89@gmail.com>
On Mon, Jul 11, 2011 at 23:10, Tay Ray Chuan <rctay89@gmail.com> wrote:
Show 23 quoted lines
> (Shawn, I was held up with the patch messages, sorry for the delay.)
>
> Port JGit's HistogramDiff(Index) over to C. This algorithm extends the
> patience algorithm to "support low-occurrence common elements" [1].
>
> Rough numbers show that it is a faster alternative to its --patience
> cousin, as well as to the default Meyers algorithm:
>
>  $ time ./git log --histogram -p v1.0.0 >/dev/null
>
>  real    0m12.998s
>  user    0m11.506s
>  sys     0m1.487s
>  $ time ./git log -p v1.0.0 >/dev/null
>
>  real    0m13.575s
>  user    0m12.101s
>  sys     0m1.468s
>  $ time ./git log --patience -p v1.0.0 >/dev/null
>
>  real    0m14.978s
>  user    0m13.508s
>  sys     0m1.464s
Nice!

Not the big difference that it is for us in JGit (between histogram and Myers), but its nice to see an improvement here, even if it is only 0.5s for the entire 1.0.0 history. How do the diffs come out? One of the arguments for patience diff is the formatting can sometimes be more readable for certain changes, but its slower. Histogram tries to apply a similar algorithm as patience in order to get the formatting benefits, but also some performance improvements.

Have you looked at a patch that differs in output between Myers and patience, and then compared those to the histogram version?

> The first patch implements JGit's HistogramDiff(Index) proper. The
> second and third patches aren't essential but yield performance gains.
...
> [RFC/PATCH 1/3] teach --histogram to diff
> [RFC/PATCH 2/3] xdiff/xprepare: skip classification
> [RFC/PATCH 3/3] xdiff/xprepare: use a smaller sample size for histogram
Do we need sampling at all for histogram? Can you skip it?
-- 
Shawn.
Previous: Tay Ray ChuanNext: Junio C Hamano
Message 7 of 24 in “teach --histogram to diff”
  1. 0/3 teach --histogram to diffTay Ray Chuan, Jul 12, 2011
  2. 1/3 teach --histogram to diffTay Ray Chuan, Jul 12, 2011
  3. 2/3 xdiff/xprepare: skip classificationTay Ray Chuan, Jul 12, 2011
  4. 3/3 xdiff/xprepare: use a smaller sample size for histogram diffTay Ray Chuan, Jul 12, 2011
  5. Junio C HamanoJul 12, 2011
  6. Tay Ray ChuanJul 13, 2011
  7. Shawn PearceJul 12, 2011
  8. Junio C HamanoJul 12, 2011
  9. Tay Ray ChuanJul 13, 2011
  10. Tay Ray ChuanJul 13, 2011
  11. 0/8 teach --histogram to diffTay Ray Chuan, Aug 1, 2011
  12. 1/8 xdiff/xprepare: use memset()Tay Ray Chuan, Aug 1, 2011
  13. 2/8 do away with xdl_mmfile_next()Tay Ray Chuan, Aug 1, 2011
  14. 3/8 xdiff/xprepare: refactor abort cleanupsTay Ray Chuan, Aug 1, 2011
  15. 4/8 xdiff/xpatience: factor out fall-back-diff functionTay Ray Chuan, Aug 1, 2011
  16. 5/8 t4033-diff-patience: factor out testsTay Ray Chuan, Aug 1, 2011
  17. 6/8 teach --histogram to diffTay Ray Chuan, Aug 1, 2011
  18. 7/8 xdiff/xprepare: skip classificationTay Ray Chuan, Aug 1, 2011
  19. 8/8 xdiff/xprepare: use a smaller sample size for histogram diffTay Ray Chuan, Aug 1, 2011
  20. 0/4 changes for rc/histogram-diff in 'next'Tay Ray Chuan, Aug 1, 2011
  21. 1/4 xdiff: do away with xdl_mmfile_next()Tay Ray Chuan, Aug 1, 2011
  22. 2/4 xdiff/xhistogram: rework handling of recursed resultsTay Ray Chuan, Aug 1, 2011
  23. 3/4 xdiff/xhistogram: rely on xdl_trim_ends()Tay Ray Chuan, Aug 1, 2011
  24. 4/4 xdiff/xhistogram: drop need for additional variableTay Ray Chuan, Aug 1, 2011

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.