--- a/xpcom/typelib/xpt/tools/xpt.py
+++ b/xpcom/typelib/xpt/tools/xpt.py
@@ -97,16 +97,48 @@ def enum(*names):
     class Foo(object):
         __metaclass__ = M_add_class_attribs(enumerate(names))
 
         def __setattr__(self, name, value):  # this makes it read-only
             raise NotImplementedError
     return Foo()
 
 
+# List with constant time index() and contains() methods.
+class IndexedList(object):
+    def __init__(self, iterable):
+        self._list = []
+        self._index_map = {}
+        for i in iterable:
+            self.append(i)
+
+    def sort(self):
+        self._list.sort()
+        self._index_map = {val: i for i, val in enumerate(self._list)}
+
+    def append(self, val):
+        self._index_map[val] = len(self._list)
+        self._list.append(val)
+
+    def index(self, what):
+        return self._index_map[what]
+
+    def __contains__(self, what):
+        return what in self._index_map
+
+    def __iter__(self):
+        return iter(self._list)
+
+    def __getitem__(self, index):
+        return self._list[index]
+
+    def __len__(self):
+        return len(self._list)
+
+
 # Descriptor types as described in the spec
 class Type(object):
     """
     Data type of a method parameter or return value. Do not instantiate
     this class directly. Rather, use one of its subclasses.
 
     """
     _prefixdescriptor = struct.Struct(">B")
@@ -1145,17 +1177,17 @@ class Typelib(object):
     _header = struct.Struct(">16sBBHIII")
 
     def __init__(self, version=TYPELIB_VERSION, interfaces=[], annotations=[]):
         """
         Instantiate a new Typelib.
 
         """
         self.version = version
-        self.interfaces = list(interfaces)
+        self.interfaces = IndexedList(interfaces)
         self.annotations = list(annotations)
         self.filename = None
 
     @staticmethod
     def iid_to_string(iid):
         """
         Convert a 16-byte IID into a UUID string.