--- a/src/cmp.rs	Sat Oct 21 14:26:38 2017 +0200
+++ b/src/cmp.rs	Sat Oct 21 18:59:41 2017 +0200
@@ -88,15 +88,7 @@
 
 impl Cmp for InternalKeyCmp {
     fn cmp(&self, a: &[u8], b: &[u8]) -> Ordering {
-        let (_, seqa, keya) = key_types::parse_internal_key(a);
-        let (_, seqb, keyb) = key_types::parse_internal_key(b);
-
-        match self.0.cmp(keya, keyb) {
-            Ordering::Less => Ordering::Less,
-            Ordering::Greater => Ordering::Greater,
-            // reverse comparison!
-            Ordering::Equal => seqb.cmp(&seqa),
-        }
+        key_types::cmp_internal_key(self.0.as_ref().as_ref(), a, b)
     }
 
     fn id(&self) -> &'static str {

--- a/src/key_types.rs	Sat Oct 21 14:26:38 2017 +0200
+++ b/src/key_types.rs	Sat Oct 21 18:59:41 2017 +0200
@@ -1,5 +1,8 @@
+
+use cmp::Cmp;
 use types::SequenceNumber;
 
+use std::cmp::Ordering;
 use std::io::Write;
 
 use integer_encoding::{FixedInt, VarInt, VarIntWriter, FixedIntWriter};
@@ -93,6 +96,20 @@
     }
 }
 
+/// cmp_internal_key efficiently compares to keys in InternalKey format.
+pub fn cmp_internal_key<'a, 'b>(ucmp: &Cmp, a: InternalKey<'a>, b: InternalKey<'b>) -> Ordering {
+    match ucmp.cmp(&a[0..a.len() - 8], &b[0..b.len() - 8]) {
+        Ordering::Less => Ordering::Less,
+        Ordering::Greater => Ordering::Greater,
+        Ordering::Equal => {
+            let seqa = parse_tag(FixedInt::decode_fixed(&a[a.len() - 8..])).1;
+            let seqb = parse_tag(FixedInt::decode_fixed(&b[b.len() - 8..])).1;
+            // reverse comparison!
+            seqb.cmp(&seqa)
+        }
+    }
+}
+
 /// A memtable key is a bytestring containing (keylen, key, tag, vallen, val). This function
 /// builds such a key. It's called key because the underlying Map implementation will only be
 /// concerned with keys; the value field is not used (instead, the value is encoded in the key,