On Tue, 23 Mar 2010, Andres Valloud wrote:
As soon as you get a JIT VM, you will be surprised at how expensive primitives that require calling a C function can be. You might be better off without the primitive and with a more streamlined hashed collection instead. Also, the presence of the primitive will allow little to no flexibility...
We don't have a JIT and who knows if and when we will have one. Until then the following runtime rule applies most of the time: primitives < code mostly bytecodes < code with sends. And note that here I was talking abot #pointsTo: which when sent to an array tells if and object is in the array using ==. LargeIdentitySet uses this primitive to tell if the object is in the "list" of objects which have the same identity hash.
Levente
On 3/23/10 16:47 , Levente Uzonyi wrote:
On Wed, 24 Mar 2010, Bert Freudenberg wrote:
On 23.03.2010, at 23:57, Levente Uzonyi wrote:
On Tue, 23 Mar 2010, Bert Freudenberg wrote:
On 23.03.2010, at 16:01, Lukas Renggli wrote:
>> Just an idea: we could get rid of compact classes, which would give >> us >> additional 6 bits (5 bits from the compact class index plus 1 bit >> from the >> header type because there would only be 2 header types left). This >> would >> increase the identity hash values from 4096 to 262144. In a >> PharoCore1.0 >> image there are 148589 instances of compact classes, hence this would >> cost >> 580k. Or, we could just add an additional word and use the spare bits >> from >> the old identity hash for other stuff, e.g., immutability ;) >> > I like the first idea, we could even have the 17 continuous bits for > identity hash the 1 separate bit for immutability. > Yes please, I love it :-)
Lukas
Well, someone should code it up, and then lets's see macro benchmarks :)
That's a great idea, but I'm sure it'll take a while until that happens. Fortunately identityhash related benchmarks can be done without changing the vm. I rewrote a bit the benchmark from Chris, created three classes which have 17, 18 and 30 bits for #scaledIdentityHash. Ran the benchmark with these three classes + Object, collected the data and created some diagrams. I'm sure most people don't care about the code/data[1], so here are the diagrams: http://leves.web.elte.hu/identityHashBits/identityHashBits.png http://leves.web.elte.hu/identityHashBits/identityHashBits2.png http://leves.web.elte.hu/identityHashBits/identityHashBits3.png
The first one contains the four graphs. It clearly shows that 12 bits (Object) are insufficient for #identityHash. Even 5 more bits gives 8-9x speedup and a dramatic change in behavior.
The second is the same as the first, but it shows only the 17, 18 and 30 bits case. Note that the primes (hashtable sizes) are now optimized for 12 bits. If they are optimized for 17/18 bits then the results can be better for larger set sizes (130+/260+) where they show worse behavior compared to the 18/30 bits case.
The third graph shows how an optimized data structure (LargeIdentitySet) compares to the 17, 18 and 30 bits case using only 12 bits.
[1] All the code/data that were used to generate these graphs can be found here http://leves.web.elte.hu/identityHashBits
Levente
P.S. I also created a 12 bit version of the 17-18-30 bit classes and found that it's 1.2-2.0x slower than Object, so the values after the vm changes are expected to be even better than what these graphs show.
So this seems to indicate your specialized data structure beats all VM hash bits extension?
For IdentitySet - probably yes, up to a few million elements, but I expect the difference to be smaller with the vm support and optimal table sizes. (note that a "normal" image contains less than 500000 objects). For IdentityDictionary - probably not, because we don't have a fast primitive that can be used for the lookups.
Levente
Also, we don't know yet how getting rid of compact classes would affect performance.
- Bert -
.