Number: 128

Date: 17-Mar-84  0':22':20

Submitter: Masinter.PA

Source: 

Subject: Change GC Hash algorithm to XOR Hiloc

Assigned To: 

Attn: Charnley,vanMelle,JonL,Masinter

Status: Open

In/By: 

Problem Type: Performance

Impact: Minor

Difficulty: Moderate

Frequency: Intermittent

Priority: Perhaps

System: Language Support

Subsystem: Microcode

Machine: 

Disk: 

Lisp Version: 

Source Files: 

Microcode Version: 

Memory Size: 

File Server: 

Server Software Version: 

Disposition: '
[Date':  2 Apr 84 12':48 PST'
From': vanMelle.pa'
AR 128': change to Perhaps]'
["JonL.pa" "24-Sep-84 03':55':46" Attn': Description':]

Description: '
It is believed that GC hash table collisions would be substantially reduced if we changed the hash-key to XOR the hiloc in with the loloc to compute the key. This is a coordinated Lisp/microcode change for all three microcodes.'
'
-----'
'
Date': 26 Mar 84 16':37 PST'
From': vanMelle.pa'
...'
Ar 128.  Impact': may be minor.  There is no solid evidence to believe that this change to GC will have a major impact on gc hash table collisions.  Simulations might tell us.  If Attn': includes Charnley, it should also include JonL for the Dorado microcode.  Difficulty is easy, modulo the coordination among all the microcodes.  We''ve been saving this up for next time we need to make a coordinated change.Date': 11 May 84 14':58 PDT'
From': JonL.pa'
Subject': Re': performance problems on DLion'
In-reply-to': masinter.pa''s message of 11 May 84 12':08 PDT'
To': masinter'
cc': JonL, HThompson, vanMelle, Purcell, Charnley'
'
I remember this suggestion (the one in AR 128) being discussed shortly after I came here, so it''s been around for at least two years with no action on it.  I can''t but believe that it would help;  how much it would help is totally up for grabs.'
'
The suggestion is to begin hashing into the GC refcnt table with '
   (XOR (\HILOC X) (\LOLOC X)) '
rather than just '
   (\LOLOC X)'
which is currently used.  It would involve coordinated changes in the three microcodes, and would be a good candidate for inclusion the next round of such changes.'
'
-- JonL --'
'
P.S. A less "biased" computation would be 1''s complement addition mod 2^16; the ucodes could probably do this just by adding and branching on overflow (if overflow occurs, then they just add another 1 in).'
'
'
[I also believe that performance could be marginally improved by ** adding in, mod 2^16, ** the datatype number -- since large-unit datatypes tend to clump their references all at the beginning of an allocation unit. -- JonL 24-Sep-84]'


Workaround: 

Test Case: 

Edit-By: JonL.pa

Edit-Date: 24-Sep-84 03':55':47