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

Re: [PATCH] xdiff/xprepare: improve O(n*m) performance in xdl_cleanup_records()

From
Junio C Hamano <gitster@pobox.com>
Date
Aug 16, 2011, 17:39 UTC
Message-ID
<7vd3g5i7ci.fsf@alter.siamese.dyndns.org>
In-Reply-To
<20110816113710.000025a7@unknown>
Tay Ray Chuan <rctay89@gmail.com> writes:
Show 5 quoted lines
> From 0da9ec94604978f877e7f7c00d307b5cdbb22b29 Mon Sep 17 00:00:00 2001
> From: Tay Ray Chuan <rctay89@gmail.com>
> Date: Tue, 16 Aug 2011 11:35:28 +0800
> Subject: [PATCH] xdiff/xprepare: improve O(n*m) performance in
>  xdl_cleanup_records()
You do not need these four lines. Thanks.
Show 6 quoted lines
> In xdl_cleanup_records(), we see O(n*m) performance, where n is the
> number of records from xdf->dstart to xdf->dend, and m is the size of a
> bucket in xdf->rhash (<= by mlim).
>
> Here, we improve this to O(n) by pre-computing nm (in rcrec->len(1|2))
> in xdl_classify_record().

Could we have some benchmarks to let the readers get a feel of how much improvement this patch brings in?

This tries to trade cycles with memory, right? How much bloat are we talking about here?

Previous: Tay Ray ChuanNext: Tay Ray Chuan
Message 7 of 16 in “git diff is slow (--patience is fast)”
  1. Marat RadchenkoAug 9, 2011
  2. Tay Ray ChuanAug 9, 2011
  3. Marat RadchenkoAug 9, 2011
  4. Tay Ray ChuanAug 16, 2011
  5. xdiff/xprepare: improve O(n*m) performance in xdl_cleanup_records()Tay Ray Chuan, Aug 16, 2011
  6. Tay Ray ChuanAug 16, 2011
  7. Junio C HamanoAug 16, 2011
  8. xdiff/xprepare: improve O(n*m) performance in xdl_cleanup_records()Tay Ray Chuan, Aug 17, 2011
  9. Jeff KingAug 17, 2011
  10. Tay Ray ChuanAug 17, 2011
  11. Jeff KingAug 18, 2011
  12. Tay Ray ChuanAug 19, 2011
  13. Johannes SixtAug 21, 2011
  14. Marat RadchenkoAug 24, 2011
  15. Marat RadchenkoAug 24, 2011
  16. Marat RadchenkoAug 27, 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.