diff --git a/src/regexp_bt.c b/src/regexp_bt.c
index 698ff04..5bf0e0c 100644
--- a/src/regexp_bt.c
+++ b/src/regexp_bt.c
@@ -3271,8 +3271,10 @@
 	    break;
 	}
 #ifdef FEAT_RELTIME
-	// Check for timeout once in a 100 times to avoid overhead.
-	if (tm != NULL && ++tm_count == 100)
+	// Check for timeout once in 250 times to avoid excessive overhead from
+	// reading the clock.  The value has been picked to check about once
+	// per msec on a modern CPU.
+	if (tm != NULL && ++tm_count == 250)
 	{
 	    tm_count = 0;
 	    if (profile_passed_limit(tm))
@@ -3313,7 +3315,7 @@
 	op = OP(scan);
 	// Check for character class with NL added.
 	if (!rex.reg_line_lbr && WITH_NL(op) && REG_MULTI
-			     && *rex.input == NUL && rex.lnum <= rex.reg_maxline)
+			   && *rex.input == NUL && rex.lnum <= rex.reg_maxline)
 	{
 	    reg_nextline();
 	}
@@ -4990,8 +4992,10 @@
 	    else
 		++col;
 #ifdef FEAT_RELTIME
-	    // Check for timeout once in a twenty times to avoid overhead.
-	    if (tm != NULL && ++tm_count == 20)
+	    // Check for timeout once in 500 times to avoid excessive overhead
+	    // from reading the clock.  The value has been picked to check
+	    // about once per msec on a modern CPU.
+	    if (tm != NULL && ++tm_count == 500)
 	    {
 		tm_count = 0;
 		if (profile_passed_limit(tm))
diff --git a/src/regexp_nfa.c b/src/regexp_nfa.c
index 511b904..1e7cd9b 100644
--- a/src/regexp_nfa.c
+++ b/src/regexp_nfa.c
@@ -5649,11 +5649,27 @@
     static int
 nfa_did_time_out()
 {
-    if (nfa_time_limit != NULL && profile_passed_limit(nfa_time_limit))
+    static int tm_count = 0;
+
+    // Check for timeout once in 800 times to avoid excessive overhead from
+    // reading the clock.  The value has been picked to check about once per
+    // msec on a modern CPU.
+    if (nfa_time_limit != NULL)
     {
-	if (nfa_timed_out != NULL)
-	    *nfa_timed_out = TRUE;
-	return TRUE;
+	if (tm_count == 800)
+	{
+	    if (profile_passed_limit(nfa_time_limit))
+	    {
+		if (nfa_timed_out != NULL)
+		    *nfa_timed_out = TRUE;
+		return TRUE;
+	    }
+	    // Only reset the count when not timed out, so that when it did
+	    // timeout it keeps timing out until the time limit is changed.
+	    tm_count = 0;
+	}
+	else
+	    ++tm_count;
     }
     return FALSE;
 }
diff --git a/src/version.c b/src/version.c
index 3cc224e..480ff28 100644
--- a/src/version.c
+++ b/src/version.c
@@ -735,6 +735,8 @@
 static int included_patches[] =
 {   /* Add new patch number below this line */
 /**/
+    5028,
+/**/
     5027,
 /**/
     5026,