Programming DIY / Программирование — это просто!: решето эратосфена

Показаны сообщения с ярлыком решето эратосфена. Показать все сообщения

пятница, 4 марта 2011 г.

Кто из компиляторов быстрее - cl, lcc или tcc

Люблю делать всякие сравнения компиляторов.

Сегодня на ринге Студия 2010, lcc и tcc. Все три я активно использую под Windows для языка С.

Сравнивать будем на любимом решете Эратосфена (erato-c-int.c):

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <string.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;

  long sqrt_n = sqrt(n) + 1;

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

  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):

SRC=erato-c-int
N=100000000

all:  build run

build: build-cl build-lcc build-tcc

run: run-cl run-lcc run-tcc

build-cl:
  @cl /nologo /O2 -Fe$(SRC)-cl.exe $(SRC).c

run-cl:
  @echo ---
  -@cl 2>&1 | findstr Compiler
  @ntimer.exe $(SRC)-cl.exe $(N) | findstr ETime

build-lcc:
  @c:\lcc\bin\lcc -O2 -o $(SRC)-lcc.obj $(SRC).c
  @c:\lcc\bin\lcclnk -o $(SRC)-lcc.exe $(SRC)-lcc.obj

run-lcc:
  @echo ---
  @c:\lcc\bin\lcc -v
  @ntimer.exe $(SRC)-lcc.exe $(N) | findstr ETime

build-tcc:
  @c:\tcc\tcc -O2 -o $(SRC)-tcc.exe $(SRC).c

run-tcc:
  @echo ---
  @c:\tcc\tcc -v
  @ntimer.exe $(SRC)-tcc.exe $(N) | findstr ETime

Погнали:

---
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 16.00.30319.01 for 80x86
ETime(   0:00:04.374 ) UTime(   0:00:04.196 ) KTime(   0:00:00.124 )
---
Logiciels/Informatique lcc-win32 version 3.8. Compilation date: Jan 29 2011 11:51:05
ETime(   0:00:04.415 ) UTime(   0:00:04.102 ) KTime(   0:00:00.202 )
---
tcc version 0.9.25
ETime(   0:00:04.944 ) UTime(   0:00:04.492 ) KTime(   0:00:00.280 )

Вывод не особо захватывающий. Все выступили примерно одинаково.

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

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

Кто быстрее: vector<bool> или vector<int>

суббота, 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: После экспериментов в комментариях выходит, что и на С, и на С++ можно добиться равного быстродействия, если использовать битовые поля. Просто в С++ это синтаксически проще, но не более того.

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

Кто быстрее: vector<bool> или vector<int>

воскресенье, 1 февраля 2009 г.

Кто быстрее: vector<bool> или vector<int>

Я много раз слышал, что стандартный класс std::vector, специализированный для хранения типа bool, то есть std::vector<bool>, который по задумке создателей должен работать заметно быстрее своего смыслового аналога std::vector<int>, на самом деле нет так и хорош. Но тут, как говориться, бабушка на двое сказала, так как с одной стороны операция с базовым типом процессора int обычно является почти самой быстрой атомарной операцией, а другой стороны тип bool может быть упакован в тот же "быстрый" int пачкой по 32 или 64 штуки за раз, и можно оперировать сразу группой значений. В общем, целое поле для оптимизации.

Я люблю все проверять лично, так что привожу результаты своей проверки.

Итак, объект — программа нахождения простых чисел "Решето Эратосфена". Классический алгоритм для проверки на вшивость всяких оптимизаторов. На оригинальность и оптимальность кода не претендую.

Файл era.cpp:

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

int main(int argc, char* argv[]) {
  // Получаем предельное значение эксперимента из командной
  // строки. По умолчанию - 100. Это основной, влияющий
  // на время работы алгоритма, параметр.
  long n = argc > 1 ? std::atoi(argv[1]) : 100;
  // Корень квадратный из максимума, округленный до большего
  // целого.
  long sqrt_n = static_cast<long>(std::sqrt(static_cast<double>(n))) + 1;

  // Массив-вектор для хранения значений. Это центр внимания нашего
  // эксперимента. Макрос TYPE задает тип элементов вектора и должен
  // быть задан в опциях при компиляции: -DTYPE=int или
  // -DTYPE=bool соответственно.
  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;
}

Эксперимент я проводил на ноутбуке с процессором Core 2 1ГГц. Для конкретно этой машины я выбрал предел поиска в 10000000. При этом значении времена работы программы с одной стороны небольшие (удобно для повторения замеров), но другой стороны — весьма показательные.

Теперь компилятор. В забеге принимали участие:

GNU g++ 3.4.4 (cygwin)
Borland/Codegear bcc32.exe 5.93 (Codegear Studio 2007)
Microsoft cl.exe 14.00 (Visual Studio 2005)
Microsoft cl.exe 15.00 (Visual Studio 2008)

Операционная система Windows XP SP3.

Каждый компилятор получил свои максимально полные опции оптимизации на скорость, так как глупо говорить об эффективности программы на С++ без включенной оптимизации компилятора (ни тебе inline-функций, ни использования регистров процессора и т.д.) Но для целостности картины результаты без оптимизации тоже приведены (и будет позже ясно почему).

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

Файл build.cmd:

bcc32 -DTYPE=bool -eera-bcc32-bool.exe era.cpp
bcc32 -DTYPE=int -eera-bcc32-int.exe era.cpp
bcc32 -O2 -DTYPE=bool -eera-bcc32-bool-opt.exe era.cpp
bcc32 -O2 -DTYPE=int -eera-bcc32-int-opt.exe era.cpp

g++ -DTYPE=bool -o era-g++-bool.exe era.cpp
g++ -DTYPE=int -o era-g++-int.exe era.cpp
g++ -O3 -funroll-all-loops -fomit-frame-pointer -mtune=nocona -DTYPE=bool -o era-g++-bool-opt.exe era.cpp
g++ -O3 -funroll-all-loops -fomit-frame-pointer -mtune=nocona -DTYPE=int -o era-g++-int-opt.exe era.cpp

call cl2008.cmd
cl /EHsc /DTYPE=bool /Feera-cl2008-bool.exe era.cpp
cl /EHsc /DTYPE=int /Feera-cl2008-int.exe era.cpp
cl /EHsc /arch:SSE2 /O2 -DTYPE=bool /Feera-cl2008-bool-opt.exe era.cpp
cl /EHsc /arch:SSE2 /O2 -DTYPE=int /Feera-cl2008-int-opt.exe era.cpp

call cl2005.cmd
cl /EHsc /DTYPE=bool /Feera-cl2005-bool.exe era.cpp
cl /EHsc /DTYPE=int /Feera-cl2005-int.exe era.cpp
cl /EHsc /arch:SSE2 /O2 -DTYPE=bool /Feera-cl2005-bool-opt.exe era.cpp
cl /EHsc /arch:SSE2 /O2 -DTYPE=int /Feera-cl2005-int-opt.exe era.cpp

При скрипты cl2005.cmd и cl2008.cmd я уже писал.

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

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

Файл run.cmd:

ntimer -1 era-cl2005-bool.exe 10000000
ntimer -1 era-cl2005-int.exe 10000000
ntimer -1 era-cl2005-bool-opt.exe 10000000
ntimer -1 era-cl2005-int-opt.exe 10000000

ntimer -1 era-cl2008-bool.exe 10000000
ntimer -1 era-cl2008-int.exe 10000000
ntimer -1 era-cl2008-bool-opt.exe 10000000
ntimer -1 era-cl2008-int-opt.exe 10000000

ntimer -1 era-bcc32-bool.exe 10000000
ntimer -1 era-bcc32-int.exe 10000000
ntimer -1 era-bcc32-bool-opt.exe 10000000
ntimer -1 era-bcc32-int-opt.exe 10000000

ntimer -1 era-g++-bool.exe 10000000
ntimer -1 era-g++-int.exe 10000000
ntimer -1 era-g++-bool-opt.exe 10000000
ntimer -1 era-g++-int-opt.exe 10000000

Для измерения времени работы я использовал программу ntimer. Ее нужно скачать, распаковать и положить ntimer.exe в текущий каталог. Будучи запущенной с ключом "-1" эта программа печатает времена в одну строку. Нас интересует самое первое печатаемой ей время.

Барабанная дробь! Запускаем...

Таблица с временами работы (по порядку):

Компилятор	Версия	Тип элемента	Оптимизация	Время (сек.)
Visual Studio 2005	14.00	bool	Выкл	23.75
Visual Studio 2005	14.00	int	Выкл	1.75
Visual Studio 2005	14.00	bool	Вкл	1.171
Visual Studio 2005	14.00	int	Вкл	1.312
Visual Studio 2008	15.00	bool	Выкл	23.062
Visual Studio 2008	15.00	int	Выкл	1.703
Visual Studio 2008	14.00	bool	Вкл	2.390
Visual Studio 2008	14.00	int	Вкл	1.312
Borland/Codegear 2007	5.93	bool	Выкл	8.375
Borland/Codegear 2007	5.93	int	Выкл	1.296
Borland/Codegear 2007	5.93	bool	Вкл	8.156
Borland/Codegear 2007	5.93	int	Вкл	1.328
gcc (cygwin)	3.4.4	bool	Выкл	4.640
gcc (cygwin)	3.4.4	int	Выкл	3.109
gcc (cygwin)	3.4.4	bool	Вкл	0.984
gcc (cygwin)	3.4.4	int	Вкл	1.343

А теперь в отсортированном виде по возрастанию времени:

Компилятор	Версия	Тип элемента	Оптимизация	Время (сек.)
gcc (cygwin)	3.4.4	bool	Вкл	0.984
Visual Studio 2005	14.00	bool	Вкл	1.171
Borland/Codegear 2007	5.93	int	Выкл	1.296
Visual Studio 2005	14.00	int	Вкл	1.312
Visual Studio 2008	14.00	int	Вкл	1.312
Borland/Codegear 2007	5.93	int	Вкл	1.328
gcc (cygwin)	3.4.4	int	Вкл	1.343
Visual Studio 2008	15.00	int	Выкл	1.703
Visual Studio 2005	14.00	int	Выкл	1.75
Visual Studio 2008	14.00	bool	Вкл	2.390
gcc (cygwin)	3.4.4	int	Выкл	3.109
gcc (cygwin)	3.4.4	bool	Выкл	4.640
Borland/Codegear 2007	5.93	bool	Вкл	8.156
Borland/Codegear 2007	5.93	bool	Выкл	8.375
Visual Studio 2008	15.00	bool	Выкл	23.062
Visual Studio 2005	14.00	bool	Выкл	23.75

Итак, на первом месте gcc в режиме bool с оптимизацией. На втором месте Visual Studio снова в режиме bool и оптимизацией. Интересно выступил борландовый компилятор, получив третье место, причем без оптимизации. Так как априори борландовый bcc32.exe считается весьма посредственным компилятором в плане качества кода и оптимизатора, то полученное им третье место весьма и весьма странно.

Конечно, пытливый читатель сразу заметит, что я как-то очень лихо проскочил один очень важный вопрос, а именно — версию STL. Не могу поручиться, что каждый из этих компиляторов поставляется с абсолютно неизменной и, как принято считать, "стандартной" версией этой библиотеки. Каждая фирма что-то меняет всегда под себя.

В итоге, я так и не получил однозначного ответа на изначальный вопрос — пользоваться ли std::vector вместо std::vector или нет. Слишком много побочных факторов. Поэтому я бы посоветовал, если вы встали перед такой же дилеммой в вашем проекте, провести эксперимент на месте с вашим конкретным компилятором, вашей версией STL, на вашей конкретной платформе и т.д., то есть с учетом всех ваших факторов. Можно использовать приведенные мной программы и скрипты. Если у вас будут интересные и неоднозначные результаты, пишите.

Programming DIY / Программирование — это просто!

пятница, 4 марта 2011 г.

Кто из компиляторов быстрее - cl, lcc или tcc

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

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

воскресенье, 1 февраля 2009 г.

Кто быстрее: vector<bool> или vector<int>

Поиск по этому блогу

Просмотры за последний месяц

Это Я

Motto / Девиз этого блога

Настоящий компьютер

Мои проекты

Постоянные читатели

Erlang

Работа и интервью

Библиотека для C++

Статьи

Спортивное программирование

Приемчики

Эксперименты

Книги

Инструменты

Архив блога

Ярлыки

Друзья

На всякий случай

Programming DIY / Программирование — это просто!

пятница, 4 марта 2011 г.

Кто из компиляторов быстрее - cl, lcc или tcc

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

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

воскресенье, 1 февраля 2009 г.

Кто быстрее: vector<bool> или vector<int>

Поиск по этому блогу

Просмотры за последний месяц

Это Я

Motto / Девиз этого блога

Настоящий компьютер

Мои проекты

Постоянные читатели

Erlang

Работа и интервью

Библиотека для C++

Статьи

Спортивное программирование

Приемчики

Эксперименты

Книги

Инструменты

Архив блога

RSS

Ярлыки

Друзья

На всякий случай

пятница, 4 марта 2011 г.

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

воскресенье, 1 февраля 2009 г.