[vim/vim] Rework addstate_here() for performance (PR #20756)

[John Marriott]

This PR attempts to address an item in todo.txt concerning function addstate_here(), dated 18-Feb-2019.

When addstate_here() adds nfa_thread_T elements to the array l, it maintains the correct sequence by potentially reallocating the array and rearranging the array's elements using calls to mch_memmove() to physically move the memory blocks into position.

This PR changes this by treating the array as a psuedo linked list. It adds previous and next indexes to each element. In addition, first and last indexes are added to the list itself. When new elements are added to the array, only these indices need to be adjusted to maintain the correct sequence. This removes the need to reallocate the array and move around array elements to maintain the sequence.

Obviously, this will leave elements in the array that are no longer being referenced (ie deactivated), but I think that is more than made up for by the increase in performance (O(n) vs O(1)).

Example

Before the change
Consider this array of nfa_thread_T elements:

Index: 0  1  2
Seqn:  0  1  2
     +--+--+--+
     | A| B| C|
     +--+--+--+

After calling addstate_here() to replace index 1 ('B') with new elements 'D', 'E' and 'F':

Index: 0  1  2  3  4
Seqn:  0  1  2  3  4
     +--+--+--+--+--+
     | A| D| E| F| C|
     +--+--+--+--+--+

After this change
Here is the same array with it's previous and next indexes:

Index: 0  1  2
Seqn:  0  1  2
     +--+--+--+
     | A| B| C|
     +--+--+--+
Prev:  -  0  1
Next:  1  2  -
First: 0
Last:  2

After calling addstate_here() to replace index 1 ('B') with new elements 'D', 'E' and 'F':

Index: 0  1  2  3  4  5
Seqn:  0     4  1  2  3
     +--+--+--+--+--+--+
     | A| B| C| D| E| F|
     +--+--+--+--+--+--+
Prev:  -     5  0  3  4
Next:  3     -  4  5  2
First: 0
Last:  2

Also:
In function addstate(), move some variables closer to where they are used.

I have been using this code in my own builds for a few weeks now but I welcome any feedback.

I hope this makes sense.
Cheers
John

---

You can view, comment on, or merge this pull request online at:

  https://github.com/vim/vim/pull/20756

Commit Summary

• e968301 Rework addstate_here() for performance
• a6f5115 Fix typo

File Changes

(1 file)

• M src/regexp_nfa.c (183)

Patch Links:

• https://github.com/vim/vim/pull/20756.patch
• https://github.com/vim/vim/pull/20756.diff

—
Reply to this email directly, view it on GitHub, or unsubscribe.
Triage notifications, keep track of coding agent tasks and review pull requests on the go with GitHub Mobile for iOS and Android. Download it today!
You are receiving this because you are subscribed to this thread.Message ID: <vim/vim/pull/20756@github.com>

[h_east]

h-east left a comment (vim/vim#20756)

Since you mentioned it's "for performance" shouldn't you also include a comparison of processing times before and after the change?

—
Reply to this email directly, view it on GitHub, or unsubscribe.
Triage notifications, keep track of coding agent tasks and review pull requests on the go with GitHub Mobile for iOS and Android. Download it today!

You are receiving this because you are subscribed to this thread.Message ID: <vim/vim/pull/20756/c4955194399@github.com>

[John Marriott]

basilisk0315 left a comment (vim/vim#20756)

I selected a few tests (from testdir) and ran each one 10 times. I then removed the best and worst of each run leaving 8 results which were averaged. Here are the averages (all measurements are in seconds):
Test: test_alot.vim
Original: 13.313
New: 9.037
Diff: +4.275

Test: test_alot_latin.vim
Original: 1.163
New: 1.116
Diff: +0.047

Test: test_regexp_latin.vim
Original: 1.039
New: 1.098
Diff: -0.059

Test: test_subsitute.vim
Original: 1.097
New: 1.282
Diff: -0.184

Test: test_hightlight.vim
Original: 10.888
New: 8.691
Diff: +2.197

All of these measurements were taken on my archlinux VM running on a Windows 11 host.

—
Reply to this email directly, view it on GitHub, or unsubscribe.
Triage notifications, keep track of coding agent tasks and review pull requests on the go with GitHub Mobile for iOS and Android. Download it today!

You are receiving this because you are subscribed to this thread.Message ID: <vim/vim/pull/20756/c4964168182@github.com>

[h_east]

h-east left a comment (vim/vim#20756)

Thanks for the follow-up numbers.

What is the basis for selecting these particular tests?

The tests you picked do not go through the code path this PR changes.
Even so, your numbers show a difference between Original and New.
That suggests there is also a problem in how the measurements were taken.

More fundamentally: do you actually understand which path exercises the
code that this PR modifies?

If you want to make a performance case, please:

• Measure master vs this branch on the same machine, interleaved, several
  runs each.
• Use the existing benchmark src/testdir/test_bench_regexp.vim (run it with
  make benchmark). It reports the time for re=0, re=1 and re=2
  separately, so you can isolate re=2, which is the engine this PR changes.
  Note that on a slow machine the re=2 run may be capped by the search()
  timeout (its 4th argument, 10000 ms) and saturate around 10s. If that
  happens, raise that 4th argument from 10000 to 100000 so the search runs
  to completion.
• Put the resulting before/after numbers (re=2 in particular) in the PR
  description up front.

—
Reply to this email directly, view it on GitHub, or unsubscribe.
Triage notifications, keep track of coding agent tasks and review pull requests on the go with GitHub Mobile for iOS and Android. Download it today!

You are receiving this because you are subscribed to this thread.Message ID: <vim/vim/pull/20756/c4967781421@github.com>

[John Marriott]

basilisk0315 left a comment (vim/vim#20756)

The tests you picked do not go through the code path this PR changes.

Interesting you say that. In my measurements, running those tests resulted in addstate_here() being called as follows:

Test	# Calls(1)	# Times Change was exercised(2)
test_alot.vim	34,264	4,132
test_alot_latin.vim	7,506	740
test_regexp_latin.vim	7,506	740
test_subsitute.vim	640	14
test_hightlight.vim	2,737	13

(1) # Calls was measured by gprof.
(2) # Time Change was exercised was measured by adding a fprintf statement to the end of addstate_here() and counting them up.

More fundamentally: do you actually understand which path exercises the
code that this PR modifies?

Given the above, what am I missing?

If you want to make a performance case of a regular expression engine, please:

Thanks for your suggestion.

—
Reply to this email directly, view it on GitHub, or unsubscribe.
Triage notifications, keep track of coding agent tasks and review pull requests on the go with GitHub Mobile for iOS and Android. Download it today!

You are receiving this because you are subscribed to this thread.Message ID: <vim/vim/pull/20756/c4975511296@github.com>