'Точка вдоль пути' проблема производительности визуализации d3

Question

Я прошел визуализацию d3 «точка-путь» с помощью кода: https://bl.ocks.org/mbostock/1705868. Я заметил, что пока точка движется по пути, она потребляет от 7 до 11% загрузки ЦП.

В текущем сценарии у меня есть около 100 путей, и на каждом пути мне придется перемещать точки (круги) от источников к пунктам назначения.Таким образом, он потребляет более 90% памяти процессора, так как одновременно перемещается большее количество точек.

Я пробовал так:

                   function translateAlong(path) {
                      var l = path.getTotalLength();
                      return function(d, i, a) {
                          return function(t) {
                               var p = path.getPointAtLength(t * l);
                               return "translate(" + p.x + "," + p.y + ")";
                          };
                       };
                    }

                    // On each path(100 paths), we are moving circles from source to destination.
                    var movingCircle = mapNode.append('circle')
                        .attr('r', 2)
                        .attr('fill', 'white')

                    movingCircle.transition()
                        .duration(10000)
                        .ease("linear")
                        .attrTween("transform", translateAlong(path.node()))
                        .each("end", function() {
                            this.remove();
                        });

Так что должно быть лучшеуменьшить загрузку процессора?Благодаря.

Answer 1

Есть несколько подходов к этому, которые сильно различаются по потенциальной эффективности.

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

Если частота кадров падает ниже 60, это, вероятно, означает, что мы приближаемся к загрузке процессора. Я использовал частоту кадров ниже, чтобы помочь указать емкость процессора, так как она легче измеряется, чем загрузка процессора (и, вероятно, менее инвазивна).

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

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

---

Хорошо, давайте запустим некоторые переходы с более чем 100 узлами по более чем 100 путям со скоростью 60 кадров в секунду.

D3v4

Во-первых, d3v4, вероятно, предлагает здесь некоторые преимущества. v4 синхронизированные переходы, которые, кажется, имели эффект немного улучшенного времени. d3.transition очень эффективный и недорогой в любом случае, так что это не самое полезное - но обновление не плохая идея.

Есть также незначительные специфичные для браузера выгоды, которые можно получить, используя узлы различной формы, позиционирование по преобразованию или по cx, cy и т. Д. Я не реализовал ни одного из них, потому что усиления относительно тривиальны.

Canvas

Во-вторых, SVG просто не может двигаться достаточно быстро. Управление DOM требует времени, дополнительные элементы замедляют операции и занимают больше памяти. Я понимаю, что холст может быть менее удобным с точки зрения кодирования, но холст быстрее, чем SVG, для такого рода задач. Используйте отдельные элементы круга, чтобы представить каждый узел (так же, как с путями), и перенести их.

Экономьте больше времени, рисуя два полотна: одно для рисования один раз и для удержания путей (если необходимо), а другое для перерисовки каждого кадра с точками. Сохраните дополнительное время, установив для каждого круга значение длины пути, по которому он идет: нет необходимости каждый раз вызывать path.getTotalLength ().

Может быть, что-то вроде это

Холст упрощенные линии

В-третьих, у нас все еще есть отдельный узел с путями SVG, поэтому мы можем использовать path.getPointAtLength() - и это на самом деле довольно эффективно. Основной момент, замедляющий это, - использование изогнутых линий. Если вы можете сделать это, нарисуйте прямые линии (несколько сегментов в порядке) - разница существенная.

В качестве дополнительного бонуса используйте context.fillRect() вместо context.arc()

Чистый JS и Canvas

Наконец, D3 и отдельные узлы для каждого пути (поэтому мы можем использовать path.getTotalLength()) могут начать мешать. При необходимости оставьте их, используя типизированные массивы, context.imageData и собственную формулу для расположения узлов на путях. Вот быстрый простой пример ( 100 000 узлов , 500 000 узлов , 1 000 000 узлов (Chrome лучше всего подходит для этого, возможны ограничения браузера. пути теперь, по сути, окрашивают весь холст в сплошной цвет, я их не показываю, но узлы следуют за ними по-прежнему). Они могут перемещать 700 000 узлов со скоростью 10 кадров в секунду в моей медленной системе. Сравните эти 7 миллионов расчетов и визуализаций позиционирования перехода / секунда против примерно 7 тысяч вычислений позиционирования перехода и рендеринга / секунду, которые я получил с d3v3 и SVG (разница в три порядка):

холст A с изогнутыми линиями (кардинал) и маркерами круга (ссылка выше), холст B с прямыми (многосегментными) линиями и квадратными маркерами.

Как вы можете себе представить, машина и сценарий, которые могут визуализировать 1000 переходных узлов со скоростью 60 кадров в секунду, будут иметь значительную долю дополнительной емкости, если будут отображаться только 100 узлов.

Если переходная позиция и расчеты рендеринга являются основной активностью, а загрузка ЦП составляет 100%, то половина узлов должна освободить примерно половину емкости ЦП. В приведенном выше примере с самым медленным холстом моя машина зарегистрировала 200 узлов, переходящих по кардинальным кривым со скоростью 60 кадров в секунду (затем она начала падать, указывая на то, что емкость ЦП ограничивала частоту кадров и, следовательно, использование должно быть около 100%), при этом 100 узлов у нас приятное ~ 50% использование процессора:

Горизонтальная осевая линия - загрузка ЦП 50%, переход повторяется 6 раз

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

Сравните вышеприведенное с прямыми (многосегментными) и квадратными узлами:

Опять же, горизонтальная осевая линия составляет 50% загрузки процессора, переход повторяется 6 раз

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

Другие параметры

Их можно комбинировать с методами, описанными выше.

Не анимируйте каждую точку каждый тик

Если вы не можете позиционировать все узлы каждый тик перехода перед следующим кадром анимации, вы будете использовать почти всю загрузку вашего ЦП. Один из вариантов - не размещать каждый узел на каждом тике - вам не нужно. Это сложное решение - но позиционируйте по одной трети кругов на каждом тике - каждый круг по-прежнему можно расположить по 20 кадров в секунду (довольно плавно), но количество вычислений на кадр составляет 1/3 от того, что было бы в противном случае. Для холста вы все равно должны визуализировать каждый узел - но вы можете пропустить расчет позиции для двух третей узлов. Для SVG это немного проще, так как вы могли бы изменить d3-переход, включив в него метод every(), который устанавливает, сколько тиков проходит, прежде чем значения переходов будут пересчитаны (так, чтобы одна треть переходила на каждый тик).

Кэширование

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

Answer 2

Другим способом достижения этого может быть использование svg: animateMotion , которое вы можете использовать для перемещения элемента по заданному пути. Вот пример из документов . По сути вы хотите:

<svg>
  <path id="path1" d="...">
    <circle cx="" cy="" r="10" fill="red">
      <animateMotion dur="10s" repeatCount="0">
        <mpath xlink:href="#path1" />
      </animateMotion>
    </circle>
  </path>
</svg>

Я не профилировал это, но я думаю, что вы изо всех сил пытаетесь получить намного лучшую производительность, чем использование чего-то, встроенного в сам SVG.

Поддержка браузера

Обратите внимание, что после комментария @ibrahimtanyalcin я начал проверять совместимость браузера. Оказывается, это не поддерживается в IE или Microsoft Edge.

Answer 3

На моем компьютере:

• @ mbostock использует 8% ЦП.
• @ ibrahimtanyalcin использует 11% CPU.
• @ Ян использует 10% ЦП.

Для @mbostock и @ibrahimtanyalcin это означает, что обновление transition и transform использует ЦП.

Если я добавлю 100 таких анимаций в 1 SVG, я получу

• @ mbostock использует 50% ЦП. (1 ядро ​​заполнено)
• @ Ян использует 40% ЦП.

Все анимации выглядят плавно.

Одна из возможностей - добавить сон в функцию обновления transform, используя https://stackoverflow.com/a/39914235/9938317

Редактировать

В хорошем Эндрю Рейде ответе Я нашел несколько оптимизаций.

Я написал версию теста Canvas + JS 100 000, которая выполняет только расчётную часть и подсчитывает, сколько итераций можно выполнить за 4000 мс. Половина времени order=false, поскольку t контролирует его.

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

Блочная версия кода: 200 итераций

Согласно документации для parseInt

parseInt не должен использоваться вместо Math.floor()

Преобразование числа в строку и последующий анализ строки до . звучит не очень эффективно.

Замена parseInt() на Math.floor(): 218 итераций

Я также нашел строку, которая не имеет функции и выглядит неважно

let p = new Int16Array(2);

Он находится внутри внутреннего цикла while.

Замена этой строки на

let p;

дает 300 итераций .

Используя эти модификации, код может обрабатывать больше точек с частотой кадров 60 Гц.

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

Я был удивлен, что, если я предварительно вычислю длины сегментов и упросту вычисление segment до простого поиска в массиве, это будет медленнее, чем выполнение 4 поисков в массиве и пары Math.pow, а также добавлений и Math.sqrt.

Answer 4

Редактировать сообщение:

• Здесь является значением по умолчанию. (максимальная загрузка процессора около% 99 для 100 точек при 2,7 ГГц i7)
• Здесь - моя версия. (максимальная загрузка процессора около 20% для 100 точек при 2,7 ГГц i7)

В среднем я в 5 раз быстрее.

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

• заранее кешировать точки и рассчитывать только один раз с заданным разрешением (я разделил здесь на 1000 частей)
• уменьшить количество вызовов методов DOM в пределах requestAnimationFrame (та функция, которую вы видите, получая нормализованный параметр t)

В случае по умолчанию есть 2 звонка, 1, когда вы звоните getPointAtLength, а затем еще один, когда вы устанавливаете перевод (под капотом).

Вы можете заменить translateAlong следующим:

 function translateAlong(path){
    var points  = path.__points || collectPoints(path);
    return function (d,i){
        var transformObj = this.transform.baseVal[0];
        return function(t){
            var index = t * 1000 | 0,
                point = points[index];
            transformObj.setTranslate(point[0],point[1]);
        }
    }
}
function collectPoints(path) {
    var l = path.getTotalLength(),
        step = l*1e-3,
        points = [];
    for(var i = 0,p;i<=1000;++i){
        p = path.getPointAtLength(i*step);
        points.push([p.x,p.y]);
    }
    return path.__points = points;
}

И небольшая модификация этой линии анимации:

.tween("transform", translateAlong(path.node()))

установка attr не обязательна, вызова достаточно. Вот результат:

http://jsfiddle.net/ibowankenobi/8kx04y29/

Скажите, улучшилось ли оно, потому что я не уверен на 100%.