Работу конвейера вполне можно назвать интерпретацией.

А если эмулировать процессор на каком-нибудь хаскеле, то там столько всего появится - и монады, и стрелки, и чёрт с дьяволом...

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

Блин, ну вы ещё скажите, что выключатель света интерпретирует ваши нажатия на выключатель в разрыв или соединение электрической цепи. А чо?

Вызвал операцию не для того типа - получил неверный результат - ССЗБ.

Неверный результат для кого? Для процессора? Или неверный для твоей интерпретации полученного результата?

«я, конечно, просуммирую данные из этих двух регистров _как целые_» - это и есть интерпретация. А для тебя почему-то интерпретация заключается в проверки и определения типа. Странный ты.

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

«я, конечно, просуммирую данные из этих двух регистров _как целые_» - это и есть интерпретация

это для тебя - интерпретация. Процессор ничего не знает ни о типах, ни об операциях над значениями данных типов. Это мы интерпретируем как входные данные, так и результат. Мы, а не процессор.

А так можно договориться, что «микросхемы серии ЛА-1 интерпретируют уровни входных сигналов как двоичные 0 или 1» - бред! Вернее - приплетение абсолютно левых сущностей. Но если кому-то так нравится...

Для тебя, конечно. Но это тоже самое.

О, моя интерпретация реальности и сама реальность - тоже самое? Отличненько...

Смотри. У нас есть набор операций, который работает с одной интерпретацией. Есть набор операций, который работает с другой. Это операции над разными типами. Просто «тэгов» нет.

Даже в Haskell'ях типы есть не потому, что там есть тайпчекер и теги типов... Это дополнительные плюшки.

Это операции над разными типами. Просто «тэгов» нет.

Вот только типы эти есть только в нашей голове - в нашей интерпретации данных. В процессоре типов нет.

Тогда их точно так же нет и в любом языке(тайпчекер ничего не меняет). ИИ не существует же.

А если эмулировать процессор на каком-нибудь хаскеле, то там столько всего появится - и монады, и стрелки, и чёрт с дьяволом...

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

Ну раз для вас нет - то и не надо.

ещё раз - это интерпретация команд. Интерпретации данных нет. И уж чего точно нет - типов у данных.

Типы данных определяются операциями

т.е. в первой команде - это беззнаковое 32, в следующей - знаковое 32, в следующей - старшие 16 из этих 32, но снова беззнаковые. Это какой же тип данных лежит в регистре? А если операция одинаково работает со знаковыми и беззнаковыми - какие данные в регистре? А если операция просто читает/пишет несколько байт из памяти - какой в итоге тип данных? Что, 8 типов для одного и того-же данного? У меня нет для вас набора из гамака, лыж и противогаза.

Твоя программа упала по SIGSEGV.

Твои действия?

Проснуться в холодном поту, вспомнить, что уже XXI век и можно писать на нормальных языках.

ок. твоя программа упала, высрав километровый стектрейс (в лучшем случае)

Вопрос тот же.

но вот с чем соглашусь — что с батти надо требовать бенчмарк, а пока он не сделал его — напоминать ему при каждом его ответе

я обдумаю на досуге бенчмарк...

«Твоя программа упала по SIGSEGV.

Твои действия?»

Запустить ее еще раз?

1. железный стек всё равно быстрее.

ну так где бенчмарк, сравнивающий железный стек (бугага!) с чем-нибудь типа

ну для начала учти, что железный стек характеризуется практически нулевым временем освобождения и аллокации. В твоём примере это не используется. А таки зря. Вот посмотри этот код:

#include <stdio.h>
#include <stdlib.h>
#include <alloca.h>
#include <string.h>

//#define MALLOC

void test2()
{
·   int n = 3 + rand() % 12; 
·   int m = 2 + rand() % 15; 
#ifdef MALLOC
·   char *s = malloc(n);
·   char *d = malloc(m);
#else
·   char *s = alloca(n);
·   char *d = alloca(m);
#endif
·   memset(s, 0, n); 
·   memcpy(d, s, n < m ? n : m); 
#ifdef MALLOC
·   free(s);
·   free(d);
#endif
}

void test()
{
·   int j,k;
·   for(j = 0; j < 1000; j++)
·   {
·   ·   for(k = 0; k < 10000; k++)
·   ·   {
·   ·   ·   test2();
·   ·   }
·   }
}

int main()
{
·   test();
·   return 0;
}

ЗЫЖ результаты промахов кеша показать несколько сложнее. Возможно завтра я предоставлю и эти данные. А то сейчас уже поздно.

Не то сравниваешь

Ты же аппаратный стек не сбрасываешь каждый раз, так зачем malloc каждый раз новый. Вот корректная реализация:

#include <stdio.h>
#include <stdlib.h>
#include <alloca.h>
#include <string.h>

//#define MALLOC

int* a; 
int head, head0;

inline void enter() { head0 = head; }
inline void leave() { head = head0; }
inline void *salloca(int n) { void* r = a+head; head += n; return r; }

void test2()
{
#ifdef MALLOC
    enter();
#endif
    int n = 3 + rand() % 12; 
    int m = 2 + rand() % 15; 
#ifdef MALLOC
    char *s = salloca(n);
    char *d = salloca(m);
#else
    char *s = alloca(n);
    char *d = alloca(m);
#endif
    memset(s, 0, n); 
    memcpy(d, s, n < m ? n : m);
#ifdef MALLOC
    leave();
#endif
}



void test()
{
    int j,k;
#ifdef MALLOC
    a = malloc(1024);
#endif   
    for(j = 0; j < 1000; j++)
    {
        for(k = 0; k < 10000; k++)
        {
            test2();
        }
    }
}

int main()
{
    test();
    return 0;
}

monk@veles:~/languages/c$ gcc -DMALLOC test-stack.c
monk@veles:~/languages/c$ time ./a.out 

real	0m1.901s
user	0m1.892s
sys	0m0.000s
monk@veles:~/languages/c$ time ./a.out 

real	0m1.997s
user	0m1.980s
sys	0m0.000s
monk@veles:~/languages/c$ time ./a.out 

real	0m1.871s
user	0m1.856s
sys	0m0.004s
monk@veles:~/languages/c$ gcc test-stack.c
monk@veles:~/languages/c$ time ./a.out 

real	0m2.054s
user	0m2.036s
sys	0m0.004s
monk@veles:~/languages/c$ time ./a.out 

real	0m2.070s
user	0m2.052s
sys	0m0.000s
monk@veles:~/languages/c$ time ./a.out 

real	0m2.049s
user	0m2.032s
sys	0m0.004s

Так что программная реализация даже на 10% быстрее :-)

тебе уже написали — ты не то сравниваешь

ты вовсе не сравниваешь железный стек с софтверным стеком

ты сравниваешь железный стек+возможно_какие_доп_расходы_на_вызов_alloca с malloc-ом

сравнение железного стека с софтверным стеком должно быть построено так:

железный стек — комманды ассемблера

софтверный например так:

typedef unsigned int uint;

#define SIZE (1024*1024)

uint soft_stack[SIZE]; // софтовый стек, гы-гы
uint* stack_pointer =  soft_stack + SIZE;

inline uint* push(uint size)
{
  stack_pointer -= size;
  *stack_pointer = size;
  return stack_pointer;
}  
inline void pop()
{
  stack_pointer += *stack_pointer;
}

stack_pointer -= size;

Так push(10005000) откатит стек на 10005000 (> 1024 * 1024) uint-ов и запишет (куда-то) 10005000 (то есть SIGSEGV). Лучше так (и сигнатуры другие):

#define STACK_TYPE int
#define STACK_SIZE (1024 * 1024)

STACK_TYPE stack[STACK_SIZE], *sp = stack;

void push(STACK_TYPE);
STACK_TYPE * pop(void);

inline void push(STACK_TYPE x) { assert(sp < stack + STACK_SIZE); *sp++ = x; }
inline STACK_TYPE * pop(void) { assert(sp > stack); return --sp; }

Или так, чтобы вообще указателей снаружи не было видно:

STACK_TYPE pop(void);
inline STACK_TYPE pop(void) { assert(sp > stack); return *--sp; }

Потому как оптимизации могут сильно поменять поведение кода.

Только (говно)кода, содержащего undefined behavior. Поэтому нормальные люди берут дебаггер с -O0

Так push(10005000) откатит стек на 10005000 (> 1024 * 1024) uint-ов и запишет (куда-то) 10005000 (то есть SIGSEGV)

а с каких это пор «железный стек» сам че-то проверяет и не допускает SIGSEGV ?!

нет уж, «софтовый стек» для benchmark-а должен работать так же

отмечу, что я тестил «софтовый стек» на основе кода drBatty, где malloc реализован мной через push *с проверкой* и pop — у меня получилось небльшая разница (в пределах 10%, gcc -O2)

то, что написал drBatty, это тест, *совершенно* не относящийся к вопросу «железный стек vs. софтовый стек», и поэтому даже модифицированную его версию я постить НЕ БУДУ, чтобы не уводить разговор в сторону

нет уж, «софтовый стек» для benchmark-а должен работать так же

Но он должен быть написан нормально и иметь нормальный интерфейс. То есть

• STACK_TYPE pop(void) и void push(STACK_TYPE), так чтобы можно было использовать этот минимальный интерфейс (как функции из заголовочного файла или публичные методы класса) и не лезть в реализацию (soft_stack, stack_pointer). Твой вариант нельзя использовать как стек (в духе push, pop, etc.) не трогая stack_pointer и soft_stack. Но это нормально, так как аппаратно у нас как раз push <word>, пустой pop и %sp.
• Собственно, работать нормально. Твой вариант зачем-то оставляет дыры в массиве soft_stack. Вот это надо исправить.

Вот пример, чтобы продемонстрировать в чём претензии:

/* тут твой код */

int main()
{
    push(1); push(2); push(3); push(4); push(5);
    // зачем push возвращает указатель в массив? Так можно перезаписать стек,
    // ну и у нас и так есть значения, незачем их возвращать.

    printf("%i ", *stack_pointer); pop(); // вместо printf("%i ", pop());
    printf("%i ", *stack_pointer); pop();
    printf("%i ", *stack_pointer); pop();
    printf("%i ", *stack_pointer); pop();
    printf("%i\n", *stack_pointer); pop();

    for (int i = SIZE; i > SIZE - 16; --i) // разрывы!1 ;)
        printf("%i ", soft_stack[i]);

    puts("");
}

Выхлоп:

5 4 3 2 1
0 1 0 2 0 0 3 0 0 0 4 0 0 0 0 5

Твой вариант зачем-то оставляет дыры в массиве soft_stack. Вот это надо исправить.

это сделано *специально*, чтобы смоделировать железный стек

пример: у нас есть функция:

int f(int x, int y, int z)
{
   int a = ... ;
   int b = ... ;
   if( ... ) 
      return ... ;
   int c = f( ... , ... , ... );
   return a+b/c;
}

при входе в нее происходит ровно то, что делает push (т.е. в стек заталкивается большое пустое пространство и его длинна), а при выходе — pop; между этими вызовами происходит как раз работа с указателем, возвращенным push

такой вариант железного стека тоже интересен, хотя, конечно, не отменяет нормально теста с ассемблером, где интерфейс push & pop может быть другим

это сделано *специально*, чтобы смоделировать железный стек

Не понял. push 100500 помещает в стек одно слово (100500) и меняет esp на байт:

	.section	.rodata
fmt:
	.string	"%x\n"

	.text
	.globl	main
	.type	main, @function
main:
	movl	%esp, %esi
	movl	$fmt, %edi
	movl	$0, %eax
	call	printf

	push	$100050000

	movl	%esp, %esi
	movl	$fmt, %edi
	movl	$0, %eax
	call	printf

	pop	%rax

	ret

будет:

aa129fe8
aa129fe0

Никаких дыр нет (зачем?). У тебя push 100500 откатывает стек на 100500 байтов и потом помещает слово, оставляя пустыми 100499 байтов. Практически такого стека ни на что не хватит. Например, если взять рекурсивную процедуру использующую стек:

#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <dirent.h>
#include <sys/stat.h>

void walk_dir_rec(const char *dir)
{
    struct dirent **files;
    int n, i;
    char *file, *path;
    struct stat sb;

    if ((n = scandir(dir, &files, NULL, alphasort)) != -1) {

        for (i = 0; i < n; ++i) {

            file = files[i]->d_name;

            if (strcmp(file, ".") == 0 || strcmp(file, "..") == 0) {
                free(files[i]);
                continue;
            }

            path = calloc(strlen(dir) + strlen(file) + 2, sizeof(char));
            sprintf(path, "%s/%s", dir, file);

            if (stat(path, &sb) != -1) {
                if (S_ISDIR(sb.st_mode))
                    walk_dir_rec(path);
                else
                    printf("%s\n", path);
            }

            free(path);
            free(files[i]);
        }

        free(files);
    }
}

то её можно заменить итеративной процедурой с эмуляцией стека, причём очень небольшого стека, который всяко поместится в кеш:

#define STACK_SIZE 32

// bss
void *stack[STACK_SIZE], **sp = stack;

static inline void push(void *x)
{
    assert(sp < stack + STACK_SIZE);
    *sp++ = x;
}

static inline void *pop(void)
{
    assert(sp > stack);
    return *--sp;
}

примерно так:

void walk_dir_iter(char *dir)
{
    // `dir'                   non-local, static/heap-allocated (via `path')
    struct dirent **files;  // non-local, heap-allocated
    intmax_t n, i;          // non-local, static
    char *path;             // non-local (via `dir'), heap-allocated
    char *file;             // local, static
    struct stat sb;         // local, static

start:
    if ((n = scandir(dir, &files, NULL, alphasort)) != -1) {

        for (i = 0; i < n; ++i) {

            file = files[i]->d_name;

            if (strcmp(file, ".") == 0 || strcmp(file, "..") == 0) {
                free(files[i]);
                continue;
            }

            path = calloc(strlen(dir) + strlen(file) + 2, sizeof(char));
            sprintf(path, "%s/%s", dir, file);

            if (stat(path, &sb) != -1) {

                if (S_ISDIR(sb.st_mode)) {

                    /* `push' each non-local variable (heap-allocated variables
                     * is always non-local due to heap-based memory managment).
                     */ 
                    push((void*)dir); dir = path;
                    push((void*)files);
                    push((void*)n);
                    push((void*)i);
                    push((void*)path);
                    goto start;

                cont:
                    path = (char*)pop();
                    i = (intmax_t)pop();
                    n = (intmax_t)pop();
                    files = (struct dirent**)pop();
                    dir = (char*)pop();
                } else {

                    printf("%s\n", path);

                }
            }

            free(path);
            free(files[i]);
        }

        free(files);
    }

    if (sp == stack)
        return;
    else
        goto cont;
}

32 слов явно бы не хватило если бы мы откатывались оставляя пустые значения. Вообще, никакого бы стека не хватило, даже 100500GB, так как при такой реализации push 0xffffffffffffffff оставит (захочет оставить) одну большую дыру в 2097152TB ;)

З.Ы. бенчмарка из этих функций не получается - gcc слишком умный и работает с walk_dir_rec как tail-recursive функций, да и ABI предполагает передачу через регистры в основном. По крайней мере, там где у walk_dir_rec push и pop (штук десять) у walk_dir_iter - mov (немного побольше), так что небольшая разница есть, но её всё равно не видно:

$ gcc -std=gnu99 -Wall -Wextra -pedantic -O2 stack.c -o stack
$ time ./stack /usr > 1
./stack /usr > 1  0,25s user 0,67s system 98% cpu 0,933 total
$ gcc -std=gnu99 -Wall -Wextra -pedantic -DSOFT -DNDEBUG -O2 stack.c -o stack
$ time ./stack /usr > 2
./stack /usr > 2  0,24s user 0,69s system 98% cpu 0,937 total
$ diff 1 2
1c1
< using walk_dir_rec()
---
> using walk_dir_iter()

бенчмарка из этих функций не получается

Надо, видимо, от IO отвязать, но я не могу такой пример придумать (тут у нас много памяти + стека + рекурсия, а тут - памяти + стека-как-массива-в-памяти + goto/for/etc.).

Не понял. push 100500 помещает в стек одно слово (100500) и меняет esp на байт:

ну назови мой push как push_esp__и_еще__add_esp(int size), это понятней будет?

вообще ты похоже относишься к этому чересчур серьезно; если тебе не лень — делай drBatty-ну работу (он же там че-то тарахтел про железный стек), а вообще 99% что нихрена не будет разницы, т.к. нынешние х86 все транслируют в свой внутренний risc и там им уже пофиг че за инструкции были

работает с walk_dir_rec как tail-recursive функций

А, subj же, я даже не заметил ;)

пример простой:

1. идем по стеку и заполняем его a[j] = a[j-1]*5 mod (2 power 32)

2. f(последняя) = 1 например

3. идем по стеку обратно, вычисляя например

f(j) = ( f(j+1) xor a[j] xor ((a[j]&const) << 3) )+ a[j]

можно было бы взять f(j) = f(j+1)+a[j] но х.з. умный компилятор это соптимизует

это будет очень быстро (стек порядка 1М вызовов), поэтому в объемлющем цикле все эти значения f складываем в массив, откуда потом печатаем рандомное значение, чтобы компилятор не вздумал оптимизировать

это понятней будет?

Это - да.

делай drBatty-ну работу

Код со scandir уже писался для одной поделки - привёл как первый попавшийся пример.

f(j) = ( f(j+1) xor a[j] xor ((a[j]&const) << 3) )+ a[j]

А зачем так сложно? Это она должна есть стек за счёт call (push %rip), или за счёт явных push? С явным call можно взять любую другую функцию без TCO, а явные push тут убираются.

можно взять любую другую функцию без TCO

да, но обязательно без ТСО

ну и желательно без умножения, иначе хрень чего заметишь на фоне тормозов

апдейт: хотя, кстати, если совсем простая функция будет, то опять хрен чего заметишь на фоне тормозов на прокачке памяти

но обязательно без ТСО

Пусть будет фибоначчи с бинарной рекурсией:

#include <stdint.h>

#define STACK_SIZE 64

uintmax_t stack[STACK_SIZE], *sp = stack;

template <typename T> // requires SubtypeRelation<T, uintmax_t>
static inline void push(T x) { *sp++ = (uintmax_t)x; }

template <typename T> // requires SubtypeRelation<uintmax_t, T>
static inline void pop(T &x) { x = (T)*--sp; }

#define call(fn, rp) ip = fn##_##rp; goto fn; fn##_##rp:

enum IP { fib_rp, fib_1, fib_2 };

#define ret                                                      \
    switch (ip) {                                                \
    case fib_rp: goto fib_rp;                                    \
    case fib_1: goto fib_1;                                      \
    case fib_2: goto fib_2;                                      \
    }

#define proc(fn) uintmax_t res; IP ip; ip = fn##_rp; fn:

#define endp(fn) fn##_rp: return res;

extern "C" {
    uintmax_t fib(unsigned n);
}

uintmax_t fib(unsigned n)
{
    proc(fib)
    if (n < 2) { res = n; ret; }
  push(ip);
    push(n--);
    call(fib, 1)
    pop(n);
    push(res);
    n -= 2;
    call(fib, 2)
    n = res;
    pop(res);
    res += n;
  pop(ip);
    ret;
    endp(fib);
}

vs.

	.text

	.globl	fib
	.type	fib,@function
fib:
        pushq   %rbp
        movq    %rsp, %rbp
# if
        cmpl    $1, %edi
        ja      .else
        movl    %edi, %eax
        popq    %rbp
        ret
.else:  pushq   %rdi
        addl    $-1, %edi
        callq   fib
        popq    %rdi
        pushq   %rax
        addl    $-2, %edi
        callq   fib
        movq    %rax, %rdi
        popq    %rax
        addq    %rdi, %rax
        popq    %rbp
        ret

Проверяем так:

#include <cstdio>
#include <cstdlib>
#include <stdint.h>

extern "C" {
    uintmax_t fib(unsigned n);
}

int main (int argc, char *argv[])
{
    if (argc > 1)
        for (unsigned i = 0; i < (unsigned)atoi(argv[1]); ++i)
            printf("%jd\n", fib(i));
}

Получается:

$ g++ -O2 fib.cc fib-soft.cc -o fib-soft
$ g++ -O2 fib.cc fib-hard.s -o fib-hard
$ time ./fib-soft 45 > 1
./fib-soft 45 > 1  14,85s user 0,00s system 99% cpu 14,889 total
$ time ./fib-hard 45 > 2
./fib-hard 45 > 2  16,51s user 0,00s system 99% cpu 16,615 total

Как это можно объяснить?

то, что написал drBatty, это тест, *совершенно* не относящийся к вопросу «железный стек vs. софтовый стек»

мой тест относится к цене _выделения_ и _освобождения_ памяти. Для железного стека это почти бесплатно. Для кучи (heap) это достаточно дорого. А вот ваш «софтовый стек», это НЕ куча, это _единожды_ выделенное пространство памяти, и потому оно работает даже немного быстрее(потому-что стек не только для этого используется, а ваша память используется исключительно для теста).

Отмотай выше - тут некоторые аноны говорили, что «нормальный ЯП ВСЁ хранит в куче, и это круто!». Вот а я считаю, что хранить ВСЁ в куче - неправильно, потому как дорого _выделять_ и _освобождать_.

Хранить всё в куче и вызывать malloc на каждый чих - разные вещи

Хранить всё в куче и вызывать malloc на каждый чих - разные вещи

ок. ты предлагаешь выделить 1 раз X байт памяти, а потом выделять кусочки в этих X байтах? Тогда два вопроса:

1. чему равно X?

2. чем твой malloc будет лучше системного?

Отмотай выше - тут некоторые аноны говорили, что «нормальный ЯП ВСЁ хранит в куче, и это круто!». Вот а я считаю, что хранить ВСЁ в куче - неправильно, потому как дорого _выделять_ и _освобождать_.

ты как обычно придумываешь какой-то бред, и затем относительно успешно его опровергаешь

напомню тебе твои слова ( О хвостовой рекурсии (комментарий) )

Это единственный случай, когда можно применять рекурсию. Насчет «нужно» не соглашусь, как правило намного эффективнее будет вручную раскрытая в цикл рекурсия с явным стеком. Потому как самодельный стек на куче все же намного дешевле обойдется, чем системный стек, и до переполнения идти намного дольше.

нет. Ибо
1. железный стек всё равно быстрее.

анонимус говорит о самодельном стеке на куче, ты — о каком-то лунном единороге железном стеке, про который тебе известно, что он «всё равно быстрее»

ну так изволь предъявить тест, доказывающий преимущества железного стека

при этом «самодельный стек на куче» — это вовсе не то, что предоставляет malloc

malloc & free медленнее из-за того, что их можно вызывать в виде

a=malloc(); b=malloc(); free(a); использовать(b); free(b);

в то же время выделение памяти на стеке так использовать нельзя:

a=alloca(); b=alloca(); освободить(a); использовать(b); освободить(b);

точно так же и самодельный стек на куче быстр, но не обязан (хотя и может иногда) позволять себя использовать в таком виде:

a=аллоцировать(); b=аллоцировать(); освободить(a); использовать(b); освободить(b);

Как это можно объяснить?

это можно, но, вероятно, никак не нужно объяснять в рамках разговора о железе, куче, и стеке

дело в том, что рекурсивное вычисление фибоначчей компилятор может *очень* сильно оптимизировать вплоть до полного устранения рекурсии, так что тут, вероятно, мы видим то, что компилятор чуток с разным качеством оптимизировал два твоих разных подхода

исходя из f(n)=f(n-1)+f(n-2) компилятор, после того, как доказал, что f — чистая функция, имеет право ее заинлайнить и получить f(n)=2*f(n-2)+f(n-3)=3*f(n-3)+2*f(n-4)=... и от того, где он там остановится, скорость будет зависесть очень сильно

так же компилятор имеет право инлайнить с другого конца (начав с f(1)=1)

короче, фибоначчами можно тестить компилятор, но никак не структуры данных, в частности, скорость работы с кучей и стеком

понятно, что инлайнить f компилятор имеет право всегда, я имел в виду, что компилятор, после того, как доказал, что f — чистая функция, имеет право ее заинлайнить в виде f(n) = (n==0?1:n==1?1:n==2?2:2*f(n-2)+f(n-3) )

вот тебе сравнение железного стека и софтового:

#include <stdio.h>
#include <stdlib.h>

typedef unsigned int uint;
const int size = 1<<17;
int counter=1;

#ifdef HARDWARE_STACK

uint f(uint a)
{
  if( ++counter % size == 0 ) {
    return 1;
  }else{
    uint aa = (a<<2)+a;
    return a + ( f(aa)^a^((a&7) << 3) );
  }
}

#else

uint* soft_stack=0;
uint* soft_stack_ptr;

void init_stack()
{
  if( !soft_stack )
    soft_stack = malloc( sizeof(uint)*size );
  soft_stack_ptr = soft_stack;
}
void push(uint a)
{
  *soft_stack_ptr=a;
  ++soft_stack_ptr;
}
uint pop()
{
  return *--soft_stack_ptr;
}
uint f(uint arg)
{
  uint a=arg;
  init_stack();

  while( ++counter % size != 0 ) {
    uint aa = (a<<2)+a;
    push(a);
    a=aa;
  }
  uint result = 1;
  while( soft_stack_ptr != soft_stack ) {
    a=pop();
    result = a + ( result^a^((a&7) << 3) ) ;
  }
  return result;
}

#endif

const int N=9000;

main()
{
  uint sum=1;
  while( counter<size*N ) {
    sum+=f(sum);
  }
  printf("sum=%u\n", sum);
  return 0;
}

компилим gcc -O2, можно добавить -fomit-frame-pointer при желании

и видим, что железный стек сливает софтовому в 2 раза — у меня софтовый исполняется 4.5 секунды, железный 8.5 секунды

тест проверяет ровно то, что говорил анонимус — что развернутая ручками функция со стеком на куче исполняется не медленне, а в данном случае даже быстрее, чем рекурсивная с железным (гы-гы) стеком

ждем, когда ты предъявишь своего лунного единорога

з.ы. а почему не поровну, а быстрее? можешь попробовать объяснить

что рекурсивное вычисление фибоначчей компилятор может *очень* сильно оптимизировать

Там во втором листинге fib с двумя call написана на ассемблере, так что компилятор никак не может её оптимизировать, хоть -O3 сделай - в objdump будет тот же ассемблер что и во втором листинге. А вот первый листинг этот ровно те же самые «инструкции» что и во втором листинге, но эмулируемые, то есть с массивом вместо стека и с goto + emit new label + save new label in ip / computated goto back to (ip) label вместо call / ret / eip - вот их компилятор уже оптимизирует. Так что, да, сравнение некорректное получилось:

$ g++ -O1 fib.cc fib-soft.cc -o fib-soft
$ objdump -d fib-soft | grep "jmp.*fib"
  4005fb:	eb c0                	jmp    4005bd <fib+0x5>
  400625:	eb 96                	jmp    4005bd <fib+0x5>
$ g++ -O2 fib.cc fib-soft.cc -o fib-soft
$ objdump -d fib-soft | grep "jmp.*fib" 
  40062f:	eb 98                	jmp    4005c9 <fib+0x9>
$ cat fib.c
unsigned fib(unsigned n) { return n < 2 ? n : fib(n - 1) + fib(n - 2); }
$ gcc -O1 fib.c -S
$ grep call fib.s 
	call	fib
	call	fib
$ gcc -O2 fib.c -S
$ grep call fib.s 
	call	fib

с одинаковым количеством call/jmp софтовая реализация будет всюду проигрывать. Чтобы сделать нормальное сравнение нужно тогда всё на ассемблере писать.

чему равно X?

В зависимости от настроек VM. Как в случае с initial heap size у JVM или SBCL - они сразу большой кусок себе откусывают.

чем твой malloc будет лучше системного?

Это будет аллокатор VM связанный с GC VM и сама VM будет учитывать особенности языка, так что, в случае идиоматического использования, будет лучше системного.

анонимус говорит о самодельном стеке на куче, ты — о каком-то лунном единороге железном стеке, про который тебе известно, что он «всё равно быстрее» ну так изволь предъявить тест, доказывающий преимущества железного стека

ну дык и привёл.

malloc & free медленнее из-за того, что их можно вызывать в виде a=malloc(); b=malloc(); free(a); использовать(b); free(b);

где ты видел free() в моём коде? alloca() и удобна тем, что free() там вообще не нужно.

в то же время выделение памяти на стеке так использовать нельзя: a=alloca(); b=alloca(); освободить(a); использовать(b); освободить(b);

это не баг, а фича.

и видим, что железный стек сливает софтовому в 2 раза — у меня софтовый исполняется 4.5 секунды, железный 8.5 секунды

спасибо Кэп! шурупы, забитые молотком держатся вдвое хуже гвоздей!

А при чём тут вообще _стек_? только функциональщик, или даун-императивщик может решать такую задачу используя стек - нормальный человек просто сделает массив a[size], и потом два раза его пройдёт - от нуля до size-1 и от size-1 до 0. А зачем тут стек? Доказать мне, что он тут не в тему? Молодец, доказал, стек здесь не нужен.

А вот ты возьми задачу, где без стека не обойтись по любому. Ну к примеру те же деревья. Эта структура рекурсивная по определению, и потому, стек здесь _нужен_. Вот и сравни свой костыль, и железный стек на такой задаче. А доказывать кривость шурупов забивая их молотком - глупо.

В зависимости от настроек VM. Как в случае с initial heap size у JVM или SBCL - они сразу большой кусок себе откусывают.

это потому ПО на жабе заслужило заслуженную репутацию тупого и неповоротливого тормоза?

Это будет аллокатор VM связанный с GC VM и сама VM будет учитывать особенности языка, так что, в случае идиоматического использования, будет лучше системного.

оно будет лучше системного только в одном случае - если памяти в системе ровно столько же, сколько её у быдлокодера, который этот код писал и тестировал. Что мы собственно и наблюдаем IRL, глядя на тормозной жабокод.

и видим, что железный стек сливает софтовому в 2 раза

Не совсем так. Точнее, вот так:

        HARD    SOFT    SOFT2

-O2     8,03s   5,46s   3,25

-O3     4,12s   5,92s   3,25

SOFT2 это твоя версия в которой массив накатывается каждый раз на стеке, а не на куче (+ небольшая обфускация):

#include <stdio.h>

const unsigned size = 1 << 17;
unsigned count = 1;

unsigned f(unsigned a)
{
    unsigned s[size], i, res;
    for (i = 0; ++count % size != 0; s[i++] = a, a += a << 2);
    for (res = 1; i > 0; --i, res = s[i] + (res ^ s[i] ^ ((s[i] & 7) << 3)));
    return res;
}

int main()
{
    const unsigned n = 9000;
    unsigned sum = 1;
    for (; count < size * n; sum += f(sum));
    printf("sum = %u\n", sum);
}

Короче, непонятно что там делает gcc - всё равно нужно читать ассемблер и выявлять из-за чего именно возникает разница (всё что угодно может быть - разница в самих инструкциях (то есть прямо по тактам), в попадании в кеш, в выравнивании, в особенности работы виртуальной памяти, разнице между bss / stack / heap и т.п.).