30:T630,md`# Generator batching

Yesterday I wrote a notebook about [Hacking hashes](https://beta.observablehq.com/@tmcw/hacking-hashes-an-exploration-of-the-nyc-taxi-data-issue), a notebook that involved running the MD5 hash algorithm on 999,999 different strings. It’s a problem well-sized for a browser environment, and especially fortunate that cracking those hashes doesn’t require you to _store_ all 999,999 strings - you just rotate through them, logging successes as they are detected. But I used one trick that I didn’t fully explain, and this is an attempt to that: batching. Which is pretty equivalent, conceptually, to [loop unrolling](https://en.wikipedia.org/wiki/Loop_unrolling). Let’s dive in. ## Generators If you aren’t familiar with generators in JavaScript, or their usage in Observable, I recommend the [Hello and Welcome](https://beta.observablehq.com/@mbostock/introduction) introduction to Observable and the [generators chapter in ExploringJS](http://exploringjs.com/es6/ch_generators.html) to get a basic handle on them. Generators are special functions that, instead of just returning one value, can yield many values over time. They’re a critical part of the Observable notebook strategy, and notebooks have some special handling for them: the yielded values of generators become cell values. We sort of ‘abstract away’ whether a cell is a constant value, a block, an async value, or a generator. Here's a cell that yields one value:`31:Ta09,md`So if generators are slower than just a loop, why use them? Two big reasons: 1. You want to animate something 2. You are doing a lot of work, and don’t want to lock up the page For the [hacking hashes notebook](https://beta.observablehq.com/@tmcw/hacking-hashes-an-exploration-of-the-nyc-taxi-data-issue), my reason was #2: computing all the MD5 hashes all at once would [block the main thread](https://developer.mozilla.org/en-US/docs/Web/JavaScript/EventLoop). See, JavaScript is still a single-threaded environment. Usually when you do things in the language, you hope that the ‘chunk of work’ is small enough that it doesn’t interrupt a user’s lovely meaningful experience. For instance, when you type code in Observable, on every keystroke [CodeMirror](https://codemirror.net/), our text editor component of choice, is doing some work to figure out the correct syntax coloring, positioning, and so on. That work briefly locks up the page, but so briefly that you never notice - it’s measurable in sub-milliseconds. But if you have a lot of work to do, you have two options: 1. Move the computation into a [WebWorker](https://developer.mozilla.org/en-US/docs/Web/API/Web_Workers_API/Using_web_workers), where it can block _another_ thread and let the UI still operate smoothly. 2. Split up the work into chunks, so that other user actions can fit in the gaps between those chunks. So, do a bunch of hard work, and then leave some time in case a user wants to collapse a code block or type something, and then back to work. WebWorkers are cool, but they’re kind of fancy, and I didn’t want to get fancy. So, #2 again: splitting up the work. But remember that generators only yield about 60 values a second. I want to hash 999,999 different strings: taking ${(999999 / 60 / 60).toFixed(2)} seconds to do that is a total bummer: we want to go faster than that. So enter batching / loop unrolling: here’s the central function of that hacking notebook: \`\`\`js rainbowBatch = { licenseNumbers; for (let i = 0; i < 999999; i += 1000) { let batch = []; for (let j = i; j < i + 1000; j++) { const n = j.toString().padStart(6, '0'); batch.push([n, md5.hash(n)]); } yield batch; } } \`\`\` Note the outer loop and inner loop: the outer loop yields a batch of 1,000 items, the inner loop creates that batch. So only needs to yield 1/1000th as much as a loop that yielded every value individually. Here, let’s compute odd numbers, with different batch sizes. You can see that bigger batches = faster loops. `32:T54e,md`--- 1. The time it takes your computer to count to 10 is no longer really measurable in Javascript since Spectre, a security flaw that relies on precise timing. So [performance.now](https://developer.mozilla.org/en-US/docs/Web/API/Performance/now) is now much less accurate, and a bit more random, than it could be, because otherwise it could be used to leak private information. 2. Lovely header image from [ClipArt ETC](https://etc.usf.edu/clipart/22300/22369/cotton_22369.htm) 3. If you earned a paper diploma from a Computer Science program in college, this may remind you of [loop unrolling](https://en.wikipedia.org/wiki/Loop_unrolling) or [Duff’s device](https://en.wikipedia.org/wiki/Duff%27s_device). Which is kind of accurate! Loop unrolling is also a technique that tries to cut down on the ‘bookkeeping’ work of iterating through a loop by doing more on each loop iteration. That said, this is a rather special case, and loop unrolling / Duff’s device are obsolete in most other cases: pretty much any language that you’ll use day-to-day has extremely performant loops and very fancy optimizing compilers that are smarter than you. Using Duff’s device is just inviting a coworker to accuse you of [premature optimization](http://wiki.c2.com/?PrematureOptimization), and they’ll be right. `33:[] 2e:{"title":"Generator batching","cells":[{"id":0,"value":"$30","pinned":false,"hidden":false,"mode":"ojs"},{"id":23,"value":"{ yield 42; }","pinned":true,"hidden":false,"mode":"ojs"},{"id":30,"value":"md`But usually we use generators to yield more than one value, because that’s a big part of their utility. Here’s a generator that yields the values from 1 to 10. It runs quickly and probably has already counted to 10 by the time you’re reading this. Focus the code and click the play button ▷ to re-run it.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":33,"value":"{ for (let i = 1; i <= 10; i++) yield i; }","pinned":true,"hidden":false,"mode":"ojs"},{"id":43,"value":"md`If you clicked play to see that incrementing number - which I recommend, the payoff is huge - you probably noticed the numbers counting up. Which, well - computers are really fast at counting, right? How long does it take for a computer to count up?[1]`","pinned":false,"hidden":false,"mode":"ojs"},{"id":51,"value":"{\n let start = performance.now();\n let to = 100000;\n let sum = 0;\n for (let i = 1; i <= to; i++) {};\n return `Counting to ${to} took ${(performance.now() - start).toFixed(2)} milliseconds`;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":69,"value":"md`So if you can count to 100,000 in 1.30 milliseconds, so you should be able to count to 10 in about ${(1.3 * 1000) * (10 / 100000)} microseconds, then why can you see that generator counting up? Either you have hummingbird vision, or there’s something else going on.\n\nThere’s something else going on: generators don’t run as fast as they can when they cross cell boundaries: they _wait_ between values, using [requestAnimationFrame](https://developer.mozilla.org/en-US/docs/Web/API/window/requestAnimationFrame) to schedule their next value’s appearance. So instead of completing that loop in nanoseconds, it takes, well - 60 frames per second, 10 frames, about 1/6th of a second to run. About 60 values will take around a second, maybe a little faster or slower:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":82,"value":"{\n let to = 60;\n let start = performance.now();\n for (let i = 0; i < to; i++) yield i;\n yield `Counting to ${to} took ${(performance.now() - start).toFixed(2)} milliseconds`;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":92,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":111,"value":"{\n let timings = [];\n for (let batchSize of [100, 1000, 5000]) {\n let start = performance.now();\n for (let i = 0; i < 10000; i += batchSize) {\n let numbers = [];\n for (let j = i; j < i + batchSize; j++) numbers.push(j * 2);\n yield numbers;\n }\n timings.push(\n `| ${batchSize} | ${(performance.now() - start).toFixed(2)} |`\n );\n }\n yield md`| batch size | milliseconds |\n| --- | --- | --- |\n${timings.join(\"\\n\")}`;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":140,"value":"md`What did we learn?\n\n- Generators are great for splitting up lots of work, and for animation.\n- If you need to use a generator to yield thousands and thousands of values, you may want to speed it up by yielding fewer values and yielding values that constitute batches - arrays of results - rather than individual values.\n- The size of generator batches is something you can tune to balance the priorities of a smooth user experience with algorithm completion time.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":65,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W33","stdlib":"1","titling":"auto"}