All of lore.kernel.org
 help / color / mirror / Atom feed
From: Josh Triplett <josh@joshtriplett.org>
To: Johannes Schindelin <johannes.schindelin@gmx.de>
Cc: git@vger.kernel.org, Junio C Hamano <gitster@pobox.com>
Subject: Re: [PATCH 9/9] rebase -i: rearrange fixup/squash lines using the rebase--helper
Date: Sat, 3 Sep 2016 11:03:45 -0700	[thread overview]
Message-ID: <20160903180344.truur5ey6j6ah2wh@x> (raw)
In-Reply-To: <3810bd4bddb3b850a78e5d960207157de64a2e56.1472833365.git.johannes.schindelin@gmx.de>

On Fri, Sep 02, 2016 at 06:23:42PM +0200, Johannes Schindelin wrote:
> Let's reimplement this with linear complexity (using a hash map to
> match the commits' subject lines) for the common case; Sadly, the
> fixup/squash feature's design neglected performance considerations,
> allowing arbitrary prefixes (read: `fixup! hell` will match the
> commit subject `hello world`), which means that we are stuck with
> quadratic performance in the worst case.

If the performance of that case matters enough, we can do better than
quadratic complexity: maintain a trie of the subjects, allowing prefix
lookups.  (Or hash all the prefixes, which you can do in linear time on
a string: hash next char, save hash, repeat.)  However, that would
pessimize the normal case of either a complete subject or a sha1, due to
the extra time taken constructing the data structure.  Probably not
worth it, if you assume that most "fixup!" subjects come from `git
commit --fixup` or similar automated means.

  reply	other threads:[~2016-09-03 18:03 UTC|newest]

Thread overview: 100+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2016-09-02 16:22 [PATCH 0/9] The final building block for a faster rebase -i Johannes Schindelin
2016-09-02 16:23 ` [PATCH 1/9] rebase -i: generate the script via rebase--helper Johannes Schindelin
2016-09-02 16:23 ` [PATCH 2/9] rebase -i: remove useless indentation Johannes Schindelin
2016-09-02 16:23 ` [PATCH 3/9] rebase -i: do not invent onelines when expanding/collapsing SHA-1s Johannes Schindelin
2016-09-02 16:23 ` [PATCH 4/9] rebase -i: also expand/collapse the SHA-1s via the rebase--helper Johannes Schindelin
2016-09-02 20:56   ` Dennis Kaarsemaker
2016-09-03  7:01     ` Johannes Schindelin
2016-09-02 16:23 ` [PATCH 5/9] t3404: relax rebase.missingCommitsCheck tests Johannes Schindelin
2016-09-02 16:23 ` [PATCH 6/9] rebase -i: check for missing commits in the rebase--helper Johannes Schindelin
2016-09-02 20:59   ` Dennis Kaarsemaker
2016-09-02 16:23 ` [PATCH 7/9] rebase -i: skip unnecessary picks using " Johannes Schindelin
2016-09-02 16:23 ` [PATCH 8/9] t3415: test fixup with wrapped oneline Johannes Schindelin
2016-09-02 16:23 ` [PATCH 9/9] rebase -i: rearrange fixup/squash lines using the rebase--helper Johannes Schindelin
2016-09-03 18:03   ` Josh Triplett [this message]
2016-09-04  6:47     ` Johannes Schindelin
2017-04-25 13:51 ` [PATCH v2 0/9] The final building block for a faster rebase -i Johannes Schindelin
2017-04-25 13:51   ` [PATCH v2 1/9] rebase -i: generate the script via rebase--helper Johannes Schindelin
2017-04-26 10:45     ` Jeff King
2017-04-26 11:34       ` Johannes Schindelin
2017-04-25 13:51   ` [PATCH v2 2/9] rebase -i: remove useless indentation Johannes Schindelin
2017-04-25 13:51   ` [PATCH v2 3/9] rebase -i: do not invent onelines when expanding/collapsing SHA-1s Johannes Schindelin
2017-04-25 13:51   ` [PATCH v2 4/9] rebase -i: also expand/collapse the SHA-1s via the rebase--helper Johannes Schindelin
2017-04-25 13:52   ` [PATCH v2 5/9] t3404: relax rebase.missingCommitsCheck tests Johannes Schindelin
2017-04-25 13:52   ` [PATCH v2 6/9] rebase -i: check for missing commits in the rebase--helper Johannes Schindelin
2017-04-25 13:52   ` [PATCH v2 7/9] rebase -i: skip unnecessary picks using " Johannes Schindelin
2017-04-26 10:55     ` Jeff King
2017-04-26 11:31       ` Johannes Schindelin
2017-04-25 13:52   ` [PATCH v2 8/9] t3415: test fixup with wrapped oneline Johannes Schindelin
2017-04-25 13:52   ` [PATCH v2 9/9] rebase -i: rearrange fixup/squash lines using the rebase--helper Johannes Schindelin
2017-04-26  3:32   ` [PATCH v2 0/9] The final building block for a faster rebase -i Junio C Hamano
2017-04-26 11:59   ` [PATCH v3 " Johannes Schindelin
2017-04-26 11:59     ` [PATCH v3 1/9] rebase -i: generate the script via rebase--helper Johannes Schindelin
2017-04-27  4:31       ` Junio C Hamano
2017-04-27 14:18         ` Johannes Schindelin
2017-04-28  0:13           ` Junio C Hamano
2017-04-28  2:36             ` Junio C Hamano
2017-04-28 15:13             ` Johannes Schindelin
2017-05-01  3:11               ` Junio C Hamano
2017-05-01 11:47                 ` Johannes Schindelin
2017-04-28 10:08       ` Phillip Wood
2017-04-28 19:22         ` Johannes Schindelin
2017-05-01 10:06           ` Phillip Wood
2017-05-01 11:58             ` Johannes Schindelin
2017-05-01  0:49         ` Junio C Hamano
2017-05-01 11:06           ` Johannes Schindelin
2017-04-26 11:59     ` [PATCH v3 2/9] rebase -i: remove useless indentation Johannes Schindelin
2017-04-26 11:59     ` [PATCH v3 3/9] rebase -i: do not invent onelines when expanding/collapsing SHA-1s Johannes Schindelin
2017-04-26 11:59     ` [PATCH v3 4/9] rebase -i: also expand/collapse the SHA-1s via the rebase--helper Johannes Schindelin
2017-04-27  5:00       ` Junio C Hamano
2017-04-27  6:47         ` Junio C Hamano
2017-04-27 21:44         ` Johannes Schindelin
2017-04-28  0:15           ` Junio C Hamano
2017-04-28 15:15             ` Johannes Schindelin
2017-04-26 11:59     ` [PATCH v3 5/9] t3404: relax rebase.missingCommitsCheck tests Johannes Schindelin
2017-04-27  5:05       ` Junio C Hamano
2017-04-27 22:01         ` Johannes Schindelin
2017-04-26 11:59     ` [PATCH v3 6/9] rebase -i: check for missing commits in the rebase--helper Johannes Schindelin
2017-04-27  5:32       ` Junio C Hamano
2017-04-28 15:10         ` Johannes Schindelin
2017-04-26 12:00     ` [PATCH v3 7/9] rebase -i: skip unnecessary picks using " Johannes Schindelin
2017-04-26 12:00     ` [PATCH v3 8/9] t3415: test fixup with wrapped oneline Johannes Schindelin
2017-04-26 12:00     ` [PATCH v3 9/9] rebase -i: rearrange fixup/squash lines using the rebase--helper Johannes Schindelin
2017-04-28 21:30     ` [PATCH v4 00/10] The final building block for a faster rebase -i Johannes Schindelin
2017-04-28 21:31       ` [PATCH v4 01/10] t3415: verify that an empty instructionFormat is handled as before Johannes Schindelin
2017-04-28 21:31       ` [PATCH v4 02/10] rebase -i: generate the script via rebase--helper Johannes Schindelin
2017-05-26  3:15         ` Liam Beguin
2017-05-29 10:59           ` Johannes Schindelin
2017-05-30 15:57             ` liam Beguin
2017-05-30 18:19           ` liam Beguin
2017-05-29  6:07         ` Junio C Hamano
2017-05-29 10:54           ` Johannes Schindelin
2017-05-30  4:57             ` Junio C Hamano
2017-05-30 14:59               ` Johannes Schindelin
2017-05-30 15:08               ` revision API design, was " Johannes Schindelin
2017-05-30 22:53                 ` Junio C Hamano
2017-06-01  6:48                   ` Junio C Hamano
2017-04-28 21:31       ` [PATCH v4 03/10] rebase -i: remove useless indentation Johannes Schindelin
2017-05-26  3:15         ` Liam Beguin
2017-05-26 17:50           ` Stefan Beller
2017-05-27  3:15             ` liam Beguin
2017-04-28 21:32       ` [PATCH v4 04/10] rebase -i: do not invent onelines when expanding/collapsing SHA-1s Johannes Schindelin
2017-04-28 21:32       ` [PATCH v4 05/10] rebase -i: also expand/collapse the SHA-1s via the rebase--helper Johannes Schindelin
2017-05-26  3:15         ` Liam Beguin
2017-05-29 11:20           ` Johannes Schindelin
2017-04-28 21:32       ` [PATCH v4 06/10] t3404: relax rebase.missingCommitsCheck tests Johannes Schindelin
2017-04-28 21:32       ` [PATCH v4 07/10] rebase -i: check for missing commits in the rebase--helper Johannes Schindelin
2017-04-28 21:32       ` [PATCH v4 08/10] rebase -i: skip unnecessary picks using " Johannes Schindelin
2017-04-28 21:32       ` [PATCH v4 09/10] t3415: test fixup with wrapped oneline Johannes Schindelin
2017-04-28 21:33       ` [PATCH v4 10/10] rebase -i: rearrange fixup/squash lines using the rebase--helper Johannes Schindelin
2017-05-26  3:16         ` Liam Beguin
2017-05-29 11:26           ` Johannes Schindelin
2017-05-26  3:15       ` [PATCH v4 00/10] The final building block for a faster rebase -i Liam Beguin
2017-05-27 16:23         ` René Scharfe
2017-05-29 10:51           ` Johannes Schindelin
2017-05-29 12:50             ` Ævar Arnfjörð Bjarmason
2017-05-30 15:44               ` Johannes Schindelin
2017-05-30 20:22                 ` Ævar Arnfjörð Bjarmason
2017-05-31 18:46                   ` Ævar Arnfjörð Bjarmason
2017-05-29 10:56         ` Johannes Schindelin
2017-05-29  8:30       ` Junio C Hamano

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20160903180344.truur5ey6j6ah2wh@x \
    --to=josh@joshtriplett.org \
    --cc=git@vger.kernel.org \
    --cc=gitster@pobox.com \
    --cc=johannes.schindelin@gmx.de \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body. 
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.