Может ли (прямой) оператор канала предотвратить оптимизацию хвостового вызова?
Для задачи оптимизации параметров на работе я написал генетический алгоритм, чтобы найти хорошие настройки, потому что решение методом перебора невозможно. К сожалению, когда я возвращаюсь утром, большую часть времени мне дают StackruException,
Я использую F# уже довольно давно, поэтому я знаю о TCO и необходимости использования функций с аргументами аккумулятора и обычно использую эту форму.
После долгих поисков я думаю, что смог найти код, который вызвал исключение:
breedPopulation alive |> simulate (generation + 1) lastTime ewma
breedPopulation генерирует новое поколение от людей в текущем alive один. Затем следующий раунд / поколение начинается с вызова simulate, Когда я смотрю на разборку (всего нуб), я замечаю некоторые pop и ret так что это не похоже на обычный (нехвостый) звонок мне.
mov rcx,qword ptr [rbp+10h]
mov rcx,qword ptr [rcx+8]
mov rdx,qword ptr [rbp-40h]
cmp dword ptr [rcx],ecx
call 00007FFA3E4905C0
mov qword ptr [rbp-0F0h],rax
mov r8,qword ptr [rbp-0F0h]
mov qword ptr [rbp-80h],r8
mov r8,qword ptr [rbp-78h]
mov qword ptr [rsp+20h],r8
mov r8d,dword ptr [rbp+18h]
inc r8d
mov rdx,qword ptr [rbp+10h]
mov r9,qword ptr [rbp-20h]
mov rcx,7FFA3E525960h
call 00007FFA3E4A5040
mov qword ptr [rbp-0F8h],rax
mov rcx,qword ptr [rbp-0F8h]
mov rdx,qword ptr [rbp-80h]
mov rax,qword ptr [rbp-0F8h]
mov rax,qword ptr [rax]
mov rax,qword ptr [rax+40h]
call qword ptr [rax+20h]
mov qword ptr [rbp-100h],rax
mov rax,qword ptr [rbp-100h]
lea rsp,[rbp-10h]
pop rsi
pop rdi
pop rbp
ret
После выбрасывания оператора трубопровода и установки селекции в нормальное положение параметров, разборка отличается.
// simulate (generation + 1) lastTime ewma (breedPopulation alive)
mov ecx,dword ptr [rbp+18h]
inc ecx
mov dword ptr [rbp-30h],ecx
mov rcx,qword ptr [rbp-20h]
mov qword ptr [rbp-38h],rcx
mov rcx,qword ptr [rbp-80h]
mov qword ptr [rbp-0F0h],rcx
mov rcx,qword ptr [rbp+10h]
mov rcx,qword ptr [rcx+8]
mov rdx,qword ptr [rbp-48h]
cmp dword ptr [rcx],ecx
call 00007FFA3E4605C0
mov qword ptr [rbp-0F8h],rax
mov rax,qword ptr [rbp-0F8h]
mov qword ptr [rbp+30h],rax
mov rax,qword ptr [rbp-0F0h]
mov qword ptr [rbp+28h],rax
mov rax,qword ptr [rbp-38h]
mov qword ptr [rbp+20h],rax
mov eax,dword ptr [rbp-30h]
mov dword ptr [rbp+18h],eax
nop
jmp 00007FFA3E47585B
Это определенно короче и с финалом jmp даже лучше, чем хвостовой вызов.
Поэтому я хочу понять, если и почему |> Кажется, это проблема, и когда это действительно имеет значение - в конце концов, это первый раз, когда он кусает меня после многих лет. При каких обстоятельствах это происходит и на что нам следует обращать внимание?
Обновление: после того, как Guy Coder указал, что мои списки не IL, а сборка, я сначала перефразировал вопрос. Вот что я узнал с помощью ILSpy:
С оператором |>
Глядя на декомпилированный C#, кажется, что код переходит вперед и назад между
internal static FSharpFunc<Types.Genome[], System.Tuple<System.Tuple<float, float>, LbpArea[]>[]> simulate@265-1(Universe x, System.Threading.ManualResetEvent pleaseStop, int generation, System.DateTime lastTime, FSharpOption<double> ewma)
{
return new $Universe.simulate@267-2(x, pleaseStop, generation, lastTime, ewma);
}
а также
// internal class simulate@267-2
public override System.Tuple<System.Tuple<float, float>, LbpArea[]>[] Invoke(Types.Genome[] population)
{
LbpArea[][] array = ArrayModule.Parallel.Map<Types.Genome, LbpArea[]>(this.x.genomeToArray, population);
FSharpFunc<System.Tuple<System.Tuple<float, float>, LbpArea[]>, float> accessFitness = this.x.accessFitness;
System.Tuple<System.Tuple<float, float>, LbpArea[]>[] array2 = ArrayModule.Filter<System.Tuple<System.Tuple<float, float>, LbpArea[]>>(new $Universe.alive@274(accessFitness), ArrayModule.Parallel.Map<LbpArea[], System.Tuple<System.Tuple<float, float>, LbpArea[]>>(new $Universe.alive@273-1(this.x), array));
if (array2 == null)
{
throw new System.ArgumentNullException("array");
}
System.Tuple<System.Tuple<float, float>, LbpArea[]>[] array3 = ArrayModule.SortWith<System.Tuple<System.Tuple<float, float>, LbpArea[]>>(new $Universe.alive@275-2(), array2);
this.x.Population = array3;
System.Tuple<System.DateTime, FSharpOption<double>> tuple = this.x.printProgress<float, LbpArea[]>(this.lastTime, this.ewma, this.generation, array3);
System.DateTime item = tuple.Item1;
FSharpOption<double> item2 = tuple.Item2;
if (this.pleaseStop.WaitOne(0))
{
return array3;
}
Types.Genome[] func = this.x.breedPopulation(array3);
return $Universe.simulate@265-1(this.x, this.pleaseStop, this.generation + 1, item, item2).Invoke(func);
}
В ИЛ new звонить нет tail. оп быть найдены. С другой стороны, IL из последних строк Invoke читать
IL_00d3: call class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<class BioID.GeneticLbp.Types/Genome[], class [mscorlib]System.Tuple`2<class [mscorlib]System.Tuple`2<float32, float32>, valuetype [BioID.Operations.Biometrics]BioID.Operations.Biometrics.LbpArea[]>[]> '<StartupCode$BioID-GeneticLbp>.$Universe'::'simulate@265-1'(class BioID.GeneticLbp.Universe, class [mscorlib]System.Threading.ManualResetEvent, int32, valuetype [mscorlib]System.DateTime, class [FSharp.Core]Microsoft.FSharp.Core.FSharpOption`1<float64>)
IL_00d8: ldloc.s 7
IL_00da: tail.
IL_00dc: callvirt instance !1 class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<class BioID.GeneticLbp.Types/Genome[], class [mscorlib]System.Tuple`2<class [mscorlib]System.Tuple`2<float32, float32>, valuetype [BioID.Operations.Biometrics]BioID.Operations.Biometrics.LbpArea[]>[]>::Invoke(!0)
IL_00e1: ret
Я не знаю, что с этим делать.
Без оператора |>
Другая версия действительно очень отличается. Начиная с
internal static System.Tuple<System.Tuple<float, float>, LbpArea[]>[] simulate@264(Universe x, System.Threading.ManualResetEvent pleaseStop, Unit unitVar0)
{
FSharpFunc<int, FSharpFunc<System.DateTime, FSharpFunc<FSharpOption<double>, FSharpFunc<Types.Genome[], System.Tuple<System.Tuple<float, float>, LbpArea[]>[]>>>> fSharpFunc = new $Universe.simulate@265-2(x, pleaseStop);
(($Universe.simulate@265-2)fSharpFunc).x = x;
(($Universe.simulate@265-2)fSharpFunc).pleaseStop = pleaseStop;
System.Tuple<System.Tuple<float, float>, LbpArea[]>[] population = x.Population;
Types.Genome[] func;
if (population != null && population.Length == 0)
{
func = x.lengthRandomlyIncreasing(x.laws@53.PopulationSize@);
return FSharpFunc<int, System.DateTime>.InvokeFast<FSharpOption<double>, FSharpFunc<Types.Genome[], System.Tuple<System.Tuple<float, float>, LbpArea[]>[]>>(fSharpFunc, 0, System.DateTime.Now, null).Invoke(func);
}
FSharpFunc<LbpArea[], Types.Genome> arrayToGenome = x.arrayToGenome;
func = ArrayModule.Parallel.Map<System.Tuple<System.Tuple<float, float>, LbpArea[]>, Types.Genome>(new $Universe.simulate@296-3(arrayToGenome), population);
return FSharpFunc<int, System.DateTime>.InvokeFast<FSharpOption<double>, FSharpFunc<Types.Genome[], System.Tuple<System.Tuple<float, float>, LbpArea[]>[]>>(fSharpFunc, 0, System.DateTime.Now, null).Invoke(func);
}
это идет к
// internal class simulate@265-2
public override System.Tuple<System.Tuple<float, float>, LbpArea[]>[] Invoke(int generation, System.DateTime lastTime, FSharpOption<double> ewma, Types.Genome[] population)
{
return $Universe.simulate@265-1(this.x, this.pleaseStop, generation, lastTime, ewma, population);
}
и наконец
internal static System.Tuple<System.Tuple<float, float>, LbpArea[]>[] simulate@265-1(Universe x, System.Threading.ManualResetEvent pleaseStop, int generation, System.DateTime lastTime, FSharpOption<double> ewma, Types.Genome[] population)
{
while (true)
{
// Playing evolution...
if (pleaseStop.WaitOne(0))
{
return array3;
}
// Setting up parameters for next loop...
}
throw new System.ArgumentNullException("array");
}
ТЛ; др
Таким образом, использование оператора канала радикально изменило ход программы. Я предполагаю, что обратное движение между двумя функциями в конечном итоге вызывает исключение.
Я уже читал Tail Calls в F#, но я не думаю, что это применимо к этой ситуации, так как я не использую первоклассную функцию, возвращающую единицу в качестве значения (в моем коде F#).
Таким образом, остается вопрос: почему оператор трубопровода имеет такой разрушительный эффект? Как я мог знать заранее / что мне нужно остерегаться?
Обновление 2:
Вы можете найти сокращенную версию примера на GitHub. Пожалуйста, убедитесь, что inline оператор |> изменяет производит IL, что не то, что я ожидал.
Сокращая пример, с небольшой удачей мне удалось найти реальный источник исключения. Вы можете проверить ветку для гораздо более минимального варианта. В конце концов, это не имеет никакого отношения к трубе, но я все еще не понимаю, потому что ИМХО есть хвостовая рекурсия.
Но мои оригинальные вопросы остаются. Я просто добавляю еще один.:)
1 ответ
Исходя из минимального предоставленного случая, если код выполняется в режиме выпуска в 64-разрядной версии, он завершается с ошибкой переполнения стека. Если код запускается в режиме выпуска в 32-разрядном режиме, это успешно выполняется.
Примечание: выбор между 32-битным и 64-битным Prefer 32-bit как видно на изображениях ниже.
Увеличение размера стека приведет к успешному выполнению кода в 64-разрядном режиме выпуска. Это делается с помощью конструктора Thread.
[<EntryPoint>]
let main _ =
let test () =
let r = KissRandom()
let n = r.Normal()
Seq.item 20000 n |> printfn "%f"
/// The greatest maximum-stack-size that should be used
/// with the 'runWithStackFrame' function.
let STACK_LIMIT = 16777216
/// Run a function with a custom maximum stack size.
/// This is necessary for some functions to execute
/// without raising a StackruException.
let runWithCustomStackSize maxStackSize fn =
// Preconditions
if maxStackSize < 1048576 then
invalidArg "stackSize" "Functions should not be executed with a \
maximum stack size of less than 1048576 bytes (1MB)."
elif maxStackSize > STACK_LIMIT then
invalidArg "stackSize" "The maximum size of the stack frame should \
not exceed 16777216 bytes (16MB)."
/// Holds the return value of the function.
let result = ref Unchecked.defaultof<'T>
// Create a thread with the specified maximum stack size,
// then immediately execute the function on it.
let thread = System.Threading.Thread ((fun () -> result := fn()), maxStackSize)
thread.Start ()
// Wait for the function/thread to finish and return the result.
thread.Join ()
!result
/// Runs a function within a thread which has an enlarged maximum-stack-size.
let inline runWithEnlargedStack fn =
runWithCustomStackSize STACK_LIMIT fn
// test () // Fails with stack overflow in 64-bit mode, Release
// Runs successfully in 32-bit mode, Release
runWithEnlargedStack test
printf "Press any key to exit: "
System.Console.ReadKey() |> ignore
printfn ""
0
Этот код взят из FSharp-logic-examples и, в частности, Anh-Dung Phan
Хотя я не проверил основную причину, я подозреваю, что это связано с тем, что размер элементов для 64-разрядных систем больше, чем размер элементов для 32-разрядных систем, хотя количество элементов, помещаемых в стек, и размер стека остается одинаковым для обеих версий, увеличение размера элемента увеличивает объем памяти, необходимый для стека, до предела в 1 мегабайт.
TL; DR
Это был забавный и поучительный вопрос. Я рад, что это спросили.
Первоначально проблема, казалось, была связана с использованием |> и TCO, и поскольку это все еще имеет значение, я оставляю это в ответе. Я также хотел бы поблагодарить ФП за отклик и помощь. Мне приятно помогать тому, кто работает с вами, а не против вас.
В следующем коде, который является рекурсивным и имеет |> запускается в режиме отладки в Visual Studio, это вызывает Stackru.
Если он запускается из командной строки из bin\release каталог это не вызывает Stackru.
Использование сообщества Visual Studio 15
[<EntryPoint>]
let main argv =
let largeList =
printfn "Creating large list"
[
for i in 1 .. 100000000 do
yield i
]
// causes Stackru in Debug
// No Stackru in Release
let sum4 l =
printfn "testing sum4"
let rec sumInner4 l acc =
match l with
| h::t ->
let acc = acc + h
acc |> sumInner4 t
| [] -> acc
sumInner4 l 0
let result4 = sum4 largeList
printfn "result4: %A" result4
Где Release или Debug установлены на панели инструментов Visual Studio
и варианты проекта в режиме отладки:
и варианты для проекта в режиме выпуска
tldr;
В процессе тестирования я создал 16 различных тестов и собрал их как в режиме отладки, так и в режиме выпуска, и проверил, добрались ли они до завершения или вызвали переполнение стека. 16 разбиты на набор из 4 с 4 случаями каждый. Случаи 1,5,9,13 являются отрицательными и вызывают переполнение стека, чтобы гарантировать возможность переполнения стека. Случаи 2,6,10,14 положительно показывают, что хвостовой вызов работает и не вызывает переполнения стека. В случаях 3,7,11,15 показан хвостовой вызов с операцией, выполненной в том же операторе, что и хвостовой вызов, и на расстоянии одной факторизации от тестовых случаев с использованием |>; эти работы, как и ожидалось. Случаи 4,8,12,16 использования |> и показывает, когда он работает и не работает в режиме отладки, что, вероятно, является неожиданностью для многих. Случаи 1-4 и 9-12 используют функцию вида f x y, случаи 8-11 используют функцию вида f x и случаи 12-16 используют функцию вида f x y z, Первоначально я сделал первые 8 тестовых случаев, но после комментария Кейта сделал еще 4, которые не используют список, но все еще используют функцию из f x y и представить неожиданный результат, а затем сделал еще 4, которые используют функцию вида f x y z,
Чтобы запустить тест, вам нужно закомментировать все тесты, кроме одного, который вы планируете запустить, и собрать его один раз в режиме отладки, который затем можно запустить из Visual Studio, а затем снова собрать его в режиме выпуска и запустить. Я запускаю его из командной строки, чтобы убедиться, что у меня запущенная версия.
[<EntryPoint>]
let main argv =
let largeList =
printfn "Creating large list"
[
for i in 1 .. 100000000 do
yield i
]
// causes Stackru in Debug
// causes Stackru in Release
// Negative confirmation
// A supposed tail call that DOES cause a stack overflow in both debug and release mode
// options: f x y
let sum1 l =
printfn "test 01: "
let rec sum1Inner l acc =
match l with
| h::t ->
let acc = acc + h
1 + sum1Inner t acc
| [] -> acc
sum1Inner l 0
// No Stackru in Debug
// No Stackru in Release
// Positive confirmation
// A tail call that DOES NOT cause a stack overflow in both debug and release mode
// options: f x y
let sum2 l =
printfn "test 02: "
let rec sum2Inner l acc =
match l with
| h::t ->
let acc = acc + h
sum2Inner t acc
| [] -> acc
sum2Inner l 0
// No Stackru in Debug
// No Stackru in Release
// A test case
// options: f x y and no |>
let sum3 l =
printfn "test 03: "
let rec sum3Inner l acc =
match l with
| h::t ->
sum3Inner t (acc + h)
| [] -> acc
sum3Inner l 0
// causes Stackru in Debug
// No Stackru in Release
// A test case
// options: f x y and |>
let sum4 l =
printfn "test 04: "
let rec sum4Inner l acc =
match l with
| h::t ->
let acc = acc + h
acc |> sum4Inner t
| [] -> acc
sum4Inner l 0
// causes Stackru in Debug
// causes Stackru in Release
// Negative confirmation
// A supposed tail call that DOES cause a stack overflow in both debug and release mode
// options: f x
let sum5 () =
printfn "test 05: "
let rec sum5Inner x =
match x with
| 10000000 -> x
| _ ->
let acc = x + 1
1 + sum5Inner acc
sum5Inner 0
// No Stackru in Debug
// No Stackru in Release
// Positive confirmation
// A tail call that DOES NOT cause a stack overflow in both debug and release mode
// options: f x
let sum6 () =
printfn "test 06: "
let rec sum6Inner x =
match x with
| 10000000 -> x
| _ ->
let acc = x + 1
sum6Inner acc
sum6Inner 0
// No Stackru in Debug
// No Stackru in Release
// A test case
// options: f x and no |>
let sum7 l =
printfn "test 07: "
let rec sum7Inner x =
match x with
| 10000000 -> x
| _ -> sum7Inner (x + 1)
sum7Inner 0
// No Stackru in Debug
// No Stackru in Release
// A test case
// options: f x and |>
let sum8 () =
printfn "test 07: "
let rec sumInner8 x =
match x with
| 10000000 -> x
| _ ->
let acc = x + 1
acc |> sumInner8
sumInner8 0
// causes Stackru in Debug
// causes Stackru in Release
// Negative confirmation"
// A supposed tail call that DOES cause a stack overflow in both debug and release mode"
// options: f x y"
let sum9 () =
printfn "test 09: "
let rec sum9Inner x y =
match y with
| 10000000 -> y
| _ ->
let acc = x + y
1 + sum9Inner x acc
sum9Inner 1 0
// No Stackru in Debug
// No Stackru in Release
// Positive confirmation
// A tail call that DOES NOT cause a stack overflow in both debug and release mode
// options: f x y
let sum10 () =
printfn "test 10: "
let rec sum10Inner x y =
match y with
| 10000000 -> y
| _ ->
let acc = x + y
sum10Inner x acc
sum10Inner 1 0
// No Stackru in Debug
// No Stackru in Release
// A test case
// options: f x y and no |>
let sum11 () =
printfn "test 11: "
let rec sum11Inner x y =
match y with
| 10000000 -> y
| _ ->
sum11Inner x (x + y)
sum11Inner 1 0
// causes Stackru in Debug
// No Stackru in Release
// A test case
// options: f x y and |>
let sum12 () =
printfn "test 12: "
let rec sum12Inner x y =
match y with
| 10000000 -> y
| _ ->
let acc = x + y
acc |> sum12Inner x
sum12Inner 1 0
// causes Stackru in Debug
// No Stackru in Release
// A test case"
// options: f x y and |>"
let sum12 () =
printfn "test 12: "
let rec sum12Inner x y =
match y with
| 10000000 -> y
| _ ->
let acc = x + y
acc |> sum12Inner x
sum12Inner 1 0
// causes Stackru in Debug
// causes Stackru in Release
// Negative confirmation"
// A supposed tail call that DOES cause a stack overflow in both debug and release mode"
// options: f x y"
let sum13 () =
printfn "test 13: "
let rec sum13Inner x z y =
match y with
| 10000000 -> y
| _ ->
let acc = x + y
1 + sum13Inner x z acc
sum13Inner 1 "z" 0
// No Stackru in Debug
// No Stackru in Release
// Positive confirmation"
// A tail call that DOES NOT cause a stack overflow in both debug and release mode"
// options: f x y"
let sum14 () =
printfn "test 14: "
let rec sum14Inner x z y =
match y with
| 10000000 -> y
| _ ->
let acc = x + y
sum14Inner x z acc
sum14Inner 1 "z" 0
// No Stackru in Debug
// No Stackru in Release
// A test case"
// options: f x y and no |>"
let sum15 () =
printfn "test 15: "
let rec sum15Inner x z y =
match y with
| 10000000 -> y
| _ ->
sum15Inner x z (x + y)
sum15Inner 1 "z" 0
// causes Stackru in Debug
// No Stackru in Release
// A test case"
// options: f x y and |>"
let sum16 () =
printfn "test 16: "
let rec sum16Inner x z y =
match y with
| 10000000 -> y
| _ ->
let acc = x + y
acc |> sum16Inner x z
sum16Inner 1 "z" 0
let result1 = sum1 largeList
printfn "result1: %A" result1
let result2 = sum2 largeList
printfn "result2: %A" result2
let result3 = sum3 largeList
printfn "result3: %A" result3
let result4 = sum4 largeList
printfn "result4: %A" result4
let result5 = sum5 ()
printfn "result5: %A" result5
let result6 = sum6 ()
printfn "result6: %A" result6
let result7 = sum7 ()
printfn "result7: %A" result7
let result8 = sum8 ()
printfn "result8: %A" result8
let result9 = sum9 ()
printfn "result9: %A" result9
let result10 = sum10 ()
printfn "result10: %A" result10
let result11 = sum11 ()
printfn "result11: %A" result11
let result12 = sum12 ()
printfn "result12: %A" result12
let result13 = sum13 ()
printfn "result13: %A" result13
let result14 = sum14 ()
printfn "result14: %A" result14
let result15 = sum15 ()
printfn "result15: %A" result15
let result16 = sum16 ()
printfn "result16: %A" result16
printf "Press any key to exit: "
System.Console.ReadKey() |> ignore
printfn ""
0 // return an integer exit code