Faster Loops in JavaScript
Originally written .
Last updated .
See bug list and revision history below.
Virtually all interesting data processing requires loops. Speed is a feature. Speed is valuable. The speed of loops can sometimes be improved by spatial data locality and by temporal locality. The difference is eminently practical. For example, Adam Drake achieved a speedup of factor 235 by leveraging locality. His simple trick seems to work, because his data fits in his laptop's RAM. Servers have a surprising amount of RAM nowadays.. Note, that it seems unlikely for this trick to work on unbounded data, because storing data requires physical space. This in turn, implies a lower bound on the minimum distance and therefore, a minimum bound on the achievable latency and locality.
One ubiquitous language of today is JavaScript. It runs the most common hardware human beings use in their daily lives: smartphones and laptops. On laptops it runs within web browsers like Mozilla's Firefox, Google Chrome or Apple's Safari.
Repeated computations, meaning loops, can be implemented in many different technical ways, for example recursion, recursion-trampolines or iteration. Recursion saves state on something known as the call-stack. Trampolines put function objects onto something known as the heap as opposed to the call-stack. Well-designed iteration only touches the heap and conceptually avoids the additional function objects that trampolines require.
This sounds like iteration looks preferable from this angle. One solution to transform recursion into iteration is kown as tail-call optimization (TCO) or tail-call elimination. Some programming languages implement TCO, however, JavaScript de-facto has no tail-call optimization. And de-facto standards seem to be the most effective and most impactful standards. They are observed in the real world.
References for missing TCO in JavaScript are:
- Stackoverflow
- Mozilla's developer network (MDN), first reference
- Mozilla's developer network (MDN), second reference
Another way of implementing loops iteratively is pipelining. With caches and prefetchers modern CPUs seem to be amenable to this approach.
Pipelining loops takes Adam Drake's trick one step further by folding his chain of command line tools into one programming language subroutine or function. This folds them into a single operating system process. In contrast, unix shell pipelines involve multiple unix processes and system call overhead for communicating between them. This overhead may hamper data locality. The speedup comes from limiting indirection. See also discussions on token-threading vs. subroutine-threading.
The SERIES package by
Richard C. Waters (1989a, 1989b) provides a compiler and pipeliner for loops.
Think Pipelined Relational Query Language (PRQL)
but tested since approximately 1980.
Library SERIES went through about
ten years of testing, before being listed
in Appendix A of Common Lisp the Language, 2nd edition and
Appendix B of Common Lisp the Language, 2nd edition.
Generators have even made it into Python3.
The quicklisp library parenscript seems to be missing
(tagbody ...) and (go ...). These
are two very important features of the output of
(series-expand ...).
Here is a proposed implementation of (tagbody ...)
and (go ...) for parenscript. Most importantly,
it seems to support nested (tagbody ... (tagbody ...) ...)
forms. Most importantly, this implementation is a user-land
implementation requiring only (parenscript:defpsmacro tagbody (...) ...).
(This blog post and implementation will be polished up in future.)
Examples for SERIES in JavaScript
bash$ sbcl;
sbcl*
;; Unpack archive and place in #p"~/quicklisp/local-projects/".
;; Dependencies:
;; 1. SERIES ... already available via quicklisp
;; 2. ParenScript ... already available via quicklisp
;; 3. series-expand ... on this website, different page
;; 3. parenscript-tagbody-go ... on this same web page
;;
(ql:quickload :parenscript-series)
(use-package :parenscript-series)
;; Pipelined by SERIES
;; Compiled by ParenScript
(ps*-series
'(collect-js-array-push
(map-fn T (lambda (x) (* x 2))
(map-fn T #'1+
(scan-js-array '(1 2 3))))))
;; => #<JavaScript code>
;; => [4, 6, 8] // when executed in JavaScript
;; Pipelined by SERIES
;; Compiled by ParenScript
(ps*-series
'(collect-js-array-unshift
(map-fn T (lambda (x) (* x 2))
(map-fn T #'1+
(scan-js-array '(1 2 3))))))
;; => #<JavaScript code>
;; => [8, 6, 4] // when executed in JavaScript
Example for (tagbody ...)
The following contrived example code turns into the JavaScript code below it. It really seems like pipelining the loop by hand is not entirely worth it for every single future change. Now there is a proposed compiler for that.
bash$ sbcl;
sbcl*
;; Unpack archive and place in #p"~/quicklisp/local-projects/".
;; Dependencies:
;; 1. SERIES ... already available via quicklisp
;; 2. ParenScript ... already available via quicklisp
;; 3. series-expand ... on this website, different page
;;
(ql:quickload :parenscript-tagbody-go)
(use-package :parenscript) ; *not* package :parenscript-tagbody-go
;; Nested tagbody in preamble with lots of go-tag shadowing
(parenscript:ps*
'(cl:defun bar ()
(tagbody
(tagbody
(go x)
(alert "hi") ; skipped
x)
(tagbody)
(go x)
(alert "hi") ; skipped
(tagbody ; skipped
(go x) ; skipped
(alert "hi2") ; skipped
x) ; skipped
x
(return-from bar 5))))
;; => #<JavaScript code>
;; => 5 // when executed in JavaScript
Happy Programming.
Shoutout to Ian for being a sounding board on this stuff for over a year. Also a shoutout to the Parenscript mailing list and especially Jason for their support.
Bug list
| I.D. | Date | Version reported | Version fixed | Notes |
|---|---|---|---|---|
| — | — | — | Currently no known bugs. |
| I.D. | Date | Version reported | Version fixed | Notes |
|---|---|---|---|---|
| 4 | 0.2 | 0.3 | Silently accepting duplicate jump tags. FIX: Error upon encountering duplicate jump tags. | |
| 3 | 0.2 | 0.3 | Crash on empty (tagbody ...) form. | |
| 2 | pre 0.2 | 0.2 | Incorrectly triaged. Duplicate of Bug #1. Reported on mailing list parenscript-devel by Jason Miller. | |
| 1 | pre 0.2 | 0.2 | Problem with preamble. Failure to support (go ...) and nested (tagbody ...). Reported on mailing list parenscript-devel by Jason Miller. |
Revision history
| I.D. | Date | Version | Archive | Lenght (Human Bytes) | Length (Bytes) | SHA512 | MD5 |
|---|---|---|---|---|---|---|---|
| 4 | 0.2 | parenscript-series-asdf_v0-2.zip | 5.8K | 5966 | 5fcb2416e45f53743dd2961f1d5e4ea0dbb0ba6307f262db48074953038f3dde902379a1a50006e33a87331ffe558c852ad57a358428a93f65b4c15214745f2a | f783a0ef5f10f34ee3cb6e2e7fd59f66 | |
| 3 | 0.2 | parenscript-series-asdf_v0-2.tar.gz | 3.0K | 3103 | 242295fb8e72c8d4438f3f6a1ba31385ff74a8ec3db123d1a6e3bc91e58c9c78304447d21a77bad63e7a25b8e6928e8251a10191e87c68a696e66f2aaf2aa14b | 2052532cd89c198f52c7139cefd5debe | |
| 2 | 0.1 | parenscript-series-asdf_v0-1.zip | 5.7K | 5880 | f85155c84b54d4b6104aed79cd0a0499aa9b59aead3d2d8f4ff685b4cc39e291694c14ed84c4dcced98c366778b7ae0c3a76da8ffc35d87409acafc8610849dd | a5c3f0632dc4eab48c39a293ad7de4d9 | |
| 1 | 0.1 | parenscript-series-asdf_v0-1.tar.gz | 2.9K | 3014 | ae5839270314b0d9fc8c1376d172261ee6de5ad38b7cb6b0004c365c1c4ba3bf2ba5b8f68d8a374f0e1543e1e0fe5e2e41185c1e4d37d0a64520bbb64fdc8478 | 459f4570570e3430904fa1152975c56f |
| I.D. | Date | Version | Archive | Lenght (Human Bytes) | Length (Bytes) | SHA512 | MD5 |
|---|---|---|---|---|---|---|---|
| 4 | 0.3 | parenscript-tagbody-go-asdf_v0-3.zip | 9.2K | 9422 | acac140637fc5b70ad11562f0b961e6edba64f3d7cd5ee4eef865cf0dc6688a736f427d6b8e9636bcc7e820f4b87bd5b001590c8115187053551c8505fc66a6f | e12b2218e7885eb79a047a738b9f09e6 | |
| 3 | 0.3 | parenscript-tagbody-go-asdf_v0-3.tar.gz | 7.1K | 7266 | 47db8af99a029606c35f6178297db57e76cf5b3ab02300d6299b8090ab9b13909ccf535d70d5f4e5359d9e8be3a9f3f0ed39ed334e2416aa91a521ced5044c0d | 12be063fa95b62c32b334fa5cbda4c43 | |
| 2 | 0.2 | parenscript-tagbody-go-asdf_v0-2.zip | 7.9K | 8133 | c6bb05060f8793877e13eafdf38d6e0125cb16c4489126900d2ea4a6ad92edd0de5b2608bf2c6023df6d0583ff9660926b504d796315323f1626c1c5873a339e | af77970fc908764a556434c884905958 | |
| 1 | 0.2 | parenscript-tagbody-go-asdf_v0-2.tar.gz | 5.9K | 6038 | 16cdfbc4b3eb2a5152f1fb0b0e4c346a56430126f0397e813ac85947972836598461d8d9971bfeefb69eb63a6fefbc6e7f968f773a0d3acebda6f182b03a417f | 8e46b8ea8ada7d88d1b6f22c079c0c6b |