Быстрый доступ к 2D-массиву во флэше

    Задача простая и типичная. Есть большой двумерный массив. И нам хочется наиболее эффективно с ним работать. В моем случае, меня интересовал массив чисел (байт).

    Что ж… Самое простое, что приходит на ум — это воспользоваться стандартным двумерным массивом типа и обращаться к элементам на манер a[x][y]. Но насколько это эффективно? Возможно, будет быстрее оперировать с одномерным массивом и обращаться к элементам как a[x + y*size_x]?

    Чтобы расставить все точки над i, я написал тест, который проверяет скорость чтения и записи различных вариантов массивов.

    На ум пришли следующие варианты:
    • 2-мерный нетипизированный массив (Array)
    • 1-мерный нетипизированный массив (Array)
    • 2-мерный типизированный массив (Vector.<Vector.<int>>)
    • 1-мерный типизированный массив (Vector.<int>)
    • Использование BitmapData как хранилища и setPixel/getPixel для доступа
    • 1-мерный массив байт (ByteArray)
    • Ну, и наконец, изврат. Обращение к ByteArray, ускоренное средствами быстрого доступа к памяти технологии Alchemy

    Итак, я написал небольшой тест для сравнения скорости выполнения кода. В тесте производилась имитация чтения и записи всех элементов массива 1500х1500 точек. Каждая операция выполнялась 5 раз и бралось среднее время.

    Также, естественно, динамические массивы были заранее созданы и наполнены элементами (т.е. новые элементы не добавлялись во время тестовых замеров).

    Итак, что получилось:



    Диаграмма:



    Выводы очевидны.

    Исходный код выложил сюда: wonderfl.net/c/d58d
    Share post

    Similar posts

    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 47

      +6
      Для полноты картины код нужен.
        +3
        да он не то, что бы для полноты картины нужен. просто результаты тестов странные. у меня они другие.
          0
          Посоветуйте, куда выложить код — выложу. В топик не хочу, т.к. код получился весьма объемный.
            +1
              0
              Спасибо! Сейчас размещу код в топике.
                0
                я правильно понимаю, что для теста алхимии вы не преобразовывали байткод, а оставили его в виде вызовов методов?
                  0
                  Нет, конечно. После компиляции я прошелся по нему утилиткой, преобразовывающий байткод.
                    0
                    ну тогда очень странно. у меня алхимия быстрее всего.
                    попробуйте убрать высчитываение длинны в итерациях.
                    ASIZE * ASIZE у вас высчитывается при каждом входе в итерацию.
                      0
                      Да, как-то не подумал, что умножение будет вносить какой-то impact.

                      Но все равно, коренным образом ничего не изменилось:

                      1D Vector — write: 23 ms.
                      1D Vector — read: 25 ms.
                      ByteArray — write: 134 ms.
                      ByteArray — read: 97 ms.
                      Alchemy ByteArray — write: 49 ms.
                      Alchemy ByteArray — read: 54 ms.
                        0
                        ну в общем я не знаю. я использую алхимию постоянно, у меня она минимум в 2 раза быстрее векторов. как у вас получается иначе — я не знаю.
                          0
                          Я теперь уже тоже не знаю :( После переписывания доступа к ByteArray на [], получились такие результаты:

                          ByteArray — write: 40 ms.
                          ByteArray — read: 52 ms.
                          Alchemy ByteArray — write: 49 ms.
                          Alchemy ByteArray — read: 52 ms.

                          Что — бред. Как будто не было преобразования байткода. Не подскажите, в чем может быть косяк? Преобразование произвожу так:

                          java.exe -jar tdsi.jar -input array_performance.swf -output array_performance2.swf

                          array_performance.swf — непакованная флэшка.

                          В процессе преобразования вижу это:
                          [i] Running tool «TurboDieselSportInjection»…
                          [i] TDSI configuration:
                          [i] inlineBytecode = true
                          [i] integerCalculus = false
                          [i] bytecodePermutations = true
                          [i] inlineMemory = true
                          [i] finalize = false
                          [i] deadCodeElimination = false
                          [i] Completed in 184 milliseconds.
                          [i] www.joa-ebert.com/

                          Т.е. все выглядит, вроде, нормально… Но результаты говорят о том, что ничего не произошло.
                            0
                            собственно я на венде аппарат я запускал так:

                            tdsi.bat -i '${output.path}' -o '${output.path}' -f true -a true -e true -m true -s true
                              0
                              Я сначала тоже так пробовал. Не получилось. =(

                              Java валится с эксепшеном:

                              java.lang.VerifyError: (class: apparat/tools/tdsi/TurboDieselSportInjection$TDSITool, method: run signature: ()V) Incompatible argument to function
                              at apparat.tools.tdsi.TurboDieselSportInjection$.main(TurboDieselSportInjection.scala:40)
                              at apparat.tools.tdsi.TurboDieselSportInjection.main(TurboDieselSportInjection.scala)
                              at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
                              at sun.reflect.NativeMethodAccessorImpl.invoke(Unknown Source)
                              at sun.reflect.DelegatingMethodAccessorImpl.invoke(Unknown Source)
                              at java.lang.reflect.Method.invoke(Unknown Source)
                              at scala.tools.nsc.util.ScalaClassLoader$$anonfun$run$1.apply(ScalaClassLoader.scala:78)
                              at scala.tools.nsc.util.ScalaClassLoader$class.asContext(ScalaClassLoader.scala:24)
                              at scala.tools.nsc.util.ScalaClassLoader$URLClassLoader.asContext(ScalaClassLoader.scala:88)
                              at scala.tools.nsc.util.ScalaClassLoader$class.run(ScalaClassLoader.scala:78)
                              at scala.tools.nsc.util.ScalaClassLoader$URLClassLoader.run(ScalaClassLoader.scala:101)
                              at scala.tools.nsc.ObjectRunner$.run(ObjectRunner.scala:33)
                              at scala.tools.nsc.ObjectRunner$.runAndCatch(ObjectRunner.scala:40)
                              at scala.tools.nsc.MainGenericRunner.runTarget$1(MainGenericRunner.scala:56)
                              at scala.tools.nsc.MainGenericRunner.process(MainGenericRunner.scala:80)
                              at scala.tools.nsc.MainGenericRunner$.main(MainGenericRunner.scala:89)
                              at scala.tools.nsc.MainGenericRunner.main(MainGenericRunner.scala)
                                0
                                ну видать, бага. попробуйте собрать тест отдельно и без анонимных функций.
                                  –1
                                  Не, проблема не в этом. У меня таким образом вообще даже пустая swf'ка без кода выдает эту ошибку.

                                  Хз, что я делаю не так. Скачал последние версии scala, apparat…
                                    0
                                    ну я знаю чем помочь, но тесты в топике советую исправить, а то ни капли правды.
                                      0
                                      извините опечатался: не знаю чем помочь.
                        0
                        для ByteArray у вас тест странный. зачем вы каждый раз ставите позицию и используется зачем-то readByte/writeByte? к ByteArray можно обращаться как к массиву ba[i].
                          –1
                          Хм, пардон. С ByteArray не работал, не знал, что так можно… сейчас перепишу. Получилось весьма быстрее.
                            0
                            Так и что в самом итоге получается после всех оптимизаций?
            0
            Также, естественно, динамические массивы были заранее созданы и наполнены элементами (т.е. новые элементы не добавлялись во время тестовых замеров).
            Насколько мне известно, под «динамическими массивами» понимаются массивы, размеры которых изменяются во время выполнения программы. В вашем случае при изменении размерности x матрицы необходимо перелопачивание и перезаполнение одномерного массива, так как в этом случае обращение a[x + y*size_x] будет приводить к непредсказуемым результатам (изменен size_x). Таким образом, ваша оптимизация будет корректно работать лишь со статическими матрицами.
            Вы не первый, кто пытается оптимизировать работу с массивами, так давайте не будем пытаться изобрести новый одномерный велосипед =)
              0
              Да, будет корректно работать только со статическим размером. Не вижу в этом ничего плохого. Для моих целей — это подходит на 100%.
              0
              А вот меня сильно интересует время создания этих массивов. Когда я реализовывал A*, у меня больше времени уходило на генерацию массивов, чем на собственно алгоритм.
                –1
                Извините, не совсем понял вас. Создание массива, в моем понимании — это объявление переменной массива. Еще можно подразумевать заполнение массива, но тут это и описано — запись в массив.
                  –1
                  Давайте код в топик, а то и будет непонимание постоянное.
                    0
                    Нет. Массив создавался и наполнялся до начала замера времени. Т.е. сначала делалось:

                      –1
                      (сорри, парсер по Ctrl+V почему-то запостил коммент)

                      Сначала делалось:
                      var ar: Array = new Array();
                      for (i=0; i<ASIZE*ASIZE; i++) ar[i] = 0;

                      А уже потом — производился еще один цикл записи, но уже с замером времени. Т.е. во время замеров — массив уже был создан, наполнен и его размер не менялся.
                      0
                      объявление переменной вообще нискольно не занимает. объявление переменной — это конструкция языка, и в байткод она не попадает. и уж тем более к созданию массива она никакого отношения не имеет.
                        –1
                        А никто и не говорил, что попадает. Создать массив это:
                        var a:Array = new Array();
                        А заполнить массив этo отнюдь не то же самое.
                          0
                          объявление переменной: var a:Array
                          создать массива: new Array()
                          не путайте понятия. обе конструкции могут спокойно уживаться друг без друга.
                  0
                  Ч.Т.Д. Довольно логичные и объяснимые результаты. Достаточно посчитать сколько операция должен сделать флэш плеер в каждом случае. Хотя у меня было сомнение что с ByteAray будет быстрее, но видать вызов функции и каст в int все же дольше чем обращене к типизированнуму массиву.
                    –2
                    Да. Я был удивлен, что Vector работает быстрее, чем акселерированный алхимией ByteArray
                      –2
                      Еще я был удивлен такому медленному BitmapData
                      0
                      Побуду немного капитаном :)
                      Обращение к типизированному массиву в теории — это просто прыжок на нужное смещение (все яйчейки имеют одинаковый размер) + отсутствие typecast. Отсюда и скорость.
                      –1
                      Интересно скорее в познавательных целях, нежели на практике, имхо.
                        –14
                        1. какую платформу вы использовали? C#, Java, Cpp? не совсем понятно
                        2. на какой архитектуре вы исполняли свои тесты?
                        3. исходники бы — потому что и read & write таки могут кешироваться и прочее.
                          +8
                          попробуйте прочитать пост
                            +5
                            Да че там пост, хотябы взгляните на название блога.
                            0
                            вы использовали release или debug-build?
                            показатели очень будут меняться от способа создания билда.
                            +3
                            Мы используем в stock чартах flash-евых RB-Tree написаное ручками и заточенное под задачу. Получается быстрее Vector/Array.
                            Но у нас несколько специфичные задачи:
                            1) нелинейность массива (то есть ключи 0,1,5,100,101)
                            2) необходимость делать выборки (например с 8 по 110), причем ключи могут и не присутствовать — необходимо найти ближайшие справа/слева
                            3) выборка min/max по промежутку

                            И много чего подобного.

                            Если интересно — могу написать полноценную статью
                              +1
                              интересно
                                0
                                конечно

                              Only users with full accounts can post comments. Log in, please.