есть, например, регулярное двумерное поле клеток. часть (до половины) областей клеток на поле не несут информации. как лучше организовать данные:
1)сделать одномерный массив с данными DATA[:] и двумерный массив индексов IND[:,:], и обращаться к данным по DATA[ IND[i,j] ]
2)или же, лучше сделать эту DATA[i,j] в виде массива указателей и просто не аллокатить место под пустые клетки?
интересует с точки зрения производительности. считается, что оба массива помещаются в кэш процессора.
Если оба массива такие мелкие, что помещаются в кэш процессора первого уровня, не всё ли равно как их делать?
Вот если бы ты работал с массивами на миллионы терабайт, тогда был бы смысл что-то оптимизировать.
Лучше не занимайся вот этой ерундой:
Цитата:
thambs писал: и просто не аллокатить место под пустые клетки?
Дядя Миша
аллокатить один раз.
>смысл что-то оптимизировать.
из него очень часть надо будет читать и писать в него. а вот в кеш какого уровня он помещается я не знаю. у меня на рабочем помпе cpuinfo просто выдаёт cache size 2MB. Ну я так понимаю, первый вариант проще будет, а скорость та же?
Ты про кэш лучшы не думай. Кэш - он сам себе кэш. Там целый механизм следит за промахами и попаданиями и строит линию поведения.
Если бы он был тупой, как на каком-нибудь 486-м процессоре, тогда да, несколькими нехитрыми приёмами можно было существенно увеличить производительность.
Но массивы небольших размеров я бы выделял целиком.
Конечно если там массив под сто мегабайт я уже задумаюсь.
А два-три-пять метров, да тьху. Тоже мне размер.
Дядя Миша писал: на аллокациях много времени потеряешь.
Интересный факт - делал ради интереса свой аллокатор на предвыделенном большом куске памяти - до 60 раз быстрей чем malloc/free
__________________
Трагическая новость: Пятеро инженеров Casio умерли от смеха, узнав что Samsung анонсировали часы с заявленным временем работы в 25 часов
CrazyRussian писал: делал ради интереса свой аллокатор на предвыделенном большом куске памяти - до 60 раз быстрей чем malloc/free
Свой аллокатор был в релизной дллке, а тестовая прога собиралась в дебаге?
Иначе 60-кратный прирост объяснить нельзя, имхо.
Цитата:
thambs писал: есть, например, регулярное двумерное поле клеток. часть (до половины) областей клеток на поле не несут информации. как лучше организовать данные
XaeroX
у меня не матрицы же. в сетке клеток храню значения потенциала, элмагн-полей и плотности зарядов. а пустые клетки получаются из за того что решаю всё не в прямоугольнике, а в некотором многограннике хитрой формы, который моделирует срез разрядной камеры ЭРД.
соответственно, для того что бы рассчитать поля, мне нужно сначала много раз пробегать по значениям потенциала и плотности -- итерационным методом верхней релаксации. для того что бы рассчитать смещение частиц под воздействием этого поля -- нужно побегать по массиву частиц (он заранее декомпозирован на блоки маленького размера и пространственно упорядочен), и для каждой частицы проинтерполировть значение поля из массива. поэтому хочу что бы массив с полями был как можно меньше и помещался в кэш, так как к нему обращаться придётся больше всего.
XaeroX писал: Свой аллокатор был в релизной дллке, а тестовая прога собиралась в дебаге?
Иначе 60-кратный прирост объяснить нельзя, имхо.
Да не, все в одном модуле, про прирост - то по сути сильно замудренный вариант кода типа такого:
C++ Source Code:
1
typedefstruct 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 часов
Когда взглянул на аллокатор Сразу Рашена, в мыслях пронеслось то же слово, что и у него сейчас в статусе под моим ником.
Насчёт оптимизации и неиспользуемых клеток - разве время считывания/записи будет как-то зависеть от размеров массива? Различия же только в способе вычисления индекса, вот и нужно найти тот, что побыстрее. Это если занимаемый объём памяти не так важен, иначе конечно компромисс надо искать.
Ну этот трюк который о котором выше писал СразуРашен используется на многих приставках, ибо там нельзя динамично выделять память. Вообще я когда то обсуждал эту тему с ДМом, он меня таки убедил что предвыделять таки не стоит. (=
CrazyRussian это называется не аллокатор, а мемори пул. А слабо написать аллокатор кусков памяти произвольной длины в 60 раз быстрее обычного и фрагментирующий память в минимальной степени?
03-08-2013 13:23
