GCC, проблема с прогой

[shamaz]

Привет. Пишу библиотеку для работы с воксельными октодеревьями (для рендеринга). У меня есть прототип на Common Lisp (я решил, что туда сначала буду заносить новомодные фичи) https://github.com/shamazmazum/voxel-octrees и на C (который жрет куда меньше памяти и немного быстрее). Для работы с векторами я решил использовать SSE (особенно инструкции для работы с упакованными данными). Вышло так, что программа работает, скомпилированная gcc4.7 (и gcc4.8 тоже) без флагов оптимизации, а хотя бы с -O уже "виснет", очень быстро выделяя память.

Вот прога на pastebin:

http://pastebin.com/p65ssmWM tree.h
http://pastebin.com/tBCcMxbj tree.c
http://pastebin.com/QHWGPA2v main.c

Собираю, естественно gcc -lm -o test main.c tree.c

Проблема возникает при создании дерева из 1000000 вокселей (big_tree)

Сеанс в gdb:

> gdb76 test
GNU gdb (GDB) 7.6 [GDB v7.6 for FreeBSD]
Copyright (C) 2013 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law. Type "show copying"
and "show warranty" for details.
This GDB was configured as "x86_64-portbld-freebsd9.1".
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>...
Reading symbols from /home/vasily/testvox/voxel-octrees-c2/test...done.
(gdb) break tree.c:101
Breakpoint 1 at 0x400b92: file tree.c, line 101.
(gdb) list tree.c:101
96 int i;
97 dot *subset = malloc (sizeof (dot) * n);
98 for (i=0; i<NS; i++)
99 {
100 int sub_n = filter_set (set, subset, n, i, inner->center);
101 inner->children[i] = make_tree (subset, sub_n);
102 }
103 free (subset);
104 }
105
(gdb) rub
Undefined command: "rub". Try "help".
(gdb) run
Starting program: /home/vasily/testvox/voxel-octrees-c2/test

Breakpoint 1, make_tree (set=set@entry=0x801000000, n=n@entry=1000000) at tree.c:101
101 inner->children[i] = make_tree (subset, sub_n);
(gdb) bt
#0 make_tree (set=set@entry=0x801000000, n=n@entry=1000000) at tree.c:101
#1 0x00000000004006b7 in main () at main.c:26
(gdb) cont
Continuing.

Breakpoint 1, make_tree (set=set@entry=0x802400000, n=124815) at tree.c:101
101 inner->children[i] = make_tree (subset, sub_n);
(gdb) cont
Continuing.

Breakpoint 1, make_tree (set=set@entry=0x80200a000, n=15549) at tree.c:101
101 inner->children[i] = make_tree (subset, sub_n);
(gdb) cont
Continuing.

Breakpoint 1, make_tree (set=set@entry=0x8021f2000, n=1923) at tree.c:101
101 inner->children[i] = make_tree (subset, sub_n);
(gdb) cont
Continuing.

Breakpoint 1, make_tree (set=set@entry=0x802237000, n=252) at tree.c:101
101 inner->children[i] = make_tree (subset, sub_n);
(gdb) bt
#0 make_tree (set=set@entry=0x802237000, n=252) at tree.c:101
#1 0x0000000000400b9c in make_tree (set=set@entry=0x8021f2000, n=1923) at tree.c:101
#2 0x0000000000400b9c in make_tree (set=set@entry=0x80200a000, n=15549) at tree.c:101
#3 0x0000000000400b9c in make_tree (set=set@entry=0x802400000, n=124815) at tree.c:101
#4 0x0000000000400b9c in make_tree (set=set@entry=0x801000000, n=n@entry=1000000) at tree.c:101
#5 0x00000000004006b7 in main () at main.c:26
(gdb) cont
Continuing.

Breakpoint 1, make_tree (set=set@entry=0x802290000, n=27) at tree.c:101
101 inner->children[i] = make_tree (subset, sub_n);
(gdb) bt
#0 make_tree (set=set@entry=0x802290000, n=27) at tree.c:101
#1 0x0000000000400b9c in make_tree (set=set@entry=0x802237000, n=252) at tree.c:101
#2 0x0000000000400b9c in make_tree (set=set@entry=0x8021f2000, n=1923) at tree.c:101
#3 0x0000000000400b9c in make_tree (set=set@entry=0x80200a000, n=15549) at tree.c:101
#4 0x0000000000400b9c in make_tree (set=set@entry=0x802400000, n=124815) at tree.c:101
#5 0x0000000000400b9c in make_tree (set=set@entry=0x801000000, n=n@entry=1000000) at tree.c:101
#6 0x00000000004006b7 in main () at main.c:26

Как видите, на числе n=27 он не вызывает make_tree дальше, хотя условие выхода - n<=MAX_DOTS=7. Прошу помочь отладить и извинить за весьма объёмный исходник, так как локализировать ошибку не удается (это же C, увы ) В работающей версии, кстати, почти всё тоже самое, только нет SIMD и немного другая (более большая) структура для узла.

Прога, увы не портабельна, так как использует операции + и / для векторов (API, предоставляемый xmmintrin.h есть уже много где)

[shamaz]

Язык C, конечно

[Кащей]

работает, скомпилированная gcc4.7 (и gcc4.8 тоже) без флагов оптимизации

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

[shamaz]

Сообщение от Кащей

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

Явно костыльное и ненадежное решение

[Кащей]

Сообщение от shamaz

Явно костыльное и ненадежное решение

Допустим. А как тебе вариант переписать всё заново с периодической проверкой работоспособности в условиях приближённых к боевым?

[Stilet]

очень быстро выделяя память.

Лисп оптимизирует по другому. Там совсем другой подход.
Я проект не смотрел, но обычно когда на такое попадаюсь начинаю все с чистого листа и светлой головы.

[shamaz]

Отбой, gcc соптимизировал xorps, а инициализировать надо _mm_set_ps1(0), который компилируется в этот самый xorps. В общем виноват тем, что решил, что умнее компилятора, ССЗБ. Кстати clang3.1 генерирует более эффективный код. Яфшоке

В лиспе для лиспа всё нормально, ИМХО. Использую SBCL 1.1.8. Образ с деревом на ~504000 вокселей занимает ~400 Мб, память растет не слишком сильно. Рендерит он это на разрешении 800x600 ~2.5 секунды, а прога на C - 0.2 секунды, т.е разница в 12 раз.

Вот один из рендерингов:
http://s23.postimg.org/id4lct43t/foot.png

Данные отсюда:
http://www.volren.org/

[Кащей]

Воксели ето круто да. И выглядит прикольно.