[Tuning] OrderedCollection>>identityIndexOf:replaceWith:startingAt:stoppingAt:

Would you think it possible to find a 90% improvement in something used as frequently as OrderedCollection?

The method Array>>identityIndexOf:replaceWith:startingAt:stoppingAt: uses primitive 422 and is the most efficient way to find the index position of an object in the array (replace the object with the object). It is also nice that the collection will not change during the operation. It has been part of VisualWorks since at least version 7.3.1. I think it was Andres that had added it.

Unfortunately this wonder is only implemented for Array. The primitive would only care that the receiver is a class is an #indexedType: with objects. An OrderedCollection is just a bounded form of an array. These methods can be added to OrderedCollection to make it efficient too:

OrderedCollection>>basic_identityIndexOf: oldValue replaceWith: newValue startingAt: startIndex stoppingAt: stopIndex

                "Searches the specified portion of the receiver for the first reference

                to oldValue, replacing that reference with newValue, and answers

                the 1-based index at which the oldValue was found. Zero is returned if

                the oldValue cannot be found. The search is restricted to and inclusive

                of the specified start and stop indices. The primitive fails if the start and

                stop indices are not SmallIntegers, if either is out of range, or if the

                receiver is immutable and oldValue ~~ newValue."

                <primitive: 422>

                startIndex to: stopIndex do:

                                [:idx |

                                (self basicAt: idx) == oldValue ifTrue:

                                                [newValue ~~ oldValue ifTrue:

                                                                [self basicAt: idx put: newValue].

                                                                ^idx]].

                ^0

OrderedCollection>>identityIndexOf: oldValue replaceWith: newValue startingAt: startIndex stoppingAt: stopIndex

                "Searches the specified portion of the receiver for the first reference

                to oldValue, replacing that reference with newValue, and answers

                the 1-based index at which the oldValue was found. Zero is returned if

                the oldValue cannot be found. The search is restricted to and inclusive

                of the specified start and stop indices. The primitive fails if the start and

                stop indices are not SmallIntegers, if either is out of range, or if the

                receiver is immutable and oldValue ~~ newValue."

                | basicIndex |

                ^0 == (basicIndex := self

                                basic_identityIndexOf: oldValue

                                replaceWith: newValue

                                startingAt: startIndex + firstIndex - 1

                                stoppingAt: startIndex + firstIndex - 1 + (stopIndex - startIndex))

                                                ifTrue: [0]

                                                ifFalse: [basicIndex - firstIndex + 1]

OrderedCollection>>identityIndexOf: anElement from: startIndex to: stopIndex ifAbsent: exceptionBlock

                "Answer the identity index of anElement within the receiver.  If the receiver does

                not contain anElement, answer the result of evaluating the exceptionBlock."

                | idx |

                idx := self identityIndexOf: anElement

                                                replaceWith: anElement

                                                startingAt: startIndex

                                                stoppingAt: stopIndex.

                ^idx = 0

                                ifTrue: [exceptionBlock value]

                                ifFalse: [idx]

It reduced execution time of this test by 94%:

| oc expect |

oc := ((0 to: 100001) asOrderedCollection)

                removeFirst; removeLast; yourself.

expect := 1 to: 100000.

Time millisecondsToRun: [

                oc size ~= expect size ifTrue: [self error].

                (oc identityIndexOf: 0 ifAbsent: []) notNil ifTrue: [self error].

                expect do: [:i | oc identityIndexOf: i ].

                (oc identityIndexOf: 100001 ifAbsent: []) notNil ifTrue: [self error].

                oc

].

"after tuning"

6827

"before tuning"

116880

#( 116880 6827  -94.159)

The methods should probably be added in the order shown because the last method is an override.

OrderedCollections are searched most frequently using equality rather than identity. The attached code contains an implementation of IdentityOrderedCollection that shows a 91% reduction in execution time compared to OrderedCollection>>includes:.

| oc expect |

oc := ((0 to: 100001) asIdentityOrderedCollection)

                removeFirst; removeLast; yourself.

expect := 1 to: 100000.

Time millisecondsToRun: [

                oc size ~= expect size ifTrue: [self error].

                (oc includes: 0) ifTrue: [self error].

                expect do: [:i | (oc includes: i) ifFalse: [self error] ].

                (oc includes: 100001) ifTrue: [self error].

                oc

].

"sending #asIdentityOrderedCollection"

6815

"sending #asOrderedCollection"

72710

  1 - (6815 / 72710) * -100.0

-90.6272

Paul Baumann