F # ref-mutable переменные против полей объекта - PullRequest
Новая
       28

F # ref-mutable переменные против полей объекта

3 голосов
/ 31 мая 2010

Я пишу синтаксический анализатор на F #, и он должен быть максимально быстрым (я надеюсь проанализировать файл размером 100 МБ менее чем за минуту). Как обычно, он использует изменяемые переменные для хранения следующего доступного символа и следующего доступного токена (т.е. как лексер, так и собственно синтаксический анализатор используют одну единицу просмотра).

Моя текущая частичная реализация использует локальные переменные для них. Поскольку переменные замыкания не могут быть изменяемыми (кто-нибудь знает причину этого?), Я объявил их как ref: 

let rec read file includepath =
    let c = ref ' '
    let k = ref NONE
    let sb = new StringBuilder()
    use stream = File.OpenText file

    let readc() =
        c := stream.Read() |> char
    // etc

Я предполагаю, что это имеет некоторые накладные расходы (не очень, я знаю, но я пытаюсь добиться максимальной скорости здесь), и это немного не элегантно. Наиболее очевидной альтернативой было бы создание объекта класса анализатора и наличие в нем изменяемых переменных, являющихся полями. Кто-нибудь знает, что может быть быстрее? Есть ли какой-то консенсус, по которому считается лучший / более идиоматический стиль? Есть ли другой вариант, который мне не хватает?

Ответы [ 2 ]

5 голосов
/ 31 мая 2010

Вы упомянули, что локальные изменяемые значения не могут быть захвачены замыканием, поэтому вам нужно использовать ref вместо этого. Причина этого заключается в том, что изменяемые значения, захваченные в замыкании, должны быть распределены в куче (поскольку замыкание выделяется в куче).

F # заставляет вас написать это явно (используя ref). В C # вы можете «захватить изменяемую переменную», но компилятор преобразует ее в поле в выделенном куче объекте за сценой, так что он все равно будет в куче.

Сводка: Если вы хотите использовать замыкания, переменные должны быть размещены в куче.

Теперь, что касается вашего кода - ваша реализация использует ref, который создает небольшой объект для каждой изменяемой переменной, которую вы используете. Альтернативой может быть создание одного объекта с несколькими изменяемыми полями. Используя записи, вы можете написать: 

type ReadClosure = {
  mutable c : char
  mutable k : SomeType } // whatever type you use here

let rec read file includepath = 
  let state = { c = ' '; k = NONE } 
  // ... 
  let readc() = 
    state.c <- stream.Read() |> char 
    // etc...

Это может быть немного более эффективно, потому что вы выделяете один объект вместо нескольких объектов, но я не ожидаю, что разница будет заметна.

Есть и одна запутанная вещь в вашем коде - значение stream будет удалено после возврата функции read, поэтому вызов stream.Read может быть недопустимым (если вы вызываете readc после read завершается). 

let rec read file includepath =    
  let c = ref ' '    
  use stream = File.OpenText file    
  let readc() =    
    c := stream.Read() |> char    
  readc

let f = read a1 a2
f() // This would fail!

Я не совсем уверен, как вы на самом деле используете readc, но об этой проблеме может подумать. Кроме того, если вы объявляете его только как вспомогательное закрытие, вы, вероятно, можете переписать код без закрытия (или написать его явно, используя tail-recursion, который переводится в императивный цикл с изменяемыми переменными), чтобы избежать каких-либо выделений.

4 голосов
/ 31 мая 2010

Я сделал следующее профилирование: 

let test() = 
    tic()
    let mutable a = 0.0
    for i=1 to 10 do
        for j=1 to 10000000 do
            a <- a + float j
    toc("mutable")
let test2() = 
    tic()
    let a = ref 0.0
    for i=1 to 10 do
        for j=1 to 10000000 do
            a := !a + float j
    toc("ref")

среднее значение для изменяемого - 50 мс, а реф 600 мс. Разница в производительности связана с тем, что изменяемые переменные находятся в стеке, а переменные ref - в управляемой куче.

Относительная разница большая. Тем не менее, 10 ^ 8 раз доступа это большое число. И общее время приемлемо. Так что не стоит слишком беспокоиться о производительности переменных ref. И помните:

Преждевременная оптимизация - корень все зло.

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

Еще один пример, мы ежедневно используем массивы .net, которые также находятся в управляемой куче: 

let test3() = 
    tic()
    let a = Array.create 1 0.0
    for i=1 to 10 do
        for j=1 to 10000000 do
            a.[0] <- a.[0] + float j
    toc("array")

test3 () работает примерно так же, как и ref. Если вы слишком беспокоитесь о переменных в управляемой куче, вы больше не будете использовать массив.

...