> From:   "Andreas Raab" < andreas.raab at g... >
> Date:   Wed Jul 16, 2003  1:09 am
> Subject:   RE: [ENH][VM] HashBits, a lazy way
> Hi John,
>
> I've been looking over your changes and my feeling is that the  
> complexity of
> the implementation of having objects "magically aquire" a hash when  
> they are
> moved from young to old space just isn't worth the trouble of finding  
> the
> bugs if any mistake is ever made here.

In some respects that is my thought too, as you pointed out I've one  
bug you mentioned below, although
if I had coded up the check for hash zero leakage, I would have found  
that. However I'm
afraid that some innocent VM change would cause hash zero leakage which  
wouldn't
become easily apparent until someone reported some drastic performance  
issue.


> Perhaps as an enlightening example, you have (at least) one bug in the  
> hash
> implementation. In #newObjectHash you try to avoid zero hashes,  
> however, you
> do this based on a 16 bit counter where we only use 12 bits later on.  
> In
> other words, if the lastHash is computed to 16rX000 then the hash  
> actually
> stored *will* be zero (btw, surprising you didn't find this - it  
> happens all
> 4096 allocations or so ;-) The kind of extremely subtle problems we're
> potentially introducing here is *way* beyound what I consider  
> reasonable,
> even given the potential speed advantages. In short, if any such  
> change is
> ever made, then we really should do so on a single consistent model  
> (zero
> hash means unassigned) and not based on a mix of space location, with  
> the
> need to assign those hashes when something moves between here and  
> there. My
> opinion: Not in VI3.
>
> Here's another thought on this. Not sure if you realize this but our  
> "random
> number generator" has a periodicity of 4096, e.g., the values are  
> spread
> evenly so it's essentially nothing but a shuffled list of values from  
> zero
> to 4096. This, in turn, means that you don't have to do any  
> computation if
> you don't want to - you could precompute all the hashes and keep them  
> in a
> lookup table with the bits at the right position already. I don't know  
> what
> the implications on speed are (considering cache size effects etc.)  
> but it
> may very well be worth a try and it avoids the nastyness of the above.  
> E.g.,
> #newObjectHash might just look like:
>
> ^hashTable at: (hashIndex := hashIndex + 1 bitAnd: 4095)

I had thought about this but was concerned about memory usage, but  
perhaps not an issue.
So why don't we just try a random shuffle of 0-4095 in a hard coded  
constant table
for the hashTable and use lastHash as the index to preserve the  
existing image store/fetch logic, and
as you point out avoid the bit shift.

>
> About the other changes, the refactoring for allocating unfilled  
> objects
> look reasonable but I don't understand why you changed the "other
> primitives" to use the unfilled allocation. There is no reason for it  
> except
> from an (irrelevant) tiny increment in speed. It seems to me that we  
> should
> only optimize places where we can show that they have practical  
> implications
> - none of which is true for any of the "other primitives". Allocating  
> filled
> objects is the safe, recommended way and using unfilled allocations  
> should
> really only be done in places where we expect people to understand  
> that they
> are time-critical (such as the #floatObjectOf: or
> #positive32BitIntegerFor:).

Well all these calls used the small class allocation with fill ->yes.  
But when I refactored the
instantiateSmallClass: classPointer sizeInBytes: sizeInBytes fill:  
fillValue call I realized every call to the smallclass
really didn't need the fill, and by disposing of the fill value and  
fill flag I reduce register loading/using and an
instruction or two.

>
> BTW, your measures below are all micro-benchmarks, did you ever try  
> any of
> the macros to see what the results are in practice? In particular, the
> impact on tenuring would be interesting in the "assign hashes on  
> tenure"
> scheme. I'd like to see if there's a real-world improvement besides the
> theoretical case. And, I would actually expect any measurable  
> improvements
> come from the unfilled allocations - any chance to factor those out  
> and run
> macros on them separately?

I'll work on it, I'll do the constant hash table first and see what  
happens.

>
> Cheers,
> - Andreas
--
======================================================================== 
===
John M. McIntosh <johnmci at smalltalkconsulting.com> 1-800-477-2659
Corporate Smalltalk Consulting Ltd.  http://www.smalltalkconsulting.com
======================================================================== 
===