Number: 972

Date:  4-May-84 10':06':50

Submitter: Sannella.PA

Source: Denber.wbst

Subject: Need way to decrease fragmentation of array space (Space': The final frontier)

Lisp Version: 

Description: '
Date': 25 Apr 84 16':57 EST'
From': Denber.wbst'
Subject': Space': The final frontier'
To': trilliuminterest^.pa, Lispsupport.pa'
'
The time (25-Apr-84 16':41':58) has come, the Walrus said, to talk about storage management in Lisp and how it relates to Trillium.  I realize that the whole philosophy behind Lisp is to protect the user from all the ugliness of having to do their own storage management, but there comes a time when you simply *have* to.  We sort of started a discussion on this about a year ago, but nothing ever came of it.  Unfortunately the problem has not gone away and can be put off no longer.'
'
We have all see "arrays full" and out of space breaks in Trillium (and in animation too - anything that deals heavily in bitmaps).  GAINSPACE and RECLAIM do zip.  For starters, I would like to know how to make bitmaps vanish, I mean like really and truly gone, so if I had FOO is a 1024 x 808 bitmap, I can destroy it, then create another FOO the same size, and so on all day long.  Eventually, I''d like the ability to make entire Trillium dialogs (and all related data structures) disappear, as if they had never been loaded or run.  Is this possible?  Are there fragmentation issues here I''m not aware of?  Is it possible for mere mortals to understand Interlisp''s storage allocation mechanism?'
'
			BowingToTheWest,'
			- Michel'
'
-----'
'
From': MASINTER.PA'
Date': 26-Apr-84 23':56':25 PST'
Subject': Re': Space': The final frontier'
In-reply-to': Denber.wbst''s message of 25 Apr 84 16':57 EST'
To': Denber.wbst'
cc': trilliuminterest^, Lispsupport'
'
It is my conjecture that the problem is indeed fragmentation. It is probably no consoation that Trillium is not alone in this problem. '
'
Increasing virtual memory space (which we''re inching up to on the dandelion/1108) won''t help much -- the main problem is the lack of compaction for array space.'
'
A reliable array space compactor is hard only because many of the algorithms in Interlisp-D assume that pointers do not move.'
'
There is no short term fix in the works, unfortunately. '
'
The problem comes if you allocate a big bitmap, then let it go, then allocate a small one, and then want a big one back again. The space freed by the big bitmap gets eaten into by the small one. '
'
I suspect this is a problem which has been addressed in the literature or elsewhere, and I''m just not familiar with the solution...'
'
Does this suggest any way you can program around the problem?'
'
-----'
'
Date': 27 Apr 84 10':45 EST'
From': Denber.wbst'
Subject': Re': Space': bitmaps'
In-reply-to': MASINTER.PA''s message of 26-Apr-84 23':56':25 PST'
To': MASINTER.PA'
cc': Denber.wbst, trilliuminterest^.PA, Lispsupport.PA'
'
Would this work?  When you first start up a system, create the biggest bitmap you can that uses all available space for bitmaps (is it true that there is a fixed portion of storage reserved for bitmaps, or can "bitmap" space expand into "string space" if needed?).  Then maintain your own bitmap allocator.  You could bitblt to and from the screen out of the appropriate areas of this pool according to your "bitmap" names (actually pointers to offsets in the large bitmap).  Thus only one real bitmap would ever be created.'
'
Of course this is just a kludge - considering how important graphics are in Interlisp-D, I would like to cast a vote for enhancements in this direction.'
'
			- Michel'
'
-----'
'
From': masinter.pa'
Date': 28-Apr-84 14':35':19 PST'
Subject': Re': Space': bitmaps'
In-reply-to': Denber.wbst''s message of 27 Apr 84 10':45 EST'
To': Denber.wbst'
cc': MASINTER, trilliuminterest^, Lispsupport'
'
sorry, nice try. However, you didn''t solve the problem, you just moved it. The problem is that the current Lisp storage allocator doesn''t do well with a particular pattern of usage. You propose self-management of storage, which wouldn''t make things any better; the problems are merely shifted to the ''kludge'' allocator.'
'
-----'
'
Date': 30 Apr 84 12':06 EDT'
From': Denber.wbst'
Subject': Re': Space': bitmaps'
In-reply-to': masinter.pa''s message of 28-Apr-84 14':35':19 PST'
To': masinter.pa'
cc': trilliuminterest^.pa, Lispsupport.pa'
'
Hmm - well maybe there''s something I really don''t understand here - perhaps you could say more.  Suppose I do'
'
(SETQ BITBUF (BITMAPCREATE 128 128))'
'
(In practice, I would want this to be as big as I can make it).  Now let''s say I want four "pseudo-bitmaps" of 64 x 64.  I set up a pointer table containing (P1 (0 0 64 64)) (P2 (63 0 64 64)) (P3 (0 63 64 64)) (P4 (63 63 64 64)) where each entry is a name and a region inside BITBUF.  Whenever I want a Pn, I say (BITBLT BITBUF ...) with the appropriate region.'
'
Now say I no longer need P1 - 4, but I want Q to be a new 128 x 128 bitmap.  Why can I not just replace my pointer table with one new entry (Q (0 0 128 128))?  As far as Lisp is concerned, I haven''t created or deleted any real bitmaps.  I haven''t asked Lisp for any new space, only changed the way *I* look at already allocated space.  The storage for FOOBUF should still all be where it was when it was created, no?  Are you saying that bitmaps will fragment even at this level?  Now I''m *really* confused.'
'
			- Michel'
'
-----'
'
Date': 30 Apr 84 14':55 PDT'
From': masinter.pa'
Subject': Re': Space': bitmaps'
In-reply-to': Denber.wbst''s message of 27 Apr 84 10':45 EST'
To': Denber.wbst'
cc': MASINTER.PA, trilliuminterest^.PA, Lispsupport.PA'
'
apparently, there ARE a number of planned improvements to the storage manager which I was unaware of, some of which will help with running out of array space in the general case and with yours in particular. The priority of incorporating them in the system has been bumped up... watch this space.'
'
-----'
'
From': Koomen.Wbst'
Date':  2-May-84  3':26':44 EDT'
Subject': Re': Space': bitmaps'
In-reply-to': Denber''s message of 30 Apr 84 12':06 EDT'
To': Denber'
cc': masinter.pa, trilliuminterest^.pa, Lispsupport.pa'
'
Your suggestion to create a BITBUF and setting up a pointer table containing "pseudo-bitmaps" unfortunately is unworkable.'
First of all, as Larry pointed out, you have merely shifted the problem to a higher level. You fooled yourself in thinking it a solution by using ''nice'' numbers. Suppose however that your BITBUF is really 32K x 32K, and you have ''allocated'' some 400 ''pseudo-bitmaps'' in it. Now you want to drop 23 of them. What will you do with the 23 little spaces inside BITBUF? Reallocate? How? This is exactly the problem of the current array allocator, except that it has the benefit of the low level microcode support, and the various typing data structures, where as your system uses long ALISTS chewing LISTP''s etc!!! Any space improvements you might gain by your allocation algorithm will be more than offset by the speed loss implementing it. The only solution is the improve the current allocator''s algorithm.'
'
From Larry''s comments I gather that the allocator uses a first-fit scheme, i.e.whenever a request for bitmap space of size b bits comes in it is allocated from a ''hole'' of size h containing at least b. The fragmentation comes from being left with a smaller hole of size h-b. Eventually you will end up with a whole bunch of these little holes, each to small to be used but together wasting a significant chunk of memory. The most optimal algorithm (spacewise) would be to move all bitmaps in use to one side of the memory, effectively munging all the little holes into one big hole at the other end of memory. But, again as Larry said, that implies that objects may move, making pointers to obsolete. Which requires a entire system redesign!.'
A second way to do it would eb to use best-fit allocation.'
Oops, emergency! Talk to you later!'
'
-----'
'
Date':  9 May 84 10':59 EDT'
From': Denber.wbst'
Subject': Re': Space': bitmaps'
In-reply-to': Koomen.Wbst''s message of 9-May-84  0':31':51 EDT'
To': Koomen.Wbst'
cc': Denber.Wbst, masinter.pa, trilliuminterest^.pa, Lispsupport.pa'
'
Well congratulations on the new arrival!  As far as bitmap allocation - I realize that doing your own storage management does not make fragmentation go away, but it does let you deal with it in a more reasonable manner than going into Raid.  Allocate whatever way you like - first-fit, best-fit, snit-fit, binary buddies, whatever, the important thing is to have a reclamation phase.  The pointers move, sure - that''s part of the compacting process.  I never claimed it to be a trivial problem (in fact it''s bin-packing) but nothing you mentioned precludes doing it.  Using bitmaps this way would be slower, but isn''t that better than having your system stop entirely?'
'
Larry, you mentioned that some improvements are planned in this area - can you be a little more specific (like what & when)?  I won''t bother with a work-around if a real fix is imminent.  Thanks.'
'
			- Michel'
'
-----'
'
Date':  9 May 84 00':01 PST'
From': Halvorsen.pa'
Subject': Lisp': Running out of arrayspace, storage leak & windows/menus?'
To': LispSupport.pa'
cc': Halvorsen.pa'
'
Lisp System Date':  6-May-84 20':31':11'
Machine': Dorado (Ahwahnee)'
Microcode version': 24,4'
Memory size': 10000'
Frequency': Always'
Impact': Serious'
'
I tend to run out of arrayspace quite often.  I hunting for the problem I found that some of the windows I create myself are left hanging around,  but I also see that lots of menus, both mine and some from Lafite, Dedit etc are returned when I do (\COLLECTINUSE ''WINDOW) as are some inspector windows, scrollbars etc. etc.).  I also find my old message composition windows in this list.'
'
-----'
'
From': KAPLAN.pa'
Date':  9-May-84 16':54':26 PDT'
Subject': RAID on arrays full error'
To': Lispsupport, Masinter, Burton'
cc': Jellinek'
'
I will send something to Denber, when I have time.  It still seems to me that he is confused about what is going on--he still seems to believe that arrays aren''t being collected if he drops all pointers to them.'
'
But he raises another point, which is that the system goes into RAID when the arrays full error comes up.  I believe that this is because the window break package is attempting to open a break window, and space can''t be found.'
'
I believe we have discussed this before, but I don''t remember whether we decided what the fix should be.  Should WBREAK be fixed to use TTY break instead on an arrays full error (and perhaps storage full also)?  Or should the array allocator be fixed so as not to cause that error--to printout out a simple message to the TTY window and then do a reset, or else directly call the TTY break machinery without going thru error.'
'
The semantics of errors and errortypelst suggest that WBREAK be fixed, but I''m not religious on this.'
'
--Ron'
'
-----'
'
Date': 10 May 84 10':41 PDT'
From': Burton.pa'
Subject': Re': RAID on arrays full error'
In-reply-to': KAPLAN.pa''s message of 9-May-84 16':54':26 PDT'
To': KAPLAN.pa'
cc': Lispsupport.pa, Masinter.pa, Jellinek.pa'
'
I changed the break package to go to great lengths to not use any space after an arrays full error.  I don''t believe this is causing Denber''s RAID calls (if he is running fugue.6 or later).  I think he is referring to RAID as generic can''t do anything else condition.  Please let me know if the break package puts you in RAID.'
'
richard'


Workaround: 

Test Case: 

Edit-By: Sannella.PA

Edit-Date: 10-May-84 12':25':07

Attn: Kaplan, Lisp

Assigned To: 

In/By: 

Disposition: [7 May, changed Attn': to Kaplan, changed System/Subsystem to Language/Storage]

System: Language Support

Subsystem: Storage Formats/Mgt

Machine: 

Disk: 

Microcode Version: 

Memory Size: 

File Server: 

Server Software Version: 

Difficulty: Very Hard

Frequency: Everytime

Impact: Serious

Priority: Absolutely

Status: Open

Problem Type: Performance

Source Files: