Как писать быстрые программы

[wrest]

wrest в сообщении #1721599 писал(а):

Если цикл длинный, стек вырастает пропорционально и очищается по выходу из цикла. Для скорости это хорошо. Но как-то всё-таки недодумано. Вместо увеличения стека можно было бы его дропнуть.

Так и оказалось. Перед входом в цикл запоминается текущее значение стека. А в цикле проверяются два условия 1) не превысило ли стартовое значение лимит1 и 2) не превысило ли текущее значение лимит2
Поскольку в цикле стартовое значение не меняется, то первое условие никогда не выполняется и очистка никогда не происходит. Пытаюсь понять зачем так делает gp2c и не могу понять. Переделал прямо в Си, исключив первую проверку и оставив только вторую - и всё норм стало, необходимости в увеличении стека не возникает.

[Dmitriy40]

wrest
Это надо продублировать в тему про PARI (здесь затеряется) и плюс сообщить разработчикам.

[wrest]

Dmitriy40 в сообщении #1721616 писал(а):

Это надо продублировать в тему про PARI (здесь затеряется) и плюс сообщить разработчикам
.

Ну я пока надеюсь что это я не так понял, а не что косяк в gp2c
Длинные циклы по идее - обычное дело. Может где какой ключ есть или типа того.

[Dmitriy40]

Т.е. даже такой цикл будет вызывать переполнение стека?
for(k=1,10^9, n=k+3)
А покажите во что он компилируется?

[wrest]

Dmitriy40 в сообщении #1721620 писал(а):

Т.е. даже такой цикл будет вызывать переполнение стека?

Нет, этот не вызывает.
Функция .gp
stk(lim)=my(n=0);for(k=1,lim, n=k^4+3);
Функция .gp.c

Используется синтаксис C

/*-*- compile-command: "aarch64-linux-android-clang -c -o stk.gp.o -O3 -Wall -fno-strict-aliasing -fstack-protector-strong -Oz -isystem/data/data/com.termux/files/usr/include/c++/v1 -isystem/data/data/com.termux/files/usr/include -fPIC -I\"/data/data/com.termux/files/usr/include\" stk.gp.c && -o stk.gp.so stk.gp.o -Wl,-rpath,/data/data/com.termux/files/usr/lib "; -*-*/
#include <pari/pari.h>
/*
GP;install("init_stk","v","init_stk","./stk.gp.so");
GP;install("stk","vD0,G,","stk","./stk.gp.so");
*/
void init_stk(void);
void stk(GEN lim);
/*End of prototype*/

void
init_stk(void)    /* void */
{
  pari_sp ltop = avma;
  avma = ltop;
  return;
}

void
stk(GEN lim)      /* void */
{
  pari_sp ltop = avma;
  GEN n = gen_0;
  {
    pari_sp btop = avma;
    GEN k = gen_0;
    for (k = gen_1; gcmp(k, lim) <= 0; k = gaddgs(k, 1))
    {
      n = gaddgs(gpowgs(k, 4), 3);
      if (gc_needed(btop, 1))
        gerepileall(btop, 2, &n, &k);
    }
  }
  avma = ltop;
  return;
}

 

Ключевые строки

25     pari_sp btop = avma;

и

30       if (gc_needed(btop, 1))
31        gerepileall(btop, 2, &n, &k);

avma - глобальная переменная, расстояние до дна стека

Блок с gc_needed (paristio.h)

Используется синтаксис C

#  define _gc_needed(av,n) (avma < (pari_sp)stack_lim(av,n))
/* Define this to thoroughly check "random" garbage collecting */
#ifdef DEBUG_LOWSTACK
#  define low_stack(x,l) 1
#  define gc_needed(av,n) ((void)av,1)
#else
#  define low_stack(x,l) ((void)(x),avma < (pari_sp)(l))
#  define gc_needed(av,n) (_gc_needed(av,n) && (av) > ((pari_mainstack->bot >> 1) + (pari_mainstack->top >> 1)))
#endif

#define stack_lim(av,n) (pari_mainstack->bot+(((av)-pari_mainstack->bot)>>(n)))

То есть, зафиксированный в 25 строке btop дальше в цикле не меняется, и gc_needed всегда возвращает false

если вместо встроенного gc_needed

#  define gc_needed(av,n) (_gc_needed(av,n) && (av) > ((pari_mainstack->bot >> 1) + (pari_mainstack->top >> 1)))

сделать свой, например:

#define my_gc_needed(av,n) (avma < (pari_sp)stack_lim(av, n))

То он будет время от времени возвращать true, вызывая сбор мусора.

[Dmitriy40]

Раз k+3 не вызывает переполнения стека, а k^4+3 вызывает, дело в затрате стека на промежуточный результат gpowgs() в gaddgs(gpowgs(k, 4), 3). Странно почему в конце строки стек не освобождается, ведь область видимости промежуточной переменной закончилась, похоже это оптимизация скорости.
И тогда стоит обойтись без промежуточных переменных и переполнение стека исчезнет. Типа вместо n=k^4+3 написать n=k^4;n=n+3. Но это извращение.
Может можно как-то принудительно вызвать сборку мусора? Тогда добавить счётчик итераций и каждую скажем 100-тысячную вызывать сборку мусора.

[wrest]

Dmitriy40 в сообщении #1721624 писал(а):

Может можно как-то принудительно вызвать сборку мусора? Тогда добавить счётчик итераций и каждую скажем 100-тысячную вызывать сборку мусора.

Ну так я принудительно и попробовал, просто сверяя текущий размер стека с половиной от максимального.

wrest в сообщении #1721621 писал(а):

#define my_gc_needed(av,n) (avma < (pari_sp)stack_lim(av, n))

Ну вернее не с половиной а с какой-то долей, определяемой параметром n, при n=1 с 1/2; при n=2 с 1/4 и т.п.
Я поставил 1, то есть с половиной.
Но это требует редактирования Си кода и перекомпиляции, что канеш такое себе...

Но вообще, можно и на каждой итерации собирать мусор, если просто убрать/закомментировать строчку 30 тут:

30       if (gc_needed(btop, 1))
31        gerepileall(btop, 2, &n, &k);

будет немного медленнее (зависит от "тяжести" тела цикла).
gerepileall перемещает переменные (в примере выше n и k) в кучу, очищает стек, вовращает переменные из кучи в начало стека и очищает от них кучу. Но если тело цикла "тяжелое" то накладных расходов не много.

[wrest]

Yadryara в сообщении #1721608 писал(а):

Да, проблемы с памятью сохраняются. Именно такие. Идёт какое-то странное её потребление в зависимости от количества циклов и операций в них. В том числе при нынешнем счёте — порой тратятся гигабайты.

Ну вот сейчас начинает проясняться причина, но надо смотреть Си код того цикла, где память потребляется.
Почитайте несколько последних моих постов, где я излагаю возможную причину.

[Dmitriy40]

wrest в сообщении #1721626 писал(а):

gerepileall перемещает переменные (в примере выше n и k) в кучу, очищает стек, вовращает переменные из кучи в начало стека и очищает от них кучу. Но если тело цикла "тяжелое" то накладных расходов не много.

Может сделать проще: переменную цикла объявить ранее чтобы она была не на стеке, в начале цикла тупо обнулять стек (btop=avma) - не будет зависимости между итерациями, а уж одно присваивание быстро. В начале цикла вместо более логичного конца - из-за next/break. Правда не уверен что будет работать - непонятно как n и k оказались на стеке вместо кучи и как их (как минимум k) разместить в куче (может через my(k)?).

[wrest]

Dmitriy40 в сообщении #1721630 писал(а):

Может сделать проще: переменную цикла объявить ранее чтобы она была не на стеке, в начале цикла тупо обнулять стек (btop=avma) - не будет зависимости между итерациями, а уж одно присваивание быстро. В начале цикла вместо более логичного конца - из-за next/break.

Что-то такое, да. Но процедуры очистки используют set_avma(), а gp2c иногда вставляет avma=btop и подобное, в общем там неясно. Плюс в Сишном коде как я понимаю (может неверно) переменные сквозь циклы не видны, короче надо погружаться в синтаксис
Вот например gerepileall ( это типа устаревшее, современное gc_all, синоним):

Используется синтаксис C

INLINE GEN
gc_all(pari_sp av, int n, ...)
{
  int i;
  va_list a; va_start(a, n);
  if (n < 10)
  {
    GEN *v[10];
    for (i=0; i<n; i++) { v[i] = va_arg(a,GEN*); *v[i] = (GEN)copy_bin(*v[i]); }
    set_avma(av);
    for (i=0; i<n; i++) *v[i] = bin_copy((GENbin*)*v[i]);
    va_end(a); return *v[0];
  }
  else
  {
    GEN z, **v = (GEN**)pari_malloc(n*sizeof(GEN*));
    for (i=0; i<n; i++) { v[i] = va_arg(a,GEN*); *v[i] = (GEN)copy_bin(*v[i]); }
    set_avma(av);
    for (i=0; i<n; i++) *v[i] = bin_copy((GENbin*)*v[i]);
    z = *v[0]; pari_free(v); va_end(a); return z;
  }
}

[Dmitriy40]

wrest в сообщении #1721632 писал(а):

Плюс в Сишном коде как я понимаю (может неверно) переменные сквозь циклы не видны

Там общее правило: внешние переменные, определённые до блока {}, видны внутри блока {} если только не переопределены (тогда не видны, используется внутренняя переменная), внутренние переменные в {} видны только внутри своего {} после точки объявления (но не обязательно инициализации). Это как бы общий стандарт. В PARI так же, только блоки не выделены явно скобками {} (например переменная цикла снаружи цикла уже не видна).
Про область видимости временных переменных в строке вычислений я стандарта не помню, но по логике она должна заканчиваться концом формулы или даже концом обрамляющей функции (т.е. результат gpowgs() виден внутри вызова gaddgs(), но не должен быть виден снаружи вызова gaddgs()). И вот это в PARI для именованных переменных явно не так: gaddgs((x=gpowgs(k^4))+3) и x будет видна в программе дальше. Как оно для неименованных (временных) неясно, видимо их со стека не удаляют и из-за этого утечка памяти.

[wrest]

Dmitriy40
Я ещё смотрю сейчас на вот это недавнее приключение

wrest в сообщении #1721251 писал(а):

...реализации через компиляцию с помощью gp2c плохо чистят память, в итоге память разрастается до гигабайта - неприемлемо, можно было бы вручную поправить Си-код по сборке мусора но это не наш метод. Порог наступаео именно на таблице из 10^6 цепочек, на 10^5 всё норм, а при 10^6 время увеличиваетс я в 15 раз (а должноьменьше чем в 10).

Так вот там после проверки пора ли чистить стек, пытаются переложить таблицу из 20х10^6 элементов наверх стека Немудрено что всё начинает резко тормозить. Я просто убрал эти проверки и всё стало норм. Стек растёт но скорость не падает. Осталось понять как аккуратно почистить стек чтоб не рос, и пока непонятно. Как раз натолкнулся на непрозрачность фигурных скобок для переменных.

[Dmitriy40]

wrest в сообщении #1721646 писал(а):

Как раз натолкнулся на непрозрачность фигурных скобок для переменных.

Скобки непрозрачны лишь изнутри наружу, снаружи внутрь всё видно (что не замаскировано переопределением). Базовый принцип наследования.

[Yadryara]

Извините, у меня сложности с ответами — постоянно выбрасывает с форума. Но читать вроде пока получается.

Надежда есть, что всё-таки разберётесь с этими огромными затратами памяти. Всё никак не могу привыкнуть что вы называете таблицей список предпростых. Я привык что таблица, это обычно что-то двумерное, а список этот одномерный. И специально подчёркиваю, что степени 2-ки для этого списка предпростых в моих примерах 13-16, а вовсе не 20-24, то есть ни о каких гигабайтных затратах памяти речь идти ну никак не должна. Тем более что он small.

Но при этом устройство компа вы двое конечно знаете гораздо лучше меня. Так что пока не очень понимаю что именно мне надо делать. И ... пока снова не могу заставить себя смотреть С-код.

P. S. А, вот чуть получше с доступом стало. Стучу по деревянной комментаторской голове

[wrest]

Yadryara в сообщении #1721655 писал(а):

Так что пока не очень понимаю что именно мне надо делать.

Ну пока и непонятно
Суть в следующем. Когда вы что-то вычисляете например на бумажке, у вас образуется гора черновиков, из выкладок вам нужны только несколько результатов. Вот и тут так: эти черновики накапливаются и со временем требуется увеличение стека. Очистка состоит в переносе важных результатов в чистовик, и повторном использовании поверхности черновиков. Если черновики вовремя не очищать, имеем проблемы со стеком. Если очищать слишком часто - с производительностью.
В нормальном режиме должно очищаться автоматически, но когда этого не происходит, то начинается "утечка памяти", вот похоже это и имеем на длинных циклах в pari/gp после компиляции gp2c.