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

[danmiru]

Для полноты картины код нужен.

[BlooDHounD]

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

[soulburner]

Посоветуйте, куда выложить код — выложу. В топик не хочу, т.к. код получился весьма объемный.

[BlooDHounD]

wonderfl.net

[soulburner]

Спасибо! Сейчас размещу код в топике.

[BlooDHounD]

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

[soulburner]

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

[BlooDHounD]

ну тогда очень странно. у меня алхимия быстрее всего.
попробуйте убрать высчитываение длинны в итерациях.
ASIZE * ASIZE у вас высчитывается при каждом входе в итерацию.

[soulburner]

Да, как-то не подумал, что умножение будет вносить какой-то 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.

[BlooDHounD]

ну в общем я не знаю. я использую алхимию постоянно, у меня она минимум в 2 раза быстрее векторов. как у вас получается иначе — я не знаю.

[soulburner]

Я теперь уже тоже не знаю :( После переписывания доступа к 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/

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

[BlooDHounD]

собственно я на венде аппарат я запускал так:

tdsi.bat -i '${output.path}' -o '${output.path}' -f true -a true -e true -m true -s true

[soulburner]

Я сначала тоже так пробовал. Не получилось. =(

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)

[BlooDHounD]

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

[soulburner]

Не, проблема не в этом. У меня таким образом вообще даже пустая swf'ка без кода выдает эту ошибку.

Хз, что я делаю не так. Скачал последние версии scala, apparat…

[BlooDHounD]

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

[BlooDHounD]

извините опечатался: не знаю чем помочь.

[BlooDHounD]

для ByteArray у вас тест странный. зачем вы каждый раз ставите позицию и используется зачем-то readByte/writeByte? к ByteArray можно обращаться как к массиву ba[i].

[soulburner]

Хм, пардон. С ByteArray не работал, не знал, что так можно… сейчас перепишу. Получилось весьма быстрее.

[zallesov]

Так и что в самом итоге получается после всех оптимизаций?

[nagimov]

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

Насколько мне известно, под «динамическими массивами» понимаются массивы, размеры которых изменяются во время выполнения программы. В вашем случае при изменении размерности x матрицы необходимо перелопачивание и перезаполнение одномерного массива, так как в этом случае обращение a[x + y*size_x] будет приводить к непредсказуемым результатам (изменен size_x). Таким образом, ваша оптимизация будет корректно работать лишь со статическими матрицами.
Вы не первый, кто пытается оптимизировать работу с массивами, так давайте не будем пытаться изобрести новый одномерный велосипед =)

[soulburner]

Да, будет корректно работать только со статическим размером. Не вижу в этом ничего плохого. Для моих целей — это подходит на 100%.

[Ogra]

А вот меня сильно интересует время создания этих массивов. Когда я реализовывал A*, у меня больше времени уходило на генерацию массивов, чем на собственно алгоритм.

[exponentum]

Извините, не совсем понял вас. Создание массива, в моем понимании — это объявление переменной массива. Еще можно подразумевать заполнение массива, но тут это и описано — запись в массив.

[Ogra]

Давайте код в топик, а то и будет непонимание постоянное.

[soulburner]

Нет. Массив создавался и наполнялся до начала замера времени. Т.е. сначала делалось:

[soulburner]

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

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

А уже потом — производился еще один цикл записи, но уже с замером времени. Т.е. во время замеров — массив уже был создан, наполнен и его размер не менялся.

[BlooDHounD]

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

[exponentum]

А никто и не говорил, что попадает. Создать массив это:
var a:Array = new Array();
А заполнить массив этo отнюдь не то же самое.

[BlooDHounD]

объявление переменной: var a:Array
создать массива: new Array()
не путайте понятия. обе конструкции могут спокойно уживаться друг без друга.

[exponentum]

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

[BlooDHounD]

да? а причём тут заполнение и создание?

[exponentum]

habrahabr.ru/blogs/Flash_Platform/122401/#comment_4006472

[BlooDHounD]

а свой ответ вы читали?

[zallesov]

Ч.Т.Д. Довольно логичные и объяснимые результаты. Достаточно посчитать сколько операция должен сделать флэш плеер в каждом случае. Хотя у меня было сомнение что с ByteAray будет быстрее, но видать вызов функции и каст в int все же дольше чем обращене к типизированнуму массиву.

[soulburner]

Да. Я был удивлен, что Vector работает быстрее, чем акселерированный алхимией ByteArray

[soulburner]

Еще я был удивлен такому медленному BitmapData

[AlDev]

Побуду немного капитаном :)
Обращение к типизированному массиву в теории — это просто прыжок на нужное смещение (все яйчейки имеют одинаковый размер) + отсутствие typecast. Отсюда и скорость.

[exponentum]

Интересно скорее в познавательных целях, нежели на практике, имхо.

[zubrabubra]

1. какую платформу вы использовали? C#, Java, Cpp? не совсем понятно
2. на какой архитектуре вы исполняли свои тесты?
3. исходники бы — потому что и read & write таки могут кешироваться и прочее.

[gnomeby]

попробуйте прочитать пост

[taliban]

Да че там пост, хотябы взгляните на название блога.

[Hyzhak]

вы использовали release или debug-build?
показатели очень будут меняться от способа создания билда.

[soulburner]

релиз

[AlDev]

Мы используем в stock чартах flash-евых RB-Tree написаное ручками и заточенное под задачу. Получается быстрее Vector/Array.
Но у нас несколько специфичные задачи:
1) нелинейность массива (то есть ключи 0,1,5,100,101)
2) необходимость делать выборки (например с 8 по 110), причем ключи могут и не присутствовать — необходимо найти ближайшие справа/слева
3) выборка min/max по промежутку

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

Если интересно — могу написать полноценную статью

[olegi]

интересно

[Hyzhak]

конечно