16.2: A Simple Example

Last updated
Save as PDF

Page ID: 43758

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Consider the method Collection>>select:thenCollect:. For a given collection, this method selects elements using a predicate. It then applies a block function on each selected element. At the first sight, this behavior implies two runs over the collections: the one provided by the user of select:thenCollect: then an intermediate one that contains the selected elements. However, this intermediate collection is not indispensable, since the selection and the function application can be performed with only one run.

The method timeToRun: Profiling one program execution is usually not enough to fully identify and understand what has to be optimized. Comparing at least two different profiled executions is definitely more fruitful. The message timeToRun may be sent to a bloc to obtain the time in milliseconds that it took to evaluate the block. To have a meaningful and representative measurement, we need to “amplify” the profiling with a loop.

Here are some results:

| coll |
coll := #(1 2 3 4 5 6 7 8) asOrderedCollection.
[ 100000 timesRepeat: [ (coll select: [:each | each > 5]) collect: [:i |i * i]]] timeToRun
"Calling select:, then collect:    →    ∼ 570 - 600 ms"

| coll |
coll := #(1 2 3 4 5 6 7 8) asOrderedCollection.
[ 100000 timesRepeat: [ coll select: [:each | each > 5] thenCollect:[:i |i * i]]] timeToRun
"Calling select:thenCollect:       →    ∼ 397 - 415 ms"

Although the difference between these two executions is only about few hundred of milliseconds, opting for one method instead of the other could significantly slow your application!

Let’s scrutinize the definition of select:thenCollect:. A naive and non-optimized implementation is found in Collection. (Remember that Collection is the root class of the Pharo collection library). A more efficient implementation is defined in OrderedCollection, which takes into account the structure of an ordered collection to efficiently perform this operation.

Collection>>select: selectBlock thenCollect: collectBlock
    "Utility method to improve readability."
    
    ^ (self select: selectBlock) collect: collectBlock

OrderedCollection>>select: selectBlock thenCollect: collectBlock
    " Utility method to improve readability.
    Do not create the intermediate collection. "
    
    | newCollection |
    newCollection := self copyEmpty.
    firstIndex to: lastIndex do: [:index |
        | element |
        element := array at: index.
        (selectBlock value: element)
            ifTrue: [ newCollection addLast: (collectBlock value: element) ]].
    ^ newCollection

As you have probably guessed already, other collections such as Set and Dictionary do not benefit from an optimized version. We leave as an exercise an efficient implementation for other abstract data types. As part of the community effort, do not forget to submit your contribution to Pharo if you come up with an optimized and better version of select:thenCollect: or other methods. The Pharo team really value such effort.

The method bench. When sent to a block, the bench message estimates how many times this block is evaluated per second. For example, the expression [ 1000 factorial ] bench says that 1000 factorial may be executed approximately 350 times per second.