diff --git a/src/os_unix.c b/src/os_unix.c
index 6fd2450..083fd8f 100644
--- a/src/os_unix.c
+++ b/src/os_unix.c
@@ -8251,7 +8251,7 @@
 /*
  * Implement timeout with timer_create() and timer_settime().
  */
-static int	timeout_flag = FALSE;
+static volatile int timeout_flag = FALSE;
 static timer_t	timer_id;
 static int	timer_created = FALSE;
 
@@ -8296,7 +8296,7 @@
  * This function is not expected to fail, but if it does it will still return a
  * valid flag pointer; the flag will remain stuck as FALSE .
  */
-    const int *
+    volatile int *
 start_timeout(long msec)
 {
     struct itimerspec interval = {
@@ -8324,6 +8324,8 @@
 	timer_created = TRUE;
     }
 
+    ch_log(NULL, "setting timeout timer to %d sec %ld nsec",
+	       (int)interval.it_value.tv_sec, (long)interval.it_value.tv_nsec);
     ret = timer_settime(timer_id, 0, &interval, NULL);
     if (ret < 0)
 	semsg(_(e_could_not_set_timeout_str), strerror(errno));
@@ -8351,7 +8353,7 @@
  */
 static struct itimerval prev_interval;
 static struct sigaction prev_sigaction;
-static int		timeout_flag         = FALSE;
+static volatile int	timeout_flag         = FALSE;
 static int		timer_active         = FALSE;
 static int		timer_handler_active = FALSE;
 static int		alarm_pending        = FALSE;
@@ -8409,7 +8411,7 @@
  * This function is not expected to fail, but if it does it will still return a
  * valid flag pointer; the flag will remain stuck as FALSE .
  */
-    const int *
+    volatile int *
 start_timeout(long msec)
 {
     struct itimerval	interval = {
diff --git a/src/proto/os_unix.pro b/src/proto/os_unix.pro
index 268f3bf..a8e961b 100644
--- a/src/proto/os_unix.pro
+++ b/src/proto/os_unix.pro
@@ -87,6 +87,6 @@
 void xsmp_init(void);
 void xsmp_close(void);
 void stop_timeout(void);
-const int *start_timeout(long msec);
+volatile int *start_timeout(long msec);
 void delete_timer(void);
 /* vim: set ft=c : */
diff --git a/src/regexp.c b/src/regexp.c
index 3d08d5a..0a6a8af 100644
--- a/src/regexp.c
+++ b/src/regexp.c
@@ -22,7 +22,7 @@
 
 #ifdef FEAT_RELTIME
 static int dummy_timeout_flag = 0;
-static const int *timeout_flag = &dummy_timeout_flag;
+static volatile int *timeout_flag = &dummy_timeout_flag;
 #endif
 
 /*
diff --git a/src/regexp_bt.c b/src/regexp_bt.c
index e307c41..c007b81 100644
--- a/src/regexp_bt.c
+++ b/src/regexp_bt.c
@@ -3152,6 +3152,27 @@
     regstack.ga_len -= sizeof(regitem_T);
 }
 
+#ifdef FEAT_RELTIME
+/*
+ * Check if the timer expired, return TRUE if so.
+ */
+    static int
+bt_did_time_out(int *timed_out)
+{
+    if (*timeout_flag)
+    {
+	if (timed_out != NULL)
+	{
+	    if (!*timed_out)
+		ch_log(NULL, "BT regexp timed out");
+	    *timed_out = TRUE;
+	}
+	return TRUE;
+    }
+    return FALSE;
+}
+#endif
+
 /*
  * Save the current subexpr to "bp", so that they can be restored
  * later by restore_subexpr().
@@ -3267,10 +3288,8 @@
 	    break;
 	}
 #ifdef FEAT_RELTIME
-	if (*timeout_flag)
+	if (bt_did_time_out(timed_out))
 	{
-	    if (timed_out != NULL)
-		*timed_out = TRUE;
 	    status = RA_FAIL;
 	    break;
 	}
@@ -4687,6 +4706,14 @@
 	if (status == RA_CONT || rp == (regitem_T *)
 			     ((char *)regstack.ga_data + regstack.ga_len) - 1)
 	    break;
+
+#ifdef FEAT_RELTIME
+	if (bt_did_time_out(timed_out))
+	{
+	    status = RA_FAIL;
+	    break;
+	}
+#endif
     }
 
     // May need to continue with the inner loop, starting at "scan".
@@ -4976,12 +5003,8 @@
 	    else
 		++col;
 #ifdef FEAT_RELTIME
-	    if (*timeout_flag)
-	    {
-		if (timed_out != NULL)
-		    *timed_out = TRUE;
+	    if (bt_did_time_out(timed_out))
 		break;
-	    }
 #endif
 	}
     }
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
diff --git a/src/testdir/test_search.vim b/src/testdir/test_search.vim
index caeddc5..7b4b9fd 100644
--- a/src/testdir/test_search.vim
+++ b/src/testdir/test_search.vim
@@ -1576,10 +1576,17 @@
 
 func Test_search_timeout()
   new
+  " use a complicated pattern that should be slow with the BT engine
   let pattern = '\%#=1a*.*X\@<=b*'
-  let search_timeout = 0.02
+
+  " use a timeout of 50 msec
+  let search_timeout = 0.05
+
+  " fill the buffer so that it takes 15 times the timeout to search
   let slow_target_timeout = search_timeout * 15.0
 
+  " Fill the buffer with more and more text until searching takes more time
+  " than slow_target_timeout.
   for n in range(40, 400, 30)
       call setline(1, ['aaa', repeat('abc ', n), 'ccc'])
       let start = reltime()
@@ -1591,11 +1598,14 @@
   endfor
   call assert_true(elapsed > slow_target_timeout)
 
+  " Check that the timeout kicks in, the time should be less than half of what
+  " we measured without the timeout.  This is permissive, because the timer is
+  " known to overrun, especially when using valgrind.
   let max_time = elapsed / 2.0
   let start = reltime()
   call search(pattern, '', 0, float2nr(search_timeout * 1000))
   let elapsed = reltimefloat(reltime(start))
-  call assert_true(elapsed < max_time)
+  call assert_inrange(search_timeout * 0.9, max_time, elapsed)
 
   bwipe!
 endfunc
diff --git a/src/version.c b/src/version.c
index 3edd318..a7e622e 100644
--- a/src/version.c
+++ b/src/version.c
@@ -735,6 +735,8 @@
 static int included_patches[] =
 {   /* Add new patch number below this line */
 /**/
+    5115,
+/**/
     5114,
 /**/
     5113,