=== modified file 'src/bidi.c'
--- src/bidi.c	2013-06-08 18:28:36 +0000
+++ src/bidi.c	2013-08-02 10:23:02 +0000
@@ -61,6 +61,7 @@
 #include "character.h"
 #include "buffer.h"
 #include "dispextern.h"
+#include "region-cache.h"
 
 static bool bidi_initialized = 0;
 
@@ -1100,7 +1101,8 @@
 {
   Lisp_Object re = paragraph_start_re;
   ptrdiff_t limit = ZV, limit_byte = ZV_BYTE;
-  ptrdiff_t n = 0;
+  struct region_cache *bpc = current_buffer->bidi_paragraph_cache;
+  ptrdiff_t n = 0, oldpos = pos, next;
 
   while (pos_byte > BEGV_BYTE
 	 && n++ < MAX_PARAGRAPH_SEARCH
@@ -1111,10 +1113,17 @@
 	 of the text over which we scan back includes
 	 paragraph_start_re?  */
       DEC_BOTH (pos, pos_byte);
-      pos = find_newline_no_quit (pos, pos_byte, -1, &pos_byte);
+      if (region_cache_backward (current_buffer, bpc, pos, &next))
+	{
+	  pos = next, pos_byte = CHAR_TO_BYTE (pos);
+	  break;
+	}
+      else
+	pos = find_newline_no_quit (pos, pos_byte, -1, &pos_byte);
     }
   if (n >= MAX_PARAGRAPH_SEARCH)
-    pos_byte = BEGV_BYTE;
+    pos = BEGV, pos_byte = BEGV_BYTE;
+  know_region_cache (current_buffer, bpc, pos, oldpos);
   return pos_byte;
 }
 

=== modified file 'src/buffer.c'
--- src/buffer.c	2013-07-16 21:35:45 +0000
+++ src/buffer.c	2013-08-02 08:42:50 +0000
@@ -590,6 +590,7 @@
 
   b->newline_cache = 0;
   b->width_run_cache = 0;
+  b->bidi_paragraph_cache = new_region_cache ();
   bset_width_table (b, Qnil);
   b->prevent_redisplay_optimizations_p = 1;
 
@@ -813,6 +814,7 @@
 
   b->newline_cache = 0;
   b->width_run_cache = 0;
+  b->bidi_paragraph_cache = new_region_cache ();
   bset_width_table (b, Qnil);
 
   name = Fcopy_sequence (name);
@@ -1957,6 +1959,11 @@
       free_region_cache (b->width_run_cache);
       b->width_run_cache = 0;
     }
+  if (b->bidi_paragraph_cache)
+    {
+      free_region_cache (b->bidi_paragraph_cache);
+      b->bidi_paragraph_cache = 0;
+    }
   bset_width_table (b, Qnil);
   unblock_input ();
   bset_undo_list (b, Qnil);
@@ -2367,6 +2374,7 @@
   current_buffer->clip_changed = 1;	other_buffer->clip_changed = 1;
   swapfield (newline_cache, struct region_cache *);
   swapfield (width_run_cache, struct region_cache *);
+  swapfield (bidi_paragraph_cache, struct region_cache *);
   current_buffer->prevent_redisplay_optimizations_p = 1;
   other_buffer->prevent_redisplay_optimizations_p = 1;
   swapfield (overlays_before, struct Lisp_Overlay *);

=== modified file 'src/buffer.h'
--- src/buffer.h	2013-07-16 21:35:45 +0000
+++ src/buffer.h	2013-08-02 08:38:14 +0000
@@ -839,9 +839,12 @@
      the character's width; if it maps a character to zero, we don't
      know what its width is.  This allows compute_motion to process
      such regions very quickly, using algebra instead of inspecting
-     each character.   See also width_table, below.  */
+     each character.   See also width_table, below.
+
+     The BIDI paragraph cache should be documented, too.  */
   struct region_cache *newline_cache;
   struct region_cache *width_run_cache;
+  struct region_cache *bidi_paragraph_cache;
 
   /* Non-zero means don't use redisplay optimizations for
      displaying this buffer.  */

=== modified file 'src/insdel.c'
--- src/insdel.c	2013-08-02 08:32:32 +0000
+++ src/insdel.c	2013-08-02 08:40:09 +0000
@@ -1873,6 +1873,10 @@
     invalidate_region_cache (current_buffer,
                              current_buffer->width_run_cache,
                              start - BEG, Z - end);
+  if (current_buffer->bidi_paragraph_cache)
+    invalidate_region_cache (current_buffer,
+                             current_buffer->bidi_paragraph_cache,
+                             start - BEG, Z - end);
 
   Vdeactivate_mark = Qt;
 }