Интересно почему для match генерится такой не оптимальный код, например:
[Record]
public variant DecisionNode
{
| Condition
{
condition : GuardNode;
body : DecisionNode;
else_node : DecisionNode;
}
| Action
{
condition : option[GuardNode];
body : DecisionNode;
}
| Else
{
body : DecisionNode;
}
| Target
{
target : TransitionTarget;
destination : TransitionDestination;
}
}
public Fold[T](init : T,
cond : T * GuardNode * Condition -> T,
els : T * Else -> T,
targ : T * TransitionTarget * TransitionDestination * Target -> T,
act : T * option[GuardNode] * DecisionNode.Action -> T) : T
{
def loop(e, acc, cont)
{
match (e)
{
| Target(x, d) as t => cont(targ(acc, x, d, t))
| Condition(c, b, e) as t => loop(b, acc, bacc =>
loop(e, bacc, eacc =>
cont(cond(eacc, c, t))))
| Else(b) as t => loop(b, acc, bacc => cont(els(bacc, t)))
| Action(c, b) as t => loop(b, acc, bacc => cont(act(bacc, c, t)))
}
}
loop(this, init, x => x)
}
здесь обычный перебор веток варианта в match, в рефлекторе он генерит такой код:
if (!(e is Condition))
{
if (!(e is Action))
{
if (!(e is Else))
{
if (!(e is Target))
{
throw new MatchFailureException();
}
Target t = (Target) e;
int x = ((Target) e).target;
int d = ((Target) e).destination;
return e_._N_cont_4406.apply(_N_xnode_4367(_N_FoldThis_cp_4381._N_targ_4361.apply(x, d, t), null, null, t));
}
то есть он смотрит оператором is те ли это типы, не проще ли использовать _N_GetVariantCode(), и по нему узнавать что это за экземпляр?
Здравствуйте, CodingUnit, Вы писали:
CU>то есть он смотрит оператором is те ли это типы, не проще ли использовать _N_GetVariantCode(), и по нему узнавать что это за экземпляр?
_N_GetVariantCode используется при генерировании switch конструкции. Минимальное количество вариантов, входящих в матч настраивается опцией компилятора -min-switch-size-variants. Видимо использовать _N_GetVariantCode нужно не только для построения switch-таблицы, но и для построения дерева выбора (уже не помню, но я хотел сделать эту оптимизацию).
Здравствуйте, hardcase, Вы писали:
H>Здравствуйте, hardcase, Вы писали:
H>В любом случае нужно бенчмаркнуть это, не факт что оптимизация оправдает себя.
Там всего лишь один виртуальный вызов def code : int = GetVariantCode();
Далее проверяем его в каждом вложении, это наверное лучше чем проверять 4 раза is, Влад говорит есть тема раньше когда этот вопрос поднимали но я не могу найти.
Здравствуйте, CodingUnit, Вы писали:
CU>Там всего лишь один виртуальный вызов def code : int = GetVariantCode(); CU>Далее проверяем его в каждом вложении, это наверное лучше чем проверять 4 раза is, Влад говорит есть тема раньше когда этот вопрос поднимали но я не могу найти.
Нужно просто бенчмаркнуть и лишь после этого править матчкомпилер (если оно того стоит), — с ходу влезание в его код способен сорвать крышу у неподготовленного читателя
Влад видимо имеет в виду тему про cil switch
З.Ы. Вообще стоит отдельно подумать над разработкой DSL описаний этих оптимизаций (этакий мини-PEG), ибо существующий код тяжко поддается исправлениям.
Здравствуйте, hardcase, Вы писали:
H>З.Ы. Вообще стоит отдельно подумать над разработкой DSL описаний этих оптимизаций (этакий мини-PEG), ибо существующий код тяжко поддается исправлениям.
Более того, код матчкомпилера существенно влияет на скорость компиляции, это тот еще boilerplate!
/* иЗвиНите зА неРовнЫй поЧерК */
Re[6]: match по вариантным опциям
От:
Аноним
Дата:
21.11.11 11:12
Оценка:
Здравствуйте, hardcase, Вы писали:
"З.Ы. Вообще стоит отдельно подумать над разработкой DSL описаний этих оптимизаций (этакий мини-PEG), ибо существующий код тяжко поддается исправлениям."
Здравствуйте, hardcase, Вы писали:
H>Нужно просто бенчмаркнуть и лишь после этого править матчкомпилер (если оно того стоит), — с ходу влезание в его код способен сорвать крышу у неподготовленного читателя H>Влад видимо имеет в виду тему про cil switch
H>З.Ы. Вообще стоит отдельно подумать над разработкой DSL описаний этих оптимизаций (этакий мини-PEG), ибо существующий код тяжко поддается исправлениям.
Набросал простенький тест:
public VarTest(node : DecisionNode) : int
{
def loop(e)
{
match (e)
{
| DecisionNode.Condition(c, _, _) as t => c
| Target(x, d) => x * d
| Action(_, _) => 1
| _ => 0
}
}
loop(node)
}
public VarTest2(node : DecisionNode) : int
{
def loop(e)
{
def code = e._N_GetVariantCode();
match (code)
{
| 0 => def c = e :> DecisionNode.Condition;c.condition
| 1 => 1
| 2 => def c = e :> DecisionNode.Target;c.target * c.destination
| _ => 0
}
}
loop(node)
}
Main() : void
{
def tree = DecisionNode.Target(4, 2, 2);
def timer = Stopwatch();
timer.Start();
foreach (_ in [0..10000]) _ = VarTest(tree);
timer.Stop();
def time1 = timer.Elapsed;
timer.Restart();
foreach (_ in [0..10000]) _ = VarTest2(tree);
timer.Stop();
def time2 = timer.Elapsed;
WriteLine($"time1: $time1 . time2: $time2");
}
Порядок следования вхождений аналогичен, я подеменял экземпляр tree на разные вхождения, результаты следующие:
для постоянного первого вхождения:
is _N_GetVariantCode
4954 5604
4812 5546
4821 5533
то есть _N_GetVariantCode уступает
для второго:
6684 5413
5565 5507
5426 5391
5462 5381
примерно равны
для третьего:
6862 5795
6843 5762
6914 5811
7053 5837
то есть результат значительно лучше
Для четырех и более я думаю ситуация должна быть примерно такой же, _N_GetVariantCode относительно стабилен, но медленее при самом первом вхождении (видимо сказывается виртуальный вызов). Далее когда происходит непосредственный перебор _N_GetVariantCode уже меняет очень слабо показания, держит примерно на одном уровне и почти не зависит от количества вхождений. is видимо при однократном его вызове в теле быстрее, но его постоянное применение сильно сказывается на производительности, да еще в связках с as.
Поэтому я думаю для программ где требуется большое количество вхождений использование _N_GetVariantCode сильно дает прирост производительности независимо от количества вхождений, порядка их следования и выбираемых веток. Стоит подумать внедрить его в компилятор, хотя бы для начала как тест. Я думаю на компиляции это может сильно сказаться в лучшую сторону.
Здравствуйте, CodingUnit, Вы писали:
CU>Поэтому я думаю для программ где требуется большое количество вхождений использование _N_GetVariantCode сильно дает прирост производительности независимо от количества вхождений, порядка их следования и выбираемых веток. Стоит подумать внедрить его в компилятор, хотя бы для начала как тест. Я думаю на компиляции это может сильно сказаться в лучшую сторону.
Если бы ты внимательно читал мои сообщеня, то заметил, что _N_GetVariantCode используется, но для построения switch опкода (таблица строится от 10 вариантов). В принципе понятно — сравнивать по этому коду деревом if-ов нужно и для меньшего количества вариантов (по видимому от 3-4х вхождений).
Здравствуйте, hardcase, Вы писали:
H>Здравствуйте, CodingUnit, Вы писали:
CU>>Поэтому я думаю для программ где требуется большое количество вхождений использование _N_GetVariantCode сильно дает прирост производительности независимо от количества вхождений, порядка их следования и выбираемых веток. Стоит подумать внедрить его в компилятор, хотя бы для начала как тест. Я думаю на компиляции это может сильно сказаться в лучшую сторону.
H>Если бы ты внимательно читал мои сообщеня, то заметил, что _N_GetVariantCode используется, но для построения switch опкода (таблица строится от 10 вариантов). В принципе понятно — сравнивать по этому коду деревом if-ов нужно и для меньшего количества вариантов (по видимому от 3-4х вхождений).
H>З.Ы. связка операторов is/as оптимизируется JIT-ом.
Отлично, да прирост может быть и для нескольких вхождений, поэтому я заведу issue на баг трекере с описанием задачи, которую надо будет решить.
Здравствуйте, CodingUnit, Вы писали:
CU>я заведу issue на баг трекере с описанием задачи, которую надо будет решить.
Дык, если тебе интересно — можешь закопаться в код. Начать размышления нужно отсюда — это место, где происходит принятие решния о построении switch таблицы.
Здравствуйте, hardcase, Вы писали:
H>Здравствуйте, CodingUnit, Вы писали:
CU>>я заведу issue на баг трекере с описанием задачи, которую надо будет решить.
H>Дык, если тебе интересно — можешь закопаться в код. Начать размышления нужно отсюда — это место, где происходит принятие решния о построении switch таблицы.
Я бы закопался Ты лучше скажи когда ты меня в скайп добавишь, я тебе уже второй запрос сделал.