5

我正在分配 2 个相同大小的数组,一个在堆栈上,一个在堆上,然后通过简单的分配对它们进行迭代。

可执行文件被编译为为主线程堆栈分配 40mb。

此代码仅经过测试,可在带有 /STACK:41943040 链接器标记的 vc++ 中编译。

#include "stdafx.h"
#include <string>
#include <iostream>
#include <malloc.h>
#include <windows.h>
#include <ctime>

using namespace std;

size_t stackavail()
{
    static unsigned StackPtr;   // top of stack ptr
    __asm mov [StackPtr],esp    // mov pointer to top of stack
    static MEMORY_BASIC_INFORMATION mbi;            // page range
    VirtualQuery((PVOID)StackPtr,&mbi,sizeof(mbi)); // get range
    return StackPtr-(unsigned)mbi.AllocationBase;   // subtract from top (stack grows downward on win)
}

int _tmain(int argc, _TCHAR* argv[])
{
    string input;

    cout << "Allocating 22mb on stack." << endl;
    unsigned int start = clock();
    char eathalfastack[23068672]; // approx 22mb
    auto length = sizeof(eathalfastack)/sizeof(char);
    cout << "Time taken in ms: " << clock()-start << endl;

    cout << "Setting through array." << endl;
    start = clock();
    for( int i = 0; i < length; i++ ){
        eathalfastack[i] = i;
    }
    cout << "Time taken in ms: " << clock()-start << endl;
    cout << "Free stack space: " << stackavail() << endl;


    cout << "Allocating 22mb on heap." << endl;
    start = clock();
    // auto* heaparr = new int[23068672]; // corrected
    auto* heaparr = new byte[23068672];
    cout << "Time taken in ms: " << clock()-start << endl;

    start = clock();
    cout << "Setting through array." << endl;
    for( int i = 0; i < length; i++ ){
        heaparr[i] = i;
    }
    cout << "Time taken in ms: " << clock()-start << endl;

    delete[] heaparr;
    getline(cin, input);
}

输出是这样的:

    Allocating 22mb on stack.
    Time taken in ms: 0
    Setting through array.
    Time taken in ms: 45
    Free stack space: 18872076
    Allocating 22mb on heap.
    Time taken in ms: 20
    Setting through array.
    Time taken in ms: 35

为什么堆栈数组的迭代比堆上的相同事物慢?

编辑: nneonneo 咳出我的错误

现在输出是相同的:

    Allocating 22mb on stack.
    Time taken in ms: 0
    Setting through array.
    Time taken in ms: 42
    Free stack space: 18871952
    Allocating 22mb on heap.
    Time taken in ms: 4
    Setting through array.
    Time taken in ms: 41

根据 Öö Tiib 的回答发布版本如下:

    Allocating 22mb on stack.
    Time taken in ms: 0
    Setting through array.
    Time taken in ms: 5
    Free stack space: 18873508
    Allocating 22mb on heap.
    Time taken in ms: 0
    Setting through array.
    Time taken in ms: 10
4

3 回答 3

9

您的数组大小不同;sizeof(char[23068672]) != sizeof(int[23068672]), 元素的类型不同。

于 2012-10-16T04:10:22.103 回答
1

你的电脑出了点问题,在我的老奔腾 4 上,分配这种基于堆栈的字符数组需要 15 毫秒。您是否尝试过调试版本或其他东西?

于 2012-10-16T04:32:27.150 回答
0

您的问题有两个部分:

  1. 在堆栈与堆上分配空间
  2. 访问堆栈上的内存位置与全局可见

分配空间

首先,让我们看看在堆栈上分配空间。我们所知道的堆栈在 x86 架构上向下增长。因此,为了在堆栈上分配空间,您所要做的就是减少堆栈指针。只有一条汇编指令(dec sp,#amount)。该汇编指令始终出现在函数的序言中(函数设置代码)。因此,据我所知,在堆栈上分配空间一定不会花费任何时间。在堆栈上分配空间的成本 = (递减 sp 操作)。在现代超标量机器上,该指令的执行将与其他指令重叠。

另一方面,在堆上分配空间需要对 new/malloc 的库调用。库调用首先检查堆上是否有空间。如果是,那么它将只返回一个指向第一个可用地址的指针。如果堆栈上没有可用空间,它将使用 brk 系统调用请求内核修改附加页的页表条目。系统调用是一项昂贵的操作。它会导致管道刷新,TLB污染等。因此,在堆上分配空间的成本=(函数调用+空间计算+(brk系统调用)?)。当然,在堆上分配空间似乎比堆栈慢一个数量级。

访问元素 x86 ISA 的寻址模式允许使用直接寻址模式 (temp=mem[addr]) 对内存操作数进行寻址以访问全局变量,而堆栈上的变量通常使用索引寻址模式访问。(temp=mem[stack-pointer+offset-on-stack])。我的假设是两个内存操作数应该花费几乎相同的时间,但是,直接寻址模式似乎肯定比索引寻址模式快。关于数组的内存访问,我们有两个操作数可以访问任何元素——数组的基地址和索引变量。当我们访问堆栈上的数组时,我们添加了一个操作数 - 堆栈指针。x86 寻址模式提供了此类地址 - base+scale*index+offset 。所以,好的堆栈数组元素访问:temp=mem[sp+base-address+iterator*element-size] 和堆数组访问:temp=mem[base-address+iterator*element-size]。显然,堆栈访问必须比数组访问更昂贵。

现在,回到迭代的一般情况,如果堆栈的迭代速度较慢,这意味着寻址模式可能(我不完全确定)瓶颈,如果分配空间是瓶颈,则系统调用可能是瓶颈。

于 2012-10-16T04:54:47.137 回答