Почему не все тестовые задания одинаково полезны: разбор одного фееричного провала
Всем привет, это PsyHaSTe и сегодня я хотел бы рассказать о том, куда меня занесла нелегкая в процессе оптимизации и рефакторинга кода решения тестового задания из статьи товарища novar (кто пропустил — рекомендую ознакомиться). Какие проблемы были у этого решения? Почему все-таки человеку отказали в работе? Что можно с этим сделать? Ответы на эти и многие другие вопросы оказались слишком длинными для комментария и вылились в статью с подробным разбором, примерами и альтернативной реализацией задания.
Если вам интересно кто в здравом уме мог для выполнения поставленной задачи написать код сочетающий монады с goto, а также одновременно сократил объем кода и увеличил его производительность, то добро пожаловать под кат. И, конечно же, самое вкусное, связанное с оптимизациями на базе работы JIT — в конце.
Итак, начнем с изначальной постановки задачи. Т.к. в исходной постановке она звучит как «сделай то не знаю что, см. вложение» то дам краткую выжимку на основании этого самого тестового задания:
Реализовать класс для задания и расчета времени по расписанию. Расписание задано в стиле crontab (точный формат см. во вложении), требуется находить ближайшие в будущем или прошлом моменты, попадающие в это расписание. Обращаю Ваше внимание, что класс должен быть эффективным и не использовать много памяти и ресурсов даже тогда, когда в расписании задано много значений. Например очень много значений с шагом в одну миллисекунду.
Класс (без километровых XML комментов) который нам предлагается реализовать выглядит так:
public class Schedule
{
public Schedule() : this("*.*.* * *:*:*.*")
{
}
public Schedule(string scheduleString) { }
public DateTime NearestEvent(DateTime t1) { }
public DateTime NearestPrevEvent(DateTime t1) { }
public DateTime NextEvent(DateTime t1) { }
public DateTime PrevEvent(DateTime t1) { }
}Пожалуй, начнем со своей реализации, а потом сравним с версией из оригинальной статьи.
Что мы тут видим? В частности, конструктор отделен от использования. Это нас должно навести на мысль, что операция парсинга происходит не так часто, т.к. нам имеет смысл создать инстанс с разобранным расписанием. Откуда можно заключить, что основные оптимизации (и эффективность) должны касаться занимаемого в памяти места и времени работы методов (но не конструктора). Почему? Как минимум, потому что у нас дан класс Schedule, а для авторов тестового задания было бы странно говорить про эффективность типа, который постоянно нагружает GC — логичнее было бы использовать структуру. Ну и в целом, с точки зрения здравого смысла логично, что расписания задаются не так часто, как по ним ищут (можно посмотреть на практику использования того же крона, формат которого нам предлагают реализовать). Следовательно, конструктор вызывается сравнительно редко.
С этим решили. Теперь нам нужно выбрать структуру данных, по которой можно эффективно искать расписания. «Список событий» мы отметаем сразу из-за ремарки про 1 мс интервалы — можно посчитать сколько миллисекунд с 2000 по 2100 год (диапазон дат из нашего задания), это слишком дофига. Поэтому, вооружившись гуглом, идем и смотрим, как реализовали «правильные ребята». Я лично для этого ознакомился с двумя файлами: файлами самого крона и библиотекой Quartz. Откуда заключаем, что самый разумный формат — просто хранить признаки подходит ли нам некоторая временная точка (год, день, …) или нет. Вооружившись магией ООП берем и за 2 минуты реализуем нужный функционал:
public readonly struct ScheduleInterval
{
public int Begin { get; }
public int End { get; }
private readonly bool[] _allowedPoints;
public ScheduleInterval(int begin, int end)
{
Begin = begin;
End = end;
_allowedPoints = new bool[end - begin + 1];
}
public bool IsPointAllowed(int point) =>
_allowedPoints[point - Begin];
public bool ChangePointAllowance(int point, bool value) =>
_allowedPoints[point - Begin] = value;
// пара вспомогательных методов опущена
}Отлично, у нас есть замечательная структура, по которой удобно искать. Но на входе у нас всего лишь строка. Как нам из одного получить другое? Ну, на самом деле у нас есть несколько вариантов, по пунктам:
- Писать разбор руками — долго, муторно, подвержено ошибкам. А ещё очень долго. Из плюсов — можно выжать максимальный перформанс, максимальную гибкость (важно для бектрекинга, хороших ошибок и всего этого). Но, мы не компилятор пишем, поэтому плюсы нам не очень важны (вспоминая, что парсинг вызывается только в конструкторе), а вот минусы очень жесткие. Тем более, что в рамках тестового мы ограничены по времени. Поэтому — нет
- Писать разбор регулярками — во-первых, учитывая все нюансы формата, регуляркой парсить её замучаешься. Во-вторых, реуглярка фигово композируется — да, можно куски объявить строковыми константами и потом интерполировать куда-то в результирующую регулярку, но моя практика показывает, что обычто это совершенно нечитаемо выходит. И в-третьих, сам результат работы реуглярки придется парсить — из всех этих матчей придется выдирать группы, пытаться сопоставить их друг с другом. Вариадичность формата добивает окончательно.
- Писать разбор парсер-генератором — это всякие ANTLR и т.п. — моё скромное ИМХО что это оверкилл для такой задачи. В целом можно было бы использовать, но я не очень уверенно себя чувствую в декларативном написании грамматик
- Писать разбор парсер-комбинатором —, а вот это уже более-менее. Производительность разбора приемлемая (хотя существенно медленнее, чем ручной разбор), легко композируется, легко эмбедится в решение. Пожалуй, его и возьмем. Что там в дотнете есть? Окей гугл, «parser combinator C#». О, некий Pidgin в первой строчке. Звезд достаточно, последние коммиты свежие — берём.
Парсер-комбинатор
Итак, что такое парсер-комбинатор? Это простой монадический тип, который позволяет описывать преобразование из потока токенов (в нашем случае char[]) в некий структурированный вывод. За счет своей монадичности (т.е. композабельности) их можно сцеплять друг с другом, получая более продвинутые парсеры. Чем мы и займемся. Начнем с простого — научимся парсить звёздочки.
// вспомогательный класс, который будет хранить наши парсеры
public static class ParserHelper
{
// Парсер встречает значение char '*' Результат парсера - юнит (т.е. тип, имеющий ровно одно значение)
// брат близнец void, но в отличие от него может использоваться вездве, где ожидается тип
public static Parser Asterisk { get; } =
Char('*').Map(_ => Unit.Value);
} Отлично, давайте напишем пару тестов, чтобы удостовериться, что мы не ошиблись:
[Fact]
public void Asterisk()
{
ParserHelper.Asterisk.ParseOrThrow("*");
Assert.Throws(() =>
ParserHelper.NumberParser.ParseOrThrow("hello"));
} Отлично, парсинг успешен. Теперь нам нужно научиться парсить цифры. Нет ничего проще:
// парсим список цифр, идущих подряд. Парсим получившуюся последовательность как int
Parser NumberParser { get; } =
Digit.AtLeastOnce().Map(s => int.Parse(new string(s.ToArray()))); Хорошо, теперь мы и цифры умеем парсить. Что дальше? Теперь нам нужно научиться парсить интервал из двух цифр, разделенными дефисом. Обратим внимание, что цифра »12» должна трактоваться как интервал »12-null», т.е. мы должны разрешить концу интервала отсутствовать. Опять же, реализуем:
Parser IntervalParser { get; } =
from begin in NumberParser
from end in Char('-').Then(NumberParser).Optional()
select (begin, end); О, а это уже интереснее. Что LINQ у нас тут делает? А вот и наша монадичность проявилась — чтобы скомбинировать наши парсеры мы можем воспользоваться ду-нотацией (которая в простонародье в .Net мире называется LINQ syntax) и построить более сложный парсер на базе простых. Подробнее про связь LINQ, монад и прочих высоких материй с нашими колхозными языками я писал тут.
Итак, вернемся к нашему парсеру. Что же он делает? Сначала мы пытаемся попарсить первое число. Если у нас не удалось этого сделать то парсер сразу же завершиться с ошибкой. Если же удалось, то мы можем перейти ко второй строчке вычисления и выполнить Char('-').Then(NumberParser) — то есть попробовать попарсить число, следующее за дефисом. Т.к. в случае ошибки мы хотим получить null (а не ошибку парсинга) то добавляем Optional. Ну и в конце описываем, в каком виде мы хотим получить результат — в моем случае, тапл из инта и нуллейбл инта для начала и конца интервала соответственно.
Замечательно, написали тесты, убедились, что умеем теперь парсить интервалы. Что там у нас ещё было. Ага, шаг интервала. Пишется через /, может основываться либо на открытом интервале *, либо на диапазоне. Ну что ж, так и запишем… Хотя давайте сначала отдельный тип для этого заведем, а то таплы на 3 аргументы уже некрасиво в публичном апи выглядят:
public record ScheduleFormatEntry(int? Begin, int? End, int? Step);Теперь можно и парсер записать:
Parser WholeIntervalParser { get; } =
from interval in
Asterisk.Map(_ => (begin: default(int?), end: default(int?)))
.Or(IntervalParser.Map(x => ((int?) x.begin, x.end)))
from step in Char('/').Then(NumberParser).Optional()
select new ScheduleFormatEntry(interval.begin, interval.end, step); Код достаточно самоочевидный: сначала пытаемся пропарсить звездочку, если не вышло, то парсим то же место уже как диапазон чисел. Звездочку маппим на пару из двух нуллов, а интервал оставляем как есть, только первый компонент конвертируем int -> int?, иначе типы не сходятся. Затем смотрим, есть ли шаг интервала: если нет, то записываем в шаг null, если есть то его и указываем.
Снова тесты, снова все работает, просто потому что мы сложного ничего не делаем: мы начинали с элементарных кубиков (звездочка/циферки), а затем просто собираем их вместе в более мощные абстракции. Сила монад! Кстати. прошу обратить внимание, насколько просто и естественно в ду нотации выглядит код: просто пишем сделай то, сделай это, а об ошибке оно позаботиться само, в фоне. Просто берешь и описываешь желаемую логику, а как добиться нужного результата монада догадается сама, т.к. интерпретация заложена в ней самой и не засоряет код. Чем-то похоже на АОП, которое лет 10 назад у всех на слуху было.
Так, интервалы мы умеем парсить, что дальше? Список интервалов! Ну, что просят то и пишем:
Parser IntervalsSequenceParser { get; } =
WholeIntervalParser.SeparatedAndOptionallyTerminatedAtLeastOnce(Char(','))
.Map(x => x.ToArray())
.SelectMany(ValidateWildcards(), ((entries, _) => entries)); Ради разнообразия записал парсер не используя do нотацию. Тут мы просто говорим, что список интервалов — это результат применения парсера одного интервала на нескольких элементах, разделенными запятой. Ну и для каждого затем прогоняем валидацию, что в интервале не более одной звездочки, запрещая комбинации вроде 1,2,*,3-5,*.
В общем, остальные парсеры пишутся совершенно аналогично и в результате дописываем парсеры даты, дня недели и времени (а также соответствующие формату вспомогательные структуры):
Parser DateParser { get; } =
from years in Validate(IntervalsSequenceParser, ValidateBoundsParser("Year", Constant.MinYear, Constant.MaxYear))
from _ in Char('.')
from months in Validate(IntervalsSequenceParser, ValidateBoundsParser("Month", Constant.MinMonth, Constant.MaxMonth))
from __ in Char('.')
from days in Validate(IntervalsSequenceParser, ValidateBoundsParser("Day", Constant.MinDay, Constant.MaxDay))
select new ScheduleDate(years, months, days);
Parser DayOfWeekParser { get; } =
Validate(IntervalsSequenceParser, ValidateBoundsParser("Day of week", Constant.MinDayOfWeek, Constant.MaxDayOfWeek));
Parser TimeParser { get; } =
from hours in Validate(IntervalsSequenceParser, ValidateBoundsParser("Hour", Constant.MinHour, Constant.MaxHour))
from _ in Char(':')
from min in Validate(IntervalsSequenceParser, ValidateBoundsParser("Min", Constant.MinMinute, Constant.MaxMinute))
from __ in Char(':')
from sec in Validate(IntervalsSequenceParser, ValidateBoundsParser("Sec", Constant.MinSec, Constant.MaxSec))
from millis in Char('.').Then(Validate(IntervalsSequenceParser, ValidateBoundsParser("Millis", Constant.MinMillis, Constant.MaxMillis)))
.Optional()
select new ScheduleTime(hours, min, sec, millis ?? new[] {ScheduleFormatEntry.SinglePoint(0)});
Parser FullFormatParser { get; } =
from date in Try(DateParser).Before(Char(' ')).Optional()
from dayOfWeek in Try(DayOfWeekParser.Before(Char(' '))).Optional()
from time in TimeParser
select new ScheduleFormat(
date ?? new ScheduleDate(
new []{ScheduleFormatEntry.Always},
new []{ScheduleFormatEntry.Always},
new []{ScheduleFormatEntry.Always}
),
dayOfWeek ?? new []{ScheduleFormatEntry.Always},
time); В комментариях, пожалуй, нуждается только последний. По заданию у нас компоненты даты и дня недели являются необязательными. Если мы их не смогли распарсить, значит их не было и мы используем значение «звёздочка» по-умолчанию. Т.е. если компонент не задан, это эквивалетно * во всех позициях, где это возможно. Звездочка в наших вспомогательных структурах задается значением ScheduleFormatEntry.Always. Единственной сложностью тут является валидация границ значений в каждом, но валидация — это всегда боль и печаль. Если бы мы её убрали то получилось бы вот настолько просто:
Parser TimeParser { get; } =
from hours in IntervalsSequenceParser
from _ in Char(':')
from min in IntervalsSequenceParser
from __ in Char(':')
from sec in IntervalsSequenceParser
from millis in Char('.').Then(IntervalsSequenceParser).Optional()
select new ScheduleTime(
hours,
min,
sec,
millis ?? new[] {ScheduleFormatEntry.SinglePoint(0)}); Засим мы завершаем наше знакомство с монадами, поскольку наш FullFormatParser умеет парсить всё, что требовалось по заданию. И пора переходить к следующей части
Вспомните, что наш исходный формат выглядел как набор точек во времени с признаком разрешено/запрещено, а мы попарсили кучу непонятных интервалов вида «начало-конец-шаг». Что делаем? Правильно, преобразуем одно в другое:
public record MergedSchedule(
ScheduleInterval Years,
ScheduleInterval Months,
ScheduleInterval Days,
ScheduleInterval DayOfWeek,
ScheduleInterval Hours,
ScheduleInterval Minutes,
ScheduleInterval Seconds,
ScheduleInterval Milliseconds)
{
public static MergedSchedule FromFormat(ScheduleFormat format) =>
{
return new(
GetMerged(format.Date.Years, Constant.MinYear, Constant.MaxYear),
GetMerged(format.Date.Months, Constant.MinMonth, Constant.MaxMonth),
GetMerged(format.Date.Days, Constant.MinDay, Constant.MaxDay),
GetMerged(format.DayOfWeek, Constant.MinDayOfWeek, Constant.MaxDayOfWeek),
GetMerged(format.Time.Hours, Constant.MinHour, Constant.MaxHour),
GetMerged(format.Time.Minutes, Constant.MinMinute, Constant.MaxMinute),
GetMerged(format.Time.Seconds, Constant.MinSec, Constant.MaxSec),
GetMerged(format.Time.Milliseconds, Constant.MinMillis, Constant.MaxMillis)
);
}
private static ScheduleInterval GetMerged(ScheduleFormatEntry[] intervals, int begin, int end)
{
if (intervals.Length == 1 && intervals[0] == ScheduleFormatEntry.Always)
{
return ScheduleInterval.CreateAllowedInterval(begin, end);
}
var result = new ScheduleInterval(begin, end);
foreach (var scheduleFormatEntry in intervals)
{
var (b, e, s) = (scheduleFormatEntry.Begin,
scheduleFormatEntry.End,
scheduleFormatEntry.Step) switch
{
(null, null, {} s1) => (begin, end, s1),
({} b2, null, null) => (b2, b2, 1),
({} b3, {} e3, null) => (b3, e3, 1),
({} b4, {} e4, {} s4) => (b4, e4, s4),
_ => throw new InvalidOperationException(
$"Bad period {scheduleFormatEntry} cannot be parsed")
};
for (int i = b; i <= e; i += s)
{
result.ChangePointAllowance(i, true);
}
}
return result;
}
}Не надо пугаться, тут много копипасты из-за особенностей задачи., но в целом ничего сложного не происходит: мы просто идем по всем интервалам и проставляем булев признак — разрешено ли значение в этой дате или нет. Конечно же, на все пишем тесты, они помогут понять, правильно ли мы реализовали или нет:
[Fact]
public void SinglePoint()
{
var format = new ScheduleFormat(new ScheduleDate(
new[] {ScheduleFormatEntry.SinglePoint(2020)},
new[] {ScheduleFormatEntry.SinglePoint(9)},
new[] {ScheduleFormatEntry.SinglePoint(1)}
),
new[] {ScheduleFormatEntry.SinglePoint(1)},
new ScheduleTime(
new[] {ScheduleFormatEntry.SinglePoint(10)},
new[] {ScheduleFormatEntry.SinglePoint(0)},
new[] {ScheduleFormatEntry.SinglePoint(0)},
new[] {ScheduleFormatEntry.SinglePoint(0)}
));
var merged = MergedSchedule.FromFormat(format);
AssertSingleValidPoint(merged.Years, 2020);
AssertSingleValidPoint(merged.Months, 9);
AssertSingleValidPoint(merged.Days, 1);
AssertSingleValidPoint(merged.DayOfWeek, 1);
AssertSingleValidPoint(merged.Hours, 10);
AssertSingleValidPoint(merged.Minutes, 0);
AssertSingleValidPoint(merged.Seconds, 0);
AssertSingleValidPoint(merged.Milliseconds, 0);
}
// ... и ещё с десяток тестов, проверяющих другие возможные результаты парсингаНу и как обычно, тесты зеленые — всё хорошо. Опять же, потому что ошибиться тут негде: тривиальное преобразование одной структуры в другую, тут уже даже не используется формат, который нам на входе дан по заданию, мы используем только наши внутренние структуры. Что дает нам очередную гибкость — при изменении формата по любым причинам если это не затрагивает внутренне представление (а только разделитель, скажем, поменялся), то эти тесты продолжат работать, как и раньше. Сила декомпозиции!
Ну, парсинг мы написали, на наш формат хранения перевели, осталась мелочь, написать поиск ближайшего события? Давайте сделаем
Назад в будущее
Подглядев у Quartz как они ищут дни недели пишем аналогично, сначала подбираем год:
public DateTime NearestEvent(DateTime t1)
{
while (true)
{
while (!_innerSchedule.Years.IsPointAllowed(t1.Year))
{
t1 = new DateTime(t1.Year, 1, 1).AddYears(1);
}
return t1;
}
}затем добавляем месяц:
public DateTime NearestEvent(DateTime t1)
{
while (true)
{
while (!_innerSchedule.Years.IsPointAllowed(t1.Year))
{
t1 = new DateTime(t1.Year, 1, 1).AddYears(1);
}
// search for month
var year = t1.Year;
while (t1.Year == year && !_innerSchedule.Months.IsPointAllowed(t1.Month))
{
t1 = new DateTime(t1.Year, t1.Month, 1).AddMonths(1);
}
if (t1.Year != year)
{
continue;
}
return t1;
}
}Затем день:
public DateTime NearestEvent(DateTime t1)
{
while (true)
{
...
// search for day
var month = t1.Month;
// тут весьма тяжеловесное условие, но честно лень его расписывать иначе
while (t1.Month == month && !(_innerSchedule.DayOfWeek.IsPointAllowed((int) t1.DayOfWeek)
&& (_innerSchedule.Days.IsPointAllowed(t1.Day) ||
_innerSchedule.Days.IsPointAllowed(32)
&& t1.Day == DateTime.DaysInMonth(t1.Year, t1.Month))))
{
t1 = new DateTime(t1.Year, t1.Month, t1.Day).AddDays(1);
}
if (t1.Month != month)
{
continue;
}
}
}Обратите внимание на паттерн
while (someCond && !realCond) { ...}
if (!someCond) { continue }К моменту написания секунд меня порядком подзадолбало постоянно это писать. И тут вступает в дело герой из заголовка статьи: я вспомнил, что мне может помочь: goto! На этом моменте меня должны сразу закидать помидорами, насовать минусов в карму, откомментить «Вон Дейкстра что писал, ты чего творишь?! Позор» ну и все в таком духе. Но, по зрелому размышлению я решил, что оно во-первых убирает лишнее сравнение, во-вторых, делает код чище. Посмотрите сами, вот так выглядит поиск до дней:
public DateTime NearestEvent(DateTime t1)
{
while (true)
{
LoopStart: ;
// search for year
while (!_innerSchedule.Years.IsPointAllowed(t1.Year))
{
t1 = new DateTime(t1.Year, 1, 1).AddYears(1);
}
// search for month
var year = t1.Year;
while (!_innerSchedule.Months.IsPointAllowed(t1.Month))
{
t1 = new DateTime(t1.Year, t1.Month, 1).AddMonths(1);
if (t1.Year != year)
{
goto LoopStart;
}
}
// search for day
var month = t1.Month;
while (!(_innerSchedule.DayOfWeek.IsPointAllowed((int) t1.DayOfWeek)
&& (_innerSchedule.Days.IsPointAllowed(t1.Day) ||
_innerSchedule.Days.IsPointAllowed(32)
&& t1.Day == DateTime.DaysInMonth(t1.Year, t1.Month))))
{
t1 = new DateTime(t1.Year, t1.Month, t1.Day).AddDays(1);
if (t1.Month != month)
{
goto LoopStart;
}
}
}
}Никогда не думал, что такое скажу —, но гоуту и правда помогает в данном случае. Обычно он не нужен — рефакторинг внутренней логики в функцию обычно отлично работает. Но не в нашем случае, да, потому что нам нужно разорвать внешний цикл, а не внутренний. Кроме того, вызов функции наверняка не будет заинлайнен (особенно в случае с днями), из-за чего у нас появляются накладные расходы, которых хотелось бы избежать. В идеале это должно было бы решиться макросом или языковой фичей вроде:
mainLoop: while (true)
{
// search for year
while (!_innerSchedule.Years.IsPointAllowed(t1.Year))
{
t1 = new DateTime(t1.Year, 1, 1).AddYears(1);
}
// search for month
var year = t1.Year;
while (!_innerSchedule.Months.IsPointAllowed(t1.Month))
{
t1 = new DateTime(t1.Year, t1.Month, 1).AddMonths(1);
if (t1.Year != year)
{
continue mainLoop;
}
}
}Но увы, ни того, ни другого у нас нет. В итоге да, гоуту оказывается самым читаемым (на мой взгляд) из альтернатив. И при этом зирокост, что немаловажно.
Итоговый код функции:
public DateTime NearestEvent(DateTime t1)
{
while (true)
{
LoopStart: ;
// search for year
while (!_innerSchedule.Years.IsPointAllowed(t1.Year))
{
t1 = new DateTime(t1.Year, 1, 1).AddYears(1);
}
// search for month
var year = t1.Year;
while (!_innerSchedule.Months.IsPointAllowed(t1.Month))
{
t1 = new DateTime(t1.Year, t1.Month, 1).AddMonths(1);
if (t1.Year != year)
{
goto LoopStart;
}
}
// search for day
var month = t1.Month;
while (!(_innerSchedule.DayOfWeek.IsPointAllowed((int) t1.DayOfWeek)
&& (_innerSchedule.Days.IsPointAllowed(t1.Day) ||
_innerSchedule.Days.IsPointAllowed(32)
&& t1.Day == DateTime.DaysInMonth(t1.Year, t1.Month))))
{
t1 = new DateTime(t1.Year, t1.Month, t1.Day).AddDays(1);
if (t1.Month != month)
{
goto LoopStart;
}
}
// search for hour
var day = t1.Day;
while (!_innerSchedule.Hours.IsPointAllowed(t1.Hour))
{
t1 = new DateTime(t1.Year, t1.Month, t1.Day, t1.Hour, 0, 0).AddHours(1);
if (t1.Day != day)
{
goto LoopStart;
}
}
// search for minute
var hour = t1.Hour;
while (!_innerSchedule.Minutes.IsPointAllowed(t1.Minute))
{
t1 = new DateTime(t1.Year, t1.Month, t1.Day, t1.Hour, t1.Minute, 0).AddMinutes(1);
if (t1.Hour != hour)
{
goto LoopStart;
}
}
// search for second
var minute = t1.Minute;
while (!_innerSchedule.Seconds.IsPointAllowed(t1.Second))
{
t1 = new DateTime(t1.Year, t1.Month, t1.Day, t1.Hour, t1.Minute, t1.Second).AddSeconds(1);
if (t1.Minute != minute)
{
goto LoopStart;
}
}
// search for ms
var second = t1.Second;
while (!_innerSchedule.Milliseconds.IsPointAllowed(t1.Millisecond))
{
t1 = t1.AddMilliseconds(1);
if (t1.Second != second)
{
goto LoopStart;
}
}
return t1;
}
}Вперед в прошлое
Аналогично пишем функцию для поиска назад во времени:
public DateTime NearestPrevEvent(DateTime t1)
{
while (true)
{
LoopStart: ;
// search for year
while (!_innerSchedule.Years.IsPointAllowed(t1.Year))
{
t1 = new DateTime(t1.Year, 1, 1).AddMilliseconds(-1);
}
// search for month
var year = t1.Year;
while (!_innerSchedule.Months.IsPointAllowed(t1.Month))
{
t1 = new DateTime(t1.Year, t1.Month, 1).AddMilliseconds(-1);
if (t1.Year != year)
{
goto LoopStart;
}
}
// search for day
var month = t1.Month;
while (!(_innerSchedule.DayOfWeek.IsPointAllowed((int) t1.DayOfWeek)
&& (_innerSchedule.Days.IsPointAllowed(t1.Day) ||
_innerSchedule.Days.IsPointAllowed(32)
&& t1.Day == DateTime.DaysInMonth(t1.Year, t1.Month))))
{
t1 = new DateTime(t1.Year, t1.Month, t1.Day).AddMilliseconds(-1);
if (t1.Month != month)
{
goto LoopStart;
}
}
// search for hour
var day = t1.Day;
while (!_innerSchedule.Hours.IsPointAllowed(t1.Hour))
{
t1 = new DateTime(t1.Year, t1.Month, t1.Day, t1.Hour, 0, 0).AddMilliseconds(-1);
if (t1.Day != day)
{
goto LoopStart;
}
}
// search for minute
var hour = t1.Hour;
while (!_innerSchedule.Minutes.IsPointAllowed(t1.Minute))
{
t1 = new DateTime(t1.Year, t1.Month, t1.Day, t1.Hour, t1.Minute, 0).AddMilliseconds(-1);
if (t1.Hour != hour)
{
goto LoopStart;
}
}
// search for second
var minute = t1.Minute;
while (!_innerSchedule.Seconds.IsPointAllowed(t1.Second))
{
t1 = new DateTime(t1.Year, t1.Month, t1.Day, t1.Hour, t1.Minute, t1.Second).AddMilliseconds(-1);
if (t1.Minute != minute)
{
goto LoopStart;
}
}
// search for ms
var second = t1.Second;
while (!_innerSchedule.Milliseconds.IsPointAllowed(t1.Millisecond))
{
t1 = t1.AddMilliseconds(-1);
if (t1.Second != second)
{
goto LoopStart;
}
}
return t1;
}
}Тут стоит сделать отступление на комментарий товарища sepulkary
У вас два большущих метода, отличающихся только знаком
Однако внимательный читатель сразу заметит, что функции отличаются ещё одной немаловажной особенностью. Посмотрим, как вычисляются годы в будущее:
while (!_innerSchedule.Years.IsPointAllowed(t1.Year))
{
t1 = new DateTime(t1.Year, 1, 1).AddYears(1);
}И в прошлое:
while (!_innerSchedule.Years.IsPointAllowed(t1.Year))
{
t1 = new DateTime(t1.Year, 1, 1).AddMilliseconds(-1);
}Ведь дело в том, что если нам не подходит текущий год, то мы должны начать поиск с первого дня первого месяца следующего года.
А вот если мы ищем назад, то нам нужно 31 декабря 23:59:59.9999999999… То есть логика достаточно сильно различается.
Это можно было бы отрефачить во что-то вида t1 = yearChangingLambda(t1) — т.е. передавать лямбдой необходимое изменение, чтобы ликвидировать различие между функциями. Но тут нас кусает требование об оптимальности — на каждой итерации в горячем цикле вызывать лямбду это не вариант совершенно. Да и в целом передавать кучу лямбд аргументами выглядит некрасиво. Есть ли решение, которое нас устроит? И конечно же, ответ — мы можем всё.
Zero-cost решение проблемы различия функций
В мире дотнета есть довольно известная оптимизация, которую зачастую рассказывают на всяких конфах вроде DotNext. Это оптимизации джитом генериков для структур. Так как для структур невозможно наследование, джит может выкидывать целые куски кода, которые выполняются после проверки на конкретный тип. например, давайте посмотрим на тайплевел Bool:
public interface IBool
{
}
public struct TrueType : IBool
{
}
public struct FalseType : IBool
{
}Что мы можем полезного сделать с этими типами? Например, использовать их для тайплевел вычислений. Давайте напишем функцию, которая опускает значение с уровня типов до уровня значений:
public struct Test
{
[MethodImpl(MethodImplOptions.AggressiveInlining | MethodImplOptions.AggressiveOptimization)]
public static bool IsTrue() where T : struct, IBool =>
default(T) switch
{
TrueType _ => true,
FalseType _ => false
};
}
...
public bool Foo() => Test.IsTrue() К сожалению, после замены старого джита на RyuJit он сильно потупел и не догадывается без подсказки соптимизировать подобные кейсы
Во что, по-вашему, будет скомпилирована функция Foo? А вот во что:
C.Foo()
L0000: push ebp
L0001: mov ebp, esp
L0003: mov eax, 1
L0008: pop ebp
L0009: retЧто мы видим? Компилятор просто грузит константу 1 (true) на стек и возвращает. Т.е. он увидел, что из всех веток switch достижима только одна (там где TrueType) и выкинул все остальные. Затем он увидел, что переменная TrueType _ не используется и убрал её. После чего ему поставалось только заинлайнить тривиальную функцию return true, поэтому даже вызова функции мы в итоге не увидели, а только одинокую константу 1.
Возвращаясь к нашей проблеме:, а что, если мы вынесем вычисления дат туда же? Сказано-сделано:
public interface IDateTimeChanger
{
DateTime Change(DateTime t1)
where TIsIncrementing : struct, IBool;
}
public struct YearsChanger : IDateTimeChanger
{
[MethodImpl(MethodImplOptions.AggressiveInlining
| MethodImplOptions.AggressiveOptimization)]
public DateTime Change(DateTime t1)
where TIsIncrementing : struct, IBool
{
var baseValue = new DateTime(t1.Year, 1, 1);
return default(TIsIncrementing) switch
{
TrueType _ => baseValue.AddYears(1),
FalseType _ => baseValue.AddMilliseconds(-1)
};
}
}
// ... для других компонентов даты аналогично TIsIncrementing Это либо TrueType либо FalseType, которые передают нам соответственно признак если мы ищем вперед во времени (NearestEvent) или назад (NearestPrevEvent).
Как теперь выглядит наша функция? Вот так:
private DateTime Closest(DateTime t1) where TIsIncrementing : struct, IBool
{
var yearChanger = default(YearsChanger);
var monthChanger = default(MonthChanger);
var dayChanger = default(DayChanger);
var hourChanger = default(HourChanger);
var minuteChanger = default(MinuteChanger);
var secondChanger = default(SecondChanger);
var millisecondChanger = default(MillisecondChanger);
while (true)
{
LoopStart: ;
// search for year
while (!_innerSchedule.Years.IsPointAllowed(t1.Year))
{
t1 = yearChanger.Change(t1);
}
// search for month
var year = t1.Year;
while (!_innerSchedule.Months.IsPointAllowed(t1.Month))
{
t1 = monthChanger.Change(t1);
if (t1.Year != year)
{
goto LoopStart;
}
}
// search for day
var month = t1.Month;
while (!(_innerSchedule.DayOfWeek.IsPointAllowed((int) t1.DayOfWeek)
&& (_innerSchedule.Days.IsPointAllowed(t1.Day) ||
_innerSchedule.Days.IsPointAllowed(32)
&& t1.Day == DateTime.DaysInMonth(t1.Year, t1.Month))))
{
t1 = dayChanger.Change(t1);
if (t1.Month != month)
{
goto LoopStart;
}
}
// search for hour
var day = t1.Day;
while (!_innerSchedule.Hours.IsPointAllowed(t1.Hour))
{
t1 = hourChanger.Change(t1);
if (t1.Day != day)
{
goto LoopStart;
}
}
// search for minute
var hour = t1.Hour;
while (!_innerSchedule.Minutes.IsPointAllowed(t1.Minute))
{
t1 = minuteChanger.Change(t1);
if (t1.Hour != hour)
{
goto LoopStart;
}
}
// search for second
var minute = t1.Minute;
while (!_innerSchedule.Seconds.IsPointAllowed(t1.Second))
{
t1 = secondChanger.Change(t1);
if (t1.Minute != minute)
{
goto LoopStart;
}
}
// search for second
var second = t1.Second;
while (!_innerSchedule.Milliseconds.IsPointAllowed(t1.Millisecond))
{
t1 = millisecondChanger.Change(t1);
if (t1.Second != second)
{
goto LoopStart;
}
}
return t1;
}
} Чьё использование тривиально:
public DateTime NearestEvent(DateTime t1) => Closest(t1);
public DateTime NearestPrevEvent(DateTime t1) => Closest(t1); И, на этом с реализацией всё. Осталось посмотреть, как оно работает всё в сборе, ну и сравнить с предыдущими версиями
Сравниваем с оригинальным решением автора
Парсинг
Во всех бенчмарках версия novar считается базовой, от неё считаются все остальные. И первое, что мы сравним, это время парсинга:
BenchmarkDotNet=v0.13.0, OS=Windows 10.0.19043.1110 (21H1/May2021Update)
AMD Ryzen 7 3800X, 1 CPU, 16 logical and 8 physical cores
.NET 5.0 : .NET 5.0.8 (5.0.821.31504), X64 RyuJITКакой кошмар, ужас, в 50 раз медленнее! Выкинуть это дело на помойку, опять монадки неприменимы в реальном мире! — сказал бы кто-нибудь, и я бы с ним не согласился. Да, время парсинга кратно хуже, но, во-первых обратите внимание что оно все ещё в пределах 20 микросекунд и его достаточно чтобы перепаршивать наш дорогой формат хоть 50000 раз в секунду. Во-вторых, наш парсер в отличие от оригинального имеет кучу преимуществ: он композабелен, он легко читаем/расширяем, а главное в случае ошибки разбора сообщает вам конкретно место и подстроку, которую не смог разобрать. Оригинальный же парсер конечно же ничего не трекает и просто бросает ошибку «что-то пошло не так». А как известно, почти ничего не бывает задаром.
В общем, хотя парсер и ощутимо медленнее, он все ещё годен для любого реалистичного использования. А учитывая предполагаемый паттерн использования данного типа — мы решили задачу с более чем достойным запасом.
Идем дальше — поиск следующего значения:
Определение ближайшего события
Я взял несколько случайных паттернов из тех, что были даны как примеры в задании, и после прогона бенчмарков получил следующие результаты:
FindNextOld — это оригинальная реализация автора, FindNextNewCopypasted — последняя реализация до того, как мы воспользовались мощью типчиков, и FindNextNewTypelevel собственно итоговая тайплевел версия. Обратите внимание, что и копипастная, и тайплевел версии имеют абсолютно одинаковый перформанс. Все потому, что они компилируется в эквивалентный код. А ведь при этом мы убрали копипасту и смогли переиспользовать код, написав одну функцию для обоих вариантов. Совершенно бесплатно и без смс.
Теперь если сравнивать с авторским вариантом — то разница обусловлена тем, что в версии автора при нахождении любого расхождения начинается поиск с самого начала. В моем же случае я отслеживаю старшее значение (год для месяца, месяц для дня и т.п.) и запускаю полный перерасчет, только если этот компонент изменился. В некоторых случаях это будет давать выигрыш, в каких-то будет наоборот медленнее. Но в целом порядок времени выполнения схож, хотя на тестовых данных подход с сохранением показал лучшие результаты. Думаю, несложно будет подобрать искусственный пример, где изначальный подход будет выигрывать.
Идем дальше
Определение ближайшего предыдущего события
Тут мы видим схожие с предыдущим пунктом результаты, хотя на некоторых инпутах результат не быстрее в 2 раза, а медленнее. Видимо, это связано как раз с различием в принятии решения об откате на поиск с самого начала.
С этой частью задания кстати связана одна история: до того, как я сделал тайплевел почему-то у меня постоянно различалось время выполнения поиска в прямом и обратном порядке. Да и даже когда я объединил — все равно никак не получалось одинаковой скорости добиться — прямой проходя был всегда немного быстрее, а обратный — в 10 раз медленнее. В итоге через пару дней проглядывая код совершенно случайно нашел, в чем же косяк. Вот фикс (а затем более правильный фикс), и очередное подтверждение того, что копипаста — зло.
Итоги сравнения с оригинальным кодом
В общем, оглядываясь на результаты выше, можно увидеть улучшение во всех измерениях, которые мне кажутся важными:
- Код соблюдает SRP: есть небольшие модули, каждый из которых отвечает за свою небольшую часть. Юникс-вей, все дела. Парсер парсит, модели отражают то, что им нужно, а не то что нужно кому-то (кому надо — тот смаппит)
- Код композируем: можно спокойно поменять формат, добавить новый, поменять правила парсинга — все это инкапсулировано в отдельной части. Можно поменять логику хранения с булевых массивов на какие-нибудь бинарные деревья как в Quartz, при этом б0льшую часть кода не придется менять вообще
- Код читаем: его реально можно прочитать. Нужен парсинг — пошли посмотрели 50 строчек тут, нужно понять как маппится — 20 строчек там, нужно понять, как ищем расписания — ничего проще, вот ещё немного кода. Оригинальный код, честно говоря, я осилил не сразу, и то часть с парсингом я просто свернул — к сожалению, это слишком круто для меня)
- Отдельно хочу отметить линейную структуру поиска без триллиона if — почувствуйте сами, насколько велика разница в восприятии
- Странно отдельно упоминать это в 2021 году, но нет магических констант: все вынесено в отдельное место и можно поменять в единственном месте (в оригинальном коде с этим было немного печально)
- Дописаны тесты на негативные кейсы — то, чего кстати не хватило автору. То что мы парсим что нужно — это хорошо, но ещё нужно проверять, что не парсим чего не нужно
- Есть повод использовать монады: без комментариев :)
Ну есть конечно же и пространство для улучшений, потому как делалось все в рамках жесткого лимита времени, т.к. тратить на задание дни не считаю целесообразным:
- Убрать
int.Parse(new String(char[])): очевидное место, где совершаются аллокации и много ненужных действий - Ооптимизировать работу с дейттаймами: использовать константы TicksPerDay/TicksPerHour/… и битовые/арифметические операции чтобы отсекать неподходящие даты. Конструкторы даты постоянно проверяют инварианты, про которые по построению известно что они корректны. Можно на этом сэкономить
- Лучший нейминг
- Больше тестов
- Более хорошие ошибки парсинга для краевых случаев
- Правильные эксепшны в некоторых случаях, которые сейчас кидают слишком общие ошибки (навроде OutOfBoundsException)
- Тысячи их
Пара слов о комментариях к оригинальной статье
Хотелось бы ещё прокомментировать некоторые комменты к оригинальной статье:
nirom
Честно говоря, тестовое задание ни о чем. Видимо ищут джуна, чтобы валить на него косяки и пенать его без повода, вы не подошли, не расстраивайтесь.
Задание нормальное, как на джуна так и на сениора: просто у них решение будет отличаться. Да и вряд ли джун осилит правильный парсинг нужного формата — запутается, что за чем должно идти. Хотя и адекватного сениора, который бы стал делать тестовые задания нужно ещё поискать. Я лично делаю, только если меня заинтересовала проблема. Задачку как у автора я скорее всего проигнорировал бы, будь это задача не показательная, чтобы попробовать свои силы, а для трудоустройства. В общем, задание в целом странноватое: слишком сложное для джуна, слишком долгое для сениора. Возможно, они искали крепкого миддла без особых амбиций, но этого мы наверное уже не узнаем.
Hydro
Лень было погружаться в код до полного понимания, но почему есть ощущение, что добрую логику парсинга можно было просто сделать регулярками.
Опять же, описано в статье, но стоит отдельно отметить, что даже если на регулярках получится сделать задание, то доработать его в будущем — на моей практике проще выкинуть регулярку и написать новую, чем разобраться в старой) И только после написания новой будет понятно, что в старой имелось в виду. И адекватной ошибки, как например у парсера в данной статье
var result = FullFormatParser.ParseOrThrow("asfas.01.01 00:00:00.000");
// Parse error.
// unexpected a
// expected "*", or digit
// at line 1, col 1с регулярками не получится никогда
sepulkary
И, чтобы два раза не вставать, как говорится; вопрос к изначальной постановке задачи — не очень понимаю, зачем здесь конструктор, вижу место только для нескольких статических методов, которые принимают на вход время и строку расписания, отдавая время, удовлетворяющее условию. static не всегда хорошо, но вроде здесь вполне к месту, работаем прямо с чистыми функциями
Как было показано на бенчмарке выше, время выполнения парсинга порядка 18 мкс, а время поиска по уже разобранному выражению — 200нс, т.е. на 2 десятичных порядка меньше. Совершенно логично сохранить результат парсинга и переиспользовать его — расписания и по логике-то вряд ли меняются каждую микросекунду
