generics - 完整、高效的 NumericLiteral 模块实现

Question

基于 this question 中的讨论，任何人都可以提供代码或代码链接，显示 NumericLiteralX 模块的完整实现(例如 this one )？我对 NumericLiteralX 模块的 FromInt32/64 的高效实现特别感兴趣，该模块有助于通用数字运算。这是取自上述问题的一个可能效率低下的实现:

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 的显式转换。 。不幸的是，这有两个问题。首先是语法无效 - 在成员约束的“static-typars”部分中不能有具体类型(如 int )。我们可以通过定义辅助函数来解决这个问题

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# 的 future 版本可能会使其按原样工作，但从 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"消息(并且使用 secret --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 的值(但已缓存，因此委托(delegate)仅创建一次)。同样，(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