Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
JerryI
0 / 0 / 0
Регистрация: 26.04.2013
Сообщений: 31
#1

Быстрое копирование массивов с условиями - C++

26.04.2013, 13:59. Просмотров 1006. Ответов 15
Метки нет (Все метки)

Доброго времени суток.
У меня вопрос по поводу копирования массивов.
Есть два массива:
C++
1
2
uint8_t mainbuf[320*240];
uint8_t cb[16*16];
Мне нужно скопировать массив cb в mainbuf на определенные координаты, с условием, что значение ячейки cb != 0xE3. Пока реализую так:

C++
1
2
3
4
5
6
7
void set(int x, int y) {
   for (unsigned char i=0; i<16; ++i) {
       for (unsigned char j=0; j<16; ++j) {
           if (cb[j*16+i]!=0xE3) mainbuf[(y+j)*320+(x+i)] = cb[j*16+i];
       }
   }
}
Эта операция происходит очень медленно, а таких операций проводится довольно много.
Как можно это оптимизировать? memcpy - ? - но там нельзя использовать условия.
Прошу вашей помощи.
Заранее спасибо
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
stima
449 / 298 / 20
Регистрация: 22.03.2011
Сообщений: 966
Завершенные тесты: 2
26.04.2013, 14:11     Быстрое копирование массивов с условиями #2
В данном контексте никак.
nonedark2008
883 / 622 / 125
Регистрация: 28.07.2012
Сообщений: 1,662
26.04.2013, 14:40     Быстрое копирование массивов с условиями #3
Каково хоть задание? А то с тем что есть - никак.
stima
449 / 298 / 20
Регистрация: 22.03.2011
Сообщений: 966
Завершенные тесты: 2
26.04.2013, 14:42     Быстрое копирование массивов с условиями #4
Повангую.

У вас есть часть кода которая читает по 16*16 элементов, потом мержит это в один массив при условии.
Вопрос возможно стоит сразу заполнять нужный массив? Тем более это у вас цельный блок памяти, смещения можно высчитать.
Tulosba
:)
Эксперт С++
4392 / 3235 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
26.04.2013, 14:44     Быстрое копирование массивов с условиями #5
Такое ощущение что "маску" накладывает на изображение.
JerryI
0 / 0 / 0
Регистрация: 26.04.2013
Сообщений: 31
26.04.2013, 14:45  [ТС]     Быстрое копирование массивов с условиями #6
Вообще, это система прорисовки спрайтов в видео-память. cb - спрайт 16х16. mainbuf - видео-память. А значение 0xE3 - альфа канал(прозрачность). И есть еще таблица(массив) 15х20 (240x320 / 16), в которой хранятся коды спрайтов. Могу полный код дать, если нужно.
stima
449 / 298 / 20
Регистрация: 22.03.2011
Сообщений: 966
Завершенные тесты: 2
26.04.2013, 14:58     Быстрое копирование массивов с условиями #7
1. Распараллельте цикл
2. Копируйте поблочно.
3. Воспользуйтесь оптимизацией компилятора.

Это все самое простое что приходит сразу в голову.
JerryI
0 / 0 / 0
Регистрация: 26.04.2013
Сообщений: 31
26.04.2013, 15:13  [ТС]     Быстрое копирование массивов с условиями #8
C++
1
2
3
4
5
void set(int x, int y) {
   for (unsigned char i=0; i<16; ++i) {
           memcpy(&mainbuf[(i+y)*320+x], &cb[i*16], 16);
   }
}
Как-то так? Конечно могу ошибаться с синтаксисом memcpy, тк. совсем с ним не работал.

Добавлено через 1 минуту
И в этом случае я теряю альфа-канал.
stima
449 / 298 / 20
Регистрация: 22.03.2011
Сообщений: 966
Завершенные тесты: 2
26.04.2013, 21:28     Быстрое копирование массивов с условиями #9
Нет не так.
1. Это пример распараллеливания:
C++
1
2
3
4
5
6
7
int *array = malloc(10 * sizeof(int));
.....
for (int i=0; i < size; i += 2)
{
    *array[i] += 1;
    *array[i+1] += 1;
}
Почему так? Грубо говоря операция сложения 3 регистра у процессора 9 регистров. Цикл записанный таким образом дает возможность использовать процессору 6 регистров вместо 3, так как он точно знает что операции не пересекаются. Подробнее читайте сами.

2. Это пример копирования по блочно:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
int *source = ....
int *dest = ....
....
 
for ()
{
   int counter = 0; 
   for (int i = 0; i < size; ++i)
    {
      if (source[i] == condition)
          ++counter;
    }
    memcpy(dest, src, j + counter);
Грубо говоря инкрементирование размера который нужно скопировать + копирование блоком дешевле чем поодиночное копированиие. Но это зависит от данных, нужно тестить.

3. Это пример как влючить оптимизацию
g++ -O3 main.cpp -o mytarget.exe

Можете еще попробовать O4, но врядле она будет быстрее чем О3. Разницу нагуглите.

п.с. Это из простых оптимизаций. Остальное сложно и очень зависти от данных)
JerryI
0 / 0 / 0
Регистрация: 26.04.2013
Сообщений: 31
26.04.2013, 21:42  [ТС]     Быстрое копирование массивов с условиями #10
Спасибо. Попробую сделать, отпишусь.

Добавлено через 46 секунд
Вопрос. В примере 1 - не понял где второй массив. Там же только операции с одним массивом проводятся. Или я чего-то недопонимаю...
stima
449 / 298 / 20
Регистрация: 22.03.2011
Сообщений: 966
Завершенные тесты: 2
26.04.2013, 21:52     Быстрое копирование массивов с условиями #11
Смысл в распараллеливании. Неважно какого алгоритма. Читайте ''обьяснение". Так понятней?

C++
1
2
3
4
5
6
7
8
9
int *src = malloc(10 * sizeof(int));
int *dest = malloc(10 * sizeof(int));
 
.....
for (int i=0; i < size; i += 2)
{
    *dest[i] = src[i];
    *dest[i+1] = src[i+1];
}
п.с. Такая оптимизация есть и в memcpy. Поэтому я и советую использовать флаг оптимизации.
п.с.с. Очень грубо говоря, процессор выполнит 2 копирования одновременно, так как у него хватит регистров.

Добавлено через 3 минуты
Забыл, можно использовать кэширование. Ускорит работу, но скушает память.
JerryI
0 / 0 / 0
Регистрация: 26.04.2013
Сообщений: 31
26.04.2013, 21:56  [ТС]     Быстрое копирование массивов с условиями #12
Теперь понятно, спасибо. Что-то я туго соображаю
Somebody
2786 / 1600 / 145
Регистрация: 03.12.2007
Сообщений: 4,189
Завершенные тесты: 1
26.04.2013, 22:10     Быстрое копирование массивов с условиями #13
Цитата Сообщение от stima Посмотреть сообщение
Грубо говоря операция сложения 3 регистра у процессора 9 регистров. Цикл записанный таким образом дает возможность использовать процессору 6 регистров вместо 3, так как он точно знает что операции не пересекаются. Подробнее читайте сами.
Кому надо почитать подробнее, так это тебе, как мне кажется...
stima
449 / 298 / 20
Регистрация: 22.03.2011
Сообщений: 966
Завершенные тесты: 2
26.04.2013, 22:11     Быстрое копирование массивов с условиями #14
В чем я не прав?
Somebody
2786 / 1600 / 145
Регистрация: 03.12.2007
Сообщений: 4,189
Завершенные тесты: 1
26.04.2013, 23:24     Быстрое копирование массивов с условиями #15
Циклы раскручиваются для уменьшения накладных расходов. Реже будет выполняться переход, значение i, от которого зависит i + 1, меняется реже. Какие регистры будут использоваться - дело компилятора, тут вообще сложно сказать. Зато у процессора есть механизм переименования регистров и, например, в случае типа
Assembler
1
2
3
4
mov eax, [a]
mov [b], eax
mov eax, [c]
mov [d], eax
в качестве eax'ов вполне могут использоваться два разных регистра.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.04.2013, 00:20     Быстрое копирование массивов с условиями
Еще ссылки по теме:
C++ Помогите найти ошибку: копирование массивов
Быстрое умножение C++
Быстрое шифрование C++
Быстрое изучение С++ C++
Быстрое деление 2х длинных C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
stima
449 / 298 / 20
Регистрация: 22.03.2011
Сообщений: 966
Завершенные тесты: 2
27.04.2013, 00:20     Быстрое копирование массивов с условиями #16
Согласен и нет. Согласен с тем что Вы уточнили мой ответ, не согласен с тем, что Вы сказали, что мой ответ не правилен.
Yandex
Объявления
27.04.2013, 00:20     Быстрое копирование массивов с условиями
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru