From -4979337190200064421
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: f78e5,e94695845965b249
X-Google-Attributes: gidf78e5,public
X-Google-ArrivalTime: 1992-12-06 11:22:24 PST
Newsgroups: comp.std.c++
Path: sparky!uunet!europa.asd.contel.com!darwin.sura.net!zaphod.mps.ohio-state.edu!rpi!batcomputer!munnari.oz.au!metro!extro.ucc.su.OZ.AU!maxtal
From: maxtal@extro.ucc.su.OZ.AU (John MAX Skaller)
Subject: Re: Zero-length structures and pointer comparisons
Message-ID: <1992Dec6.142140.12581@ucc.su.OZ.AU>
Sender: news@ucc.su.OZ.AU
Nntp-Posting-Host: extro.ucc.su.oz.au
Organization: MAXTAL P/L C/- University Computing Centre, Sydney
References: <1992Dec2.205330.10372@meaddata.com> <5305@holden.lulea.trab.se>
Date: Sun, 6 Dec 1992 14:21:40 GMT
Lines: 52

In article <5305@holden.lulea.trab.se> jbn@lulea.trab.se (Johan Bengtsson) writes:
>_If_ total ordering of pointers makes common programmin tasks easier,
>the the very small speed penalty we are talking about would be quite
>insignificant.

	On 8086 class machines the speed penalty could be huge.
Instead of a single instruction comparing a register to memory,
the problem of where to put the segment part arises. There is
only one spare segment register (ES) in most memory models,
and if one of the pointers lives in an extra segment referenced
by ES then it cannot be used. Thus an a additional instruction
is required to load the segment part into a register, whose
previous contents wil have to be pushed, the comparison done
in two halves with several branches floating about,
then the register value popped back again.

	Furthermore, the segment:register pairs on the 8086 will have
to be normalised ... both of them. Of course the unnormalised
parts will have to be preserved in case there is a requirement
for this ... I think we have at least one decimal order of magnitude 
slower here.

	CMP	AX,PTR	; no total order

as opposed to

	; no  no no I'm not going to do this
	; it would take hours to figure out how to do it!

>
>What tasks are made easier?
>
>Off hand, I can only think of binary searches in sorted pointer tables.
>Are there other (portable) examples?
>

	This is whole class of examples, including all ordered
aggregates of pointers---lists, trees, etc etc.

	Another example might be where memory is allocated
on a stack, pointer comparisons could be useful unwinding the stack,
checking for dangling references in GC, implementing a 
mark and release scheme, etc.

(Of course, NOT having a total order might also be important in such
schemes if they were machine specific).

-- 
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
	Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------