*** ВНИМАНИЕ: Блог переехал на другой адрес - demin.ws ***

суббота, 6 марта 2010 г.

Решето Эратосфена - кто быстрее: Go, C или C++?

Go очень интересный язык. Компиляция в native-code (никаких виртуальных машин, JIT-компиляций и т.д.), при этом автоматическая сборка мусора и встроенная поддержка многопоточности, объектно-ориентированная модель, и в довершение всего - очень быстрая компиляция.

Лично я обычно на новых для меня языках люблю писать Решето Эратосфена в качестве "Hello, world!".

Моя версия на Go выгдядит так:

Файл erato-go-bool.go:

package main

import "fmt"
import "math"
import "flag"

func main() {
    var N int
    flag.IntVar(&N, "N", 100, "")
    flag.Parse()

    fmt.Printf("%d\n", N)

    seive := make([]bool, N)
  
    limit := int(math.Sqrt(float64(N))) + 1

    for i := 2; i < limit; i++ {
        if !seive[i] {
            for j := i * i; j < N; j += i  {
                seive[j] = true
            }
        }
    }

    count := 0
    for i := 2; i < N; i++ {
        if !seive[i] {
            count++
        }
    }
    fmt.Printf("%d\n", count)
}

И первый вопрос, который приходит в голову - а насколько это быстро работает?

Некоторое время назад я уже писал, как использовал решето для тестирования STL'евского контейнера std::vector на разных компиляторах.

Сейчас я провел похожее сравнение между Go, C++ и C.

Итак, первый кандитат - версия на Go с использованием типа bool (см. выше). Второй - тоже на Go, но с использованием типа int.

Файл erato-go-int.go:

package main

import "fmt"
import "math"
import "flag"

func main() {
    var N int
    flag.IntVar(&N, "N", 100, "")
    flag.Parse()

    fmt.Printf("%d\n", N)

    seive := make([]int, N)
  
    limit := int(math.Sqrt(float64(N))) + 1

    for i := 2; i < limit; i++ {
        if seive[i] == 0 {
            for j := i * i; j < N; j += i  {
                seive[j] = 1
            }
        }
    }

    count := 0
    for i := 2; i < N; i++ {
        if seive[i] == 0 {
            count++
        }
    }
    fmt.Printf("%d\n", count)
}

Далее идет версия на С++. Макрос TYPE позволяет переключать программу для нужно типа в контейнере (int или bool):

Файл erato-cxx.cpp:

#include <iostream>
#include <vector>
#include <cstdlib>
#include <cmath>

int main(int argc, char* argv[]) {
  int n = argc > 1 ? std::atoi(argv[1]) : 100;

  std::cout << n << std::endl;

  int sqrt_n = static_cast<int>(std::sqrt(static_cast<double>(n))) + 1;

  std::vector<TYPE> S(n, true);

  for (int i = 2; i < sqrt_n; ++i)
    if (S[i])
      for (int j = i*i; j < n; j+=i)
        S[j] = false;

  int count = 0;
  for (int i = 2; i < n; ++i)
    if (S[i])
      count++;

  std::cout << count << std::endl;

  return 0;
}

Ну и для полноты картины версия на С:

Файл erator-c-int.c:

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

int main(int argc, char* argv[]) {
  int n = argc > 1 ? atoi(argv[1]) : 100;
  int* S;
  int count;
  int sz = n * sizeof(*S);
  int i, j;

  printf("%d\n", n);

  long sqrt_n = sqrt(n) + 1;

  S = malloc(sz);
  memset(S, 0, sz);

  for (i = 2; i < sqrt_n; ++i)
    if (S[i] == 0)
      for (j = i*i; j < n; j+=i)
        S[j] = 1;

  count = 0;
  for (i = 2; i < n; ++i)
    if (S[i] == 0)
      count++;

  printf("%d\n", count);

  free(S);
  return 0;
}

Ну и Makefile для удобного запуска.

Файл Makefile:

.SILENT: 

all:
        $(MAKE) run 2>&1 | tee log
        $(MAKE) parse-log

run: go-bool go-int cxx-int cxx-bool c-int

N ?= 100000000

go-bool:
        echo $@
        6g erato-$@.go
        6l -o erato-$@ erato-$@.6
        time -p -f %e ./erato-$@ -N=$(N)

go-int:
        echo $@
        6g erato-$@.go
        6l -o erato-$@ erato-$@.6
        time -p -f %e ./erato-$@ -N=$(N)

cxx-bool:
        echo $@
        g++ -o erato-$@ \
                -O3 -funroll-all-loops -fomit-frame-pointer \
                -DTYPE=bool erato-cxx.cpp
        time -p -f %e ./erato-$@ $(N)

cxx-int:
        echo $@
        g++ -o erato-$@ \
                -O3 -funroll-all-loops -fomit-frame-pointer \
                -DTYPE=int erato-cxx.cpp
        time -p -f %e ./erato-$@ $(N)

c-int:
        echo $@
        gcc -o erato-$@ -lm \
                 -O3 -funroll-all-loops -fomit-frame-pointer erato-$@.c
        time -p -f %e ./erato-$@ $(N)

parse-log:
        printf "%10s %10s %8s %5s\n" "Language" N Count Time ; \
        (echo "------------------------------------") ; \
        while read type ; do \
                read N && \
                read count && \
                read time && \
                printf "%10s %10s %8s %5s\n" $$type $$N $$count $$time ; \
        done < log

Запускал я все это под Ubuntu 64-bit. Компилятор C и C++ - gcc 4.4.1. Компилятор Go - последний из официального репозитория.

Запускаем:

make N=100000000

и получаем следующее:

 Language           N    Count  Time
------------------------------------
   go-bool  100000000  5761455  3.96
    go-int  100000000  5761455  6.58
   cxx-int  100000000  5761455  6.76
  cxx-bool  100000000  5761455  2.20
     c-int  100000000  5761455  6.47

Получается, что сделал всех С++ с использованием std::vector<bool> для хранения массива. Затем идет Go тоже с типом bool. А С, С++ с std::vector<int> и Go с int'ом примерно равны.

Update: После экспериментов в комментариях выходит, что и на С, и на С++ можно добиться равного быстродействия, если использовать битовые поля. Просто в С++ это синтаксически проще, но не более того.

Посты по теме:

17 комментариев:

  1. Есть идеи почему вариант с C такой медленный?

    ОтветитьУдалить
  2. Почему медленный? Нормальный. Это С++ быстрый. Правильная оптимизация шаблонов (и правильное программирование на шаблонах) в С++ может дать оргомный выйгрыш. В С такой роскоши нет.

    ОтветитьУдалить
  3. а почему на сях вы не используете calloc, а вместо него malloc+memset?

    ОтветитьУдалить
  4. Кстати говоря, что интересно, тип bool на С++ он же однобайтный. Интересно как это влияет.

    ОтветитьУдалить
  5. Почему не calloc? Не знаю, привычка ;-).

    А в плане bool в С++, то тут дело не bool как таковом, а в реализации вектора для bool. Там точно отдельная имплементация, оптимизированная на хранение битов. Причем на разных версиях STL и разных компиляторах может работать с разной скоростью, и не факт, что быстрее. В моем прошлом эксперименте (ссылка в тексте) это было видно.

    ОтветитьУдалить
  6. Я скомпилировал ваш пример для Си на MSVC 2003 для int и unsigned char + использовал calloc. unsigned char работает быстрее. (для 10000000 итераций время int на моей машине 1.36 сек, время unsigned char 1.047сек).

    Не могли бы вы повторить у себя замеры для Си с использованием int / unsigned char, чтобы статистика была полной?

    ОтветитьУдалить
  7. Хм, первый раз скомпилировал без оптимизации. Повторил с максимальной оптимизацией (ключ /Ox). Оба варианта стали быстрее, но unsigned char все равно впереди:

    int 1.109
    unsigned char 0.703

    ОтветитьУдалить
  8. Да, у меня версия на С с unsigned char быстрее:

    go-bool 100000000 5761455 3.98
    go-int 100000000 5761455 6.56
    cxx-int 100000000 5761455 6.49
    cxx-bool 100000000 5761455 2.25
    c-int 100000000 5761455 7.55
    c-uchar 100000000 5761455 3.90

    ОтветитьУдалить
  9. Могу предположить, что в Go модели хранения в памяти близки к С, что объясняет схожесть замеров для int и unsigned char.

    ОтветитьУдалить
  10. Я переделал сишный вариант на использование массива битов и получил существенное ускорение. Таки да, дело не в скорости плюсов, а в выбранном типе памяти. Я так думаю, что существенный прирост скорости получается за счет того, что в случае с битовым массивом большая часть элементов такого массива остается в кеше поцессора. Как следствие -- имеем меньшие задержки при обращениях к реальной памяти.

    ОтветитьУдалить
  11. Собственно код программы использующей битовый массив (к счастью у меня уже была готовая реализация битового массива для си):

    #include
    #include
    #include
    #include


    #define BV(x) (1< 1 ? atoi(argv[1]) : 100;
    BitArray *S;
    int count;
    int sz = n * sizeof(*S) / 32 + 1;
    int i, j;
    long sqrt_n;

    printf("n = %d\n", n);

    sqrt_n = sqrt(n) + 1;

    S = calloc(1, sz);

    for (i = 2; i < sqrt_n; ++i)
    if (!bit_get(S, i))
    for (j = i*i; j < n; j+=i)
    bit_on(S, j);

    count = 0;
    for (i = 2; i < n; ++i)
    if (!bit_get(S, i))
    count++;

    printf("%d\n", count);

    free(S);
    return 0;
    }

    ОтветитьУдалить
  12. Поскольку вставить код в комментарии нормально не получается, то я закинул его на Launchpad:

    bzr branch lp:~bialix/+junk/erato-c

    ОтветитьУдалить
  13. Круто! Скомпилил ваш вариант. Получилось даже чуть быстрее С++:

    Languange N Count Time
    ------------------------------------
    go-bool 100000000 5761455 3.90
    go-int 100000000 5761455 7.10
    cxx-int 100000000 5761455 6.47
    cxx-bool 100000000 5761455 2.20
    c-int 100000000 5761455 6.54
    c-uchar 100000000 5761455 3.74
    c-bits 100000000 5761455 2.12

    Значит дело действительно просто в попадании в кеш.

    ОтветитьУдалить
  14. Думаю если вы проделаете замеры для си с битовым массивом, а также для go с битовым массивом, то результаты будут похожи на C++ с битовым вектором.

    Итого: каким будет правильный ответ на вопрос в заголовке? они все примерно равны? но в плюсах есть готовая либа сложных алгоритмов. плюсы остаются в плюсах, а готовые либы рулят.

    ОтветитьУдалить
  15. Факт. Обновил резюме поста. Выходит, что в плане скорости побеждает не язык, а архитектура.

    ОтветитьУдалить
  16. Кстати, недавно наткнулся на автоматический "сравниватель" производительности и используемой памяти программ на разных языках


    Например, C++ vs Go:
    http://shootout.alioth.debian.org/u64q/benchmark.php?test=all&lang=gpp&lang2=go

    ОтветитьУдалить