--- a/OrderedCollection.st	Fri May 13 23:48:14 2016 +0200
+++ b/OrderedCollection.st	Sat May 14 15:22:31 2016 +0200
@@ -745,22 +745,38 @@
      Return a collection containing the removed elements.
 
      Performance: 
-        this is an O(N) algorithm.
-
-        If a large number of objects is to be removed this way,
-        it may be better to rebuild a new collection via #select:,
-        since removing elements out of the middle is somewhat slow
-        due to the need to copy over remaining elements within the collection."
+        this is an O(N) algorithm (the receiver's elements are scanned once)."
 
     "/ this is a q&d implementation (possibly slow).
 
-    |removed element dstIndex|
-
-    removed := OrderedCollection new.
+    |removed element 
+     srcIndex "{ Class: SmallInteger }"
+     dstIndex "{ Class: SmallInteger }"|
 
-    dstIndex := firstIndex.
-    firstIndex to: lastIndex do:[:srcIndex |
+    "/ first search forward to the first element which has
+    "/ to be removed (meets the criteria)
+    srcIndex := firstIndex.
+    [ 
+        srcIndex > lastIndex
+        or:[ aBlock value:(contentsArray at:srcIndex) ]
+    ] whileFalse:[
+        srcIndex := srcIndex + 1.
+    ].
+    srcIndex > lastIndex ifTrue:[
+        "/ nothing removed
+        ^ #()
+    ].
+
+    "/ now srcIndex is the index of element, which is the first to be removed
+    removed := OrderedCollection new.
+    removed add:(contentsArray at:srcIndex).
+    
+    dstIndex := srcIndex.
+    srcIndex := srcIndex + 1.
+    
+    [ srcIndex <= lastIndex ] whileTrue:[
         element := contentsArray at:srcIndex.
+        srcIndex := srcIndex + 1.
         (aBlock value:element) ifTrue:[
             removed add:element
         ] ifFalse:[
@@ -776,31 +792,88 @@
      |coll|
 
      coll := OrderedCollection withAll:(1 to:10).
-     Transcript showCR:(coll removeAllSuchThat:[:el | el even]).
-     Transcript showCR:coll
+     Transcript show:'removed: '; showCR:(coll removeAllSuchThat:[:el | el even]).
+     Transcript show:'coll: '; showCR:coll
     "
+
     "
      |coll1 coll2|
 
+     Transcript showCR:'no element removed:'.
+
      coll1 := OrderedCollection withAll:(1 to:1000).
-     Transcript show:'(1000) - '; showCR:(
+     Transcript show:'  (1000) - '; showCR:(
+        Time millisecondsToRun:[
+            100 timesRepeat:[ coll1 copy removeAllSuchThat:[:el | el == 500] ]
+        ]).
+
+     coll2 := OrderedCollection withAll:(1 to:10000).
+     Transcript show:'  (10000) - '; showCR:(
+        Time millisecondsToRun:[
+            100 timesRepeat:[ coll2 copy removeAllSuchThat:[:el | el == 5000] ]
+        ]).
+
+     coll2 := OrderedCollection withAll:(1 to:50000).
+     Transcript show:'  (50000) - '; showCR:(
+        Time millisecondsToRun:[
+            100 timesRepeat:[ coll2 copy removeAllSuchThat:[:el | el == 25000] ]
+        ]).
+
+     Transcript showCR:'small number of elements removed:'.
+
+     coll1 := OrderedCollection withAll:(1 to:1000).
+     Transcript show:'  (1000) - '; showCR:(
+        Time millisecondsToRun:[
+            100 timesRepeat:[ coll1 copy removeAllSuchThat:[:el | el between:500 and:550] ]
+        ]).
+
+     coll2 := OrderedCollection withAll:(1 to:10000).
+     Transcript show:'  (10000) - '; showCR:(
+        Time millisecondsToRun:[
+            100 timesRepeat:[ coll2 copy removeAllSuchThat:[:el | el between:5000 and:5050] ]
+        ]).
+
+     coll2 := OrderedCollection withAll:(1 to:50000).
+     Transcript show:'  (50000) - '; showCR:(
+        Time millisecondsToRun:[
+            100 timesRepeat:[ coll2 copy removeAllSuchThat:[:el | el between:25000 and:25050] ]
+        ]).
+
+     Transcript showCR:'many elements removed:'.
+
+     coll1 := OrderedCollection withAll:(1 to:1000).
+     Transcript show:'  (1000) - '; showCR:(
         Time millisecondsToRun:[
             100 timesRepeat:[ coll1 copy removeAllSuchThat:[:el | el even] ]
         ]).
 
      coll2 := OrderedCollection withAll:(1 to:10000).
-     Transcript show:'(10000) - '; showCR:(
+     Transcript show:'  (10000) - '; showCR:(
         Time millisecondsToRun:[
             100 timesRepeat:[ coll2 copy removeAllSuchThat:[:el | el even] ]
         ]).
 
      coll2 := OrderedCollection withAll:(1 to:50000).
-     Transcript show:'(50000) - '; showCR:(
+     Transcript show:'  (50000) - '; showCR:(
         Time millisecondsToRun:[
             100 timesRepeat:[ coll2 copy removeAllSuchThat:[:el | el even] ]
         ]).
     "
-
+    "
+                    compiled bytecode bytecode/new (no jitter)
+        no element removed:
+          (1000)  -  10          20         20
+          (10000) -  70         240        200 
+          (50000) - 390        1190        940  
+        small number of elements removed:
+          (1000)  -  10          30         20
+          (10000) - 160         300        260 
+          (50000) - 700        1540       1180
+        many elements removed:
+          (1000)  -  10          20         30
+          (10000) - 130         290        260 
+          (50000) - 720        1470       1300  
+    "    
     "Modified: 8.2.1997 / 19:19:00 / cg"
 !