nlothik (nlothik) wrote,
nlothik
nlothik

Ну, апологеты Си, Гитлер вам капут!

Щас точки над Ё расставлять буду.

Как правильно измерять производительность программы, написанной на каком-то языке программирования? Ну, для начала, взять нормальный, хорошо изученный алгоритм. Например, любимая многими сортировка пузырьком (bubble sort) не годится. Почему? Потому что это настолько идиотский алгоритм, что он сбивает с толку предсказатель ветвления у процессора. Происходит это из-за того, что невозможно предугадать, как дальше пойдёт выполнение алгоритма, из-за чего самый худший (на бумаге) случай для сортировки пузырьком -- когда исходный массив уже рассортирован, но в обратном порядке -- на деле сортируется быстрее, чем (псевдо)случайный. Таким образом, производительность этого алгоритма в большей степени зависит от того, как работает само железо, а не насколько производителен алгоритм, написанный на каком-то языке.

А брать надо, например, сортировку вставками (insertion sort). Там всё более-менее внятно.

Далее берём и пишем программы на разных языках, стараясь делать как можно меньше различий (хотя данная философия летит под откос, если надо сравнить, например, Джаву и Хаскелл -- там вообще парадигма программирования разная). Для большинства императивных языков -- сработает. Компилируем в бинарники, запускаем, и смотрим, кто дольше выполняется.

Вот и давайте проделаем сей фокус. Я нарисовал сортировку вставками на Джаве и на голом Си. Происходит сортировка массива с 100 000 элементами, чьи значения варьируются от 0 до 32768.

Код прячу в спойлеры.

[Джава]
import java.util.Random;

public class insertionsort
{
public static void main(String[] args)
{
int taskSize = 100000;
int [] array = new int[taskSize];
Random randomizer = new Random();
int intermediate;

for (int i = 0; i < taskSize; i++)
{
array[i] = randomizer.nextInt(32768);
}

long startTime = System.nanoTime();

for (int i = 0; i < taskSize; i++)
{
for (int j = 0; j < taskSize; j++)
{
if (array[j] > array[i])
{
intermediate = array[j];
array[j] = array[i];
array[i] = intermediate;
}
}
}

long endTime = System.nanoTime();

System.out.println("Elapsed time, seconds: " + (endTime - startTime) / 1000000000.0);

}

}


[Си]
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{
int taskSize = 100000;

int array[taskSize];

int intermediate = 0;

for (int i = 0; i < taskSize; i++)
{
array[i] = rand() % 32768;

}

clock_t startTime = clock();

for (int i = 0; i < taskSize; i++)
{
for (int j = 0; j < taskSize; j++)
{
if (array[j] > array[i])
{
intermediate = array[j];
array[j] = array[i];
array[i] = intermediate;
}
}
}

clock_t endTime = clock();

double elapsed_time = (double)(endTime - startTime) / CLOCKS_PER_SEC;

printf("Elapsed time, seconds: %f\n", elapsed_time);

}


Как видите, ничего экстраординарного, обычный алгоритм сортировки с O(n2) сложностью.

Сишный код компилировал, разумеется, clang, со степенью оптимизации 3 (i.e. clang sorter.c -o sorter-clang -O3). Джаву компилировал в jar из Эклипса, JVM 9. Всё запускалось в виртуалке под Убунту 16.

И что получилось?

Программа на Си, скомпилированная clang, выполняется в среднем 11.57 секунд (min. 11.56, max. 11.58)

А та же программа на Джаве выполняется... та-дам!! -- 10.43 секунды (min. 10.42, max 10.46), то-есть, быстрее, чем на одну секунду. Получается, что Джава работает быстрее Си на 11% -- на данном алгоритме.

Так что извините, граждане, верующие, что Программа, Переписанная На Си, Всегда Будет Быстрее -- это не так.

ОК, может, это clang такой плохой компилятор? Извольте, давайте попробуем gcc (gcc sorter.c -o sorter-gcc -O3). Получилось ещё хуже =)))

Рабочее время программы стало составлять 16 секунд в среднем (min. 15.95, max. 16.06). Очевидно, потому, что gcc совсем говённый компилятор (GNU-тый софт, блин).

Предвижу, что щас налетят Настоящие Программисты на Си и скажут, что Сишный код надо было писать с Специальными ч0рными Заклинаниями, например, с указателями, и передвигаться по массиву не через цикл for, а через инкремент указателя. На что я возражу, что это получится уже немного другая программа и сравнивать их будет некорректно. И что тут уже не язык программирования будет оказывать влияние, а сама программа, так что сравнение будет бессмысленным.
Tags: #include, компьютерное, на вентилятор, программирование
Subscribe

  • Сабовый вуфер

    Поставил сабвуфер в афффтомобиль. Плоский, под сиденье. Вот такой: Провод кинул под левое крыло и затем под молдинг порога двери. Очень сильно…

  • Котейковое

    Идёт урок по арифметике. –Иванов, если я тебе дам двух котов, а потом ещё двух, сколько котов у тебя будет? –Пять –Почему…

  • Дураки, что ли

    Маск настаивает на том, чтобы заменить руль на новой Тесле S, вот таким вот, блин, причиндалом: Он дурак, что ли? Ну ведь сто раз уже…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 12 comments

  • Сабовый вуфер

    Поставил сабвуфер в афффтомобиль. Плоский, под сиденье. Вот такой: Провод кинул под левое крыло и затем под молдинг порога двери. Очень сильно…

  • Котейковое

    Идёт урок по арифметике. –Иванов, если я тебе дам двух котов, а потом ещё двух, сколько котов у тебя будет? –Пять –Почему…

  • Дураки, что ли

    Маск настаивает на том, чтобы заменить руль на новой Тесле S, вот таким вот, блин, причиндалом: Он дурак, что ли? Ну ведь сто раз уже…