Make Flog Faster

[rbong]

Update 2020/11/15: please start at the newest comments at the bottom of the page if you're interested in the latest developments on speeding up Flog

---

Flog takes a long time to run for some larger, more complex repositories.

-max-count does not solve this problem all the time because for git log --graph, git has to grab all commits before outputting anything, since you can't typically go back and redraw commits when writing output to a terminal, and it needs all commits to calculate the true branch structure.

-no-graph doesn't solve this problem perfectly either. Besides making Flog unusable as a branch viewer and turning it essentially just into a log viewer, flog still has to wait for the command to finish before outputting anything even though git immediately outputs the log. For some more complex repositories, this still causes a significant delay.

The ideal solution is to parse git log output asynchronously as it comes in, update internal data commit-by-commit, and update the buffer contents after the graph structure changes.

Note: until sorting/drawing algorithms are optimized I won't know how practical this change actually is or what concessions we'll have to make. Vimscript is a bottleneck, and even if Python ends up being better, the fact that we have to update the output buffer as soon as commits come in could be an issue. The sorting algorithm is already fairly optimized, and the drawing algorithm is very simple, and I am already seeing somewhat slower speeds than I would like.

[kevinhwang91]

I love this feature, thanks for your hard work.

[rbong]

I've racked my brain for a long time about this and experimented a bit. I think pretty much the only way we're going to get enough speed is to create a compiled binary for Flog that parses commits from git and keeps an internal record of what Flog's state and display should be. Flog, the plugin, would pretty much receive commands from this binary and do what it's told, it would just be a frontend. VimScript just isn't meant for topologically sorting hundreds or thousands of nodes in realtime and updating a visual graph, where one update can completely alter the graph. Even with the most optimized VimScript code, it would just make Flog so much more sluggish.

It's not that odd to have a plugin be a frontend for a binary. In fact, you might even say that VIM is meant for that type of plugin, although the async aspect is new. Any plugin that becomes significantly complex and slow enough is probably more appropriate as a binary. Examples: FZF, ALE, CoC.

I don't see not implementing this feature either if Flog is to have a future. This is clearly the "proper" way to handle realtime branch management, as the first party viewer gitk indicates, so I just don't see another path forward for Flog at this time. So Flog must become asynchronous if it's to be a proper branch viewer, and it must use a binary if it's to become asynchronous. However, not having a future is an option. It could be that this is just too much and you should just use an external program as a branch viewer, I haven't decided yet. Though going binary does have the benefit of allowing other programs to build Flog frontend extensions.

There are a few questions remaining though:

• Even with a backend handling all of the sorting and graph changes, does Flog become too slow just by updating huge portions of the graph constantly? This is one expensive operation that can't be avoided. Is there some way around this?
• Do we make the binary a necessary part of the plugin? Is there some benefit to still allowing the user to use Flog synchronously? How widespread is VIM 8 distributed?
• What is the proper way to bundle this binary? Should it be built and committed to the repository, or should they install it through their OS? How do other plugins handle this?

I know this is a big change, and I'm open to feedback on this approach.

[ThomasFeher]

Alternatives to separate binary:

• Neovim has built-in support for Lua which is just-in-time-compiled and should therefore be nearly as fast as a binary.
• Vim is planning to make some kind of vimscript2 for Vim 9 which will be much faster, as well.

What kind of sorting and changes is vim-flog doing? Could you show some code locations?

[rbong]

Neovim has built-in support for Lua which is just-in-time-compiled and should therefore be nearly as fast as a binary. Vim is planning to make some kind of vimscript2 for Vim 9 which will be much faster, as well.

Thank you for the suggestions. These could be great solutions. I think maybe I should build in support for different backends and do a comparison.

What kind of sorting and changes is vim-flog doing? Could you show some code locations?

It's all experimental right now and unfinished.

The pseudo code right now looks something like this:

• Start a git log command with raw commit objects in the background
• Since git doesn't have to perform topo sort, all commits are printed as it reads them
• Read the commit info including its parent commits
• Perform an insert that preserves toplogical sort to add the commit into the graph at the appropriate spot (this is how gitk roughly works) (expensive)
• Recalculate the visual representation of the graph, basically the commit structure that is drawn using --graph right now is built manually (expensive)
• Redraw the graph back in the foreground (currently expensive but unoptimized, cost can't be avoided)

If flog was using a backend, binary or otherwise, that would probably look something like this:

• Send a git log command to the backend
• The backend runs the command, performs a topo sort, updates an internal visual display of the graph, and determines optimal redraw strategy (only update new portions of the visual graph, update large chunks of the graph)
• The backend sends response messages to the Flog frontend with parsed commit data and display updates
• Flog performs the display updates and stores the parsed commit data (used for different commands)

So not much different other than separating the program out into two pieces.

[ThomasFeher]

I see, so you basically want to re-implement git --graph (or at least the graph part of it) in order to get intermediate results from it, if I understood correctly.

So this seems to be a general weakness of git --graph which would others face as well. Hence I did a quick search and found https://stackoverflow.com/a/49826884/1023843 , could that be a solution?

What would be a good repository to test on?

[rbong]

@ThomasFeher very good find.

The repository I generally test on is the Linux kernel. Doing my own testing as well now.

[rbong]

Here's what I found:

• Tested with git commit-graph write on git version 2.29.1
• After generating the commit graph, Flog becomes much more usable. It takes maybe a few hundred ms to redraw using -max_count=2000, versus taking so long that I gave up waiting
• The graph takes a long time to generate, but even after making new commits it still appears to work. I don't know how regularly, in practice, the commit graph will need to be updated
• I broke the commit graph pretty easily. I ran it once with --append, seeing if the graph could be updated quicker, and it ended up taking even longer. Subsequently, when I tried to update the graph, it took just as long. I ended up re-cloning. Just mentioning in case anyone else makes this same mistake

I will add documentation about using this command for large repositories. I think if no one finds any major problems with this in practice, it could be a satisfactory solution. I still think the proper way to implement a branch viewer is likely to follow gitk's example, but it does add a lot of complexity.

Edit: updated the documentation on how to speed up Flog

[rbong]

With the solution to increasing graph draw time, the bottleneck is now Flog's commit parsing time. I am likely going to refactor Flog to do more lazy calculations on the dev branch.

[TamaMcGlinn]

I'm not convinced that making our own binary is the only way to move forward. I wrote a little wrapper as a proof of concept which opens a new tab with :terminal fullscreen and then does git log --graph --pretty='format:%ad [%h] {%an}%d %s' --date='short' --all | less -R. The time until first screen of information for the linux kernel is about 15 seconds (with 2.2GHz processor). After doing git commit-graph write that drops to about 3 s. forest | less -R has similar performance, while flog ran for several minutes and then I decided to kill it.

It is annoying having to drop into insert mode to issue e.g. cntrl-D to the pager, but I imagine it should be possible to clean this up a bit and run the git log pager in the background, so that we can get back to a regular, non-terminal buffer.

Apart from the performance benefit, correct coloring is now also possible (and easier); the git log command can distinguish between elements it prints, so we won't get the anomolies flog shows when the commit subject contains brackets.

[rbong]

flog ran for several minutes and then I decided to kill it.

That's not quite an accurate comparison, since less will process each line of output differently than Vim.

Here's time vim -c 'read !git --no-pager log --oneline' -c 'qa!':

13.572 total

Here's time vim -c "Flog -no-graph -max-count=" -c "qa":

1:42.08 total

Similar results using --graph/not using -no-graph.

Not quite as dramatic.

I have taken several passes at optimizing individual commit processing time, but I will take another pass. Taking out individual commit processing or features is not really an option without becoming gv.vim. I will look into the current state of Lua and such too.

For now here is the suggested fix:

    let g:flog_default_arguments = {
                \ 'max_count': 2000,
                \ }

Or similar. To show 10s of thousands of commits I would not currently recommend using Flog.

Even though commit processing could be faster, asynchronous drawing is still the future of Flog or whatever comes next. Flog will always be just a hack without it. A graph viewer should build its graph incrementally, not read from git log, which builds the graph all at once.

Compare gitk, which shows output in a matter of milliseconds, and git log --graph, which takes tens of seconds to show anything. Individual commit processing time wouldn't even matter as much if Flog was asynchronous.

[rbong]

I should also say, running less in the background is not possible. You couldn't implement any of the features Flog has on top of it.

Less doesn't make the output appear faster, it just processes each commit faster. To implement any Flog features, we still need to process each commit.

[rbong]

I forgot to mention, comparisons above were done with the Linux repo.

[rbong]

Async capabilities are looking more viable now that I understand parent rewriting - this makes parsing commit output much faster. On top of that, vim 9 is coming with speed improvements. It could still be that writing this much data to a vim buffer is just not viable, but being able to do something as simple as loop quicker should help certain areas.

I'm looking into this again.

[rbong]

So my intuition is correct, vim still is not fast enough to constantly hammer the buffer with updates. Changes to the language don't help with that.

However, vimscript is now fast enough to viably draw our own graph. I was able to parse and draw 10,000 commits in the Linux repo twice as fast as we currently just parse commits.

That means that pretty graph buffer drawing without the help of git-forest is coming with vim 9, and by extension better branch highlighting.

Depending on if neovim merges vim9script, I may have to eventually write a neovim version in either vimscript or Lua.

These changes are significant enough that I'm going to call this next major update to Flog version 2 and make some breaking changes to the API that I've been waiting to make.

As far as buffer drawing goes, we will maybe have to focus more on selective buffer rendering rather than async updates. The more I think about it, async drawing might not make sense. Typical branch viewers don't have to draw to the whole screen over and over if commits are not on the screen, but we're trying to do something like that by updating the buffer constantly. Async also causes problems with things like finding the last commit.

The problem with selective buffer drawing is we have to hook into how Vim does things like searching and moving so we can update the buffer intelligently, but we can do that.

For now though, the focus in vim9script and branch drawing.

[rbong]

v2 is now out, resolving all the biggest speed issues - it draws the commit graph itself using an optimized algorithm, it automatically runs git commit-graph write, and it makes improvements to syntax highlighting.

Could it be faster? Not really, unless if Neovim adds support for Vimscript 9. And even then, not much.

I am closing this for now. If there's a particular case when Flog is slow, post a new issue