Sunday, April 25, 2010

A minimalistic native 64 bit array implementation for .NET (updated code)

If you ever felt the need to process huge amounts of data via a algorithm implemented using .NET/the CLR, you’ve surely ran into the 2^31-items-limit of the CLR’s current array implementation that only supports Int32 array indices (this also affects other collections like List<T> as those use standard arrays for storage internally).
You can try to circumvent this limitation by implementing your own array-like data-structure, either by emulating continuous storage via a collection of standard .NET-arrays (partition your data in chunks with 2^31 items each), or you can use native APIs and some evil pointer arithmetic to get maximum performance.
A while ago I tried to implement the latter approach in C#, which isn’t a big deal, only a matter of some unsafe-blocks for pointer arithmetic and a call to Marshal.AllocHGlobal for allocating memory on the unmanged heap. However, when I tried to make that custom collection into a generic one, I ran into an unsolvable problem:
public unsafe T this[long index]
{
    get
    {                
        return *((T*)pBase + index);
    }
    set
    {
        *((T*)pBase + index) = value;
    }
}

This code does not compile. The reason for that is, that there is no way to tell the C# compiler that T shall be constrained to unmanaged types.
Interestingly, F# 2.0 does feature such a constraint! This is how a minimalistic F# implementation of such an native 64 bit array could look like:
namespace NativeTools
 
#nowarn "9"
#nowarn "42"
 
open System
open System.Runtime
open Microsoft.FSharp.NativeInterop
 
module internal PointerArithmetic =
    [<CompiledName("AddIntPtrToIntPtr")>]
    [<Unverifiable>]
    let inline addNativeInt (x: nativeptr<'T>) (n: nativeint) : nativeptr<'T> = 
        (NativePtr.toNativeInt x) + n * (# "sizeof !0" type('T) : nativeint #) |> NativePtr.ofNativeInt
    
    // "reinterpret_cast<IntPtr>(x)"... EVIL!
    [<CompiledName("Int64ToIntPtr")>]
    [<Unverifiable>]
    let inline int64ToNativeint (x: int64) = (# "" x : nativeint #)
 
    [<CompiledName("AddInt64ToIntPtr")>]
    [<Unverifiable>]
    let inline addInt64 (x: nativeptr<'a>) (o: int64) : nativeptr<'a> = addNativeInt x (int64ToNativeint o)
    
[<Sealed>]
type NativeArray64<'T when 'T: unmanaged>(length: int64) =
    let itemSize: int64 = (int64)(InteropServices.Marshal.SizeOf(typeof<'T>))
    let mutable isDisposed = false
    let allocatedBytes = length * itemSize
    let blob = InteropServices.Marshal.AllocHGlobal(nativeint allocatedBytes)
    let pBlobBase: nativeptr<'T> = NativePtr.ofNativeInt blob
    let disposeLock = new Object()
 
    member this.Length = length
    member this.BaseAddress = pBlobBase
    member this.ItemSize = itemSize
    member this.IsDisposed = isDisposed
    member this.AllocatedBytes = allocatedBytes
    
    member private this.Free () =
        lock disposeLock (fun () ->
            if isDisposed
                then ()
                else InteropServices.Marshal.FreeHGlobal blob
                     isDisposed <- true
        )
           
    member this.Item
        with get (idx: int64) =
                        NativePtr.read (PointerArithmetic.addInt64 pBlobBase idx)                    
        and  set (idx: int64) (value: 'T) =
                        NativePtr.write (PointerArithmetic.addInt64 pBlobBase idx) value
        
    member private this.Items = seq {
            for i in 0L .. length - 1L do
                yield this.[i]
        }
 
    override this.Finalize () = this.Free()
    
    interface IDisposable with
        member this.Dispose () =
            GC.SuppressFinalize this
            this.Free()
 
    interface Collections.Generic.IEnumerable<'T> with
        member this.GetEnumerator () : Collections.Generic.IEnumerator<'T> =
            this.Items.GetEnumerator()
        member this.GetEnumerator () : Collections.IEnumerator =
            this.Items.GetEnumerator() :> Collections.IEnumerator

UPDATE 2010-04-25: Removed a few bugs.

You can use this data structure in your C# code like a normal array:
var length = 8L * 1024L * 1024L * 1024L;

// allocate a byte-array of 8 GiB

using(arr = new NativeTools.NativeArray64<byte>(length))

{

    arr[0] = 123;

    arr[length-1] = 222;

    Console.WriteLine("Allocated " + arr.AllocatedBytes);

}

// auto-disposed ...