Nape 2 — Сравнение производительности списков

Две недели назад, 18 сентября (за сутки до рождения сына :) ) сделал я тест производительности нейповских списков в сравнение со списками известной библиотеки ds (в прошлом as3ds).
Благодаря генерикам в haxe и препроцессору caxe, все листы в нейпе, имея одну природу, типизированы: Vec2List, ShapeList, BodyList и т.д. Потому работа всех листов в нейп идентична.
Кроме того, листы итерировались разными способами, доступными из ихней реализации.
Тестировал на запись и чтение на такой системе:
Intel I7 mobile 1.6Hz, Win7x64, Flash Player 11.4 release


Запись в лист не интересно — все одинаково. На 1 000 000 итераций оба листа записывают за 300 ms.

А вот чтение происходило по таким методам:
- прямая итерация (по английски я ее называл ‘direct iteration’, надеюсь перевод сохранил смысл);
- через итератор;
- через доступ по индексу;
- через метод foreach (доступен только для нейповских листов, в ds нету такого);

Для тестов на чтение было использовано 10 000 000 итераций.

Итак, результаты:
Прямая итерация
Nape: 70 ms
DS : 70 ms

Через итератор
Nape: 1030 ms
DS : 400 ms

Доступ по индексу
Nape : 1677 ms
DS : 1750 ms

ForEach итерация (как говорил только для Nape. Итерировал двумя способами: через анонимную ф-ю и через приватный метод класса):
anonymous function: 1800 ms;
private method: 1360 ms;

Очень часто Лука советует итерировать через ForEach. Обратите внимание, что в этом случае ситуация печальна. Печаль приходит также с методами итерации «Доступ по индексу» и «Через итератор».
Однако, через прямую итерацию все происходит очень быстро и нейповский и ds лист итерируется за 70 миллисекунд (сравните хотя бы с методом «Через итератор» 1030 мс).
(в разработках я всегда использую структуры данных библиотеки ds и потому к прямой итерации не привыкать).
И тогда я подумал, почему бы не использовать прямую итерацию и забыть про другие способы?
Написал об этом Луке и он ответил, что: «технически я делаю это правильно, но это мега-опасно из-за внутренней реализации листа в нейпе. Такой метод итерации может иметь другое поведение чем при использовании методов из АПИ. Также, часто в листе есть какие то дополнительные элементы, которые при «правильной» итерации отбрасываются и которые не отбросятся при прямой. Лист так был спроектирован, чтобы АПИ листа никак не менялось при изменения внутренней имплементации. Например, у меня в другой ветке есть имплементация листа на основе Vector и Array, но пользователь при работе это никак не заметит, так как публичное АПИ не будет изменено.»

Словом, прямую итерацию использовать нельзя (хотя если аккуратно то наверное можно ;) ) и самый быстрый способ получается использовать итератор.
Печаль приходит еще с тем, что в грядущей версии Nape будут убраны методы связаны с графикой, а это значит, что придется каждый шаг симуляции итерировать тела самостоятельно через доступные методы в нейповском листе.
Я написал об этом Луке и оказывается (хотя это не было большой неожиданностью), что эта печаль только для пользователей AS3. Для haxe пользователей, благодаря более мощному компилятору haxe (в частности возможности инлайнинга), даже самый медленный метод foreach работает с такой же скоростью как прямое итерирование.

(кстати, списки в нейпе, как сказал Лука, однонаправленные, а в ds использую только двунаправленные DLL — не думаю, что сильно много памяти сэкономлю, зато в нем есть прекрасный метод unlink, который мгновенно удаляет нод из списка, в отличии от remove)

Код теста

Баги? Замечания? Пишите в комменты.

Поделиться в соц. сетях

Опубликовать в LiveJournal
Опубликовать в Google Plus
  • приветкакдела

    Интересно было бы посмотреть на внутреннее устройство списков.
    А то я проводил такие же тесты, точно так же спрашивал у Луки, и, оказывается, итераторы при использование в haxe работают так же, как прямая итерация в вашем примере, сложностью O(1), в отличии от as3, где как ни итерируй (по-правильному), сложность всегда O(n).

  • VirtualMaestro

    Согласен, очень интересно. Хотя сколько ни читал его код очень сложно понять — везде натыкан его caxe, а с ним я не разбирался.
    С другой стороны мне было бы больше интересно посмотреть как работают его листы в связке с нейпом. Что там такого наворочено, что не возможно использовать их просто как например тот же DLL из ds ? Для AS3 пользователей DLL принимает тип Object, но это никак не сказывается на производительности (может быть самую каплю), так как кастинг почти ничего не стоит (тоже делал тесты по этому поводу).

    • Dmitriy Yermak

      Вот интересен такой момент. Если на haxe все эти списки работают быстрее, то подключая его swc и используя методы которые полностью реализованы в этом swc, изначально написанном на haxe — то получаем производительность как у haxe?
      Понятно что используя его структуры данных в своем коде получим производительность как у AS3? Но как будут работать сами его функции если их просто вызвать без изменений?
      Сорри за вопрос, я в этом полный чайник. :)

      • VirtualMaestro

        Это интересный вопрос и размышляя над ним я пока не нашел ответа (надо глубже копать как компилятор организовывает код). Понятно, что haxe компилятор лучше оптимизирует байт-код, что у него есть инлайнинг, но почему после компиляции в SWC (соответственно после всех оптимизаций) мы получаем скорость меньше? Есть смутные догадки, но это только догадки.
        Подключая swc компилинную под haxe мы не получим туже производительность, проверенно экспериментально.
        Когда то Лука делал такой тест (по-моему с демкой Pyramid stress test) — он брал код на ас и такой же на хекс и после компиляции демка на хекс была быстрее демки ас на 3 фпс, а это много. При этом надо заметить, что основная функциональность (то есть сам Nape) скомпилирована на haxe в виде swc нейпа. А функциональность самой демки (которая была имплиментирована на as3 и haxe) очень маленькая и никакой серьёзной нагрузки не несет. Отсюда вывод, от библиотек скомпиленых под haxe мы получаем большую производительность, чем если бы они были скомпилены под mxmlc, но после компиляции конечного продукта, в котором использовалась эта библиотека, мы получим скорость больше на haxe чем на mxmlc и как уже написал выше, это не будет связано только с оптимизацией кода самого проекта. Похоже, что код библиотеки также дополнительно оптимизируется. По крайней мере лучшего объяснения на данный момент я не нашел.

  • Dmitriy

    Я прошу прощения. Наверное ответ тривиален и очевиден, но все-таки. Стандартные массивы и векторы Flash проигрывают в скорости данному DS? Или Вы его используете ради расширенной функциональности?
    И еще, объясните пожалуйста что такое прямая итерация. Погуглил, ничего внятного не нашел.

    Спасибо.

  • VirtualMaestro

    Дело в том, что массивы и списки это разные структуры данных (Vector это тот же массив, только типизированный, потому работает быстрее (может быть есть какие нибудь еще внутренние особенности реализации, но это не столь важно)).
    Массивы — последовательные ячейки памяти, доступ к которым осуществляется через индекс (если точнее то по адресу памяти).
    Список состоит из элементов (еще называемых нодами, Node), каждый из которых содержит ссылку на предыдущий и следующий нод (если мы говорим о двунаправленном списке, если однонаправленный то только ссылку на следующий нод).

    Массив
    Плюсы:
    - константное время доступа к элементу по индексу;
    - быстрая итерация;
    - быстрое добавление элемента в конец массива;
    - быстрое создание ячейки массива;

    Минусы:
    - очень медленное удаление элемента;
    - медленное добавление в начало или в середину;

    Списки
    Плюсы:
    - быстрое добавление нода в начало и в конец, а также, если известный нод, к заданному ноду, перед ним или после него. Тем самым добавление нода в любое место списка (не только середина);
    - почти мгновенное удаление нода (не важно на каком месте он находится);
    - очень быстрая итерация списка (хотя массив итерируется быстро, но список еще быстрее!);

    Минусы:
    - доступ по индексу очень медленный (строго говоря такого понятия для списков вообще нет. Просто некоторые реализации эмитируют такую функ-ность);
    - относительно медленное создание нода;

    Если же говорить в контексте AS3 — родные массивов и списки из библиотеки DS, то стоит заметить еще такие важные детали:
    - менеджирование памяти у массивов плохое из за внутреннего строения — сборщику мусора нужно больше попотеть, чтобы убрать не нужный массив из памяти;
    - менеджирование памяти у списков из DS отличное — если вы обнулили список, то сборщик мусора практически не парится, чтобы убрать его;
    - в систему списков встроена система пула (также есть прекеширование), что позволяет эффективно управлять нодами. Это значит, что минус, который я приписал спискам о медленном создании нода, может оказаться вовсе не минусом, так как при создании нового нода он будет не создаваться, а просто вернется из пула;
    - у нода (класс DLLNode) есть замечательный метод unlink, что позволяет практически мгновенно удалить нод из списка;

    По всем выше приведенным причинам я практически не использую массивы (массивы использую, только если мне надо ассоциативный массив — доступ по строкам работает мгновенно).

    Прямое итерирование, это я так назвал способ итерации списка, чтобы отличать его от других способов (через итератор, метод foreach или доступ по индексу).
    Посмотрите код теста. Найдите там «DS read ‘direct’ test».
    Это способ когда я напрямую использую указатели нода для обхода списка:
    while(node)
    {
    node = node.next;
    }

  • Dmitriy

    Ок, спасибо.
    Хотя с развернутостью ответа, если честно, вы переборщили. :)
    Я так понимаю что Вы используете в основном прямую итерацию с Нейпом?
    Были ли проблемы, и есть ли критерии по которым Вы отсеиваите служебные ноды?
    При такой разнице в скорости не вижу смысла использовать что-то другое в критичных с скорости местах.
    Хотя, по правде сказать, мне еще ни разу не приходилось перебирать сколько-нибудь существенные по длине списки в Nape. :) Но лучше знать заранее.

  • VirtualMaestro

    Пока не использую, так как до этого не придавал этому значения — на веру брал, что скорость большая. Да и мест таких критических не было. Служебные ноды не отсеивал. Лука в общем сказал, что мол там что то может быть, а в каких ситуациях и как определить не сказал.
    Но с приходом новой версии над этой проблемой надо будет думать. Если делается игра и где то в ней один раз за цикл итерируются тела это одно дело, а когда пишется движок, то каждая миллисекунда должна быть на счету, чтобы дать максимальный потенциал пользователю движка. Ведь это только движок, а какие ресурсы еще сама игра потянет?… (по крайней мере это моя философия).

  • Dmitriy

    Полностью согласен насчет ресурсов.
    Решил на свой страх и риск использовать прямой метод.

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

  • VirtualMaestro

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

  • ЛюВонг

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

  • Dmitriy

    to ЛюВонг.
    Возможно, но неадекватности не замечено. Конечно происходит смена шейпов не очень быстро. Но поскольку это босс и противник только один — то скорости вполне хватает.
    Честно сказать не вижу более простого решения. У него больше 200 кадров рисованой анимации. Создать несколько Body и двигать можно, но описать их движение формулами не получится. Можно, конечно, каждый кадр присваивать им координаты, масштабировать и поворачивать на основе данных заранее подготовленного массива данных… но так больше гемороя.
    У меня прямо во Flash IDE поверх анимации накидано несколько простых шейпов (круг, прямоугольник), на основании которых каждый кадр генерятся Shapes Нейпа. Заняло такое описание физической формы юнита минут 10.
    В общем если не будет хватать скорости — тогда буду париться. :)

  • VirtualMaestro

    @Dmitriy, было бы интересно посмотреть в действии с дебажной отрисовкой нейпа, чтобы наглядно увидеть идею с динамическими шейпами. Конечно, потом после релиза игры, если это не будет секретом :)

  • Dmitriy

    Думаю что не будет. :)
    Как доделаю — выложу.

    • Cobolin

      Было бы классно :)

  • Crash-512

    Если никто не указал ещё, то в ASC2.0 давно появился инлайнинг. Юзаем свежий компилятор, в параметрах пишем -inline, перед функцией пишем тэг [Inline], функция обязательно должна быть final, static или global.