完整、高效的 NumericLiteral 模块实现 [英] Complete, efficient NumericLiteral module implementation

问题描述

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

Building on a discussion in this question, could anyone provide code, or a link to code, showing a complete implementation of a NumericLiteralX module (such as this one)? I'm especially interested in an efficient implementation of FromInt32/64 for a NumericLiteralX module that facilitates generic numeric operations. Here's a perhaps inefficient implementation taken from the aforementioned question:

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 

如何改进和完成?

推荐答案

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

I'll just address FromInt32. In an ideal world, we could define it as simply as

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

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

which would use static constraints to ensure that we could inline an explicit conversion from int. Unfortunately, there are two problems with this. The first is that the syntax is invalid - you can't have a concrete type (like int) in the "static-typars" portion of a member constraint. We can work around this by defining a helper function

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

由于这两个函数都是内联的，这并不比第一次尝试的效率低，只是更冗长.

Since both of these functions are inlined, this isn't any less efficient than the first attempt, it's just wordier.

这里是我们遇到第二个问题的地方:这将适用于真正的 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 开始，我们需要想出一个解决方法.

Here's where we run into the second problem: this will work for real op_Explicit definitions (or op_Implicit, which is treated specially by the compiler so that it is subsumed by op_Explicit). So (10G : bigint) will be inlined as if you had written System.Numerics.BigInt.op_Implicit 10, which is as efficient as we can hope for. However, F# also simulates op_Explicit for many primitive types (e.g. for conversions from int to float, byte, etc.), and since the definition of FromInt32 relies on the existence of these members it will fail at runtime (that is, (10G : float) and even (10G : int) will compile but will throw an exception when executed). Ideally a future version of F# might enable this to work as-is, but as of F# 2.0, we'll need to come up with a workaround.

如果我们可以使用类似的方法来处理 F# 核心库如何处理此类问题，那就太好了，这将需要对所有隐含运算符进行特殊大小写，但会导致所有内容都以完美的效率内联:

It would be nice if we could use a similar approach to how the F# core library handles this kind of problem, which would require special casing all of the implied operators but would result in everything being inlined with perfect efficiency:

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

但是，F# 编译器通过 静态优化条件仅用于 F# 库中" 消息(并使用秘密 --compiling-fslib 标志只会让事情变得更糟 :)).

However, the F# compiler rejects this with a "Static optimization conditionals are only for use within the F# library" message (and compiling with the secret --compiling-fslib flag only makes things worse :)).

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

Instead, we need to use a few additional layers of indirection to achieve something similar at runtime. First, we'll create a runtime mapping of types to conversion functions by using a static member of a generic type:

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

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

This is similar to what we were trying to achieve with the static optimization conditionals in the previous attempt, but it's deferred to runtime instead of everything being evaluated at compile time. Now we just need to define a few values to use this type:

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 进行显式转换的类型(或由编译器模拟的类型)).FromInt32 中对 constrain() 的实际调用应该在编译期间得到优化.

Here, the constrain function is just used to make sure that FromInt32 can only be applied to types where there's an explicit conversion from int (or one simulated by the compiler). The actual call to constrain() within FromInt32 should get optimized away during compilation.

使用这种方法，(10G : bigint) 将被编译为类似 IntConverterDynamicImplTable<bigint>.Result 10 和 IntConverterDynamicTable<bigint>.Result 将有一个等价于 (System.Func(bigint.op_Implicit)).Invoke 的值(但被缓存，因此委托只创建一次).类似地，(10G : int64) 将编译为 IntConverterDynamicImplTable.Result 10，并且 IntConverterDynamicTable.Result 将有一个值等价于转换函数(int64 : int -> int64)，所以有一些方法调用的开销，但整体性能应该很好.

With this approach, (10G : bigint) will get compiled to something like IntConverterDynamicImplTable<bigint>.Result 10, and IntConverterDynamicTable<bigint>.Result will have a value equivalent to (System.Func<int,bigint>(bigint.op_Implicit)).Invoke (but cached, so that the delegate is only created once). Similarly, (10G : int64) will compile to IntConverterDynamicImplTable<int64>.Result 10, and IntConverterDynamicTable<int64>.Result will have a value equivalent to the conversion function (int64 : int -> int64), so there are overheads of a few method calls, but the overall performance should be very good.

编辑

但是，如果您只是在寻找比 FromInt32 和 FromInt64 的简单实现更高效的东西，O(n)，这是一个仍然比较简单的版本，只需要 O(log n) 时间:

However, if you're just looking for something more efficient than a naive implementations of FromInt32 and FromInt64 taking time O(n), here's a version which is still relatively simple and only takes O(log n) time:

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

这篇关于完整、高效的 NumericLiteral 模块实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！