🚀 go-pugleaf

In article <BzDJHu.t2@frumious.uucp>, pat@frumious.uucp (Patrick Smith) writes:
|> Surely one would want to insist on
|> 
|>    p == q   =>   ptrcmp(p,q) == 0
|> 
|> If this weren't true, one wouldn't be able to use ptrcmp as a basis
|> for organizing an ordered binary tree for searching.  Are there any
|> likely-to-be-common uses of ptrcmp which don't need this assumption?
|> 
|> Unfortunately, meeting this condition might be expensive on
|> segmented architectures (according to the many other postings
|> on this subject).

I've had it!  Enough blathering about what might be possible or expensive
on segmented architectures!  A segmented architecture does not present as
many difficulties as some people think.  In a segmented machine, like the
80x86, pointers can be divided into two catagories:

	a) Segment with offset ("far" pointers)
	b) Offset-only ("near" pointers)

In what is commonly called the "large memory model," only far pointers
are found.  In the "small memory model," only near pointers are found.
It is valid to use both near and far pointers in the same program.

Far pointers present no special difficulties for equality tests unless
operating-system operations map multiple segments to the same memory
location, in which case the program is no longer strictly conforming.
(Normalizing pointers, a practice used in some 8086 C compilers, is not
usually necessary.  A compiler that normalizes must also pay the price with
a more complicated equality check.)

Near pointers present a problem at first glance, because the segment
information seems to be missing.  But that ignores a fundamental fact about
near pointers:

	A pointer can be represented as an offset without a segment IF AND
	ONLY IF THE SEGMENT IS KNOWN OR IMPLIED BY CONTEXT.

This means that the compiler can always know the segment part of a near
pointer.  Consider the following code:

	void* memcpy(void* s1, const void* s2, size_t n);
	...
	int *px, *py;
	int s;
	...
	memcpy(x, y, s);

Assume px and py are near (offset-only) pointers.

At the point that memcpy is called, px and py might have the same offset.
In order for memcpy to work (and it MUST work if this is a conforming
implementation), either px and py must point into the same segment, OR the
compiler must be able to determine the correct segment for each.  In the
latter case, the segment information must be supplied to memcpy, e.g. in
the conversion from int* to void*.  The important thing to note is that
memcpy CAN distiguish px from py even if they have the same offset.

SOOO...  It is already a requirement that two pointers to different objects
must be distinguishable.  It is therefore easy to meet a requirement that
pointers to *different* objects must compare *unequal*.  More difficult, in
light of normalization and OS hanky-panky, is the current ARM requirement
that pointers to the *same* object must compare *equal*.  However as I
stated earlier, OS hanky-panky is non-conforming and normalization is an
implementation decision that carries the price of slower pointer
comparisons.

Absolute orderings are a slightly different matter.  In the case of < and
>, one might expect a significant performance improvement if the pointers
are assumed to point into the same array, since the segment part can be
ignored even for far pointers.  A ptrcmp() function might be worthwhile and
should present no special implementation problems for segmented
architectures.  However, systems (like the lisp machine) where pointers
change behind the program's back DO present a problem since the
bit-pattern-based ordering could change even if the equality/inequality
property does not change.  This would argue against *requiring* a ptrcmp()
function.

-- 

- Pablo

------------------------------------------------------------------------
Pablo Halpern             (617) 290-3542
HP Waltham                pabloh@hpwarq.wal.hp.com

I am self-employed, so my opinions *do* reflect those of my employer.
However, they may not reflect the opinions of my client.
------------------------------------------------------------------------