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

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

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

- - Великая битва 4х языков программирования на простейшей задачке (http://forum.boolean.name/showthread.php?t=15917)

ffinder

26.11.2011 02:40

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

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

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

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

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

ffinder

26.11.2011 02:46

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

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

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

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

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

ffinder

26.11.2011 02:53

Ответ: Великая битва 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 мс

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

ffinder

26.11.2011 03:00

Ответ: Великая битва 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 мс

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

ffinder

26.11.2011 03:02

Ответ: Великая битва 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 раза.
Так и хочется спросить, Нотч, почему Майнкрафт так тормозит???

dsd	26.11.2011 03:22

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

Markova

26.11.2011 03:30

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

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

Randomize

26.11.2011 03:33

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

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

ffinder

26.11.2011 03:51

Ответ: Великая битва 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

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

Randomize

26.11.2011 03:52

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

Вложений: 1

Мой тест на 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

ffinder

26.11.2011 04:06

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

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

moka	26.11.2011 04:51

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

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

Платон Александрович

26.11.2011 06:13

Ответ: Великая битва 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д массивы - чистое нубство :)

Randomize

26.11.2011 06:28

Ответ: Великая битва 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) как это сделано в оригинальной игре)

Платон Александрович

26.11.2011 07:35

Ответ: Великая битва 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

Markova

26.11.2011 08:03

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

Цитата:

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

Вот… а теперь он не подолёку встал, ругается матом и пьет пива)
alloc 0 ms fill 247 ms

Платон Александрович спас положение!:super:

Платон Александрович

26.11.2011 08:38

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

Цитата:

Сообщение от Markova (Сообщение 211291)

про alloc 0 я пояснил почему - память не выделяется в случае такого массива (с квадратными скобками), он статичный, для него используется память из стека. Так что не считается, а то тут некоторые товарищи уже шум поднимают по поводу честности теста :-)

HolyDel

26.11.2011 09:21

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

Вложений: 1

эффективность работы программиста (когда дело касается не формошлепства) на С++ вещь спорная. такчто я вчеркнул его назад.

Код:

#include <iostream>

#include <Windows.h>



int main()

{

        int counter = 0;



        auto a = GetTickCount();



        int* map = new int[512*128*512];



        int allocate_time = GetTickCount() - a;



        a = GetTickCount();

        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)

                                {

                                        ++counter;

                                        map[512 * 128 * x + 128 * y + z] = counter;

                                }

                        }

                }

        }



        int fill_time = GetTickCount() - a;



        std::cout<<"allocate time:"<<allocate_time<<std::endl;

        std::cout<<"fill time:"<<(fill_time/20)<<std::endl;



        std::cin.get();

        return 0;

}

allocate - 0
fill - 17

ffinder

26.11.2011 11:55

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

Вариант HolyDel'а выдает:
выделение памяти под массив: 0 мс
время заполнения массива: 21 мс

Плюсы как всегда дают всем просраться грубой силой;)

ffinder

26.11.2011 12:30

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

Цитата:

Сообщение от MoKa (Сообщение 211283)

В .Net, используй в циклах ++x а не x++.

результат не изменился.

Цитата:

Сообщение от MoKa (Сообщение 211283)

И используй Jagged Array, он будет где-то в 2-3 раза быстрее.

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

ffinder

26.11.2011 12:45

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

Цитата:

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

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

тут согласен полностью.
перемерял, получилось:
выделение: 50 мс
заполнение: 678 мс

Цитата:

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

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

в данном случае, батенька Платон Александрович, нельзя оптимизировать даже немного. А вы тут bit-swizzling'ом индексы высчитываете. Если так, то и в остальных тестах индекс нужно расчитывать именно по такой формуле, а это нарушает условие "битвы", что писать код должно быть удобно и чисто.

Цитата:

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

В результате у меня аллокация ~0мс (ну это понятно, память со стека берется), заполнение ~210мс

вот тут не согласен категорически. массив занимает 128 мегабайт, на стеке такое просто не поместится. хотелось бы узнать, что Марк нахимичил с кодогенерацией и чем директива Local так ускоряет выделение памяти.

Цитата:

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

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

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

Платон Александрович

26.11.2011 14:32

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

Цитата:

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

А вы тут bit-swizzling'ом индексы высчитываете.

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

Цитата:

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

Если так, то и в остальных тестах индекс нужно расчитывать именно по такой формуле

По крайней мере для плюсов ненадо, компилятор оптимизирующий, он сам поймет что размеры константные, да еще степени двойки, и все сделает хорошо :) В отличие от блица :)

Цитата:

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

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

Цитата:

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

а если серьезно - то вы зацикливаетесь на хранении и сжатии данных, из расчета, что они будут статичными.

О статичном речи и не шло вообще, minecraft же. Жду пояснений по поводу

Цитата:

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

Всякие разреженные деревья не подходят.

BlackDragon

26.11.2011 16:05

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

Вложений: 1

johnk

27.11.2011 07:21

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

Вложений: 1

Чисто ради интереса перевел вариант HolyDel'a на Ди:

Код:

import std.c.windows.windows : GetTickCount;

import std.stdio : writef, readln;



void main()

{

        int counter = 0;

        auto current = GetTickCount();



        int[] map = new int[512 * 128 * 512];



        int allocationTime = GetTickCount() - current;



        current = GetTickCount();

        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)

                                {

                                        ++counter;

                                        map[512 * 128 * x + 128 * y + z] = counter;

                                }

                        }

                }

        }



        int fillingTime = GetTickCount() - current;



        writef("Allocation took: ", allocationTime, "ms\n");

        writef("Total filling time: ", fillingTime, "ms\n");

        writef("Average fill time per step: ", fillingTime/20, "ms\n");



        readln();

}

dmd 1.071, ключи компиляции: -inline -O -release.

У меня результаты странные:

Цитата:

Allocation took: 141ms
Total filling time: 1734ms
Average fill time per step: 86ms

Проверьте плиз кому не лень.

BlackDragon

27.11.2011 14:46

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

Цитата:

Сообщение от johnk (Сообщение 211392)

Проверьте плиз кому не лень.

Allocation took: 78 ms
Total filling time: 938 ms
Average fill time per step: 46 ms

HolyDel

28.11.2011 07:39

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

allocate 125
fill 84

выделение памяти действительно очень долгое. странно.

pax	28.11.2011 11:11

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

Вариант HolyDel'a на шарпе:

PHP код:


		
			
using System;

namespace speedTest
{
    static class Program
    {
        static int Main()
        {
            int counter = 0;

            var a = DateTime.Now.Ticks;

            var map = new int[512 * 128 * 512];

            var allocate_time = DateTime.Now.Ticks - a;

            a = DateTime.Now.Ticks;
            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)
                        {
                            ++counter;
                            map[512 * 128 * x + 128 * y + z] = counter;
                        }
                    }
                }
            }

            var fill_time = DateTime.Now.Ticks - a;
            Console.WriteLine("allocate time: {0}", allocate_time / 10000f);
            Console.WriteLine("fill time: {0}", (fill_time / 20f) / 10000f);
            Console.Read();
            return 0;
        }
    }
}

Результаты на рабочей машине (не той которая в подписи, а чуть по мощнее, но тоже i5)

allocate time: 1,0001
fill time: 43,00246

HolyDel

28.11.2011 11:29

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

Цитата:

И используй Jagged Array, он будет где-то в 2-3 раза быстрее.

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

упд. теория подтвердилась практикой:

Код:

using System;



namespace speedTest

{

    static class Program

    {

        static int Main()

        {

            int counter = 0;



            var a = DateTime.Now.Ticks;



            int[][][] map = new int[512][][];



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

            {

                map[y]= new int[128][];



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

                {

                    map[y][z] = new int[512];

                }

            }

            var allocate_time = DateTime.Now.Ticks - a;

            a = DateTime.Now.Ticks;

            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)

                        {

                            ++counter;

                            map[x][y][z] = counter;

                        }

                    }

                }

            }



            var fill_time = DateTime.Now.Ticks - a;

            Console.WriteLine("allocate time: {0}", allocate_time / 10000f);

            Console.WriteLine("fill time: {0}", (fill_time / 20f) / 10000f);

            Console.Read();

            return 0;

        }

    }

}

529 на аллокацию и 254 на заливку.
у меня вариант pax-а дает 2 на аллокацию и 176 на заливку.

AVL	28.11.2011 14:10

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

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

pax	28.11.2011 14:17

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

Цитата:

Сообщение от AVL (Сообщение 211493)

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

Так попробуй!

johnk

28.11.2011 14:44

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

Вложений: 1

Код:

import std.c.windows.windows : GetTickCount;

import std.stdio : writefln, readln;



void main()

{

    int counter = 0;

    auto current = GetTickCount();



    scope map = new int[512 * 128 * 512];



    int allocationTime = GetTickCount() - current;



    writefln("Allocation took: %dms", allocationTime);



    current = GetTickCount();

    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)

                {

                    ++counter;

                    map[512 * 128 * x + 128 * y + z] = counter;

                }

            }

        }

    }



    int fillingTime = GetTickCount() - current;



    writefln("Total filling time: %dms", fillingTime);

    writefln("Average fill time per step: %dms", fillingTime/20);



    readln();

}

Версия для D 2.056.
Результаты чуток получше, но, увы...

Цитата:

Allocation took: 125ms
Total filling time: 1609ms
Average fill time per step: 80ms

Ди, к сожалению, далеко не конкурент С++ :mad:

moka	28.11.2011 16:23

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

Сделал 3 теста на C#, первый вариант, затем тот что PAX'а, и потом jagged от HolyDel'а.
В общем результаты такие:
Multidimensional:
Allocate: 1.6ms
Fill: 712.95ms
Get(65536 times): 1.03ms

Flattened:
Allocate: 1.6ms
Fill: 223.68ms
Get(65536 times): 0.62ms

Jagged:
Allocate: 448.18ms
Fill: 296.11ms
Get(65536 times): 0.46ms

Intel Pentium 4 CPU 3.00Ghz (2 CPUs)

Получается, работа в общем с Flatenned на C# в основном самый быстрый способ. Но с Jagged, если использовать статический массив, то доступ к данным будет быстрее.
Учитывая постоянный доступ, если он будет необходим, лучше всё таки использовать именно Jagged массив. А если нужен динамичный, то Flatten. Обычный мультиразмерный - естественно идёт мимо.

HolyDel

28.11.2011 17:27

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

и намного ты быстрее напишешь, чем cl.exe нагенерит?

Код:

; 23   : ++counter;

        inc        esi

; 24   : map[512 * 128 * x + 128 * y + z] = counter;

        mov        DWORD PTR [eax], esi

        add        eax, 4

        dec        ecx

        jne        SHORT $LL3@main

Платон Александрович

28.11.2011 18:14

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

Вложений: 1

Цитата:

Сообщение от HolyDel (Сообщение 211522)

и намного ты быстрее напишешь, чем cl.exe нагенерит?

Код:

; 23   : ++counter;

        inc        esi

; 24   : map[512 * 128 * x + 128 * y + z] = counter;

        mov        DWORD PTR [eax], esi

        add        eax, 4

        dec        ecx

        jne        SHORT $LL3@main

какое-то двусмысленное выражение :)
если написать в смысле напечатать, то быстрее не смогу :-), а если написать код который был бы быстрее, то вот
раза в два быстрее *trollface*

Код:

mov eax, 1

@@:

    movnti dword [ebp], eax

    add ebp, 4

    inc eax

test eax, 512 * 128 * 512 - 1

jnz @b

диалект fasm
ЗЫ
полный сырок

Код:

format PE console

entry start



include 'macro/import32.inc'

include 'macro/proc32.inc'



section '.data' data readable writeable



    text_alloc db 'allocation time %d ms', 13, 10, 0

    text_fill db 'fill time %d ms', 13, 10, 0



section 'code' code readable executable



start:



    stdcall [timeBeginPeriod], 1



    stdcall [timeGetTime]

    mov [esp+4], eax



    stdcall [GetProcessHeap]



    stdcall [HeapAlloc], eax, 0, 512 * 128 * 512 * 4

    mov ebp, eax



    stdcall [timeGetTime]

    mov [esp+8], eax



    mov eax, 1

    @@:

        movnti dword [ebp], eax

        add ebp, 4

        inc eax

    test eax, 512 * 128 * 512 - 1

    jnz @b



    stdcall [timeGetTime]

    mov [esp+12], eax



    stdcall [timeEndPeriod], 1



    mov eax, [esp+8]

    sub eax, [esp+4]

    ccall [printf], text_alloc, eax



    mov eax, [esp+12]

    sub eax, [esp+8]

    ccall [printf], text_fill, eax



    stdcall [ExitProcess], 0



section 'idata' import data readable



        library\

           kernel32, 'kernel32.dll',\

           winmm, 'winmm.dll',\

           msvcrt, 'msvcrt.dll'



        import kernel32,\

                    GetProcessHeap, 'GetProcessHeap',\

                    HeapAlloc, 'HeapAlloc',\

                    ExitProcess, 'ExitProcess',\

                    GetTickCount, 'GetTickCount'



        import winmm,\

                 timeBeginPeriod, 'timeBeginPeriod',\

                 timeGetTime, 'timeGetTime',\

                 timeEndPeriod, 'timeEndPeriod'



        import msvcrt,\

                  printf, 'printf'

HolyDel

28.11.2011 19:30

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

Платон, при всем уважении, твой ексешник у меня работает 36-43 мс. а сгенирированный студией 16 (если одна итерация, как у тебя, и 12, если итераций 20 как в исходном примере) такчто студия в два раза *trollface* fasm-а.

i7 - 2600K 3.4, 16GB, Win7 64 bit

ffinder

28.11.2011 19:33

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

Цитата:

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

странно, но твой код дает дикий разброс времени выполнения от 60 до 340 мс.
но, учитывая, что джава может за 43 мс, то 60 на асме - это абсолютный фейл.
Да, "зоопарк" архитектур убил асм, как средство оптимизации.
ЗЫ: Core i3 Sandy Bridge

HolyDel

28.11.2011 19:34

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

такчто плюсы грубой силой дали просраться даже asm-у :)

johnk, второй вариант на D 31, 19. уже очень близко к крестам.

AVL	28.11.2011 19:51

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

Вложений: 1

Код:

var

  c:integer;

  n,t:integer;



procedure fill;

var

  a:array[1..512,1..128,1..512] of integer;

  i,j,k:integer;

begin

  writeln('allocation:',(milliseconds-n));

  n:=milliseconds;

  c:=1;

  for i:=1 to 512 do

    for j:=1 to 128 do

      for k:=1 to 512 do begin

        a[i,j,k]:=c;

        c:=c+1;

      end;

  t:=milliseconds-n;

  writeln('filling:',t);

end;

begin

  n:=milliseconds;

  fill;

end.

PascalABC.NET:
allocation:546
filling:891

MidletPascal: (эмулятор KEmulator Lite)
allocation: 515
filling: 234 // :4to:

Железо - P4 3.2 GHz

HolyDel

28.11.2011 20:10

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

AVL, ну ексешник же... дай.

Платон Александрович

28.11.2011 20:13

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

Цитата:

Сообщение от HolyDel (Сообщение 211546)

Ну значит не судьба :) Надежда была на единственную (остальной-то код ничем не отличается от студийного) инструкцию movnti которая кеш не дергает за счет чего быстрее выполняется, но видимо в новых пеньках это не так. У меня 4ый.
Можно еще попробывать SSE, но врятли будет профит на таком простом заполнении памяти.

Цитата:

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

Да-да, все из-за специфичной movnti :) Но можно оптимизировать под основные ходовые процессоры и на старте выбирать по используемому процессору, тогда будет хорошо :)

ЗЫ
Как здесь удалять мессаги-то? Не вижу такой кнопки

ffinder

28.11.2011 20:18

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

Цитата:

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

Да-да, все из-за специфичной movnti :) Но можно оптимизировать под основные ходовые процессоры и на старте выбирать по используемому процессору, тогда будет хорошо :)

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

pax	28.11.2011 21:07

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

Ну чо, выбор ложиться на C# или на яву?

johnk

28.11.2011 21:23

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

бери Nemerle :-)

.Squid

28.11.2011 22:26

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

C++ FTW!

HolyDel

28.11.2011 23:52

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

Цитата:

Получается, работа в общем с Flatenned на C# в основном самый быстрый способ. Но с Jagged, если использовать статический массив, то доступ к данным будет быстрее.

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

ffinder

29.11.2011 00:19

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

Цитата:

Сообщение от HolyDel (Сообщение 211607)

с flatten надо просто выполнить несколько арифмитических операций, чтобы вычислить индекс, а с jagged нужны как минимум два обращения к памяти. покажи код.

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

HolyDel

29.11.2011 11:05

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

да не, на верхнем уровне по любому должно быть дерево. просто на ноде дерева должен висеть не один кубик, а массив 16х16х16 например.

moka	29.11.2011 15:20

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

Вот снова затестил, такой результат:

Multidimensional allocate: 1.258ms
Multidimensional fill: 701.627ms
Multidimensional get 65536 times: 1.09ms
Flattened allocate: 1.751ms
Flattened fill: 212.648ms
Flattened get 65536 times: 0.331ms
Jagged allocate: 460.847ms
Jagged fill: 286.233ms
Jagged get 65536 times: 0.455ms

Вот код с тремя вариантами:

PHP код:


		
			
using System;

using System.Diagnostics;

using System.Threading;



namespace speedTest {

    static class Program {

        static int Main() {

            int counter = 0;



            Stopwatch timer = new Stopwatch();



            Thread.Sleep(100);



            { // Multidimensional

                long elapsedAllocation, elapsedFill, elapsedGet, number;



                timer.Restart();



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



                elapsedAllocation = timer.ElapsedTicks;

                Console.WriteLine("Multidimensional allocate: {0}ms", Math.Round(elapsedAllocation * 1000f / Stopwatch.Frequency, 3));

                timer.Restart();



                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++) {

                                ++counter;

                                map[x, y, z] = counter;

                            }

                        }

                    }

                }



                elapsedFill = timer.ElapsedTicks;

                Console.WriteLine("Multidimensional fill: {0}ms", Math.Round((elapsedFill / 20f) * 1000f / Stopwatch.Frequency, 3));

                timer.Restart();



                for (int i = 0; i < 65536; ++i) {

                    number = map[100, 10, 100];

                }



                elapsedGet = timer.ElapsedTicks;

                Console.WriteLine("Multidimensional get 65536 times: {0}ms", Math.Round(elapsedGet * 1000f / Stopwatch.Frequency, 3));

            }



            Thread.Sleep(100);



            { // Flattened

                long elapsedAllocation, elapsedFill, elapsedGet, number;



                timer.Restart();



                int[] map = new int[512 * 128 * 512];



                elapsedAllocation = timer.ElapsedTicks;

                Console.WriteLine("Flattened allocate: {0}ms", Math.Round(elapsedAllocation * 1000f / Stopwatch.Frequency, 3));

                timer.Restart();



                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++) {

                                ++counter;

                                map[512 * 128 * x + 128 * y + z] = counter;

                            }

                        }

                    }

                }



                elapsedFill = timer.ElapsedTicks;

                Console.WriteLine("Flattened fill: {0}ms", Math.Round((elapsedFill / 20f) * 1000f / Stopwatch.Frequency, 3));

                timer.Restart();



                for (int i = 0; i < 65536; ++i) {

                    number = map[512*128*100+128*10+100];

                }



                elapsedGet = timer.ElapsedTicks;

                Console.WriteLine("Flattened get 65536 times: {0}ms", Math.Round(elapsedGet * 1000f / Stopwatch.Frequency, 3));

            }



            Thread.Sleep(100);



            { // Jagged

                long elapsedAllocation, elapsedFill, elapsedGet, number;



                timer.Restart();



                int[][][] map = new int[512][][];

                for (int y = 0; y < 512; ++y) {

                    map[y] = new int[128][];



                    for (int z = 0; z < 128; ++z) {

                        map[y][z] = new int[512];

                    }

                }



                elapsedAllocation = timer.ElapsedTicks;

                Console.WriteLine("Jagged allocate: {0}ms", Math.Round(elapsedAllocation * 1000f / Stopwatch.Frequency, 3));

                timer.Restart();



                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++) {

                                ++counter;

                                map[x][y][z] = counter;

                            }

                        }

                    }

                }



                elapsedFill = timer.ElapsedTicks;

                Console.WriteLine("Jagged fill: {0}ms", Math.Round((elapsedFill / 20f) * 1000f / Stopwatch.Frequency, 3));

                timer.Restart();



                for (int i = 0; i < 65536; ++i) {

                    number = map[100][10][100];

                }



                elapsedGet = timer.ElapsedTicks;

                Console.WriteLine("Jagged get 65536 times: {0}ms", Math.Round(elapsedGet * 1000f / Stopwatch.Frequency, 3));

            }





            Console.Read();

            return 0;

        }

    }

}

HolyDel

29.11.2011 17:15

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

Вложений: 1

оно берется с кэша! Мока!

Код:

using System;

using System.Diagnostics;

using System.Threading;



namespace speedTest

{

    static class Program

    {

        public struct index

        {

            public int x, y, z;

        };



        static int Main()

        {

            int counter = 0;



            int count_values = 512 * 128 * 512;







            index[] ordered_values = new index[count_values];

            index[] random_values = new index[count_values];



            {

                int x = 0, y = 0, z = 0;

                Random r = new Random();



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

                {



                    ordered_values[i].x = z;

                    ordered_values[i].y = y;

                    ordered_values[i].z = x;



                    x++;

                    if (x > 511)

                    {

                        x = 0;

                        y++;

                    }

                    if (y > 127)

                    {

                        y = 0;

                        z++;

                    }





                    random_values[i].x = r.Next(511);

                    random_values[i].y = r.Next(127);

                    random_values[i].z = r.Next(511);

                }

            }

            Stopwatch timer = new Stopwatch();



            Thread.Sleep(100);



            { // Multidimensional 

                long elapsedAllocation, elapsedFill, elapsedGet, number;



                timer.Restart();



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



                elapsedAllocation = timer.ElapsedTicks;

                Console.WriteLine("Multidimensional allocate: {0}ms", Math.Round(elapsedAllocation * 1000f / Stopwatch.Frequency, 3));

                timer.Restart();



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

                            {

                                ++counter;

                                map[x, y, z] = counter;

                            }

                        }

                    }

                }



                elapsedFill = timer.ElapsedTicks;

                Console.WriteLine("Multidimensional fill: {0}ms", Math.Round((elapsedFill / 20f) * 1000f / Stopwatch.Frequency, 3));

                timer.Restart();



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

                {

                    number = map[ordered_values[i].x, ordered_values[i].y, ordered_values[i].z];

                }



                elapsedGet = timer.ElapsedTicks;

                Console.WriteLine("Multidimensional get all times (ordered): {0}ms", Math.Round(elapsedGet * 1000f / Stopwatch.Frequency, 3));



                timer.Restart();



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

                {

                    number = map[random_values[i].x, random_values[i].y, random_values[i].z];

                }



                elapsedGet = timer.ElapsedTicks;

                Console.WriteLine("Multidimensional get all times (random): {0}ms", Math.Round(elapsedGet * 1000f / Stopwatch.Frequency, 3));

            }



            Thread.Sleep(100);



            { // Flattened 

                long elapsedAllocation, elapsedFill, elapsedGet, number;



                timer.Restart();



                int[] map = new int[512 * 128 * 512];



                elapsedAllocation = timer.ElapsedTicks;

                Console.WriteLine("Flattened allocate: {0}ms", Math.Round(elapsedAllocation * 1000f / Stopwatch.Frequency, 3));

                timer.Restart();



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

                            {

                                ++counter;

                                map[512 * 128 * x + 128 * y + z] = counter;

                            }

                        }

                    }

                }



                elapsedFill = timer.ElapsedTicks;

                Console.WriteLine("Flattened fill: {0}ms", Math.Round((elapsedFill / 20f) * 1000f / Stopwatch.Frequency, 3));

                timer.Restart();



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

                {

                    number = map[512 * 128 * ordered_values[i].x + 128 * ordered_values[i].y + ordered_values[i].z];

                }



                elapsedGet = timer.ElapsedTicks;

                Console.WriteLine("Flattened get all times (ordered): {0}ms", Math.Round(elapsedGet * 1000f / Stopwatch.Frequency, 3));



                timer.Restart();



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

                {

                    number = map[512 * 128 * random_values[i].x + 128 * random_values[i].y + random_values[i].z];

                }



                elapsedGet = timer.ElapsedTicks;

                Console.WriteLine("Flattened get all times (random): {0}ms", Math.Round(elapsedGet * 1000f / Stopwatch.Frequency, 3));

            }



            Thread.Sleep(100);



            { // Jagged 

                long elapsedAllocation, elapsedFill, elapsedGet, number;



                timer.Restart();



                int[][][] map = new int[512][][];

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

                {

                    map[y] = new int[128][];



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

                    {

                        map[y][z] = new int[512];

                    }

                }



                elapsedAllocation = timer.ElapsedTicks;

                Console.WriteLine("Jagged allocate: {0}ms", Math.Round(elapsedAllocation * 1000f / Stopwatch.Frequency, 3));

                timer.Restart();



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

                            {

                                ++counter;

                                map[x][y][z] = counter;

                            }

                        }

                    }

                }



                elapsedFill = timer.ElapsedTicks;

                Console.WriteLine("Jagged fill: {0}ms", Math.Round((elapsedFill / 20f) * 1000f / Stopwatch.Frequency, 3));

                timer.Restart();



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

                {

                    number = map[ordered_values[i].x][ordered_values[i].y][ordered_values[i].z];

                }



                elapsedGet = timer.ElapsedTicks;

                Console.WriteLine("Jagged get all times (ordered): {0}ms", Math.Round(elapsedGet * 1000f / Stopwatch.Frequency, 3));



                timer.Restart();



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

                {

                    number = map[random_values[i].x][random_values[i].y][random_values[i].z];

                }



                elapsedGet = timer.ElapsedTicks;

                Console.WriteLine("Jagged get all times (random): {0}ms", Math.Round(elapsedGet * 1000f / Stopwatch.Frequency, 3));

            }





            Console.Read();

            return 0;

        }

    }

}

вот вариант с последовательнам и рандомным доступом:
MD
allocate 6
fill 198
get(order) 149
get(rand) 956
FLAT
allocate 0.21
fill 39
get(order) 62.5 \ ??WTF
get(rand) 59.58 / ??WTF
JAGGED
allocate 210
fill 52
get(order) 92
get(rand) 677

pax	29.11.2011 17:22

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

Мои результаты (i5-2500K 3.3ГГц):

Multidimensional allocate: 4,948ms
Multidimensional fill: 218,264ms
Multidimensional get 65536 times: 0,148ms
Flattened allocate: 0,239ms
Flattened fill: 45,047ms
Flattened get all times (ordered): 60,754ms
Flattened get all times (random): 65,615ms
Jagged allocate: 182,714ms
Jagged fill: 66,86ms
Jagged get all times (ordered): 99,008ms
Jagged get all times (random): 748,584ms

HolyDel

29.11.2011 17:29

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

вот у тебя тоже наблюдается аномалия на flatten. ordered тоже должен быть быстрее, чем random. но почему то нет. кто сможет объяснить почему?

правка: короче ето из-за оптимизирующего компилятора. вот так:

Код:

   elapsedFill = timer.ElapsedTicks;

                Console.WriteLine("Flattened fill: {0}ms", Math.Round((elapsedFill / 20f) * 1000f / Stopwatch.Frequency, 3));

                timer.Restart();

                int number1 = 0;

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

                {

                    number1 += map[512 * 128 * ordered_values[i].x + 128 * ordered_values[i].y + ordered_values[i].z];

                }



                elapsedGet = timer.ElapsedTicks;

                Console.WriteLine("Flattened get all times (ordered): {0}ms number  = {1}", Math.Round(elapsedGet * 1000f / Stopwatch.Frequency, 3),number1);



                timer.Restart();

                number1 = 0;

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

                {

                    number1 += map[512 * 128 * random_values[i].x + 128 * random_values[i].y + random_values[i].z];

                }



                elapsedGet = timer.ElapsedTicks;

                Console.WriteLine("Flattened get all times (random): {0}ms number  = {1}", Math.Round(elapsedGet * 1000f / Stopwatch.Frequency, 3),number1);

все возвращается на свои места 78 ordered, 533 random.

HolyDel

29.11.2011 17:38

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

причем на плюсах:

Код:

#include <iostream>

#include <Windows.h>

#include <cstdlib>



 struct index

{

    int x, y, z;

};





int main()

{



        int count_values = 512 * 128 * 512;







    index *ordered_values = new index[count_values];

    index *random_values = new index[count_values];



    {

        int x = 0, y = 0, z = 0;



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

        {



            ordered_values[i].x = z;

            ordered_values[i].y = y;

            ordered_values[i].z = x;



            x++;

            if (x > 511)

            {

                x = 0;

                y++;

            }

            if (y > 127)

            {

                y = 0;

                z++;

            }





            random_values[i].x = rand()%512;

            random_values[i].y = rand()%128;

            random_values[i].z = rand()%512;

        }

    }



        int counter = 0;



        auto a = GetTickCount();



        int* map = new int[512*128*512];



        int allocate_time = GetTickCount() - a;



        a = GetTickCount();

        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)

                                {

                                        ++counter;

                                        map[512 * 128 * x + 128 * y + z] = counter;

                                }

                        }

                }

        }



        int fill_time = GetTickCount() - a;



        a = GetTickCount();

        int value = 0;

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

        {

                value += map[512 * 128 * ordered_values[i].x + 128 * ordered_values[i].y + ordered_values[i].z];

        }

        int ordered_time = GetTickCount() - a;

        std::cout<<"value:"<<value<<std::endl;

        a = GetTickCount();

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

        {

                value += map[512 * 128 * random_values[i].x + 128 * random_values[i].y + random_values[i].z];

        }

        int random_time = GetTickCount() - a;

        std::cout<<"value:"<<value<<std::endl;



        std::cout<<"allocate time:"<<allocate_time<<std::endl;

        std::cout<<"fill time:"<<(fill_time/20)<<std::endl;

        std::cout<<"ordered time:"<<ordered_time<<std::endl;

        std::cout<<"random time:"<<random_time<<std::endl;



        std::cin.get();

        return 0;

}

дает вполне ожидаемые 46 для ordered и 390 для random;
естественно, сюда еще входит время обращение к массиву для получения индекса.

moka	29.11.2011 18:09

Что-то я не смог избавиться от "оптимизаций компилятором", которые ухудшили результат получения данных при ordered и random индексах..

UPD: получилось.

Intel Pentium 4 3.00 Ghz

UPD2:
Вот такие результаты:

Код:

array size: 512 * 128 * 512 = 33554432

 --- Multidimensional

allocate:               25.945ms

fill:                   8221.827ms

get Ordered:            6834.768ms

get Random Order:       10833.646ms

 --- Flattened

allocate:               39.469ms

fill:                   985.824ms

get Ordered:            5357.747ms

get Random Order:       2922.386ms

 --- Jagged

allocate:               3119.915ms

fill:                   328.575ms

get Ordered:            6037.242ms

get Random Order:       8589.737ms

И вот такие результаты на более малого размера объём:

Код:

array size: 256 * 64 * 256 = 4194304

 --- Multidimensional

allocate:               2.107ms

fill:                   99.551ms

get Ordered:            96.638ms

get Random Order:       401.702ms

 --- Flattened

allocate:               0.201ms

fill:                   50.118ms

get Ordered:            49.65ms

get Random Order:       281.263ms

 --- Jagged

allocate:               39.366ms

fill:                   39.935ms

get Ordered:            50.619ms

get Random Order:       390.059ms

Заметьте, что в более малого объёма, как раз есть оптимизация на основе сортировки, а в большом нету..
Это случаем не потому что там идёт какое-то разбиение участка памяти на куски из-за слишком больших размеров?

Вот код обновил:

PHP код:


		
			
using System;
using System.Diagnostics;
using System.Threading;

namespace speedTest {
    static class Program {
        public struct index {
            public int x, y, z;
        };

        static int Main() {
            long elapsed, number;
            int width  = 256;
            int height = 64;
            int depth  = 256;
            int volume = width * height * depth;

            Console.WriteLine("array size: {0} * {1} * {2} = {3}", width, height, depth, volume);

            index[] indicesOrdered = new index[volume];
            index[] indicesRandom = new index[volume];

            { // fill up get values
                Random rnd = new Random();
                int i = 0;

                for (int z = 0; z < depth; ++z) {
                    for (int y = 0; y < height; ++y) {
                        for (int x = 0; x < width; ++x) {
                            indicesOrdered[i].x = z;
                            indicesOrdered[i].y = y;
                            indicesOrdered[i].z = x;

                            indicesRandom[i].x = rnd.Next(width);
                            indicesRandom[i].y = rnd.Next(height);
                            indicesRandom[i].z = rnd.Next(depth);

                            ++i;
                        }
                    }
                }
            }

            Stopwatch timer = new Stopwatch();

            Console.WriteLine(" --- Multidimensional");
            Thread.Sleep(100);

            { // Multidimensional
                int counter = 0;

                timer.Restart();

                int[,,] map = new int[width, height, depth];

                elapsed = timer.ElapsedTicks;
                Console.WriteLine("allocate: \t\t{0}ms", Math.Round(elapsed * 1000f / Stopwatch.Frequency, 3));
                timer.Restart();

                for (int x = 0; x < width; x++) {
                    for (int y = 0; y < height; y++) {
                        for (int z = 0; z < depth; z++) {
                            ++counter;
                            map[x, y, z] = counter;
                        }
                    }
                }

                elapsed = timer.ElapsedTicks;
                Console.WriteLine("fill: \t\t\t{0}ms", Math.Round(elapsed * 1000f / Stopwatch.Frequency, 3));
                timer.Restart();

                for (int i = 0; i < volume; ++i) {
                    number = map[indicesOrdered[i].x, indicesOrdered[i].y, indicesOrdered[i].z];
                }

                elapsed = timer.ElapsedTicks;
                Console.WriteLine("get Ordered: \t\t{0}ms", Math.Round(elapsed * 1000f / Stopwatch.Frequency, 3));
                timer.Restart();

                for (int i = 0; i < volume; ++i) {
                    number = map[indicesRandom[i].x, indicesRandom[i].y, indicesRandom[i].z];
                }

                elapsed = timer.ElapsedTicks;
                Console.WriteLine("get Random Order: \t{0}ms", Math.Round(elapsed * 1000f / Stopwatch.Frequency, 3));
            }

            Console.WriteLine(" --- Flattened");
            Thread.Sleep(100);

            { // Flattened
                int counter = 0;

                timer.Restart();

                int[] map = new int[width * height * depth];

                elapsed = timer.ElapsedTicks;
                Console.WriteLine("allocate: \t\t{0}ms", Math.Round(elapsed * 1000f / Stopwatch.Frequency, 3));
                timer.Restart();

                for (int x = 0; x < width; x++) {
                    for (int y = 0; y < height; y++) {
                        for (int z = 0; z < depth; z++) {
                            ++counter;
                            map[width * height * x + height * y + z] = counter;
                        }
                    }
                }

                elapsed = timer.ElapsedTicks;
                Console.WriteLine("fill: \t\t\t{0}ms", Math.Round(elapsed * 1000f / Stopwatch.Frequency, 3));
                timer.Restart();

                for (int i = 0; i < volume; ++i) {
                    number = map[width * height * indicesOrdered[i].x + height * indicesOrdered[i].y + indicesOrdered[i].z];
                }

                elapsed = timer.ElapsedTicks;
                Console.WriteLine("get Ordered: \t\t{0}ms", Math.Round(elapsed * 1000f / Stopwatch.Frequency, 3));
                timer.Restart();

                for (int i = 0; i < volume; ++i) {
                    number = map[width * height * indicesRandom[i].x + height * indicesRandom[i].y + indicesRandom[i].z];
                }

                elapsed = timer.ElapsedTicks;
                Console.WriteLine("get Random Order: \t{0}ms", Math.Round(elapsed * 1000f / Stopwatch.Frequency, 3));
            }

            Console.WriteLine(" --- Jagged");
            Thread.Sleep(100);

            { // Jagged
                int counter = 0;

                timer.Restart();

                int[][][] map = new int[width][][];
                for (int y = 0; y < width; ++y) {
                    map[y] = new int[height][];

                    for (int z = 0; z < height; ++z) {
                        map[y][z] = new int[depth];
                    }
                }

                elapsed = timer.ElapsedTicks;
                Console.WriteLine("allocate: \t\t{0}ms", Math.Round(elapsed * 1000f / Stopwatch.Frequency, 3));
                timer.Restart();

                for (int x = 0; x < width; x++) {
                    for (int y = 0; y < height; y++) {
                        for (int z = 0; z < depth; z++) {
                            ++counter;
                            map[x][y][z] = counter;
                        }
                    }
                }

                elapsed = timer.ElapsedTicks;
                Console.WriteLine("fill: \t\t\t{0}ms", Math.Round(elapsed * 1000f / Stopwatch.Frequency, 3));
                timer.Restart();

                for (int i = 0; i < volume; ++i) {
                    number = map[indicesOrdered[i].x][indicesOrdered[i].y][indicesOrdered[i].z];
                }

                elapsed = timer.ElapsedTicks;
                Console.WriteLine("get Ordered: \t\t{0}ms", Math.Round(elapsed * 1000f / Stopwatch.Frequency, 3));
                timer.Restart();

                for (int i = 0; i < volume; ++i) {
                    number = map[indicesRandom[i].x][indicesRandom[i].y][indicesRandom[i].z];
                }

                elapsed = timer.ElapsedTicks;
                Console.WriteLine("get Random Order: \t{0}ms", Math.Round(elapsed * 1000f / Stopwatch.Frequency, 3));
            }
            Console.Read();
            return 0;
        }
    }
}

pax	29.11.2011 18:15

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

Результаты:

array size: 256 * 64 * 256 = 4194304
--- Multidimensional
allocate: 0,743ms
fill: 37,29ms
get Ordered: 16,391ms
get Random Order: 86,846ms
--- Flattened
allocate: 0,073ms
fill: 12,771ms
get Ordered: 13,568ms
get Random Order: 12,551ms
--- Jagged
allocate: 10,595ms
fill: 10,976ms
get Ordered: 12,797ms
get Random Order: 56,314ms

array size: 512 * 128 * 512 = 33554432
--- Multidimensional
allocate: 7,78ms
fill: 258,828ms
get Ordered: 133,145ms
get Random Order: 791,616ms
--- Flattened
allocate: 0,283ms
fill: 55,868ms
get Ordered: 64,609ms
get Random Order: 64,498ms
--- Jagged
allocate: 175,661ms
fill: 86,344ms
get Ordered: 95,213ms
get Random Order: 741,485ms

moka	29.11.2011 18:38

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

Вот ещё потестил, и вывел в виде % кто превосходит или уступает multidimensional массиву, отфильтровав (сверху самые быстрые).

Код:

array size: 256 * 64 * 256 = 4194304



alloc:

flat (907%) = 0.201ms

mult (100%) = 1.823ms

jagg (4%) = 42.266ms



fill:

flat (204%) = 50.041ms

jagg (180%) = 56.568ms

mult (100%) = 101.929ms



get ordered:

flat (193%) = 49.872ms

jagg (190%) = 50.646ms

mult (100%) = 96.195ms



get random:

flat (141%) = 275.65ms

mult (100%) = 388.513ms

jagg (99%) = 391.662ms

Код:

array size: 512 * 128 * 512 = 33554432



alloc:

flat (1019%) = 1.249ms

mult (100%) = 12.728ms

jagg (2%) = 646.334ms



fill:

jagg (227%) = 333.841ms

flat (192%) = 395.861ms

mult (100%) = 758.735ms



get ordered:

jagg (178%) = 404.737ms

flat (132%) = 544.013ms

mult (100%) = 719.182ms



get random:

flat (118%) = 2809.882ms

mult (100%) = 3304.364ms

jagg (76%) = 4329.8ms

ffinder

27.09.2012 00:49

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

вот еще один бенчмарк в копилку. язык F# (для .NET)
постарался товарищ boxxyfag

Код:

open System

open Microsoft.FSharp.Collections



let beforeAllocation = DateTime.Now

let yobaArray        = Array3D.zeroCreate 512 512 128

let afterAllocation  = DateTime.Now

let mutable i = 0

for n in 1..20 do 

    for x in 0..511 do 

    for y in 0..511 do 

    for z in 0..127 do 

        yobaArray.[x, y, z] <- i

        i <- i + 1

let afterLoop       = DateTime.Now

let totalLoopTime   = afterLoop - afterAllocation

let averageLoopTime = new TimeSpan(totalLoopTime.Ticks / 20L)

printfn "Allocation time: %A"   <| afterAllocation - beforeAllocation

printfn "Total loop time: %A"   <| totalLoopTime

printfn "Average loop time: %A" <| averageLoopTime 

Console.ReadLine()              |> ignore

результаты:
Microsoft (R) F# 2.0 Interactive build 4.0.40219.1
Windows 7 Pro 32
Amd turion rm-74 2,20 GHz

Allocation time: 00:00:00.0040002
Total loop time: 00:00:21.1218322
Average loop time: 00:00:01.0560916

ffinder

27.09.2012 00:50

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

код на F# с аллокацией и одновременной инициализацией массива:

Код:

open System

open Microsoft.FSharp.Collections;



let finalValues =

    let arrSize = 512 * 512 * 128

    let start = 19 * arrSize

    seq { for i in 0..arrSize-1 -> start + i } 

    

let enumerator = finalValues.GetEnumerator()

let getNext _ _ _ = 

    enumerator.MoveNext()

    enumerator.Current



let timeBefore = DateTime.Now

let yobaArray  = Array3D.init 512 512 128 getNext

let timeAfter  = DateTime.Now

printfn "Allocation and init time: %A" <| timeAfter - timeBefore



Console.ReadLine()

результаты:
Allocation and init time: 00:00:13.5615343

ffinder

27.09.2012 00:53

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

код на фортране, который должен по идее был всех победить, но у аффтара с рекордом не вышло ;)
автор: zxc

Код:

      integer before(3), after(3), I, J, K, N 

      real loop_time_min, loop_time_sec, avg

      dimension A(512, 512, 128)

      call itime(before)     

      

      ! nowN - array for time 1/2/3 -> h/m/s

      do 1 N = 1, 20  

        do 2 I = 1, 512

          do 3 J = 1, 512

            do 4 K = 1, 512

              A(I, J, K) = N

    4       continue

    3     continue

    2   continue

    1 continue         



      CALL itime(after)

      loop_time_min = after(2) - before(2)

      loop_time_sec = after(3) - before(3)

      avg = (loop_time_min*60+loop_time_sec)/20

      WRITE(*,*) "Loop Time: ", loop_time_min, loop_time_sec 



      stop

      end

результаты:

Celeron(R) Dual-Core CPU T3500 @ 2.10GHz
Loop Time: 0.0000000 31.000000
AVG: 1.5500000

Часовой пояс GMT +4, время: 02:43.