From 2a3d9a06c9a1e6fd4d45eb7c89fd867ca641c563 Mon Sep 17 00:00:00 2001 From: Eli Zaretskii Date: Sun, 16 Mar 2014 18:28:34 +0200 Subject: [PATCH] Fix bug #16830 with slow search for newlines in forward-line. src/search.c (find_newline): Speed up the function when using the newline cache, by halving the number of calls to region_cache_forward and region_cache_backward. --- src/ChangeLog | 6 +++ src/search.c | 108 ++++++++++++++++++++++++++++++++++++++++++-------- 2 files changed, 98 insertions(+), 16 deletions(-) diff --git a/src/ChangeLog b/src/ChangeLog index 424416398e8..30692059f03 100644 --- a/src/ChangeLog +++ b/src/ChangeLog @@ -1,3 +1,9 @@ +2014-03-16 Eli Zaretskii + + * search.c (find_newline): Speed up the function when using the + newline cache, by halving the number of call to + region_cache_forward and region_cache_backward. (Bug#16830) + 2014-03-15 Juanma Barranquero * buffer.c (Fset_buffer): Document return value (bug#17015). diff --git a/src/search.c b/src/search.c index 40ab5db495a..3de194c5056 100644 --- a/src/search.c +++ b/src/search.c @@ -715,19 +715,62 @@ find_newline (ptrdiff_t start, ptrdiff_t start_byte, ptrdiff_t end, examine. */ ptrdiff_t tem, ceiling_byte = end_byte - 1; - /* If we're looking for a newline, consult the newline cache - to see where we can avoid some scanning. */ + /* If we're using the newline cache, consult it to see whether + we can avoid some scanning. */ if (newline_cache) { ptrdiff_t next_change; + int result = 1; + immediate_quit = 0; - while (region_cache_forward - (cache_buffer, newline_cache, start, &next_change)) - start = next_change; + while (start < end && result) + { + ptrdiff_t lim1; + + result = region_cache_forward (cache_buffer, newline_cache, + start, &next_change); + if (result) + { + start = next_change; + lim1 = next_change = end; + } + else + lim1 = min (next_change, end); + + /* The cache returned zero for this region; see if + this is because the region is known and includes + only newlines. While at that, count any newlines + we bump into, and exit if we found enough off them. */ + start_byte = CHAR_TO_BYTE (start); + while (start < lim1 + && FETCH_BYTE (start_byte) == '\n') + { + start_byte++; + start++; + if (--count == 0) + { + if (bytepos) + *bytepos = start_byte; + return start; + } + } + /* If we found a non-newline character before hitting + position where the cache will again return non-zero + (i.e. no newlines beyond that position), it means + this region is not yet known to the cache, and we + must resort to the "dumb loop" method. */ + if (start < next_change && !result) + break; + result = 1; + } + if (start >= end) + { + start = end; + start_byte = end_byte; + break; + } immediate_quit = allow_quit; - start_byte = CHAR_TO_BYTE (start); - /* START should never be after END. */ if (start_byte > ceiling_byte) start_byte = ceiling_byte; @@ -762,9 +805,9 @@ find_newline (ptrdiff_t start, ptrdiff_t start_byte, ptrdiff_t end, unsigned char *nl = memchr (lim_addr + cursor, '\n', - cursor); next = nl ? nl - lim_addr : 0; - /* If we're looking for newlines, cache the fact that - this line's region is free of them. */ - if (newline_cache) + /* If we're using the newline cache, cache the fact that + the region we just traversed is free of newlines. */ + if (newline_cache && cursor != next) { know_region_cache (cache_buffer, newline_cache, BYTE_TO_CHAR (lim_byte + cursor), @@ -800,14 +843,47 @@ find_newline (ptrdiff_t start, ptrdiff_t start_byte, ptrdiff_t end, if (newline_cache) { ptrdiff_t next_change; + int result = 1; + immediate_quit = 0; - while (region_cache_backward - (cache_buffer, newline_cache, start, &next_change)) - start = next_change; + while (start > end && result) + { + ptrdiff_t lim1; + + result = region_cache_backward (cache_buffer, newline_cache, + start, &next_change); + if (result) + { + start = next_change; + lim1 = next_change = end; + } + else + lim1 = max (next_change, end); + start_byte = CHAR_TO_BYTE (start); + while (start > lim1 + && FETCH_BYTE (start_byte - 1) == '\n') + { + if (++count == 0) + { + if (bytepos) + *bytepos = start_byte; + return start; + } + start_byte--; + start--; + } + if (start > next_change && !result) + break; + result = 1; + } + if (start <= end) + { + start = end; + start_byte = end_byte; + break; + } immediate_quit = allow_quit; - start_byte = CHAR_TO_BYTE (start); - /* Start should never be at or before end. */ if (start_byte <= ceiling_byte) start_byte = ceiling_byte + 1; @@ -840,7 +916,7 @@ find_newline (ptrdiff_t start, ptrdiff_t start_byte, ptrdiff_t end, /* If we're looking for newlines, cache the fact that this line's region is free of them. */ - if (newline_cache) + if (newline_cache && cursor != prev + 1) { know_region_cache (cache_buffer, newline_cache, BYTE_TO_CHAR (ceiling_byte + prev + 1), -- 2.39.2