태그 보관물: heap

heap

더 빠름 : 스택 할당 또는 힙 할당 들릴지 모르지만 이것은 내가 일하는

이 질문은 초등하게 들릴지 모르지만 이것은 내가 일하는 다른 개발자와의 토론입니다.

나는 힙을 할당하는 대신 가능한 한 할당 할당을 처리하려고했습니다. 그는 나에게 말을 걸고 어깨 너머로보고 있었고, 그들이 같은 성능으로 현명하기 때문에 필요하지 않다고 말했다.

필자는 항상 스택을 늘리는 것이 일정한 시간이라는 인상을 받았으며 힙 할당의 성능은 할당 (적절한 크기의 구멍 찾기)과 할당 해제 (단편화를위한 구멍 축소)에 대한 힙의 현재 복잡성에 달려 있습니다. 많은 표준 라이브러리 구현은 실수하지 않으면 삭제 중에이 작업을 수행하는 데 시간이 걸립니다.

이것은 아마도 컴파일러에 매우 의존적 일 것입니다. 이 프로젝트에서는 특히 PPC 아키텍처에 Metrowerks 컴파일러를 사용하고 있습니다. 이 조합에 대한 통찰력이 가장 도움이되지만 일반적으로 GCC 및 MSVC ++에 대해서는 어떤 경우가 있습니까? 힙 할당이 스택 할당만큼 성능이 좋지 않습니까? 차이가 없습니까? 또는 차이가 너무 작아서 무의미한 미세 최적화가됩니다.



답변

실제로 스택 할당은 스택 포인터를 이동하기 때문에 스택 할당이 훨씬 빠릅니다. 메모리 풀을 사용하면 힙 할당에서 비슷한 성능을 얻을 수 있지만 약간의 복잡성과 자체 두통이 발생합니다.

또한 스택 대 힙은 성능 고려 사항 일뿐만 아니라; 또한 예상되는 개체 수명에 대해 많은 정보를 제공합니다.


답변

스택이 훨씬 빠릅니다. 문자 그대로 대부분의 아키텍처, 예를 들어 x86에서 단일 명령어 만 사용합니다.

sub esp, 0x10

(이것은 스택 포인터를 0x10 바이트 아래로 이동시켜 변수에 의해 사용되도록 해당 바이트를 “할당”합니다.)

물론 스택 할당을 과도하게 사용하거나 재귀를 시도하면 신속하게 알 수 있으므로 스택 크기는 매우 유한합니다.

또한 프로파일 링을 통해 입증 할 수없는 코드 성능을 최적화 할 이유가 거의 없습니다. “조기 최적화”는 종종 가치보다 더 많은 문제를 일으 킵니다.

내 경험 법칙 : 컴파일 타임에 일부 데이터가 필요하다는 것을 알고 있으며 크기가 수백 바이트 미만이면 스택 할당합니다. 그렇지 않으면 힙 할당합니다.


답변

솔직히 성능을 비교하는 프로그램을 작성하는 것은 쉽지 않습니다.

#include <ctime>
#include <iostream>

namespace {
    class empty { }; // even empty classes take up 1 byte of space, minimum
}

int main()
{
    std::clock_t start = std::clock();
    for (int i = 0; i < 100000; ++i)
        empty e;
    std::clock_t duration = std::clock() - start;
    std::cout << "stack allocation took " << duration << " clock ticks\n";
    start = std::clock();
    for (int i = 0; i < 100000; ++i) {
        empty* e = new empty;
        delete e;
    };
    duration = std::clock() - start;
    std::cout << "heap allocation took " << duration << " clock ticks\n";
}

어리석은 일관성은 작은 마음의 홉 고블린 이라고합니다 . 분명히 컴파일러를 최적화하는 것은 많은 프로그래머의 마음에 얽힌 것입니다. 이 토론은 답변의 맨 아래에 있었지만 사람들은 분명히 그 내용을 읽지 않아도되므로 이미 대답 한 질문을 피하기 위해 여기로 이동하고 있습니다.

최적화 컴파일러는이 코드가 아무 작업도하지 않으며 모든 것을 최적화 할 수 있습니다. 그런 일을하는 것은 옵티마이 저의 일이며, 옵티 마이저와 싸우는 것은 어리석은 일입니다.

현재 사용중인 모든 옵티 마이저를 속일 수있는 미래의 방법이 없기 때문에 최적화가 해제 된 상태 에서이 코드를 컴파일하는 것이 좋습니다.

옵티 마이저를 켜고 싸우는 것에 대해 불평하는 사람은 누구나 공개 조롱을 받아야합니다.

나노초 정밀도에 관심이 있다면 사용하지 않을 것입니다 std::clock() 입니다. 박사 학위 논문으로 결과를 게시하고 싶다면 이것에 대해 더 많이 다루고 GCC, Tendra / Ten15, LLVM, Watcom, Borland, Visual C ++, Digital Mars, ICC 및 기타 컴파일러를 비교할 것입니다. 실제로 힙 할당은 스택 할당보다 수백 배 더 오래 걸리며 더 이상 질문을 조사하는 데 유용한 정보가 없습니다.

최적화 프로그램은 테스트중인 코드를 제거하는 사명을 가지고 있습니다. 옵티 마이저에게 실행을 지시 한 다음 옵티 마이저를 실제로 최적화하지 않도록 속이려 할 이유가 없습니다. 그러나 그렇게하는 데 가치가 있으면 다음 중 하나 이상을 수행합니다.

  1. 에 데이터 멤버를 추가 empty하고 루프에서 해당 데이터 멤버에 액세스하십시오. 그러나 데이터 멤버에서만 읽은 경우 옵티마이 저는 일정한 폴딩을 수행하고 루프를 제거 할 수 있습니다. 데이터 멤버에만 쓰면 옵티마이 저는 루프의 마지막 반복을 제외한 모든 것을 건너 뛸 수 있습니다. 또한이 질문은 “스택 할당 및 데이터 액세스 대 힙 할당 및 데이터 액세스”가 아닙니다.

  2. 선언 e volatile, 하지만 volatile종종 잘못 컴파일 (PDF)를.

  3. e루프 내부 의 주소를 가져와 extern다른 파일에 선언 되고 정의 된 변수에 할당하십시오 . 그러나이 경우에도 컴파일러는 적어도 스택에서 e항상 동일한 메모리 주소에 할당 된 다음 위의 (1)과 같이 일정한 접기를 수행 한다는 것을 알 수 있습니다. 루프의 모든 반복을 얻지 만 객체는 실제로 할당되지 않습니다.

명백히,이 테스트는 할당과 할당 해제를 측정한다는 점에서 결함이 있으며, 원래 질문은 할당 해제에 대해 묻지 않았습니다. 물론 스택에 할당 된 변수는 해당 범위의 끝에서 자동으로 할당이 해제되므로 delete(1) 숫자를 기울이지 않습니다 (스택 할당 해제는 스택 할당에 대한 숫자에 포함되므로 힙 할당 해제를 측정하는 것은 공정합니다). 2) delete시간 측정을 한 후에 새로운 포인터에 대한 참조를 유지하고 호출하지 않는 한 꽤 나쁜 메모리 누수가 발생 합니다.

내 컴퓨터에서 Windows에서 g ++ 3.4.4를 사용하면 100000 미만의 할당에 대해 스택 및 힙 할당 모두에 대해 “0 클럭 틱”이 표시되고 스택 할당 및 “15 클럭 틱에 대해”0 클럭 틱 “이 표시됩니다. 힙 할당의 경우 ” 10,000,000 개의 할당을 측정 할 때 스택 할당에는 31 개의 클럭 틱이, 힙 할당에는 1562 개의 클럭 틱이 필요합니다.


예, 최적화 컴파일러는 빈 객체를 생성하지 않아도됩니다. 올바르게 이해하면 전체 첫 번째 루프를 제거 할 수도 있습니다. 10,000,000 스택 할당으로 반복을 부딪쳤을 때 31 클럭 틱이 걸렸고 힙 할당에는 1562 클럭 틱이 걸렸습니다. g ++에게 실행 파일을 최적화하도록 지시하지 않으면 g ++이 생성자를 생략하지 않았다고 말하는 것이 안전하다고 생각합니다.


필자가 작성한 이후 몇 년 동안 Stack Overflow는 최적화 된 빌드에서 성능을 게시하는 것이 좋습니다. 일반적으로 이것이 맞다고 생각합니다. 그러나 실제로 코드 최적화를 원하지 않는 경우 컴파일러에게 코드 최적화를 요청하는 것은 어리석은 일이라고 생각합니다. 그것은 주차 대행에 대한 추가 비용을 지불하는 것과 매우 유사하지만 열쇠를 넘기는 것을 거부합니다. 이 특별한 경우에는 최적화 프로그램을 실행하고 싶지 않습니다.

약간 수정 된 벤치 마크 버전을 사용하여 (원본 프로그램이 루프를 통해 매번 스택에 무언가를 할당하지 않은 유효 지점을 해결하기 위해) 최적화없이 컴파일하지만 라이브러리를 릴리스하기 위해 링크 (유효한 지점을 해결하기 위해) 디버그 라이브러리에 연결하여 발생하는 속도 저하를 포함시키지 않으려는 경우)

#include <cstdio>
#include <chrono>

namespace {
    void on_stack()
    {
        int i;
    }

    void on_heap()
    {
        int* i = new int;
        delete i;
    }
}

int main()
{
    auto begin = std::chrono::system_clock::now();
    for (int i = 0; i < 1000000000; ++i)
        on_stack();
    auto end = std::chrono::system_clock::now();

    std::printf("on_stack took %f seconds\n", std::chrono::duration<double>(end - begin).count());

    begin = std::chrono::system_clock::now();
    for (int i = 0; i < 1000000000; ++i)
        on_heap();
    end = std::chrono::system_clock::now();

    std::printf("on_heap took %f seconds\n", std::chrono::duration<double>(end - begin).count());
    return 0;
}

표시합니다 :

on_stack took 2.070003 seconds
on_heap took 57.980081 seconds

커맨드 라인으로 컴파일 할 때 내 시스템에서 cl foo.cc /Od /MT /EHsc.

최적화되지 않은 빌드를 얻는 방법에 동의하지 않을 수 있습니다. 괜찮습니다. 원하는만큼 벤치 마크를 자유롭게 수정하십시오. 최적화를 켜면 다음과 같은 결과가 나타납니다.

on_stack took 0.000000 seconds
on_heap took 51.608723 seconds

스택 할당이 실제로 즉각적이기 때문이 아니라 절반 정도의 컴파일러가 on_stack유용한 것을 수행하지 않고 최적화 할 수 있다는 것을 알 수 있기 때문 입니다. 내 Linux 랩톱의 GCC는 on_heap유용한 기능을 수행하지 않으며이를 최적화합니다.

on_stack took 0.000003 seconds
on_heap took 0.000002 seconds

답변

다른 멀티 코어 시스템에도 적용 할 수있는 Xbox 360 크세논 프로세서의 스택 대 힙 할당에 대해 흥미로운 점은 힙에 할당하면 중요 섹션이 다른 모든 코어를 중지하도록 할당되어 할당자가 수행 할 수 있다는 것입니다. 충돌하지 않습니다. 따라서 타이트한 루프에서 스택 할당은 실속을 막기 때문에 고정 크기의 배열로가는 길이었습니다.

멀티 코어 / 멀티 프로세스를 코딩하는 경우 고려할 또 다른 속도 향상 일 수 있습니다. 스택 할당은 범위 지정된 기능을 실행하는 코어에서만 볼 수 있으며 다른 코어 / CPU에는 영향을 미치지 않습니다.


답변

성능이 뛰어난 특정 크기의 객체에 대해 특수 힙 할당자를 작성할 수 있습니다. 그러나 일반적인 힙 할당자는 특히 성능이 좋지 않습니다.

또한 개체의 예상 수명에 대해 Torbjörn Gyllebring에 동의합니다. 좋은 지적!


답변

스택 할당과 힙 할당이 일반적으로 호환되지 않는다고 생각합니다. 또한 두 가지 성능 모두 일반적인 용도로 충분하기를 바랍니다.

나는 작은 아이템들 중 어느 것이 든 할당 범위에 더 적합한 것을 강력히 추천합니다. 큰 품목의 경우 힙이 필요할 수 있습니다.

여러 스레드가있는 32 비트 운영 체제에서는 주소 공간을 조각해야하며 조만간 하나의 스레드 스택이 다른 스레드 스택으로 실행되기 때문에 스택이 다소 제한적입니다 (일반적으로 최소한 몇 mb 이상임). 단일 스레드 시스템 (Linux glibc 단일 스레드)에서는 스택이 커지고 커질 수 있기 때문에 제한이 훨씬 적습니다.

64 비트 운영 체제에는 스레드 스택을 상당히 크게 만들 수있는 충분한 주소 공간이 있습니다.


답변

일반적으로 스택 할당은 스택 포인터 레지스터에서 빼기로 구성됩니다. 힙을 검색하는 것보다 훨씬 빠릅니다.

때때로 스택 할당에는 가상 메모리 페이지를 추가해야합니다. 0으로 된 메모리의 새 페이지를 추가 할 때는 디스크에서 페이지를 읽을 필요가 없으므로 일반적으로 힙을 검색하는 것 (특히 힙의 일부가 페이지 아웃 된 경우)보다 훨씬 빠릅니다. 드문 경우이지만 이러한 예제를 구성 할 수 있습니다. 이미 RAM에있는 힙 부분에서 충분한 공간을 사용할 수 있지만 스택에 새 페이지를 할당하면 다른 페이지가 작성 될 때까지 기다려야합니다. 디스크에. 드문 상황에서 힙이 더 빠릅니다.