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

Question

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

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

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

Answer 1

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

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

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

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

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

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

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

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

В случае с ЦП, все дело в том, чтобы конвейер был заполнен. Если вы слишком мало работаете с процессором, он будет тратить время на вращение NO OP, пока он ждет, когда вы его зададите. Если вы слишком много отдаете ЦП, вы не можете отправлять запросы другим ресурсам, таким как диск или видеокарта, которые могут выполняться параллельно. Это означает, что позже ЦПУ придется ждать, пока они вернутся, и ничего не делать. Основным фактором для буферизации в CPU является поддержание всего, что вам нужно (для CPU), как можно ближе к FPU / ALU. В типичной архитектуре это (в порядке убывания близости): регистры, кэш L1, кэш L2, кэш L3, RAM.

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

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

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

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

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

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

Answer 2

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

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

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

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

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

Answer 3

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

<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>

Answer 4

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

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

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

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

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