Number: 819

Date: 23-Apr-84 17':25':06

Submitter: Sheil

Source: Sheil

Subject: Array allocation should Bucket free lists

Assigned To: Masinter

Attn: Release

Status: Fixed


Problem Type: Performance

Impact: Serious

Difficulty: Moderate

Frequency: Everytime

Priority: Absolutely

System: Language Support

Subsystem: Storage Formats/Mgt



Lisp Version: 

Source Files: 

Microcode Version: 

Memory Size: 

File Server: 

Server Software Version: 

Disposition: Mike': Pls cxheck to see if this is in the queue already and simply adjust the priorities, if it is - Beau'
["Masinter" " 5-Sep-84 12':34':08" Attn': Status':(Open->Fixed) Difficulty':(Hard->Moderate)]'
["Masinter" " 5-Sep-84 12':36':34" Assigned% To': Attn': Status':(Open->Fixed) Difficulty':(Hard->Moderate) Disposition': Edit-By': Edit-Date':]

Description: We have often talked about modifying the array allocator to bucket its free list by block size to prevent paging in huge amounts of array space whenever an allocation is required. It is my informal opinion that this problem has reached crisis proportions on small machines, given the number and diversity of subsystems that many users have running simultaneously. I beleive that we know what has to be done here and it''s just a question of doing it. At the very least this task should be reprioritized.'
Date': 27 Jul 84 15':47 PDT'
Subject': [': Array changes?]'
To': LispSupport'
cc': Kaplan'
Since I''m not gonna get to this right away, if there is an AR on bucketizing the array free list, could you add this? Otherwise, could you make such an AR? You can attn': Masinter, vanMelle, Kaplan if you like.'
     ----- Begin Forwarded Messages -----'
Date': 24-Jul-84 21':33':57 PDT'
Subject': Array changes?'
To': Masinter'
If you are really going in to work on the bucket scheme, there are 2 other things that I think ought to be done':'
1.  Pick off the case where NCELLS=1 and GCTYPE=UNBOXED and give back a (CREATECELL \FIXP).  No use having all the extra overhead words and fragmentation due to such small blocks when there already exists an MDS type that will do just as well.'
2.  Change the allocator to traffic internaly in quad-word block sizes.  I.e., (FOLDHI NCELLS CELLSPERQUAD) to begin with, and adjust the various constants and macros to do \ADDBASE4 instead of \ADDBASE2.  This will mean that the quad-word alignment won''t have to be enforced, and also that hasharrays (also double pointer arrays) can be twice as long.'
Number 1 is easy and cost-free.  2 is harder, maybe not for this time around, but if you feel ambitious and want to help hashing...'
     ----- End Forwarded Messages -----'


Test Case: 

Edit-By: Masinter

Edit-Date:  5-Sep-84 12':36':35