[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: MAPHASH problems in Interlisp??
- To: Vittal Kini <KINI at USC-ISIB>
- Subject: Re: MAPHASH problems in Interlisp??
- From: Masinter at PARC-MAXC
- Date: Mon, 01 Mar 1982 14:11:31 -8000
- Date: 1 Mar 1982 13:09 PST
- Cc: InterlispSites^
- In-reply-to: KINI's message of 23 Feb 1982 1604-PST
(I'm cc:ing InterlispSites^ on the response because this problem is not widely
(1) You have unfortunately run into one of the more subtle problems with
MAPHASH in Interlisp-10: if a garbage collection which MOVES STORAGE
occurs during the middle of a MAPHASH, it is possible for the hash
pointers to move around, and for entries to be missed and for some entries
to be visitied twice. This is the only situation in which MAPHASH will
omit items or present them twice (note that "rehashing" actually copies the
original array into another one, so that if a rehash occurs because of overflow,
you may get outdated information but not any duplicates.)
(2) The problem is that if a reclaim needs to increase the size of one of the
contiguous areas (such as array space or string pointer space), it may actually
move around pages of atoms. It isn't that atoms get compacted but rather that
other spaces have to increase which causes the atoms to get moved around.
(3) The way that I worked around this problem when I ran into it was
(a) MAPHASH down the array, collecting a list of the "keys"
(b) MAPC down that list, performing the operation
This guarantees that no string/array/pname garbage collection will occur during
There are some proposals for fixing this problem in Interlisp-10 (e.g., marking the
array that it is being maphashed, and if so marked, not rehashing during a
reclaim but fixing it the next puthash) but so far (for the last 4 years) no
progress on fixing it.
This bug is not present in other Interlisp implementations, as far as I know.