From: niklas@appli.se (Niklas Hallqvist)
Newsgroups: comp.lang.c++
Subject: Re: Doubly-linked list trick (was Re: Garbage Collection for C++)
Date: 19 Aug 92 19:29:37 GMT
Organization: Applitron Datasystem AB, GOTHENBURG, SWEDEN

tmb@arolla.idiap.ch (Thomas M. Breuel) writes:

:In article <2134@appli.se> niklas@appli.se (Niklas Hallqvist) writes:

:   Emphasises mine!  This means the trick WILL be portable to all platforms
:   where there exists an integral type large enough (ie. almost all platforms).
:   I agree that this may be a bad habit, BUT... what I wanted to tell was:
:   It's REAL HARD (read: impossible) to implement GC on most architectures if
:   this rule [allowing conversions of pointers to/from integers] is left in.

:No, it's not at all hard. Since C++ programs that rely on
:integer/pointer conversions are already unportable, a very small
:number of these already unportable programs would simply be unportable
:to a larger number of implementations.

Excuse me, but I don't understand.  My interpretation of the ARM is that
given your implementation supplies an integral type with more (or equal
amount of) bits than a void pointer, you can safely cast any pointer to
that integral type, fiddle with this integer in a reversible way, do the
reverse transformation, cast it back and get the original pointer.  Thus,
if you know your implementation meets this prerequisite, then running a
program only unportable in this way WILL produce the same results on
every such architecture since the ARM guarantees it.  Adding conservative
GC might change this invariance.  So, I conclude the ARM must be rephrased
in order to enable GC.

Actually, I find it strange that the ARM states a facility to be well-
defined under certain conditions and implementation dependent otherwise
instead of just saying it's implementation dependent.  I'm sure there
are a rationale for this, if someone has, please tell me.

:In practice, none of this is a significant problem: even if you carry
:out integer/pointer conversions, almost all of the time you are going
:to keep the real pointer around, either as an integer or as a pointer.
:Those old program programs that don't (if any) can be run either with
:GC turned off, or they can be modified slightly to keep the original
:pointers around.

No argument, but I wasn't talking of practice :-)

:C/C++ has undergone significantly greater changes than this.

:For a more extensive discussion of these issues, I suggest looking at
:comp.compilers.

I will see to we will get this group here, we have had a limited news-
feed here during the summer.  Too bad, I'd want to get that discussion :-(

:					Thomas.

:PS: Where was the outcry of indignation when, all of a sudden,
:uninitialized static member definitions didn't count as definitions
:anymore? Unlike restricting encoded pointers, this did force me to
:change some of _my_ source code.

In gnu.g++.bugs, there has been lots of outcries when G++ changed in this
way.  Well, you asked :-)  I won't cry out, if we'll restrict encoded
pointers.  What's important is that we DO restrict them if we bless GC.

:PPS: As to the XOR trick, you can use doubly linked lists of small
:arrays of elements to get equivalent space savings portably.

Yes, but in order to keep these savings you have to move elements between
arrays every time you add/remove elements in the middle of the list.
Otherwise you may have half full arrays spending the saved space.
Those element movements can be quite expensive... but you're right,
it's definitely more portable, and used as stacks and queues, they should
work real well.
-- 
Niklas Hallqvist	Phone: +46-(0)31-40 75 00
Applitron Datasystem	Fax:   +46-(0)31-83 39 50
Molndalsvagen 95	Email: niklas@appli.se
S-412 63  GOTEBORG, Sweden     mcsun!seunet!appli!niklas
Newsgroups: comp.lang.c++