URL: https://www.opennet.me/cgi-bin/openforum/vsluhboard.cgi
Форум: vsluhforumID9
Нить номер: 4659
[ Назад ]

Исходное сообщение
"Глубокая рекурсия в 2х ОС"

Отправлено Halt , 20-Сен-05 10:58 
Привет всем !

Собственно суть ...

У меня есть многопоточная (pthread) программа (далее просто proga) , которая в отдельных потоках запускает
некоторые функции из библиотек . (1 поток может использ только 1 такую библ.) и в каждой библиотеке есть
некотрая ф-ция сериализации древовидного списка в строку . (эта ф-ция рекурсивная) .

Ну так вот ... в linux (mdk 10) работает , а в freebsd 5.4 сама библиотека пашет , а в proge нет .
Причём проблема как раз в ф-ции сериализации . Например если дерево это
массив из 1000 массивов с 1 элементом , то proga на 224 элементе (на массиве из 1 эл.) НЕТ НЕ ВАЛИТСЯ , а зависает как будто (в KDE Syst Guard колонка user% начинает быстро расти до уровня 50-80) ... короче это происходит в момент очередного рекурсивным вызова ф-ции сериализации .

?????

Можно считать , что в proge и ф-ции сериализ. ошибок нет (по крайней мере которые могут всё свалить) , потому что
эти вещи многократно проверены правильной работой в линухе и на небольших массивах во фре .


P.S. На rsdn`е я уже задавал этот вопрос , но
там мне не помогли мягко говоря .

Хотелось бы узнать хотя бы направление в котором стоит разбираться , потому что у самого что то нет никаких мыслей (( .


Содержание

Сообщения в этом обсуждении
"Глубокая рекурсия в 2х ОС"
Отправлено mig , 20-Сен-05 14:15 
А если взглянуть на сами потоки - не завершаются ли они у тебя в некоторых участках кода ;) Или, возможно возникает состояние гонки? А еще лучше если кусок кода покажешь.

"Глубокая рекурсия в 2х ОС"
Отправлено halt , 21-Сен-05 10:14 

Потоки точно не завершаются раньше .
Слёт происходит всегда после опрделённого числа рекурсивных вызовов .

Самое странное , что если бы код был не верен , то он не должен был правильно работать в линухе , но он работает .

Кстати под отладчиком процесс получает сигнал SIGSEGV , и почему то не завершается , а виснет .

Вас интересует код ф-ция сериализации ?


"Глубокая рекурсия в 2х ОС"
Отправлено chip , 21-Сен-05 11:35 
>Кстати под отладчиком процесс получает сигнал SIGSEGV , и почему то не
>завершается , а виснет .

От этого и нужно плясать. Используется ли какая-нибудь оптимизация ? Возможно, в коде повешен обработчик на SIGSEGV?


"Глубокая рекурсия в 2х ОС"
Отправлено enot , 21-Сен-05 13:49 
>>Кстати под отладчиком процесс получает сигнал SIGSEGV , и почему то не
>>завершается , а виснет .
>
>От этого и нужно плясать. Используется ли какая-нибудь оптимизация ? Возможно, в
>коде повешен обработчик на SIGSEGV?


Угу, и потоки во FreeBSD и Linux по разному реализованы...
Стек потока часом рекурсией не сносится?


"Глубокая рекурсия в 2х ОС"
Отправлено halt , 21-Сен-05 14:52 

>>От этого и нужно плясать. Используется ли какая-нибудь оптимизация ?

Оптимизация используется O2 , но и без неё тоже самое .

>>коде повешен обработчик на SIGSEGV?

Обработчик на SIGSEGV не установлен .

>Угу, и потоки во FreeBSD и Linux по разному реализованы...
>Стек потока часом рекурсией не сносится?

Вот и я думаю что сносится . Очень на это похоже . А как это лечится ?!


"Глубокая рекурсия в 2х ОС"
Отправлено chip , 21-Сен-05 17:36 
>Вот и я думаю что сносится . Очень на это похоже .
>А как это лечится ?!

Кропотливым поиском потенциальных ошибок в своем коде.


"Глубокая рекурсия в 2х ОС"
Отправлено chip , 21-Сен-05 17:59 
>Вот и я думаю что сносится . Очень на это похоже .
>А как это лечится ?!

К слову сказать несколько схожая тематика: http://www.opennet.me/openforum/vsluhforumID9/4039.html#0


"Глубокая рекурсия в 2х ОС"
Отправлено chip , 21-Сен-05 18:03 
>Оптимизация используется O2 , но и без неё тоже самое .

Укажите полностью параметры передаваемые gcc ? Используется -pthread или -lpthread ? Почитайте про разницу libpthread, libc_r, libthr. Все они доступны на FreeBSD > 5.x. Насколько я помню по рассылкам с libthr были определенные проблемы, в частности при использовании ULE шедулера.


"Глубокая рекурсия в 2х ОС"
Отправлено halt , 21-Сен-05 19:23 

>Укажите полностью параметры передаваемые gcc ? Используется -pthread или -lpthread ? Почитайте про разницу libpthread, libc_r, libthr. Все они доступны на FreeBSD > 5.x. Насколько я помню по рассылкам с libthr были определенные проблемы, в частности при использовании ULE шедулера.

Компилю g++ и линкую -lpthread . На сколько я понимаю скажем -lstdc++ уже потокозащищённая ... или нет ? (просто аналога libc_r я не встречал для libstdc++) .

  


"Глубокая рекурсия в 2х ОС"
Отправлено DeadMustdie , 22-Сен-05 09:49 
Рекурсивные алгоритмы хороши в академических целях, при
объяснении студентам неких базовых понятий. А в практическом
программировании применение рекурсии с нефиксированной глубиной
вызова практически всегда есть признак ламера, ибо стек не
резиновый (куда менее резиновый, чем та же куча - особенно в
многопоточной программе, где куча общая, а стек у каждого потока
свой собственный).

Абсолютно любой рекурсивный алгоритм можно без большой головной
боли реализовать без использования основного стека (хотя бы при
помощи управляемого вручную стека самопального, при
необходимости увеличивающегося до предельного размера памяти,
доступной программе). Что я Вам и советую сделать.


"Глубокая рекурсия в 2х ОС"
Отправлено halt , 22-Сен-05 13:20 
Может быть и стоит переписать .

Без особых проблем говорите . Хорошо . А где можно пример посмотреть какой нибудь реализации рекурсивной ф-ции без рекурсии ?

Самопальный стек должен быть аналогом обычного , но только находиться в куче и управл. мной ?



"Глубокая рекурсия в 2х ОС"
Отправлено DeadMustdie , 22-Сен-05 20:46 
Нечто вроде:

struct MyStackItem {
  MyStateData data;
  MyStackItem* next;
};

MyStackItem* stackPush(MyStackItem** root)
{
  struct MyStackItem* tmp = (struct MyStackItem*)malloc(sizeof(struct MyStackItem));
  tmp->next = *root;
  *root = tmp;
  return tmp;
}

MyStackItem* stackPop(MyStackItem** root)
{
  struct MyStackItem* tmp = *root;
  if ( *root )
    *root = (*root)->next;
  return tmp;
}

...

struct MyStackItem* stackRoot = NULL;
struct MyStackItem* currStack = stackPush(&stackRoot);
...
while ((currStack = stackPop(&stackRoot))!=NULL) {
  /* заталкиваем в стек новые "задания" */
  /* обрабатываем текущее "задание" в *currStack */
}

Вот Вам и рекурсия без использования основного стека.
На C++ всё получится существенно короче и работать скорее
всего будет чуток побыстрее (при сравнимых затратах труда).


"Глубокая рекурсия в 2х ОС"
Отправлено halt , 23-Сен-05 00:22 
Спасибо за пример .

Т.е. я так понимаю : вместо рекурсивных вызовов в ф-ции
я записываю необходимые данные в стек и завершаюсь , а в цикле
извлекаю запись , запускаю ф-цию и т.д.

f(p,...)
{
...
st2->p = p2 ;
push(st2) ;  //f(p2,...) ;
return ;
...
}

st->p = p ;
push(st) ;

while((tmp=pop()))
{
f(tmp->p) ;
}

Получается совсем просто . В стеке вообще только 1 запись находится .
Кстати в алгоритме моей ф-ции так и происходит , что после
очередного рек вызова (т.е. после его заверш.) она просто завершается .
Мда ... надо было так сразу сделать .

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

А вы считаете , что нужно вообще отказаться от рек. ф-ций ?


"Глубокая рекурсия в 2х ОС"
Отправлено halt , 24-Сен-05 22:56 
Избавился от рекурсии , сейчас всё работает .

А вот ключ -pthread вообще не работал без -lpthread
и в манах про него ничё не написано .

Всем спасибо .