January 29th, 2018

компьютеры

Си опять не обогнал Джаву

Попробовал снова устроить соревнование двух языков программирования. В качестве подопытного алгоритма в этот раз у нас очень древний (200 лет до нашей эры!) способ нахождения всех простых чисел до некоторого целого числа n, называемый Решето Эратосфена. Берём массив чисел и начинаем вычёркивать составные числа: начиная с 2 и кончая n, вычёркиваем в массиве все числа, являющиеся кратными текущему числу. Например, если надо найти все простые числа до 10, начиная с 2 мы зачеркнём 4, 6, 8. Потом зачеркнём всё кратное 3, т.е. 6, 9. И так далее. В результате останутся только простые числа.

Я знаю, что 6 уже было зачёркнуто как кратное 2. Но вставление лишнего if в самый центр цикла (т.е. в то, что выполняется максимальное количество раз) сильно замедляет работу алгоритма. В машинном времени дешевле поставить 0 в нужном месте в памяти, чем проверять лишний раз.

Сложность алгоритма O(n log(log(n))).

Я находил все простые числа до 200 000 000 (больше не получалось, выскакивало переполнение кучи). После чего распечатывал первые 10 и последние 10. Делал я это во-первых, с целью проверить правильность работы алгоритма, а во-вторых компилятор нынче сильно умный, зараза, пошёл. Он мог увидеть, что у меня все эти данные потом в программе не используются, и тупо пропустить выполнение. Уже видел такое не раз и не два.

[Сишный код]
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{

int limit = 200000000;

static int primes[200000000];

for (int i = 2; i < limit; i++)
{
primes[i] = 1;
}

clock_t startTime = clock();

for (int i = 2; i < limit; i++)
{
if(primes[i] == 1)
{
for (int j = 2; j < (double)limit / i; j++)
{
primes[j * i] = 0;
}

}
}

clock_t endTime = clock();

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

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

int maxToPrint = 10;
int printed = 0;

for (int i = 2; i < limit; i++)
{
if (primes[i] == 1)
{
printf("%i\n", i);
printed++;
}

if (printed == maxToPrint)
{
break;
}

}

printed = 0;

for (int i = limit - 1; i > 0; i--)
{
if (primes[i] == 1)
{
printf("%i\n", i);
printed++;
}

if (printed == maxToPrint)
{
break;
}
}

}


[Джавовский код]
public class primes
{

public static void main(String[] args)
{

int limit = 200000000;

int primes[] = new int[200000000];

for (int i = 2; i < limit; i++)
{
primes[i] = 1;
}

//init done
long startTime = System.nanoTime();

for (int i = 2; i < limit; i++)
{
if(primes[i] == 1)
{
for (int j = 2; j < (double)limit / i; j++)
{
primes[j * i] = 0;
}

}
}

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

int maxToPrint = 10;
int printed = 0;

for (int i = 2; i < limit; i++)
{
if (primes[i] == 1)
{
System.out.println(i);
printed++;
}

if (printed == maxToPrint)
{
break;
}

}

printed = 0;

for (int i = limit - 1; i > 0; i--)
{
if (primes[i] == 1)
{
System.out.println(i);
printed++;
}

if (printed == maxToPrint)
{
break;
}
}

}

}


А теперь -- результаты.

Под виртуалкой Ubuntu Сишная версия слегка выигрывала, выполняясь в среднем за 6.51 секунд против 6.71 секунд у Джава-варианта.
Под баш-оболочкой в Windows 10 с большим отрывом выиграла уже Джава, выполняясь за 4.75 секунд вместо 6.4 у Сишной версии.
И, наконец, я скомпилировал Сишный код под Windows, поставив дистрибутив LLVM (clang), и запустил всё просто в командной строке. Скорость выполнения обоих программ оказалась одинаковой -- от 4.69 до 4.75 секунд для обоих вариантов, разница, если она и была, составляла какие-то доли процента -- статистически незначимо.

Си компилировал везде clang со степенью оптимизации 3. В этот раз gcc показал себя не так сильно отстающим от clang (но всё же отстающим), как в прошлый раз. Java -- JDK 9, экспорт в jar из Eclipse.

Итого! Как мы видим, скорость выполнения данных программ больше зависит от того, где и как программа запускается, чем от языка программирования.

Засим -- извольте откланяться, на тему "Си быстрее Джавы" я могу предъявить уже два теста, где Си нихера не быстрее Джавы. Если кто-то продолжит упорствовать, пусть пишет свои тесты, выкладывает код в открытый доступ, чтобы можно было устроить независимую перепроверку. А я -- за то, чтобы брать ПРАВИЛЬНЫЙ инструмент под задачу, а не размахивать флагом "Лучший язык программирования -- Паскаль". Драйверы низкоуровневые или там ядро ОС -- пишите на голых Сях. А крупный корпоративный проект на них вы писать УСРЁТЕСЬ, а на Джаве -- нормально. Что лучше -- молоток или пила? Отвёртка или кувалда? Да ни то ни другое. Они разные и для разного.
facepalm

К вопросу о секретности данных

Как известно, 99% всей секретной информации добывается из открытых источников. Суммированная, обработанная информация, и особенно сделанные из этой информации выводы -- даже если это обработка газетных заметок -- легко может быть секретной.

Вываливание в общий доступ GPS-треков, полученных с "умных" часов, позволило определить, например, истинные размеры американских военных баз, пути патрулирования, проходы:



https://www.forbes.com/sites/thomasbrewster/2018/01/29/strava-fitness-data-location-privacy-scare/

Молодцы, что сказать.

Понятие "неприкосновенности частной жизни", КМК, тупо исчезло за последние 10 лет. Шпионят абсолютно за всеми, и, *censored*, никто не понимает, что за инфу они собирают, как её надо охранять, и какие могут быть последствия от разглашения.