[gclist] Re: finding object prefix from infix pointer

Francois-Rene Rideau fare@tunes.org
Fri, 9 Jul 1999 14:51:02 +0200

On Fri, Jul 09, 1999 at 02:15:40PM +0200, marc.shapiro@inria.fr wrote:
> I'm interested in a discussion of the alternatives: this is a costly
> operation.

>[Proposed possibly hierarchical bitmaps]

> Sorry, these acronyms (BIBOP, BLOB, BSOB) are unfamiliar to me. Could you
> explain?
BIBOP is BIg Bag of Pages.
It means that you group objects of same kind by pages,
and differentiate them according to their address.
If the "kind" of an object includes its size,
and you have known alignments depending on size,
then you may easily deduce the start of an object from its address.
In the general case, BIBOPs require some structure to be maintained
in parallel with the hardware mapping table to associate data to pages.
I know BIBOPs have been in use since the seventies.
It could be considered that statically wiring object kinds
into address ranges (technique used in emacsen of old) be
a degenerate form of BIBOPs that have been statically partially evaluated.

"BLOB" means "Binary Large OBject". Name used by database people
for such things as pictures and sound embedded among the data in the base.
When you have BLOBs, you just can't scan them down to find a header marker,
because they are large, and may contain arbitrary bit patterns as data.

"BSOB" is a term I just coined to oppose BLOB: "Binary Small OBjects".
Binary objects have no reason to be particularly large.
Typically, floating-point numbers, bignums, or long fixnums
(hint: money accounts), or just text strings (which in non-US country
isn't limited to ASCII) are as many small binary objects.
Because of their arbitrary bit patterns, you just can't use the suggested
"scan down until I find a header" tactic, even though they be small.

As to avoiding the cost of chasing infix pointers rather than paying it
("mieux vaut prévenir que guérir"), has anyone studied the feasability
to have existing compiler backends (e.g. GCC)
output proper "recovery" information together with the code they spit?
Maybe someone from the C-- projects (do they still exist?)?

Years ago (my! what have I been doing all that time?),
I proposed the use of such recovery code
to dynamically achieve safe-points needed for multithreaded GC
without having to pay for contorting tight loops and polling regularly.
I have recently stumbled on a nice general theory of code recovery
as a "soundness" property of multithreaded implementations,
while formalizing the notion of implementation in its most generic meaning.
Has anyone heard about similar works?

Best regards,

[ "Faré" | VN: Уng-Vû Bân | Join the TUNES project!   http://www.tunes.org/  ]
[ FR: François-René Rideau | TUNES is a Useful, Nevertheless Expedient System ]
[ Reflection&Cybernethics  | Project for  a Free Reflective  Computing System ]
(Meta)Ignorance is not being able to distinguish hype from information.