1 files changed, 16 insertions, 6 deletions
diff --git a/platform/lang-impl/src/com/intellij/util/indexing/ChangeTrackingValueContainer.java b/platform/lang-impl/src/com/intellij/util/indexing/ChangeTrackingValueContainer.java
index 913faaeefe79..c3b3cbe580ad 100644
--- a/platform/lang-impl/src/com/intellij/util/indexing/ChangeTrackingValueContainer.java
+++ b/platform/lang-impl/src/com/intellij/util/indexing/ChangeTrackingValueContainer.java
@@ -26,7 +26,6 @@ import org.jetbrains.annotations.Nullable;
 
 import java.io.DataOutput;
 import java.io.IOException;
-import java.util.Iterator;
 import java.util.List;
 
 /**
@@ -79,7 +78,7 @@ class ChangeTrackingValueContainer<Value> extends UpdatableValueContainer<Value>
 
   @NotNull
   @Override
-  public Iterator<Value> getValueIterator() {
+  public ValueIterator<Value> getValueIterator() {
     return getMergedData().getValueIterator();
   }
 
@@ -118,6 +117,7 @@ class ChangeTrackingValueContainer<Value> extends UpdatableValueContainer<Value>
         return merged;
       }
 
+      FileId2ValueMapping<Value> fileId2ValueMapping = null;
       final ValueContainer<Value> fromDisk = myInitializer.compute();
       final ValueContainerImpl<Value> newMerged;
 
@@ -127,11 +127,17 @@ class ChangeTrackingValueContainer<Value> extends UpdatableValueContainer<Value>
         newMerged = ((ChangeTrackingValueContainer<Value>)fromDisk).getMergedData().copy();
       }
 
+      if (myAdded != null && newMerged.size() > ValueContainerImpl.NUMBER_OF_VALUES_THRESHOLD) {
+        // Calculate file ids that have Value mapped to avoid O(NumberOfValuesInMerged) during removal
+        fileId2ValueMapping = new FileId2ValueMapping<Value>(newMerged);
+      }
+      final FileId2ValueMapping<Value> finalFileId2ValueMapping = fileId2ValueMapping;
       if (myInvalidated != null) {
         myInvalidated.forEach(new TIntProcedure() {
           @Override
           public boolean execute(int inputId) {
-            newMerged.removeAssociatedValue(inputId);
+            if (finalFileId2ValueMapping != null) finalFileId2ValueMapping.removeFileId(inputId);
+            else newMerged.removeAssociatedValue(inputId);
             return true;
           }
         });
@@ -140,9 +146,13 @@ class ChangeTrackingValueContainer<Value> extends UpdatableValueContainer<Value>
       if (myAdded != null) {
         myAdded.forEach(new ContainerAction<Value>() {
           @Override
-          public boolean perform(final int id, final Value value) {
-            newMerged.removeAssociatedValue(id); // enforcing "one-value-per-file for particular key" invariant
-            newMerged.addValue(id, value);
+          public boolean perform(final int inputId, final Value value) {
+            // enforcing "one-value-per-file for particular key" invariant
+            if (finalFileId2ValueMapping != null) finalFileId2ValueMapping.removeFileId(inputId);
+            else newMerged.removeAssociatedValue(inputId);
+
+            newMerged.addValue(inputId, value);
+            if (finalFileId2ValueMapping != null) finalFileId2ValueMapping.associateFileIdToValue(inputId, value);
             return true;
           }
         });