是什么让它成为在 Web 浏览器中打印 1 到 1,000,000（用空格分隔）最快的 JavaScript？

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

  •  02-07-2019
  •  | 
  •  

题

我正在阅读有关 JavaScript 中的输出缓冲的内容 这里, 我试图理解作者所说的在网页上打印 1 到 1,000,000 的速度最快的脚本。（向下滚动到标题“中奖百万号码脚本”。）经过一番研究，我有几个问题：

  • 与其他方法相比，是什么让这个脚本如此高效？
  • 为什么缓冲可以加快速度？
  • 如何确定要使用的适当缓冲区大小？
  • 这里有人有什么可以进一步优化这个脚本的技巧吗？

（我意识到这可能是 CS101，但我是那些该死的自学成才的黑客之一，我希望从集体的智慧中受益。谢谢！）

有帮助吗？

解决方案

与其他方法相比，是什么让这个脚本如此高效？

作者对该算法做了一些优化。其中每一个都需要对如何利用底层机制有相当深入的了解（例如JavaScript、CPU、寄存器、缓存、显卡等）。我认为他正在做两个关键的优化（其余的只是锦上添花）：

  • 缓冲输出
  • 使用整数数学而不是字符串操作

既然您明确询问了缓冲，我将很快讨论它。他使用的整数数学有两个性能优势：整数加法的每次操作比字符串操作更便宜，并且使用的内存更少。

我不知道 JavaScript 和 Web 浏览器如何处理整数到浏览器中显示字形的转换，因此与字符串相比，将整数传递到 document.write 可能会产生惩罚。然而，他正在执行 (1,000,000 / 1000) document.write 调用，而不是 1,000,000 - 1,000 次整数加法。这意味着他在形成消息时执行的操作比将消息发送到显示器的操作多了大约 3 个数量级。因此，向 document.write 发送整数与字符串相比，其损失必须超过 3 个数量级，从而抵消了操作整数的性能优势。

为什么缓冲可以加快速度？

其工作原理的具体细节取决于您所使用的平台、硬件和实现。无论如何，这都是为了平衡您的算法与引起瓶颈的资源。

例如，在文件 I/O 的情况下，缓冲区很有用，因为它利用了旋转磁盘一次只能写入一定量的事实。给它太少的工作，它就不会使用磁盘旋转时通过主轴头下方的每个可用位。给它太多，你的应用程序将不得不等待（或进入睡眠状态），而磁盘完成你的写入 - 时间可能花在准备下一条记录写入上！确定文件 I/O 的理想缓冲区大小的一些关键因素包括：扇区大小、文件系统块大小、交错、磁头数量、旋转速度和面密度等。

就 CPU 而言，关键在于保持管道满载。如果你给 CPU 的工作太少，它就会在等待你分配任务时花时间旋转任何操作。如果你给CPU太多，你可能不会将请求分派给其他可以并行执行的资源，例如磁盘或显卡。这意味着稍后 CPU 将不得不等待这些返回而无所事事。CPU 中缓冲的主要因素是使（CPU）所需的一切尽可能靠近 FPU/ALU。在典型的架构中，这是（按照邻近度递减的顺序）：寄存器、L1 缓存、L2 缓存、L3 缓存、RAM。

在向屏幕写入一百万个数字的情况下，这就是用视频卡在屏幕上绘制多边形。这样想吧。假设对于添加的每个新数字，视频卡必须执行 100,000,000 次操作才能在屏幕上绘制多边形。在一个极端情况下，如果一次在页面上放置 1 个数字，然后让您的视频卡将其写出来，并且您对 1,000,000 个数字执行此操作，则视频卡将必须执行 10^14 次操作 - 100 万亿次操作！另一个极端，如果你把全部100万个数字一次性全部发送到显卡上，只需要100,000,000次操作。最佳点是中间的某个位置。如果您一次执行一个操作，CPU 就会执行一个工作单元，并在 GPU 更新显示时等待很长时间。如果您首先写入整个 1M 项目字符串，则 GPU 不会执行任何操作，而 CPU 则会运行。

如何确定使用哪个缓冲区大小？

除非您的目标是具有特定算法的非常具体且定义良好的平台（例如为互联网路由编写数据包路由），您通常无法从数学上确定这一点。通常，您可以根据经验找到它。猜测一个值，尝试一下，记录结果，然后选择另一个值。您可以根据您正在管理的瓶颈，对从哪里开始以及调查的范围做出一些有根据的猜测。

这里有人有什么可以进一步优化这个脚本的技巧吗？

我不知道这是否可行，而且我还没有测试过它，缓冲区大小通常是 2 的倍数，因为计算机的底层固定是二进制的，字大小是 通常 是二的倍数（但情况并非总是如此！）。例如，64 字节比 60 字节更有可能是最佳值，1024 比 1000 更有可能是最佳值。这个问题特有的瓶颈之一是，迄今为止大多数浏览器（Google Chrome 是我所知道的第一个例外）都让 javascript 在与网页渲染机制的其余部分相同的线程中串行运行。这意味着 javascript 会执行一些填充缓冲区的工作，然后等待很长时间直到 document.write 调用返回。如果 JavaScript 作为单独的进程异步运行，就像在 Chrome 中一样，您可能会获得显着的加速。这当然是攻击瓶颈的根源，而不是使用它的算法，但有时这是最好的选择。

并不像我希望的那么简洁，但希望这是一个很好的起点。缓冲是计算中各种性能问题的重要概念。充分了解代码所使用的底层机制（硬件和软件）对于避免或解决性能问题非常有用。

其他提示

我敢打赌，打印 1m 个数字时最慢的事情是浏览器重绘页面，因此调用 document.write() 的次数越少越好。当然，这需要与大字符串连接相平衡（因为它们涉及分配和复制）。

通过实验可以确定正确的缓冲区大小。

在其他示例中，缓冲有助于沿着自然边界对齐。这里有些例子

  • 32 位 CPU 可以更有效地传输 32 位。
  • TCP/IP 数据包有最大大小。
  • 文件 I/O 类具有内部缓冲区。
  • 图像（如 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