Index: sys/vm/_vm_phys.h
===================================================================
--- sys/vm/_vm_phys.h
+++ sys/vm/_vm_phys.h
@@ -64,6 +64,8 @@
 	void		*md_first;
 #endif
 	int		domain;
+	short		left;
+	short		right;
 	struct vm_freelist (*free_queues)[VM_NFREEPOOL][VM_NFREEORDER_MAX];
 };
 
Index: sys/vm/vm_phys.c
===================================================================
--- sys/vm/vm_phys.c
+++ sys/vm/vm_phys.c
@@ -82,6 +82,7 @@
 
 struct vm_phys_seg __read_mostly vm_phys_segs[VM_PHYSSEG_MAX];
 int __read_mostly vm_phys_nsegs;
+static short __read_mostly vm_phys_segs_root;
 static struct vm_phys_seg vm_phys_early_segs[8];
 static int vm_phys_early_nsegs;
 
@@ -577,8 +578,17 @@
 	/*
 	 * Coalesce physical memory segments that are contiguous and share the
 	 * same per-domain free queues.
+	 *
+	 * Maintain a heap of coalesced memory segments, with biggest segments
+	 * at the top of the heap. 'vm_phys_segs_root' identifies the top of
+	 * the heap. Offsets 'left' and 'right' locate children of heap
+	 * elements.  Offset zero indicates no child.  During construction,
+	 * the links along the right fringe of the heap point backwards,
+	 * and are reversed to complete the heap.
 	 */
 	prev_seg = vm_phys_segs;
+	prev_seg->left = 0;
+	prev_seg->right = 0;
 	seg = &vm_phys_segs[1];
 	end_seg = &vm_phys_segs[vm_phys_nsegs];
 	while (seg < end_seg) {
@@ -587,16 +597,39 @@
 			prev_seg->end = seg->end;
 			KASSERT(prev_seg->domain == seg->domain,
 			    ("vm_phys_init: free queues cannot span domains"));
-			vm_phys_nsegs--;
 			end_seg--;
 			for (tmp_seg = seg; tmp_seg < end_seg; tmp_seg++)
 				*tmp_seg = *(tmp_seg + 1);
 		} else {
+			segind = 0;
+			tmp_seg = seg;
+			do {
+				if (seg->end - seg->start <=
+				    prev_seg->end - prev_seg->start)
+					break;
+				tmp_seg = prev_seg;
+				prev_seg -= prev_seg->right;
+				tmp_seg->right = segind;
+				segind = tmp_seg - prev_seg;
+			} while (tmp_seg != prev_seg);
+			if (tmp_seg == prev_seg)
+				prev_seg = seg;
+			seg->left = seg - tmp_seg;
+			seg->right = seg - prev_seg;
 			prev_seg = seg;
 			seg++;
 		}
 	}
-
+	vm_phys_nsegs = end_seg - vm_phys_segs;
+	segind = 0;
+	do {
+		tmp_seg = prev_seg;
+		prev_seg -= prev_seg->right;
+		tmp_seg->right = segind;
+		segind = tmp_seg - prev_seg;
+	} while (tmp_seg != prev_seg);
+	vm_phys_segs_root = prev_seg - vm_phys_segs;
+	
 	/*
 	 * Initialize the free queues.
 	 */
@@ -876,6 +909,38 @@
 }
 
 /*
+ * Find the last segment before the given physical address.
+ */
+static int
+vm_phys_addr_to_seg(vm_paddr_t pa)
+{
+	int segind;
+	
+#if 0
+	for (segind = vm_phys_nsegs - 1;
+	    segind >= 0 && vm_phys_segs[segind].start >= pa; segind--);
+#else
+	segind = vm_phys_segs_root;
+	for (;;) {
+		if (pa < vm_phys_segs[segind].start) {
+			if (vm_phys_segs[segind].left == 0) {
+				--segind;
+				break;
+			}
+			segind -= vm_phys_segs[segind].left;
+			
+		} else if (vm_phys_segs[segind].end <= pa) {
+			if (vm_phys_segs[segind].right == 0)
+				break;
+			segind += vm_phys_segs[segind].right;
+		} else
+			break;
+	}
+#endif
+	return (segind);
+}
+
+/*
  * Find the vm_page corresponding to the given physical address.
  */
 vm_page_t
@@ -884,9 +949,10 @@
 	struct vm_phys_seg *seg;
 	int segind;
 
-	for (segind = 0; segind < vm_phys_nsegs; segind++) {
+	segind = vm_phys_addr_to_seg(pa);
+	if (segind >= 0) {
 		seg = &vm_phys_segs[segind];
-		if (pa >= seg->start && pa < seg->end)
+		if (pa < seg->end)
 			return (&seg->first_page[atop(pa - seg->start)]);
 	}
 	return (NULL);
@@ -1236,7 +1302,7 @@
 vm_phys_scan_contig(int domain, u_long npages, vm_paddr_t low, vm_paddr_t high,
     u_long alignment, vm_paddr_t boundary, int options)
 {
-	vm_paddr_t pa_end;
+	vm_paddr_t pa_end, pa_start;
 	vm_page_t m_end, m_run, m_start;
 	struct vm_phys_seg *seg;
 	int segind;
@@ -1246,22 +1312,21 @@
 	KASSERT(powerof2(boundary), ("boundary is not a power of 2"));
 	if (low >= high)
 		return (NULL);
-	for (segind = 0; segind < vm_phys_nsegs; segind++) {
+	for (segind = vm_phys_addr_to_seg(high); segind >= 0; segind--) {
 		seg = &vm_phys_segs[segind];
 		if (seg->domain != domain)
 			continue;
-		if (seg->start >= high)
+		if (low >= seg->end)
 			break;
-		if (low >= seg->end)
-			continue;
 		if (low <= seg->start)
-			m_start = seg->first_page;
+			pa_start = seg->start;
 		else
-			m_start = &seg->first_page[atop(low - seg->start)];
+			pa_start = low;
 		if (high < seg->end)
 			pa_end = high;
 		else
 			pa_end = seg->end;
+		m_start = &seg->first_page[atop(pa_start - seg->start)];
 		if (pa_end - VM_PAGE_TO_PHYS(m_start) < ptoa(npages))
 			continue;
 		m_end = &seg->first_page[atop(pa_end - seg->start)];
@@ -1374,10 +1439,9 @@
 	vm_domain_free_assert_locked(VM_DOMAIN(domain));
 	if (low >= high)
 		return (NULL);
-	m_run = NULL;
-	for (segind = vm_phys_nsegs - 1; segind >= 0; segind--) {
+	for (segind = vm_phys_addr_to_seg(high); segind >= 0; segind--) {
 		seg = &vm_phys_segs[segind];
-		if (seg->start >= high || seg->domain != domain)
+		if (seg->domain != domain)
 			continue;
 		if (low >= seg->end)
 			break;
@@ -1394,9 +1458,9 @@
 		m_run = vm_phys_alloc_seg_contig(seg, npages, low, high,
 		    alignment, boundary);
 		if (m_run != NULL)
-			break;
+			return (m_run);
 	}
-	return (m_run);
+	return (NULL);
 }
 
 /*