CLR array covariance implementation

С давних времён (ещё с первой версии) в систему типов .NET введена такая штука, как ковариантные массивы. Эта фича разрешает неявные приведения типа массивов из элементов типа B к типу массивов из элементов типа A, если существует неявное ссылочное приведение типа B к типу A (то есть типы-значения сразу отпадают).

К сожалению, язык F# не предусматривает работу с вариантностью/ковариантностью вовсе (даже аннотации в определениях типов интерфейсов и делегатов). Однако, так как поддержку ковариантности массивов обеспечивает рантайм, фичей всё равно можно воспользоваться, через даункаст из типа obj (то есть с проверкой времени выполнения):

let xs : string array = [| "abc"; "def"; "ghi" |]
let ys : obj array    = downcast (box xs)

Интерес представляет то, что если теперь воспользоваться данным массивом как обычным массивом obj[] и сохранить в него ссылку на какой-либо экземпляр другого ссылочного типа, то мы получим исключение System.ArrayTypeMismatchException:

// ys на самом деле string[]
ys.[0] <- new obj()

То есть вместе с массивом хранится дополнительная информация о том, элементы какого типа он всё же может хранить и при каждой записи в массив элементов ссылочного типа осуществляется проверка времени исполнения. Однако проверка происходит не только при записи, но и взятии адреса:

type Foo =
     // метод с byref-параметром
     static member Bar(x: obj byref) =
          x <- new obj()

Foo.Bar(&ys.[0]) // буууух!

Таким образом, слизав данную фичу с Java реализовав подобную сомнительную возможность, команда CLR добавила оверхэд ко всем операциям записи в массивы ссылочных типов, а значит прибавили тормозов ко всем коллекциям, базирующимся на массивах (например, System.Collections.Generic.List<T>, но не для списков F#).

Воспользовавшись кодом из данного поста, померяем влияние проверки времени выполнения, сравнив скорость с массивом специальных типов-значений, просто оборачивающих в себя значения типа 'a:

/// Тип-значение, представляющий собой
/// некую ячейку хранения значения типа 'a
[<Struct>]
type Holder<'a> =
     new x = { Value = x }   // конструктор
     val mutable Value: 'a   // изменяемая ячейка

// и произвольное значение ссылочного типа
let ref_value = "abc"

Measure.run [ // тестирование скорости записи

    "запись элементов в массив",
    fun () -> let xs = Array.zeroCreate 1
              for i = 0 to 100000 do
                  xs.[0] <- ref_value

    "запись обёрнутых элементов",
    fun () -> let xs = Array.zeroCreate 1
              for i = 0 to 100000 do
                  xs.[0] <- Holder ref_value
]

Measure.run [ // тестирование скорости чтения

    "чтение элементов в массива",
    fun () -> let xs = [| "abc" |]
              for i = 0 to 100000 do
                  ignore xs.[0]

    "чтение обёрнутых элементов",
    fun () -> let xs = [| Holder "abc" |]
              for i = 0 to 100000 do
                  ignore xs.[0].Value
]

Результаты (у меня Core i3 380M @ 2533 Mhz), запись:

Чтение:

Оверхэд небольшой, конечно же, особенно с учётом того, что запись элемента массива сама по себе ооочень быстра. Однако в масштабах рантайма и фрэймворка, замедление в 1.5-2 раза всё же играет роль. Интересно, что проверка может быть устранена для массивов sealed-типов, однако на практике этого не происходит.

Данную технику оборачивания в тип-значение можно применять при реализации собственных изменяемых коллекций структур данных, базирующихся на массивах. Чтение из такого массива не имеет оверхэда (либо он меньше погрешности измерения).

— update —

Результаты Mono 2.10 for Windows немного отличаются (обратите внимание на заметно меньшее количество итераций):

Notes

  1. controlflow posted this