October 2009 - Pharo-dev - lists.pharo.org

Re: [Pharo-project] hashing collections
by Ralph Boland Oct. 25, 2009

Oct. 25, 2009

> > Watch out for cancellation effects... if the collections are > sequenceable and the hash values of their contents are not well > distributed, you may end up with performance issues because the hash > values cancel each other because the hash function commutes. Â Consider > for example the hash value of the following collections: > > #(1 2 3) > #(1 2 3 4 4) > #(1 2 3 5 5) > #(1 4 2 3 4) > #(5 4 3 2 1 4 5) > > #(6) > #(1 2 3 4 5 6 5 4 3 2 1) > > I am not familiar with your application, though, so perhaps the data > does not cause these problems. > > Andres. > You are right. These are serious problems with my idea and I retract the proposal that the idea may be preferable to the problems we have with putting the standard collections into Sets and Dictionaries. It works well in my application because in each case the collections have no duplicates and order doesn't matter. That is, in my application, the hash collections are all effectively sets or dictionaries in compacted form. I use a bit of code specific to my application to ensure they then are compared efficiently. Ralph > Ralph Boland wrote: >> Food for thought: >> >> In my finite state machine generator I do a lot of >> hashing of sometimes large collections. >> For performance reasons I created hash value storing versions >> of the relevant collection classes. Â Getting the hash value >> of the hashed version of a collection was then very fast >> (accessing an instance value) and the hash values were good. >> >> For example, for Array I created HashArray Â The hash >> value of a HashArray was the XOR of the hash values of >> the elements of the HashArray. Â Note that this meant >> that each time you changed the entry in a HashArray >> you had to update the hash value. >> So for HashArray Â Â at: index put: object Â Â would look something >> like: >> >> Â Â Â hash := (hash xor: object hash) xor: (self at: index). >> Â Â Â super at: index put: object. >> >> If you like living on the edge you could instead leave out updating >> the hash value until you put the HashArray object where its hash >> value would be needed (like a Set or Dictionary (key)). >> This is of course error prone but then >> putting collections in Sets or Dictionaries (keys) >> is inherently error prone anyway because modifying the collection >> changes its hash value thus breaking every Set or Dictionary >> containing the collection. >> >> I would be temped to have all real collection classes (e.g. not Interval) >> not be storable in Sets or Dictionaries (key) at all and instead require >> hash versions of the collection be used but of course this would >> surely break a lot of things. >> >> Ralph Boland >> >> >>

1 0

[Pharo-project] Improve pharo modularity: a first step
by Laval Jannik Oct. 25, 2009

Oct. 25, 2009

Hi all, I would like to improve the modularity of packages in pharo. A first simple thing that I see, is methods "example" use a lot of things in the system. And create cycles between packages. So, I propose to create a new package named "Examples" and put in it all methods named "example2"... Jannik

5 6

[Pharo-project] [update 1.1] #11019
by StÃ©phane Ducasse Oct. 25, 2009

Oct. 25, 2009

11019 ----- - Issue 1343: System-Pragmas - new system category which includes Pragma class and Pragma related stuffs from System-Settings - Reorganized Kernel package by moving Pragma class from Kernel- Methods to Kernel-Pragmas system category - Moved PragmaCollector and related stuff from System-Settings to Kernel-Pragmas.

1 0

[Pharo-project] hashing collections
by Ralph Boland Oct. 25, 2009

Oct. 25, 2009

Food for thought: In my finite state machine generator I do a lot of hashing of sometimes large collections. For performance reasons I created hash value storing versions of the relevant collection classes. Getting the hash value of the hashed version of a collection was then very fast (accessing an instance value) and the hash values were good. For example, for Array I created HashArray The hash value of a HashArray was the XOR of the hash values of the elements of the HashArray. Note that this meant that each time you changed the entry in a HashArray you had to update the hash value. So for HashArray at: index put: object would look something like: hash := (hash xor: object hash) xor: (self at: index). super at: index put: object. If you like living on the edge you could instead leave out updating the hash value until you put the HashArray object where its hash value would be needed (like a Set or Dictionary (key)). This is of course error prone but then putting collections in Sets or Dictionaries (keys) is inherently error prone anyway because modifying the collection changes its hash value thus breaking every Set or Dictionary containing the collection. I would be temped to have all real collection classes (e.g. not Interval) not be storable in Sets or Dictionaries (key) at all and instead require hash versions of the collection be used but of course this would surely break a lot of things. Ralph Boland -- Quantum Theory cannot save us from the tyranny of a deterministic universe. But it does give God something to do.

2 1

[Pharo-project] HashTable vs Dictionary
by Laval Jannik Oct. 25, 2009

Oct. 25, 2009

Hi, Since some weeks, We use in our projects the project HashTable, available at http://www.squeaksource.com/ht.html It could be a good idea to integrate these collections to replace Dictionary and Set. --- Jannik Laval PhD Student - Rmod Team - INRIA Certified Project Management Associate (IPMA) http://www.jannik-laval.eu http://rmod.lille.inria.fr ---

8 35

[Pharo-project] [update 1.1] #11018
by StÃ©phane Ducasse Oct. 25, 2009

Oct. 25, 2009

11018 ----- - Issue 1258 Number-readFrom-followUp There is no use invoking SqNumberParser with failBlock: [^ self error: ...] because this is the default behaviour... - Fix FontTest>>#testResetAfterEmphasized. aFont derivativeFonts cannot be assumed to store emphasized versions indexed by their emph code. - adds squeezeNumberOutOfString: to Number, as discussed in the Pharo workshop. On the way, it fixes an issue in SqNumberParser, where it would return itself rather than the result of the failblack, when parsing fails. Also, a test is added to test and document the new squeezing number out of strings behavior.

1 0

[Pharo-project] [update 1.1] #11017
by StÃ©phane Ducasse Oct. 24, 2009

Oct. 24, 2009

11017 ----- - 1220 followup some more #removeAll following http://code.google.com/p/pharo/issues/detail?id=1220 - Issue 1321: [Sqeak trunk] Shallow copy of BlockClosure Remove BlockClosure>postCopy

1 0

Oct. 24, 2009

nicolas following the includesSelectors: fix I imagine that replacing all the selectors do: by selectorsDo: will avoid creating unnecessary intermediate collection. I checked and there are some places where we could fix that. Stef

2 1

[Pharo-project] System changes & security model
by Igor Stasenko Oct. 24, 2009

Oct. 24, 2009

I trying to make a clean-room prototype of new Package system (yeah yeah..:) The idea is following: the package(s) is in control! I.e. each change to package contents should pass validity checks before getting applied. This would allow us to enforce some policy, which could help to maintain a code in system in good shape. For instance, the most wanted feature, as to me, is to ask package if it: - allows extending other packages by extension methods - allows extensions to be added to package own classes the problem with current kernel, that it never asks anyone if it allowed to do something or not.. instead, the code applies change, and only then using SystemChangeNotifier to broadcast the event of change to any interesting parties.. Such approach hinders any attempts to build a secure system, because once change is made, it could be too late to revert it and its very easy to bypass any system facilities which normally could prevent the user from doing wrong things (like removing Delay class or one of its critical methods ;). And there is a SystemEditor, which unfortunately, not ready for use with Traits :( but afaik, it don't providing any means to validate the changes before applying. Or does? Maybe its worth to create another notification which can notify the interesting parties before the change will be applied? What you think? -- Best regards, Igor Stasenko AKA sig.

1 0

Oct. 24, 2009

11016 ----- - Issue 1359: PseudoClass>> DNU includesSelector: - Issue 1358: Dictionary select: answer a shallow copy | original even | original := Dictionary new. original at: #one put: 1. original at: #two put: 2. even := original select: [:value |value even]. even at: #two put: #two. self assert: (original at: #two) = 2

1 0