How can we afford to grow the pie?

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:

  1. Stackoverflow
  2. Mozilla's developer network (MDN), first reference
  3. 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 (1989a1989b) 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

Data pipeline that benefits from pipelining.
Data pipeline that benefits from pipelining.

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

Bug list of parenscript-series
I.D.DateVersion reportedVersion fixedNotes
Currently no known bugs.
Bug list of parenscript-tagbody-go
I.D.DateVersion reportedVersion fixedNotes
40.20.3Silently accepting duplicate jump tags. FIX: Error upon encountering duplicate jump tags.
30.20.3Crash on empty (tagbody ...) form.
2pre 0.20.2Incorrectly triaged. Duplicate of Bug #1. Reported on mailing list parenscript-devel by Jason Miller.
1pre 0.20.2Problem with preamble. Failure to support (go ...) and nested (tagbody ...). Reported on mailing list parenscript-devel by Jason Miller.

Revision history

Revision history of parenscript-series
I.D.DateVersionArchiveLenght (Human Bytes)Length (Bytes)SHA512MD5
40.2parenscript-series-asdf_v0-2.zip5.8K59665fcb2416e45f53743dd2961f1d5e4ea0dbb0ba6307f262db48074953038f3dde902379a1a50006e33a87331ffe558c852ad57a358428a93f65b4c15214745f2af783a0ef5f10f34ee3cb6e2e7fd59f66
30.2parenscript-series-asdf_v0-2.tar.gz3.0K3103242295fb8e72c8d4438f3f6a1ba31385ff74a8ec3db123d1a6e3bc91e58c9c78304447d21a77bad63e7a25b8e6928e8251a10191e87c68a696e66f2aaf2aa14b2052532cd89c198f52c7139cefd5debe
20.1parenscript-series-asdf_v0-1.zip5.7K5880f85155c84b54d4b6104aed79cd0a0499aa9b59aead3d2d8f4ff685b4cc39e291694c14ed84c4dcced98c366778b7ae0c3a76da8ffc35d87409acafc8610849dda5c3f0632dc4eab48c39a293ad7de4d9
10.1parenscript-series-asdf_v0-1.tar.gz2.9K3014ae5839270314b0d9fc8c1376d172261ee6de5ad38b7cb6b0004c365c1c4ba3bf2ba5b8f68d8a374f0e1543e1e0fe5e2e41185c1e4d37d0a64520bbb64fdc8478459f4570570e3430904fa1152975c56f
Revision history of parenscript-tagbody-go
I.D.DateVersionArchiveLenght (Human Bytes)Length (Bytes)SHA512MD5
40.3parenscript-tagbody-go-asdf_v0-3.zip9.2K9422acac140637fc5b70ad11562f0b961e6edba64f3d7cd5ee4eef865cf0dc6688a736f427d6b8e9636bcc7e820f4b87bd5b001590c8115187053551c8505fc66a6fe12b2218e7885eb79a047a738b9f09e6
30.3parenscript-tagbody-go-asdf_v0-3.tar.gz7.1K726647db8af99a029606c35f6178297db57e76cf5b3ab02300d6299b8090ab9b13909ccf535d70d5f4e5359d9e8be3a9f3f0ed39ed334e2416aa91a521ced5044c0d12be063fa95b62c32b334fa5cbda4c43
20.2parenscript-tagbody-go-asdf_v0-2.zip7.9K8133c6bb05060f8793877e13eafdf38d6e0125cb16c4489126900d2ea4a6ad92edd0de5b2608bf2c6023df6d0583ff9660926b504d796315323f1626c1c5873a339eaf77970fc908764a556434c884905958
10.2parenscript-tagbody-go-asdf_v0-2.tar.gz5.9K603816cdfbc4b3eb2a5152f1fb0b0e4c346a56430126f0397e813ac85947972836598461d8d9971bfeefb69eb63a6fefbc6e7f968f773a0d3acebda6f182b03a417f8e46b8ea8ada7d88d1b6f22c079c0c6b