Re: [Pharo-dev] Implementing lazy loading for expandable collections
I just did a quick implementation with your idea in mind. The implementation is very easy and looks like this: OrderedCollection class>>new ^ self new: 0 OrderedCollection>>growSize ^ array size max: 10 I changed #growSize so that the first grow will end up having the same size the #new would create previously. Otherwise the number of grows would be very high for small collections. This change saves a factor 4 of space on new OrderedCollections (Array new sizeInMemory â> 4, (Array new: 10) sizeInMemory â> 44). Using nil instead of an empty array would achieve memory savings of factor 14, but with the extra message sends and initialization logic (and the extra instance variable) I think that factor 10 is good enough. What do you think? Cheers, Max On 30.09.2014, at 09:43, Max Leske <maxleske@gmail.com> wrote:
Hi Alex,
I want to improve my lazy loading implementation and I was hoping to get your feedback. So I hope you donât mind if I forward this message from the original thread to you.
Cheers, Max
Begin forwarded message:
From: Max Leske <maxleske@gmail.com> Subject: Re: [Pharo-dev] Implementing lazy loading for expandable collections Date: 22. September 2014 14:06:55 MESZ To: Pharo Development List <pharo-dev@lists.pharo.org>
On 20.09.2014, at 14:27, Alexandre Bergel <alexandre.bergel@me.com> wrote:
Hi Max!
Thanks! This is something I wanted to push to Pharo for a long time. A simpler approach, would be to initialize the internal array to #() when initialized per default. This will provide pretty much the same benefits, and will not break the existing tools.
Does this make sense to you?
I think that would work well for standard use cases with #new. However, it wouldnât work for explicit size requests. The question of course is, how often will a collection be created with an explicit size and *still* stay empty. I guess you would know that better than me.
I opted for the other solution because I didnât want to change the meaning of #new (which is to request a default size of 10) and because I simply assumed that even collections with explicitly requested size could stay empty.
In terms of simplicity I like youâre idea far better of course :) It also makes a lot of changes moot that are necessary to initialize the array when required, because the array will simply be grown.
What do your measurements say?
Cheers, Max
Alexandre
Le 19-09-2014 à 2:35, Max Leske <maxleske@gmail.com> a écrit :
Iâve written an implementation of lazily initialized expandable collections (for OrderedCollection and subclasses only for now), inspired by Alexandreâs talk at ESUG (http://www.youtube.com/watch?v=x0YJ2dsZdKg&list=UUO-vBhaKVZf0al-ISMMPvRw). The implementation is pretty much straight forward but there are a couple of culprits I want to point out in case anybody else wants to do this:
- my implementation requires an extra instance variable in OrderedCollection to store the requested size. This extra instance variable will break Monticello (and possibly other tools) because Monticello uses OrderedCollections to load code and the particular way it uses them makes it impossible to change the number of instance variables on OrderedCollection. Also, all .mcz files written after the change will not be loadable by images without the new instance variable (same reason). - the above means that you have to modify the code in the image manually and save a new âbase image" - read only messages should obviously not initialize the array. The âfirstIndexâ and âlastIndexâ variables are quite handy for that. I initialize those variables to 1 and 0 respectively which makes most things work already (e.g. #size, #isEmpty etc.). - when trying to implement the same for HashedCollection I couldnât. The image didnât just stop working, there was no output at all on the console, not even when using a debug VM. The problem seems to be MethodDictionary, at least thatâs the only subclass of Dictionary for which adding an instance variable doesnât work.
Iâll share some memory monitoring as soon as I have something significant (only just rolled it out).
Big thanks to Alex for his talk and the cool work he and his students did!
Cheers, Max
A similar implementation is possible for HashedCollection: HashedCollection class>>new ^ self basicNew initialize: 1 â<âââââââââ initialize to 1 instead of 5" HashedCollection>>grow "Grow the elements array and reinsert the old elements" | oldElements | oldElements := array. array := Array new: (HashTableSizes atLeast: self growSize). â<âââââââââ use #growSize here" tally := 0. oldElements do: [ :each | each == nil ifFalse: [ self noCheckAdd: each ] ] HashedCollection>>growSize "Answer what my next higher table size should be" ^HashTableSizes atLeast: self capacity * 3 // 2 + 5 â<âââââââââ increased from +2 to +5â Iâm not really sure about this change though. HashedCollections are a bit more complicated and maybe itâs ok to initialize them with 5? Also: there are a few subclasses (e.g. MethodDictionary) that need extra attention (they override various methods like #grow, #growTo:, #newâ¦). BTW: initializing HashedCollections with 0 doesnât work because not all methods correctly check the array size and just assume that at least one element can be added. On 30.09.2014, at 10:13, Max Leske <maxleske@gmail.com> wrote:
I just did a quick implementation with your idea in mind. The implementation is very easy and looks like this:
OrderedCollection class>>new ^ self new: 0
OrderedCollection>>growSize ^ array size max: 10
I changed #growSize so that the first grow will end up having the same size the #new would create previously. Otherwise the number of grows would be very high for small collections. This change saves a factor 4 of space on new OrderedCollections (Array new sizeInMemory â> 4, (Array new: 10) sizeInMemory â> 44).
Using nil instead of an empty array would achieve memory savings of factor 14, but with the extra message sends and initialization logic (and the extra instance variable) I think that factor 10 is good enough. What do you think?
Cheers, Max
On 30.09.2014, at 09:43, Max Leske <maxleske@gmail.com> wrote:
Hi Alex,
I want to improve my lazy loading implementation and I was hoping to get your feedback. So I hope you donât mind if I forward this message from the original thread to you.
Cheers, Max
Begin forwarded message:
From: Max Leske <maxleske@gmail.com> Subject: Re: [Pharo-dev] Implementing lazy loading for expandable collections Date: 22. September 2014 14:06:55 MESZ To: Pharo Development List <pharo-dev@lists.pharo.org>
On 20.09.2014, at 14:27, Alexandre Bergel <alexandre.bergel@me.com> wrote:
Hi Max!
Thanks! This is something I wanted to push to Pharo for a long time. A simpler approach, would be to initialize the internal array to #() when initialized per default. This will provide pretty much the same benefits, and will not break the existing tools.
Does this make sense to you?
I think that would work well for standard use cases with #new. However, it wouldnât work for explicit size requests. The question of course is, how often will a collection be created with an explicit size and *still* stay empty. I guess you would know that better than me.
I opted for the other solution because I didnât want to change the meaning of #new (which is to request a default size of 10) and because I simply assumed that even collections with explicitly requested size could stay empty.
In terms of simplicity I like youâre idea far better of course :) It also makes a lot of changes moot that are necessary to initialize the array when required, because the array will simply be grown.
What do your measurements say?
Cheers, Max
Alexandre
Le 19-09-2014 à 2:35, Max Leske <maxleske@gmail.com> a écrit :
Iâve written an implementation of lazily initialized expandable collections (for OrderedCollection and subclasses only for now), inspired by Alexandreâs talk at ESUG (http://www.youtube.com/watch?v=x0YJ2dsZdKg&list=UUO-vBhaKVZf0al-ISMMPvRw). The implementation is pretty much straight forward but there are a couple of culprits I want to point out in case anybody else wants to do this:
- my implementation requires an extra instance variable in OrderedCollection to store the requested size. This extra instance variable will break Monticello (and possibly other tools) because Monticello uses OrderedCollections to load code and the particular way it uses them makes it impossible to change the number of instance variables on OrderedCollection. Also, all .mcz files written after the change will not be loadable by images without the new instance variable (same reason). - the above means that you have to modify the code in the image manually and save a new âbase image" - read only messages should obviously not initialize the array. The âfirstIndexâ and âlastIndexâ variables are quite handy for that. I initialize those variables to 1 and 0 respectively which makes most things work already (e.g. #size, #isEmpty etc.). - when trying to implement the same for HashedCollection I couldnât. The image didnât just stop working, there was no output at all on the console, not even when using a debug VM. The problem seems to be MethodDictionary, at least thatâs the only subclass of Dictionary for which adding an instance variable doesnât work.
Iâll share some memory monitoring as soon as I have something significant (only just rolled it out).
Big thanks to Alex for his talk and the cool work he and his students did!
Cheers, Max
participants (1)
-
Max Leske