Ну, что делает это кеш нам не описали, поэтому ничего кроме рукомахательства я Вам не смогу сказать.
Основная идея в том, что вместо того чтобы создавать кучу маленьких списков, часто гораздо эффективнее будет создать один большой список. К этому списку обычно требуется также какая индексная структура данных, но это в среднем наоборот ускоряет код. Это нам немного ломает ооп-шные абстракции, но зато открывает путь к весьма интересным оптимизациям.
Наверное каноничным примером подобного преобразования является СНМ. В ней мы вместо того, чтобы хранить множества как отдельные структуры данных, складывается все множества в одну огромную структуру данных — но это даёт нам непревзойдённую эффективность объединения множеств почти за константу.
Если говорить из современных инкарнаций, то подобное преобразования можно найти в AoS -> SoA(struct of arrays), ecs и в целом в data-oriented programming.
В этом подходе есть что-то интересное. Но пока что из него тяжело что-то извлечь. Таксономию можно строить как угодно и в ней может быть столько веток, сколько пожелает автор. Поэтому эти 3 варианта сами по себе ценности не несут.
Вопрос в том, как данной таксономией воспользоваться. Не хватает какого-то описания, как её применить для решения задач. И что гораздо важнее: а какие вообще задачи решаются. Этот вопрос в утрированной форме отражён в комментариях выше: а зачем вообще нужно что-то кроме мютекса?
Говоря о самой таксономии, мне кажется упущен один важный класс: native rmw. Этот класс включает в себя выполнение мутирующей операции за одну инструкцию. Например, атомарный инкремент часто компилируется в одну процессорную инструкцию. Хотя данный класс очень похож на 1-ый(cas-loop), он принципиально отличается отсутствием контеншена.
Last write wins
Вообще говоря так писать не очень хорошо. Поскольку у нас порядка между записями, то что такое "последняя запись" сказать сложно. Эта тонкая неоднозначность формулировок становится особенно видна когда появляются всякие visibility, ordering и happens before. Чуть корректнее говорить "some write wins".
P.S. В языках с gc ABA проблема почти никогда не возникает (разве что в интрузивных структурах данных — и то в каких-то патологических юзкейсах). Поэтому не очень понятно при чём здесь это.
P.P.S. CRDT это вообще не в ту степь. Они вообще не решают проблему мутации одного объекта — они рассматривают проблему мутации нескольких независимых копий. Поэтому кажется совсем не в тему (ну и тогда уже тащить также и OT, т.к. он гораздо чаще используется в рамках одного процесса).
Вы, видимо, недооцениваете производительность современных процессоров. В среднем квадратичный алгоритм выполняется достаточно быстро на 50-ти тысячах элементов и только дальше начинаются тормоза. И вполне себе реально, чтобы реальная нагрузка на код прилетела сильно позже (через месяцы, иногда годы) коммита в прод — в таком случае логическая цепочка может и не образоваться.
Плюс здесь играют роль такие факторы:
Незнание что быстрее вообще можно: "матрицы быстрее чем за N^3 умножать нельзя, куда там оптимизировать"...
Закидывание ресурсами/серверами/подами. Особенно усугубилось с введением горизонтального масштабирования.
Административным/бизнесовым запретом на отправку больших данных: "вы можете иметь не более 3 подписок"...
Поэтому, к сожалению, требуются очень хорошие процессы в плане тестирования и приёмки чтобы приобрести алгоритмическое мышление в рамках работы. Такое есть очень мало где.
Ну вот говорит говорит Вам нейронка: пиши здесь здесь два вложенных цикла. Вы возразите: "но это же O(n^2)!" А она Вам: всё будет работать быстро, там вложенный цикл выполняется редко. И как быть?
Или вот говорит она Вам: вот дерево/куча, без балансировки, используй его здесь. А это опять намёк на квадрат. Начинаете расспрашивать, и оказывается, что у них операции выполняются за "аммортизированный логарифм". И добро пожаловать в удивительное приключение об анализе аммортизированного времени.
К сожалению, есть довольно много весьма простых и эффективных алгоритмов, которые, тем не менее, имеют очень сложные доказательства корректности и ещё более сложный анализ сложности. И без хорошей алгоритмической подготовки(а иногда и с ней) эти доказательства не прочитать даже.
Кажется ключевая проблема не совсем в списках. Подобного рода динамические массивы вообще не предназначены для подписей, которые в памяти занимают место, сопоставимое с объёмом всей памяти. Ну просто банально потому, что всякие List и Dictionary дают нам скорость и удобство ценой очень сильного потребления памяти.
Как только разбрасываться памятью становиться расточительно — необходимы другие подходы и структуры данных. Тут можно применять как точное предвыделение памяти (как нас заставляет делать тот же zig). Так и всякие векторные трансформации: часто лучше разместить все данные этого "кеша" в одном большом массиве, — это и код упростит(внезапно), и перф даст. Печально, правда, что про векторные представления очень редко говорят :(
А где здесь про олимпиадное программирование? Самое типичное стимулирование на "тяп-ляп и в продакшен" — здесь дело в менеджменте. Какой людям таргет поставишь — такой результат и получишь.
Поэтому мы не можем говорить только о трёх процентах кода — тормозит всё и понемногу. Да, в особо неудачных приложениях, которые никто никогда не профилировал, можно найти узкое место, но после его починки мы вернёмся к ситуации равномерно неоптимального кода.
Это очень неочевидное утверждение, которое ещё нужно доказывать (через исследования!). Более того, обычно плоский профиль появляется именно в результате хорошей оптимизации.
Я внимательно вгляделся и, если заметите, нигде не говорил, что оно неправильно :)
Стоило в самом первом комментарии указать, что Вы говорите про упорядоченные поля. Я не считаю, что упорядоченные поля являются хорошим способом согласовать порядок с алгебраической структурой. Они требуют слишком многого (существования положительных чисел). Но опредедений лучше, увы, я не знаю
Как известно, алгоритмы заэто алгоритмы, которые падают только на проде (падают в смысле "выходят за все мыслимые пределы по времени").
Аналогичный пример: если не знать про FullScan vs IndexScan, то заметить наличие проблемного FullScan во время разработки — крайне маловероятно. И я видел примеры, когда делали таблицу с историческими данными без индексов...
А математики тут как помогут? Всё же довольно много алгоритмов на практике используют различные шорткаты и особенности задачи. Поэтому их сначала внедряют в прод, а потом, через годы приходят математики и оформляют их в какой-то общий алгоритм.
Вы выбираете эти условия весьма произвольно. Такими темпами можно дойти и до того, что нельзя ввести порядок на вещественных числах (потому что на натуральных есть свойства, которые не выполняются на вещественных).
Огласите полный список условий...
P.S. вещественные числа тоже ведут себя довольно странно: извообще говоря не следует.
Вы просто их по разным осям сравниваете. Если брать выразительность по какой-то оси и разрешимость по этой же оси, то основной тезис статьи для них будет верен, независимо от выбора оси (сравнения).
С другой стороны, 32-битный UNICODE не менее выразителен, чем UTF-8, и если пренебречь существованием комбинированных символов, с вычислением длины у него будет всё в порядке.
Не, с понятием "что такое длина" у него всё также плохо. Типичный пример: эмоджи, вязь, диактрики и прочее. (например, статья на эту тему)
Этот цикл никогда не завершится, но памяти потребляет O(1)
Не очень понятно, как это противоречит цитируемому тезису: "определить для произвольной машины ...". Если Вы про различие вида "не посчитается потому что бесконечный цикл" от "не посчитается потому что закончится память" — то это придирки.
Множество входных последовательностей, которые допускает регулярный автомат, может быть бесконечным, и тогда непонятно, что значит "определить множество входов", потому что непонятно, как его представить. Разве что как в виде самого автомата.
Здесь стандартный подход к этому — перечислимые множества. То есть множество определяется программой, которая по номеру элемента может за конечное время найти этот элемент, или сказать, что такого не существует (тогда множество конечно). Порядок элементов здесь не важен, если что.
Комплексные числа тоже можно линейно упорядочить. Например, их можно упорядочить в лексикографическом порядке.
Потеряете связь с алгебраической структурой (например изследует).
---
Короче говоря, кмк, придираетесь.
Не очень понятно, что такое "выразительность" и что такое "разрешимость"
Если вопрос о точном формальном определении, то оно здесь не очень нужно. Для любого разумного определения будет свойственна подобная дуальность/конфликт.
Если говорить конкретно про го, то логика у них примерно такая (только большие аллокации):
Если при аллокации памяти кусок ещё не занулён — зануляем его ручками, целиком
Но, там, вроде бы, есть фоновое зануление памяти, если есть лишние вычислительные ресурсы.
Если же говорить про "а как это вообще можно реализовать", то дело тоже не шибко хитрое. Опишу принцип, без какой либо оптимизации:
В каждый момент времени у нас есть два массива: текущий и следующий
В момент, когда наш текущий массив достиг заполненности r, мы аллоцируем новый массив, но не зануляем его
Дальше, при каждой выставке в текущий массив, мы зануляем R элементов в новом массиве (просто помним сколько мы уже занулили, сколько ещё нужно занулить)
Когда мы достигнет заполненности m, нам нужно переместить элементы в новый массив. Делать мы это будем лениво.
Соответственно теперь при каждой вставке мы будем перемещать по M элементов в новый массив
Когда мы достигнем заполненности x, мы просто сделаем новый массив текущим. Ожидается, что к этому моменту все элементы уже были перемещены.
В целом, нетрудно подобрать такие r, m и такие R, M, что каждый из этапов гарантированно будет успевать закончиться. Например: r=4/8, m=5/8, x=6/8, R=16, M=6, фактор роста массива в 2 раза. В такой схеме на каждой операции будет выполняться O(1) действий (по модулю коллизий и стоимости malloc).
Но, честно говоря, в тот момент, когда паузы от реллокаций станут действительно существенными, я бы просто перешёл на запрос сырой памяти от ОС (т.к. это будет проще и быстрее).
Тут вся фишка в том, что массивы — это архитектурный костыль с точки зрения CS, но при этом очень хорошо оптимизированный. Поэтому, у нас срабатывает два эффекта:
Сортировка массивом на порядок быстрее сортировки через дерево
Хешмапы на порядок быстрее деревьев, т.к. хешмапы в среднем находят ключ за 2-3 шага, а деревья вполне себе могут и 20 шагов потратить.
В оптимизации констант массивы, кеши и прочее — гораздо больше срабатывает.
Про константы замечание понятное. Но как раз суть в том, что у хешмапа (даже с учётом онлайн ресайзинга) константы ниже на любых размерах. Разве что может быть проблема с потреблением памяти — но кого оно волнует в жвм :)
"Когда важен порядок ключей" — непонятно что значит. Либо у нас есть какой-то дополнительный запрос, который учитывает порядок ключей (например lower bound) — об этом писал в самом начале.
Либо же нас интересует порядок итерации (например при выводе). Здесь есть странный хак: можно использовать хешмап, а при выводе сначала копировать в массив, а потом массив сортировать. Что удивительно, такой подход чаще будет быстрее чем TreeMap.
Поэтому действительно оправданым TreeMap становится тогда, когда мы на нём начинаем считать всякую статистику, или начинаем строить кастомные структуры данных. А это уже какая-то экзотика для типичного бэка.
Ну, что делает это кеш нам не описали, поэтому ничего кроме рукомахательства я Вам не смогу сказать.
Основная идея в том, что вместо того чтобы создавать кучу маленьких списков, часто гораздо эффективнее будет создать один большой список. К этому списку обычно требуется также какая индексная структура данных, но это в среднем наоборот ускоряет код. Это нам немного ломает ооп-шные абстракции, но зато открывает путь к весьма интересным оптимизациям.
Наверное каноничным примером подобного преобразования является СНМ. В ней мы вместо того, чтобы хранить множества как отдельные структуры данных, складывается все множества в одну огромную структуру данных — но это даёт нам непревзойдённую эффективность объединения множеств почти за константу.
Если говорить из современных инкарнаций, то подобное преобразования можно найти в AoS -> SoA(struct of arrays), ecs и в целом в data-oriented programming.
В этом подходе есть что-то интересное. Но пока что из него тяжело что-то извлечь. Таксономию можно строить как угодно и в ней может быть столько веток, сколько пожелает автор. Поэтому эти 3 варианта сами по себе ценности не несут.
Вопрос в том, как данной таксономией воспользоваться. Не хватает какого-то описания, как её применить для решения задач. И что гораздо важнее: а какие вообще задачи решаются. Этот вопрос в утрированной форме отражён в комментариях выше: а зачем вообще нужно что-то кроме мютекса?
Говоря о самой таксономии, мне кажется упущен один важный класс: native rmw. Этот класс включает в себя выполнение мутирующей операции за одну инструкцию. Например, атомарный инкремент часто компилируется в одну процессорную инструкцию. Хотя данный класс очень похож на 1-ый(cas-loop), он принципиально отличается отсутствием контеншена.
Вообще говоря так писать не очень хорошо. Поскольку у нас порядка между записями, то что такое "последняя запись" сказать сложно. Эта тонкая неоднозначность формулировок становится особенно видна когда появляются всякие visibility, ordering и happens before. Чуть корректнее говорить "some write wins".
P.S. В языках с gc ABA проблема почти никогда не возникает (разве что в интрузивных структурах данных — и то в каких-то патологических юзкейсах). Поэтому не очень понятно при чём здесь это.
P.P.S. CRDT это вообще не в ту степь. Они вообще не решают проблему мутации одного объекта — они рассматривают проблему мутации нескольких независимых копий. Поэтому кажется совсем не в тему (ну и тогда уже тащить также и OT, т.к. он гораздо чаще используется в рамках одного процесса).
Вы, видимо, недооцениваете производительность современных процессоров. В среднем квадратичный алгоритм выполняется достаточно быстро на 50-ти тысячах элементов и только дальше начинаются тормоза. И вполне себе реально, чтобы реальная нагрузка на код прилетела сильно позже (через месяцы, иногда годы) коммита в прод — в таком случае логическая цепочка может и не образоваться.
Плюс здесь играют роль такие факторы:
Незнание что быстрее вообще можно: "матрицы быстрее чем за N^3 умножать нельзя, куда там оптимизировать"...
Закидывание ресурсами/серверами/подами. Особенно усугубилось с введением горизонтального масштабирования.
Административным/бизнесовым запретом на отправку больших данных: "вы можете иметь не более 3 подписок"...
Поэтому, к сожалению, требуются очень хорошие процессы в плане тестирования и приёмки чтобы приобрести алгоритмическое мышление в рамках работы. Такое есть очень мало где.
Ну вот говорит говорит Вам нейронка: пиши здесь здесь два вложенных цикла. Вы возразите: "но это же O(n^2)!" А она Вам: всё будет работать быстро, там вложенный цикл выполняется редко. И как быть?
Или вот говорит она Вам: вот дерево/куча, без балансировки, используй его здесь. А это опять намёк на квадрат. Начинаете расспрашивать, и оказывается, что у них операции выполняются за "аммортизированный логарифм". И добро пожаловать в удивительное приключение об анализе аммортизированного времени.
К сожалению, есть довольно много весьма простых и эффективных алгоритмов, которые, тем не менее, имеют очень сложные доказательства корректности и ещё более сложный анализ сложности. И без хорошей алгоритмической подготовки(а иногда и с ней) эти доказательства не прочитать даже.
Кажется ключевая проблема не совсем в списках. Подобного рода динамические массивы вообще не предназначены для подписей, которые в памяти занимают место, сопоставимое с объёмом всей памяти. Ну просто банально потому, что всякие List и Dictionary дают нам скорость и удобство ценой очень сильного потребления памяти.
Как только разбрасываться памятью становиться расточительно — необходимы другие подходы и структуры данных. Тут можно применять как точное предвыделение памяти (как нас заставляет делать тот же zig). Так и всякие векторные трансформации: часто лучше разместить все данные этого "кеша" в одном большом массиве, — это и код упростит(внезапно), и перф даст. Печально, правда, что про векторные представления очень редко говорят :(
А где здесь про олимпиадное программирование? Самое типичное стимулирование на "тяп-ляп и в продакшен" — здесь дело в менеджменте. Какой людям таргет поставишь — такой результат и получишь.
Это очень неочевидное утверждение, которое ещё нужно доказывать (через исследования!). Более того, обычно плоский профиль появляется именно в результате хорошей оптимизации.
Насколько я понимаю, в тех же трансформерах, нет больших матриц. Там просто много маленьких матриц — вот поэтому от штрассена нет особого профита.
Если же идти в научные вычисления (например емнип intel mkl), то там вполне себе применяют штрассена.
Я внимательно вгляделся и, если заметите, нигде не говорил, что оно неправильно :)
Стоило в самом первом комментарии указать, что Вы говорите про упорядоченные поля. Я не считаю, что упорядоченные поля являются хорошим способом согласовать порядок с алгебраической структурой. Они требуют слишком многого (существования положительных чисел). Но опредедений лучше, увы, я не знаю
Как известно, алгоритмы за
это алгоритмы, которые падают только на проде (падают в смысле "выходят за все мыслимые пределы по времени").
Аналогичный пример: если не знать про FullScan vs IndexScan, то заметить наличие проблемного FullScan во время разработки — крайне маловероятно. И я видел примеры, когда делали таблицу с историческими данными без индексов...
А математики тут как помогут? Всё же довольно много алгоритмов на практике используют различные шорткаты и особенности задачи. Поэтому их сначала внедряют в прод, а потом, через годы приходят математики и оформляют их в какой-то общий алгоритм.
Вы выбираете эти условия весьма произвольно. Такими темпами можно дойти и до того, что нельзя ввести порядок на вещественных числах (потому что на натуральных есть свойства, которые не выполняются на вещественных).
Огласите полный список условий...
P.S. вещественные числа тоже ведут себя довольно странно: из
вообще говоря не следует
.
Вы просто их по разным осям сравниваете. Если брать выразительность по какой-то оси и разрешимость по этой же оси, то основной тезис статьи для них будет верен, независимо от выбора оси (сравнения).
Не, с понятием "что такое длина" у него всё также плохо. Типичный пример: эмоджи, вязь, диактрики и прочее. (например, статья на эту тему)
Не очень понятно, как это противоречит цитируемому тезису: "определить для произвольной машины ...". Если Вы про различие вида "не посчитается потому что бесконечный цикл" от "не посчитается потому что закончится память" — то это придирки.
Здесь стандартный подход к этому — перечислимые множества. То есть множество определяется программой, которая по номеру элемента может за конечное время найти этот элемент, или сказать, что такого не существует (тогда множество конечно). Порядок элементов здесь не важен, если что.
Потеряете связь с алгебраической структурой (например из
следует
).
---
Короче говоря, кмк, придираетесь.
Если вопрос о точном формальном определении, то оно здесь не очень нужно. Для любого разумного определения будет свойственна подобная дуальность/конфликт.
Если говорить конкретно про го, то логика у них примерно такая (только большие аллокации):
Если при аллокации памяти кусок ещё не занулён — зануляем его ручками, целиком
Но, там, вроде бы, есть фоновое зануление памяти, если есть лишние вычислительные ресурсы.
Если же говорить про "а как это вообще можно реализовать", то дело тоже не шибко хитрое. Опишу принцип, без какой либо оптимизации:
В каждый момент времени у нас есть два массива: текущий и следующий
В момент, когда наш текущий массив достиг заполненности r, мы аллоцируем новый массив, но не зануляем его
Дальше, при каждой выставке в текущий массив, мы зануляем R элементов в новом массиве (просто помним сколько мы уже занулили, сколько ещё нужно занулить)
Когда мы достигнет заполненности m, нам нужно переместить элементы в новый массив. Делать мы это будем лениво.
Соответственно теперь при каждой вставке мы будем перемещать по M элементов в новый массив
Когда мы достигнем заполненности x, мы просто сделаем новый массив текущим. Ожидается, что к этому моменту все элементы уже были перемещены.
В целом, нетрудно подобрать такие r, m и такие R, M, что каждый из этапов гарантированно будет успевать закончиться. Например: r=4/8, m=5/8, x=6/8, R=16, M=6, фактор роста массива в 2 раза. В такой схеме на каждой операции будет выполняться O(1) действий (по модулю коллизий и стоимости malloc).
Но, честно говоря, в тот момент, когда паузы от реллокаций станут действительно существенными, я бы просто перешёл на запрос сырой памяти от ОС (т.к. это будет проще и быстрее).
Ну, да, но опять же нет острой необходимости занулять всё и сразу при аллокации. Можно по мере работы с массивом постепенно его занулять.
На практике, плюс-минус везде используются всякие хаки с page fault-ами для того, чтобы лениво занулять страницы данных.
Если использовать calloc и аналоги, будет
. И емнип, в jvm будет именно calloc, а не ручное зануление.
В русскоязычном сообществе устоявшийся перевод - "корзин". Это не имеет отношения к bucket vs basket
Тут вся фишка в том, что массивы — это архитектурный костыль с точки зрения CS, но при этом очень хорошо оптимизированный. Поэтому, у нас срабатывает два эффекта:
Сортировка массивом на порядок быстрее сортировки через дерево
Хешмапы на порядок быстрее деревьев, т.к. хешмапы в среднем находят ключ за 2-3 шага, а деревья вполне себе могут и 20 шагов потратить.
В оптимизации констант массивы, кеши и прочее — гораздо больше срабатывает.
Про константы замечание понятное. Но как раз суть в том, что у хешмапа (даже с учётом онлайн ресайзинга) константы ниже на любых размерах. Разве что может быть проблема с потреблением памяти — но кого оно волнует в жвм :)
"Когда важен порядок ключей" — непонятно что значит. Либо у нас есть какой-то дополнительный запрос, который учитывает порядок ключей (например lower bound) — об этом писал в самом начале.
Либо же нас интересует порядок итерации (например при выводе). Здесь есть странный хак: можно использовать хешмап, а при выводе сначала копировать в массив, а потом массив сортировать. Что удивительно, такой подход чаще будет быстрее чем TreeMap.
Поэтому действительно оправданым TreeMap становится тогда, когда мы на нём начинаем считать всякую статистику, или начинаем строить кастомные структуры данных. А это уже какая-то экзотика для типичного бэка.