September 2010 - Pharo-dev - lists.pharo.org

Re: [Pharo-project] Compiler throws error in Gemstone, not in Pharo

by StÃ©phane Ducasse

ah yes an empty statement. Ugly we cleaned a lot of .. in the past I hope that Opal will fix that On Sep 13, 2010, at 4:07 PM, Johan Brichau wrote: > What's the dot doing after 'aSelector' ? :-) > > it's an empty statement -> gs parser does not allow that > > btw, I think this is a rule in code critic, so if you launch that, you will get all these problems before trying to load them into GS > > On 13 Sep 2010, at 13:55, StÃ©phane Ducasse wrote: > >> Yes but what is wrong on gemstone. >> >> Stef >> >> >>> Dear list, >>> >>> while testing between Pharo and Gemstone I've noticed that Pharo allows following code, while Gemstone does not. >>> >>> renderSelectorAndReturnBrushForSelector: aSelector. >>> ^canvas textInput >>> id: (self idForSelector: aSelector); >>> value: (self inputValueForSelector: aSelector); >>> script: (canvas jQuery new datepicker); >>> yourself >>> >>> The error is that in the message definition: renderSelectorAndReturnBrushForSelector: aSelector. there is a dot on the end. >>> >>> This seems like an error in the Pharo compiler ? or not? >>> >>> Kind Regards, >>> >>> Bart >>> _______________________________________________ >>> Pharo-project mailing list >>> Pharo-project(a)lists.gforge.inria.fr >>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >> >> >> _______________________________________________ >> Pharo-project mailing list >> Pharo-project(a)lists.gforge.inria.fr >> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

Sept. 13, 2010

Re: [Pharo-project] Improving generate accessors for refactoring browser

by Guillermo Polito

which pattern? I thought we were discussing about the default... :S I think that anObject is an ugly default, yes. I prefere to have >>niceSarasa: aNiceSarasa niceSarasa := aNiceSarasa than >>niceSarasa: anObject niceSarasa := anObject Obviously, these are useful only when we autogenerate the accesors :). If I have to modify every accesor I autogenerate, it's like not autogenerating it :). BTW, I never use that refactor :P. Cheers! On Mon, Sep 13, 2010 at 11:16 AM, Lukas Renggli <renggli(a)gmail.com> wrote: > In my image only 9% of the accessors follow this pattern. > > Lukas > > 2010/9/13 Bart Gauquie <bart.gauquie(a)gmail.com>: > > don't use the type, i only uses the name of the parameter var to derive > the > > name of parameter > > > > 2010/9/13 Miguel Enrique CobÃ¡ MartÃnez <miguel.coba(a)gmail.com> > >> > >> El lun, 13-09-2010 a las 14:02 +0200, Lukas Renggli escribiÃ³: > >> > How you derive the type? > >> > >> I think it only uses the name of the inst var to name the parameter var > >> in the accessor. > >> > >> > > >> > >From the method name? I think only very few accessors/inst-vars are > >> > named after the type. > >> > > >> > Also note that you can edit the type directly in the changes browser > >> > before you install it, that's what I typically do. > >> > > >> > Lukas > >> > > >> > 2010/9/13 Mariano Martinez Peck <marianopeck(a)gmail.com>: > >> > > i would like that too > >> > > > >> > > On Sep 12, 2010 7:27 PM, "Bart Gauquie" <bart.gauquie(a)gmail.com> > >> > > wrote: > >> > > > >> > > Dear list, > >> > > > >> > > I've noticed that when I'm using the generate accessors refactoring, > >> > > I'm > >> > > always adapting the generated code for the mutator: > >> > > number: anObject > >> > > number := anObject > >> > > to: > >> > > number: aNumber > >> > > number := aNumber > >> > > So I've adapted the refactoring code a bit so that it automatically > >> > > generates this correctly. Anybody also thinks this is useful? If so, > I > >> > > will > >> > > create a bug/improvement and a slice for it. > >> > > Kind regards, > >> > > > >> > > Bart > >> > > _______________________________________________ > >> > > Pharo-project mailing list > >> > > Pharo-project(a)lists.gforge.inria.fr > >> > > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > >> > > > >> > > _______________________________________________ > >> > > Pharo-project mailing list > >> > > Pharo-project(a)lists.gforge.inria.fr > >> > > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > >> > > > >> > > >> > > >> > > >> > >> -- > >> Miguel CobÃ¡ > >> http://miguel.leugim.com.mx > >> > >> > >> _______________________________________________ > >> Pharo-project mailing list > >> Pharo-project(a)lists.gforge.inria.fr > >> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > > > > > > -- > > imagination is more important than knowledge - Albert Einstein > > Logic will get you from A to B. Imagination will take you everywhere - > > Albert Einstein > > Learn from yesterday, live for today, hope for tomorrow. The important > thing > > is not to stop questioning. - Albert Einstein > > The true sign of intelligence is not knowledge but imagination. - Albert > > Einstein > > However beautiful the strategy, you should occasionally look at the > results. > > - Sir Winston Churchill > > It's not enough that we do our best; sometimes we have to do what's > > required. - Sir Winston Churchill > > > > _______________________________________________ > > Pharo-project mailing list > > Pharo-project(a)lists.gforge.inria.fr > > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > > > > > > -- > Lukas Renggli > www.lukas-renggli.ch > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >

Sept. 13, 2010

Re: [Pharo-project] Compiling the VM for MacOSX

by Alexandre Bergel

Yup, much clearer now. Thanks John! Alexandre On 11 Sep 2010, at 19:11, John M McIntosh wrote: > On 2010-09-11, at 7:42 AM, Alexandre Bergel wrote: >> >>> If you want a fast vm i recommend to compile in deployment, but that take more time. >> >> How do I compile in deployment? By inspecting the project and selecting the "Build" tab? > > Ok, there is a bit of learning that has to take place since I'm going to assume if you want to > build your own VM, then you should be familiar with XCode, otherwise you should just > use the pre-built binaries. > > The Build tab you refer to lets you change the compile, link, deployment settings. > > In the Menu Bar the "Project" menu has "Set Active..." to let you choose which project to build > and the type, etc... > > >> >> Cheers, >> Alexandre >> > > -- > =========================================================================== > John M. McIntosh <johnmci(a)smalltalkconsulting.com> Twitter: squeaker68882 > Corporate Smalltalk Consulting Ltd. http://www.smalltalkconsulting.com > =========================================================================== > > > > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project -- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.

Sept. 13, 2010

Re: [Pharo-project] Compiler throws error in Gemstone, not in Pharo

by Lukas Renggli

> it's an empty statement -> gs parser does not allow that > > btw, I think this is a rule in code critic, so if you launch that, you will get all these problems before trying to load them into GS Yes, Slime detects these kind of syntactic problems that impact portability. Lukas -- Lukas Renggli www.lukas-renggli.ch

Sept. 13, 2010

Re: [Pharo-project] Improving generate accessors for refactoring browser

by Lukas Renggli

In my image only 9% of the accessors follow this pattern. Lukas 2010/9/13 Bart Gauquie <bart.gauquie(a)gmail.com>: > don't use the type, i only uses the name of the parameter var to derive the > name of parameter > > 2010/9/13 Miguel Enrique CobÃ¡ MartÃnez <miguel.coba(a)gmail.com> >> >> El lun, 13-09-2010 a las 14:02 +0200, Lukas Renggli escribiÃ³: >> > How you derive the type? >> >> I think it only uses the name of the inst var to name the parameter var >> in the accessor. >> >> > >> > >From the method name? I think only very few accessors/inst-vars are >> > named after the type. >> > >> > Also note that you can edit the type directly in the changes browser >> > before you install it, that's what I typically do. >> > >> > Lukas >> > >> > 2010/9/13 Mariano Martinez Peck <marianopeck(a)gmail.com>: >> > > i would like that too >> > > >> > > On Sep 12, 2010 7:27 PM, "Bart Gauquie" <bart.gauquie(a)gmail.com> >> > > wrote: >> > > >> > > Dear list, >> > > >> > > I've noticed that when I'm using the generate accessors refactoring, >> > > I'm >> > > always adapting the generated code for the mutator: >> > > number: anObject >> > > Â Â number := anObject >> > > to: >> > > number: aNumber >> > > Â Â number := aNumber >> > > So I've adapted the refactoring code a bit so that it automatically >> > > generates this correctly. Anybody also thinks this is useful? If so, I >> > > will >> > > create a bug/improvement and a slice for it. >> > > Kind regards, >> > > >> > > Bart >> > > _______________________________________________ >> > > Pharo-project mailing list >> > > Pharo-project(a)lists.gforge.inria.fr >> > > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >> > > >> > > _______________________________________________ >> > > Pharo-project mailing list >> > > Pharo-project(a)lists.gforge.inria.fr >> > > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >> > > >> > >> > >> > >> >> -- >> Miguel CobÃ¡ >> http://miguel.leugim.com.mx >> >> >> _______________________________________________ >> Pharo-project mailing list >> Pharo-project(a)lists.gforge.inria.fr >> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > > > -- > imagination is more important than knowledge - Albert Einstein > Logic will get you from A to B. Imagination will take you everywhere - > Albert Einstein > Learn from yesterday, live for today, hope for tomorrow. The important thing > is not to stop questioning. - Albert Einstein > The true sign of intelligence is not knowledge but imagination. - Albert > Einstein > However beautiful the strategy, you should occasionally look at the results. > - Sir Winston Churchill > It's not enough that we do our best; sometimes we have to do what's > required. - Sir Winston Churchill > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > -- Lukas Renggli www.lukas-renggli.ch

Sept. 13, 2010

Re: [Pharo-project] One order of magnitude faster sets/dicts?!

by Adrian Lienhard

No, they just compared to Pharo 1.1. But the benchmarks are available in a separate package. Adrian On Sep 13, 2010, at 15:52 , StÃ©phane Ducasse wrote: > do you know if they compare with squeak because levent did a lot of work in that area. > > Stef > > On Sep 13, 2010, at 2:55 PM, Adrian Lienhard wrote: > >> This mail is quite long as I copied it from a conversation with Toon Verwaest. Toon and Camillo re-implemented hashed collections for Pinocchio (http://scg.unibe.ch/research/pinocchio) Their benchmarks have shown that the new implementation is significantly faster than the one in Pharo 1.1. The source code is available from www.squeaksource.com/p.html (they haven't set a license, but I'm pretty sure they'll release their code as MIT). >> >> I post this here to find somebody knowledgeable in the area to take a look at the code and figure out whether this implementation would be interesting for Pharo... >> >> Cheers, >> Adrian >> >> >> citing Toon: >> >> We ran some benchmarks on our data structures (It's in comparison with and benchmarked in standard Pharo 1.1). We just add / remove integers within a certain range thus always perfectly distributed making it ideal for Pharo dictionaries. >> >> The numbers show how long a certain benchmark took on average in 20 runs of the benchmark and its standard deviation over those runs. A single benchmark run generally consists of many individual operations on the collection in question. For example: >> >> benchIncludes >> 1 to: set size * 2 do: [ :i| >> set includes: i ] >> >> where the set has size 10000. Evaluating this once results in a single run. So the number at the top of the benchmark is the sum of all averages with the average stdev. >> >> The results: >> >> PDictionary: 15.8 +/-1.7 >> Do 0.472 +/-0.079 >> RemoveKey 0.010 +/-0.021 >> AtPut 0.947 +/-0.02 >> AtIfAbsentPut 1.64 +/-0.96 >> AtPutExisting 0.198 +/-0.011 >> KeysAndValuesDo 0.502 +/-0.09 >> IncludesKey 0.365 +/-0.024 >> AtPutNew 4.2 +/-1.3 >> Includes 7.40 +/-0.33 >> >> Dictionary: 138.2 +/-4.7 >> Do 0.830 +/-0.098 >> RemoveKey 10.292 +/-0.077 >> AtPut 0.957 +/-0.044 >> AtIfAbsentPut 1.52 +/-0.95 >> AtPutExisting 0.203 +/-0.011 >> KeysAndValuesDo 0.850 +/-0.096 >> IncludesKey 80.25 +/-0.25 >> AtPutNew 3.5 +/-1.3 >> Includes 39.8 +/-4.4 >> >> PSet: 1.767 +/-0.057 >> Remove 0.008 +/-0.018 >> Add 0.845 +/-0.039 >> AddExisting 0.310 +/-0.021 >> AddNew 0.240 +/-0.021 >> Includes 0.365 +/-0.024 >> >> Set: 70.9 +/-1.2 >> Remove 7.737 +/-0.051 >> Add 0.755 +/-0.022 >> AddExisting 0.305 +/-0.015 >> AddNew 2.473 +/-0.03 >> Includes 59.6 +/-1.2 >> >> >> Obviously the very slight differences have to be taken with a grain of salt, but whenever it's more than 10x faster it's quite unlikely that it's due to some random runtime variation that might totally change in another run. >> >> An important thing for our datastructures is that they don't degrade since we don't have colliding hashes; but we didn't really test that yet (although it becomes obvious in some of the benchmark results such as removing of elements and testing presence of elements). >> >>> Is there anything special that one would neet to consider when replacing the old implementation in Pharo with yours? >> >> What doesn't happen at the moment is shrinking dictionaries after they have grown significantly. I wouldn't know at what point to do so either; nor do I think Dictionary does that? >> >> There is a parameter indicating how many elements can be added before it switches from a SmallDictionary version to a dictionary with buckets. This is set to 20 by default, and I have no idea if it makes sense to change it; I didn't really profile what the optimal number is. Maybe it makes sense to make that a constant in the code rather than an instance variable to save a bit of space and time ... >> >> We have our own PHashedCollection subclassing from Collection; so the biggest part of the hierarchy is compatible with what Pharo has. Mostly while porting Pinocchio-specific stuff will have to be removed; mostly annotations related to Pinocchio Primitives and exporting directives. This is all straightforward though. >> >> The current "ratio" of hashes to elements is set to 500%. So basically when you have 32 buckets it will only grow when it contains 160 elements (or key-value pairs), so 5 elements per bucket on average. This seems to not make it slower which is understandable since SmallDictionary is pretty fast for small amounts of elements; but this ratio might have to be tweaked depending on the kind of objects and is currently a parameter. The advantage of using 500% is that you have A LOT less garbage. >> >> Oh, and our dictionaries do use a lot less garbage, since Pharo's dictionaries use association objects for each key-value pair. We don't, so we never generate garbage when you remove an object. >> Our Sets on the other hand do use a bit more memory because of the bucket scheme. Sets don't use associations so we don't have an edge there :) Only performance-wise in that case. >> >> The hashes are masked with the amount of buckets - 1, since the buckets are always a power of 2. >> This implies that the lower bits of the hash are the most significant ones. This does not work together with the current identityHash / IdentityDictionary since the 12bit hash is shifted to the left by 18 (or so). This would make all the lower 18 bits 0 and all objects thus ending up in the first bucket. >> >> That is a very important thing to note enough. However, I also think it's a bit strange to just bitshift the identityHash by 18. You don't win any significant numbers with it ... you have 12bit hashes; no way to improve that (without changing the image format). Since we overfill our dictionaries however this works quite ok with those bad hashes; and we'll only start wasting a bit of space after you have added 20480 elements to the dictionary (you have 4096 different hashes with 12 bits, * 5). >> >> >> >> _______________________________________________ >> Pharo-project mailing list >> Pharo-project(a)lists.gforge.inria.fr >> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

Sept. 13, 2010

Re: [Pharo-project] Compiler throws error in Gemstone, not in Pharo

by Johan Brichau

What's the dot doing after 'aSelector' ? :-) it's an empty statement -> gs parser does not allow that btw, I think this is a rule in code critic, so if you launch that, you will get all these problems before trying to load them into GS On 13 Sep 2010, at 13:55, StÃ©phane Ducasse wrote: > Yes but what is wrong on gemstone. > > Stef > > >> Dear list, >> >> while testing between Pharo and Gemstone I've noticed that Pharo allows following code, while Gemstone does not. >> >> renderSelectorAndReturnBrushForSelector: aSelector. >> ^canvas textInput >> id: (self idForSelector: aSelector); >> value: (self inputValueForSelector: aSelector); >> script: (canvas jQuery new datepicker); >> yourself >> >> The error is that in the message definition: renderSelectorAndReturnBrushForSelector: aSelector. there is a dot on the end. >> >> This seems like an error in the Pharo compiler ? or not? >> >> Kind Regards, >> >> Bart >> _______________________________________________ >> Pharo-project mailing list >> Pharo-project(a)lists.gforge.inria.fr >> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

Sept. 13, 2010

Re: [Pharo-project] Improving generate accessors for refactoring browser

by Bart Gauquie

don't use the type, i only uses the name of the parameter var to derive the name of parameter 2010/9/13 Miguel Enrique CobÃ¡ MartÃnez <miguel.coba(a)gmail.com> > El lun, 13-09-2010 a las 14:02 +0200, Lukas Renggli escribiÃ³: > > How you derive the type? > > I think it only uses the name of the inst var to name the parameter var > in the accessor. > > > > > >From the method name? I think only very few accessors/inst-vars are > > named after the type. > > > > Also note that you can edit the type directly in the changes browser > > before you install it, that's what I typically do. > > > > Lukas > > > > 2010/9/13 Mariano Martinez Peck <marianopeck(a)gmail.com>: > > > i would like that too > > > > > > On Sep 12, 2010 7:27 PM, "Bart Gauquie" <bart.gauquie(a)gmail.com> > wrote: > > > > > > Dear list, > > > > > > I've noticed that when I'm using the generate accessors refactoring, > I'm > > > always adapting the generated code for the mutator: > > > number: anObject > > > number := anObject > > > to: > > > number: aNumber > > > number := aNumber > > > So I've adapted the refactoring code a bit so that it automatically > > > generates this correctly. Anybody also thinks this is useful? If so, I > will > > > create a bug/improvement and a slice for it. > > > Kind regards, > > > > > > Bart > > > _______________________________________________ > > > Pharo-project mailing list > > > Pharo-project(a)lists.gforge.inria.fr > > > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > > > > > > _______________________________________________ > > > Pharo-project mailing list > > > Pharo-project(a)lists.gforge.inria.fr > > > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > > > > > > > > > > > -- > Miguel CobÃ¡ > http://miguel.leugim.com.mx > > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > -- imagination is more important than knowledge - Albert Einstein Logic will get you from A to B. Imagination will take you everywhere - Albert Einstein Learn from yesterday, live for today, hope for tomorrow. The important thing is not to stop questioning. - Albert Einstein The true sign of intelligence is not knowledge but imagination. - Albert Einstein However beautiful the strategy, you should occasionally look at the results. - Sir Winston Churchill It's not enough that we do our best; sometimes we have to do what's required. - Sir Winston Churchill

Sept. 13, 2010

Re: [Pharo-project] One order of magnitude faster sets/dicts?!

by StÃ©phane Ducasse

do you know if they compare with squeak because levent did a lot of work in that area. Stef On Sep 13, 2010, at 2:55 PM, Adrian Lienhard wrote: > This mail is quite long as I copied it from a conversation with Toon Verwaest. Toon and Camillo re-implemented hashed collections for Pinocchio (http://scg.unibe.ch/research/pinocchio) Their benchmarks have shown that the new implementation is significantly faster than the one in Pharo 1.1. The source code is available from www.squeaksource.com/p.html (they haven't set a license, but I'm pretty sure they'll release their code as MIT). > > I post this here to find somebody knowledgeable in the area to take a look at the code and figure out whether this implementation would be interesting for Pharo... > > Cheers, > Adrian > > > citing Toon: > > We ran some benchmarks on our data structures (It's in comparison with and benchmarked in standard Pharo 1.1). We just add / remove integers within a certain range thus always perfectly distributed making it ideal for Pharo dictionaries. > > The numbers show how long a certain benchmark took on average in 20 runs of the benchmark and its standard deviation over those runs. A single benchmark run generally consists of many individual operations on the collection in question. For example: > > benchIncludes > 1 to: set size * 2 do: [ :i| > set includes: i ] > > where the set has size 10000. Evaluating this once results in a single run. So the number at the top of the benchmark is the sum of all averages with the average stdev. > > The results: > > PDictionary: 15.8 +/-1.7 > Do 0.472 +/-0.079 > RemoveKey 0.010 +/-0.021 > AtPut 0.947 +/-0.02 > AtIfAbsentPut 1.64 +/-0.96 > AtPutExisting 0.198 +/-0.011 > KeysAndValuesDo 0.502 +/-0.09 > IncludesKey 0.365 +/-0.024 > AtPutNew 4.2 +/-1.3 > Includes 7.40 +/-0.33 > > Dictionary: 138.2 +/-4.7 > Do 0.830 +/-0.098 > RemoveKey 10.292 +/-0.077 > AtPut 0.957 +/-0.044 > AtIfAbsentPut 1.52 +/-0.95 > AtPutExisting 0.203 +/-0.011 > KeysAndValuesDo 0.850 +/-0.096 > IncludesKey 80.25 +/-0.25 > AtPutNew 3.5 +/-1.3 > Includes 39.8 +/-4.4 > > PSet: 1.767 +/-0.057 > Remove 0.008 +/-0.018 > Add 0.845 +/-0.039 > AddExisting 0.310 +/-0.021 > AddNew 0.240 +/-0.021 > Includes 0.365 +/-0.024 > > Set: 70.9 +/-1.2 > Remove 7.737 +/-0.051 > Add 0.755 +/-0.022 > AddExisting 0.305 +/-0.015 > AddNew 2.473 +/-0.03 > Includes 59.6 +/-1.2 > > > Obviously the very slight differences have to be taken with a grain of salt, but whenever it's more than 10x faster it's quite unlikely that it's due to some random runtime variation that might totally change in another run. > > An important thing for our datastructures is that they don't degrade since we don't have colliding hashes; but we didn't really test that yet (although it becomes obvious in some of the benchmark results such as removing of elements and testing presence of elements). > >> Is there anything special that one would neet to consider when replacing the old implementation in Pharo with yours? > > What doesn't happen at the moment is shrinking dictionaries after they have grown significantly. I wouldn't know at what point to do so either; nor do I think Dictionary does that? > > There is a parameter indicating how many elements can be added before it switches from a SmallDictionary version to a dictionary with buckets. This is set to 20 by default, and I have no idea if it makes sense to change it; I didn't really profile what the optimal number is. Maybe it makes sense to make that a constant in the code rather than an instance variable to save a bit of space and time ... > > We have our own PHashedCollection subclassing from Collection; so the biggest part of the hierarchy is compatible with what Pharo has. Mostly while porting Pinocchio-specific stuff will have to be removed; mostly annotations related to Pinocchio Primitives and exporting directives. This is all straightforward though. > > The current "ratio" of hashes to elements is set to 500%. So basically when you have 32 buckets it will only grow when it contains 160 elements (or key-value pairs), so 5 elements per bucket on average. This seems to not make it slower which is understandable since SmallDictionary is pretty fast for small amounts of elements; but this ratio might have to be tweaked depending on the kind of objects and is currently a parameter. The advantage of using 500% is that you have A LOT less garbage. > > Oh, and our dictionaries do use a lot less garbage, since Pharo's dictionaries use association objects for each key-value pair. We don't, so we never generate garbage when you remove an object. > Our Sets on the other hand do use a bit more memory because of the bucket scheme. Sets don't use associations so we don't have an edge there :) Only performance-wise in that case. > > The hashes are masked with the amount of buckets - 1, since the buckets are always a power of 2. > This implies that the lower bits of the hash are the most significant ones. This does not work together with the current identityHash / IdentityDictionary since the 12bit hash is shifted to the left by 18 (or so). This would make all the lower 18 bits 0 and all objects thus ending up in the first bucket. > > That is a very important thing to note enough. However, I also think it's a bit strange to just bitshift the identityHash by 18. You don't win any significant numbers with it ... you have 12bit hashes; no way to improve that (without changing the image format). Since we overfill our dictionaries however this works quite ok with those bad hashes; and we'll only start wasting a bit of space after you have added 20480 elements to the dictionary (you have 4096 different hashes with 12 bits, * 5). > > > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

Sept. 13, 2010

Re: [Pharo-project] One order of magnitude faster sets/dicts?!

by Levente Uzonyi

On Mon, 13 Sep 2010, Adrian Lienhard wrote: > This mail is quite long as I copied it from a conversation with Toon Verwaest. Toon and Camillo re-implemented hashed collections for Pinocchio (http://scg.unibe.ch/research/pinocchio) Their benchmarks have shown that the new implementation is significantly faster than the one in Pharo 1.1. The source code is available from www.squeaksource.com/p.html (they haven't set a license, but I'm pretty sure they'll release their code as MIT). > > I post this here to find somebody knowledgeable in the area to take a look at the code and figure out whether this implementation would be interesting for Pharo... > > Cheers, > Adrian > > > citing Toon: > > We ran some benchmarks on our data structures (It's in comparison with and benchmarked in standard Pharo 1.1). We just add / remove integers within a certain range thus always perfectly distributed making it ideal for Pharo dictionaries. > > The numbers show how long a certain benchmark took on average in 20 runs of the benchmark and its standard deviation over those runs. A single benchmark run generally consists of many individual operations on the collection in question. For example: > > benchIncludes > 1 to: set size * 2 do: [ :i| > set includes: i ] > > where the set has size 10000. Evaluating this once results in a single run. So the number at the top of the benchmark is the sum of all averages with the average stdev. > > The results: > > PDictionary: 15.8 +/-1.7 > Do 0.472 +/-0.079 > RemoveKey 0.010 +/-0.021 > AtPut 0.947 +/-0.02 > AtIfAbsentPut 1.64 +/-0.96 > AtPutExisting 0.198 +/-0.011 > KeysAndValuesDo 0.502 +/-0.09 > IncludesKey 0.365 +/-0.024 > AtPutNew 4.2 +/-1.3 > Includes 7.40 +/-0.33 > > Dictionary: 138.2 +/-4.7 > Do 0.830 +/-0.098 > RemoveKey 10.292 +/-0.077 > AtPut 0.957 +/-0.044 > AtIfAbsentPut 1.52 +/-0.95 > AtPutExisting 0.203 +/-0.011 > KeysAndValuesDo 0.850 +/-0.096 > IncludesKey 80.25 +/-0.25 > AtPutNew 3.5 +/-1.3 > Includes 39.8 +/-4.4 > > PSet: 1.767 +/-0.057 > Remove 0.008 +/-0.018 > Add 0.845 +/-0.039 > AddExisting 0.310 +/-0.021 > AddNew 0.240 +/-0.021 > Includes 0.365 +/-0.024 > > Set: 70.9 +/-1.2 > Remove 7.737 +/-0.051 > Add 0.755 +/-0.022 > AddExisting 0.305 +/-0.015 > AddNew 2.473 +/-0.03 > Includes 59.6 +/-1.2 > > > Obviously the very slight differences have to be taken with a grain of salt, but whenever it's more than 10x faster it's quite unlikely that it's due to some random runtime variation that might totally change in another run. I'm a bit skeptic, because 10x improvement is pretty hard to get if the benchmark is not flawed and the code doesn't use VM support. I wonder what the #pPrimitive:plugin: pragmas stand for in PDictionary's #at:ifAbsent: and #at:put:. Where can I find the benchmark code? > > An important thing for our datastructures is that they don't degrade since we don't have colliding hashes; but we didn't really test that yet (although it becomes obvious in some of the benchmark results such as removing of elements and testing presence of elements). > >> Is there anything special that one would neet to consider when replacing the old implementation in Pharo with yours? > > What doesn't happen at the moment is shrinking dictionaries after they have grown significantly. I wouldn't know at what point to do so either; nor do I think Dictionary does that? The current HashedCollections don't shrink. Remove is a rarely used operation. > > There is a parameter indicating how many elements can be added before it switches from a SmallDictionary version to a dictionary with buckets. This is set to 20 by default, and I have no idea if it makes sense to change it; I didn't really profile what the optimal number is. Maybe it makes sense to make that a constant in the code rather than an instance variable to save a bit of space and time ... > > We have our own PHashedCollection subclassing from Collection; so the biggest part of the hierarchy is compatible with what Pharo has. Mostly while porting Pinocchio-specific stuff will have to be removed; mostly annotations related to Pinocchio Primitives and exporting directives. This is all straightforward though. > > The current "ratio" of hashes to elements is set to 500%. So basically when you have 32 buckets it will only grow when it contains 160 elements (or key-value pairs), so 5 elements per bucket on average. This seems to not make it slower which is understandable since SmallDictionary is pretty fast for small amounts of elements; but this ratio might have to be tweaked depending on the kind of objects and is currently a parameter. The advantage of using 500% is that you have A LOT less garbage. > > Oh, and our dictionaries do use a lot less garbage, since Pharo's dictionaries use association objects for each key-value pair. We don't, so we never generate garbage when you remove an object. > Our Sets on the other hand do use a bit more memory because of the bucket scheme. Sets don't use associations so we don't have an edge there :) Only performance-wise in that case. One could implement the current dictionaries without associations, that's just less object-oriented. That would generate even less "garbage". > > The hashes are masked with the amount of buckets - 1, since the buckets are always a power of 2. > This implies that the lower bits of the hash are the most significant ones. This does not work together with the current identityHash / IdentityDictionary since the 12bit hash is shifted to the left by 18 (or so). This would make all the lower 18 bits 0 and all objects thus ending up in the first bucket. > > That is a very important thing to note enough. However, I also think it's a bit strange to just bitshift the identityHash by 18. You don't win any significant numbers with it ... you have 12bit hashes; no way to improve that (without changing the image format). Since we overfill our dictionaries however this works quite ok with those bad hashes; and we'll only start wasting a bit of space after you have added 20480 elements to the dictionary (you have 4096 different hashes with 12 bits, * 5). Let's imagine that we want to put 10000 objects into a IdentitySet. Each object has it's identityHash in the 0..4095 range. The hash function is very simple: hash \\ capacity + 1. Therefore the values of the hash function will all be in 1..4096, even if capacity is ~15000. This causes a lot of collisions (the table will be consist of a few very long chains degrading performance to unacceptable leves). These collisions are avoided by the shift. Levente > > > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >

Sept. 13, 2010