On Fri, Mar 1, 2019 at 5:17 PM Sergei M. Abramov abram_AT_botik.ru < 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). ;-) Ну а мы > это дело перелопатили потом. > > Всего доброго, > > Сергей Абрамов > >
