Add richer data model address arithmetic: AddrDiff and AddrInt (ie d Int_ptr_diff and Int_ptr_size)

currently GHC's internals and code gen don't provide a strong distinction between Ints as data, and Ints for pointer / address arithmetic. This also comes up as being problematical in a number of ways.

1. We wind up having many portability issues around Int and pointer / address sizes.
2. adds some inessential complexity / problems to adding new architectures to ghc. eg x32 ABI which has 32bit pointers and 64bit ints somewhat breaks current assumptions in the GHC primops (because arrays are indexed by a byte offset, and the valid range for those is determined by the ABI pointer size!)
3. this Ints and Ptrs confusion we currently have, also means we can't leverage the Integer support in SIMD registers that is in most modern CPUs! If we could have those two separated better, theres a lot of low leve optimizations we could do for Int/Word data that we currently cant do!

Trac metadata

Trac field	Value
Version	7.6.3
Type	FeatureRequest
TypeOfFailure	OtherFailure
Priority	high
Resolution	Unresolved
Component	Compiler
Test case
Differential revisions
BlockedBy
Related
Blocking
CC
Operating system
Architecture

mentioned in issue #8287

changed milestone to %7.10.1

changed weight to 7

added Tfeature request Trac import labels

On point 2:

It seems to me that the current Foreign.Ptr API

plusPtr :: Ptr a -> Int -> Ptr b
minusPtr :: Ptr a -> Ptr b -> Int

pretty much forces Int to be the same size as a C pointer, on any architecture. For a real x32 executable, this would mean 32-bit Int, while for a "fake x32" mode which maintains a heap below 4G and stores heap pointers as 4 bytes, but otherwise is a normal x86_64 executable, this would mean 64-bit Int. There doesn't seem to be a good reason why the Int used for normal arithmetic, and used to count things in data structures like Map, should be tied to that C pointer size.

As a matter of fact, an appropriate replacement for those Ints in Foreign.Ptr already exists in Foreign.C.Types: CPtrdiff, "Haskell type representing the C ptrdiff_t type".

agreed with Reid.

its worth remarking though, that internally that CPtrdiff type is just Int64 on x86_64. It really needs to be a distinguished type internally, not just a newtype wrapper around an Int (at least for a satisfactory analogue for GHC and correct code gen)

Presumably an Addr# is wide enough to contain an offset? So perhaps we should use Addr# instead of Int# for address differences? We could have and AddrDiff# type, but then we'd need arithmetic over it etc. Maybe just a type synonym for Addr#?

Anyway feel free to propose a concrete design.

Simon

@simon I think so! (though i could be wrong). I'll have to mull over it a bit as I have time

on the associated api: would motivate adding Torsors to GHC Base I think. http://www.reddit.com/r/haskell/comments/166iju/subtractable_values_are_torsors/

http://ro-che.info/articles/2013-01-08-torsors.html and

http://hackage.haskell.org/packages/archive/vector-space/latest/doc/html/Data-AffineSpace.html

with the key bits being

class AdditiveGroup (Diff p) => AffineSpace p whereSource

Associated Types
type Diff p Source

Associated vector space

Methods
(.-.) :: p -> p -> Diff pSource

Subtract points

(.+^) :: p -> Diff p -> pSource

Point plus vector

in this case, the Addr would the the "points", and the offset type would be type Diff Addr = AddrDiff

or something like that.

Reid Barton (who's been experimenting with an x32 ABI) made an observation yesterday evening on IRC #ghc about address vs int sizes for ghc

[09:24:34] <rwbarton>	 ugh, I didn't think about the fact that integer-gmp exposes its representation to the world
[09:24:43] <rwbarton>	 that means potentially anybody is assuming that Int is the same size as mp_limb_t
[09:24:47] <hvr_>	 dcoutts_: fwiw, bytestring w/ ghc-head/linux/i386 passed too
[09:55:47] <rwbarton>	 I guess ghcjs has the same problem
[09:56:07] <rwbarton>	 can't support exporting the J# constructor
[09:56:25] <hvr_>	 rwbarton: what problem exactly?
[09:57:11] <rwbarton>	 so my problem that I just realized is on x32
[09:57:34] <rwbarton>	 where Int is 4 bytes, but gmp uses 8 byte limbs
[09:57:59] <rwbarton>	 I can't have people going around constructing Integers with J#, because first of all they might not provide a ByteArray# that's a multiple of 8 bytes long
[09:59:49] <rwbarton>	 so ideally (for me) there would be a type with the S# and J# constructors for pattern matching on, that was distinct from Integer
[10:00:14] <rwbarton>	 that former type exported, the constructors of Integer not exported
[10:00:29] <rwbarton>	 with conversions between them that on "ordinary" platforms are zero-cost
[10:04:34] <hvr_>	 rwbarton: btw, I've been wishing for some bignum-only type
[10:04:45] <hvr_>	 i.e. an Integer only w/ J#
[10:05:38] <hvr_>	 then the proper Integer type could use that unboxed as single field in its J# constructor

This is just another data point to consider in any design constraints

mentioned in issue #9416 (closed)

removed milestone

this is still an issue, but should be punted to 7.12

changed milestone to %8.0.1

Milestone renamed

changed milestone to %8.2.1

changed weight to 5

This won't be happening for 8.0 I'm afraid.

Trac metadata

Trac field	Value
Priority	high → normal

Un-milestoning due to lack of progress. Feel free to pick it up though!

added Pnormal label