10

我在这里阅读有关 JavaScript 中的输出缓冲的信息，并试图了解作者所说的在网页上打印 1 到 1,000,000 的速度最快的脚本。（向下滚动到标题“中奖百万数字脚本”。）研究了一下，我有几个问题：

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

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

4

4 回答 4

7

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

作者对该算法进行了多项优化。其中每一个都需要对如何使用底层机制（例如，Javascript、CPU、寄存器、缓存、视频卡等）有相当深入的了解。我认为他正在进行 2 个关键优化（其余的只是锦上添花）：

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

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

我不知道 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 的工作太少，它会在等待你执行任务时花时间旋转 NO OP。如果你给 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 更新显示时等待很长时间。

您如何确定要使用的缓冲区大小？

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

这里有没有人有任何技巧可以进一步优化这个脚本？

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

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

于 2008-09-26T04:07:06.620 回答
2

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

通过实验发现确定正确的缓冲区大小。

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

  • 32 位 CPU 可以更有效地传输 32 位。
  • TCP/IP 数据包具有最大大小。
  • 文件 I/O 类具有内部缓冲区。
  • 图像，如 TIFF，可以与它们的数据一起存储在条带中。

与其他系统的自然边界对齐通常可以带来性能优势。

于 2008-09-26T03:15:23.890 回答
1

考虑它的一种方法是考虑一次对 document.write() 的调用非常昂贵。但是，构建一个数组并将该数组加入一个字符串不是。因此，减少对 document.write() 的调用次数有效地减少了写入数字所需的总体计算时间。

缓冲区是一种尝试将两个不同成本的工作结合在一起的方法。

计算和填充数组对于小数组来说成本小，而对于大数组来说，bug 成本大。无论写入的大小如何，document.write 的固定成本都很大，但对于较大的输入，其缩放比例小于 o(n)。

因此，将较大的字符串排队写入或缓冲它们可以提高整体性能。

顺便说一句，在文章中找到了不错的发现。

于 2008-09-26T03:23:04.247 回答
1

所以这个一直让我发疯，因为我不认为它真的是最快的。所以这是我的实验，任何人都可以玩。也许我写错了或其他什么，但看起来一次完成所有操作而不是使用缓冲区实际上是一种更快的操作。或者至少在我的实验中。

<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>
于 2008-09-26T05:24:08.447 回答