diff --git a/coregrind/m_wordfm.c b/coregrind/m_wordfm.c
index c43908e..2ddc795 100644
--- a/coregrind/m_wordfm.c
+++ b/coregrind/m_wordfm.c
@@ -418,22 +418,29 @@
 
 static
 Bool avl_find_bounds ( AvlNode* t, 
-                       /*OUT*/UWord* kMinP, /*OUT*/UWord* kMaxP,
-                       UWord minKey, UWord maxKey, UWord key,
+                       /*OUT*/UWord* kMinP, /*OUT*/UWord* vMinP,
+                       /*OUT*/UWord* kMaxP, /*OUT*/UWord* vMaxP,
+                       UWord minKey, UWord minVal,
+                       UWord maxKey, UWord maxVal,
+                       UWord key,
                        Word(*kCmp)(UWord,UWord) )
 {
-   UWord lowerBound = minKey;
-   UWord upperBound = maxKey;
+   UWord kLowerBound = minKey;
+   UWord vLowerBound = minVal;
+   UWord kUpperBound = maxKey;
+   UWord vUpperBound = maxVal;
    while (t) {
       Word cmpresS = kCmp ? kCmp(t->key, key)
                           : cmp_unsigned_Words(t->key, key);
       if (cmpresS < 0) {
-         lowerBound = t->key;
+         kLowerBound = t->key;
+         vLowerBound = t->val;
          t = t->child[1];
          continue;
       }
       if (cmpresS > 0) {
-         upperBound = t->key;
+         kUpperBound = t->key;
+         vUpperBound = t->val;
          t = t->child[0];
          continue;
       }
@@ -444,8 +451,10 @@
          maybe we could, but we're not gonna.  Ner!) */
       return False;
    }
-   *kMinP = lowerBound;
-   *kMaxP = upperBound;
+   if (kMinP) *kMinP = kLowerBound;
+   if (vMinP) *vMinP = vLowerBound;
+   if (kMaxP) *kMaxP = kUpperBound;
+   if (vMaxP) *vMaxP = vUpperBound;
    return True;
 }
 
@@ -661,10 +670,16 @@
 
 // See comment in pub_tool_wordfm.h for explanation
 Bool VG_(findBoundsFM)( WordFM* fm,
-                        /*OUT*/UWord* kMinP, /*OUT*/UWord* kMaxP,
-                        UWord minKey, UWord maxKey, UWord key )
+                        /*OUT*/UWord* kMinP, /*OUT*/UWord* vMinP,
+                        /*OUT*/UWord* kMaxP, /*OUT*/UWord* vMaxP,
+                        UWord minKey, UWord minVal,
+                        UWord maxKey, UWord maxVal,
+                        UWord key )
 {
-   return avl_find_bounds( fm->root, kMinP, kMaxP, minKey, maxKey,
+   return avl_find_bounds( fm->root, kMinP, vMinP,
+                                     kMaxP, vMaxP,
+                                     minKey, minVal, 
+                                     maxKey, maxVal,
                                      key, fm->kCmp );
 }
 
diff --git a/exp-ptrcheck/README.ABOUT.PTRCHECK.txt b/exp-ptrcheck/README.ABOUT.PTRCHECK.txt
index c528098..7c25b50 100644
--- a/exp-ptrcheck/README.ABOUT.PTRCHECK.txt
+++ b/exp-ptrcheck/README.ABOUT.PTRCHECK.txt
@@ -319,11 +319,6 @@
 
 * Extend system call checking to work on stack and global arrays
 
-* Fix big performance problem to do with heap-vs-syscall checking.
-  How: in h_main.c: get rid of get_Seg_containing_addr_SLOW and
-  implement the same by doing a search in addr_to_seg_map.  This would
-  fix the heap-vs-syscall performance problem noted above.
-
 * Print a warning if a shared object does not have debug info attached
 
 
diff --git a/exp-ptrcheck/h_main.c b/exp-ptrcheck/h_main.c
index ccce7a4..6a5d560 100644
--- a/exp-ptrcheck/h_main.c
+++ b/exp-ptrcheck/h_main.c
@@ -417,13 +417,13 @@
    }
 }
 
-static WordFM* addr_to_seg_map = NULL;
+static WordFM* addr_to_seg_map = NULL; /* GuestAddr -> Seg* */
 
 static void addr_to_seg_map_ENSURE_INIT ( void )
 {
    if (UNLIKELY(addr_to_seg_map == NULL)) {
       addr_to_seg_map = VG_(newFM)( VG_(malloc), "pc.h_main.attmEI.1",
-                                    VG_(free), NULL );
+                                    VG_(free), NULL/*unboxedcmp*/ );
    }
 }
 
@@ -780,8 +780,93 @@
    sm->vseg[sm_off] = vseg;
 }
 
+// Find the Seg which contains the given address.
 // Returns UNKNOWN if no matches.  Never returns BOTTOM or NONPTR.
 // Also, only returns in-use segments, not freed ones.
+/* Doing this fast is distinctly difficult when there are more than a
+   few heap allocated blocks live.  Basically it is done by searching
+   addr_to_seg_map for 'a'.
+
+   First, if 'a' is the start address of a segment, then we can detect
+   that by simply doing a VG_(lookupFM) of 'a', and we are done (nice
+   and easy).
+
+   If 'a' is within some segment, but does not point to the start, it
+   is much more complex.  We use VG_(findBoundsFM) to find the segment
+   with the largest .addr field which is <= a, and we then inspect the
+   segment to see if 'a' really falls inside it or not.  This is all a
+   bit complex and fragile, and so there's a lot of assertery in the
+   code below.  It has been crosschecked however against the trivial
+   _SLOW implementation shown after the end of this fn.
+*/
+static Seg* get_Seg_containing_addr( Addr a )
+{
+   UWord keyW, valW;
+   Seg*  s2;
+
+   /* Since we are going to poke around in it */
+   addr_to_seg_map_ENSURE_INIT();
+
+   /* first, see if 'a' is at the start of a block.  We do this both
+      because it's easy and more imporantly because VG_(findBoundsFM)
+      will fail in this case, so we need to exclude it first. */
+   if (VG_(lookupFM)( addr_to_seg_map, &keyW, &valW, a )) {
+      tl_assert(keyW == a);
+      s2 = (Seg*)valW;
+      tl_assert(s2->addr == a);
+   } else {
+      Bool  ok;
+      UWord kMin, vMin, kMax, vMax;
+      Seg   minSeg;
+      Seg   maxSeg;
+      UWord minAddr = 0;
+      UWord maxAddr = ~minAddr;
+      VG_(memset)(&minSeg, 0, sizeof(minSeg));
+      VG_(memset)(&maxSeg, 0, sizeof(maxSeg));
+      minSeg.addr = minAddr;
+      maxSeg.addr = maxAddr;
+      ok = VG_(findBoundsFM)( addr_to_seg_map,
+                              &kMin, &vMin, &kMax, &vMax,
+                              minAddr, (UWord)&minSeg,
+                              maxAddr, (UWord)&maxSeg, a );
+      tl_assert(ok); /* must be so, since False is only returned when
+                        'a' is directly present in the map, and we
+                        just established that it isn't. */
+      /* At this point, either vMin points at minSeg, or it points at a
+         real Seg.  In the former case, there is no live heap-allocated
+         Seg which has a start address <= a, so a is not in any block.
+         In the latter case, the Seg vMin points at may or may not
+         actually contain 'a'; we can only tell that by inspecting the
+         Seg itself. */
+      s2 = (Seg*)vMin;
+      tl_assert(kMin == s2->addr);
+      if (s2 == &minSeg) {
+         /* the former */
+         s2 = UNKNOWN;
+      } else {
+         /* the latter */
+         tl_assert(s2->addr <= a);
+         /* if s2 doesn't actually contain 'a', we must forget about it. */
+         if (s2->szB == 0 /* a zero sized block can't contain anything */
+             || s2->addr + s2->szB < a /* the usual range check */)
+            s2 = UNKNOWN;
+      }
+      /* while we're at it, do as much assertery as we can, since this
+         is all rather complex.  Either vMax points at maxSeg, or it
+         points to a real block, which must have a start address
+         greater than a. */
+      tl_assert(kMax == ((Seg*)vMax)->addr);
+      if (kMax == (UWord)&maxSeg) {
+         /* nothing we can check */
+      } else {
+         tl_assert(a < kMax); /* hence also a < ((Seg*)vMax)->addr */
+      }
+   }
+
+   return s2;
+}
+
+/* XXXX very slow reference implementation.  Do not use.
 static Seg* get_Seg_containing_addr_SLOW( Addr a )
 {
    SegGroup* group;
@@ -799,6 +884,8 @@
    }
    return UNKNOWN;
 }
+*/
+
 
 
 /*------------------------------------------------------------*/
@@ -1084,8 +1171,8 @@
    }
 
    // Check first and last bytes match
-   seglo = get_Seg_containing_addr_SLOW( s );
-   seghi = get_Seg_containing_addr_SLOW( e );
+   seglo = get_Seg_containing_addr( s );
+   seghi = get_Seg_containing_addr( e );
    tl_assert( BOTTOM != seglo && NONPTR != seglo );
    tl_assert( BOTTOM != seghi && NONPTR != seghi );
 
diff --git a/exp-ptrcheck/sg_main.c b/exp-ptrcheck/sg_main.c
index 7c0ecb4..6e2369b 100644
--- a/exp-ptrcheck/sg_main.c
+++ b/exp-ptrcheck/sg_main.c
@@ -1564,12 +1564,16 @@
            if (0) VG_(printf)("Tree sizes %ld %ld\n",
                               VG_(sizeFM)(siTrees[tid]), VG_(sizeFM)(giTree));
            sOK = VG_(findBoundsFM)( siTrees[tid], 
-                                    (UWord*)&sLB, (UWord*)&sUB,
-                                    (UWord)&sNegInf, (UWord)&sPosInf,
+                                    (UWord*)&sLB,    NULL/*unused*/,
+                                    (UWord*)&sUB,    NULL/*unused*/,
+                                    (UWord)&sNegInf, 0/*unused*/,
+                                    (UWord)&sPosInf, 0/*unused*/,
                                     (UWord)&sKey );
            gOK = VG_(findBoundsFM)( giTree,
-                                    (UWord*)&gLB, (UWord*)&gUB,
-                                    (UWord)&gNegInf, (UWord)&gPosInf,
+                                    (UWord*)&gLB,    NULL/*unused*/,
+                                    (UWord*)&gUB,    NULL/*unused*/,
+                                    (UWord)&gNegInf, 0/*unused*/,
+                                    (UWord)&gPosInf, 0/*unused*/,
                                     (UWord)&gKey );
            if (!(sOK && gOK)) {
               /* If this happens, then [ea,ea+szB) partially overlaps
diff --git a/include/pub_tool_wordfm.h b/include/pub_tool_wordfm.h
index ef9abfb..7b99490 100644
--- a/include/pub_tool_wordfm.h
+++ b/include/pub_tool_wordfm.h
@@ -105,12 +105,22 @@
 // values are returned in *kMinP and *kMaxP.  It follows that if fm is
 // empty then the returned values are simply minKey and maxKey.
 //
+// For convenience the associated value fields are also returned
+// through *vMinP and *vMaxP.  To make that possible in the general
+// case, the caller must supply via minVal and maxVal, the value
+// fields associated with minKey and maxKey.
+//
 // If the operation was successful (that is, the given key is not
 // present), True is returned.  If the given key is in fact present,
-// False is returned, and *kMinP and *kMaxP are undefined.
+// False is returned, and *kMinP, *vMinP, *kMaxP and *vMaxP are
+// undefined.  Any of kMinP, vMinP, kMaxP and vMaxP may be safely
+// supplied as NULL.
 Bool VG_(findBoundsFM)( WordFM* fm,
-                        /*OUT*/UWord* kMinP, /*OUT*/UWord* kMaxP,
-                        UWord minKey, UWord maxKey, UWord key );
+                        /*OUT*/UWord* kMinP, /*OUT*/UWord* vMinP,
+                        /*OUT*/UWord* kMaxP, /*OUT*/UWord* vMaxP,
+                        UWord minKey, UWord minVal,
+                        UWord maxKey, UWord maxVal,
+                        UWord key );
 
 // How many elements are there in fm?
 UWord VG_(sizeFM) ( WordFM* fm );