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

Ответ 1

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

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

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

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

Я не знаю, как 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, оперативная память.

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

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

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

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

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

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

Ответ 2

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

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

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

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

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

Ответ 3

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

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

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

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

Приятно найти статью.

Ответ 4

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

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