是什么使它成为在Web浏览器中打印1到1,000,000（以空格分隔）的最快的JavaScript？ [英] What makes this the fastest JavaScript for printing 1 to 1,000,000 (separated by spaces) in a web browser?

问题描述

我正在阅读JavaScript中的输出缓冲 此处，并且试图让我的头脑绕过作者所说的在打印1到1,000,000网页时最快的脚本。 （向下滚动到标题获胜的一百万个数字脚本。）稍微研究一下后，我有几个问题：

I was reading about output buffering in JavaScript here, and was trying to get my head around the script the author says was the fastest at printing 1 to 1,000,000 to a web page. (Scroll down to the header "The winning one million number script".) After studying it a bit, I have a few questions:

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


• 为什么缓冲加快了速度？


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


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

• What makes this script so efficient compared to other approaches?
• Why does buffering speed things up?
• How do you determine the proper buffer size to use?
• Does anyone here have any tricks up her/his sleeve that could optimize this script further?

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

(I realize this is probably CS101, but I'm one of those blasted, self-taught hackers and I was hoping to benefit from the wisdom of the collective on this one. Thanks!)

推荐答案

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

作者对此算法进行了多次优化。这些中的每一个都需要相当深入地理解所使用的底层机制（例如Javascript，CPU，寄存器，缓存，视频卡等）。我认为他正在进行两项关键优化（其余只是结冰）：

What makes this script so efficient compared to other approaches?

There are several optimizations that the author is making to this algorithm. Each of these requires a fairly deep understanding of how the are underlying mechanisms utilized (e.g. Javascript, CPU, registers, cache, video card, etc.). I think there are 2 key optimizations that he is making (the rest are just icing):

• 缓冲输出


• 使用整数数学而不是字符串操作

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

I'll discuss buffering shortly since you ask about it explicitly. The integer math that he's utilizing has two performance benefits: integer addition is cheaper per operation than string manipulation and it uses less memory.

我不知道JavaScript和Web浏览器如何处理浏览器中整数到显示字形的转换，因此传递整数可能会有一些损失与字符串比较时的document.write。但是，他正在执行（1,000,000 / 1000）document.write调用，而不是1,000,000 - 1,000个整数添加。这意味着他正在执行大约3个数量级的操作来形成消息，而不是将其发送到显示器。因此，将一个整数与一个字符串发送到document.write的代价必须超过3个数量级才能抵消操纵整数的性能优势。

I don't know how JavaScript and web browsers handle the conversion of an integer to a display glyph in the browser, so there may be a penalty associated with passing an integer to document.write when compared to a string. However, he is performing (1,000,000 / 1000) document.write calls versus 1,000,000 - 1,000 integer additions. This means he is performing roughly 3 orders of magnitude more operations to form the message than he is to send it to the display. Therefore the penalty for sending an integer vs a string to document.write would have to exceed 3 orders of magnitude offset the performance advantage of manipulating integers.

其工作原理的具体细节取决于您使用的平台，硬件和实现。在任何情况下，都是关于平衡你的算法与导致资源的瓶颈。

The specifics of why it works vary depending on what platform, hardware, and implementation you are using. In any case, it's all about balancing your algorithm to your bottleneck inducing resources.

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

For instance, in the case of file I/O, buffer is helpful because it takes advantage of the fact that a rotating disk can only write a certain amount at a time. Give it too little work and it won't be using every available bit that passes under the head of the spindle as the disk rotates. Give it too much, and your application will have to wait (or be put to sleep) while the disk finishes your write - time that could be spent getting the next record ready for writing! Some of the key factors that determine ideal buffer size for file I/O include: sector size, file system chunk size, interleaving, number of heads, rotation speed, and areal density among others.

在CPU的情况下，它是关于保持管道满的全部。如果你给CPU太少的工作，它将花费时间旋转NO OPs等待你的任务。如果给CPU太多，则可能不会将请求分派给可以并行执行的其他资源，例如磁盘或视频卡。这意味着以后在CPU上必须等待这些返回而无需做任何事情。 CPU中缓冲的主要因素是使您需要的所有内容（对于CPU）尽可能靠近FPU / ALU。在典型的体系结构中，这是（按照接近度递减的顺序）：寄存器，L1缓存，L2缓存，L3缓存，RAM。

In the case of the CPU, it's all about keeping the pipeline full. If you give the CPU too little work, it will spend time spinning NO OPs while it waits for you to task it. If you give the CPU too much, you may not dispatch requests to other resources, such as the disk or the video card, which could execute in parallel. This means that later on the CPU will have to wait for these to return with nothing to do. The primary factor for buffering in the CPU is keeping everything you need (for the CPU) as close to the FPU/ALU as possible. In a typical architecture this is (in order of decreasing proximity): registers, L1 cache, L2 cache, L3 cache, RAM.

在写入一百万个数字的情况下在屏幕上，它是关于使用视频卡在屏幕上绘制多边形。想想这样。假设对于添加的每个新号码，视频卡必须进行100,000,000次操作才能在屏幕上绘制多边形。在一个极端情况下，如果一次在页面上放置一个数字，然后将您的视频卡写出来并为1,000,000个数字执行此操作，那么视频卡将需要执行10 ^ 14次操作 - 100万亿次操作！在另一个极端情况下，如果您将整个100万个数字一次性地发送到视频卡，那么只需要100,000,000次操作。最佳点是在中间的某些位置。如果你这样做一次，CPU会做一个工作单元，并在GPU更新显示器时等待很长时间。如果你首先编写整个1M项目字符串，那么当CPU流失时，GPU什么也不做。

In the case of writing a million numbers to the screen, it's about drawing polygons on your screen with your video card. Think about it like this. Let's say that for each new number that is added, the video card must do 100,000,000 operations to draw the polygons on your screen. At one extreme, if put 1 number on the page at a time and then have your video card write it out and you do this for 1,000,000 numbers, the video card will have to do 10^14 operations - 100 trillion operations! At the other extreme, if you took the entire 1 million numbers and sent it to the video card all at once, it would take only 100,000,000 operations. The optimal point is some where in the middle. If you do it one a time, the CPU does a unit of work, and waits around for a long time while the GPU updates the display. If you write the entire 1M item string first, the GPU is doing nothing while the CPU churns away.

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

Unless you are targeting a very specific and well defined platform with a specific algorithm (e.g. writing packet routing for an internet routing) you typically cannot determine this mathematically. Typically, you find it empirically. Guess a value, try it, record the results, then pick another. You can make some educated guesses of where to start and what range to investigate based on the bottlenecks you are managing.

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

I don't know if this would work and I have not tested it however, buffer sizes typically come in multiples of 2 since the under pinnings of computers are binary and word sizes are typically in multiples of two (but this isn't always the case!). For example, 64 bytes is more likely to be optimal than 60 bytes and 1024 is more likely to be optimal than 1000. One of the bottlenecks specific to this problem is that most browsers to date (Google Chrome being the first exception that I'm aware of) have javascript run serially within the same thread as the rest of the web page rendering mechanics. This means that the javascript does some work filling the buffer and then waits a long time until the document.write call returns. If the javascript was run as separate process, asynchronously, like in chrome, you would likely get a major speed up. This is of course attacking the source of the bottleneck not the algorithm that uses it, but sometimes that is the best option.

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

Not nearly as succinct as I would like it, but hopefully it's a good starting point. Buffering is an important concept for all sorts of performance issues in computing. Having an good understanding of the underlying mechanisms that your code is using (both hardware and software) is extremely useful in avoiding or addressing performance issues.

这篇关于是什么使它成为在Web浏览器中打印1到1,000,000（以空格分隔）的最快的JavaScript？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！