java, Си и PHP

[valyala]

java, Си и PHP

Даны различные алгоритмы сортировки. От самых медленных (сортировка "пузырьком") до самых быстрых (сортировка Хора, Шелла, поразрядная сортировка).

Вопрос: когда эти алгоритмы будут работать быстрее - когда реализованы на java, Си или на PHP?

Делаем ставки, господа!

Пожалуйста, аргументируйте свои ответы и предположения.

 

[Frol]

Вопрос: когда эти алгоритмы будут работать быстрее - когда реализованы на java, Си или на PHP?

дело не в языке, а в программисте

 

[valyala]

А чтобы наши дебаты пошли в правильном направлении, приведу реализацию алгоритма восходящей поразрядной сортировки на java, Си и PHP:
java:

    public void sort_low_radix(int a[])
    {
        int cnt[][] = new int[4][];
        int b[];
        int i, j;
        int a_len = a.length;

        if (a_len < 2) {
            // массив длиной 1 элемент не нужно сортировать :)
            return;
        }

        // инициализируем счетчик [cnt]
        for (j = 0; j < 4; j++) {
            cnt[j] = new int[257];
            for (i = 0; i < 257; i++) cnt[j][i] = 0;
        }

        // выделяем память под копию сортируемого массива
        b = new int[a_len];

        // подсчитываем количество элементов для каждого значения j-го разряда
        for (i = 0; i < a_len; i++) {
            for (j = 0; j < 4; j++) {
                cnt[j][1 + ((a[i] >>> (8 * j)) & 0xff)]++;
            }
        }

        for (j = 0; j < 4; j++) {
            /*
                вычисляем позиции cnt[i], начиная с которых будут располаться элементы
                с соответствующим значением j-го разряда
            */
            for (i = 1; i < 256; i++) cnt[j][i] += cnt[j][i - 1];
            // расставляем элементы из массива a в массив b в указанном порядке
            for (i = 0; i < a_len; i++) {
                b[cnt[j][(a[i] >>> (8 * j)) & 0xff]++] = a[i];
            }
            // копируем массив b на место массива a
            for (i = 0; i < a_len; i++) a[i] = b[i];
        }
    }

Си:

void sort_low_radix(int *a, size_t a_len)
{
    if (a_len < 2) return;

    unsigned int cnt[4][257] = {0};
    int *b;
    size_t i, j;

    /* выделяем память под копию сортируемого массива */
    b = (int *) malloc(a_len * sizeof(int));
	if (b == NULL) return;

    // подсчитываем количество элементов для каждого значения j-го разряда
    for (i = 0; i < a_len; i++) {
        for (j = 0; j < 4; j++) cnt[j][1 + ((a[i] >> (8 * j)) & 0xff)]++;
    }

    for (j = 0; j < 4; j++) {
        /*
            вычисляем позиции cnt[i], начиная с которых будут располаться элементы
            с соответствующим значением j-го разряда
        */
        for (i = 1; i < 256; i++) cnt[j][i] += cnt[j][i - 1];
        // расставляем элементы из массива a в массив b в указанном порядке
        for (i = 0; i < a_len; i++) {
            b[cnt[j][(unsigned char) (a[i] >> (8 * j)) & 0xff]++] = a[i];
        }
        memcpy(a, b, a_len * sizeof(int)); // копируем массив b на место массива a
    }
    free(b);
}

PHP:

function sort_low_radix(& $a) {
    $a_len = sizeof($a);

    if ($a_len < 2) {
        // массив длиной 1 элемент не нужно сортировать :)
        return;
    }

    // инициализируем счетчик $cnt
    for ($i = 0; $i < 4; $i++) {
        $cnt[$i] = array_fill(0, 257, 0);
    }

    // инициализируем вспомогательный массив
    $b = array();

    // подсчитываем количество элементов для каждого значения j-го разряда
    for ($i = 0; $i < $a_len; $i++) {
        for ($j = 0; $j < 4; $j++) {
            $cnt[$j][1 + (($a[$i] >> (8 * $j)) & 0xff)]++;
        }
    }

    for ($j = 0; $j < 4; $j++) {
        /*
            вычисляем позиции $cnt[$i], начиная с которых будут располагаться элементы
            с соответствующим значением j-го разряда
        */
        for ($i = 1; $i < 256; $i++) $cnt[$j][$i] += $cnt[$j][$i - 1];
        // расставляем элементы из массива $a в массив $b в указанном порядке
        for ($i = 0; $i < $a_len; $i++) {
            $b[$cnt[$j][($a[$i] >> (8 * $j)) & 0xff]++] = $a[$i];
        }
        // копируем массив $b на место массива $a
        $a = $b;
    }
}

 

[AnToXa]

ява(из-за динамического профайлинга) или, что чуть вероятнее, в C.

и расскажи нам как ты тестил.

 

[Demiurg]

вопрос из области:
на чем быстрее доехать на автомобиле, самолете или параходе.

 

[DimbIch]

Demiurg
а смотря куда )

 

[Demiurg]

DimbIch
в том то и дело

 

[Cid]

Подобное сравнение не совсем корректно. Что значит "работать быстрее"?

Скомпилированный бинарник получает управление и ресурсы непосредственно в контексте процесса ОС.

Байт-код Java.class выполняется с помощью JVM, соответственно скорость работы и используемые ресурсы увеличиваются еще и с учетом скорости трансляции .class в исполняемый код и обработку его JVM.

Исходные тексты скриптов PHP считываются процессом веб-сервера, и потом обрабатываются PHP-процессором. Соответственно, играет роль время необходимое для подъема процесса, отведенные ресурсы для процесса с учетом нагрузки на сервер и т.п.

В то же время, вызов бинарника (считай запуск приложения при обработке скрипта) - задача куда более трудоемкая, чем обработка с помощью PHP.

Ну, это так, навскидку.

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

 

[neko]

valyala
если тебя интересует вопрос поищи гуглем
я где-то видел очень много алгоритмов причем там считались разные реализации одного и того же, сделанные разными людьми, всякие средние и пр.

с. джава и перл
в среднем вроде было c < perl < java
ну а perl < php

-~{}~ 28.10.04 06:45:

Cid
ты прав только очень длинно написал
любое подобное сравнение некорректно

 

[PhpGuest]

Автор оригинала: neko
valyala
если тебя интересует вопрос поищи гуглем
я где-то видел очень много алгоритмов причем там считались разные реализации одного и того же, сделанные разными людьми, всякие средние и пр.

с. джава и перл
в среднем вроде было c < perl < java
ну а perl < php

-~{}~ 28.10.04 06:45:

Cid
ты прав только очень длинно написал
любое подобное сравнение некорректно

а чего некорректно то? можем замерить время выполнения прям куска кода сортироваки например на массиве уевой тучи обьема или на моалой но много раз и все станет ясно ) ASSEMBLER рулит!

 

[alpine]

PhpGuest
>> ASSEMBLER рулит!
Куда он рулит ?!

-~{}~ 28.10.04 13:07:

valyala
Может давай применительно к веб разбирать?

 

[valyala]

ява(из-за динамического профайлинга) или, что чуть вероятнее, в C.

AnToXa, а что такое динамический профайлинг и как он влияет на скорость исполнения программ виртуальной машиной ява?

и расскажи нам как ты тестил.

Все началось с того, что мне на глаза попалась вот эта статья: http://soft.compulenta.ru/2004/6/17/47645/, в которой говорится, что виртуальная машина ява исполняет код быстрее, чем процессор - машинные инструкции, полученные компилятором gcc из исходного кода на C++. Я не поверил. И решил провести "независимое тестирование", включив в него кроме java и Си еще PHP c perl'ом.

Перед тестированием не было сомнений, что Cи всех сделает. Я предполагал, что perl будет быстрее, чем PHP. Но даже не догадывался, какое место займет java.

Для начала приведу версии компиляторов и интерпретаторов, которые использовались во время тестирования:
java - client JVM 5 beta как под винду, так и под юникс. Скачать можно отсюда: http://java.sun.com/j2se/1.5.0/download.jsp
Cи - lcc-win32 под винду. Скачиваем отсюда: http://www.cs.virginia.edu/~lcc-win32/, gcc 3.4.2 под юникс http://gcc.gnu.org/
PHP - PHP5.0.2 как под винду, так и под юникс. Неужели не знаете, откуда скачать? http://www.php.net/downloads.php
perl - ActivePerl 5.8.4.810 под винду. http://activestate.com/Products/ActivePerl/

Во всех компиляторах и интерпретаторах использовались настройки по умолчанию. Debug mode везде отключен.

Засекалось время, непосредственно затраченное на сортировку, а не общее время выполнения программы.

Получены следующие результаты:
1) Java - как это ни парадоксально, но первое место заняла java. Кто-нибудь может внятно объяснить, как интерпретатор байт-кода оказался быстрее, чем процессор, непосредственно исполняющий машинные инструкции, полученные компилятором Си? Не стоит забывать, что в java встроена проверка на границы массива, динамическое управление памятью и многопоточность, которые явно не прибавляют ей скорости.
2) Cи. Ненамного отставал (10% - 50%) от java абсолютно на всех алгоритмах сортировки.
3) perl. Медленне, чем Си, раз эдак в 50.
4) PHP. Медленне, чем perl, в 2 раза. Т.е. медленне, чем Cи, в 100 раз.

Выводы:
1) не используйте perl и PHP для сортировки больших массивов чисел
2) После этих тестов у меня кардинально изменилось отношение к java.
3) самый быстрый алгоритм сортировки огромных массивов равномерно распределенных по всей области значений случайных целых чисел (больше десяти миллионов) - восходящая поразрядная сортировка. Ее алгоритм приведен в начале треда. Например, на компьютере с процессором Althlon-800Mhz под win2k, этот алгоритм, реализованный на java, сортирует массив из десяти миллионов элементов за 5 секунд, а С-шная функция qsort() из библиотеки stdlib.h справляется с аналогичным массивом в среднем за 32 секунды.

 

[AnToXa]

1. где полные исходники тестов?
2. как все это собиралось?
3. динамический профайлинг - это оптимизация кода в процессе выполнения, т.к. jvm не надо стартовать при каждом запуске "скрипта", то это можно сделать, плюс оптимизация выделения памяти.
4. > Например, на компьютере с процессором Althlon-800Mhz под win2k [т.д.] опять же расскажи нам как ты тестил.

 

[fisher]

немного смущает, что платформа была выбрана win2K. и просединюсь к антохе - без подробной информации о том, как тестировали - разговор почти ни о чем (хотя если исключить из рассмотрения яву, оставив СИ-пхп-перл, - имхо результаты весьма правдоподобные).

 

[valyala]

1. где полные исходники тестов?

Вверху я привел для примера исходник одного из алгоритмов сортировки под java, Cи и PHP. Если приведу остальные, то меня обзовут флудером Вопрос темы - не в том, как выглядят исходники, а в том, почему java оказалась быстрее Си. Если кого-нибудь, кроме меня, этот вопрос заинтересует, то он без труда реализует другие алгоритмы сортировки и проверит все самостоятельно.
Кстати, сортировка - это, по сути, активная работа с памятью и огрномное количество инструкций (процессорных или байт-кодовых).

2. как все это собиралось?

java:
javac ./SortTest.java
java SortTest sort_method

c:
gcc ./sort_test.c
./a.out sort_method

php:
http://localhost/sort_test.php?method=sort_method

perl:
perl ./sort_test.pl sort_method

3. динамический профайлинг - это оптимизация кода в процессе выполнения, т.к. jvm не надо стартовать при каждом запуске "скрипта", то это можно сделать, плюс оптимизация выделения памяти.

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

4. > Например, на компьютере с процессором Althlon-800Mhz под win2k [т.д.] опять же расскажи нам как ты тестил.

Просто прогонял тесты по несколько раз и вычислял матожидание и дисперсию получаемого времени сортировки.

 

[AnToXa]

почему ява оказалась быстрее C можно сказать только имея код как раз.

>Не представляю, как можно динамически оптимизировать алгоритм сортировки, если при каждом запуске генерируется
>массив псевдослучайных чисел?
оптимизируется код, некоторые функции инлайнятся, где-то делается грамотный prefetch, память не выделяется каждый раз и т.п.

попробуй собрать icc с максимальными настройками по скорости, а потом еще отпрофайлить(icc умеет) и тогда результаты тебя приятно удивлят скорее всего.

 

[valyala]

почему ява оказалась быстрее C можно сказать только имея код как раз.

Ок. Все алгоритмы приводить не буду. Приведу самый короткий.
Вот код на Си (под винду):

#include <stdio.h> // for printf(), size_t
#include <stdlib.h> // for malloc(), free()
#include <windows.h> // for GetTickCount(), DWORD

#define NUMBERS_CNT 10000

/* сортировка линейными вставками */
void sort_linear_ins(int *a, size_t a_len)
{
    int tmp;
    size_t i, j;

    for (i = 1; i < a_len; i++) {
        j = i;
        tmp = a[j];
        while (j > 0 && tmp < a[j - 1]) {
            a[j] = a[j - 1];
            j--;
        }
        a[j] = tmp;
    }
}

int main(int argc, char *argv[])
{
    int *a;
    int i;
    DWORD t;

    /* выделяем память под массив */
    a = (int *) malloc(NUMBERS_CNT * sizeof(int));
    if (a == NULL) return 1;
    /* генерируем массив случайных чисел */
    srand((unsigned int) GetTickCount());
    for (i = 0; i < NUMBERS_CNT; i++) {
        a[i] = rand();
    }
    /* сортируем этот массив и засекаем время сортировки */
    t = GetTickCount();
    sort_linear_ins(a, NUMBERS_CNT);
    t = GetTickCount() - t;
	/* показываем время сортировки */
    printf("time: %lu milliseconds", t);
    free(a); /* очищаем память */
    return 0;
}

А вот код на java:

import java.lang.System;
import java.util.Random;

class SortTest
{
    private static final int NUMBERS_CNT = 10000; // количество чисел для сортировки

    public static void main(String args[])
    {
        Random rndGenerator = new Random(); // инициализируем генератор псевдослучайных чисел
        int a[] = new int[NUMBERS_CNT]; // массив, который необходимо будет отсортировать
        int i;
        long t;

        // создаем массив псевдослучайных чисел
        for (i = 0; i < NUMBERS_CNT; i++)
            a[i] = rndGenerator.nextInt(0x7fffffff);

        // запускаем функцию сортировки и засекаем время выполнения этой функции
        t = System.currentTimeMillis();
        sort_low_radix(a);
        t = System.currentTimeMillis() - t;

        System.out.print("time: " + t + " milliseconds\n");
    }

    // сортировка линейными вставками
    private static void sort_low_radix(int a[])
    {
        int tmp;
        int i, j;
        int a_len = a.length;

        for (i = 1; i < a_len; i++) {
            j = i;
            tmp = a[j];
            while (j > 0 && tmp < a[j - 1]) {
                a[j] = a[j - 1];
                j--;
            }
            a[j] = tmp;
        }
    }
}

При стандартных настройках под у меня получились следующие результаты:
Cи: 580 миллисекунд
java: 370 миллисекунд

А вот если в lcc включить оптимизацию, то результат, действительно, приятно меня удивил и поставил все на свои места. В этот раз программа на Си справляется с задачей за 150 миллисекунд.

То же самое относится и к другим тестам - после включения оптимизации в компиляторе Cи все становится на свои места.
Но все равно, JVM меня удивил своей скоростью. Раньше у меня был стереотип, что java - большой тормоз. Оказалось, что это не совсем так.

 

[CMHungry]

На вычислительных задач ява уже давно не тормоз. А вот гуй на яве тот еще тормоз. Zend Studio на p3 - слайд-шоу просто, на п4 простеньком - 1.6 - вполне нормально.

 

[neko]

valyala
47 ms
vc++ 6 sp5

видишь ли когда мы говорим "ява быстрее пхп" мы подразумеваем sun JVM (а есть ли другие?) и известно чей php
а что такое си?
тут вообще все зависит от компилятора
а ты взял какой-то бесплатный и хочешь по нему сделать выводы

-~{}~ 29.10.04 12:42:

а стоп, железо то другое у меня хехе
в общем все равно тут нет смысла сравнивать не настраивая и не выбирая наилучший компилятор под опр. платформу
т.к. на практике это всегда будет делаться