Full Width [alt+shift+f] Shortcuts [alt+shift+k]
Sign Up [alt+shift+s] Log In [alt+shift+l]
57

Recently

from macwright.com [alt+shift+b] in programming

October was another pleasantly busy month in Brooklyn. Really took advantage of the breadth of New York culture: I saw an opera at the Metropolitan Opera House, and then went to see prog-metal band Polyphia play guitar solos as fast as possible. At the latter, there were multiple mosh pits and the most packed audience I’ve ever encountered. It was my first ‘metal’ oriented concert, and the friendliness and openness of everyone who attended was remarkable. Via Arts Gowanus, I saw lots of local art and was especially struck by Perrin Ireland’s art about animals, gender, and climate change. Books I read five great books in a row but broke the streak by reading Charles Eisenstein. Still, it was nice to enjoy book after book, especially Feel Free, which completely validated the buzz around Zadie Smith. Switching back to Instapaper and Feedbin from Readwise Reader In meta-reading news, I had switched from a combination of Feedbin and Instapaper to Readwise Reader, but I just switched back. I’m still 100% rooting for Readwise - it’s extremely cool that they’re bootstrapped and they’re rolling out features and improvements so quickly. And there were certain features I’ll miss, like their PDF and YouTube reading interfaces. But Readwise Reader’s interface gives me a feeling of an expansive, search-based collection. I found it really hard to get organized, because everything came down to search interfaces. As much as I like tagging and searching, I don’t think that those can be the only interfaces because they both lack discoverability. Part of why I absolutely adore tools like DEVONThink is that they represent organizational structure so well. So, back to Feedbin and Instapaper for me. There was also a killer Instapaper feature I had been missing - “Send to Kindle”, which I use every night to read internet articles on a less glowy device. Good articles Via University of Winds, Debbie Chachra’s Why I am Not a Maker resonated. I find myself really enjoying articles that...
1st Nov 2023

Stay updated

Get a weekly newsletter with the top 5 articles worth reading every week.

More from macwright.com

Recently

I watched a large part of All Watched Over By Machines of Loving Grace this month. This also counts as a “listening” item, because the theme song, “Baby Love Child” by Pizzicato Five, is also spectacular. Guitar Moves is a good series of interviews by Matt Sweeney, who I mostly know via his involvement in Bonnie Prince Billy. It’s a really cool format. I like how he interviews guitarists with recognizable sounds, and you get to see how little they need to play to sound just like themselves. The episode with St. Vincent is excellent too: she’s one of my guitar heroes: check out the guitar solo in Just The Same But Brand New, or her version of Dig a Pony. I also watched No Other Land. Everyone should watch No Other Land. AI thoughts roundup I don’t have a conclusion. Really, that’s my current state: ambivalence. I acknowledge that these tools are incredibly powerful, I’ve even started incorporating them into my work in certain limited ways (low-stakes code like POCs and unit tests seem like an ideal use case), but I absolutely hate them. I hate the way they’ve taken over the software industry, I hate how they make me feel while I’m using them, and I hate the human-intelligence-insulting postulation that a glorified Excel spreadsheet can do what I can but better. Nolan Lawson: AI ambivalence As I always say, the purpose of the system is what it does. Or, in this case, how I think about AI stuff is mostly affected by how people use AI stuff, and how people use AI stuff is a real mixed bag. There’s the tidal wave of spam, the aesthetic of fascism, the low-effort marketing materials with nonsense images, the non-consensual AI porn. I see all of the bad stuff every day both online and in the odd subway ad. The good stuff seems pretty theoretical, though: the press releases about AI-driven medical advances never seem to break into the real world. The stories about engineers 10x’ing their ability seem pretty mixed: we’re already at the hangover-and-regret phase with programmers bemoaning how they’ve generated so much slop and lost so much knowledge. Anyway, I’m mildly optimistic about the potential! But it’s a lot like crypto in that you could theoretically use the technology for something good but most people loudly used it for bad stuff, and people including me judged it based on what it did. AI has to start doing some good stuff soon. Potential isn’t enough. I think one thing chatGPT’s invention has revealed is how many people - including some very important people in society - find just basic reading and writing to be laborious and cumbersome to perform, and how oddly closely that type of strained literacy correlates with having other shitty opinions. From mtsw on Bluesky, about this story about Andrew Cuomo using ChatGPT to half-assedly write a policy platform. Right off the bat I should say that judging people for their level of literacy reeks of classism and so on. My own ability to read & write has a lot to do with my place in society: I went to good schools, had a stable home life, and smart parents. However, “the way that society was set up” kind of evened this out. Extremely social people with cultural capital and chiseled jawlines and biceps would get their rewards, and people like… myself, we would get rewarded for literacy and critical thinking. When one group needed the other, it was usually some kind of payment or partnership: Cuomo pays his scriptwriter, the TV show creator pays the actors. And some people can do both sides of the equation. But LLMs definitely indicate that people do not like this deal. Whew, they don’t like writing, but they also don’t like paying the writers or reading what they write. Maybe they could rejigger the system so that they could do it all. They have ideas for music and art but no interest in learning about music, practicing instruments, going to art school, or concentrating on a task for a long time, so why not generate it all? Why not, well - there are reasons, those reasons being that the generated output usually passes their own vibe check but once someone who looks closely at things or reads all the words encounters it, everyone points at the slop and it’s embarrassing. (Cuomo will never be embarrassed) Plus, you’re always going to get average results by asking a device that is incapable of creativity or thought. Also, you’ll miss out on the human experience of creating. And you’ll be indirectly feeding output data into training data for future LLMs, consequentially making their output worse. (Cuomo does not care about consequences) Colophon update I’ve moved the images for this website to Bunny (that’s an affiliate link, here’s a non-affiliate link if that’s what you prefer). When I initially moved my photos to this website, I set them up with Amazon S3 for storage and CloudFront to serve them with a CDN. Using AWS is painful for me, so I moved them to Cloudflare R2, which is Cloudflare’s equivalent to S3, and Cloudflare as a CDN. Thanks to owning my own domains, swapping out image hosts is pretty quick: switching to Bunny took all of five minutes. So what’s the deal with Bunny? Partly I’ve become a little more negative on Cloudflare and R2: I think Cloudflare’s technology is neat, but R2 has iffy reliability and Cloudflare has iffy politics. I’m also intrigued by diversifying my dependencies geographically. Bunny is a Slovenian company, and my email is from an Australian company. This probably won’t have any practical effect, but it feels kind of good for obvious reasons to even minutely hedge my bets here. So far Bunny has been great. They don’t support the S3 protocol but they do support SFTP, which works just as well for my purposes and works great with the beautiful Transmit app. Before, with R2, I was using the significantly less beautiful Cyberduck application because Cloudflare R2 doesn’t support all of the S3 protocol. It seems to be just as fast as Cloudflare was, too. And I’m somewhat reassured by the prospect of paying Bunny. I don’t like the feeling of getting “free” services like I can from Cloudflare. I want that customer relationship. Reading Then again, pop culture is powerful, and even the dumbest marketing both affects and reflects it. Busch Light’s can holder shaped like a cup that holds beer is dumb, which is fine, because most beer promos are. But the fact that the brand frames it as a functional, masculine alternative to Stanley’s H2.0 Flowstate affirms a similarly retrograde outlook on gender roles to the one that young American men are seeking out on the political right. From my friend Dave’s article about Busch Light’s weird attempt to riff on the Stanley Tumbler trend. I was once a loyal listener of the Chapo Trap House podcast, but fell off of it in 2020 when their support of Bernie Sanders led them to be jerks about Elizabeth Warren. But reading this Vanity Fair article about the cohosts of the podcast endeared them to me a bit. “Like to thank” is linguistic phlegm. “I’d like to thank the Academy.” They’d “like to thank” me. Well I’d like to be 6’3” and drive a G Wagon, thanks. I’d like you to accept my novella. I’d like to quit paying three dollars to Submittable every time I want to send a story out. The world is full of actions I would like to do. The most direct way to say thank you is just to say it: “thank you, name, for doing X.” “I’d like to thank” is a performative thanks, a thanks with a smirk and a blink, eyeing for extra credit. Just because people say it in their award show acceptance speeches doesn’t mean you should say it, too. In fact, that’s the reason you shouldn’t say it. Loved this article “Close reading my rejections” from friend of the blog Barrett Hathcock.

1st May 2025 • 36 votes
Personal tools

I used to make little applications just for myself. Sixteen years ago (oof) I wrote a habit tracking application, and a keylogger that let me keep track of when I was using a computer, and generate some pretty charts. I’ve taken a long break from those kinds of things. I love my hobbies, but they’ve drifted toward the non-technical, and the idea of keeping a server online for a fun project is unappealing (which is something that I hope Val Town, where I work, fixes). Some folks maintain whole ‘homelab’ setups and run Kubernetes in their basement. Not me, at least for now. But I have been tiptoeing back into some little custom tools that only I use, with a focus on just my own computing experience. Here’s a quick tour. Hammerspoon Hammerspoon is an extremely powerful scripting tool for macOS that lets you write custom keyboard shortcuts, UIs, and more with the very friendly little language Lua. Right now my Hammerspoon configuration is very simple, but I think I’ll use it for a lot more as time progresses. Here it is: hs.hotkey.bind({"cmd", "shift"}, "return", function() local frontmost = hs.application.frontmostApplication() if frontmost:name() == "Ghostty" then frontmost:hide() else hs.application.launchOrFocus("Ghostty") end end) Not much! But I recently switched to Ghostty as my terminal, and I heavily relied on iTerm2’s global show/hide shortcut. Ghostty doesn’t have an equivalent, and Mikael Henriksson suggested a script like this in GitHub discussions, so I ran with it. Hammerspoon can do practically anything, so it’ll probably be useful for other stuff too. SwiftBar I review a lot of PRs these days. I wanted an easy way to see how many were in my review queue and go to them quickly. So, this script runs with SwiftBar, which is a flexible way to put any script’s output into your menu bar. It uses the GitHub CLI to list the issues, and jq to massage that output into a friendly list of issues, which I can click on to go directly to the issue on GitHub. #!/bin/bash # <xbar.title>GitHub PR Reviews</xbar.title> # <xbar.version>v0.0</xbar.version> # <xbar.author>Tom MacWright</xbar.author> # <xbar.author.github>tmcw</xbar.author.github> # <xbar.desc>Displays PRs that you need to review</xbar.desc> # <xbar.image></xbar.image> # <xbar.dependencies>Bash GNU AWK</xbar.dependencies> # <xbar.abouturl></xbar.abouturl> DATA=$(gh search prs --state=open -R val-town/val.town --review-requested=@me --json url,title,number,author) echo "$(echo "$DATA" | jq 'length') PR" echo '---' echo "$DATA" | jq -c '.[]' | while IFS= read -r pr; do TITLE=$(echo "$pr" | jq -r '.title') AUTHOR=$(echo "$pr" | jq -r '.author.login') URL=$(echo "$pr" | jq -r '.url') echo "$TITLE ($AUTHOR) | href=$URL" done Tampermonkey Tampermonkey is essentially a twist on Greasemonkey: both let you run your own JavaScript on anybody’s webpage. Sidenote: Greasemonkey was created by Aaron Boodman, who went on to write Replicache, which I used in Placemark, and is now working on Zero, the successor to Replicache. Anyway, I have a few fancy credit cards which have ‘offers’ which only work if you ‘activate’ them. This is an annoying dark pattern! And there’s a solution to it - CardPointers - but I neither spend enough nor care enough about points hacking to justify the cost. Plus, I’d like to know what code is running on my bank website. So, Tampermonkey to the rescue! I wrote userscripts for Chase, American Express, and Citi. You can check them out on this Gist but I strongly recommend to read through all the code because of the afore-mentioned risks around running untrusted code on your bank account’s website! Obsidian Freeform This is a plugin for Obsidian, the notetaking tool that I use every day. Freeform is pretty cool, if I can say so myself (I wrote it), but could be much better. The development experience is lackluster because you can’t preview output at the same time as writing code: you have to toggle between the two states. I’ll fix that eventually, or perhaps Obsidian will add new API that makes it all work. I use Freeform for a lot of private health & financial data, almost always with an Observable Plot visualization as an eventual output. For example, when I was switching banks and one of the considerations was mortgage discounts in case I ever buy a house (ha 😢), it was fun to chart out the % discounts versus the required AUM. It’s been really nice to have this kind of visualization as ‘just another document’ in my notetaking app. Doesn’t need another server, and Obsidian is pretty secure and private.

3rd Apr 2025 • 71 votes
Recently

I have a non-recently post ready to write, any day now… Reading This was a strong month for reading: I finished The Hidden Wealth of Nations, Useful Not True, and Cyberlibertarianism. I had a book club that read Cyberlibertarianism so we discussed it last week. I have a lot of qualms with the book, and gave it two stars for that reason. But I will admit that it’s taking up space in my mind. The ‘cyberlibertarian’ ideology was familiar to me before reading it. The book’s critique of it didn’t shift my thinking that much. But I have been thinking a lot about what it argued for, which is a world in which the government has very extensive powers – to limit what is said online, to regulate which companies can even create forums or social media platforms. He also believed that a government should be able to decrypt and read conversations between private citizens. It’s a very different idea of government power than what I’m used to, and well outside my comfort zone. I think it’s interesting to consider these things: the government probably should have some control of some kinds of speech, and in some cases it’s useful to have the FBI tapping the phones of drug smugglers or terrorists. How do we really define what’s acceptable and what isn’t? I don’t know, I want to do more thinking about the uncomfortable things that nevertheless may be necessary for functioning of society. Besides that, there is so much to read. This month I added a lot of news subscriptions to my pile, which I think is now Hell Gate, Wired, NYTimes, Bloomberg, 404 Media, The Verge, and a bunch of newsletters. This interview with Stephanie Kelton, who is at the forefront of the Modern Monetary Theory movement in America, and wrote the very good book The Deficit Myth. This 404 Media story on an AI-generated ‘true crime’ YouTube channel is great because the team at 404 Media does both deep research and they interrogate their sources. Nathan Tankus has always been good but in this era he’s essential reading. His piece on Fort Knox is quick and snappy. His others are more involved but always worth reading. Listening We’ve been rewatching The Bear and admiring the dad-rock soundtrack. This Nine Inch Nails track shows up at the end of a season: And this Eno track: Besides that, this track from Smino played at a local cocktail bar. The bars at 0:45 sound like they’re tumbling downhill in a delightful way. Watching So I bought a sewing machine in February, a beautiful old Kenmore 158-series, produced in the 1970s in Japan. It’s awesome. How sewing machines work is amazing, as this video lays out. There’s so much coordinated motion happening for every stitch, and the machines are so well-designed that they last for decades easily. Besides that, I just watched The Apprentice, which I really did not like. Elsewhere I was on a podcast with Jeremy Jung, taking about Placemark! My post in the /micro/ section, All Hat No Cowboy, probably could have or should have been a blog post, but I was feeling skittish about being too anti-AI on the main.

1st Mar 2025 • 47 votes
Recently

I am not going to repeat the news. But man, things are really, really bad and getting worse in America. It’s all so unendingly stupid and evil. The tech industry is being horrible, too. Wishing strength to the people who are much more exposed to the chaos than I am. Reading A Confederacy of Dunces was such a perfect novel. It was pure escapism, over-the-top comedy, and such an unusual artifact, that was sadly only appreciated posthumously. Very earnestly I believe that despite greater access to power and resources, the box labeled “socially acceptable ways to be a man” is much smaller than the box labeled “socially acceptable ways to be a woman.” This article on the distinction between patriarchy and men was an interesting read. With the whole… politics out there, it’s easy to go off the rails with any discussion about men and women and whether either have it easy or hard. The same author wrote this good article about declining male enrollment in college. I think both are worth a read. Whenever I read this kind of article, I’m reminded of how limited and mostly fortunate my own experience is. There’s a big difference, I think, in how vigorously you have to perform your gender in some red state where everyone owns a pickup truck, versus a major city where the roles are a little more fluid. Plus, I’ve been extremely fortunate to have a lot of friends and genuine open conversations about feelings with other men. I wish that was the norm! On Having a Maximum Wealth was right up my alley. I’m reading another one of the new-French-economist books right now, and am still fascinated by the prospect of wealth taxes. My friend David has started a local newsletter for Richmond, Virginia, and written a good piece about public surveillance. Construction Physics is consistently great, and their investigation of why skyscrapers are all glass boxes is no exception. Watching David Lynch was so great. We watched his film Lost Highway a few days after he passed, and it was even better than I had remembered it. Norm Macdonald’s extremely long jokes on late-night talk shows have been getting me through the days. Listening This song by the The Hard Quartet – a supergroup of Emmett Kelly, Stephen Malkmus (Pavement), Matt Sweeney and Jim White. It’s such a loving, tender bit of nonsense, very golden-age Pavement. They also have this nice chill song: I came across this SML album via Hearing Things, which has been highlighting a lot of good music. Small Medium Large by SML It’s a pretty good time for these independent high-quality art websites. Colossal has done the same for the art world and highlights good new art: I really want to make it out to see the Nick Cave (not the musician) art show while it’s in New York.

4th Feb 2025 • 67 votes
2025 Predictions

I was just enjoying Simon Willison’s predictions and, heck, why not. 1: The web becomes adversarial to AI The history of search engines is sort of an arms race between websites and search engines. Back in the early 2000s, juicing your ranking on search engines was pretty easy - you could put a bunch of junk in your meta description tags or put some text with lots of keywords on each page and make that text really tiny and transparent so users didn’t notice it but Google did. I doubt that Perplexity’s userbase is that big but Perplexity users are probably a lot wealthier on average than Google’s, and there’s some edge to be achieved by getting Perplexity to rank your content highly or recommend your website. I’ve already noticed some search results including links to content farms. There are handful of startups that do this already, but the prediction is: the average marketing exec at a consumer brand will put some of their budget to work on fooling AI. That means serving different content to AI scrapers, maybe using some twist on Glaze and other forms of adversarial image processing to make their marketing images more tantalizing to the bots. Websites will be increasingly aware that they’re being consumed by AI, and they will have a vested interest in messing with the way AI ‘perceives’ them. As Simon notes in his predictions, AIs are gullible: and that’s before there are widespread efforts to fool them. There’s probably some way to detect an AI scraper, give it a special payload, and trick it into recommending your brand of razors whenever anyone asks, and once someone figures it out this will be the marketing trend of the decade. 2: Copyright nihilism breeds a return to physical-only media The latest lawsuit about Meta’s use of pirated books, allegedly with Mark Zuckerberg’s explicit permission, if true, will be another reason to lose faith in the American legal system’s intellectual property system entirely. We’ve only seen it used to punish individuals and protect corporations, regardless of the facts and damages, and there’s no reason to believe it will do anything different (POSIWID). The result, besides an uptick in nihilism, could be a rejuvenation of physical-only releases. New albums only released on vinyl. Books only available in paperback format. More private screenings of hip movies. When all digital records are part of the ‘training dataset,’ a niche, hipster subset will be drawn to things that aren’t as easily captured and reproduced. This is parallel, to the state of closed-source models from Anthropic or OpenAI. They’re never distributed or run locally. They exist as bytes on some hard drive and in some massive GPU’s memory in some datacenter, and there aren’t Bittorrents pirating them because they’re kept away from people, not because of the power of copyright law. What can be accessed can be copied, so secrecy and inaccessibility is valuable. 3: American tech companies will pull out of Europe because they want to do acquisitions The incoming political administration will probably bring an end to Lina Khan’s era of the FTC, and era in which the FTC did stuff. We will go back to a ‘hands off’ policy in which big companies will acquire each other pretty often without much government interference. But, even in Khan’s era, the real nail in the coffin for one of the biggest acquisitions - Adobe’s attempt to buy Figma – was regulators from the EU and UK. Those regulators will probably keep doing stuff, so I think it’s likely that the next time some company wants to acquire a close competitor, they just close up shop in the EU, maybe with a long-term plan to return. 4: The tech industry’s ‘DEI backlash’ will run up against reality The reality is that the gap between women and men in terms of college degrees is really big: “Today, 47% of U.S. women ages 25 to 34 have a bachelor’s degree, compared with 37% of men.” And that a great deal of the tech industry’s workforce is made of up highly-skilled people who are on H-1B visas. The synthesis will be that tech workers will be more diverse, in some respects, but by stripping away the bare-bones protections around their presence, companies will keep them in a more vulnerable and exploitable position. But hard right-wingers will have plenty to complain about because these companies will continue to look less white and male, because the labor pool is not that. 5: Local-first will have a breakthrough moment I think that Zero Sync has a good chance at cracking this really hard problem. So does electric and maybe jazz, too. The gap between the dream of local-first apps and the reality has been wide, but I think projects are starting to come to grips with a few hard truths: Full decentralization is not worth it. You need to design for syncing a subset of the data, not the entire dataset. You need an approach to schema evolution and permission checking These systems are getting there. We could see a big, Figma-level application built on Zero this year that will set the standard for future web application architecture. 6: Local, small AI models will be a big deal Embedding models are cool as heck. New text-to-speech and speech-to-text models are dramatically better than what came before. Image segmentation is getting a lot better. There’s a lot of stuff that is coming out of this boom that will be able to scale down to a small model that runs on a phone, browser, or at least on our own web servers without having to call out to OpenAI or Anthropic APIs. It’ll make sense for costs, performance, and security. Candle is a really interesting effort in this area. Mini predictions Substack will re-bundle news. People are tired of subscribing to individual newsletters. Substack will introduce some ~$20/month plan that gives you access to all of the newsletters that participate in this new pricing model. TypeScript gets a zeitwork equivalent and lots of people use it. Same as how prettier brought full code formatting from TypeScript, autoloading is the kind of thing that once you have it, it’s magic. What if you could just write <SomeComponent /> in your React app and didn’t have to import it? I think this would be extremely addictive and catch on fast. Node.js will fend off its competitors. Even though Val Town is built around Deno’s magic, I’ve been very impressed that Node.js is keeping up. They’ve introduced permissions, just like Deno, and native TypeScript support, just like the upstarts. Bun and Deno will keep gaining adherents, but Node.js has a long future ahead of it. Another US city starts seriously considering congestion pricing. For all the chatter and terrible discourse around the plan, it is obviously a good idea and it will work, as it has in every other case, and inspire other cities to do the same. Stripe will IPO. They’re still killing it, but they’re killing it in an established, repeatable way that public markets will like, and will let up the pressure on the many, many people who own their stock.

11th Jan 2025 • 78 votes

More in programming

Clip of me singing Despard in Ruddigore in 2013

A clip of me singing a funny song from Gilbert and Sullivan’s Ruddigore back in 2013

11 hours ago • 1 votes
How and Why fork() Uses Copy-on-Write

In this video, we look at why fork() needs copy-on-write, how it works inside the kernel, and a memory usage problem that Instagram encountered with Python.

17 hours ago • 1 votes
What we lost when we lost comments

Comments require commitment, but they’re worth it.

23 hours ago • 1 votes
Two-Stack Sliding-Window Aggregation

An aggregation is some kind of summary of a set of data. This can be the sum, length, minimum, etc. It is quite common to want to calculate such a summary repeatedly, e.g. “the maximum noise level in dB for the past 30 seconds” for a nuisance detector. In such a case we say there is a sliding window over our data, and we want to aggregate over our window. If our aggregation is a binary operator with an inverse, like integer sums, there is a very easy solution using a double-ended queue: from collections import deque class SlidingWindowSum: def __init__(self): self.sum = 0 self.elems = deque() def push(self, x): self.sum += x self.elems.append(x) def pop(self): self.sum -= self.elems.popleft() def eval(self): return self.sum But what if our operator has no inverse? This is actually the case for most interesting summaries such as minimum, quantile, approximate unique count (for example using HyperLogLog), etc. In fact, even something as simple as a floating-point sum suffers from the fact that floating-point addition is not invertible. For example, if you ever have a NaN in your input data with the above naive algorithm your sum will forever remain NaN, even long after the bad value has left your window. Six years ago I came up with an algorithm for maintaining just the minimum/maximum in a sliding window and posted it to cs.stackexchange. I now consider this algorithm pointless, because it turns out there is a simple and efficient algorithm that solves this problem for a very wide class of aggregations. I’m writing this blog post to spread the word, because I feel it should be more widely known. Folklore I came across this algorithm while reading a far more advanced paper, Low-Latency Sliding-Window Aggregation in Worst-Case Constant Time by Tangwongsan et al. Why is this paper titled low-latency? Because it does the same as what I’m about to describe, but in O(1) time for each step. However, in it they also described a “two-stack” algorithm, which does it in amortized O(1), and is far, far simpler. Amortized O(1) means that across many operations the total amount of work per element is constant, but an individual operation can take much longer. This is almost always fine, unless you absolutely need a low upper bound on latency. Funnily enough that paper attributes this algorithm to “adamax” from a 2011 Stack Overflow post. They in turn credit a 2001 lecture note by D. Sleator for the inspiration. However, this lecture note does not describe a sliding window aggregate, it describes the classical two-stack algorithm for implementing a FIFO queue and does amortized analysis on it. Ultimately I would not be surprised to find that this algorithm was already described in an obscure paper from the 1970s, seeing how simple and brilliant it is. Two stacks Like the authors of the paper, I will generalize the two-stack algorithm to arbitrary associative aggregation functions. By abstracting the aggregation as a set of functions, empty(), unit(x), combine(x, y) and finalize(x), you can describe many possible aggregations, for example a mean: empty = lambda: (0, 0) unit = lambda x: (x, 1) combine = lambda x, y: (x[0] + y[0], x[1] + y[1]) finalize = lambda x: x[0] / x[1] if x[1] else None I’d like to note here that these functions have the following signatures: fn empty() -> Agg; fn unit(x: Value) -> Agg; fn combine(x: Agg, y: Agg) -> Agg; fn finalize(x: Agg) -> Out; I’m making a distinction here between Value, Agg and Out because while they seem superficially similar for something like an integer sum, for an approximate unique count on strings you would have (Value, Agg, Out) = (String, HyperLogLogSketch, u64), three wildly different types. Without further ado, the algorithm: class TwoStackAgg: def __init__(self): self.values = [] self.values_agg = empty() self.cum_aggs = [] def push(self, x): self.values.append(x) self.values_agg = combine(self.values_agg, unit(x)) def pop(self): if not self.cum_aggs: cum_agg = empty() while self.values: cum_agg = combine(unit(self.values.pop()), cum_agg) self.cum_aggs.append(cum_agg) self.values_agg = empty() self.cum_aggs.pop() def eval(self): return finalize( combine(self.cum_aggs[-1], self.values_agg) if self.cum_aggs else self.values_agg ) That’s it, the entire algorithm. There’s two stacks (values and cum_aggs) and one more aggregate, values_agg. At any point in time values_agg holds the aggregate of values, and cum_aggs contains the cumulative aggregates of all values in our window that aren’t in values, in reverse order. From this we can get the aggregate over our entire window in constant time by by combining the last value of cum_aggs with values_agg. The neat part is that (assuming w is our window size) every wth operation we drain all of values and maintain a running aggregate while pushing the partial cumulative aggregates onto cum_aggs. This is what makes it amortized O(1), doing O(w) internal operations every wth pop bounds the total amount of work per element to O(1), even though a singular operation might not be constant time. I think this is best visualized. Suppose we sum [1, 2, ..., 10] with a fixed-size sliding window of four elements, then the state on each eval() call would look like this (values_agg not shown as it is simply the aggregate of the values): cum_aggs values out [] [] = 0 [] [1] = 1 [] [1, 2] = 1 + 2 [] [1, 2, 3] = 1 + 2 + 3 [] [1, 2, 3, 4] = 1 + 2 + 3 + 4 [4, 3 + 4, 2 + 3 + 4] [5] = 2 + 3 + 4 + 5 [4, 3 + 4] [5, 6] = 3 + 4 + 5 + 6 [4] [5, 6, 7] = 4 + 5 + 6 + 7 [] [5, 6, 7, 8] = 5 + 6 + 7 + 8 [8, 7 + 8, 6 + 7 + 8] [9] = 6 + 7 + 8 + 9 [8, 7 + 8] [9, 10] = 7 + 8 + 9 + 10 [8] [9, 10] = 8 + 9 + 10 [] [9, 10] = 9 + 10 [10] [] = 10 [] [] = 0 In total the memory usage is O(w), where w is your maximum window size. Note that for simplicity of analysis and the example I assumed a fixed-size window w, but there is nothing about the two-stack algorithm that requires this. You can call push(x) and pop() as many times as you’d like between each eval(), growing and shrinking the window size as needed. Floating-point non-associativity Note that we required above that our aggregate combine is associative, meaning: combine(combine(x, y), z) = combine(x, combine(y, z)) Technically speaking, floating-point addition doesn’t respect this. Nevertheless, the above algorithm is still very useful because the results closely match the expected outcome, even more so if you use a compensated summation algorithm like Kahan summation. Another neat thing about the two-stack algorithm is that it doesn’t require commutativity, if you follow the above implementation precisely. The order of operands is maintained, which can matter for things like string concatenation. However, there is a second very useful property of the above algorithm. Each aggregate is strictly a combination of the elements in the window, and none outside the window. This means if your window contains a NaN or infinity (or some other outlier), that value only poisons the windows that contain it rather than the rest of your computation. But even without NaN or infinity it is useful, due to not propagating errors endlessly. E.g. if your sliding window starts with [1e20, 1], this is what would happen with a naive rolling sum: >>> 1e20 + 1 - 1e20 - 1 -1.0 Compensated summation will reduce these effects, but not making your result depend on values outside of the window will eliminate long-term error accumulation entirely.

23 hours ago • 1 votes
Lighthouse map

Lovely global map with animated lights sweeping the waters

yesterday • 1 votes
📚 BoredReading

You seem to be enjoying this.

Join free to unlock everything.

Create free account

Already have an account? Sign in