Получил очередные 10% производительности.
Что странно каждая оптимизация разгоняет парсер на ~10%...
Так же сделал поддержку полноценных FSM. Теперь в FSM закатывается не только ? но и * и +. Однако прироста производительности это не дало.
Нужно еще минимизацию FSM сделать. Это должно дать еще немножко прироста и уменьшить размер генерируемого кода.
Например сейчас генерируется вот такой код:
private __GENERATED_PEG__RULE__decimalIntegerLiteral__(pos : int, text : string) : int
{
unchecked
{
mutable (c : char);
_ = c;
{
def pos =
{
mutable okPos = -1;
mutable curPos = pos;
l0:
DEFAULT;
when (curPos >= text.Length) goto l5 [1];;
c = text[curPos];
++curPos;
when ('0' <= c && c <= '9') goto l1 [1];;
goto l5 [1];;
l1:
DEFAULT;
okPos = curPos;
when (curPos >= text.Length) goto l5 [1];;
c = text[curPos];
++curPos;
when ('0' <= c && c <= '9') goto l2 [1];;
goto l5 [1];;
l2:
DEFAULT;
okPos = curPos;
when (curPos >= text.Length) goto l5 [1];;
c = text[curPos];
++curPos;
when ('0' <= c && c <= '9') goto l2 [1];;
goto l5 [1];;
l4:
DEFAULT;
okPos = curPos;
l5:
DEFAULT;
okPos
};
if (pos >= 0)
{
def newPos =
{
__GENERATED_PEG__RULE__integerTypeSuffix__(pos, text)
};
if (newPos >= 0)
{
();
newPos
}; else
{
();
pos
}
}; else -1
}
}
}
Состояния l1 и l2 будут объеденены при минимизации ДКА. Тут мы получим только уменьшение кода. Но есть случаи (там кода много по этому не показываю) когда должен быть некоторый прирост производительности.
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
WH>Получил очередные 10% производительности. WH>Что странно каждая оптимизация разгоняет парсер на ~10%...
WH>Так же сделал поддержку полноценных FSM. Теперь в FSM закатывается не только ? но и * и +. Однако прироста производительности это не дало.
Так, а что дало то эти 10%?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Надеюсь это происходит только в релизе? А то не ясно как отлаживать парсеры.
Конечно. Все оптимизации только в релизе.
Ты кстати посморишь что там компилятору не нравится?
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Плюс, боюсь, что все несколько серьезнее и это может быть не баг. Возможно, что совать лэйблы в match просто не безопасно. При развороте для одного вхождения match-а может быть сгенерировано несколько участков кода которые будут дублировать содержимое вхождения. Если я прав, то устранить эту "ошибку" будет не просто.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Плюс, боюсь, что все несколько серьезнее и это может быть не баг. Возможно, что совать лэйблы в match просто не безопасно. При развороте для одного вхождения match-а может быть сгенерировано несколько участков кода которые будут дублировать содержимое вхождения. Если я прав, то устранить эту "ошибку" будет не просто.
Но парсер C# работает.
Проблема в настройках компилятора. Re: [PEG]Переделал генерацию FSM на goto.
Ну, так выкиньте DebugSymbols из релиза. Они, кстати, резко замедляют выполнение, так как по факту при этом сборке ставится атрибут отладочной (и оптимизация никогда не работает).
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, WolfHound, Вы писали:
WH>Нужно еще минимизацию FSM сделать. Это должно дать еще немножко прироста и уменьшить размер генерируемого кода. WH>Например сейчас генерируется вот такой код:
Прикрутил минимизацию. Скорости это не добавило но код маленько сдулся.
Теперь выглядит так:
private __GENERATED_PEG__RULE__decimalIntegerLiteral__(pos : int, text : string) : int
{
unchecked
{
mutable (c : char);
_ = c;
{
def pos =
{
mutable okPos = -1;
mutable curPos = pos;
l5968:
DEFAULT;
when (curPos >= text.Length) goto l5971 [1];;
c = text[curPos];
++curPos;
when ('0' <= c && c <= '9') goto l5969 [1];;
goto l5971 [1];;
l5969:
DEFAULT;
okPos = curPos;
when (curPos >= text.Length) goto l5971 [1];;
c = text[curPos];
++curPos;
when ('0' <= c && c <= '9') goto l5969 [1];;
goto l5971 [1];;
l5970:
DEFAULT;
okPos = curPos;
l5971:
DEFAULT;
okPos
};
if (pos >= 0)
{
def newPos =
{
__GENERATED_PEG__RULE__integerTypeSuffix__(pos, text)
};
if (newPos >= 0)
{
();
newPos
}; else
{
();
pos
}
}; else -1
}
}
}
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, VladD2, Вы писали:
VD>А что сейчас превращается в ДКА?
Строки, множества символов, ?, +, *, последовательность и выбор.
VD>Скажем если у нас есть вот такое правило: VD>
VD>то есть перечисление литералов содержащее внутри отрицательный предикат (смотри выделенное), оно будет превращено в ДКА?
Данное правило будет преобразованно частично.
Вот это будет преобразованно "++" / "--" / "+" / "-" / "~" / "!"
def newPos =
{
mutable okPos = -1;
mutable curPos = pos;
l6325:
DEFAULT;
when (curPos >= text.Length) goto l6330 [1];;
c = text[curPos];
++curPos;
when (c == '+') goto l6327 [1];;
when (c == '-') goto l6328 [1];;
when (c == '!' || c == '~') goto l6329 [1];;
goto l6330 [1];;
l6327:
DEFAULT;
okPos = curPos;
when (curPos >= text.Length) goto l6330 [1];;
c = text[curPos];
++curPos;
when (c == '+') goto l6329 [1];;
goto l6330 [1];;
l6328:
DEFAULT;
okPos = curPos;
when (curPos >= text.Length) goto l6330 [1];;
c = text[curPos];
++curPos;
when (c == '-') goto l6329 [1];;
goto l6330 [1];;
l6329:
DEFAULT;
okPos = curPos;
l6330:
DEFAULT;
okPos
};
Остальное нет.
Я просто не могу придумать как загнать в FSM предикат.
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
WH>Данное правило будет преобразованно частично. WH>Вот это будет преобразованно "++" / "--" / "+" / "-" / "~" / "!"
Тоже не плохо.
Значит надо предикаты стараться в конец списка ставить?
WH>Я просто не могу придумать как загнать в FSM предикат.
А можно в предикат засовывать ("++" / "--" / "+" / "-" / "~" / "!" / "&" !"&" / "*"), а потом состоянии сформированном для "&" !"&" делать дополнительную проверку?
Ведь на самом деле очень важно fail по первому символу.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Тоже не плохо. VD>Значит надо предикаты стараться в конец списка ставить?
Да.
VD>А можно в предикат засовывать ("++" / "--" / "+" / "-" / "~" / "!" / "&" !"&" / "*"), а потом состоянии сформированном для "&" !"&" делать дополнительную проверку?
Там все сложно. Я не знаю как это сделать.
Сейчас все просто.
Сначала делаем так:
mutable okPos = -1;
Когда попадаем в допускающее состояние делаем так
okPos = curPos;
Если у нас кончилась строка
when (curPos >= text.Length) goto l6330 [1];;
или попался символ по которому мы не можем никуда перейти переходим в конец и возвращаем okPos
l6330:
DEFAULT;
okPos
Таким образом если нам по пути попалось допускающее состояние то okPos будет показывать на конец сматченой строки.
Если нет то там будет -1.
Как закодировать предикат используя только это
public variant Transition
{
public From : int;
public To : int;
| Symbol { Chars : RangeSet }
| Epsilon
Я не знаю. ИМХО это просто не возможно.
Таким образом придется добавлять специальные переходы.
А это совершенно не предсказуемым образом скажется на DFSMTransform.n.
Сейчас алгоритмы трансформации НКА в ДКА и минимизации ДКА хоть и выглядят страшно (из-за того что приходится работать с интервалами) но реализуют классические алгоритмы.
Как на этих алгоритмах скажутся переходы о которых теория автоматов ничего не знает я даже представить боюсь.
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, hardcase, Вы писали:
H>Как думаешь, имеет смысл прикрутить FSM-трансформацию в компилятор для матча по строке?
Не знаю.
Нужно проводить измерения.
Вот что можно так это сделать макру типа такой:
peg match (str)
{
| "adasd" =>
| "asd"+ =>
| "num:" " "* ['0'..'9']+ as number : int =>
}
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
WH>Там все сложно... WH>...Как на этих алгоритмах скажутся переходы о которых теория автоматов ничего не знает я даже представить боюсь.
На хрен тут сложные теории? Если тебе дать на вход правило:
"++" / "--" / "+" / "-" / "~" / "!" / "&" / "*"
у тебя же проблем не возникнет?
И определить, что в итоге разобрано "&" твой код сможет ведь?
Ну, вот в этом переходе нужно добавить проверку предиката.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
