High-performance Tree Wrangling, the APL Way // Aaron Hsu // Dyalog '18

Channel:Dyalog User Meetings · Length:30:37 · Published:2018-11-30 · Views:5790

Watch on YouTube

Summary

Aaron Hsu shows how to manipulate and transform tree data in APL using arrays and inverted tables instead of pointers. He claims much smaller code, better performance and easier parallelisation.

Why HN recommends it

HN recommends it as a striking example of high-performance tree handling with array programming.

He has one talk (available on YouTube) about his approach to using arrays to working with tree structures in a high-performance way in APL — HN, 2021

Programming language design · Software performance & optimization · Algorithms & data structures

Subtitles (excerpt)

while we get started I'd like to encourage everybody stand up move around a little bit I don't know shift in your seats do something anything and I have a handout so you know it's gonna be fun you're not allowed to look yet all right pass won't take one pass it down up those up the aisle we go do not look do not peek it won't be any fun that way all right so now get up get stretched and get get get your heads in because I've already justified what we're gonna do so we're just gonna get straight into it we're gonna have some fun and prepare your evaluators everybody has their repple session in we're good yeah first execution set it remember it we're good okay so trees everybody knows trees does anybody not know trees here all right all right good so most people when we're working with trees including APL errs we have to work in some way with this and of course you're welcome to stay standing during this entire thing or you can sit down it's up to you most people think of trees like this so we've got a top root node and then we have some siblings going or some children going down from there and then from there those children can have children and so on and we have a bunch of descendants and we have some siblings so at the root node there's one the Adam node

On Hacker News

> " his saves on allocations, saves on total memory usage " Co-Dfns is Aaron Hsu's project, and he has a talk[1] on a compiler implemented in a nano-pass style, once in Racket, once in Chez Scheme[2] and once in Dyalog APL, each using CPU and GPU. For compiling an AST with ~16 million nodes, he gives benchmark figures that Dyalog APL takes 64MB RAM to hold it, Racket takes 1051MB and Chez Scheme … — jodrellblank, 2021-06
I had this feeling exactly listening (great, as everything Aaron does) presentation about manipulation and transformation of trees in APL, [VIDEO] — snaky, 2020-01
Qualification: I was introduced to FP a number of years ago and have finally reached a point where I feel that I have a deep understanding of FP in general. In my mind, Haskell is the "best" language out there ("best" in that it provides the best overall gain when all tradeoffs are considered). I'm no longer confident that Haskell is the "best" language anymore. I was recently introduced to a lan… — kadblas, 2019-06

Related videos