Добрый вечер, Андрей! «Хотя кэши тоже стали большими и рабочие множества в задачах обработки символьной информации стали больше в них помещаться, но по идее векторное представление должно обгонять.» Мне кажется, тут ещё и определяет сама структура данных. Например, для такой (условный пример) t.Expr ::= s.NUMBER | (t.Expr s.Op t.Expr) s.Op ::= '+' | '-' | '*' | '/' большой разницы между списком и вектором не будет (в плане использования кэша). Потому что и вектора-кусочки тоже будут маленькие, и тоже могут быть рандомно рассеяны по куче. Хотя, конечно, вектор будет требовать меньше памяти, и операции с ним будут быстрее. С уважением, Александр Коновалов From: Andrei Klimov andrei_AT_klimov.net <refal@botik.ru> Sent: Friday, March 1, 2019 6:56 PM To: refal@botik.ru Subject: Re: Сравнение веток Рефала On Fri, Mar 1, 2019 at 5:17 PM Sergei M. Abramov abram_AT_botik.ru <refal@botik.ru <mailto:refal@botik.ru> > wrote: День добрый, всем!
> ... По мере тасования памяти скорость падает до 2 раз. Тема диссертации Светланы Подколзиной (Трубицыной): реализация Лиспа с массивным представлением по направлению CDR. CAR -- ссылка, CDR -- соседняя ячейка (близось адресов). Тракторная сборка мусора, которая как бульдозер сдвигала все нужное, собирая свободные ячейки в крупные массивы. С чем боролись? Кэша тогда не было, а вот виртуальная память была. И по мере "тасования памяти" шаг в с;едующую ячейку списка с большой вероятностью приводил к пэйдж-фолту. Вот с этим и боролись. И сейчас есть с чем и за что бороться: * произвольный доступ в оперативную память – в кеш: один, другой... всё дольше и дольше, а в конце в большую память – 50-100 тактов * а доступ подряд идет с предвыборкой в кеш на максимальной скорости памяти Списковая память была еще терпима в 70-е годы, когда, например, на БЭСМ-6 <https://parallel.ru/history/besm6.html> доступ в память (2 мкс) был того же порядка, что и одна логическая операция (0.5 мкс) и совпадал с временем плавающей арифметики. Да и тогда на БЭСМ-6 доступ подряд шел по разным кубам памяти и был быстрее. А сейчас разница между произвольным доступом и доступом по подряд идущим адресам на 1-2 десятичных порядка – вопиюща. То есть пришло время векторных представлений в т.ч. и символьной информации. Хотя кеши тоже стали большими и рабочие множества в задачах обработки символьной информации стали больше в них помещаться, но по идее векторное представление должно обгонять. Очень было бы интересно провести сравнительные измерения такой же тщательности, как команда Леонида Эйсымонта делала в 80-е годы. Нужно брать задачи/тесты, которые можно промасштабировать от помещающихся в кеш до превышающих во много раз и посмотреть на графиках как списковая память проваливается. Обсуждающийся пример хорош. Но хотелось бы еще иметь прототипы реальных задач, например, обходы больших графов графов (коммивояжер и др.), компьютерная алгебра (базис Гребнера, феймановские диаграммы) и т.п. Я ставлю на то, что векторное представление заметно обгонит, когда объемы данных превысят кеш во много раз. (Не говоря уж об экономии памяти на ссылки.) Андрей Так что, грусть по массивному представлению имеет давнюю историю. А тот поход за массивным лиспом помню с удовольствием... Мы опирались на реализацию лиспа на фортране с исходными текстами. Фортрановская колода, не очень здоровая. В начале которой просто были описаны два COMMON массива: CAR(1000000) и CDR(1000000). ;-) Ну а мы это дело перелопатили потом. Всего доброго, Сергей Абрамов
