Re: Продавленный стек

[Андрей Любимец]

12.09.2014 2:32, Dmitrii Kashin пишет:

 
 Хотя конечно, мне рассказывали историю о человеке, который макросом
 заменял в исходниках точку. Правда, этого человека никто не любит. =)
Билл Гейтс, судя по повадкам? ;-) (сорри за офтоп)


--
To UNSUBSCRIBE, email to debian-russian-requ...@lists.debian.org
with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org
Archive: https://lists.debian.org/5412889e.4040...@nskes.ru

Re: Продавленный стек

[Dmitrii Kashin]

Aleksey Andreev li...@mail.ru writes:

 11.09.2014 23:32, Dmitrii Kashin пишет:

 Но всё равно получаю SegFault в следствие переполнения.
 Дело ведь не в неявности вызова команды а в рекурсии.
 Про неявный return ( ret ) я упомянул для того что бы показать где
 освобождается стек.
 Простите, Алексей, я хочу уточнить одну деталь. Я правильно сейчас
 понимаю, что Вы утверждаете, что рекурсивно описанная процедура всегда
 порождает рекурсивный процесс, выедающий стек?
 Выеданием стека я назвал не переполнение а активное его использование.
 Если оптимизатор построил хвостовую, то стек не задействуется. На
 сколько я помню разворачивается в цикл.
 При нормальных условиях дефолтного размера стека хватает даже достаточно
 глубоких рекурсиях.
 Он нужен для хранения адреса возврата и, в зависимости от способа вызова
 функции, параметров.
 В первоначальном коде я не обнаружил условия выхода из рекурсии.
 А значит у вас выедался стек при вызове функции + расход на выделение
 памяти под класс в каждом вызове,
 возможно выделение памяти производилось тоже на стеке.
 Думаю именно в этом и была причина сегфолта - стек закончился в
 следствии ничем не ограниченного выедания :)

Это очень грустно. =/


pgpfaa4BaSGCG.pgp
Description: PGP signature

Re: Продавленный стек

[Dmitrii Kashin]

Nikolay Kachanov nikolay.kacha...@gmail.com writes:

 Пожалуйста,

  09/11/2014 11:13:02 PM, Dmitrii Kashin:
 Николай, раз уж такое дело, можно работающий вариант попросить патчем?
 =)

Николай, а почему он работает?
Почему моя функция не была оптимизирована, а Ваша была?

Я не решительно не понимаю, какие условия должны быть соблюдены для
того, чтобы GCC использовал TCO. Поискал в интернете - не нашёл.

Я попробовал поизменять Вашу функцию и так, и эдак... Пробовал убрать
const, пробовал убрать static, пробовал возвращать не int, а
Grid1D... Но всё сразу же приводит к выключению TCO. Почему?


pgpJ7eYIKw7B9.pgp
Description: PGP signature

Продавленный стек

[Dmitrii Kashin]

Здравствуйте, сообщество. Я понимаю, что это, возможно, не самое
правильное место для вопроса по программированию, но мне достоверно
известно, что здесь сидят более-менее грамотные люди, которые мне
действительно могут помочь. И других таких мест мне, увы, знать не
довелось.

Я пишу программу на C++ (использую только подмножество синтаксиса языка
С99 плюс перегрузку операторов - никаких классов/объектов/потоков).

Суть программы сводится к следующему: она берёт сетку, модифицирует
все её значения (шагает), после чего проделывает с полученной сеткой
аналогичные операции. И так до тех пор, пока не достигнет какого-нибудь
результата.

Так вот, я обнаружил, что умудряюсь, похоже, продавить стек.
После примерно 20 тысяч шагов программа выдаёт SegFault и
завершается. Я посмотрел в gdb бэктрейс и увидел там over2 фреймов.

Собственно, хочется, чтобы кто-то посмотрел и по возможности помог
советом: вот отсюда[1] можно скачать архив с последней версией.

Собирать надо одним из следующих образов:
1) make test-shock1
2) make test-shock2a
3) make test-shock2b

В чём суть:

В бэктрейсе множественные вызовы функции make_step, которая вызывается
из маршевой функции на каждой итерации.

Вот так это примерно происходит:

void
march (Grid1D grid)
{
  ...
  Grid1D newgrid = make_step(grid, tau);
  march(newgrid);
};


А вот как определена сама функция:

Grid1D
make_step(Grid1D grid, double tau)
{
  Grid1D newgrid = grid_skel(grid);
  newgrid.iter += 1;
  newgrid.time += tau;

  double h = grid.h;
  double N = grid.N;

  ConservVars lf;
  ConservVars rf = count_left_flux(grid,0,tau);
  for (unsigned int i=0; iN; i++)
{
  lf = rf;
  if (i != N-1)
rf = count_left_flux(grid,i+1,tau);
  newgrid.cells[i].vars = grid.cells[i].vars - tau*(rf-lf)/h;
};
  free(grid.cells);
  return newgrid;
 };


Никак не пойму, что ж с ней не так-то: функция была вызвана, отработала,
вернула результат. Значит кадр в стеке ей вроде бы уже не нужен. Но он
остаётся. Почему?

[1] http://git.freehck.ru/cfrolov.git/


pgptHcPWwDcm5.pgp
Description: PGP signature

Re: Продавленный стек

[Dmitrii Kashin]

Dmitrii Kashin free...@freehck.ru writes:

 Собственно, хочется, чтобы кто-то посмотрел и по возможности помог
 советом: вот отсюда[1] можно скачать архив с последней версией.

 Собирать надо одним из следующих образов:
 1) make test-shock1
 2) make test-shock2a
 3) make test-shock2b

 ...

 [1] http://git.freehck.ru/cfrolov.git/

Ох, что-то этот интерфейс хоть и красив, но не слишком мне понятен. =)
Куда проще, чем через него, сделать вот так:
% git clone http://git.freehck.ru/repos/cfrolov.git


pgpeWNQyYBtv6.pgp
Description: PGP signature

Re: Продавленный стек

[Aleksey Andreev]

11.09.2014 13:25, Dmitrii Kashin пишет:



 Вот так это примерно происходит:
 
 void
 march (Grid1D grid)
 {
   ...
   Grid1D newgrid = make_step(grid, tau);
   march(newgrid);
 };
 


 Никак не пойму, что ж с ней не так-то: функция была вызвана, отработала,
 вернула результат. Значит кадр в стеке ей вроде бы уже не нужен. Но он
 остаётся. Почему?
Извините, код не смотрел, но из того что вижу поясню:
Вы из функции march вызываете еще одну march, таким образом не
освобождая стек вызовов.
Cтек освободится при вызове неявного return в конце ф-ции.
В данном случае стек тратится на сохранение точки возврата из функции,
но возврата не происходит.

С уважением, Алексей А.

Re: Продавленный стек

[Dmitrii Kashin]

Aleksey Andreev li...@mail.ru writes:

 11.09.2014 13:25, Dmitrii Kashin пишет:

 Вот так это примерно происходит:
 
 void
 march (Grid1D grid)
 {
   ...
   Grid1D newgrid = make_step(grid, tau);
   march(newgrid);
 };
 

 Извините, код не смотрел, но из того что вижу поясню:
 Вы из функции march вызываете еще одну march, таким образом не
 освобождая стек вызовов.
 Cтек освободится при вызове неявного return в конце ф-ции.
 В данном случае стек тратится на сохранение точки возврата из функции,
 но возврата не происходит.

Ага. Ну вот, я наконец понял, что неправильно детектировал проблему.
Она именно в рекурсивном вызове маршевой функции, а make_step тут не при
чём.

Поскольку Вы упомянули про неявный return, я попробовал указать return
явно, слегка переписав функцию, чтобы она возвращала результат:

Grid1D
march (Grid1D grid)
{
  ...
  if (!finFlag)
{
  printf(Making iteration %06d; Passed time: %f\n, grid.iter+1, 
grid.time);
  Grid1D newgrid = make_step(grid, tau);
  grid = newgrid;
}
  else
{
  printf(Final conditions are reached! Finishing.\n);
  return grid;
};
  return grid;
}


Но всё равно получаю SegFault в следствие переполнения.

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

PS: Я ещё не сразу сообразил, кстати, что gcc требует указание флага -O2
для хвостовой рекурсии. Я, лиспер, хорошо живу: у нас-то она сама собой
разумеется. А в Си она, оказывается, *оптимизация*. Ну это я так,
побухтеть.

PPS: А вот не подскажете ли мне ещё эху или рассылку, где с подобными
вопросами я не был бы белой вороной? =)


pgpXKNvqbLspz.pgp
Description: PGP signature

Re: Продавленный стек

[Aleksey Andreev]

11.09.2014 14:50, Dmitrii Kashin пишет:
 Ага. Ну вот, я наконец понял, что неправильно детектировал проблему.
 Она именно в рекурсивном вызове маршевой функции, а make_step тут не при
 чём.

 Поскольку Вы упомянули про неявный return, я попробовал указать return
 явно, слегка переписав функцию, чтобы она возвращала результат:
 
 Grid1D
 march (Grid1D grid)
 {
   ...
   if (!finFlag)
 {
   printf(Making iteration %06d; Passed time: %f\n, grid.iter+1,
grid.time);
   Grid1D newgrid = make_step(grid, tau);
   grid = newgrid;
 }
   else
 {
   printf(Final conditions are reached! Finishing.\n);
   return grid;
 };
   return grid;
 }
 

 Но всё равно получаю SegFault в следствие переполнения.
Дело ведь не в неявности вызова команды а в рекурсии.
Про неявный return ( ret ) я упомянул для того что бы показать где
освобождается стек.


 Тем не менее, я переписал этот кусок при помощи цикла, и программа вроде
 как валиться перестала. Такой результат меня полностью устраивает,
 спасибо.
Если Grid1D не указатель, то многовато у вас копирования класса в
циклах. просядет производительность.
Но для одноразового кода наверно пойдет :)
И я не понял, что там за танцы с newgrid, результат множественных правок? :)

 PPS: А вот не подскажете ли мне ещё эху или рассылку, где с подобными
 вопросами я не был бы белой вороной? =)
Тут я вам ничего посоветовать не могу, не пользуюсь.

Успехов в освоении.

С уважением, Алексей А.

Re: Продавленный стек

[Nikolay Kachanov]

Вот так должно работать:

int march (const Grid1D  grid)
{
...
 
  static Grid1D newgrid;
 
  // шаг
  if (!finFlag)
{
  printf(Making iteration %06d; Passed time: %f\n, grid.iter+1,
grid.time);
  newgrid = make_step(grid, tau);
  return march(newgrid);
}
else
  return 0;
  }


 11.09.2014 14:50:27, Dmitrii Kashin:
 Но всё равно получаю SegFault в следствие переполнения.

 


-- 
To UNSUBSCRIBE, email to debian-russian-requ...@lists.debian.org
with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org
Archive: https://lists.debian.org/54118adb.1000...@gmail.com

Re: Продавленный стек

[Aleksey Andreev]

11.09.2014 15:43, Nikolay Kachanov пишет:
 Вот так должно работать:

 int march (const Grid1D  grid)
 {
 ...
  
   static Grid1D newgrid;
  
   // шаг
   if (!finFlag)
 {
   printf(Making iteration %06d; Passed time: %f\n, grid.iter+1,
 grid.time);
   newgrid = make_step(grid, tau);
   return march(newgrid);
 }
 else
   return 0;
   }

return march(newgrid) все равно будет выедать стек, но в отличии от
первоначального варианта тут предусмотрен выход из рекурсии.

p.s. А зачем else перед return 0; ? Мелочь, конечно. Давно не
проверял, сейчас компиляторы ставят ненужные jmp в таких случаях?

С уважением, Алексей А.

Re: Продавленный стек

[Nikolay Kachanov]

 11.09.2014 15:57:00, Aleksey Andreev:

 return march(newgrid) все равно будет выедать стек, но в отличии от
 первоначального варианта тут предусмотрен выход из рекурсии.
Судя по asm-коду и отсутствию сегфолта (ждал до 8, потом остановил),
компилятор хвостовую рекурсию
делает.
 p.s. А зачем else перед return 0; ? Мелочь, конечно. Давно не
 проверял, сейчас компиляторы ставят ненужные jmp в таких случаях?
Это я так, для порядку :-).


 


-- 
To UNSUBSCRIBE, email to debian-russian-requ...@lists.debian.org
with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org
Archive: https://lists.debian.org/54119f23.70...@gmail.com

Re: Продавленный стек

[Dmitrii Kashin]

Nikolay Kachanov nikolay.kacha...@gmail.com writes:

  11.09.2014 15:57:00, Aleksey Andreev:

 return march(newgrid) все равно будет выедать стек, но в отличии от
 первоначального варианта тут предусмотрен выход из рекурсии.

 Судя по asm-коду и отсутствию сегфолта (ждал до 8, потом
 остановил), компилятор хвостовую рекурсию делает.

Николай, раз уж такое дело, можно работающий вариант попросить патчем?
=)


pgpyCclGF51ON.pgp
Description: PGP signature

Re: Продавленный стек

[Dmitrii Kashin]

Aleksey Andreev li...@mail.ru writes:

 11.09.2014 14:50, Dmitrii Kashin пишет:
 Ага. Ну вот, я наконец понял, что неправильно детектировал проблему.
 Она именно в рекурсивном вызове маршевой функции, а make_step тут не при
 чём.

 Поскольку Вы упомянули про неявный return, я попробовал указать return
 явно, слегка переписав функцию, чтобы она возвращала результат:
 ...
 Но всё равно получаю SegFault в следствие переполнения.
 Дело ведь не в неявности вызова команды а в рекурсии.
 Про неявный return ( ret ) я упомянул для того что бы показать где
 освобождается стек.

Простите, Алексей, я хочу уточнить одну деталь. Я правильно сейчас
понимаю, что Вы утверждаете, что рекурсивно описанная процедура всегда
порождает рекурсивный процесс, выедающий стек?

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

 Если Grid1D не указатель, то многовато у вас копирования класса в
 циклах. просядет производительность.

Это цена удобства. Самая первая версия программы содержала указатели во
всех функциях - в результате я замучился: во-первых бесконечные
стрелочки сделали код совершенно нечитаемым, особенно в научных формулах
(ну я где-то полгода назад жаловался в этой рассылке об этом), а
во-вторых у меня стали получаться конструкции, которые меня очень уж
угнетали, вот по типу этих вот:
--
return (grid-cells)[cell_number];
(get_cell(newgrid,i))-convergence = coef;
--
Расстановка стрелочек, скобочек и амперсанов стала основной работой,
которой я занимался вместо того, чтобы модифицировать логику программы.

Так что при работе с Си, копирование имеет свои плюсы.

Хотя конечно, мне рассказывали историю о человеке, который макросом
заменял в исходниках точку. Правда, этого человека никто не любит. =)

 Но для одноразового кода наверно пойдет :)

Кто его знает, как у него судьба сложится?
Вполне может быть станется, что тяп-ляп и в продакшн. =/

 И я не понял, что там за танцы с newgrid, результат множественных правок? :)

Да просто всё: есть сетка grid на предыдущем шаге по времени, а есть
newgrid - на следующем. Высчитываем newgrid по grid, после чего
присваиваем grid = newgrid и повторяем итерацию.


pgpdCaaiI2b4V.pgp
Description: PGP signature

Re: Продавленный стек

[Aleksey Andreev]

11.09.2014 23:32, Dmitrii Kashin пишет:

 Но всё равно получаю SegFault в следствие переполнения.
 Дело ведь не в неявности вызова команды а в рекурсии.
 Про неявный return ( ret ) я упомянул для того что бы показать где
 освобождается стек.
 Простите, Алексей, я хочу уточнить одну деталь. Я правильно сейчас
 понимаю, что Вы утверждаете, что рекурсивно описанная процедура всегда
 порождает рекурсивный процесс, выедающий стек?
Выеданием стека я назвал не переполнение а активное его использование.
Если оптимизатор построил хвостовую, то стек не задействуется. На
сколько я помню разворачивается в цикл.
При нормальных условиях дефолтного размера стека хватает даже достаточно
глубоких рекурсиях.
Он нужен для хранения адреса возврата и, в зависимости от способа вызова
функции, параметров.
В первоначальном коде я не обнаружил условия выхода из рекурсии.
А значит у вас выедался стек при вызове функции + расход на выделение
памяти под класс в каждом вызове,
возможно выделение памяти производилось тоже на стеке.
Думаю именно в этом и была причина сегфолта - стек закончился в
следствии ничем не ограниченного выедания :)
 Тем не менее, я переписал этот кусок при помощи цикла, и программа
 вроде как валиться перестала. Такой результат меня полностью
 устраивает, спасибо.
 Если Grid1D не указатель, то многовато у вас копирования класса в
 циклах. просядет производительность.
 Это цена удобства. Самая первая версия программы содержала указатели во
 всех функциях - в результате я замучился: во-первых бесконечные
 стрелочки сделали код совершенно нечитаемым, особенно в научных формулах
 (ну я где-то полгода назад жаловался в этой рассылке об этом), а
 во-вторых у меня стали получаться конструкции, которые меня очень уж
 угнетали, вот по типу этих вот:
 --
 return (grid-cells)[cell_number];
 (get_cell(newgrid,i))-convergence = coef;
 --
 Расстановка стрелочек, скобочек и амперсанов стала основной работой,
 которой я занимался вместо того, чтобы модифицировать логику программы.
Сильно зависит от проработанности структуры программы.

 Так что при работе с Си, копирование имеет свои плюсы.
Как раз на Си проще передать указатель чем копировать. А вот Си++ делает
это самостоятельно.


С уважением, Алексей А.

Re: Продавленный стек

[Nikolay Kachanov]

Пожалуйста,

 09/11/2014 11:13:02 PM, Dmitrii Kashin:
 Николай, раз уж такое дело, можно работающий вариант попросить патчем?
 =)


 
diff -Naur master/Makefile master-tr/Makefile
--- master/Makefile	2014-09-11 13:42:39.0 +0400
+++ master-tr/Makefile	2014-09-12 08:36:47.985330799 +0400
@@ -1,5 +1,5 @@
 CXX=g++
-CFLAGS=-Wall -g -ggdb
+CFLAGS=-Wall -g -ggdb -O2
 LDFLAGS=-lm
 SOURCES=main.cxx variables.cxx cell.cxx grid.cxx solver.cxx timestep_constant.cxx march.cxx
 STASH=grid-init.o
diff -Naur master/march.cxx master-tr/march.cxx
--- master/march.cxx	2014-09-11 13:42:39.0 +0400
+++ master-tr/march.cxx	2014-09-11 15:16:50.204903767 +0400
@@ -4,8 +4,8 @@
 #include solver.h
 #include march-config.h
 
-void
-march (Grid1D grid)
+int
+march (const Grid1D  grid)
 {
   int finFlag = 0;
   int printFlag = 0;
@@ -59,12 +59,19 @@
 printGridToFile(grid);
 
 
+  static Grid1D newgrid;
+  
   // шаг
   if (!finFlag)
 {
   printf(Making iteration %06d; Passed time: %f\n, grid.iter+1, grid.time);
-  Grid1D newgrid = make_step(grid, tau);
-  march(newgrid);
-};
+  newgrid = make_step(grid, tau);
+  return march(newgrid);
+}
+else
+{
+  return 0;
+}
+  
 }
 
diff -Naur master/march.h master-tr/march.h
--- master/march.h	2014-09-11 13:42:39.0 +0400
+++ master-tr/march.h	2014-09-11 15:00:18.642406733 +0400
@@ -3,6 +3,6 @@
 #ifndef MARCH
 #define MARCH
 
-void march (Grid1D grid);
+int march (const Grid1D  grid);
 
 #endif //MARCH