Переношу реплику Аркадия под этот сабж.
А то мысли про джунгли окажутся потерянными в нескольких тредах.
Андрей

On Wed, Feb 13, 2019 at 6:26 PM Arkady Klimov arkady.klimov_AT_gmail.com <
refal@botik.ru> wrote:

> То, о чем написал Сергей действительно полезно на практике. У меня
> написана некая система работы с полиномами, и там обрабатываются
> неравенства вида P(x,y,...) < K, где K - целое число, а P не содержит
> свободного члена. В списке таких неравенств часто надо находить неравенства
> с общей левой частью (подобные). Конечно, полиномы должны иметь
> канонизированное представление. Тогда, джунгли очень даже полезны будут при
> поиске пар подобных неравенств посредством образца
>                e1 (tA e) e2 (tA e) e3
> Ну и память экономится, если таких пар много.
>
> А насчет сборки мусора - так Антон и написал же, что ее нет, а есть
> счетчики ссылок. А нужна она только чтобы зависшие ящики подчищать. Но мне
> кажется, что это особо и не нужно - всегда можно руками вовремя обнулить.
> А если и вводить, то надо и "слабые" ссылки вводить.
>
> Другое дело, что возможно счетчики ссылок будут мешать распараллеливанию
> "над общей памятью". Даже если функции чистые и формально независимые, при
> параллельном выполнении придется корректировки ссылок делать защищенно,
> скажем atomic. Вопрос к залу: это не очень тормозить будет? Не потеряется
> ли эффект от распараллеливания? Надо б проверить.
> Аркадий К.
>
>
> вт, 12 февр. 2019 г. в 17:22, Eisymont Leonid verger-lk_AT_yandex.ru <
> refal@botik.ru>:
>
>> Так это массивное представление оправдало себя или нет? В сухом остатке
>> ведь - сборка мусора на ровном месте(раньше не было), какие-то переполнения
>> стеков. А в программах копирования списков не так уж и много, откуда этот
>> миф? Ради чего?
>> Наукообразия? Кто в больших программах про эти "джунгли" думать будет?
>> Имеются несколько недоработанных реализаций? Какая лучше всех, чем
>> пользоваться можно? Бенчмарки были или нет? М.б. просто рефал-2 взять и все
>> дела. Восстановить распараллеливание там хотя бы через машинные операции и
>> все. Прирост скорости будет в сотни раз на современных системах, а не
>> проценты или разы. Как быть?
>> Л.Эйсымонт
>>
>>
>> 12.02.2019, 15:53, "Sergei M. Abramov abram_AT_botik.ru" <refal@botik.ru
>> >:
>>
>> День добрый, всем!
>>
>> Антон, спасибо за детали. Думаю снято много обвинений в сторону
>> массивного представления ;-)
>>
>> Коллеги, и это не все фенечки еще описаны. Как мелкий пример: как мне
>> помнится (Антон поправит), были еще реализованы "коллапсирующие
>> джунгли" или "табулирование сравнения термов-скобок".
>>
>> Суть простая:
>>
>> 0. Терм-скобка это поинтер на первое звено p и длина L.
>>
>> 1. У сравнения двух термов-скобок на равенство есть масса быстрых слуюаев:
>> 1.0 Если L1 == 0 && L2==0, то термы равны
>> 1.1 Если L1 /= L2, то термы не равны,
>> 1.2 Если p1==p2 && L1==L2, то термы равны
>>
>> 2. Наконец, если нам пришлось делать длинное сравнение и в конце
>> выяснилось, что термы таки равны, то мы делаем "коллапсирующие
>> джунгли" -- делаем присваивание: p2 = p1, L2=L1 (второе лишнее, но
>> пусть будет). Тут и память освободилась и следующий раз сравнение на
>> равенство пройдет быстрее ;-)
>>
>> О! Ран-тайм рефала плюс полировался с любовью ;-)
>>
>> Всего доброго,
>>
>> Сергей Абрамов
>>
>>
>> Anton Orlov orlovan_AT_gmail.com.
>>
>> Вы писали 11 февраля 2019 г., 21:39:24:
>>
>>  Добрый день!
>>
>>  On Mon, Feb 11, 2019 at 12:50 PM Arkady Klimov
>>  arkady.klimov_AT_gmail.com <http://arkady.klimov_at_gmail.com/> <
>> refal@botik.ru> wrote:
>>
>>  Может ли кто ответить на такие вопросы по реализации Рефал+ на C++
>>  (в статье они не обсуждается - не тот уровень абстракции):
>>
>>  1.Какая организована работа с памятью? Какой менеджер памяти
>>  используется? Свой или каждый новый чанк через malloc запрашивается?
>>
>>  Сделан свой аллокатор по алгоритму близнецов, описанному Кнутом
>>  (https://en.wikipedia.org/wiki/Buddy_memory_allocation). Это делал
>> Андрей Слепухин.
>>
>>  2.Используются ли счетчики ссылок? Или полная сборка мусора время от
>> времени? Какой сборщик мусора?
>>
>>  Используются счётчики ссылок. Полной сборки мусора нет, поэтому
>>  память может течь (например, возможны циклы через ящики). Сборка
>>  мусора была в планах, но так и не была реализована (на практике
>> надобность в ней не ощущалась).
>>
>>  3.Есть ли версия конкатенации inplace (когда память для выражения
>>  взята "с запасом")? Андрей уже ответил частично.
>>
>>  В алгоритме близнецов все выделяемые куски имеют размер 2^n.
>>  Выражение помещается посередине нового куска, а справа и слева
>>  естественным образом получается запас по месту. При конкатенации,
>>  если этой дырки рядом с одним из выражений достаточно, то копируется
>>  только одно из выражений, а новая память не выделяется.
>>
>>  Например, если выражение длины N строится дописыванием в
>>  конец/начало по одному терму, то это требует O(log N) аллокаций
>>  (амортизированная стоимость O(1)).
>>
>>  Антон
>>
>>  P.S. Помимо списков и массивов есть ещё потенциально интересные
>>  структуры данных для представления выражений. Например, rope
>>  (https://en.wikipedia.org/wiki/Rope_(data_structure)) и Finger tree
>>  (https://en.wikipedia.org/wiki/Finger_tree), но серьёзно для
>>  рефальского применения их никто не исследовал, насколько я знаю.
>>
>>  Буду благодарен за разъяснения.
>>  Аркадий
>>
>>  пн, 11 февр. 2019 г. в 11:12, Sergei M. Abramov abram_AT_botik.ru <
>> refal@botik.ru>:
>>
>>  Замысловатый ответ ни о чем.  Так какой результат, если есть статьи,
>>
>>  >> то ссылки где?.
>>
>>   http://www.botik.ru/PSI/RCMS/publications/publications.html
>>
>>   А далее Гуугл "site:www.botik.ru/PSI/RCMS/publications Рефал Плюс"
>>
>>   И там сразу находим:
>>
>>
>> http://www.botik.ru/PSI/RCMS/publications/publ-texts/04-Abramov-Novyj-podkhod-p-373.pdf
>>
>>   С уважением,
>>
>>   Абрамов С.М.
>>   ab...@botik.ru
>>   мобильный: +7(903)2928308
>>
>> --
>> С уважением,
>> Абрамов С.М. mailto:ab...@botik.ru
>>
>> --
> _______________
> *С уважением, *
> *Аркадий Климов,*
> *с.н.с. ИППМ РАН,*
> *+7(499)135-32-95*
> *+7(916)072-81-48*
>
    • ... Andrei Klimov andrei . klimov_AT_gmail . com
      • ... Sergei Romanenko sergei . romanenko_AT_supercompilers . ru
        • ... Александр Коновалов a . v . konovalov87_AT_mail . ru
      • ... Александр Коновалов a . v . konovalov87_AT_mail . ru
        • ... Andrei Klimov andrei_AT_klimov . net
      • ... Andrei Klimov andrei_AT_klimov . net
        • ... Александр Коновалов a . v . konovalov87_AT_mail . ru
          • ... Andrei Klimov andrei_AT_klimov . net
            • ... Александр Коновалов a . v . konovalov87_AT_mail . ru
              • ... Andrei Klimov andrei_AT_klimov . net
              • ... Andrei Klimov andrei_AT_klimov . net
        • ... Anton Orlov orlovan_AT_gmail . com
          • ... Александр Коновалов a . v . konovalov87_AT_mail . ru
  • Re:... Andrei Klimov andrei_AT_klimov . net

Ответить