OrderedSet pitfall

FYI, in case someone else is tempted to use stock OrderedSet as a way of removing duplicates from their sequenceable collections whilst preserving their order,

values := (1 to: 500000) collect: [:i | Time millisecondClockValue].

values asSet size. 259

Time millisecondsToRun: [OrderedSet withAll: values]. 4086

Time millisecondsToRun: [(values inject: OrderedCollection new -> Set new

                into:

                                [:assoc :ea |

                                (assoc value includes: ea)

                                                ifFalse:

                                                                [assoc value add: ea.

                                                                assoc key add: ea].

                                assoc]) key]. 149

Regards,

-Boris

Heh,

values := (1 to: 500000) collect: [:i | Time microsecondClock].

values asSet size. 93303

Time millisecondsToRun: [OrderedSet withAll: values]. 1475110 "24 minutes"

Time millisecondsToRun: [(values inject: OrderedCollection new -> Set new

                into:

                                [:assoc :ea |

                                (assoc value includes: ea)

                                                ifFalse:

                                                                [assoc value add: ea.

                                                                assoc key add: ea].

                                assoc]) key]. 157

-Boris

FYI, in case someone else is tempted to use stock OrderedSet as a way of removing duplicates from their sequenceable collections whilst preserving their order,

values := (1 to: 500000) collect: [:i | Time millisecondClockValue].

values asSet size. 259

Time millisecondsToRun: [OrderedSet withAll: values]. 4086

Time millisecondsToRun: [(values inject: OrderedCollection new -> Set new

                into:

                                [:assoc :ea |

                                (assoc value includes: ea)

                                                ifFalse:

                                                                [assoc value add: ea.

                                                                assoc key add: ea].

                                assoc]) key]. 149

Regards,

-Boris

Boris,

That 24 minute measurement was funny, and easily avoided. The attached code makes a 95% performance improvement in that measurement. It could be made even faster by using different Dictionary implementation.

Paul Baumann

| values |

values := (1 to: 50000) collect: [:i | Time microsecondClock].

Time millisecondsToRun: [OrderedSet withAll: values].

"Faster_OrderedSet"

1348

"Original"

  29433

1 - (1348 / 29433) * -100.0

-95.4201

Heh,

values := (1 to: 500000) collect: [:i | Time microsecondClock].

values asSet size. 93303

Time millisecondsToRun: [OrderedSet withAll: values]. 1475110 "24 minutes"

Time millisecondsToRun: [(values inject: OrderedCollection new -> Set new

                into:

                                [:assoc :ea |

                                (assoc value includes: ea)

                                                ifFalse:

                                                                [assoc value add: ea.

                                                                assoc key add: ea].

                                assoc]) key]. 157

-Boris

FYI, in case someone else is tempted to use stock OrderedSet as a way of removing duplicates from their sequenceable collections whilst preserving their order,

values := (1 to: 500000) collect: [:i | Time millisecondClockValue].

values asSet size. 259

Time millisecondsToRun: [OrderedSet withAll: values]. 4086

Time millisecondsToRun: [(values inject: OrderedCollection new -> Set new

                into:

                                [:assoc :ea |

                                (assoc value includes: ea)

                                                ifFalse:

                                                                [assoc value add: ea.

                                                                assoc key add: ea].

                                assoc]) key]. 149

Regards,

-Boris

Paul,

Totally. My comment was mostly to point out that there’s quite a bit of room for improvement in that base system class considering that it seems such an obvious candidate for this specific task based on the name alone.

Regards,

-Boris

Boris,

That 24 minute measurement was funny, and easily avoided. The attached code makes a 95% performance improvement in that measurement. It could be made even faster by using different Dictionary implementation.

Paul Baumann

| values |

values := (1 to: 50000) collect: [:i | Time microsecondClock].

Time millisecondsToRun: [OrderedSet withAll: values].

"Faster_OrderedSet"

1348

"Original"

  29433

1 - (1348 / 29433) * -100.0

-95.4201

Heh,

values := (1 to: 500000) collect: [:i | Time microsecondClock].

values asSet size. 93303

Time millisecondsToRun: [OrderedSet withAll: values]. 1475110 "24 minutes"

Time millisecondsToRun: [(values inject: OrderedCollection new -> Set new

                into:

                                [:assoc :ea |

                                (assoc value includes: ea)

                                                ifFalse:

                                                                [assoc value add: ea.

                                                                assoc key add: ea].

                                assoc]) key]. 157

-Boris

FYI, in case someone else is tempted to use stock OrderedSet as a way of removing duplicates from their sequenceable collections whilst preserving their order,

values := (1 to: 500000) collect: [:i | Time millisecondClockValue].

values asSet size. 259

Time millisecondsToRun: [OrderedSet withAll: values]. 4086

Time millisecondsToRun: [(values inject: OrderedCollection new -> Set new

                into:

                                [:assoc :ea |

                                (assoc value includes: ea)

                                                ifFalse:

                                                                [assoc value add: ea.

                                                                assoc key add: ea].

                                assoc]) key]. 149

Regards,

-Boris

This message may contain confidential information and is intended for specific recipients unless explicitly noted otherwise. If you have reason to believe you are not an intended recipient of this message, please delete it and notify the sender. This message may not represent the opinion of IntercontinentalExchange, Inc. (ICE), its subsidiaries or affiliates, and does not constitute a contract or guarantee. Unencrypted electronic mail is not secure and the recipient of this message is expected to provide safeguards from viruses and pursue alternate means of communication where privacy or a binding message is desired.

Boris,

Agreed. The biggest performance hit in the Collections is the hidden cost of #to:do: enumerations. It doesn't show in the profiler so tuning tends to focus on other costs instead of considering the design itself. Your example with OrderedSet>>includes: shows an extreme of how costly it can be. Methods like Dictionary>>findKeyOrNil: (on a miss) also suffer costs like these. There are collection designs that avoids those costs while also allowing index searches using primitive instead of #to:do:.

Paul Baumann

Paul,

Totally. My comment was mostly to point out that there’s quite a bit of room for improvement in that base system class considering that it seems such an obvious candidate for this specific task based on the name alone.

Regards,

-Boris

Boris,

That 24 minute measurement was funny, and easily avoided. The attached code makes a 95% performance improvement in that measurement. It could be made even faster by using different Dictionary implementation.

Paul Baumann

| values |

values := (1 to: 50000) collect: [:i | Time microsecondClock].

Time millisecondsToRun: [OrderedSet withAll: values].

"Faster_OrderedSet"

1348

"Original"

  29433

1 - (1348 / 29433) * -100.0

-95.4201

Heh,

values := (1 to: 500000) collect: [:i | Time microsecondClock].

values asSet size. 93303

Time millisecondsToRun: [OrderedSet withAll: values]. 1475110 "24 minutes"

Time millisecondsToRun: [(values inject: OrderedCollection new -> Set new

                into:

                                [:assoc :ea |

                                (assoc value includes: ea)

                                                ifFalse:

                                                                [assoc value add: ea.

                                                                assoc key add: ea].

                                assoc]) key]. 157

-Boris

FYI, in case someone else is tempted to use stock OrderedSet as a way of removing duplicates from their sequenceable collections whilst preserving their order,

values := (1 to: 500000) collect: [:i | Time millisecondClockValue].

values asSet size. 259

Time millisecondsToRun: [OrderedSet withAll: values]. 4086

Time millisecondsToRun: [(values inject: OrderedCollection new -> Set new

                into:

                                [:assoc :ea |

                                (assoc value includes: ea)

                                                ifFalse:

                                                                [assoc value add: ea.

                                                                assoc key add: ea].

                                assoc]) key]. 149

Regards,

-Boris

This message may contain confidential information and is intended for specific recipients unless explicitly noted otherwise. If you have reason to believe you are not an intended recipient of this message, please delete it and notify the sender. This message may not represent the opinion of IntercontinentalExchange, Inc. (ICE), its subsidiaries or affiliates, and does not constitute a contract or guarantee. Unencrypted electronic mail is not secure and the recipient of this message is expected to provide safeguards from viruses and pursue alternate means of communication where privacy or a binding message is desired.

Trading memory for speed, one could simply add an (identity) ‘set’ ivar to an OrderedSet to keep track of unique values, while using ‘values’ ivar to keep track of the order, which is essentially what my #inject:into: example was doing to remove duplicates from ordered collection.

-Boris

Boris,

Agreed. The biggest performance hit in the Collections is the hidden cost of #to:do: enumerations. It doesn't show in the profiler so tuning tends to focus on other costs instead of considering the design itself. Your example with OrderedSet>>includes: shows an extreme of how costly it can be. Methods like Dictionary>>findKeyOrNil: (on a miss) also suffer costs like these. There are collection designs that avoids those costs while also allowing index searches using primitive instead of #to:do:.

Paul Baumann

Paul,

Totally. My comment was mostly to point out that there’s quite a bit of room for improvement in that base system class considering that it seems such an obvious candidate for this specific task based on the name alone.

Regards,

-Boris

Boris,

That 24 minute measurement was funny, and easily avoided. The attached code makes a 95% performance improvement in that measurement. It could be made even faster by using different Dictionary implementation.

Paul Baumann

| values |

values := (1 to: 50000) collect: [:i | Time microsecondClock].

Time millisecondsToRun: [OrderedSet withAll: values].

"Faster_OrderedSet"

1348

"Original"

  29433

1 - (1348 / 29433) * -100.0

-95.4201

Heh,

values := (1 to: 500000) collect: [:i | Time microsecondClock].

values asSet size. 93303

Time millisecondsToRun: [OrderedSet withAll: values]. 1475110 "24 minutes"

Time millisecondsToRun: [(values inject: OrderedCollection new -> Set new

                into:

                                [:assoc :ea |

                                (assoc value includes: ea)

                                                ifFalse:

                                                                [assoc value add: ea.

                                                                assoc key add: ea].

                                assoc]) key]. 157

-Boris

FYI, in case someone else is tempted to use stock OrderedSet as a way of removing duplicates from their sequenceable collections whilst preserving their order,

values := (1 to: 500000) collect: [:i | Time millisecondClockValue].

values asSet size. 259

Time millisecondsToRun: [OrderedSet withAll: values]. 4086

Time millisecondsToRun: [(values inject: OrderedCollection new -> Set new

                into:

                                [:assoc :ea |

                                (assoc value includes: ea)

                                                ifFalse:

                                                                [assoc value add: ea.

                                                                assoc key add: ea].

                                assoc]) key]. 149

Regards,

-Boris

This message may contain confidential information and is intended for specific recipients unless explicitly noted otherwise. If you have reason to believe you are not an intended recipient of this message, please delete it and notify the sender. This message may not represent the opinion of IntercontinentalExchange, Inc. (ICE), its subsidiaries or affiliates, and does not constitute a contract or guarantee. Unencrypted electronic mail is not secure and the recipient of this message is expected to provide safeguards from viruses and pursue alternate means of communication where privacy or a binding message is desired.

This message may contain confidential information and is intended for specific recipients unless explicitly noted otherwise. If you have reason to believe you are not an intended recipient of this message, please delete it and notify the sender. This message may not represent the opinion of IntercontinentalExchange, Inc. (ICE), its subsidiaries or affiliates, and does not constitute a contract or guarantee. Unencrypted electronic mail is not secure and the recipient of this message is expected to provide safeguards from viruses and pursue alternate means of communication where privacy or a binding message is desired.

Boris,

It isn't even a tradeoff between allocation and speed if the collections are pre-sized properly. Collection class>>withAll: is missing overrides for collections that can be pre-sized.

Here is a 98% increase on the 95% increase I showed earlier.

| values |

values := (1 to: 500000) collect: [:i | Time microsecondClock].

Time millisecondsToRun: [OrderedSet withAll: values].

818

817

46724

53783

1 - (817 / 46724) * -100.0

-98.2514

Just add this method to the code I provided earlier:

OrderedSet class>>withAll: aCollection

                " Answer a new instance of this class,

                whose elements are the elements of aCollection. "

                | newCollection |

                newCollection := self new: aCollection size.

                newCollection addAll: aCollection.

                ^newCollection

Paul Baumann

Trading memory for speed, one could simply add an (identity) ‘set’ ivar to an OrderedSet to keep track of unique values, while using ‘values’ ivar to keep track of the order, which is essentially what my #inject:into: example was doing to remove duplicates from ordered collection.

-Boris

Boris,

Agreed. The biggest performance hit in the Collections is the hidden cost of #to:do: enumerations. It doesn't show in the profiler so tuning tends to focus on other costs instead of considering the design itself. Your example with OrderedSet>>includes: shows an extreme of how costly it can be. Methods like Dictionary>>findKeyOrNil: (on a miss) also suffer costs like these. There are collection designs that avoids those costs while also allowing index searches using primitive instead of #to:do:.

Paul Baumann

Paul,

Totally. My comment was mostly to point out that there’s quite a bit of room for improvement in that base system class considering that it seems such an obvious candidate for this specific task based on the name alone.

Regards,

-Boris

Boris,

That 24 minute measurement was funny, and easily avoided. The attached code makes a 95% performance improvement in that measurement. It could be made even faster by using different Dictionary implementation.

Paul Baumann

| values |

values := (1 to: 50000) collect: [:i | Time microsecondClock].

Time millisecondsToRun: [OrderedSet withAll: values].

"Faster_OrderedSet"

1348

"Original"

  29433

1 - (1348 / 29433) * -100.0

-95.4201

Heh,

values := (1 to: 500000) collect: [:i | Time microsecondClock].

values asSet size. 93303

Time millisecondsToRun: [OrderedSet withAll: values]. 1475110 "24 minutes"

Time millisecondsToRun: [(values inject: OrderedCollection new -> Set new

                into:

                                [:assoc :ea |

                                (assoc value includes: ea)

                                                ifFalse:

                                                                [assoc value add: ea.

                                                                assoc key add: ea].

                                assoc]) key]. 157

-Boris

FYI, in case someone else is tempted to use stock OrderedSet as a way of removing duplicates from their sequenceable collections whilst preserving their order,

values := (1 to: 500000) collect: [:i | Time millisecondClockValue].

values asSet size. 259

Time millisecondsToRun: [OrderedSet withAll: values]. 4086

Time millisecondsToRun: [(values inject: OrderedCollection new -> Set new

                into:

                                [:assoc :ea |

                                (assoc value includes: ea)

                                                ifFalse:

                                                                [assoc value add: ea.

                                                                assoc key add: ea].

                                assoc]) key]. 149

Regards,

-Boris

This message may contain confidential information and is intended for specific recipients unless explicitly noted otherwise. If you have reason to believe you are not an intended recipient of this message, please delete it and notify the sender. This message may not represent the opinion of IntercontinentalExchange, Inc. (ICE), its subsidiaries or affiliates, and does not constitute a contract or guarantee. Unencrypted electronic mail is not secure and the recipient of this message is expected to provide safeguards from viruses and pursue alternate means of communication where privacy or a binding message is desired.

This message may contain confidential information and is intended for specific recipients unless explicitly noted otherwise. If you have reason to believe you are not an intended recipient of this message, please delete it and notify the sender. This message may not represent the opinion of IntercontinentalExchange, Inc. (ICE), its subsidiaries or affiliates, and does not constitute a contract or guarantee. Unencrypted electronic mail is not secure and the recipient of this message is expected to provide safeguards from viruses and pursue alternate means of communication where privacy or a binding message is desired.

Whoops. Pre-sizing didn't compensate for the allocation cost between designs. There is a tradeoff between memory and speed. The performance difference is huge,  though I'm not going to wait over 24 minutes to get a precise number for the 500000x test to compare with 817 ms.

| values |

values := (1 to: 1000) collect: [:i | Time microsecondClock].

AllocationProfiler profile: [OrderedSet withAll: values].

"Faster_OrderedSet + pre-size"

12256 bytes

"Original OrderedSet"

5240 bytes

Boris,

It isn't even a tradeoff between allocation and speed if the collections are pre-sized properly. Collection class>>withAll: is missing overrides for collections that can be pre-sized.

Here is a 98% increase on the 95% increase I showed earlier.

| values |

values := (1 to: 500000) collect: [:i | Time microsecondClock].

Time millisecondsToRun: [OrderedSet withAll: values].

818

817

46724

53783

1 - (817 / 46724) * -100.0

-98.2514

Just add this method to the code I provided earlier:

OrderedSet class>>withAll: aCollection

                " Answer a new instance of this class,

                whose elements are the elements of aCollection. "

                | newCollection |

                newCollection := self new: aCollection size.

                newCollection addAll: aCollection.

                ^newCollection

Paul Baumann

Trading memory for speed, one could simply add an (identity) ‘set’ ivar to an OrderedSet to keep track of unique values, while using ‘values’ ivar to keep track of the order, which is essentially what my #inject:into: example was doing to remove duplicates from ordered collection.

-Boris

Boris,

Agreed. The biggest performance hit in the Collections is the hidden cost of #to:do: enumerations. It doesn't show in the profiler so tuning tends to focus on other costs instead of considering the design itself. Your example with OrderedSet>>includes: shows an extreme of how costly it can be. Methods like Dictionary>>findKeyOrNil: (on a miss) also suffer costs like these. There are collection designs that avoids those costs while also allowing index searches using primitive instead of #to:do:.

Paul Baumann

Paul,

Totally. My comment was mostly to point out that there’s quite a bit of room for improvement in that base system class considering that it seems such an obvious candidate for this specific task based on the name alone.

Regards,

-Boris

Boris,

That 24 minute measurement was funny, and easily avoided. The attached code makes a 95% performance improvement in that measurement. It could be made even faster by using different Dictionary implementation.

Paul Baumann

| values |

values := (1 to: 50000) collect: [:i | Time microsecondClock].

Time millisecondsToRun: [OrderedSet withAll: values].

"Faster_OrderedSet"

1348

"Original"

  29433

1 - (1348 / 29433) * -100.0

-95.4201

Heh,

values := (1 to: 500000) collect: [:i | Time microsecondClock].

values asSet size. 93303

Time millisecondsToRun: [OrderedSet withAll: values]. 1475110 "24 minutes"

Time millisecondsToRun: [(values inject: OrderedCollection new -> Set new

                into:

                                [:assoc :ea |

                                (assoc value includes: ea)

                                                ifFalse:

                                                                [assoc value add: ea.

                                                                assoc key add: ea].

                                assoc]) key]. 157

-Boris

FYI, in case someone else is tempted to use stock OrderedSet as a way of removing duplicates from their sequenceable collections whilst preserving their order,

values := (1 to: 500000) collect: [:i | Time millisecondClockValue].

values asSet size. 259

Time millisecondsToRun: [OrderedSet withAll: values]. 4086

Time millisecondsToRun: [(values inject: OrderedCollection new -> Set new

                into:

                                [:assoc :ea |

                                (assoc value includes: ea)

                                                ifFalse:

                                                                [assoc value add: ea.

                                                                assoc key add: ea].

                                assoc]) key]. 149

Regards,

-Boris

This message may contain confidential information and is intended for specific recipients unless explicitly noted otherwise. If you have reason to believe you are not an intended recipient of this message, please delete it and notify the sender. This message may not represent the opinion of IntercontinentalExchange, Inc. (ICE), its subsidiaries or affiliates, and does not constitute a contract or guarantee. Unencrypted electronic mail is not secure and the recipient of this message is expected to provide safeguards from viruses and pursue alternate means of communication where privacy or a binding message is desired.

This message may contain confidential information and is intended for specific recipients unless explicitly noted otherwise. If you have reason to believe you are not an intended recipient of this message, please delete it and notify the sender. This message may not represent the opinion of IntercontinentalExchange, Inc. (ICE), its subsidiaries or affiliates, and does not constitute a contract or guarantee. Unencrypted electronic mail is not secure and the recipient of this message is expected to provide safeguards from viruses and pursue alternate means of communication where privacy or a binding message is desired.

This message may contain confidential information and is intended for specific recipients unless explicitly noted otherwise. If you have reason to believe you are not an intended recipient of this message, please delete it and notify the sender. This message may not represent the opinion of IntercontinentalExchange, Inc. (ICE), its subsidiaries or affiliates, and does not constitute a contract or guarantee. Unencrypted electronic mail is not secure and the recipient of this message is expected to provide safeguards from viruses and pursue alternate means of communication where privacy or a binding message is desired.

values := (1 to: 500000) collect: [:i | Time millisecondClockValue].

values asSet size. 184

Time millisecondsToRun: [OrderedSet withAll: values]. 2795

AllocationProfiler profile: [OrderedSet withAll: values]. 2660 bytes

Time millisecondsToRun: [(values inject: OrderedCollection new -> Set new

                into:

                                [:assoc :ea |

                                (assoc value includes: ea)

                                                ifFalse:

                                                                [assoc value add: ea.

                                                                assoc key add: ea].

                                assoc]) key]. 112

AllocationProfiler profile: [(values inject: OrderedCollection new -> Set new

                into:

                                [:assoc :ea |

                                (assoc value includes: ea)

                                                ifFalse:

                                                                [assoc value add: ea.

                                                                assoc key add: ea].

                                assoc]) key]. 5360 bytes

Whoops. Pre-sizing didn't compensate for the allocation cost between designs. There is a tradeoff between memory and speed. The performance difference is huge,  though I'm not going to wait over 24 minutes to get a precise number for the 500000x test to compare with 817 ms.

| values |

values := (1 to: 1000) collect: [:i | Time microsecondClock].

AllocationProfiler profile: [OrderedSet withAll: values].

"Faster_OrderedSet + pre-size"

12256 bytes

"Original OrderedSet"

5240 bytes

Boris,

It isn't even a tradeoff between allocation and speed if the collections are pre-sized properly. Collection class>>withAll: is missing overrides for collections that can be pre-sized.

Here is a 98% increase on the 95% increase I showed earlier.

| values |

values := (1 to: 500000) collect: [:i | Time microsecondClock].

Time millisecondsToRun: [OrderedSet withAll: values].

818

817

46724

53783

1 - (817 / 46724) * -100.0

-98.2514

Just add this method to the code I provided earlier:

OrderedSet class>>withAll: aCollection

                " Answer a new instance of this class,

                whose elements are the elements of aCollection. "

                | newCollection |

                newCollection := self new: aCollection size.

                newCollection addAll: aCollection.

                ^newCollection

Paul Baumann

Trading memory for speed, one could simply add an (identity) ‘set’ ivar to an OrderedSet to keep track of unique values, while using ‘values’ ivar to keep track of the order, which is essentially what my #inject:into: example was doing to remove duplicates from ordered collection.

-Boris

Boris,

Agreed. The biggest performance hit in the Collections is the hidden cost of #to:do: enumerations. It doesn't show in the profiler so tuning tends to focus on other costs instead of considering the design itself. Your example with OrderedSet>>includes: shows an extreme of how costly it can be. Methods like Dictionary>>findKeyOrNil: (on a miss) also suffer costs like these. There are collection designs that avoids those costs while also allowing index searches using primitive instead of #to:do:.

Paul Baumann

Paul,

Totally. My comment was mostly to point out that there’s quite a bit of room for improvement in that base system class considering that it seems such an obvious candidate for this specific task based on the name alone.

Regards,

-Boris

Boris,

That 24 minute measurement was funny, and easily avoided. The attached code makes a 95% performance improvement in that measurement. It could be made even faster by using different Dictionary implementation.

Paul Baumann

| values |

values := (1 to: 50000) collect: [:i | Time microsecondClock].

Time millisecondsToRun: [OrderedSet withAll: values].

"Faster_OrderedSet"

1348

"Original"

  29433

1 - (1348 / 29433) * -100.0

-95.4201

Heh,

values := (1 to: 500000) collect: [:i | Time microsecondClock].

values asSet size. 93303

Time millisecondsToRun: [OrderedSet withAll: values]. 1475110 "24 minutes"

Time millisecondsToRun: [(values inject: OrderedCollection new -> Set new

                into:

                                [:assoc :ea |

                                (assoc value includes: ea)

                                                ifFalse:

                                                                [assoc value add: ea.

                                                                assoc key add: ea].

                                assoc]) key]. 157

-Boris

FYI, in case someone else is tempted to use stock OrderedSet as a way of removing duplicates from their sequenceable collections whilst preserving their order,

values := (1 to: 500000) collect: [:i | Time millisecondClockValue].

values asSet size. 259

Time millisecondsToRun: [OrderedSet withAll: values]. 4086

Time millisecondsToRun: [(values inject: OrderedCollection new -> Set new

                into:

                                [:assoc :ea |

                                (assoc value includes: ea)

                                                ifFalse:

                                                                [assoc value add: ea.

                                                                assoc key add: ea].

                                assoc]) key]. 149

Regards,

-Boris

This message may contain confidential information and is intended for specific recipients unless explicitly noted otherwise. If you have reason to believe you are not an intended recipient of this message, please delete it and notify the sender. This message may not represent the opinion of IntercontinentalExchange, Inc. (ICE), its subsidiaries or affiliates, and does not constitute a contract or guarantee. Unencrypted electronic mail is not secure and the recipient of this message is expected to provide safeguards from viruses and pursue alternate means of communication where privacy or a binding message is desired.

This message may contain confidential information and is intended for specific recipients unless explicitly noted otherwise. If you have reason to believe you are not an intended recipient of this message, please delete it and notify the sender. This message may not represent the opinion of IntercontinentalExchange, Inc. (ICE), its subsidiaries or affiliates, and does not constitute a contract or guarantee. Unencrypted electronic mail is not secure and the recipient of this message is expected to provide safeguards from viruses and pursue alternate means of communication where privacy or a binding message is desired.

This message may contain confidential information and is intended for specific recipients unless explicitly noted otherwise. If you have reason to believe you are not an intended recipient of this message, please delete it and notify the sender. This message may not represent the opinion of IntercontinentalExchange, Inc. (ICE), its subsidiaries or affiliates, and does not constitute a contract or guarantee. Unencrypted electronic mail is not secure and the recipient of this message is expected to provide safeguards from viruses and pursue alternate means of communication where privacy or a binding message is desired.

This message may contain confidential information and is intended for specific recipients unless explicitly noted otherwise. If you have reason to believe you are not an intended recipient of this message, please delete it and notify the sender. This message may not represent the opinion of IntercontinentalExchange, Inc. (ICE), its subsidiaries or affiliates, and does not constitute a contract or guarantee. Unencrypted electronic mail is not secure and the recipient of this message is expected to provide safeguards from viruses and pursue alternate means of communication where privacy or a binding message is desired.

Alan,

The idea is to preserve the order, plus not all objects would answer to #<=?

I hope I didn’t completely misread your intent.

-Boris

Haven't looked in detail, but I suspect that one could just use a binaryIndexOf:ifAbsent: search rather than a linear search and get a very large improvement without needing to introduce an additional collection or reliance on hashing. And for the particular case of addAll:, if that method knew enough to just sort the elements and then go once through them rejecting all those that were equal to the previous element, it would be quite a lot faster, probably faster than something relying on hashing.

Boris,

Your allocation results are different because your computer is faster. Your computer answered 32% fewer equal values than mine did from #millisecondClockValue. Your computer was 50% faster in the "OrderedSet withAll:" test and  65% faster on the OC->Set association. Your computer allocated 33% fewer bytes for that test because you had more equal values. Not a good comparison of implementation differences.

| values |

values := (1 to: 500000) collect: [:i | Time millisecondClockValue].

values asSet size.

268

271

BTW, the OrderedSet class>>withAll: method I showed is not good for general use because so few of the additions were equal. The execution time was great, but the allocation was wasteful. There are techniques to pre-size with a reasonable estimate that will perform well, but that was not it. You'll get better performance in your examples if you pre-size the collections yourself according to what you estimate for your application.

"AllocationProfiler profile: [(OrderedSet new: 300) addAll: values]."  "1240 bytes"

...(values inject: (OrderedCollection new: 300) -> (Set new: 300)...

Your use of the Set would be more allocation efficient in your example code than the Dictionary I used in the refactored OrderedSet, but it is not faster when compared on a single computer. The OC->Set code (with pre-size shown above) ran in 221 ms on my computer, but the refactored OrderedSet  with the internal Dictionary did the work in 176 ms. Allocation bytes went from 4968 bytes to 9592 bytes; the dictionary is of course allocating Associations. Another Dictionary implementation would be faster while also being more efficient.

The Dictionary however would be faster when testing removals.  OrderedSet could be made to use either.  The allocations would be comparable because they rely on the same underlying collections.

Paul Baumann

values := (1 to: 500000) collect: [:i | Time millisecondClockValue].

values asSet size. 184

Time millisecondsToRun: [OrderedSet withAll: values]. 2795

AllocationProfiler profile: [OrderedSet withAll: values]. 2660 bytes

Time millisecondsToRun: [(values inject: OrderedCollection new -> Set new

                into:

                                [:assoc :ea |

                                (assoc value includes: ea)

                                                ifFalse:

                                                                [assoc value add: ea.

                                                                assoc key add: ea].

                                assoc]) key]. 112

AllocationProfiler profile: [(values inject: OrderedCollection new -> Set new

                into:

                                [:assoc :ea |

                                (assoc value includes: ea)

                                                ifFalse:

                                                                [assoc value add: ea.

                                                                assoc key add: ea].

                                assoc]) key]. 5360 bytes

Whoops. Pre-sizing didn't compensate for the allocation cost between designs. There is a tradeoff between memory and speed. The performance difference is huge,  though I'm not going to wait over 24 minutes to get a precise number for the 500000x test to compare with 817 ms.

| values |

values := (1 to: 1000) collect: [:i | Time microsecondClock].

AllocationProfiler profile: [OrderedSet withAll: values].

"Faster_OrderedSet + pre-size"

12256 bytes

"Original OrderedSet"

5240 bytes

Boris,

It isn't even a tradeoff between allocation and speed if the collections are pre-sized properly. Collection class>>withAll: is missing overrides for collections that can be pre-sized.

Here is a 98% increase on the 95% increase I showed earlier.

| values |

values := (1 to: 500000) collect: [:i | Time microsecondClock].

Time millisecondsToRun: [OrderedSet withAll: values].

818

817

46724

53783

1 - (817 / 46724) * -100.0

-98.2514

Just add this method to the code I provided earlier:

OrderedSet class>>withAll: aCollection

                " Answer a new instance of this class,

                whose elements are the elements of aCollection. "

                | newCollection |

                newCollection := self new: aCollection size.

                newCollection addAll: aCollection.

                ^newCollection

Paul Baumann

Trading memory for speed, one could simply add an (identity) ‘set’ ivar to an OrderedSet to keep track of unique values, while using ‘values’ ivar to keep track of the order, which is essentially what my #inject:into: example was doing to remove duplicates from ordered collection.

-Boris

Boris,

Agreed. The biggest performance hit in the Collections is the hidden cost of #to:do: enumerations. It doesn't show in the profiler so tuning tends to focus on other costs instead of considering the design itself. Your example with OrderedSet>>includes: shows an extreme of how costly it can be. Methods like Dictionary>>findKeyOrNil: (on a miss) also suffer costs like these. There are collection designs that avoids those costs while also allowing index searches using primitive instead of #to:do:.

Paul Baumann

Paul,

Totally. My comment was mostly to point out that there’s quite a bit of room for improvement in that base system class considering that it seems such an obvious candidate for this specific task based on the name alone.

Regards,

-Boris

Boris,

That 24 minute measurement was funny, and easily avoided. The attached code makes a 95% performance improvement in that measurement. It could be made even faster by using different Dictionary implementation.

Paul Baumann

| values |

values := (1 to: 50000) collect: [:i | Time microsecondClock].

Time millisecondsToRun: [OrderedSet withAll: values].

"Faster_OrderedSet"

1348

"Original"

  29433

1 - (1348 / 29433) * -100.0

-95.4201

Heh,

values := (1 to: 500000) collect: [:i | Time microsecondClock].

values asSet size. 93303

Time millisecondsToRun: [OrderedSet withAll: values]. 1475110 "24 minutes"

Time millisecondsToRun: [(values inject: OrderedCollection new -> Set new

                into:

                                [:assoc :ea |

                                (assoc value includes: ea)

                                                ifFalse:

                                                                [assoc value add: ea.

                                                                assoc key add: ea].

                                assoc]) key]. 157

-Boris

FYI, in case someone else is tempted to use stock OrderedSet as a way of removing duplicates from their sequenceable collections whilst preserving their order,

values := (1 to: 500000) collect: [:i | Time millisecondClockValue].

values asSet size. 259

Time millisecondsToRun: [OrderedSet withAll: values]. 4086

Time millisecondsToRun: [(values inject: OrderedCollection new -> Set new

                into:

                                [:assoc :ea |

                                (assoc value includes: ea)

                                                ifFalse:

                                                                [assoc value add: ea.

                                                                assoc key add: ea].

                                assoc]) key]. 149

Regards,

-Boris

This message may contain confidential information and is intended for specific recipients unless explicitly noted otherwise. If you have reason to believe you are not an intended recipient of this message, please delete it and notify the sender. This message may not represent the opinion of IntercontinentalExchange, Inc. (ICE), its subsidiaries or affiliates, and does not constitute a contract or guarantee. Unencrypted electronic mail is not secure and the recipient of this message is expected to provide safeguards from viruses and pursue alternate means of communication where privacy or a binding message is desired.

This message may contain confidential information and is intended for specific recipients unless explicitly noted otherwise. If you have reason to believe you are not an intended recipient of this message, please delete it and notify the sender. This message may not represent the opinion of IntercontinentalExchange, Inc. (ICE), its subsidiaries or affiliates, and does not constitute a contract or guarantee. Unencrypted electronic mail is not secure and the recipient of this message is expected to provide safeguards from viruses and pursue alternate means of communication where privacy or a binding message is desired.

This message may contain confidential information and is intended for specific recipients unless explicitly noted otherwise. If you have reason to believe you are not an intended recipient of this message, please delete it and notify the sender. This message may not represent the opinion of IntercontinentalExchange, Inc. (ICE), its subsidiaries or affiliates, and does not constitute a contract or guarantee. Unencrypted electronic mail is not secure and the recipient of this message is expected to provide safeguards from viruses and pursue alternate means of communication where privacy or a binding message is desired.

This message may contain confidential information and is intended for specific recipients unless explicitly noted otherwise. If you have reason to believe you are not an intended recipient of this message, please delete it and notify the sender. This message may not represent the opinion of IntercontinentalExchange, Inc. (ICE), its subsidiaries or affiliates, and does not constitute a contract or guarantee. Unencrypted electronic mail is not secure and the recipient of this message is expected to provide safeguards from viruses and pursue alternate means of communication where privacy or a binding message is desired.

Paul,

Oh, I wasn’t intending this as a comparison with your results, rather as a basic report of comparing base implementation with an #inject:into: alternative that I ended up using for this specific purpose of removing duplicates and preserving order. Unfortunately, I’m a bit swamped these days to really follow the in-depth discussion on the improvements that could be made to OrderedSet internally to achieve better results, but it sounds like there are some sound ideas for Cincom to ponder if/when they choose to.

Thanks!

-Boris

Boris,

Your allocation results are different because your computer is faster. Your computer answered 32% fewer equal values than mine did from #millisecondClockValue. Your computer was 50% faster in the "OrderedSet withAll:" test and  65% faster on the OC->Set association. Your computer allocated 33% fewer bytes for that test because you had more equal values. Not a good comparison of implementation differences.

| values |

values := (1 to: 500000) collect: [:i | Time millisecondClockValue].

values asSet size.

268

271

BTW, the OrderedSet class>>withAll: method I showed is not good for general use because so few of the additions were equal. The execution time was great, but the allocation was wasteful. There are techniques to pre-size with a reasonable estimate that will perform well, but that was not it. You'll get better performance in your examples if you pre-size the collections yourself according to what you estimate for your application.

"AllocationProfiler profile: [(OrderedSet new: 300) addAll: values]."  "1240 bytes"

...(values inject: (OrderedCollection new: 300) -> (Set new: 300)...

Your use of the Set would be more allocation efficient in your example code than the Dictionary I used in the refactored OrderedSet, but it is not faster when compared on a single computer. The OC->Set code (with pre-size shown above) ran in 221 ms on my computer, but the refactored OrderedSet  with the internal Dictionary did the work in 176 ms. Allocation bytes went from 4968 bytes to 9592 bytes; the dictionary is of course allocating Associations. Another Dictionary implementation would be faster while also being more efficient.

The Dictionary however would be faster when testing removals.  OrderedSet could be made to use either.  The allocations would be comparable because they rely on the same underlying collections.

Paul Baumann

values := (1 to: 500000) collect: [:i | Time millisecondClockValue].

values asSet size. 184

Time millisecondsToRun: [OrderedSet withAll: values]. 2795

AllocationProfiler profile: [OrderedSet withAll: values]. 2660 bytes

Time millisecondsToRun: [(values inject: OrderedCollection new -> Set new

                into:

                                [:assoc :ea |

                                (assoc value includes: ea)

                                                ifFalse:

                                                                [assoc value add: ea.

                                                                assoc key add: ea].

                                assoc]) key]. 112

AllocationProfiler profile: [(values inject: OrderedCollection new -> Set new

                into:

                                [:assoc :ea |

                                (assoc value includes: ea)

                                                ifFalse:

                                                                [assoc value add: ea.

                                                                assoc key add: ea].

                                assoc]) key]. 5360 bytes

Whoops. Pre-sizing didn't compensate for the allocation cost between designs. There is a tradeoff between memory and speed. The performance difference is huge,  though I'm not going to wait over 24 minutes to get a precise number for the 500000x test to compare with 817 ms.

| values |

values := (1 to: 1000) collect: [:i | Time microsecondClock].

AllocationProfiler profile: [OrderedSet withAll: values].

"Faster_OrderedSet + pre-size"

12256 bytes

"Original OrderedSet"

5240 bytes

Boris,

It isn't even a tradeoff between allocation and speed if the collections are pre-sized properly. Collection class>>withAll: is missing overrides for collections that can be pre-sized.

Here is a 98% increase on the 95% increase I showed earlier.

| values |

values := (1 to: 500000) collect: [:i | Time microsecondClock].

Time millisecondsToRun: [OrderedSet withAll: values].

818