HLFX.Ru Forum (https://hlfx.ru/forum/index.php)
- Технические вопросы (https://hlfx.ru/forum/forumdisplay.php?forumid=20)
-- организация данных (https://hlfx.ru/forum/showthread.php?threadid=4041)

организация данных

есть, например, регулярное двумерное поле клеток. часть (до половины) областей клеток на поле не несут информации. как лучше организовать данные:
1)сделать одномерный массив с данными DATA[:] и двумерный массив индексов IND[:,:], и обращаться к данным по DATA[ IND[i,j] ]
2)или же, лучше сделать эту DATA[i,j] в виде массива указателей и просто не аллокатить место под пустые клетки?
интересует с точки зрения производительности. считается, что оба массива помещаются в кэш процессора.

__________________
http://www.moddb.com/mods/monorail-quest

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

__________________
My Projects: download page

F.A.Q по XashNT
Блог разработчика в телеграме

Дядя Миша
аллокатить один раз.
>смысл что-то оптимизировать.
из него очень часть надо будет читать и писать в него. а вот в кеш какого уровня он помещается я не знаю. у меня на рабочем помпе cpuinfo просто выдаёт cache size 2MB. Ну я так понимаю, первый вариант проще будет, а скорость та же?

__________________
http://www.moddb.com/mods/monorail-quest

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

__________________
My Projects: download page

F.A.Q по XashNT
Блог разработчика в телеграме

__________________
Трагическая новость: Пятеро инженеров Casio умерли от смеха, узнав что Samsung анонсировали часы с заявленным временем работы в 25 часов

__________________

XaeroX
у меня не матрицы же. в сетке клеток храню значения потенциала, элмагн-полей и плотности зарядов. а пустые клетки получаются из за того что решаю всё не в прямоугольнике, а в некотором многограннике хитрой формы, который моделирует срез разрядной камеры ЭРД.
соответственно, для того что бы рассчитать поля, мне нужно сначала много раз пробегать по значениям потенциала и плотности -- итерационным методом верхней релаксации. для того что бы рассчитать смещение частиц под воздействием этого поля -- нужно побегать по массиву частиц (он заранее декомпозирован на блоки маленького размера и пространственно упорядочен), и для каждой частицы проинтерполировть значение поля из массива. поэтому хочу что бы массив с полями был как можно меньше и помещался в кэш, так как к нему обращаться придётся больше всего.

__________________
http://www.moddb.com/mods/monorail-quest

1

typedef struct object_s

2

{

3

  int field1;

4

  int field2;

5

}object_t;

6

7

object_t Pool[MAX_OBJECTS];

8

int UsedObjects = 0;

9

10

object_t * Alloc()

11

{

12

  return &Pool[UsedObjects++];

13

}

__________________
Трагическая новость: Пятеро инженеров Casio умерли от смеха, узнав что Samsung анонсировали часы с заявленным временем работы в 25 часов

Дак ты уже выделил память. Что ты сравниваешь-то?
Выделять выделенную память в 60 раз быстрее чем выделять невыделенную память?

__________________
My Projects: download page

F.A.Q по XashNT
Блог разработчика в телеграме

CrazyRussian
Какой же это аллокатор? Где функция Free(), например?

__________________

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

Насчёт оптимизации и неиспользуемых клеток - разве время считывания/записи будет как-то зависеть от размеров массива? Различия же только в способе вычисления индекса, вот и нужно найти тот, что побыстрее. Это если занимаемый объём памяти не так важен, иначе конечно компромисс надо искать.

Ну этот трюк который о котором выше писал СразуРашен используется на многих приставках, ибо там нельзя динамично выделять память. Вообще я когда то обсуждал эту тему с ДМом, он меня таки убедил что предвыделять таки не стоит. (=

1

#define POOLSIZE	(256 * 1024)

2

3

static char		memoryPool[POOLSIZE];

4

static int		allocPoint;

5

6

void *G_Alloc( int size ) {

7

  char	*p;

8

9

  if ( g_debugAlloc.integer ) {

10

    G_Printf( "G_Alloc of %i bytes (%i left)\n", size, POOLSIZE - allocPoint - ( ( size + 31 ) & ~31 ) );

11

  }

12

13

  if ( allocPoint + size > POOLSIZE ) {

14

    G_Error( "G_Alloc: failed on allocation of %i bytes\n", size ); // bk010103 - was %u, but is signed

15

    return NULL;

16

  }

17

18

  p = &memoryPool[allocPoint];

19

20

  allocPoint += ( size + 31 ) & ~31;

21

22

  return p;

23

}

__________________
My Projects: download page

F.A.Q по XashNT
Блог разработчика в телеграме

CrazyRussian это называется не аллокатор, а мемори пул. А слабо написать аллокатор кусков памяти произвольной длины в 60 раз быстрее обычного и фрагментирующий память в минимальной степени?

__________________