diff --git a/gdb/linux-nat.c b/gdb/linux-nat.c
index 509212e..ea2e4dc 100644
--- a/gdb/linux-nat.c
+++ b/gdb/linux-nat.c
@@ -677,8 +677,46 @@ linux_child_set_syscall_catchpoint (struct target_ops *self,
   return 0;
 }
 
-/* List of known LWPs.  */
+typedef struct lwp_info *lwp_info_p;
+
+DEF_VEC_P(lwp_info_p);
+
+/* List of known LWPs, sorted by LWP PID.  This speeds up the common
+   case of mapping a PID returned from the kernel to our corresponding
+   lwp_info data structure.  */
+static VEC(lwp_info_p) *lwp_list_by_lwpid;
+
+/* Head of double-linked list of known LWPs.  Sorted by reverse
+   creation order.  This order is assumed in some cases.  E.g.,
+   reaping status after killing alls lwps of a process: the leader LWP
+   must be reaped last.  */
 struct lwp_info *lwp_list;
+
+/* Add LP to sorted-by-creation-order double-linked list.  */
+
+static void
+lwp_list_add (struct lwp_info *lp)
+{
+  lp->next = lwp_list;
+  if (lwp_list != NULL)
+    lwp_list->prev = lp;
+  lwp_list = lp;
+}
+
+/* Remove LP from sorted-by-creation-order double-linked list.  */
+
+static void
+lwp_list_remove (struct lwp_info *lp)
+{
+  /* Remove from sorted-by-creation-order list.  */
+  if (lp->next != NULL)
+    lp->next->prev = lp->prev;
+  if (lp->prev != NULL)
+    lp->prev->next = lp->next;
+  if (lp == lwp_list)
+    lwp_list = lp->next;
+}
+
 
 
 /* Original signal mask.  */
@@ -759,26 +797,36 @@ lwp_free (struct lwp_info *lp)
 static void
 purge_lwp_list (int pid)
 {
-  struct lwp_info *lp, *lpprev, *lpnext;
-
-  lpprev = NULL;
+  struct lwp_info **base = VEC_address (lwp_info_p, lwp_list_by_lwpid);
+  struct lwp_info **lp_out_p;
+  struct lwp_info *lp_in;
+  int ix;
 
-  for (lp = lwp_list; lp; lp = lpnext)
+  lp_out_p = base;
+  for (ix = 0; VEC_iterate (lwp_info_p, lwp_list_by_lwpid, ix, lp_in); ix++)
     {
-      lpnext = lp->next;
-
-      if (ptid_get_pid (lp->ptid) == pid)
+      if (ptid_get_pid (lp_in->ptid) == pid)
 	{
-	  if (lp == lwp_list)
-	    lwp_list = lp->next;
-	  else
-	    lpprev->next = lp->next;
-
-	  lwp_free (lp);
+	  lwp_list_remove (lp_in);
+	  lwp_free (lp_in);
 	}
       else
-	lpprev = lp;
+	{
+	  *lp_out_p = lp_in;
+	  lp_out_p++;
+	}
     }
+
+  VEC_truncate (lwp_info_p, lwp_list_by_lwpid, lp_out_p - base);
+}
+
+/* Predicate function which returns true if LHS should sort before RHS
+   in a list of memory regions, useful for VEC_lower_bound.  */
+
+static int
+lp_lwpid_lessthan (struct lwp_info *lhs, struct lwp_info *rhs)
+{
+  return ptid_get_lwp (lhs->ptid) < ptid_get_lwp (rhs->ptid);
 }
 
 /* Add the LWP specified by PTID to the list.  PTID is the first LWP
@@ -799,6 +847,7 @@ static struct lwp_info *
 add_initial_lwp (ptid_t ptid)
 {
   struct lwp_info *lp;
+  int ix;
 
   gdb_assert (ptid_lwp_p (ptid));
 
@@ -812,8 +861,13 @@ add_initial_lwp (ptid_t ptid)
   lp->ptid = ptid;
   lp->core = -1;
 
-  lp->next = lwp_list;
-  lwp_list = lp;
+  /* Add to sorted-by-creation-order list.  */
+  lwp_list_add (lp);
+
+  /* Add to sorted-by-lwpid list too.  */
+  ix = VEC_lower_bound (lwp_info_p, lwp_list_by_lwpid, lp,
+			lp_lwpid_lessthan);
+  VEC_safe_insert (lwp_info_p, lwp_list_by_lwpid, ix, lp);
 
   return lp;
 }
@@ -839,27 +893,65 @@ add_lwp (ptid_t ptid)
   return lp;
 }
 
+/* Bsearch comparison function for lwp_list_by_lwpid.  */
+
+static int
+lwp_lwpid_cmp (const void *key, const void *elt)
+{
+  const long lwpid_key = *(long *) key;
+  const struct lwp_info *lp = *(const struct lwp_info **) elt;
+  const long lwpid_lp = ptid_get_lwp (lp->ptid);
+
+  if (lwpid_key < lwpid_lp)
+    return -1;
+  if (lwpid_key > lwpid_lp)
+    return 1;
+  return 0;
+}
+
+/* Find an LWP in the sorted-by-lwpid LWP vector.  Returns vector
+   index if found, or -1 if not found.  */
+
+static int
+find_lwp_by_lwpid_index (long lwpid)
+{
+  struct lwp_info **found_p;
+  struct lwp_info **base;
+  size_t nmemb;
+  size_t size;
+
+  base = VEC_address (lwp_info_p, lwp_list_by_lwpid);
+  nmemb = VEC_length (lwp_info_p, lwp_list_by_lwpid);
+  size = sizeof (struct lwp_info **);
+  found_p = (struct lwp_info **) bsearch (&lwpid, base, nmemb,
+				       size, lwp_lwpid_cmp);
+  if (found_p != NULL)
+    return found_p - base;
+
+  return -1;
+}
+
 /* Remove the LWP specified by PID from the list.  */
 
 static void
 delete_lwp (ptid_t ptid)
 {
-  struct lwp_info *lp, *lpprev;
+  struct lwp_info *lp;
+  int ix;
 
-  lpprev = NULL;
+  ix = find_lwp_by_lwpid_index (ptid_get_lwp (ptid));
+  if (ix == -1)
+    return;
 
-  for (lp = lwp_list; lp; lpprev = lp, lp = lp->next)
-    if (ptid_equal (lp->ptid, ptid))
-      break;
+  lp = VEC_index (lwp_info_p, lwp_list_by_lwpid, ix);
 
-  if (!lp)
-    return;
+  /* Remove from sorted-by-lwpid list.  */
+  VEC_ordered_remove (lwp_info_p, lwp_list_by_lwpid, ix);
 
-  if (lpprev)
-    lpprev->next = lp->next;
-  else
-    lwp_list = lp->next;
+  /* Remove from sorted-by-creation-order list.  */
+  lwp_list_remove (lp);
 
+  /* Release.  */
   lwp_free (lp);
 }
 
@@ -870,18 +962,17 @@ static struct lwp_info *
 find_lwp_pid (ptid_t ptid)
 {
   struct lwp_info *lp;
-  int lwp;
+  int lwp, ix;
 
   if (ptid_lwp_p (ptid))
     lwp = ptid_get_lwp (ptid);
   else
     lwp = ptid_get_pid (ptid);
 
-  for (lp = lwp_list; lp; lp = lp->next)
-    if (lwp == ptid_get_lwp (lp->ptid))
-      return lp;
-
-  return NULL;
+  ix = find_lwp_by_lwpid_index (lwp);
+  if (ix == -1)
+    return NULL;
+  return VEC_index (lwp_info_p, lwp_list_by_lwpid, ix);
 }
 
 /* See nat/linux-nat.h.  */
diff --git a/gdb/linux-nat.h b/gdb/linux-nat.h
index 73888e5..94fc5ed 100644
--- a/gdb/linux-nat.h
+++ b/gdb/linux-nat.h
@@ -101,7 +101,9 @@ struct lwp_info
   /* Arch-specific additions.  */
   struct arch_lwp_info *arch_private;
 
-  /* Next LWP in list.  */
+  /* Previous and next pointers in double-linked list of known LWPs,
+     sorted by reverse creation order.  */
+  struct lwp_info *prev;
   struct lwp_info *next;
 };
 
