BlueMountainCapital/Deedle — pull request #283 by buybackoff (2014-11-18 11:38:28+00:00)
Title: Abstract address

**This is to make Address abstract**

Currently, Address if defined as `type Address = int64` and in many places (not only linear implementation) `int64` is used where `Address` is implied. Aliasing makes it possible. Current definition of address itself implies that it is starts with zero, linear and continuous - effectively the same int32/64. However, an abstract address is just a pointer to get a value from a vector.

A better definition of address is anything with the following properties:

* An address is a comparable value type with default constructor;
* Its default constructor returns the smallest possible (zero) address
(which is in general not the first value);
* Decrementing zero address results in an invalid address;
* Any transformation or operation on invalid address results in an invalid address or invalidOp;
* An address type must implement explicit conversion to and from `int64`;
* Zero address is always 0L, invalid address is always `-1L`.

An abstract address implements the following interface:

type IAddress<'T when 'T :> IAddress<'T>
and 'T : comparison
and 'T : struct
and 'T : (new : unit -> 'T)
>=
interface
/// Next possible address (not next address with a value)
abstract Increment : unit -> 'T
/// Previous possible address (not next address with a value)
abstract Decrement : unit -> 'T
end

A helper class adds `op_Explicit` constraints and defines the only possible operations on an address:

[]
type private AddressHelper<'T when 'T :> IAddress<'T>
and 'T : comparison
and 'T : struct
and 'T : (new : unit -> 'T)
and 'T : (static member op_Explicit: int64 -> 'T)
and 'T : (static member op_Explicit: 'T -> int64)
>() =
static let zero = new 'T()
static let invalid = zero.Decrement()
static member inline Increment(address : 'T) : 'T = address.Increment()
static member inline Decrement(address : 'T) : 'T = address.Decrement()
/// Invalid address in defined as zero address decremented
static member inline Invalid with get() : 'T = invalid
static member inline AsInt64<'T>(addr : 'T) : int64 = int64 addr
static member inline OfInt64<'T>(value : int64) : 'T =
( ^T : (static member op_Explicit : int64 -> 'T) value)

There is no method `generateRange (lo:Address, hi:Address)` from the current implementation, because an abstract address cannot know all used addresses between `lo` and `hi`, but only all *possible* addresses, which could be a very huge number in a general case.

Such definition of address makes a clear distinction between an *address*, a *key* and an *index* of a value. An address is something that corresponds 1-to-1 to a *key* (and derived from it) and something that could be used to get a value from a vector. An *index* (lower case) is a position of a key or a value from the beginning of an Index (capitalized, IIndex<'K>) or a vector (possibly the word *position* is better to avoid confusion with the IIndex).

The default linear address is implemented as:

/// Represents a type used for addressing values in a linear vector/index
[]
type Address = // linear address
struct
val private value : int64
new(index:int64) = {value = index}
end
override x.Equals(yobj) =
match yobj with
| :? Address as y -> (x.value = y.value)
| _ -> false
override x.GetHashCode() = x.value.GetHashCode()
override x.ToString() = x.value.ToString()
interface System.IComparable

with
member x.CompareTo y = x.value.CompareTo(y.value)
interface System.IComparable with
member x.CompareTo other =
match other with
| :? Address as y -> x.value.CompareTo(y.value)
| _ -> invalidArg "other" "Cannot compare values of different types"

static member op_Explicit(addr: Address) : int64 = addr.value
static member op_Explicit(value: int64) : Address = Address(value)

interface IAddress

with
member x.Decrement() = if x.value <> -1L then Address(x.value - 1L) else Address(-1L)
member x.Increment() = if x.value <> -1L then Address(x.value + 1L) else Address(-1L)

type AddressHelper = AddressHelper

The address module is redefined as:

[]
module Address =
let invalid : Address = AddressHelper.Invalid
let inline asInt64 (x:Address) : int64 = AddressHelper.AsInt64(x)
let inline asInt (x:Address) : int = int <| AddressHelper.AsInt64(x)
let inline ofInt64 (x:int64) : Address = AddressHelper.OfInt64(x)
let inline ofInt (x:int) : Address = AddressHelper.OfInt64(int64 x)
let inline increment (x:Address) = AddressHelper.Increment(x)
let inline decrement (x:Address) = AddressHelper.Decrement(x)

Both Index and Vector implement additional properties:

/// Return address at a specified index
abstract AddressAt : int64 -> Address
/// Return index at a specified address
abstract IndexAt : Address -> int64

These properties are used everywhere instead of `Address.zero`, `Address.asInt64`, `Address.ofInt64`. Even though an address type is required to have `op_Explicit` to and from `int64`, such conversion doesn't convert an *address* to an *index* and vice versa. The `int64` conversion is used for implementation: any practical address space is less than 2^64 and could be encoded as `int64` (e.g. number of nanoseconds since 1/1/1900 will exceed 2^62 only in 2046).

Linear Index implements these properties as:

member inline private x.AddressAt(index) = Address.ofInt64 index
member inline private x.IndexAt(address) = Address.asInt64 address

All methods are inlined, therefore these methods effectively call `op_Explicit` methods from the `AddressHelper` class. A quick performance tests shows that calling `Address.ofInt64` is as fast as calling a constrcutor or just using `int64` directly.

// In fsi a, b and c show the same timing (40-50 msec after fsi reset), d is more than 20 times slower (c.1100 msec after fsi reset)
let a = Array.init 10000000 (fun i -> Address.ofInt64(int64 i)) |> Array.length
let b = Array.init 10000000 (fun i -> Address(int64 i)) |> Array.length
let c = Array.init 10000000 (fun i -> (int64 i)) |> Array.length
let d = Array.init 10000000 (fun i -> Activator.CreateInstance

()) |> Array.length

The abstract address implementation decouples Deedle's data structures from `int64` and allows to reuse Deedle's interfaces; yet it keeps existing API unchanged and passes all tests on my machine.