forum.boolean.name - Великая битва 4х языков программирования на простейшей задачке

forum.boolean.name (http://forum.boolean.name/index.php)

- Алгоритмика (http://forum.boolean.name/forumdisplay.php?f=21)

Великая битва 4х языков программирования на простейшей задачке

Приветсвую, булкомэны!
Думаю многие хотели бы сделать свой майнкрафт с ГСЧ и крупнопиксельными женщинами. И вот хотелось бы узнать на каком языке это лучше всего делать.

Под лучше я понимаю два критерия:
- эффективность работы программиста
- эффективность работы программы

Исходя из первого пункта всякие С/С++ были выкинуты из перечня возможных твердой рукой и без всякого сожаления.
Objective C проваливает оба пункта и мы тоже с ним прощаемся.

Оставшиеся кандидаты:
.NET Framework
Java
Blitz3D
PHP (ради лулзов)
Erlang (ради эпичности)

Ответ: Великая битва 4х языков программирования на простейшей задачке

Итак, задача:
выделяем трехмерный массив целых чисел 512х128х512
есть счетчик, целое число
обходим массив, пишем в ячейку значение счетчика, увеличиваем счетчик на единицу.
всё.

Вот такая ерундовая задачка.

На разных языках были написаны тесты.
Спасибо таким товарищам:
Romanzes'у за вариант на Java
Phantom'у за вариант на PHP
Randomize'у за вариант на BlitzMAX

Все задачки тестировались на ноутбуке с такой конфигурацией:
Core i3 2100MHz, 4Gb RAM, Win7 64bit.

Ответ: Великая битва 4х языков программирования на простейшей задачке

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

Код:

allocStart = MilliSecs()

Dim voxelData(512,128,512)

allocStop = MilliSecs()

alloc = allocStop - allocStart

Print "alloc: " + alloc + " ms"

counter = 0



fillStart = MilliSecs()

For i = 0 To 20

    For x = 0 To 512

        For y = 0 To 128

            For z = 0 To 512

                voxelData(x,y,z) = counter

                counter = counter + 1

            Next

        Next

    Next

Next

fillStop = MilliSecs()



fill = (fillStop - fillStart) / 20



Print "fill: " + fill + " ms"

Input("press any key")

Debug отключен. Цикл заполнения массива выполняется 20 раз, результат усредняется.

Результаты:
время выделения памяти под массив: 327 мс
время заполнения массива: 716 мс

Ну, неплохо для начала.

Ответ: Великая битва 4х языков программирования на простейшей задачке

теперь потестируем .NET 4 - технологию, отвечающую за скриптинг в движке Unity3D (это не совсем верно, т.к. в Unity используется Mono - аналог .NET Framework)

Код:

using System;



namespace BigArray

{

    class Program

    {

        public static void Main(string[] args)

        {

            int counter = 0;

            

            int allocateStart = Environment.TickCount;

            int[,,] voxelData = new int[512,128,512];

            int allocateStop = Environment.TickCount;

            

            Console.WriteLine("Allocation time: {0} ms", allocateStop - allocateStart);

            

            int fillStart = Environment.TickCount;

            for(int i = 0; i < 20; i++)

            {

                for(int x = 0; x < 512; x++)

                {

                    for(int y = 0; y < 128; y++)

                    {

                        for(int z = 0; z < 512; z++)

                        {

                            voxelData[x,y,z] = counter++;

                        }

                    }

                }

            }

            int fillStop = Environment.TickCount;

            

            Console.WriteLine("Fill time: {0} ms", (fillStop - fillStart) / 20);

            

            Random random = new Random();

            int randomX = random.Next(0, 511);

            int randomY = random.Next(0, 127);

            int randomZ = random.Next(0, 511);

            Console.WriteLine("Random array element at: ({0},{1},{2}) is {3}", randomX, randomY, randomZ, voxelData[randomX, randomY, randomZ]);

            

            Console.Write("Press any key to continue . . . ");

            Console.ReadKey(true);

        }

    }

}

И результаты:
время выделения массива: 0 мс
время заполения: 187 мс

Вот так, старичок Блиц нервно курит в стороне. Всё таки новые технологии явно лучше. Прямо проникаешься производительностью дотнета.

Ответ: Великая битва 4х языков программирования на простейшей задачке

Следующим пунктом идет Java 7. Технология, стоящая за оригинальным Minecraft.

Код:

package bigarrayjava;



import java.util.Random;



public class BigArrayJava 

{

    public static void main(String[] args) 

    {

        int counter = 0;

        long allocateStart = System.currentTimeMillis();

        int[][][] voxelData = new int[512][128][512];

        long allocateStop = System.currentTimeMillis();

        long allocateElapsed = allocateStop - allocateStart;

        System.out.println("Allocate: " + allocateElapsed + " ms");

        

        long fillStart = System.currentTimeMillis();

        for(int i = 0; i < 20; i++)

        {

            for(int x = 0; x < 512; x++)

            {

                for(int y = 0; y < 128; y++)

                {

                    for(int z = 0; z < 512; z++)

                    {

                        voxelData[x][y][z] = counter++;

                    }

                }

            }

        }

        long fillStop = System.currentTimeMillis();

        long fillElapsed = (fillStop - fillStart) / 20;

        System.out.println("Fill: " + fillElapsed + " ms");

        

        Random random = new Random();

        int randomX = random.nextInt(511);

        int randomY = random.nextInt(127);

        int randomZ = random.nextInt(511);

        

        System.out.println("Random element at (" + randomX + "," + randomY + "," + randomZ + ") is " 

                + voxelData[randomX][randomY][randomZ]);

    }

}

Результаты:
время выделения памяти под массив: 265 мс
время заполения массива: 41 мс

Гордость и величие дотнета померкли и скукожились. Java выигрывает на заполнении массива в более чем 4 раза.
Так и хочется спросить, Нотч, почему Майнкрафт так тормозит???

Ответ: Великая битва 4х языков программирования на простейшей задачке

А у меня на блитз другой результат alloc 76 ms fill 1179 ms это плохо да?
естественно не сравнивая с .NET 4, может ещё что-то в памяти сидит.

Ответ: Великая битва 4х языков программирования на простейшей задачке

ffinder, может объединить сообщения? Просто сейчас тут понафлудят и будут посты раскидны ажбы как.

Ответ: Великая битва 4х языков программирования на простейшей задачке

Настало время ЭПИЧНОЙ ЭПИЧНОСТИ!
На самом деле нет. Я так пошутил. В Эрланге нет изменяемых массивов. Массивы сделаны через деревья. И еще Эрланг это интерпретатор.
Поэтому я не стал парится, и просто написал в консоли:

Код:

 {{StartMega, StartSecs, StartMicro}, VoxelData, {StopMega,  StopSecs, StopMicro}} = {now(), [X || X <- lists:seq(0,  512*128*512)], now()}.

StopSecs - StartSecs.

что дало грубый и безжалостный результат в 59 секунд и список длинной в 33 миллиона элементов.

А самые внимательные заметили, что в названии темы 4 языка, а в списке тестируемых - 5. Как же так?

Просто PHP съел гигабайт памяти и вылетел не решив поставленную задачу:-D

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

Ответ: Великая битва 4х языков программирования на простейшей задачке

Мой тест на BlitzMax:

PHP код:




SuperStrict 
Framework brl.basic 
Import brl.standardio 
 
Local allocStart:Int = MilliSecs() 
Local voxelData:Int[512, 128, 512] 
Local allocStop:Int = MilliSecs() 
Local alloc:Int = allocStop - allocStart 
Print "alloc: " + alloc + " ms" 
 
Local counter:Int = 0 
 
Local fillStart:Int = MilliSecs() 
For Local i:Int = 0 Until 20 
    For Local x:Int = 0 Until 512 
        For Local y:Int = 0 Until 128 
            For Local z:Int = 0 Until 512 
                voxelData[x, y, z] = counter 
                counter = counter + 1 
            Next 
        Next 
    Next 
Next 
Local fillStop:Int = MilliSecs() 
Local fill:Int = (fillStop - fillStart) / 20 
 
Print "fill: " + fill + " ms" 
Input("press any key")

Alloc: 178ms
Fill: 258ms

Машина для теста:
AMD Athlon 1.81GHz
1Gb RAM
Windows 7 x86

Ответ: Великая битва 4х языков программирования на простейшей задачке

тестовая программа Randomize'а дает такой результат:
выделение памяти: 45 мс
заполнение массива: 75 мс

Ответ: Великая битва 4х языков программирования на простейшей задачке

В .Net, используй в циклах ++x а не x++.
Также, используй StopWatch для корректного замера времени на операцию.
И используй Jagged Array, он будет где-то в 2-3 раза быстрее.

Ответ: Великая битва 4х языков программирования на простейшей задачке

Цитата:

Сообщение от ffinder (Сообщение 211267)

Код:

For i = 0 To 20

Цикл заполнения массива выполняется 20 раз

Не 20, а 21, хотя потом время делишь на 20.

В данном конкретном случае можно немного оптимизировать :)

Код:

Local Time1% = MilliSecs()

Local Voxels%[512 * 128 * 512]

Local Time2% = MilliSecs()

Local n% = 0

For i = 0 To 20 - 1

        For x = 0 To (512 - 1) Shl 16 Step 1 Shl 16

                For y = 0 To (128 - 1) Shl 9 Step 1 Shl 9

                        Local xy% = x Or y

                        For z = 0 To 512 - 1

                                Voxels[xy Or z] = n

                                n = n + 1

                        Next

                Next

        Next

Next

Local Time3% = MilliSecs()

Print(Str(Time2 - Time1))

Print(Str((Time3 - Time2) / 20))

Input("")

End

В результате у меня аллокация ~0мс (ну это понятно, память со стека берется), заполнение ~210мс
ЗЫ
Твой вариант: аллокация ~244мс, заполнение ~5740мс
проц P-4 Prescott 3Ghz
ЗЫЫ
Да и еще, помоему для minecraft-like игр юзать 3д массивы - чистое нубство :)

Ответ: Великая битва 4х языков программирования на простейшей задачке

Цитата:

Сообщение от Платон Александрович (Сообщение 211285)

PHP код:




For i = 0 To 20 - 1 
    For x = 0 To (512 - 1) Shl 16 Step 1 Shl 16 
        For y = 0 To (128 - 1) Shl 9 Step 1 Shl 9 
            Local xy% = x Or y

Это мне одному кажется чушью? Зачем столько лишних операций? Да, побитовые операции хороши, но у нас тут идёт сравнение на равных условиях без всяких там выёживаний.

Цитата:

Сообщение от Платон Александрович (Сообщение 211285)

Да и еще, помоему для minecraft-like игр юзать 3д массивы - чистое нубство

Альтернативные предложения? (если не понятно - используемый в тесте 3d массив является чанком(chunk) как это сделано в оригинальной игре)

Ответ: Великая битва 4х языков программирования на простейшей задачке

Цитата:

Сообщение от Randomize (Сообщение 211286)

Зачем столько лишних операций?

Где ты там увидел лишние операции? Можно конечно было в уме посчитать размер и шаг циклов, но зачем если это константы, пускай компилятор сам считает. Ну вот читабельный вариант, если так непонятно

Код:

Const Width% = 512

Const Height% = 128

Const Depth% = 512

Const Pitch% = Height * Depth

...

For x = 0 To (Width - 1) * Pitch Step Pitch

    For y = 0 To (Height - 1) * Depth Step Depth

        Local xy% = x Or y

        For z = 0 To Depth - 1

...

Цитата:

Сообщение от Randomize (Сообщение 211286)

но у нас тут идёт сравнение на равных условиях без всяких там выёживаний.

внимательней читай, я сказал что в данном случае можно оптимизировать. Да и сравнивать языки без использования их особенностей глупо. Это все равно что тракториста просить поездить на тракторе и болиде формулы-1 и спросить что лучше ездит :-) У каждого языка есть свои фичи, и если уж ты пишешь на этом языке, то стоих их использовать, особенно если они могут улучшить программу.

Цитата:

Сообщение от Randomize (Сообщение 211286)

Альтернативные предложения?

Для начала надо подумать на организацией памяти, вот так втупую использовать большой 3д массив глупо. Надо исходить из конкретных задач, ибо произвольный доступ к такому массиву всегда чреват кеш-миссами. А значит нужно подумать как уменьшить кол-во данных в таком массиве, сжимать\разжимать его, сделать доступ менее произвольным. Это уже алгоритмический уровень, и язык здесь играет гораздо меньшую роль.
Можно использовать octree или BVH, ибо 3д массив не адаптивен, на пустых пространствах много памяти тратится бесполезно.
Память выделять из пула.
Хранить смещения вместо указателей, это немного уменьшит узлы дерева.
Дерево обновлять локально - скользить вверх\вниз по веткам.
Периодически перестраивать дерево уменьшая фрагментацию памяти, сложно конечно, но думаю возможно.
Использовать выравнивание памяти.
Попытать автора вот этой штуки :-)
Еще что-нибудь, надо подумать :-)
ЗЫ
Sparse voxel octree заюзать *trollface*

А вообще я не пойму смысла такого "бенчмарка", тут практически нечего тестировать, какой нафиг запись в массив, напишите реализацию какого-нить достаточно сложного мат. алгоритма и на нем тестируйте, еще бы сложение двух переменных потестировали :-D