=== modified file 'src/alloc.c'
--- src/alloc.c	2012-10-10 15:31:21 +0000
+++ src/alloc.c	2012-10-12 06:21:37 +0000
@@ -3324,8 +3324,10 @@
   register Lisp_Object overlay;
 
   overlay = allocate_misc (Lisp_Misc_Overlay);
-  OVERLAY_START (overlay) = start;
-  OVERLAY_END (overlay) = end;
+  XOVERLAY (overlay)->start = start;
+  XMARKER (start)->overlay_boundary = 1;
+  XOVERLAY (overlay)->end = end;
+  XMARKER (end)->overlay_boundary = 1;
   set_overlay_plist (overlay, plist);
   XOVERLAY (overlay)->next = NULL;
   return overlay;
@@ -3345,6 +3347,7 @@
   p->charpos = 0;
   p->next = NULL;
   p->insertion_type = 0;
+  p->overlay_boundary = 0;
   return val;
 }
 
@@ -3369,6 +3372,7 @@
   m->charpos = charpos;
   m->bytepos = bytepos;
   m->insertion_type = 0;
+  m->overlay_boundary = 0;
   m->next = BUF_MARKERS (buf);
   BUF_MARKERS (buf) = m;
   return obj;

=== modified file 'src/buffer.c'
--- src/buffer.c	2012-10-12 01:47:40 +0000
+++ src/buffer.c	2012-10-12 06:11:47 +0000
@@ -146,9 +146,17 @@
 static void alloc_buffer_text (struct buffer *, ptrdiff_t);
 static void free_buffer_text (struct buffer *b);
 static struct Lisp_Overlay * copy_overlays (struct buffer *, struct Lisp_Overlay *);
-static void modify_overlay (struct buffer *, ptrdiff_t, ptrdiff_t);
+static void modify_range (struct buffer *, ptrdiff_t, ptrdiff_t);
 static Lisp_Object buffer_lisp_local_variables (struct buffer *, bool);
 
+static void
+modify_overlay (struct buffer *b, struct Lisp_Overlay *ov)
+{
+  eassert (b == XBUFFER (Fmarker_buffer (ov->start)));
+  eassert (b == XBUFFER (Fmarker_buffer (ov->end)));
+  modify_range (b, marker_position (ov->start), marker_position (ov->end));
+}
+
 /* These setters are used only in this file, so they can be private.  */
 static void
 bset_abbrev_mode (struct buffer *b, Lisp_Object val)
@@ -882,12 +890,9 @@
 static void
 drop_overlay (struct buffer *b, struct Lisp_Overlay *ov)
 {
-  eassert (b == XBUFFER (Fmarker_buffer (ov->start)));
-  modify_overlay (b, marker_position (ov->start),
-		  marker_position (ov->end));
-  Fset_marker (ov->start, Qnil, Qnil);
-  Fset_marker (ov->end, Qnil, Qnil);
-
+  modify_overlay (b, ov);
+  unchain_marker (XMARKER (ov->start));
+  unchain_marker (XMARKER (ov->end));
 }
 
 /* Delete all overlays of B and reset it's overlay lists.  */
@@ -895,24 +900,37 @@
 void
 delete_all_overlays (struct buffer *b)
 {
+  struct Lisp_Marker *m, **mp;
   struct Lisp_Overlay *ov, *next;
 
-  /* FIXME: Since each drop_overlay will scan BUF_MARKERS to unlink its
-     markers, we have an unneeded O(N^2) behavior here.  */
   for (ov = b->overlays_before; ov; ov = next)
     {
-      drop_overlay (b, ov);
+      modify_overlay (b, ov);
       next = ov->next;
       ov->next = NULL;
     }
 
   for (ov = b->overlays_after; ov; ov = next)
     {
-      drop_overlay (b, ov);
+      modify_overlay (b, ov);
       next = ov->next;
       ov->next = NULL;
     }
 
+  /* Unchain all overlay boundary markers at once.  */
+  for (mp = &BUF_MARKERS (b); *mp; )
+    {
+      m = *mp;
+      eassert (m->buffer == b);
+      if (m->overlay_boundary)
+	{
+	  m->buffer = NULL;
+	  *mp = m->next;
+	}
+      else
+	mp = &m->next;
+    }
+
   set_buffer_overlays_before (b, NULL);
   set_buffer_overlays_after (b, NULL);
 }
@@ -3874,10 +3892,11 @@
   return overlay;
 }
 
-/* Mark a section of BUF as needing redisplay because of overlays changes.  */
+/* Mark a section of BUF as needing redisplay because of overlays changes
+   in [START..END].  */
 
 static void
-modify_overlay (struct buffer *buf, ptrdiff_t start, ptrdiff_t end)
+modify_range (struct buffer *buf, ptrdiff_t start, ptrdiff_t end)
 {
   if (start > end)
     {
@@ -3997,20 +4016,20 @@
     {
       /* Redisplay where the overlay was.  */
       if (ob)
-        modify_overlay (ob, o_beg, o_end);
+        modify_range (ob, o_beg, o_end);
 
       /* Redisplay where the overlay is going to be.  */
-      modify_overlay (b, n_beg, n_end);
+      modify_range (b, n_beg, n_end);
     }
   else
     /* Redisplay the area the overlay has just left, or just enclosed.  */
     {
       if (o_beg == n_beg)
-	modify_overlay (b, o_end, n_end);
+	modify_range (b, o_end, n_end);
       else if (o_end == n_end)
-	modify_overlay (b, o_beg, n_beg);
+	modify_range (b, o_beg, n_beg);
       else
-	modify_overlay (b, min (o_beg, n_beg), max (o_end, n_end));
+	modify_range (b, min (o_beg, n_beg), max (o_end, n_end));
     }
 
   /* Delete the overlay if it is empty after clipping and has the
@@ -4337,9 +4356,7 @@
   if (! NILP (buffer))
     {
       if (changed)
-	modify_overlay (XBUFFER (buffer),
-			marker_position (OVERLAY_START (overlay)),
-			marker_position (OVERLAY_END   (overlay)));
+	modify_overlay (XBUFFER (buffer), XOVERLAY (overlay));
       if (EQ (prop, Qevaporate) && ! NILP (value)
 	  && (OVERLAY_POSITION (OVERLAY_START (overlay))
 	      == OVERLAY_POSITION (OVERLAY_END (overlay))))

=== modified file 'src/buffer.h'
--- src/buffer.h	2012-09-11 04:22:03 +0000
+++ src/buffer.h	2012-10-12 06:24:24 +0000
@@ -1138,11 +1138,15 @@
 
 /* Return the marker that stands for where OV starts in the buffer.  */
 
-#define OVERLAY_START(OV) XOVERLAY (OV)->start
+#define OVERLAY_START(OV)					\
+  (eassert (XMARKER (XOVERLAY (OV)->start)->overlay_boundary),	\
+   XOVERLAY (OV)->start)
 
 /* Return the marker that stands for where OV ends in the buffer.  */
 
-#define OVERLAY_END(OV) XOVERLAY (OV)->end
+#define OVERLAY_END(OV)						\
+  (eassert (XMARKER (XOVERLAY (OV)->end)->overlay_boundary),	\
+   XOVERLAY (OV)->end)
 
 /* Return the plist of overlay OV.  */
 

=== modified file 'src/lisp.h'
--- src/lisp.h	2012-10-11 16:23:37 +0000
+++ src/lisp.h	2012-10-12 06:11:48 +0000
@@ -1268,7 +1268,7 @@
 {
   ENUM_BF (Lisp_Misc_Type) type : 16;		/* = Lisp_Misc_Marker */
   unsigned gcmarkbit : 1;
-  int spacer : 13;
+  int spacer : 12;
   /* This flag is temporarily used in the functions
      decode/encode_coding_object to record that the marker position
      must be adjusted after the conversion.  */
@@ -1276,6 +1276,8 @@
   /* 1 means normal insertion at the marker's position
      leaves the marker after the inserted text.  */
   unsigned int insertion_type : 1;
+  /* 1 means this marker is used as an overlay boundary.  */
+  unsigned int overlay_boundary : 1;
   /* This is the buffer that the marker points into, or 0 if it points nowhere.
      Note: a chain of markers can contain markers pointing into different
      buffers (the chain is per buffer_text rather than per buffer, so it's