<div dir="ltr">Hi All,<div><br></div><div> sorted: for Array is OK, but for Array-like subclasses of ArrayedCollection it's suboptimal. For example:</div><div><br></div><div><div><br></div><div><div>32-bit Mac OS X 2.2GHz Core i7 MBP</div><div><div><br></div><div>[| samples r samplesArray |</div><div>samples := Bitmap new: 256 * 1024.</div><div>r := Random new.</div><div>1 to: samples size do:</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>[:i|</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>samples at: i put: (r next * (1 << 32)) asInteger - 1].</div><div>samplesArray := samples asArray.</div><div>(1 to: 3) collect: [:i| {[samples sorted] timeToRun. [samplesArray sorted] timeToRun}] #(#(266 243) #(293 239) #(413 247))]</div></div><div><br></div><div>64-bit Mac OS X 2.2GHz Core i7 MBP<br></div><div>| samples r samplesArray |</div><div>samples := Bitmap new: 256 * 1024.</div><div>r := Random new.</div><div>1 to: samples size do:</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>[:i|</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>samples at: i put: (r next * (1 << 32)) asInteger - 1].</div><div>samplesArray := samples asArray.</div><div>(1 to: 3) collect: [:i| {[samples sorted] timeToRun. [samplesArray sorted] timeToRun}] #(#(143 134) #(300 133) #(141 137))</div></div></div><div><br></div><div>My point is about the difference in sorting speed for Array vs Bitmap, but before that note that 64-bit is faster to sort because there are fewer 32-bit to LargePositiveInteger conversions, but the difference between the Bitmap vs Array sort is larger on 64-bit because the 64-bit generation scavenger has a performance problem (which is why I'm looking at the above, fixing the VM profiler to work for 64-bit address spaces).</div><div><br></div><div><br></div><div>What's going on here is that Array's sorted: is</div><div><br></div><div><div>Array>>#sorted: aSortBlockOrNil</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>^self copy sort: aSortBlockOrNil</div></div><div><br></div><div>but for other subclasses of ArrayedCollection it is</div><div><br></div><div><div>Collection>>#sorted: aSortBlockOrNil</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>^self asArray sort: aSortBlockOrNil</div><div><br></div><div>so there is a slow copy of the Bitmap or ByteArray to an Array with equivalent elements, but a shallow copy (which is fast) in Array>>#sorted: to sort an Array.</div><div><br></div><div>When you look at the timings above you can see that when a GC occurs due to the slow copy it takes much longer to sort the Bitmap, and that it always takes longer to sort the Bitmap than the Array.</div><div><br></div><div>For many subclasses of ArrayedCollection, essentially everything other than the RunArrays and CompiledMethod, which are specialised, there is no need to convert to an Array, and a direct access to a shallow copy would work just as well.</div><div><br></div><div>So shouldn't we instead implement this as</div><div><br></div><div><div>ArrayedCollection>>#sorted: aSortBlockOrNil</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>^self copy sort: aSortBlockOrNil</div></div><div><br></div><div>and in subclasses that are exceptions override as e.g.</div><div><div>RunArray>>#sorted: aSortBlockOrNil</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>^self asArray sort: aSortBlockOrNil</div></div><div><br></div><div>SparseLargeArray>>#sorted: aSortBlockOrNil</div><div> something much cleverer....</div><div><br></div><div><br></div><div>?</div><div class="gmail_signature"><div dir="ltr"><div><span style="font-size:small;border-collapse:separate"><div>_,,,^..^,,,_<br></div><div>best, Eliot</div></span></div></div></div>
</div></div>