diff --git a/src/regexp_nfa.c b/src/regexp_nfa.c
index 8e069f3..369d96f 100644
--- a/src/regexp_nfa.c
+++ b/src/regexp_nfa.c
@@ -6438,14 +6438,24 @@
 	    case NFA_VCOL:
 	    case NFA_VCOL_GT:
 	    case NFA_VCOL_LT:
-		result = nfa_re_num_cmp(t->state->val, t->state->c - NFA_VCOL,
-		    (long_u)win_linetabsize(
-			    reg_win == NULL ? curwin : reg_win,
-			    regline, (colnr_T)(reginput - regline)) + 1);
-		if (result)
 		{
-		    add_here = TRUE;
-		    add_state = t->state->out;
+		    int     op = t->state->c - NFA_VCOL;
+		    colnr_T col = (colnr_T)(reginput - regline);
+
+		    /* Bail out quickly when there can't be a match, avoid the
+		     * overhead of win_linetabsize() on long lines. */
+		    if ((col > t->state->val && op != 1)
+			    || (col - 1 > t->state->val && op == 1))
+			break;
+		    result = nfa_re_num_cmp(t->state->val, op,
+			(long_u)win_linetabsize(
+				reg_win == NULL ? curwin : reg_win,
+							   regline, col) + 1);
+		    if (result)
+		    {
+			add_here = TRUE;
+			add_state = t->state->out;
+		    }
 		}
 		break;
 
@@ -6744,6 +6754,11 @@
 	    reg_nextline();
 	else
 	    break;
+
+	/* Allow interrupting with CTRL-C. */
+	fast_breakcheck();
+	if (got_int)
+	    break;
     }
 
 #ifdef ENABLE_LOG
diff --git a/src/version.c b/src/version.c
index 4f31005..1367621 100644
--- a/src/version.c
+++ b/src/version.c
@@ -742,6 +742,8 @@
 static int included_patches[] =
 {   /* Add new patch number below this line */
 /**/
+    577,
+/**/
     576,
 /**/
     575,