Number: 1440

Date: 14-Jun-84 16':42':41

Submitter: Sannella.PA

Source: JonL.pa

Subject: Increase max # litatoms above 32K

Assigned To: 

Attn: jonl, masinter, lisp

Status: Open

In/By: 

Problem Type: Performance

Impact: Fatal

Difficulty: Hard

Frequency: Everytime

Priority: Perhaps

System: Language Support

Subsystem: Storage Formats/Mgt

Machine: 

Disk: 

Lisp Version: 

Source Files: 

Microcode Version: 

Memory Size: 

File Server: 

Server Software Version: 

Disposition: '
["Sannella.PA" "21-Aug-84 11':44':47" Description':]'
["Sannella.PA" "28-Aug-84 09':56':07" Description':]'
["JonL.pa" " 4-Sep-84 21':44':20" Priority':(Absolutely->Perhaps)]'
["Sannella.PA" "11-Sep-84 10':19':13" Description':]'
["Sannella.PA" "25-Sep-84 12':58':03" Subject': Description':]

Description: '
Date':  3 Jun 84 23':11 PDT'
From': Jonl.pa'
Subject': FOO -- still the biggest loser in the world'
To': LispCore^.pa'
cc': Jonl.pa'
'
Mitch Model''s recent note to LispSUpport emphasizes the problems we have with litatoms -- '
  1) the limit of 32K is too small'
'
...'
With respect to point (1) -- we do have a reasonable scheme to go to a 64K limit; it involves modifying all the ucodes in a non-trivial way, because with the larger limit on atom indices the defspace and valspace cells are no longer contained within one segment (and ucode needs more ''cycles'' to do segment carry-across).'
'
...'
'
-----'
'
'
Return-Path': <MMODEL@BBNG.ARPA>'
Received': from BBNG.ARPA by Xerox.ARPA ; 03 JUN 84 18':03':02 PDT'
Date': 3 Jun 84 21':02 EDT'
Sender': MMODEL@BBNG.ARPA'
Subject': Re': Efficiency Hacks?'
From': MMODEL@BBNG.ARPA'
To': LispSupport.pa'
Cc': GREENFELD@BBNG.ARPA, WWoods@BBNG.ARPA'
Message-ID': <[BBNG.ARPA] 3-Jun-84 21':02':28.MMODEL>'
In-Reply-To': The message of 23 May 84 16':47':26 PDT (Wednesday) from LispSupport.pa@XEROX.ARPA'
'
Continuing previous discussion':'
'
We are building a LARGE system and are exploring a variety of'
efficiency issues.  We find that the system spends a great deal'
of time swapping (with 1.5 mb memories and Dolpins or Dandelions'
with the small disk).  As the system nears its limit (6 mbyte),'
it thrashes more and more.  Running with VMEMSIZE about 10K we'
often see 80% swap time.  One of our problems is a lot of atom'
names (app.  30K)': our subjective impression is that atom hashing'
is slow and responsible for a great deal of our system''s'
sluggishness.  We are also worried about exceeding the'
implementation''s limit on atoms.  (We understand it is 32K and we'
probably will exceed that.)'
'
So, we are looking for ways to reduce the number of atoms or'
improve paging performance.'
'
Does MAKESYS do anything useful in INTERLISP-D?  Is there a way'
to preload atoms to improve paging performance by getting the'
hash table data structures onto fewer pages?  Are there any plans'
to improve atom representation, the hashing algorithms, or paging'
mechanisms?'
'
Will block-compilation buy us anything?'
'
        --- Mitchell'
'
-----'
'
Sender': Sannella.PA'
Date':  4 Jun 84 17':12':29 PDT (Monday)'
Subject': Re': Efficiency Hacks?'
In-reply-to': <[BBNG.ARPA] 3-Jun-84 21':02':28.MMODEL>'
To': MMODEL@BBNG.ARPA'
cc': LispSupport, GREENFELD@BBNG.ARPA, WWoods@BBNG.ARPA'
From': LispSupport.pa'
Reply-To': LispSupport.pa'
'
"As the system nears its limit (6 mbyte),it thrashes more and more." --- What do you expect?  As the working set increases, you have to spend more time swapping to access all of the data scattered throughout the vmem.  If it is indeed true that you are using all of this information, there isn''t much that you can do (except get more real memory).  However, in most cases, it is possible to reduce the working set, by being careful to release pointers to objects no longer needed.  Have you tried using the GCHAX lisp library package?  This provides a few functions for groveling around the vmem, detecting garbage that shouldn''t be saved.'
'
"our subjective impression is that atom hashing is slow and responsible for a great deal of our system''s sluggishness."  ---  Possibly true, if you have a lot of atoms.  So the question becomes': do you really need to represent so many things as atoms?'
'
"We are also worried about exceeding the implementation''s limit on atoms.  (We understand it is 32K and we probably will exceed that.)"  ---  You are correct; the limit is 32K atoms.  There is a proposal around for extending it to 64K.'
'
"Does MAKESYS do anything useful in INTERLISP-D?"  --- as the manual says (p 14.4), it is just like SYSOUT, except that it also does some cleaning-up operations (like clearing the screen), so it probably won''t help you.'
'
"Is there a way to preload atoms to improve paging performance by getting the'
hash table data structures onto fewer pages?" --- not that I know of.  You might try experimenting with various methods of loading up your system, and take measurements.'
'
"Are there any plans to improve atom representation, the hashing algorithms, or paging mechanisms?"  ---  There are always plans around for increasing performance in various ways, but it is hard to do this without tearing the low-level system apart, so we have to be careful.'
'
"Will block-compilation buy us anything?" --- all block-compiling can do for you in Interlisp-D is to prevent naming conflicts, by automatically renaming functions internal to a block.  There is no performance advantage.'
'
-----'
'
Date':  5 JUN 84 20':36 PDT'
From': MASINTER.PA'
Subject': atoms etc.'
To':   MModel@bbng, greenfeld@bbng, wwoods@bbng, lispsupport'
'
In most Lisp implementations, atoms are not very efficient for representation structures. They *are* convenient, of course. I take it that most of your symbols are gensyms of some sort? '
'
I think there is some hope for slight improvements in the atom hash algorithm. I don''t think that will help with your thrashing problem. GCHAX and COREHAX are pretty poor tools for figuring out what is going on, but they''re the best we have right now.'
'
There will be a new performance analysis tool, called SPY, which should help in determining whether in fact your system is spending any appreciable amount of time doing atom hashing.'
'
If COREHAX doesn''t say how much of your workingset is due to atom pnames and symbol table, maybe I can fix it to.'
'
I''ve found using SPY that my intuitions about where the system is spending its time have often been wrong...'
'
If you still can''t figure out what is happening, maybe you could ship a SYSOUT with some instructions on what to run to get some typically bad behavior? '
'
Larry'
'
-----'
'
Date':  5 Jun 84 21':36 PDT'
From': JonL.pa'
Subject': Re': Efficiency Hacks?'
In-reply-to': LispSupport.pa''s message of 4 Jun 84 17':12':29 PDT (Monday)'
To': LispSupport.pa'
cc': JonL.pa'
'
If Mitch Model''s conjectures are true, then we have a a few more good reasons to proceed with the extension to litatom capabilities in Interlisp-D.  I have three main points to make, the second of which is rather lengthy, so I''ll warn you in advance':'
   1) How to find out how many litatoms your sysout has'
...'
1) They think that they have about 30000 litatoms -- how do they know?  Currently, the value of the variable \AtomFrLst (minus about 1) will be the number of litatoms created in a given sysout.  As we are all aware, Interlisp-D has no mechanism for reclamation of "dead" litatoms.  If they are approching this limit, then they will be the third *** major *** AI project which recently had to undertake a serious revision of implementation, due solely to the limit on litatoms (i.e., litatoms are the "natural" structure wanted, and the projects converted only after bumping into the hard limit).'
'
...'
'
 -----'
'
Return-Path': <GREENFELD@BBNG.ARPA>'
Received': from BBNG.ARPA by Xerox.ARPA ; 07 JUN 84 04':48':03 PDT'
Date': 7 Jun 84 07':46 EDT'
Sender': GREENFELD@BBNG.ARPA'
Subject': Re': atoms etc.'
From': GREENFELD@BBNG.ARPA'
To': MASINTER.PA'
Cc': MModel@BBNG.ARPA, wwoods@BBNG.ARPA'
Cc': lispsupport.PA'
Message-ID': <[BBNG.ARPA] 7-Jun-84 07':46':38.GREENFELD>'
In-Reply-To': The message of 5 JUN 84 20':36 PDT from MASINTER.PA@XEROX.ARPA'
'
Larry, we''re going to minimize our use of atoms, but in fact we'
don''t have that many gensyms.  I''ll get the numbers later, but an'
initial Fugue.6 loadup starts with some 5-6 thousand atoms; add a'
few packages (such as singlefileindex, etc) and Loops, and you''re'
up another few thousand or more.  Our code adds quite a few (and'
the use of Loops adds many).  I''m not sure whether we can really'
use many fewer, unless there''s a way to either get rid of atoms'
completely, or have the compiler put out fewer.  I think you''d'
find the list of atoms in the startup system releases'
interesting.'
'
When is SPY going to be available to us folks out in the world?'
We''d love to use it.  (I''ve heard a little about it)'
'
Norton'
'
'
(I''ll be out there tomorrow talking to Beau and the TEdit folks -'
perhaps we can say hello)'
'
-----'
'
Date':  7 Jun 84 13':59':17 PDT (Thursday)'
From': Masinter.PA'
Subject': Re': atoms etc.'
In-reply-to': <[BBNG.ARPA] 7-Jun-84 07':46':38.GREENFELD>'
To': GREENFELD@BBNG.ARPA'
cc': MASINTER, MModel@BBNG.ARPA, wwoods@BBNG.ARPA, lispsupport'
'
um, 5-6 thousand in the system plus another 5-6 thousand would make still around 12 thousand, which is less than half the total. Are you really close to running out?'
'
Spy is going to be included in Carol.'
'
-----'
'
Date':  7 Jun 84 15':23 PDT'
From': JonL.pa'
Subject': Re': atoms etc.'
In-reply-to': GREENFELD@BBNG.ARPA''s message of 7 Jun 84 07':46 EDT'
To': GREENFELD@BBNG'
cc': MASINTER.PA, MModel@BBNG, wwoods@BBNG, lispsupport.PA'
'
A Full.sysout here starts with over 18000 litatoms; I''m surprised that a Fugue.6 Lisp.Sysout only has 5 or 6 thousand.  Reminder': look at value of \AtomFrLst to see how many atoms exist.'
'
On the other hand, Loops is an exceptionally bad offender in the creation of litatoms; Danny just yesterday sent a note to LoopsCore^ mentioning that he will probably go ahead with the plan to flush litatoms entirely from use as unique IDs, using only strings.  That should free up lots of litatom space for Loops users.'
'
It is true, as Norton suggested in a note to me, that as an application begins to near the "stretching" limits of Interlisp-D, there will likely be more than one crack in the dike.  Array space fragmentations is one known source of highly-variable timing instability;  Main Data Space may also enter the picture, but we haven''t monitored that.  SPY itself is of no help in tracking these things down, but a program written along similar lines (i.e., "Monte-Carlo-like" sampling, driven off the 1/60''th second keyboardHandler interrupt) could help provide a picture of dynamic pageing rate, and what the cause might be.'
'
-- JonL --'
'
-----'
'
Date': 28 Jun 84 16':51 EDT'
From': Koomen.wbst'
Subject': Lisp': atoms'
To': LispSupport.pa'
cc': Koomen.wbst'
Lisp-System-Date': 25-Jun-84 13':07':37'
Machine-Type': Dandelion'
'
A number of times I have run into a problem with litatoms, or rather, I suspect, with running out of space for them. Just now even while I was trying to send this message! Each time the system freezes up entirely, except for mouse tracking. The only way I could do anything was by CTRL-H then interrupting the MOUSE process.  Each time the system was interrupted below MKATOM,which had some very strange looking arguments (like {}#n,nnnnn)  And about the only thing to do is to reboot and start over. Very anoying. '
If only Interlisp-D would GC atoms like Interlisp-Vax does...'
'
-----'
'
mjs 6/29'
'
Subject': Re': Lisp': atoms'
In-reply-to': Koomen.wbst''s message of 28 Jun 84 16':51 EDT'
To': Koomen.wbst'
cc': LispSupport.pa'
From': LispSupport.pa'
Reply-To': LispSupport.pa'
'
There are two problems here':'
'
(1)  System loops in MKATOM when it runs out of atoms.'
'
This problem will be fixed in the next release.  The system will cause an error when atom space gets low, and go into RAID when there are no more atoms left.'
'
(2)  System has rigid limits on max # atoms, and it doesn''t GC atoms.'
'
This is a serious problem, as more and more people run into the atom limit.  In the short term, it should be possible to increase the max number of litatoms.'
'
In the mean time, all that I can suggest is that you examine your programs, and see if you are creating atoms unnecessarily.'
'
-----'
'
Return-Path': <SHULMAN@RUTGERS.ARPA>'
Received': from RUTGERS.ARPA by Xerox.ARPA ; 20 AUG 84 17':19':54 PDT'
Date': 20 Aug 84 20':18':35 EDT'
From': Jeffrey Shulman <SHULMAN@RUTGERS.ARPA>'
Subject': Atom space'
To': lispsupport.pa'
cc': SHULMAN@RUTGERS.ARPA'
'
'
	We have run out of atom space.  Is there anything we can do'
about it?'
'
						Jeff'
'
-----'
'
Date': 20 Aug 84 19':44 PDT'
From': JonL.pa'
Subject': Re': Atom space'
In-reply-to': Jeffrey Shulman <SHULMAN@RUTGERS.ARPA>''s message of 20 Aug 84 20':18':35 EDT'
To': SHULMAN@RUTGERS'
cc': lispsupport.pa, LispCore^'
'
Re what to do when you run out of litatoms (as you recently did)':   Sometimes users who GENSYM a lot find they can substitute STRINGPs for the random litatoms.  But if this isn''t feasible for you, then I suggest that you  bug LispSupport/LispCore^ to implement 64K litatoms -- current limit is 32K, and going to 64K is a relatively minor leap. [Doing it "right" might be more of a leap -- see below].'
'
I''d be curious to know how many litatoms your application needs.  E.g., right now, in a FULL.SYSOUT (with Tedit, Lafite, etc loaded), there are only about 12000 litatoms available for the user; but with 64K litatoms, there would be closer to 46K available for the user, which is a 4-fold increase.  Would that help?'
'
--------------------------------------'
Implementational consequences of "a relatively minor leap"':'
--------------------------------------'
'
1) ucode changes -- an extra ''tick'' in functional call and globalvar fetch, to account for doubling an index which can be as bit as 16-bits to start with; '
'
2) an adverse effect would be to "eat out" more segments of virtual address space for the definition cells and top-level value cells, but previous statistics show that not increasing pnamechars space might be OK.'
'
3) statistics taken recently point out that less than 4% of litatoms have more than one kind of "cell" (DEF cell, PLIST cell, or VAL cell); makes a good argument for multiplexing a single "cell" for litatoms, rather than arbitrarily reserving 3 such cells.  Also makes a good case for allocating litatoms as a record structure out of Main data space.'
'
-- JonL --'
'
-----'
'
Return-Path': <SHULMAN@RUTGERS.ARPA>'
Redistributed': LispCore^.pa'
Received': from RUTGERS.ARPA by Xerox.ARPA ; 21 AUG 84 06':30':45 PDT'
Date': 21 Aug 84 09':30':34 EDT'
From': Jeffrey Shulman <SHULMAN@RUTGERS.ARPA>'
Subject': Re': Atom space'
To': JonL.pa'
cc': lispsupport.pa, LispCore^.pa'
In-Reply-To': Message from "JonL.pa@XEROX.ARPA" of 20 Aug 84 22':44':00 EDT'
'
'
	We would be very much in favor of 64K atom space (if not larger.)'
Our VLSI design system is pushing up against the limits of Interlisp-D.'
'
							Jeff'
'
-----'
Return-Path': <SHULMAN@RUTGERS.ARPA>'
Redistributed': LispCore^.pa'
Received': from RUTGERS.ARPA by Xerox.ARPA ; 21 AUG 84 07':40':10 PDT'
Date': 21 Aug 84 10':39':55 EDT'
From': Jeffrey Shulman <SHULMAN@RUTGERS.ARPA>'
Subject': Re': Atom space'
To': JonL.pa'
cc': lispsupport.pa, LispCore^.pa'
In-Reply-To': Message from "JonL.pa@XEROX.ARPA" of 20 Aug 84 22':44':00 EDT'
'
'
	Is there any way to garbage collect unneeded atoms?'
'
							Jeff'
-------'
'
Date': 21 Aug 84 17':12 PDT'
From': JonL.pa'
Subject': Re': Atom space'
In-reply-to': Jeffrey Shulman <SHULMAN@RUTGERS.ARPA>''s message of 21 Aug 84 10':39':55 EDT'
To': SHULMAN@RUTGERS'
cc': JonL.pa, lispsupport.pa, LispCore^.pa'
'
NIL.'
'
This would unfortunately require a significant amount of development.  Since reference counts are not maintained for litatoms (and we probably don''t want to change that), then a stop-and-copy kind of GC would be the best hope.  Incidentally, we do want to write a stop-and-copy, in order to solve two other problems of refcnt''ing GC': (1) to reclaim circular structures, and (1) to compactify a fragmented memory.'
'
-- JonL --'
'
-----'
'
Date': 10 Sep 84 15':43 PDT'
From': hihn.pasa'
Subject': Atom names and Hash Table'
To': masinter.pa'
cc': 1100support, hihn.pasa'
'
Rick Martin suggested I drop you a line to confirm the solutions to be recommended to the problems described below.  Thank you for your assistance.'
'
Shaul Markovich from the University of Michigan has an application which generates an unusually large number of atoms.  After several days of hacking the system begins to slow down. Many of these atoms have the same prefix to their name.  Assuming  he is not running out of array space the only solution we have come up with is that he should use GENSYM to generate atom names. '
'
Furthermore he claims that the hash function (?) requires 80 jumps to find an open spot in the hash table which is related to using so many similair atom names.  The solution , along with changing the names ,is to do CLEARHASH regularly since HASH is not garbage collected.'
'
Thanks again.'
'
Jairus'
'
-----'
'
Date': 10 Sep 84 19':04 PDT'
From': masinter.pa'
Subject': Re': Atom names and Hash Table'
In-reply-to': hihn.pasa''s message of 10 Sep 84 15':43 PDT'
To': hihn.pasa'
cc': LispSupport, 1100support.pasa'
'
the "atom hash table" cannot be cleared.'
'
Using GENSYM will not help his problem. '
'
Not using Atoms probably will. Can you find out more about his application and the way in which it uses atoms?'
'
In Interlisp-D, litatoms are (currently) a fixed finite resource, and programs that generate lots of atoms don''t do as well as their implementors expect.'
'
In most of the implementations I''ve looked at, there isn''t much about "atom"ness that is being exploited, e.g., they might use a datatype with fixed fields or a property list without the atom around, etc.'
'
We want to fix our atom allocation scheme to do better even for applications like Shaul''s, but it will not happen in time for Harmony.'
'
'


Workaround: 

Test Case: 

Edit-By: Sannella.PA

Edit-Date: 25-Sep-84 12':58':04