diff --git a/src/regexp_nfa.c b/src/regexp_nfa.c
index 4e111f1..5ba80f2 100644
--- a/src/regexp_nfa.c
+++ b/src/regexp_nfa.c
@@ -311,12 +311,12 @@
 static void nfa_save_listids(nfa_regprog_T *prog, int *list);
 static void nfa_restore_listids(nfa_regprog_T *prog, int *list);
 static int nfa_re_num_cmp(long_u val, int op, long_u pos);
-static long nfa_regtry(nfa_regprog_T *prog, colnr_T col, proftime_T *tm);
-static long nfa_regexec_both(char_u *line, colnr_T col, proftime_T *tm);
+static long nfa_regtry(nfa_regprog_T *prog, colnr_T col, proftime_T *tm, int *timed_out);
+static long nfa_regexec_both(char_u *line, colnr_T col, proftime_T *tm, int *timed_out);
 static regprog_T *nfa_regcomp(char_u *expr, int re_flags);
 static void nfa_regfree(regprog_T *prog);
 static int  nfa_regexec_nl(regmatch_T *rmp, char_u *line, colnr_T col, int line_lbr);
-static long nfa_regexec_multi(regmmatch_T *rmp, win_T *win, buf_T *buf, linenr_T lnum, colnr_T col, proftime_T *tm);
+static long nfa_regexec_multi(regmmatch_T *rmp, win_T *win, buf_T *buf, linenr_T lnum, colnr_T col, proftime_T *tm, int *timed_out);
 static int match_follows(nfa_state_T *startstate, int depth);
 static int failure_chance(nfa_state_T *state, int depth);
 
@@ -3959,6 +3959,7 @@
 static int nfa_match;
 #ifdef FEAT_RELTIME
 static proftime_T  *nfa_time_limit;
+static int	   *nfa_timed_out;
 static int         nfa_time_count;
 #endif
 
@@ -5508,6 +5509,20 @@
     return 0L;
 }
 
+#ifdef FEAT_RELTIME
+    static int
+nfa_did_time_out()
+{
+    if (nfa_time_limit != NULL && profile_passed_limit(nfa_time_limit))
+    {
+	if (nfa_timed_out != NULL)
+	    *nfa_timed_out = TRUE;
+	return TRUE;
+    }
+    return FALSE;
+}
+#endif
+
 /*
  * Main matching routine.
  *
@@ -5551,7 +5566,7 @@
     if (got_int)
 	return FALSE;
 #ifdef FEAT_RELTIME
-    if (nfa_time_limit != NULL && profile_passed_limit(nfa_time_limit))
+    if (nfa_did_time_out())
 	return FALSE;
 #endif
 
@@ -5694,6 +5709,19 @@
 	/* compute nextlist */
 	for (listidx = 0; listidx < thislist->n; ++listidx)
 	{
+	    /* If the list gets very long there probably is something wrong.
+	     * At least allow interrupting with CTRL-C. */
+	    fast_breakcheck();
+	    if (got_int)
+		break;
+#ifdef FEAT_RELTIME
+	    if (nfa_time_limit != NULL && ++nfa_time_count == 20)
+	    {
+		nfa_time_count = 0;
+		if (nfa_did_time_out())
+		    break;
+	    }
+#endif
 	    t = &thislist->t[listidx];
 
 #ifdef NFA_REGEXP_DEBUG_LOG
@@ -6915,7 +6943,7 @@
 	if (nfa_time_limit != NULL && ++nfa_time_count == 20)
 	{
 	    nfa_time_count = 0;
-	    if (profile_passed_limit(nfa_time_limit))
+	    if (nfa_did_time_out())
 		break;
 	}
 #endif
@@ -6948,7 +6976,8 @@
 nfa_regtry(
     nfa_regprog_T   *prog,
     colnr_T	    col,
-    proftime_T	    *tm UNUSED)	/* timeout limit or NULL */
+    proftime_T	    *tm UNUSED,	/* timeout limit or NULL */
+    int		    *timed_out UNUSED)	/* flag set on timeout or NULL */
 {
     int		i;
     regsubs_T	subs, m;
@@ -6961,6 +6990,7 @@
     reginput = regline + col;
 #ifdef FEAT_RELTIME
     nfa_time_limit = tm;
+    nfa_timed_out = timed_out;
     nfa_time_count = 0;
 #endif
 
@@ -7087,7 +7117,8 @@
 nfa_regexec_both(
     char_u	*line,
     colnr_T	startcol,	/* column to start looking for match */
-    proftime_T	*tm)		/* timeout limit or NULL */
+    proftime_T	*tm,		/* timeout limit or NULL */
+    int		*timed_out)	/* flag set on timeout or NULL */
 {
     nfa_regprog_T   *prog;
     long	    retval = 0L;
@@ -7181,7 +7212,7 @@
 	prog->state[i].lastlist[1] = 0;
     }
 
-    retval = nfa_regtry(prog, col, tm);
+    retval = nfa_regtry(prog, col, tm, timed_out);
 
     nfa_regengine.expr = NULL;
 
@@ -7340,7 +7371,7 @@
     rex.reg_icombine = FALSE;
 #endif
     rex.reg_maxcol = 0;
-    return nfa_regexec_both(line, col, NULL);
+    return nfa_regexec_both(line, col, NULL, NULL);
 }
 
 
@@ -7376,7 +7407,8 @@
     buf_T	*buf,		/* buffer in which to search */
     linenr_T	lnum,		/* nr of line to start looking for match */
     colnr_T	col,		/* column to start looking for match */
-    proftime_T	*tm)		/* timeout limit or NULL */
+    proftime_T	*tm,		/* timeout limit or NULL */
+    int		*timed_out)	/* flag set on timeout or NULL */
 {
     rex.reg_match = NULL;
     rex.reg_mmatch = rmp;
@@ -7391,7 +7423,7 @@
 #endif
     rex.reg_maxcol = rmp->rmm_maxcol;
 
-    return nfa_regexec_both(NULL, col, tm);
+    return nfa_regexec_both(NULL, col, tm, timed_out);
 }
 
 #ifdef DEBUG