Number: 1060

Date:  9-May-84 14':59':51

Submitter: masinter.PA

Source: HThompson.pa

Subject: GC collision table filling up in long-running program?

Assigned To: 

Attn: JonL, Masinter

Status: Open

In/By: 

Problem Type: Performance

Impact: Serious

Difficulty: Hard

Frequency: Everytime

Priority: Perhaps

System: Language Support

Subsystem: Storage Formats/Mgt

Machine: 1108

Disk: 

Lisp Version: 

Source Files: 

Microcode Version: 

Memory Size: 

File Server: 

Server Software Version: 

Disposition: '
["JonL.pa" "24-Sep-84 03':37':56" Description':]'
["JonL.pa" "24-Sep-84 03':56':50" Description':]

Description: '
'
Date':  9 MAY 84 09':35 PDT'
From': HTHOMPSON.PA'
Subject': timings'
To':   Masinter'
'
Well, it''s pretty weird.'
First of all the problem of slow degradation is real, and'
not attributable to page faulting (as observed in the cursor and'
measured with (PAGEFAULTS).'
'
Over a period of about 30 minutes of continuous re-execution, the'
poerformance of my chart parser degraded from 3.1 seconds for a particular'
parse, to nearly 9 seconds, and when loaded into a completely clean sysout,'
it took only 2.1 seconds.'
All of these timings were with 0 pagefaults, and approx. 4000 conses.'
The code involved does build some circular structures.'
'
The timing degradation is quite bizarre in detail - the following is a copy'
of the notes I made as it ran continuously':'
<the first part of this does not record every run, just samples>'
'
(All timings in 10ths of a second)'
(All timings are from (CLOCK 2) which seems reasonably accurate, and'
insignificantly different from (CLOCK 0) except when large amounts of'
GC or swapping are involved)'
'
Time	Time	Swaps if any	GC'
31	4'
'
<10 minute interval>'
'
46	0'
50	'
64'
54'
44'
61'
'
<10 minute interval>'
'
60'
67'
67'
73'
72'
68	32	yes'
67'
63'
66	29'
'
<5 minute interval>'
'
79'
81'
'
<10 minute interval>'
<from here on I recorded every run>'
'
79'
82'
78'
86	20'
86	8	yes'
75'
76'
80'
100	33	yes'
76'
81'
82'
91	8'
100	29	yes'
83'
76'
82'
90	16'
94	22	yes'
83'
76'
77'
89	22	yes'
'
As the last section shows, there is some, albeit incomprehensible,'
pattern to the process.  After a g.c. things speed up a bit, then'
usually but not always get steadily worse, until we get some swapping activity and then immediately another g.c.'
'
I will gladly take any further measurements you think might'
help - alas I cannot do a DOSTATS...'
Cheers'
ht'
'
'
'
Date': 11 May 84 01':06 PDT'
From': JonL.pa'
Subject': Re': performance problems on DLion'
In-reply-to': masinter.PA''s message of 9 May 84 15':01':31 PDT (Wednesday)'
To': masinter.PA'
cc': HThompson.PA, jonl.PA'
'
This looks exactly like a problem I ran into when doing some of the "consy" benchmarks with Dick Gabriel':  The GC hash table becomes "impacted", and as time goes by, the time spent in reference-counting (which is rather pervasive) goes up significantly.'
'
I added a function, \#COLLISIONS, to the GCHAX file some time ago to be able to predict this problem without running STATS.  No args; result is a 3-list of # of GC hash table entries, # of entries in collision chains, and the ratio of these two #''s.'
'
I''ve watched this ratio vary between 5% and 35%, and seen some benchmarks slow down by a factor of 2.  Henry''s reports suggests that a factor of 3 is even possible.  Henry': would you like to try again, dribbling out calls to \#COLLISIONS every time you are about to time a run?'
'
-- JonL --'
'
'
[There have been suggestions to improve the gcRefcnt hashtable performance by xor''ing in the hiloc of the pointer being "refcnt"''d; I''d rather suggest *adding* in the hiloc (mod 2^16) as well as adding in the datatype number.   See also AR 128.    -- JonL -- 24-Sep-84]'


Workaround: 

Test Case: 

Edit-By: JonL.pa

Edit-Date: 24-Sep-84 03':56':50