Re: [Pharo-dev] Implementing lazy loading for expandable collections (part 2)
I'm more worried about this part. [ 10000 timesRepeat: [ | c | c := OrderedCollection new. c add: 1. 2 to: 10000 do: [ :i | c add: i beforeIndex: (c atRandom) ] ] ] timeToRun "5 min. 30 s." Stephan
Hmm. Looking at the results in a relatively up to date Squeak 4.5: [ 10000 timesRepeat: [ | c | c := OrderedCollection new: 100000. 1 to: 10000 do: [ :i | c add: i ] ] ] timeToRun 3624 [ 10000 timesRepeat: [ | c | c := OrderedCollection new: 10000. 1 to: 10000 do: [ :i | c add: i ] ] ] timeToRun 2540 [ 10000 timesRepeat: [ | c | c := OrderedCollection new: 0. 1 to: 10000 do: [ :i | c add: i ] ] ] timeToRun 2879 [ 10000 timesRepeat: [ | c | c := OrderedCollection new: 1000. 1 to: 10000 do: [ :i | c add: i ] ] ] timeToRun 2784 Apparently Squeak takes more time to allocate the large array than Pharo? That would explain why the first run is so much slower than the other 3 - the exact opposite of Max's results (for Pharo 1.3 - but inline with Pharo4 - although not as extreme as Pharo4). Then, what about an array that only adds at the beginning (instead of end)? I would expect worse performance - especially if I removed the space at the beginning. WIthout any of those changes, though: [ 10000 timesRepeat: [ | c | c := OrderedCollection new: 100000. 1 to: 10000 do: [ :i | c addFirst: i ] ] ] timeToRun 2782 [ 10000 timesRepeat: [ | c | c := OrderedCollection new: 10000. 1 to: 10000 do: [ :i | c addFirst: i ] ] ] timeToRun 1845 [ 10000 timesRepeat: [ | c | c := OrderedCollection new: 0. 1 to: 10000 do: [ :i | c addFirst: i ] ] ] timeToRun 2052 [ 10000 timesRepeat: [ | c | c := OrderedCollection new: 1000. 1 to: 10000 do: [ :i | c addFirst: i ] ] ] timeToRun 1962 Weird that it turned out faster. Maybe it has to do with the first time it runs out of room, it move data (and doesn't allocate a new array?). Stephan's code (in the same image): [ 10000 timesRepeat: [ | c | c := OrderedCollection new: 100000. c add: 1. 2 to: 10000 do: [ :i | c add: i beforeIndex: (i atRandom) ] ] ] timeToRun 200434 This last is much slower - every time it adds an value, it forces a copy of the data. It will not be as fast as the others. -cbc On Wed, Jan 14, 2015 at 6:05 AM, Stephan Eggermont <stephan@stack.nl> wrote:
I'm more worried about this part.
[ 10000 timesRepeat: [ | c | c := OrderedCollection new. c add: 1. 2 to: 10000 do: [ :i | c add: i beforeIndex: (c atRandom) ] ] ] timeToRun "5 min. 30 s."
Stephan
Hi Stephan, On Wed, Jan 14, 2015 at 6:05 AM, Stephan Eggermont <stephan@stack.nl> wrote:
I'm more worried about this part.
[ 10000 timesRepeat: [ | c | c := OrderedCollection new. c add: 1. 2 to: 10000 do: [ :i | c add: i beforeIndex: (c atRandom) ] ] ] timeToRun "5 min. 30 s."
Stephan
About 90% of the entire time is in the string copying primitive. Not much to be done there. Sista could speed this up by eliminating the validation overhead of the primitive. But with our current VM technology there's not a lot one can do given that OrderedCollection is organized as a flat stack. This is probably a case where an ordered tree would be faster, albeit have a lot more space overhead. /Users/eliot/Cog/oscogvm/build.macos32x86/squeak.cog.spur/Fast.app/Contents/MacOS/Squeak 1/14/2015 eden size: 4,101,312 stack pages: 160 code size: 1,048,576 500 timesRepeat: [| c | c := OrderedCollection new. c add: 1. 2 to: 10000 do: [:i | c add: i beforeIndex: c atRandom]] gc prior. clear prior. 25.14 seconds; sampling frequency 1459 hz 36250 samples in the VM (36670 samples in the entire program) 98.85% of total 2749 samples in generated vm code 7.58% of entire vm ( 7.50% of total) 33501 samples in vanilla vm code 92.42% of entire vm (91.36% of total) % of generated vm code (% of total) (samples) (cumulative) 10.51% ( 0.79%) Semaphore>>critical: (289) (10.51%) 7.97% ( 0.60%) Collection>>atRandom (219) (18.48%) 6.37% ( 0.48%) BoxedFloat64>>/ (175) (24.85%) 5.82% ( 0.44%) ceSmallMethodContext (160) (30.67%) 5.60% ( 0.42%) OrderedCollection>>insert:before: (154) (36.27%) 5.17% ( 0.39%) BoxedFloat64>>* (142) (41.43%) 3.78% ( 0.28%) BlockClosure>>ensure: (104) (45.22%) 3.60% ( 0.27%) Random>>nextValue (99) (48.82%) 3.35% ( 0.25%) BlockClosure>>value (92) (52.16%) 3.20% ( 0.24%) Array>>replaceFrom:to:with:startingAt: (88) (55.37%) 3.20% ( 0.24%) BoxedFloat64>>truncated (88) (58.57%) 3.20% ( 0.24%) OrderedCollection>>add:beforeIndex: (88) (61.77%) 2.87% ( 0.22%) BlockClosure>>valueNoContextSwitch (79) (64.64%) 2.87% ( 0.22%) Random>>next (79) (67.52%) 2.58% ( 0.19%) BoxedFloat64>>- (71) (70.10%) 2.51% ( 0.19%) OrderedCollection>>size (69) (72.61%) 2.22% ( 0.17%) Semaphore>>wait (61) (74.83%) 2.11% ( 0.16%) SmallInteger>>- (58) (76.94%) 2.11% ( 0.16%) UndefinedObject>>DoIt (58) (79.05%) 2.07% ( 0.16%) OrderedCollection>>at: (57) (81.12%) 2.07% ( 0.16%) Random>>nextInt: (57) (83.19%) 1.93% ( 0.14%) SequenceableCollection>>atRandom: (53) (85.12%) 1.93% ( 0.14%) SmallInteger>>+ (53) (87.05%) 1.75% ( 0.13%) Magnitude>>between:and: (48) (88.80%) 1.71% ( 0.13%) Semaphore>>signal (47) (90.51%) 1.49% ( 0.11%) Number>>quo: (41) (92.00%) 1.49% ( 0.11%) Object>>at:put: (41) (93.49%) 1.31% ( 0.10%) Collection class>>mutexForPicking (36) (94.80%) 1.20% ( 0.09%) Object>>at: (33) (96.00%) 1.05% ( 0.08%) Collection class>>randomForPicking (29) (97.05%) 0.87% ( 0.07%) Number>>strictlyPositive (24) (97.93%) 0.76% ( 0.06%) BoxedFloat64>>> (21) (98.69%) 0.62% ( 0.05%) SmallInteger>>> (17) (99.31%) 0.51% ( 0.04%) SmallInteger>><= (14) (99.82%) 0.18% ( 0.01%) ...others... (5) (100.0%) % of vanilla vm code (% of total) (samples) (cumulative) 97.38% (88.96%) primitiveStringReplace (32623) (97.38%) 0.90% ( 0.82%) primitiveTruncated (302) (98.28%) 0.61% ( 0.56%) scavengeReferentsOf (204) (98.89%) 0.36% ( 0.33%) copyAndForward (122) (99.25%) 0.20% ( 0.18%) primitiveWait (66) (99.45%) 0.18% ( 0.16%) scavengeLoop (59) (99.63%) 0.12% ( 0.11%) synchronousSignal (40) (99.75%) 0.07% ( 0.06%) primitiveSignal (22) (99.81%) 0.04% ( 0.04%) instantiateC...ndexableSize(15) (99.86%) 0.04% ( 0.04%) processWeakSurvivor (14) (99.90%) 0.03% ( 0.03%) mapStackPages (10) (99.93%) 0.01% ( 0.01%) scavengingGCTenuringIf(5) (99.94%) 0.06% ( 0.05%) ...others... (19) (100.0%) -- best, Eliot
participants (3)
-
Chris Cunningham -
Eliot Miranda -
Stephan Eggermont