完整,高效的NumericLiteral模块实现

Question

基于这个问题的讨论,任何人都可以提供代码或代码链接,显示NumericLiteralX模块的完整实现(例如这个)吗？我特别感兴趣的是有效实现FromInt32/ 64用于NumericLiteralX促进通用数字运算的模块.这是从上述问题中得出的可能效率低下的实现:

module NumericLiteralG = 
    let inline FromZero() = LanguagePrimitives.GenericZero
    let inline FromOne() = LanguagePrimitives.GenericOne
    let inline FromInt32 (n:int) =
        let one : ^a = FromOne()
        let zero : ^a = FromZero()
        let n_incr = if n > 0 then 1 else -1
        let g_incr = if n > 0 then one else (zero - one)
        let rec loop i g = 
            if i = n then g
            else loop (i + n_incr) (g + g_incr)
        loop 0 zero 

怎么可以改进和完成？

Answer 1

我只想解决FromInt32.在理想的世界中,我们可以简单地将其定义为

let inline FromInt32 i = 
  ((^t or int) : (static member op_Explicit : int -> ^t) i)

这将使用静态约束来确保我们可以内联显式转换int.不幸的是,这有两个问题.第一个是语法无效 - 你不能int在成员约束的"static-typars"部分中有一个具体的类型(如).我们可以通过定义辅助函数来解决这个问题

let inline cvt i = ((^t or ^u) : (static member op_Explicit : ^u -> ^t) i)
let inline FromInt32 (i:int) = cvt i

由于这两个函数都是内联的,因此这并不比第一次尝试的效率低,它只是更啰嗦.

这是我们遇到第二个问题的地方:这将适用于真正的op_Explicit定义(或者op_Implicit,由编译器专门处理,以便它被包含op_Explicit).因此(10G : bigint),如果您已经编写了内容System.Numerics.BigInt.op_Implicit 10,这将是我们希望的有效率.但是,F#还模拟op_Explicit了许多基本类型(例如,对于转换int为float,byte等等),并且由于定义FromInt32依赖于这些成员的存在,它将在运行时失败(即,(10G : float)甚至(10G : int)将编译但将抛出执行时的异常).理想情况下,F#的未来版本可能会使其按原样运行,但从F#2.0开始,我们需要提出一种解决方法.

如果我们可以使用类似的方法来解决F#核心库如何处理这类问题,这将需要特殊的套管所有隐含的运算符,但会导致所有内容都以完美的效率内联:

let inline FromInt32 (i : int) : ^t =
  cvt i
  when ^t : int   = int i
  when ^t : float = float i
  when ^t : byte  = byte i
  ...

但是,F#编译器通过"Static optimization conditionals are only for use within the F# library"消息拒绝这个(并且使用秘密--compiling-fslib标志进行编译只会使事情变得更糟:)).

相反,我们需要使用一些额外的间接层来在运行时实现类似的功能.首先,我们将使用泛型类型的静态成员创建类型到转换函数的运行时映射:

type IntConverterDynamicImplTable<'t>() =
  static let result : int -> 't =
    let ty = typeof< 't> //'
    if   ty.Equals(typeof<sbyte>)      then sbyte      |> box |> unbox
    elif ty.Equals(typeof<int16>)      then int16      |> box |> unbox
    elif ty.Equals(typeof<int32>)      then int        |> box |> unbox
    elif ty.Equals(typeof<int64>)      then int64      |> box |> unbox
    elif ty.Equals(typeof<nativeint>)  then nativeint  |> box |> unbox
    elif ty.Equals(typeof<byte>)       then byte       |> box |> unbox
    elif ty.Equals(typeof<uint16>)     then uint16     |> box |> unbox
    elif ty.Equals(typeof<char>)       then char       |> box |> unbox
    elif ty.Equals(typeof<uint32>)     then uint32     |> box |> unbox
    elif ty.Equals(typeof<uint64>)     then uint64     |> box |> unbox
    elif ty.Equals(typeof<unativeint>) then unativeint |> box |> unbox
    elif ty.Equals(typeof<decimal>)    then decimal    |> box |> unbox
    elif ty.Equals(typeof<float>)      then float      |> box |> unbox
    elif ty.Equals(typeof<float32>)    then float32    |> box |> unbox
    else 
      let m = 
        try ty.GetMethod("op_Implicit", [| typeof<int> |])
        with _ -> ty.GetMethod("op_Explicit", [| typeof<int> |])
      let del =
        System.Delegate.CreateDelegate(typeof<System.Func<int,'t>>, m)
        :?> System.Func<int,'t>
      del.Invoke |> box |> unbox
  static member Result = result

这类似于我们在前一次尝试中使用静态优化条件尝试实现的内容,但它延迟到运行时而不是在编译时评估的所有内容.现在我们只需要定义一些值来使用这种类型:

let inline constrain< ^t, ^u when (^t or ^u) : (static member op_Explicit : ^t -> ^u)> () = ()
let inline FromInt32 i : ^t = 
  constrain<int, ^t>()
  IntConverterDynamicImplTable.Result i

这里,该constrain函数仅用于确保FromInt32只能应用于从int(或编译器模拟的)显式转换的类型.在编译期间,对constrain()内部的实际调用FromInt32应该被优化掉.

使用这种方法,(10G : bigint)将编译成类似的东西IntConverterDynamicImplTable<bigint>.Result 10,并且IntConverterDynamicTable<bigint>.Result将具有等效的值(System.Func<int,bigint>(bigint.op_Implicit)).Invoke(但是缓存,以便委托仅创建一次).同样,(10G : int64)将编译为IntConverterDynamicImplTable<int64>.Result 10,并且IntConverterDynamicTable<int64>.Result将具有等效于转换函数的值(int64 : int -> int64),因此存在一些方法调用的开销,但整体性能应该非常好.

编辑

但是,如果你只是寻找一些比天真的实现更有效的东西FromInt32并FromInt64花费时间O(n),这里的版本仍然相对简单,只需要O(log n)时间:

module SymmetricOps =
  let inline (~-) (x:'a) : 'a = -x
  let inline (+) (x:'a) (y:'a) : 'a = x + y
  let inline (-) (x:'a) (y:'a) : 'a = x - y
  let inline (*) (x:'a) (y:'a) : 'a = x * y
  let inline (/) (x:'a) (y:'a) : 'a = x / y
  let inline (%) (x:'a) (y:'a) : 'a = x % y

module NumericLiteralG = 
  open SymmetricOps
  let inline FromOne() = LanguagePrimitives.GenericOne
  let inline FromZero() = LanguagePrimitives.GenericZero
  let rec compute zero one two (/) (%) Two (+) (-) (*) pow2 rest n =
    if n = zero then rest
    else 
      let rest' =
        let nmod2 = n % two
        if nmod2 = zero then rest
        elif nmod2 = one then rest + pow2
        else rest - pow2
      compute zero one two (/) (%) Two (+) (-) (*) (Two * pow2) rest' (n / two)
  let inline FromInt32 i = compute 0  1  2  (/) (%) (FromOne() + FromOne()) (+) (-) (*) (FromOne()) (FromZero()) i
  let inline FromInt64 i = compute 0L 1L 2L (/) (%) (FromOne() + FromOne()) (+) (-) (*) (FromOne()) (FromZero()) i