diff --git a/src/regexp_nfa.c b/src/regexp_nfa.c
index 191cddb..40e7448 100644
--- a/src/regexp_nfa.c
+++ b/src/regexp_nfa.c
@@ -4237,6 +4237,27 @@
     return TRUE;
 }
 
+#ifdef FEAT_RELTIME
+/*
+ * Check if we are past the time limit, if there is one.
+ */
+    static int
+nfa_did_time_out(void)
+{
+    if (*timeout_flag)
+    {
+	if (nfa_timed_out != NULL)
+	{
+	    if (!*nfa_timed_out)
+		ch_log(NULL, "NFA regexp timed out");
+	    *nfa_timed_out = TRUE;
+	}
+	return TRUE;
+    }
+    return FALSE;
+}
+#endif
+
 #ifdef ENABLE_LOG
     static void
 open_debug_log(int result)
@@ -4451,7 +4472,7 @@
 /*
  * Add "state" and possibly what follows to state list ".".
  * Returns "subs_arg", possibly copied into temp_subs.
- * Returns NULL when recursiveness is too deep.
+ * Returns NULL when recursiveness is too deep or timed out.
  */
     static regsubs_T *
 addstate(
@@ -4480,6 +4501,11 @@
 #endif
     static int		depth = 0;
 
+#ifdef FEAT_RELTIME
+    if (nfa_did_time_out())
+	return NULL;
+#endif
+
     // This function is called recursively.  When the depth is too much we run
     // out of stack and crash, limit recursiveness here.
     if (++depth >= 5000 || subs == NULL)
@@ -5643,24 +5669,6 @@
     return 0L;
 }
 
-#ifdef FEAT_RELTIME
-/*
- * Check if we are past the time limit, if there is one.
- * To reduce overhead, only check one in "count" times.
- */
-    static int
-nfa_did_time_out(void)
-{
-    if (*timeout_flag)
-    {
-	if (nfa_timed_out != NULL)
-	    *nfa_timed_out = TRUE;
-	return TRUE;
-    }
-    return FALSE;
-}
-#endif
-
 /*
  * Main matching routine.
  *
@@ -5708,7 +5716,6 @@
     if (got_int)
 	return FALSE;
 #ifdef FEAT_RELTIME
-    // Check relatively often here, since this is the toplevel matching.
     if (nfa_did_time_out())
 	return FALSE;
 #endif
@@ -7109,7 +7116,6 @@
 	if (got_int)
 	    break;
 #ifdef FEAT_RELTIME
-	// Check for timeout once in a twenty times to avoid overhead.
 	if (nfa_did_time_out())
 	    break;
 #endif