Полная, эффективная реализация модуля NumericLiteral

Question

Основываясь на обсуждении в this question, может ли кто-либо предоставить код или ссылку на код, показывающий полную реализацию модуля NumericLiteralX (например, this one)? Меня особенно интересует эффективная реализация 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) в разделе «статические-typars» ограничения члена. Мы можем обойти это, определив вспомогательную функцию

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

Поскольку обе эти функции встраиваемой, это не какой-либо менее эффективен, чем при первой попытке, это просто 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 нам нужно придумать обходной путь.

Было бы хорошо, если бы мы могли использовать аналогичный подход к тому, как # библиотеке ядра F обрабатывает проблемы такого рода, что потребует специального корпуса всего подразумеваемых операторов, но привел бы во всем быть встраиваемый с идеальной эффективностью:

Однако компилятор 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 может быть применен только к типам, где есть явное преобразование из междунар (или один имитируемый компилятором). Фактический вызов 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), поэтому есть накладные расходы на несколько вызовов методов, но общая производительность должна быть очень хорошей.

EDIT

Однако, если вы просто ищете что-то более эффективное, чем наивные реализаций FromInt32 и FromInt64 нашли время O (п), вот версия, которая все еще относительно простой и только принимает O (журнал 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