Comments 96
А кэш очищался перед каждым прогоном теста?
Если нет — в первом прогоне (или даже в генерации данных) было обращение к памяти, а во втором и следующих прогонах измерялась скорость повторного доступа к кэшу. То есть, не было случайного паттерна доступа и проявлялось ускорение за счёт кэширования (пологие участки на графиках).
Отсюда важный вывод: если вам нужно обращаться к одному и тому же участку памяти несколько раз, то минимизируйте промежутки между обращениями.
Обращение к одному и тому же участку — это не произвольный доступ. Даже если это не один блок памяти, а множество участков, расположенных не подряд, как в связном списке.
В статье почему-то говорится о произвольном доступе, хотя тесты проводятся много итераций для одного и того же списка (я посмотрел код автора на гитхабе). Естественно, список кэшируется (полностью или нет). И это влияет на результаты тестов. Если для каждой итерации брать разные списки (расположенные в некэшированных участках памяти) — полагаю, результаты будут другими.
Не сразу заметил, что под временем доступа O(√N) имеется в виду среднее время доступа к объёму памяти N (именно это, а не что-то другое, замеряет автор своими тестами), а не худшее время одиночного чтения.
В рамках этой статьи мы O(f(N)) будет означать, что f(N) — это верхняя граница (худший случай) по времени, которое необходимо для получения доступа к N байтов памяти (или, соответственно, N одинаковых по размеру элементов).
Так — да, почти сходится. Вместо O(N) из-за кэша получается что-то вроде O(√N), когда есть повторные обращения. Но не вместо O(1), не вместо единичного чтения! И замеряется не худший случай, а средний.
Аналогия с хождением по библиотеке странная. Когда контроллер памяти выставляет 32 бита адреса, он сразу (через фиксированное число тактов) получает доступ к любому из 2^32 байт информации. Если 64 бита — к любому из 2^64 байт. Никто никуда не ходит! Латентность не растёт пропорционально корню количества данных.
Аналогия с чёрной дырой ещё страннее. При современных (невысоких) плотностях и объёмах наверняка можно хранить информацию на узлах в трёхмерной структуре в количестве, пропорциональном объёму структуры, а не площади.
Очень спорная статья, с неверной методикой замеров и странными размышлениями. Неудивительно, что столько людей посчитали её юмором.
Латентность не растёт пропорционально корню количества данных.
Как раз основная мысль статьи — что в зависимости от размера памяти, используемой программой, меняется и латентность доступа к ней. Если программа активно использует 10 кб памяти — то все данные будут в самом быстром кеше, и время произвольного доступа допустим 1 нс. Если же программа активно использует 1 Гб памяти, то (в случае случайного обращения к ним) задержка при каждом обращении будет уже 100 нс.
Если это не «Латентность растёт пропорционально корню количества данных.» — тогда что?
Вместо O(N) из-за кэша получается что-то вроде O(√N), когда есть повторные обращения. Но не вместо O(1), не вместо единичного чтения!
Вот именно что sqrt(N) — это время единичного чтения! Видимо действительно статья написана не очень хорошо, раз столько людей не понимают, что имеет в виду автор.
А уж как получить sqrt(N) вместо N для обхода всех элементов (всего), это я вообще не понял у вас. Всё равно нужно как минимум O(N) операций, как ни крути.
Отличный шуточный пост посреди недели, спасибо! Можно с серьезным лицом показывать коллегам и встревоженно спрашивать "о б-ги, как же нам жить дальше?".
По сути поста — плохая аналогия подобна котенку с дверцей. Если всю мякотку свести к одному практическому примеру, то вы утверждаете, что компьютер с 64 ГБ памяти тратит на получение 1 байта в восемь раз больше времени, чем компьютер с 1 ГБ памяти. Ну конечно же так и есть! Даже поспорить не с чем. Пока библиотекарь дойдет до границы чипа, пока найдет нужный байт в каталоге байтов… А там и обед уже, а потом и короткий день.
Ну и да, глупый вопрос не по теме — с чего вы вообще взяли, что доступ к произвольному элементу связного списка — это O(1)?
P.S. У вас все [ссылки] отвалились.
Если всю мякотку свести к одному практическому примеру, то вы утверждаете, что компьютер с 64 ГБ памяти тратит на получение 1 байта в восемь раз больше времени, чем компьютер с 1 ГБ памяти.Вы вообще разницу между
N и O(N) понимаете?Возьмите сотню компьютеров с 1 ГБ памяти и соответствуюших им компьтеров с 64 ГБ памяти разных поколений, устредните — и, скорее всего, примерно 8 раз разницу и получите. Потому что в совсем старых системах у вас 1ГБ памяти будет стоять на каком-нибудь Pentium3, а 64 ГБ — это будет NUMA-монстр с дикими задержками и там разница будет раз в сто. Сегодня 1ГБ — это будет настольный комп, а 64 ГБ — это будет Xeon и с регистровой памятью и разница может быть раза в два. Завтра — это всё попадёт на «плоский участок» и разницы не будет, а послезавтра — 1ГБ попадуют в кеш L3 и мы снова получим разницу в два порядка.
Это как раз ваши аналогии подобны котёнку с дверцей…
Мне как то довелось выяснять что быстрее обращается к элементу, deque или vector. Совершенно разные O.
Кстати, моделей и до этого было несколько. В той же теории алгоритмов принято время на сложение двух чисел и объем занимаемой числами памяти считать равным O(log M), где M — само число; на практике же обычно принимают их за O(1), а не ограниченность типов данных закрывают глаза (хотя с точки зрения математики понятие O и ограниченность сверху несовместимы).
А уж при переходе к модели Машины Тьюринга и вовсе вся асимптотика настолько меняется, что вопрос «какой алгоритм быстрее» даже не ставится.
А вот в при построении архитектуры процессора понятие «О большое» используют очень ограниченно либо вовсе не используют — потому что, во-первых, борьба идет за каждый такт — а во-вторых, ограничения сверху довольно низкие.
32 разряда для процессора — это 32 разряда, а для прикладной программы — 4 миллиона допустимых значений.
А определение для O никто и не меняет.
Emil Ernerfeldt просто забыл в определение константу ;) Если мы возьмем константу равной доступа к SSD, то оценка сверху не измениться.
Просто автор предложил новую модель абстрактного вычислительного устройства чтобы можно было лучше оценивать какой из алгоритмов быстрее.
Ничего он не предложил, т.к. этот метод не работает для произвольной программы:
Но если вам нужно создавать объекты в разное время или перемешивать их, то ничего не получится.
Вот только сама эта константа будет меняться при переходе к всё более ёмким SSD, из-за растущих накладных расходов на хранение и извлечение данных. И эти расходы асимтотически приближаются к sqrt(N) при N стремящимся к бесконечности и плотности записи стремящейся к теоретическому пределу. Так что пофиксить проблему простым повышением константы не удастся, за неимением таковой константы.
госпади какой бред
Если вы оцениваете время доступа к некой определённой памяти, то стоит исключить из экспериментов обращения к прочим. После того, как это не получится сделать за разумное время, попробуйте составить математическую модель происходящего — ну, хотя бы полином, каждый член которого будет соответствовать уровню иерархии памяти — было бы интересно.
Подскажите, плиз, как для двоичного поиска получили сложность O(√N) из классической логарифмической, можно формулу, не понятно.
Спасибо.
Там не утверждается, что для двоичного поиска сложность будет O(√N). Но ее несложно вывести: требуется O(log N) операций доступа к памяти, каждое обращение стоит O(√N), так что итоговая сложность O(√N log N).
O(√N) + O(√N/2) + O(√N/4) +… (всего log(N) членов) = ??? (Сложность доступа к первому элементу + сложность доступа ко второму+...)
Смущает то что сложность при бинарном поиске:
O(1)+O(1)+O(1)+...(всего log(N) членов) = O(log(N) (Сложность доступа к первому элементу + сложность доступа ко второму+..., классическая формула)
Поэтому решаю первую формулу:
O(√N + √N/2 + √N/4 +… ) = O(√N*(1+√1/2+√1/4+...) = (тут я не знал как упростить ряд, но взял калькуляpython получил что ряд сходится к ~3.41, и достигает 3.41 уже при 20 членах.
Поэтому сложность = O(3.41*√N)
А при учете сложности алгоритма константный умножитель не учитывается, получается O(√N)
поиск элемента в хеш-таблице это O(1)
Это неверно, даже если считать не время, а обращения к памяти. При фиксированной мощности хеш-функции p с ростом количества хранимых элементов N вероятность коллизии будет расти как N/p, то есть линейно по N (и это при удачной хеш-функции, а реально могут быть перекосы). Традиционные реализации хеш-таблиц подразумевают использование списков при коллизиях, так что получаем скорость доступа вообще O(N) в классических терминах.
На самом деле применение хеш-таблиц оправдано для случаев, когда коллизии редки, то есть N не должно быть больше p, но тогда и O-анализ обессмысливается.
Я-то как раз понимаю, это мое профильное образование. Просто его часто используют слишком вульгарно, мне даже доводилось видеть такие таблицы:
чего-то там: O(1000)
чего-то сям: O(10^5)
(Имелось в виду, что некоторая величина имела значение порядка 10^3, 10^5, что вообще никакого отношения к O-нотации не имеет.)
Если ограничить load factor константой, и при ее превышении увеличивать таблицу и перехешировать все элементы, то сложность остается O(1) для поиска, O(1) для удаления и (амортизационно, в среднем) O(1) для добавления.
Вопрос к автору. У вас осталась программа, которой вы меряли производительность? Интересно, чтобы вы модифицировали ее определенным образом (если осталась — я опишу каким) — и потом провели снова замеры. Но к sqrt(n) это уже не относится. Просто интересно проверить одну штуку.
Так же, было б полезно залить на гитхаб ее.
Автор вам вряд ли ответит, так же, как всем вышеспросившим. Это перевод.
А тестовая программа есть на гитхабе: https://github.com/emilk/ram_bench
Это математики, решили, что физики опять шутят.
У автора ошибка в рассуждениях. Если график строить и дальше вправо, то он так и останется горизонтальным, на уровне 1 микросекунды. После HDD никаких новых уровней ухудшения производительности памяти не будет, и раз О-большое меряет поведение только при больших значениях, то оно так и будет константой.
После HDD никаких новых уровней ухудшения производительности памяти не будетО как. Вот прямо даже так? А сколько эксабайт было в системах, с которыми вы работали, нельзя спросить? И как вы их упихали на несколько HDD?
За HDD сначала идёт стойка (из 40 машин примерно), потом кластер, потом датацентр, потом региональная коллекция датацентров, потом глобальная коллекция датацентров…
На каждом шаге идёт увеличение задержек и снижение ширины канала доступа, увы. Так где всё кончается — кончается и график. Никакого осмысленного горизонтального участка (на двойной логарифмической шкале!) там нету.
Ну, что является самым плотным во вселенной? Черная дыра! [Оказывается], что масса черной дыры пропорциональна радиусу: m ∝ r. То есть количество информации, которую можно поместить в сфере радиусом r это N ∝ r²
О чем это вообще? Как вообще количество информации может описываться расстоянием? Заранее спасибо за разъяснение.
Максимальное количество информации, которое можно сохранить в некотором объекте, совпадает с его энтропией и является логарифмом числа возможных различимых состояний этого объекта.
Любую информационную систему может поглотить черная дыра — и, согласно второму закону термодинамики, суммарная энтропия от этого не увеличится. Отсюда следствие — энтропия любой информационной системы не может превышать энтропию черной дыры тех же размеров.
Черная дыра может хранить информацию только на горизонте событий — поэтому ее энтропия пропорциональна площади горизонта событий, то есть квадрату радиуса.
Следовательно, максимальное теоретически достижимое количество информации, которую может хранить информационная система, ограничено значением, пропорциональным квадрату радиуса описанной вокруг системы сферы.
Разумеется, этот предел глубоко теоретический и еще долго будет оставаться таковым.
Как-то так. Не самая знакомая для меня область — мог что-то напутать.
Для образования ЧД подойдет любая форма энергии, в том числе безмассовая.
Вы так дойдёте до того, что скажите, что два звездолёта утетающих в разные стороны от Земли со скоростью 0.9c удаляются друг от друга со скоростью 1.8c, ага. Не надо так.
никаких базмассовых частиц в природе просто не существует
Современное определение массы имеет в виду только массу покоя. Хотя это и не опровергает вас в отношении возможности образования черной дыры из фотонов.
На самом деле это он про голографический принцип. У Леонарда Сасскинда в его «Битве при чёрной дыре» это хорошо объяснено. Голографический принцип утверждает, что всё находящееся внутри некоторой области пространства, можно описать посредством битов информации, расположенных на её границе. Дальше я привожу цитату из книги, глава 18, «Мир как голограмма»:
Самая массивная вещь, которую можно запихнуть в нашу область, — это чёрная дыра, горизонт которой совпадает с границей. Вещи не должны быть массивнее её, в противном случае они не поместятся внутри границы, но существует ли какой-то предел, ограничивающий число битов информации в этих вещах? Нас интересует определение максимального числа битов, которое можно запихнуть внутрь сферы.
Теперь представьте себе материальную сферическую оболочку — уже не воображаемую границу, а сделанную из настоящего вещества, — окружающую всю рассматриваемую систему. Эта оболочка, будучи сделанной из реальной материи, имеет собственную массу. Из чего бы она ни состояла, её можно сжимать внешним давлением или гравитационным притяжением находящегося внутри вещества, пока она идеально не совпадёт с границей области.
Исходные вещи, которые были у нас с самого начала, содержат некоторое количество энтропии — скрытой информации, — значение которой мы уточнять не будем. Однако нет сомнений в том, что окончательная энтропия — это энтропия чёрной дыры, то есть её площадь, выраженная в планковских единицах.
Для завершения доказательства остается лишь напомнить, что второе начало термодинамики требует, чтобы энтропия всегда возрастала. Поэтому энтропия чёрной дыры должна быть больше, чем у любых исходных вещей. Сводя всё воедино, получаем доказательство удивительного факта: максимальное число битов информации, которое может при каких угодно условиях поместиться в области пространства, равно числу планковских пикселов, которые можно уместить на площади её границы. Неявно это означает, что существует «граничное описание» всего, что происходит внутри области пространства; поверхность границы — это двумерная голограмма трёхмерной внутренней области. Для меня это самый лучший тип доказательства: пара фундаментальных принципов, мысленный эксперимент и далеко идущие выводы.
Или я что то упускаю?
Для того, чтобы обратиться к ячейке информации — надо послать к ней сигнал и получить ответ. При постоянной скорости распространения сигнала время доступа пропорционально расстоянию. А среднее расстояние зависит от объема памяти.
Чем больше в компьютере памяти — тем больше время доступа к ней. Значит, время доступа не является константой.
Статья конечно интересная, но мне показалось что автор сознательно выбрал логарифмическую шкалу. При использовании обычной шкалы ситуация становится совсем не настолько страшной, http://joxi.ru/bmovQbxFMK1Bwr т.е. можно с точки зрения алгоритмов считать что доступ к памяти имеет сложность O(1) пока память собственно есть. Первоначальные 4Mb скоростного доступа можно считать бонусом. Если начать учитывать их, то это уже не асимптотика а попытка точно вычислить время работы программы, что полезно в конкретных задачах (например программисты микроконтроллеров, там свой мир) но в общей теории алгоритмов почти бесполезно.
Если вам нужно стабильно использовать больше памяти чем есть на устройстве, то может стоит задуматься о покупке лишней планки? Опять же, использование памяти в таких объёмах обычно следствие решения специфических задач (например big data) которые имеют свою теорию, свои алгоритмы и так далее.
Поэтому моё мнение: утверждение что сложность бинарного поиска O(log N * sqrt N) — казуистика и отражает реальную ситуацию в весьма ограничем количестве случаев.
Вы правы в том, что если рассуждать о скорости работы разных математических компроютеров — то O(1) может быть неплохой точкой отсчёта.
Но вопрос: как потом это всё к реальному-то компьютеру приложить? Человеку ведь все эти O(1) и O(N) не нужны как бы совсем, ему нужно чтобы 60 кадров в секунду картинка обновлялась и компьютер «не тупил».
Как это приложить к реальному компьютеру это тема отдельного разговора.Но computer science, не приложенный к компьютеру — это мастурбация какая-то!
А конкретные приложения к реальному компьютеру делаются в первую очередь тестированием и профилированием применительно к конкретному оборудованию.С этого момента — поподробнее. Давайте исключим код, который затачивается под конкретное железо (PlayStation4 или там суперкомпьютер какой — неважно).
Рассмотрим обычный такой код, который пишется сегодня и будет использоваться, в том числе, и в 2030м году (это, собственно, подавляющее большинство создаваемого кода: мало кто бросается переписывать всё с нуля при выходе очередного творения от Intel'а или там ARM'а). Как тут «профилированием применительно к конкретному оборудованию» обойтись?
Тут действительно очень сильно не хватает тега "юмор".
Нельзя же считать размер памяти произвольным. Как минимум рано или поздно исчерпается адресное пространство, после чего любой описанный в статье алгоритм будет работать за O(1).
А вообще с таким же успехом можно утверждать, что модуль моего pgp-ключа можно разложить на множители за O(1), а также, что операция сложения выполняется не за O(1), а за O(log(N)), где N это размер машинного слова.
Куда интереснее было бы увидеть рассуждения касательно схемной сложности для обеспечения доступа к произвольной ячейке памяти.
> Как минимум рано или поздно исчерпается адресное пространство, после чего любой описанный в статье алгоритм будет работать за O(1).
Вы не поняли месседжа статьи, речь там о том, что мы проводим O-анализ в контексте совершенно другой модели памяти в принципе: это бесконечная иерархия кэшей (L1 → L2 → L3 → RAM → SSD → дисковый сервер → удаленный датацентр →… → сфера Дайсона → и так до бесконечности, все более и более удаленные физически области). То есть, в этой модели «адресное пространство» никогда не исчерпается. И говорить про O(1), который наступит при достаточном "zoom out" здесь уже нельзя. В этой модели нельзя «отзумиться до предела» — увидев ровную линию на графике. Провести O-анализ здесь можно исходя из физики пространства, в котором информация хранится, рассмотрев предельный случай — черную дыру. Именно это автор и делает в статье ;)
Откуда дровишки? Вы Вселенную с так называемой «видимой Вселенной» не перепутали, случаем? :)
Вообще это логично учитывая современные представления (большой взрыв + инфляция). Тот же объем не может быть бесконечным, т.к. расширение вселенной не могло достигать бесконечных величин, а хотя значение инфляции было велико, оно все же было конечным.
Таким образом область, докуда может дойти сигнал (а ведь он ещё должен вернуться) конечен, даже если вселенная истинно бесконечна.
Все отдают себе отчет, что есть разные тайминги доступа к разным уровням.
Время обращения к памяти — не строго монотонная функция!
А также данные и обращения к ним стараются выстроить так, чтобы они шли последовательно. Даже если не будет кеша, мы поимеем выгоду.
Вообще странная статья, будто автор недавно открыл кеширование. :)
Кстати, работа допустим с 1МБ данных не гарантирует, что они будут закешированы и доступны за 10 нс.
Что вообще переводчик думает о статье freetonik?
Использовался связанный список. Доступ был последовательным.
Ну и линейная зависимость соответсвует наклону графика в два раза больше, чем у синей линии — это явно далеко от истины.
Например, если частота обращения к «отдаленным» областям памяти убывает экспоненциально с ростом «удаленности» данных, тогда для алгоритма асимптотическая оценка времени доступа к памяти совсем другая будет.
Это учтено вот тут:
Стоит заметить, что действия, производимые между операциями, имеют значение. Если ваша программа работает с памятью размером N, то любой произвольный запрос к памяти будет O(√N). Так что проход по списку размером K будет стоить O(K√N). При повторном проходе (сразу, без обращения к другой памяти) стоимость будет O(K√K). Отсюда важный вывод: если вам нужно обращаться к одному и тому же участку памяти несколько раз, то минимизируйте промежутки между обращениями.
А сколько у автора статьи памяти на его ноутбуке?
Мне сдается, что у него 8Gb и вот эта вертикальная палка на 8Gb в конце вызвана тем, что у него кончилась память и он попал в swap на SSD диске. Потому как для кэша процессора 8Gb как-то много, а вот для объема памяти на ноуте в самый раз. Да и порядок замедления примерно соотвествует разницей между RAM и SSD диском вокнутым в SATA(не PCI-E).
Если эта теория верна, то скорее всего эта вертикальная палка не отражает реально скорость RAM, а отражает скорость SSD, и если запустить тест на 256Gb сервере там будет ровная полка, на которую супер теорию про доступ к памяти за O(sqrt(N)) ну никак не натянуть.
Поэтому предлагаю залинковать оригинал и посмотреть не первое апреля ли там дата, чтобы понять шутник автор, или идиот :)
Миф о RAM и O(1)