Что делает этот JavaScript самым быстрым для печати от 1 до 1 000 000 (через пробелы) в веб-браузере?

StackOverflow https://stackoverflow.com/questions/137534

  •  02-07-2019
  •  | 
  •  

Вопрос

Я читал о буферизации вывода в JavaScript здесь, и пытался разобраться в сценарии, который, по словам автора, был самым быстрым при печати от 1 до 1 000 000 страниц на веб-странице.(Прокрутите вниз до заголовка "Сценарий выигрышного номера на миллион".) После небольшого изучения у меня возникло несколько вопросов:

  • Что делает этот скрипт таким эффективным по сравнению с другими подходами?
  • Почему буферизация ускоряет процесс?
  • Как вы определяете правильный размер буфера для использования?
  • Есть ли у кого-нибудь здесь в запасе какие-нибудь хитрости, которые могли бы еще больше оптимизировать этот скрипт?

(Я понимаю, что это, вероятно, CS101, но я один из этих проклятых хакеров-самоучек, и я надеялся воспользоваться мудростью коллектива в этом вопросе.Спасибо!)

Это было полезно?

Решение

Что делает этот скрипт таким эффективным по сравнению с другими подходами?

Есть несколько оптимизаций, которые автор вносит в этот алгоритм.Каждый из них требует довольно глубокого понимания того, как используются лежащие в основе механизмы (напримерJavascript, процессор, регистры, кэш, видеокарта и т.д.).Я думаю, что есть 2 ключевые оптимизации, которые он делает (остальные - просто глазурь).:

  • Буферизация выходных данных
  • Использование целочисленной математики вместо манипулирования строками

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

Я не знаю, как JavaScript и веб-браузеры обрабатывают преобразование целого числа в отображаемый глиф в браузере, поэтому может возникнуть штраф, связанный с передачей целого числа в document.write при сравнении со строкой.Тем не менее, он выполняет (1,000,000 / 1000) вызовы document.write по сравнению с 1,000,000 - 1,000 сложениями целых чисел.Это означает, что он выполняет примерно на 3 порядка больше операций для формирования сообщения, чем для отправки его на дисплей.Следовательно, штраф за отправку целого числа вместо строки в document.write должен был бы превышать 3 порядка величины, что компенсировало бы преимущество в производительности при манипулировании целыми числами.

Почему буферизация ускоряет процесс?

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

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

В случае с центральным процессором все дело в том, чтобы поддерживать конвейер заполненным.Если вы дадите процессору слишком мало работы, он будет тратить время на выполнение КАКИХ-либо операций, ожидая, пока вы поставите перед ним задачу.Если вы слишком загружаете процессор, вы можете не отправлять запросы к другим ресурсам, таким как диск или видеокарта, которые могли бы выполняться параллельно.Это означает, что позже процессору придется ждать, пока они вернутся, и ему нечего будет делать.Основным фактором буферизации в процессоре является хранение всего, что вам нужно (для процессора), как можно ближе к FPU / ALU.В типичной архитектуре это (в порядке уменьшения близости):регистры, кэш L1, кэш L2, кэш L3, оперативная память.

В случае записи миллиона чисел на экран речь идет о рисовании полигонов на экране с помощью видеокарты.Подумайте об этом вот так.Допустим, что для каждого добавленного нового числа видеокарта должна выполнить 100 000 000 операций по рисованию полигонов на вашем экране.В крайнем случае, если помещать на страницу по 1 числу за раз, а затем попросить вашу видеокарту записать его, и вы сделаете это для 1 000 000 чисел, видеокарте придется выполнить 10 ^ 14 операций - 100 триллионов операций!С другой стороны, если бы вы взяли весь 1 миллион номеров и отправили его на видеокарту сразу, потребовалось бы всего 100 000 000 операций.Оптимальная точка находится где-то посередине.Если вы делаете это один раз, центральный процессор выполняет единицу работы и долго ждет, пока графический процессор обновит отображение.Если вы сначала запишете всю строку элемента размером 1 М, графический процессор ничего не будет делать, в то время как центральный процессор будет работать вхолостую.

Как вы определяете, какой размер буфера использовать?

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

Есть ли у кого-нибудь здесь в запасе какие-нибудь хитрости, которые могли бы еще больше оптимизировать этот скрипт?

Я не знаю, сработает ли это, и я не тестировал это, однако размеры буфера обычно кратны 2, поскольку нижеприведенные закрепления компьютеров являются двоичными, а размеры слов равны обычно кратно двум (но это не всегда так!).Например, 64 байта с большей вероятностью будут оптимальными, чем 60 байт, а 1024 с большей вероятностью будут оптимальными, чем 1000.Одним из узких мест, характерных для этой проблемы, является то, что большинство браузеров на сегодняшний день (Google Chrome является первым известным мне исключением) имеют javascript, запускаемый последовательно в том же потоке, что и остальная часть механизма рендеринга веб-страницы.Это означает, что javascript выполняет некоторую работу, заполняя буфер, а затем долго ждет, пока вызов document.write не вернется.Если бы javascript запускался как отдельный процесс, асинхронно, как в chrome, вы, скорее всего, получили бы значительное ускорение.Это, конечно, атака на источник узкого места, а не на алгоритм, который его использует, но иногда это лучший вариант.

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

Другие советы

Я бы поспорил, что самая медленная вещь при печати 1 млн чисел - это перерисовка страницы браузером, поэтому, чем меньше раз вы вызовете document.write(), тем лучше.Конечно, это должно быть сбалансировано с большими конкатенациями строк (потому что они включают выделение и копирование).

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

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

  • 32-разрядные процессоры могут передавать 32 бита более эффективно.
  • Пакеты TCP / IP имеют максимальные размеры.
  • Классы файлового ввода-вывода имеют внутренние буферы.
  • Изображения, как и TIFF, могут храниться вместе с их данными в виде полос.

Согласование с естественными границами других систем часто может привести к повышению производительности.

Один из способов подумать об этом - учесть, что один вызов document.write() обходится очень дорого.Однако построение массива и объединение этого массива в строку - это не так.Таким образом, уменьшение количества вызовов document.write() эффективно сокращает общее вычислительное время, необходимое для записи чисел.

Буферы - это способ попытаться связать воедино два разных по стоимости вида работ.

Вычисление и заполнение массивов требует небольших затрат для небольших массивов и больших затрат для больших массивов.document.write имеет большие постоянные затраты независимо от размера записи, но масштабируется меньше o (n) для больших входных данных.

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

Кстати, хорошая находка в статье.

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

<html>
<head>
<script type="text/javascript">
    function printAllNumberBuffered(n, bufferSize)
    {
        var startTime = new Date();

        var oRuntime = document.getElementById("divRuntime");
        var oNumbers = document.getElementById("divNumbers");

        var i = 0;
        var currentNumber;
        var pass = 0;
        var numArray = new Array(bufferSize);

        for(currentNumber = 1; currentNumber <= n; currentNumber++)
        {
            numArray[i] = currentNumber;

            if(currentNumber % bufferSize == 0 && currentNumber > 0)
            {
                oNumbers.textContent += numArray.join(' ');
                i = 0;
            }
            else
            {
                i++;
            }
        }

        if(i > 0)
        {
            numArray.splice(i - 1, bufferSize - 1);
            oNumbers.textContent += numArray.join(' ');
        }

        var endTime = new Date();

        oRuntime.innerHTML += "<div>Number: " + n + " Buffer Size: " + bufferSize + " Runtime: " + (endTime - startTime) + "</div>";
    }

    function PrintNumbers()
    {
        var oNumbers = document.getElementById("divNumbers");
        var tbNumber = document.getElementById("tbNumber");
        var tbBufferSize = document.getElementById("tbBufferSize");

        var n = parseInt(tbNumber.value);
        var bufferSize = parseInt(tbBufferSize.value);

        oNumbers.textContent = "";

        printAllNumberBuffered(n, bufferSize);
    }
</script>
</head>
<body>
<table  border="1">
    <tr>
        <td colspan="2">
            <div>Number:&nbsp;<input id="tbNumber" type="text" />Buffer Size:&nbsp;<input id="tbBufferSize" type="text" /><input type="button" value="Run" onclick="PrintNumbers();" /></div>
        </td>
    </tr>
    <tr>
        <td style="vertical-align:top" width="30%">
            <div  id="divRuntime"></div>
        </td>
        <td width="90%">
            <div id="divNumbers"></div>
        </td>
    </tr>
</table>
</body>
</html>
Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top