Сравнивать на json-е скучно. Возьмите хотя бы парсер выражений на 10-15 уровней приоритетов.
В код не вчитывается, но кажется Вы используете рекурсивный спуск. Он, вообще говоря, довольно неоптимален на сложных грамматиках. Плюс, у ANTLR чуть шире класс разбираемых грамматик, чем LL(k).
Не очень понятно, а какую проблему Ваша система пытается решить. Contextual keywords, language embedding, что-то ещё?
Сам синтаксис всё ещё довольно сложный и шумный (сравните с условными antlr и tree sitter). Встраивания фрагментов на C++ являются скорее недостатком, чем преимуществом: если уж мы полезли в генератор, то хочется в нём и оставаться.
Также, пример с выражениями Вам не просто так привели. Разумеется, есть классические примеры, как делать грамматику выражений с приоритетами. Но это довольно плохой подход. Хочется видеть хотя бы shunting yard/pratt parsing. Тут же вопрос: а какой parse tree Вы для этих выражений строите?... Помниться была статья, где паркинг питона ускоряли в 300 раз, просто устраняя вот эту лозу из дерева разбора.
Не, ну бенчмаркать нужно очень аккуратно. Как минимум, нужно делать бенчи в независимых окружениях: у Вас сначала оптимизатор специализирует getA на один архетип, а потом видит, что эвристика сломалась и переоптимизирует её - вот и дополнительные 6мс. Дальше вопрос в том, что сам код с циклом лучше тоже завернуть в функцию - чтобы сам цикл тоже оптимизировать. Плюс мб имеет смысл сначала заготовить массив объектов, а потом уже получать доступ к свойствам. А то инлайнер может чудеса творить.
В целом, внезапно неплохой сайт для бенчей у Карловского сделан.
Потому что break никогда не вернет значение. Например:
let v: Int32 = break;
//^ можно, мы из этого v никогда не прочитаем
let x: Int32 = for(...) {}
//^ нельзя: цикл может закончиться, а значения у нас нет
Разумеется, в таком применении, это не очень полезно. Но в комбинации с другими фичами, это может быть интересным:
let v: Int32 = if isPrime(n) {
n*n
} else {
continue
}
Здесь мы в одной ветке не считаем значение, а просто обрываем цикл.
В целом, тип Nothing также дает возможность объявить функцию, которая всегда кидает исключение (какой-нибудь throwExceptionWithExtendedInfo()).
Сами типы Unit и Nothing, судя по всему, пришли из котлина. Аналогичные типы есть в расте: пустой кортеж `()` и never type `!`. Поэтому стандартная история для современного мейнстрима.
Вообще, язык выглядит как помесь котлина и свифта, с элементами раста. Хотя из описания статьи многое осталось непонятно про собственно сам язык и среду исполнения. Видимо прийдется курить доку, чтобы составить представление о языке.
Первый вариант почти что UB, из-за TBAA. Спасает только, что uint8_t разрешено алиаситься с любыми типами.
Если бы каст был бы хотя бы между int16_t и int32_t (или например между флоатом и интом), то этот код был бы UB. И емнип, крайние версии кланга стали эксплуатировать это уб в подобном коде.
Знали ли Вы это или нет — хороший вопрос.
Чтобы правильно делать reinterpret, нужно делать memcpy в буфер и обратно в другой тип.
Такой подход ломается на банальном `await process(state)` — поскольку внутри process могут быть другие await-ы, или того хуже коллбеки. Препроцессить абсолютно весь код — сложно (например, потому что браузерные апи не выйдет препроцессить).
Вообще, правильным решением было бы профорсить AsyncLocalStorage (он же cls). Но кажется проползал завис и есть только реализация в ноде :(
Можно было бы проэмулировать cls через препроцессор, и я думаю уже даже есть такие решения. Но хрупко это все, в прод бы я такое не потянул.
Ну, как поддержать синхронный авторан конкурентно с ассинхронным — понятно.
По сути, нужно внутри библиотеки вставлять семафор на ассинхронные автораны (чтобы одновременно было запущенно не более одного авторана). Иначе, как подтверждает @nin-jin, это выстрел в ногу, как только у нас запустится два ассинхронных авторана (например, если у них поменяется общая зависимость). Я об этом и написал в самом первом своем комментарии.
Поэтому для меня совершенно непонятна затея await-ить автораны (мы же делаем await только для первого запуска, а со всеми остальными ничего не понятно).
Ограничение на последовательное исполнение ассинхронных авторанов, в целом, понятно. Вопрос только в том, а что можно сделать полезного с учетом этого ограничения. Не будет ли это источником водопадов?
Ну, так Ваши замеры и показывают, что 2.5 секунды. Не, понятно, что там ещё какие-то копейки будут от собственно синхронного исполнения — но это вообще не суть вопроса. Суть вопроса в том, чтобы понять как поведет Ваша методика, если там будут хоть какие-то нетривиальные промисы.
То, что Вы меряете только один промис, а не оба — просто придираетесь к формулировкам. Разумеется мерять нужно время от старта до момента появления обоих write-ов.
Ну и вопрос "сколько времени займет" здесь носит качественный, а не количественный характер. Вы делаете то, что в других библиотеках совершенно отсутствует — в этом случае вести разговор об абсолютном перфе нет особого смысла. Интересно понять качественное поведение Вашего решения.
Если хотите вести конструктивный диалог, приводите реальные примеры,
Я вроде задаю конкретные вопросы и привожу конкретные примеры. Основной вопрос сводится к тому, что не до конца понятен принцип работы Вашего подхода, а также его особенности (и в течении нашего разговора у меня вопросов становиться только больше).
Про расчеты написал выше, что в них нет смысла при разговоре о качественном поведении подхода.
P. S. Вы почему-то то и дело пытаетесь меня в чем-то обвинить. Не надо так. Вы кажется достаточно хорошо знакомы с деталями, чтобы можно было опустить какие-то формальности и терминологические споры.
Ну, хорошая реализация исполняет этот код за 2.5 секунды. Если же вводится запрет на параллельное исполнение ассинхронных эффектов, то потребуется целых 5 секунд. Из Вашего описания в статье, я так понимаю, Вы именно что вводите этот запрет, чтобы понимать их какого эффекта происходит чтение.
Ваши упоминания LIFO стека я увидел и при прочтении статьи. Но что конкретно это значит — разительно непонятно. Я могу себе представить 2-3+ сильно разных способов использовать LIFO стек. Вот поэтому и спрашиваю.
Тогда не очень понятно. Если у Вас могут параллельно могут исполняться два ассинхронных эффекта, то как Вы отслеживание их зависимости?
Тест из примера в статье не показывает параллельно ли они исполняются, или последовательно (может у Вас внутри там семафор).
await эффектов это не какой-то отдельный кейс, и это никак не противоречит тому, что эффекты мы создаем один раз, а выполняются они сколько угодно раз.
Тогда совершенно непонятно, зачем он нужен. Какой юзкейс, безопасно ли пользователю забыть сделать await эффекту?
Если я правильно понял, Вы сделали в системе не более одного активного ассинхронного эффекта. Если это так, то в этом нет смысла — ассинхронные эффекты хочется всё же исполнять параллельно.
Также, совершенно непонятный кейс с await-ом эффектов. Мы же эффекты один раз настраиваем и они потом много раз перезапускаются — между эффектами нет явного порядка.
Короче, непонятно зачем это всё нужно (не в смысле ассинхронные эффекты в принципе, а конкретно Ваше виденье).
Тогда можно просто вставить ссылку на узел дерева прямо в саму ноту. Это гораздо эффективнее получится.
То есть, классически это решается так. Вы используете дерево для поиска по данным (интервалам времени) - возвращают эти поиски узлы (условно NoteNode). Далее операции удаления, обновления и прочего принимают напрямую эту NoteNode - в ней есть ссылки на узлы дерева. Поэтому у Вас пропадает операция поиска по объекту.
На моей практике, такой подход кратно упрощает реализацию.
На самом деле, замерить худший случай не так то и просто будет. Самая главная проблема - это нагрузка на аллокатор и сборщик мусора.
Например, при добавлении в связный список, у нас всегда аллоцируется узел списка. Чаще всего, это просто инкремент указателя в чистилище. Но, если окажется, что чистилище у нас занято - произойдёт малая сборка мусора. А это линейный проход по всему чистилищу (вероятно 16-256 MB на десктопе) - то есть довольно долго.
В случае же List, у нас либо хватает места и произойдёт простой инкремент индекса/указателя. Может не хватить места и произойдёт реаллок - это всего лишь копия элементов списка, а не целого чистилища. И крайний случай - может тоже не хватить памяти и произойдёт малая сборка мусора - тут тот же худший случай.
Поэтому наивный бенчмарк может померять не то (особено в языках с GC - у них большой фактор играет сборка мусора).
На практике, при длинах списка до 100 элементов, List работает быстрее LinkedList даже в худщем случае. Вся вот эта история с быстрыми точечными операциями становиться интересной когда у Вас миллионы элементов в списке - но там обычный LinkedList плохо работает, нужны интрузивные структуры данных.
Вообще, для таких задач часто подходят splay-деревья. Они не обладают гарантиями реального времени, но зато они очень хорошо оптимизируются под нагрузку.
Касательно работы с несколькими значениями для одного ключа, классически это решается курсора и:
Разрешаете дублирование ключей
Вместо операции search вводите операции lower_bound и upper_bound (ну или search_first и search_last)
При этом, результаты поиска возвращают не значения, а курсоры: специальные объекты, которые могут перемещаться вперёд-назад (и получать значения)
Справиться с линейным поиском по значениям без наложения ограничений на сами значения нельзя. Но я не очень понял зачем Вам искать по значениям (только как деталь реализации с координатами - но это решается курсорами).
Но зато можно делать дерево поиска по составному ключу. В качестве ключа мы используем пары (K1, K2). Порядок сравнения в них лексикографический. Тогда с одной стороны, у нас есть дерево поиска по (K1, K2) без повторяющихся ключей, а с другой стороны - дерево поиска по K1, но уже с повторяющимися ключами.
P. S. Имхо, делать обобщенные(в смысле дженериков) структуры данных не очень полезно. Гораздо важнее делать структуры данных под конкретные применения — там можно гораздо лучше использовать специфику задачи.
А потому всегда должен смотреть на худший случай тоже.
Это не всегда хорошая затея.
Фишка в том, что этот "худший" случай не может происходить слишком часто. Если выражаться формально, то там аммортизированное O(1).
Если вы не желаете структуры данных под реальное время, то вам стоит смотреть на суммарное время выполнения операций — а оно у списков кратно быстрее.
Прелесть нотации "O" большое в том, что мне даже не нужно бенчмарки запускать для понимания скорости
Вообще нет. Если бы это было бы так, мы бы все использовали фибоначеву кучу и галактические алгоритмы (спойлер: у них очень хорошее O, но на всех доступных сейчас объёмах данных, они очень медленные).
Ну, или с другой стороны: знали ли Вы, что современные реализации сортировок используют сортировку вставками, а не квиксорт в некоторых случаях — так быстрее.
Оно unsafe - это правда, но это не имеет отношения к синшному аби. Для сишного аби нужно использовать extern "C" а также использовать только типы со стабильным аби. Хотя данный конкретный пример настолько простой, что есть тупо нет альтернативных вариантов.
Впрочем, я перечитал с чего начался тред, и проблема в том, что раст умеет инлайнить функции из dylib (через split metadata, или через метадату прямо в dylib). И с недавних пор раст автоматически помечает простые функции как #[inline].
Чтобы этого избежать можно пометить функцию как #[inline(never)]. Или же увеличить тело функции, чтобы раст не инлайнил эту функцию.
Сравнивать на json-е скучно. Возьмите хотя бы парсер выражений на 10-15 уровней приоритетов.
В код не вчитывается, но кажется Вы используете рекурсивный спуск. Он, вообще говоря, довольно неоптимален на сложных грамматиках. Плюс, у ANTLR чуть шире класс разбираемых грамматик, чем LL(k).
Не очень понятно, а какую проблему Ваша система пытается решить. Contextual keywords, language embedding, что-то ещё?
Сам синтаксис всё ещё довольно сложный и шумный (сравните с условными antlr и tree sitter). Встраивания фрагментов на C++ являются скорее недостатком, чем преимуществом: если уж мы полезли в генератор, то хочется в нём и оставаться.
Также, пример с выражениями Вам не просто так привели. Разумеется, есть классические примеры, как делать грамматику выражений с приоритетами. Но это довольно плохой подход. Хочется видеть хотя бы shunting yard/pratt parsing. Тут же вопрос: а какой parse tree Вы для этих выражений строите?... Помниться была статья, где паркинг питона ускоряли в 300 раз, просто устраняя вот эту лозу из дерева разбора.
Не, ну бенчмаркать нужно очень аккуратно. Как минимум, нужно делать бенчи в независимых окружениях: у Вас сначала оптимизатор специализирует getA на один архетип, а потом видит, что эвристика сломалась и переоптимизирует её - вот и дополнительные 6мс. Дальше вопрос в том, что сам код с циклом лучше тоже завернуть в функцию - чтобы сам цикл тоже оптимизировать. Плюс мб имеет смысл сначала заготовить массив объектов, а потом уже получать доступ к свойствам. А то инлайнер может чудеса творить.
В целом, внезапно неплохой сайт для бенчей у Карловского сделан.
Ага. Обычно в таких начинаниях делают бектест на обучающих данных... Переобучение, короче говоря =/
Потому что break никогда не вернет значение. Например:
Разумеется, в таком применении, это не очень полезно. Но в комбинации с другими фичами, это может быть интересным:
Здесь мы в одной ветке не считаем значение, а просто обрываем цикл.
В целом, тип Nothing также дает возможность объявить функцию, которая всегда кидает исключение (какой-нибудь throwExceptionWithExtendedInfo()).
Сами типы Unit и Nothing, судя по всему, пришли из котлина. Аналогичные типы есть в расте: пустой кортеж `()` и never type `!`. Поэтому стандартная история для современного мейнстрима.
Вообще, язык выглядит как помесь котлина и свифта, с элементами раста. Хотя из описания статьи многое осталось непонятно про собственно сам язык и среду исполнения. Видимо прийдется курить доку, чтобы составить представление о языке.
Первый вариант почти что UB, из-за TBAA. Спасает только, что uint8_t разрешено алиаситься с любыми типами.
Если бы каст был бы хотя бы между int16_t и int32_t (или например между флоатом и интом), то этот код был бы UB. И емнип, крайние версии кланга стали эксплуатировать это уб в подобном коде.
Знали ли Вы это или нет — хороший вопрос.
Чтобы правильно делать reinterpret, нужно делать memcpy в буфер и обратно в другой тип.
Такой подход ломается на банальном `await process(state)` — поскольку внутри process могут быть другие await-ы, или того хуже коллбеки. Препроцессить абсолютно весь код — сложно (например, потому что браузерные апи не выйдет препроцессить).
Вообще, правильным решением было бы профорсить AsyncLocalStorage (он же cls). Но кажется проползал завис и есть только реализация в ноде :(
Можно было бы проэмулировать cls через препроцессор, и я думаю уже даже есть такие решения. Но хрупко это все, в прод бы я такое не потянул.
Ну, как поддержать синхронный авторан конкурентно с ассинхронным — понятно.
По сути, нужно внутри библиотеки вставлять семафор на ассинхронные автораны (чтобы одновременно было запущенно не более одного авторана). Иначе, как подтверждает @nin-jin, это выстрел в ногу, как только у нас запустится два ассинхронных авторана (например, если у них поменяется общая зависимость). Я об этом и написал в самом первом своем комментарии.
Поэтому для меня совершенно непонятна затея await-ить автораны (мы же делаем await только для первого запуска, а со всеми остальными ничего не понятно).
Ограничение на последовательное исполнение ассинхронных авторанов, в целом, понятно. Вопрос только в том, а что можно сделать полезного с учетом этого ограничения. Не будет ли это источником водопадов?
Ну, так Ваши замеры и показывают, что 2.5 секунды. Не, понятно, что там ещё какие-то копейки будут от собственно синхронного исполнения — но это вообще не суть вопроса. Суть вопроса в том, чтобы понять как поведет Ваша методика, если там будут хоть какие-то нетривиальные промисы.
То, что Вы меряете только один промис, а не оба — просто придираетесь к формулировкам. Разумеется мерять нужно время от старта до момента появления обоих write-ов.
Ну и вопрос "сколько времени займет" здесь носит качественный, а не количественный характер. Вы делаете то, что в других библиотеках совершенно отсутствует — в этом случае вести разговор об абсолютном перфе нет особого смысла. Интересно понять качественное поведение Вашего решения.
Я вроде задаю конкретные вопросы и привожу конкретные примеры. Основной вопрос сводится к тому, что не до конца понятен принцип работы Вашего подхода, а также его особенности (и в течении нашего разговора у меня вопросов становиться только больше).
Про расчеты написал выше, что в них нет смысла при разговоре о качественном поведении подхода.
P. S. Вы почему-то то и дело пытаетесь меня в чем-то обвинить. Не надо так. Вы кажется достаточно хорошо знакомы с деталями, чтобы можно было опустить какие-то формальности и терминологические споры.
Ну, хорошая реализация исполняет этот код за 2.5 секунды. Если же вводится запрет на параллельное исполнение ассинхронных эффектов, то потребуется целых 5 секунд. Из Вашего описания в статье, я так понимаю, Вы именно что вводите этот запрет, чтобы понимать их какого эффекта происходит чтение.
Ваши упоминания LIFO стека я увидел и при прочтении статьи. Но что конкретно это значит — разительно непонятно. Я могу себе представить 2-3+ сильно разных способов использовать LIFO стек. Вот поэтому и спрашиваю.
Не очень понятно. Давайте такой пример:
Сколько будет исполняться данный код:
При старте
После изменения shared
После изменения x2
После изменения y2
?
P.S. Я умышленно не сделал await autorun. Если это существенно влияет на ответы, либо корректность - скажите.
Тогда не очень понятно. Если у Вас могут параллельно могут исполняться два ассинхронных эффекта, то как Вы отслеживание их зависимости?
Тест из примера в статье не показывает параллельно ли они исполняются, или последовательно (может у Вас внутри там семафор).
Тогда совершенно непонятно, зачем он нужен. Какой юзкейс, безопасно ли пользователю забыть сделать await эффекту?
А какое значение будет показано пользователю в res1 и res2? Они будут одинаковыми, будут ли они зависеть от порядка исполнения?
Мне не кажется это поведение разумным. Всё же ошибка в деве для такого гораздо лучше.
Если я правильно понял, Вы сделали в системе не более одного активного ассинхронного эффекта. Если это так, то в этом нет смысла — ассинхронные эффекты хочется всё же исполнять параллельно.
Также, совершенно непонятный кейс с await-ом эффектов. Мы же эффекты один раз настраиваем и они потом много раз перезапускаются — между эффектами нет явного порядка.
Короче, непонятно зачем это всё нужно (не в смысле ассинхронные эффекты в принципе, а конкретно Ваше виденье).
Тогда можно просто вставить ссылку на узел дерева прямо в саму ноту. Это гораздо эффективнее получится.
То есть, классически это решается так. Вы используете дерево для поиска по данным (интервалам времени) - возвращают эти поиски узлы (условно NoteNode). Далее операции удаления, обновления и прочего принимают напрямую эту NoteNode - в ней есть ссылки на узлы дерева. Поэтому у Вас пропадает операция поиска по объекту.
На моей практике, такой подход кратно упрощает реализацию.
На самом деле, замерить худший случай не так то и просто будет. Самая главная проблема - это нагрузка на аллокатор и сборщик мусора.
Например, при добавлении в связный список, у нас всегда аллоцируется узел списка. Чаще всего, это просто инкремент указателя в чистилище. Но, если окажется, что чистилище у нас занято - произойдёт малая сборка мусора. А это линейный проход по всему чистилищу (вероятно 16-256 MB на десктопе) - то есть довольно долго.
В случае же List, у нас либо хватает места и произойдёт простой инкремент индекса/указателя. Может не хватить места и произойдёт реаллок - это всего лишь копия элементов списка, а не целого чистилища. И крайний случай - может тоже не хватить памяти и произойдёт малая сборка мусора - тут тот же худший случай.
Поэтому наивный бенчмарк может померять не то (особено в языках с GC - у них большой фактор играет сборка мусора).
На практике, при длинах списка до 100 элементов, List работает быстрее LinkedList даже в худщем случае. Вся вот эта история с быстрыми точечными операциями становиться интересной когда у Вас миллионы элементов в списке - но там обычный LinkedList плохо работает, нужны интрузивные структуры данных.
Вообще, для таких задач часто подходят splay-деревья. Они не обладают гарантиями реального времени, но зато они очень хорошо оптимизируются под нагрузку.
Касательно работы с несколькими значениями для одного ключа, классически это решается курсора и:
Разрешаете дублирование ключей
Вместо операции search вводите операции lower_bound и upper_bound (ну или search_first и search_last)
При этом, результаты поиска возвращают не значения, а курсоры: специальные объекты, которые могут перемещаться вперёд-назад (и получать значения)
Справиться с линейным поиском по значениям без наложения ограничений на сами значения нельзя. Но я не очень понял зачем Вам искать по значениям (только как деталь реализации с координатами - но это решается курсорами).
Но зато можно делать дерево поиска по составному ключу. В качестве ключа мы используем пары (K1, K2). Порядок сравнения в них лексикографический. Тогда с одной стороны, у нас есть дерево поиска по (K1, K2) без повторяющихся ключей, а с другой стороны - дерево поиска по K1, но уже с повторяющимися ключами.
P. S. Имхо, делать обобщенные(в смысле дженериков) структуры данных не очень полезно. Гораздо важнее делать структуры данных под конкретные применения — там можно гораздо лучше использовать специфику задачи.
Это не всегда хорошая затея.
Фишка в том, что этот "худший" случай не может происходить слишком часто. Если выражаться формально, то там аммортизированное O(1).
Если вы не желаете структуры данных под реальное время, то вам стоит смотреть на суммарное время выполнения операций — а оно у списков кратно быстрее.
Вообще нет. Если бы это было бы так, мы бы все использовали фибоначеву кучу и галактические алгоритмы (спойлер: у них очень хорошее O, но на всех доступных сейчас объёмах данных, они очень медленные).
Ну, или с другой стороны: знали ли Вы, что современные реализации сортировок используют сортировку вставками, а не квиксорт в некоторых случаях — так быстрее.
Оно unsafe - это правда, но это не имеет отношения к синшному аби. Для сишного аби нужно использовать extern "C" а также использовать только типы со стабильным аби. Хотя данный конкретный пример настолько простой, что есть тупо нет альтернативных вариантов.
Впрочем, я перечитал с чего начался тред, и проблема в том, что раст умеет инлайнить функции из dylib (через split metadata, или через метадату прямо в dylib). И с недавних пор раст автоматически помечает простые функции как #[inline].
Чтобы этого избежать можно пометить функцию как #[inline(never)]. Или же увеличить тело функции, чтобы раст не инлайнил эту функцию.
А, они так и не реализовали used для функций. Тогда только no_mangle