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

Инициализировать массив быстро? - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 25, средняя оценка - 4.84
vb_lord
2 / 2 / 0
Регистрация: 06.12.2011
Сообщений: 33
10.12.2011, 20:04     Инициализировать массив быстро? #1
Возможно ли инициализировать все элементы массива каким-то числом быстрее, чем через цикл? Как это можно сделать? Если нельзя, то как лучше это сделать в цикле-помещать локальные переменные счетчика и числа в процессорные регистры?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
DeadRipper
64 / 70 / 3
Регистрация: 25.06.2009
Сообщений: 244
10.12.2011, 21:06     Инициализировать массив быстро? #21
Цитата Сообщение от vb_lord Посмотреть сообщение
А какой вариан может быть для статичного числа? Возможно, смогу привести к этому виду код некоторых функций.
ну фактически все сводится к посту taras atavin
можно заранее создать число большее по размеру которое было бы сочетанием нескольких переменных, но когда неизвестно это число мне кажется это только дольше будет
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
10.12.2011, 21:06     Инициализировать массив быстро? #22
taras atavin, mmx работает с массивами данных
register же наврятли для этого применялся
vb_lord
2 / 2 / 0
Регистрация: 06.12.2011
Сообщений: 33
10.12.2011, 21:12  [ТС]     Инициализировать массив быстро? #23
Цитата Сообщение от alex_x_x Посмотреть сообщение
mmx/sse не, не слышали?
В разделе code generation настроек есть опция включения генерации кода компилятором, использующим расширенные наборы инструкций sse, sse2. Но это не раздел optimization. Надеюсь, что при отключенной оптимизации, эта опция будет работать как независимая, т.к. терять в скорости арифметики тоже неохота...
DeadRipper
64 / 70 / 3
Регистрация: 25.06.2009
Сообщений: 244
10.12.2011, 21:17     Инициализировать массив быстро? #24
Цитата Сообщение от vb_lord Посмотреть сообщение
Спасибо, к сожаленю, не владею ассемблером, изучать нет времени.
ну тут не все так сложно:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <windows.h>
#include <stdio.h>
 
void main ()
{
int massiv[100];
int chislo=200;
int *pmassiv=massiv; //указатель на массив (не знаю как на асме его взять от massiv)
 
_asm{
 
    //записываем в стек 3 регистра мб они использовались где то
push eax; //будет элементом массива
push ebx; //будет числом
push ecx; // будет счетчиком 0..99
 
mov eax,pmassiv; //адрес на начало массива ложим в eax
mov ebx,chislo; //ложим в ebx число
xor ecx,ecx;// зануляем ecx
 
cc: //начало цикла
mov [eax],ebx //пишем в ячейку массива число []-означает что пишем не в eax а по адресу в eax
add eax,4 //увеличиваем адрес на 4 (int)
inc ecx; //увеличиваем счетчик на 1
cmp ecx,100;
jz ce;       //если ecx==100 выходим
jmp cc;
ce: //выход из цикла
 
pop eax;   //возвращаем программе взятые нами регистры как они были
pop ebx;
pop ecx;
}
 
for(int a=0;a<100;++a)
{
printf("massiv[%d] = %d \n",a,massiv[a]);
}
 
system("pause");
}
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
10.12.2011, 21:21     Инициализировать массив быстро? #25
Цитата Сообщение от alex_x_x Посмотреть сообщение
register же наврятли для этого применялся
счётчик - не массив.
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
10.12.2011, 21:28     Инициализировать массив быстро? #26
Что-то мне кажется, что компилятор сделает код не хуже, чем эта ассемблерая вставка.
Если убрать лишний jmp, лишний cmp (можно ecx менять от 99 до 0), развернуть цикл, возможно, добавить prefetch'и (не знаю, будет ли лучше, но попробовать не вредно), копировать целыми xmm регистрами сразу по 4 элемента, тогда надо будет уже сравнивать.
DeadRipper
64 / 70 / 3
Регистрация: 25.06.2009
Сообщений: 244
10.12.2011, 21:35     Инициализировать массив быстро? #27
Цитата Сообщение от Somebody Посмотреть сообщение
Что-то мне кажется, что компилятор сделает код не хуже, чем эта ассемблерая вставка.
разве что берет число он каждый раз по памяти, когда лучше бы занести его в регистр
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
10.12.2011, 22:12     Инициализировать массив быстро? #28
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <cstdlib>
 
using namespace std;
 
int main()
{
    const size_t s = 10000;
    int a[s];
    int x;
    cin >> x;
    asm("int $3");
    for (size_t i = 0; i < s; i++)
        a[i] = x;
    cout << a[rand() % s] << endl;
}
g++, максимальная оптимизация:
Код
0040137B  |. 8B9424 5C9C000>MOV EDX,DWORD PTR SS:[ESP+9C5C]
00401382  |. 31DB           XOR EBX,EBX
00401384  |. 8D4424 1C      LEA EAX,DWORD PTR SS:[ESP+1C]
00401388  |> 891498         /MOV DWORD PTR DS:[EAX+EBX*4],EDX
0040138B  |. 43             |INC EBX
0040138C  |. 81FB 10270000  |CMP EBX,2710
00401392  |.^75 F4          \JNZ SHORT tt.00401388
+ ещё MMX/SSE/SSE2:
Код
0040138F  |. 8D4424 10      LEA EAX,DWORD PTR SS:[ESP+10]
00401393  |. 66:0F6E8C24 5C>MOVD MM1,DWORD PTR SS:[ESP+9C5C]
0040139C  |. 66:0F70C1 00   PSHUFW MM0,MM1,0
004013A1  |. 8D9424 509C000>LEA EDX,DWORD PTR SS:[ESP+9C50]
004013A8  |. 90             NOP
004013A9  |. 8DB426 0000000>LEA ESI,DWORD PTR DS:[ESI]
004013B0  |> 66:0F7F00      /MOVQ QWORD PTR DS:[EAX],MM0
004013B4  |. 83C0 10        |ADD EAX,10
004013B7  |. 39D0           |CMP EAX,EDX
004013B9  |.^75 F5          \JNZ SHORT tt.004013B0
Даже цикл по 16-байтной границе выровнен.

Добавлено через 10 минут
А с ключом -funroll-loops вообще замечательно
Код
0040138F   . 8D9424 509C000>LEA EDX,DWORD PTR SS:[ESP+9C50]
00401396   . 66:0F6E8C24 5C>MOVD MM1,DWORD PTR SS:[ESP+9C5C]
0040139F   . 66:0F70C1 00   PSHUFW MM0,MM1,0
004013A4   . 8D4424 10      LEA EAX,DWORD PTR SS:[ESP+10]
004013A8   . 89D1           MOV ECX,EDX
004013AA   . 29C1           SUB ECX,EAX
004013AC   . 66:0F7F00      MOVQ QWORD PTR DS:[EAX],MM0
004013B0   . 83E9 10        SUB ECX,10
004013B3   . C1E9 04        SHR ECX,4
004013B6   . 8D4424 20      LEA EAX,DWORD PTR SS:[ESP+20]
004013BA   . 83E1 07        AND ECX,7
004013BD   . 39D0           CMP EAX,EDX
004013BF   . 0F84 99000000  JE tt.0040145E
004013C5   . 85C9           TEST ECX,ECX
004013C7   . 74 67          JE SHORT tt.00401430
004013C9   . 83F9 01        CMP ECX,1
004013CC   . 74 49          JE SHORT tt.00401417
004013CE   . 83F9 02        CMP ECX,2
004013D1   . 74 3D          JE SHORT tt.00401410
004013D3   . 83F9 03        CMP ECX,3
004013D6   . 74 31          JE SHORT tt.00401409
004013D8   . 83F9 04        CMP ECX,4
004013DB   . 90             NOP
004013DC   . 8D7426 00      LEA ESI,DWORD PTR DS:[ESI]
004013E0   . 74 20          JE SHORT tt.00401402
004013E2   . 83F9 05        CMP ECX,5
004013E5   . 74 14          JE SHORT tt.004013FB
004013E7   . 83F9 06        CMP ECX,6
004013EA   . 74 08          JE SHORT tt.004013F4
004013EC   . 66:0F7F00      MOVQ QWORD PTR DS:[EAX],MM0
004013F0   . 8D4424 30      LEA EAX,DWORD PTR SS:[ESP+30]
004013F4   > 66:0F7F00      MOVQ QWORD PTR DS:[EAX],MM0
004013F8   . 83C0 10        ADD EAX,10
004013FB   > 66:0F7F00      MOVQ QWORD PTR DS:[EAX],MM0
004013FF   . 83C0 10        ADD EAX,10
00401402   > 66:0F7F00      MOVQ QWORD PTR DS:[EAX],MM0
00401406   . 83C0 10        ADD EAX,10
00401409   > 66:0F7F00      MOVQ QWORD PTR DS:[EAX],MM0
0040140D   . 83C0 10        ADD EAX,10
00401410   > 66:0F7F00      MOVQ QWORD PTR DS:[EAX],MM0
00401414   . 83C0 10        ADD EAX,10
00401417   > 66:0F7F00      MOVQ QWORD PTR DS:[EAX],MM0
0040141B   . 83C0 10        ADD EAX,10
0040141E   . 39D0           CMP EAX,EDX
00401420   . 74 3C          JE SHORT tt.0040145E
00401422   . 8DB426 0000000>LEA ESI,DWORD PTR DS:[ESI]
00401429   . 8DBC27 0000000>LEA EDI,DWORD PTR DS:[EDI]
00401430   > 66:0F7F00      MOVQ QWORD PTR DS:[EAX],MM0
00401434   . 66:0F7F40 10   MOVQ QWORD PTR DS:[EAX+10],MM0
00401439   . 66:0F7F40 20   MOVQ QWORD PTR DS:[EAX+20],MM0
0040143E   . 66:0F7F40 30   MOVQ QWORD PTR DS:[EAX+30],MM0
00401443   . 66:0F7F40 40   MOVQ QWORD PTR DS:[EAX+40],MM0
00401448   . 66:0F7F40 50   MOVQ QWORD PTR DS:[EAX+50],MM0
0040144D   . 66:0F7F40 60   MOVQ QWORD PTR DS:[EAX+60],MM0
00401452   . 66:0F7F40 70   MOVQ QWORD PTR DS:[EAX+70],MM0
00401457   . 83E8 80        SUB EAX,-80
0040145A   . 39D0           CMP EAX,EDX
0040145C   .^75 D2          JNZ SHORT tt.00401430
vb_lord
2 / 2 / 0
Регистрация: 06.12.2011
Сообщений: 33
19.12.2011, 22:28  [ТС]     Инициализировать массив быстро? #29
Если массив объявлен так:

C++
1
2
3
4
5
double **array=new double *[array_size];
for(int i=0; i<array_size; i++)
{
   array[i] = new double[array_size];
}
,

то можно ли его инициализировать нулями так:

C++
1
2
3
4
5
memset(array, 0, sizeof(double)*array_size);
for(int i=0; i<array_size; i++)
{
   memset(array[i], 0, sizeof(double)*array_size);
}
?
Jupiter
Каратель
Эксперт C++
6543 / 3963 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
19.12.2011, 22:44     Инициализировать массив быстро? #30
Цитата Сообщение от vb_lord Посмотреть сообщение
то можно ли его инициализировать нулями так:
а смысл когда можно так
C++
1
2
3
4
5
double **array=new double *[array_size]();
for(int i=0; i<array_size; i++)
{
   array[i] = new double[array_size]();
}
vb_lord
2 / 2 / 0
Регистрация: 06.12.2011
Сообщений: 33
19.12.2011, 22:50  [ТС]     Инициализировать массив быстро? #31
Спасибо, это мне сэкономит несколько циклов

Цитата Сообщение от Jupiter Посмотреть сообщение
а смысл когда можно так
C++
1
2
3
4
5
double **array=new double *[array_size]();
for(int i=0; i<array_size; i++)
{
   array[i] = new double[array_size]();
}
Т.е. сразу при объявлении массива скобки () обозначают, что все элементы равны 0?
Jupiter
Каратель
Эксперт C++
6543 / 3963 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
19.12.2011, 22:56     Инициализировать массив быстро? #32
Цитата Сообщение от vb_lord Посмотреть сообщение
Т.е. сразу при объявлении массива скобки () обозначают, что все элементв равны 0?
а поверить и проверить, не?
иначе бы я и не писал
vb_lord
2 / 2 / 0
Регистрация: 06.12.2011
Сообщений: 33
19.12.2011, 23:01  [ТС]     Инициализировать массив быстро? #33
Цитата Сообщение от Jupiter Посмотреть сообщение
а поверить и проверить, не?
иначе бы я и не писал
Пишу длл, к сожалению, не знаю как ее запускать и отлаживать, а если исполняемый файл сделать, то не знаю как там выводить на экран. Такое положение скобок вижу впервые. Раньше в VB6 сразу выводил в текстовое поле, а в С++ готовых форм нет. Надеюсь, что аккуратно напишу библиотеку без ошибок...
vb_lord
2 / 2 / 0
Регистрация: 06.12.2011
Сообщений: 33
20.12.2011, 02:55  [ТС]     Инициализировать массив быстро? #34
Научился выводить в консоль. Проверяем исходный вариант:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// exe_for_test.cpp : Defines the entry point for the console application.
#include "stdafx.h"
#include "conio.h"
 
int _tmain(int argc, _TCHAR* argv[])
{
    // определение размера массива
    int some_array_size=2;
    // цикл для тестирования содержимого массива
    for (int i=1; i<11; i++)
    {
        // выделение памяти массиву
        double **some_array=new double *[some_array_size];
        for(int i=0; i<some_array_size; i++)
        {
            some_array[i] = new double[some_array_size];
        }
        // вывод значений массива
        printf("%d, %d, %d, %d \n", some_array[0][0], some_array[0][1], some_array[1][0], some_array[1][1]);
        // удаление массива
        for(int i=0; i<some_array_size; i++)
        {
            delete [] some_array[i];
            some_array[i]=NULL;
        }
        delete [] some_array;
        some_array=NULL;
    }
    _getch();
    return 0;
}
Получаем, что в ячейках что-то есть:
Миниатюры
Инициализировать массив быстро?  
vb_lord
2 / 2 / 0
Регистрация: 06.12.2011
Сообщений: 33
20.12.2011, 03:12  [ТС]     Инициализировать массив быстро? #35
Проверяем вариант Jupiter:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// exe_for_test.cpp : Defines the entry point for the console application.
#include "stdafx.h"
#include "conio.h"
 
int _tmain(int argc, _TCHAR* argv[])
{
    // определение размера массива
    int some_array_size=2;
    // цикл для тестирования содержимого массива
    for (int i=1; i<11; i++)
    {
        // выделение памяти массиву
        double **some_array=new double *[some_array_size]();
        for(int i=0; i<some_array_size; i++)
        {
            some_array[i] = new double[some_array_size]();
        }
        // вывод значений массива
        printf("%d, %d, %d, %d \n", some_array[0][0], some_array[0][1], some_array[1][0], some_array[1][1]);
        // удаление массива
        for(int i=0; i<some_array_size; i++)
        {
            delete [] some_array[i];
            some_array[i]=NULL;
        }
        delete [] some_array;
                some_array=NULL;
    }
        _getch();
    return 0;
}

Получаем, что ячейки пусты: браво Jupiter!
Если бы еще кто-то подсказал, как этими скобками пользоваться, и почему 0 они дают, было бы совсем здорово.
Изображения
 
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
20.12.2011, 07:01     Инициализировать массив быстро? #36
Цитата Сообщение от DeadRipper Посмотреть сообщение
ну фактически все сводится к посту taras atavin
можно заранее создать число большее по размеру которое было бы сочетанием нескольких переменных, но когда неизвестно это число мне кажется это только дольше будет
Почему?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void s(short int x, short int *&a, unsingned int n)
{
 long int *p;
 long int *e;
 long int t;
 t=x|(x<<(sizeof(x)*8));// Объединяем один раз
 a= new short int [n];
 if (a)
 {
  e=(long int *)a;
  for (p=e+n/2-1; p>=e; --p) // И экономим тысячи инитов. У него ведь на весь массив одно значение
  {
   *p=t;
  }
 }
}
Добавлено через 3 минуты
Цитата Сообщение от DeadRipper Посмотреть сообщение
xor ecx,ecx;// зануляем ecx
И после этого ты говоришь об оптимизации?! С нолём надо сравнивать, так как это быстрее любого другого сравнения.

Добавлено через 9 минут
Цитата Сообщение от DeadRipper Посмотреть сообщение
разве что берет число он каждый раз по памяти, когда лучше бы занести его в регистр
Когда это оправдано, он помещает данные в регистры, в компилированном коде часть переменных даже вообще ни когда не бывает ни где, кроме регистров. Но чтоб поместить данное в регистр, сначала надо сохранить другое данное. А если для трёх часто используемых даннных будет использоваться общий регистр из-за нехватки регистров, а для трёх более редких - индивидуальные, то при каждом обращении к общему регистру происходит два обращения к памяти, что медленнее доступа к индивидуальным регистрам, что тормозит исполнение, а при противоположном распределении регистров это бы происходило реже и реже торможение. Регистров то не так уж много, есть камни всего с четырьмя регистрами общего назначения.

Добавлено через 3 минуты
Цитата Сообщение от Jupiter Посмотреть сообщение
а смысл когда можно так
Код C++
double **array=new double *[array_size]();
for(int i=0; i<array_size; i++)
{
* *array[i] = new double[array_size]();
}
Я бы не стал полагаться на дефолтозануление по new за исключением объектов и только с известными дефолтоконструкторами. А дабл - скаляр.
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
20.12.2011, 11:56     Инициализировать массив быстро? #37
Цитата Сообщение от taras atavin Посмотреть сообщение
Я бы не стал полагаться на дефолтозануление по new за исключением объектов и только с известными дефолтоконструкторами. А дабл - скаляр.
Почему? В стандарте же (пункт 8.5) чётко говорится:
Цитата Сообщение от C++98
To default-initialize an object of type T means:
--if T is a non-POD class type (_class_), the default constructor for
T is called (and the initialization is ill-formed if T has no acces-
sible default constructor);
--if T is an array type, each element is default-initialized;
--otherwise, the storage for the object is zero-initialized.
...
An object whose initializer is an empty set of parentheses, i.e., (),
shall be default-initialized.
Цитата Сообщение от C++11
To value-initialize an object of type T means:
— if T is a (possibly cv-qualified) class type (Clause 9) with a user-provided constructor (12.1), then the
default constructor for T is called (and the initialization is ill-formed if T has no accessible default
constructor);
— if T is a (possibly cv-qualified) non-union class type without a user-provided constructor, then the object
is zero-initialized and, if T’s implicitly-declared default constructor is non-trivial, that constructor is
called.
— if T is an array type, then each element is value-initialized;
— otherwise, the object is zero-initialized.
...
An object whose initializer is an empty set of parentheses, i.e., (), shall be value-initialized.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
20.12.2011, 12:13     Инициализировать массив быстро? #38
Цитата Сообщение от Somebody Посмотреть сообщение
-if T is a non-POD class type
Это не английский, подкласс по-английски subclass.
Вопрос таков: пчелить, иль не пчелить
(гамлет в кривом тройном переводе английски-русский-англиский-русский).
Цитата Сообщение от Somebody Посмотреть сообщение
To default-initialize an object of type T means:
--if T is a non-POD class type (_class_), the default constructor for
T is called (and the initialization is ill-formed if T has no acces-
sible default constructor);
--if T is an array type, each element is default-initialized;
--otherwise, the storage for the object is zero-initialized.
...
An object whose initializer is an empty set of parentheses, i.e., (),
shall be default-initialized.
Инициализация дефотным значением, если значение не задано явно. И что? Само дефолтное значение может быть каким угодно, хоть рандомным. Зато, в конструкторе сказано, что экземпляр класса всегда создаётся конструктором, если не указан иной конструктор - дефолтным и если экземпляр является элементом массива - тоже дефолтным конструктором, дефолтное значение определено объектов в дефолтном конструкторе, на у если юзишь другой конструктор, то значение задано явно. Какими точно словами - не знаю, но смысл этот.
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
20.12.2011, 14:21     Инициализировать массив быстро? #39
Цитата Сообщение от vb_lord Посмотреть сообщение
Массивы double и int типов
можно разобрать это
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
typedef struct x
{
    uint64_t x1;
    uint64_t x2;
    uint64_t x3;
    uint64_t x4;
} x_t;
 
int main()
{
    int s = sizeof(x_t) / sizeof(int), i = 0;
    int arr[s];
    x_t y;
    y.x1 = 0x7f7f7f7f8a8a8a8a;
    y.x2 = 0x8a8a8a8a7f7f7f7f;
    y.x3 = 0x7f7f7f7f8a8a8a8a;
    y.x4 = 0x8a8a8a8a7f7f7f7f;
    memmove( &arr[0], &y, sizeof(x_t) );
    while ( i < s )
        printf("%x ", arr[ i++ ]);
 
    return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.02.2012, 09:57     Инициализировать массив быстро?
Еще ссылки по теме:

не получается инициализировать массив C++
Как инициализировать массив в классе C++
Как инициализировать массив в dll ? C++

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

Или воспользуйтесь поиском по форуму:
vb_lord
2 / 2 / 0
Регистрация: 06.12.2011
Сообщений: 33
17.02.2012, 09:57  [ТС]     Инициализировать массив быстро? #40
А ведь еще быстрее наверно можно, если директивы OpenMP использовать в вариантах с циклами.
Yandex
Объявления
17.02.2012, 09:57     Инициализировать массив быстро?
Ответ Создать тему
Опции темы

Текущее время: 00:45. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru