tmp with mpl

@NeonLost · Регистрация: 23.02.2012

Author24 — интернет-сервис помощи студентам

я в ран тайме заполняю массив числами фибоначи до 10000 элемента...можно ли вычислить в компиле тайм и в рантайме только заполнить?..)

@diagon · 12.02.2013, 20:31

1) Оно вряд ли скомпилится, слишком много шаблонных инстанцирований будет... Ну, за пару часиков может и скомпилится.
2) Даже первые 100 элементов заполнить не получится из-за того, что результат перестанет влезать в стандартные типы данных. Следовательно, нужно либо вычислять по какому-то модулю, либо использовать длинную арифметику.

@NeonLost · 12.02.2013, 21:09 **[ТС]**

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

1) Оно вряд ли скомпилится, слишком много шаблонных инстанцирований будет... Ну, за пару часиков может и скомпилится.
2) Даже первые 100 элементов заполнить не получится из-за того, что результат перестанет влезать в стандартные типы данных. Следовательно, нужно либо вычислять по какому-то модулю, либо использовать длинную арифметику.

чет я не подумал...пускай будут не числа фибоначи, а формула i*3cos(45)/2(где i от 1 до 1000)

@yekka · 14.02.2013, 22:07

Набросал такой код:

C++

#include <iostream>
#include <algorithm>
#include <iterator>
 
template <long N, long R = 1, long S = 0>
struct CompileTimeArray {
    long value;
    CompileTimeArray<N - 1, R + 1, S + R> tail;
 
    CompileTimeArray() : value(S) {}
};
 
template <long R, long S>
struct CompileTimeArray<0L, R, S> {
    long value;
 
    CompileTimeArray() : value(S) {}
};
 
int main() {
    CompileTimeArray<LENGTH> array;
    long * array_pointer = (long *) &array;
    std::ostream_iterator<long> iter(std::cout, " ");
    std::copy(array_pointer, array_pointer + LENGTH, iter);
    std::endl(std::cout);
}

создаем массив из элементов последовательности $https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{n(n-1)}{2}$ . Причем значения считаем во время компиляции, а во время исполнения только заполняем массив.

Пример:

Код

$ g++ recur.cpp  -DLENGTH=10 && ./a.out
0 1 3 6 10 15 21 28 36 45

С массивом из 100'000 элементов компилятор возился около шести минут и отожрал под это дело два с половиной гигабайта памяти:

Код

$ time g++ recur.cpp  -DLENGTH=100000 -ftemplate-depth=200000 -finline-limit=200000 -O1

real    5m44.512s
user    5m40.933s
sys     0m2.116s

К сожалению, заставить компилятор проинлайнить все конструкторы мне не удалось. Из 100'000 компилятор проинлайнил только 53759:

Assembler

00000000005c19d2 <_ZN16CompileTimeArrayILl99998ELl3ELl3EEC1Ev>:
  5c19d2:   48 83 ec 08             sub    $0x8,%rsp
  5c19d6:   48 c7 07 03 00 00 00    movq   $0x3,(%rdi)
  5c19dd:   48 c7 47 08 06 00 00    movq   $0x6,0x8(%rdi)
  5c19e4:   00
  5c19e5:   48 c7 47 10 0a 00 00    movq   $0xa,0x10(%rdi)
  5c19ec:   00
  5c19ed:   48 c7 47 18 0f 00 00    movq   $0xf,0x18(%rdi)
  5c19f4:   00
  5c19f5:   48 c7 47 20 15 00 00    movq   $0x15,0x20(%rdi)
  5c19fc:   00
  5c19fd:   48 83 c7 28             add    $0x28,%rdi
  5c1a01:   e8 a2 ff ff ff          callq  5c19a8 <_ZN16CompileTimeArrayILl99993ELl8ELl28EEC1Ev>
  5c1a06:   48 83 c4 08             add    $0x8,%rsp
  5c1a0a:   c3                      retq
  5c1a0b:   0f 1f 44 00 00          nopl   0x0(%rax,%rax,1)

Так что при заполнении массива будет совершено более 46000 вложенных вызовов конструкторов.

@NeonLost Пес войны 111 / 88 / 22 Регистрация: 23.02.2012 Сообщений: 653
		1
	tmp with mpl 12.02.2013, 19:30. Показов 1849. Ответов 3 Метки нет (Все метки) я в ран тайме заполняю массив числами фибоначи до 10000 элемента...можно ли вычислить в компиле тайм и в рантайме только заполнить?..) 0

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	12.02.2013, 20:31	2
	1) Оно вряд ли скомпилится, слишком много шаблонных инстанцирований будет... Ну, за пару часиков может и скомпилится. 2) Даже первые 100 элементов заполнить не получится из-за того, что результат перестанет влезать в стандартные типы данных. Следовательно, нужно либо вычислять по какому-то модулю, либо использовать длинную арифметику. 0

@NeonLost Пес войны 111 / 88 / 22 Регистрация: 23.02.2012 Сообщений: 653
	12.02.2013, 21:09 [ТС]	3
	Сообщение от diagon 1) Оно вряд ли скомпилится, слишком много шаблонных инстанцирований будет... Ну, за пару часиков может и скомпилится. 2) Даже первые 100 элементов заполнить не получится из-за того, что результат перестанет влезать в стандартные типы данных. Следовательно, нужно либо вычислять по какому-то модулю, либо использовать длинную арифметику. чет я не подумал...пускай будут не числа фибоначи, а формула i*3cos(45)/2(где i от 1 до 1000) 0

	14.02.2013, 22:07

Опции темы

tmp with mpl

Решение