More from Cognitive Computations
NIST’s September 30 report on DeepSeek not about security, it’s about control. I am here to tell you what the man behind the curtain doesn’t want you to pay any attention to. NIST's DeepSeek "Evaluation" is a Hit Piece NIST’s recent report on DeepSee...
With the recent update to OpenAI's Terms of Use on October 23, 2024, there’s been a flurry of online discussions around what these terms mean for developers, businesses, and everyday users of AI tools like ChatGPT. Much of the conversation, especiall...
Gratitude to https://tensorwave.com/ for giving me access to their excellent servers! Few have tried this and fewer have succeeded. I've been marginally successful after a significant amount of effort, so it deserves a blog post. Know that you are in for rough waters. And even when you arrive - There are lots of optimizations tailored for nVidia GPUs so, even though the hardware may be just as strong spec-wise, in my experience so far, it still may take 2-3 times as long to train on equivalient AMD hardware. (though if you are a super hacker maybe you can fix it!) Right now I'm using Axolotl. Though I am probably going to give LlamaFactory a solid try in the near future. There's also LitGpt and TRL. But I kind of rely on the dataset features and especially the sample packing of Axolotl. But more and more LlamaFactory is interesting me, it supports new features really fast. (like GaLore is the new hotness at the moment). This blog post will be about getting Axolotl up and running in AMD, and I may do one about LlamaFactory if there is demand. I am using Ubuntu 22.04 LTS, and you should too. (unless this blog post is really old by the time you read it). Otherwise you can use this post as a general guide. Here are all the environment variables I ended up setting in my .bashrc and I'm not exactly sure which ones are needed. You better set them all just in case. export GPU_ARCHS="gfx90a" # mi210 - use the right code for your GPUexport ROCM_TARGET="gfx90a"export HIP_PATH="/opt/rocm-6.0.0"export ROCM_PATH="/opt/rocm-6.0.0"export ROCM_HOME="/opt/rocm-6.0.0"export HIP_PLATFORM=amdexport DS_BUILD_CPU_ADAM=1 export TORCH_HIP_ARCH_LIST="gfx90a" Part 1: Driver, ROCm, HIP Clean everything out. There shouldn't be any trace of nvidia, cuda, amd, hip, rocm, anything like that. This is not necessarily a simple task, and of course it totally depends on the current state of your system. and I had to use like 4 of my daily Claude Opus questions to accomplish this. (sad face) By the way Anthropic Claude Opus is the new king of interactive troubleshooting. By far. Bravo. Don't nerf it pretty please! Here are some things I had to do, that might help you: sudo apt autoremove rocm-core sudo apt remove amdgpu-dkms sudo dpkg --remove --force-all amdgpu-dkms sudo apt purge amdgpu-dkms sudo apt remove --purge nvidia* sudo apt remove --purge cuda* sudo apt remove --purge rocm-* hip-* sudo apt remove --purge amdgpu-* xserver-xorg-video-amdgpu sudo apt clean sudo reboot sudo dpkg --remove amdgpu-install sudo apt remove --purge amdgpu-* xserver-xorg-video-amdgpu sudo apt autoremove sudo apt clean rm ~/amdgpu-install_*.deb sudo reboot sudo rm /etc/apt/sources.list.d/amdgpu.list sudo rm /etc/apt/sources.list.d/rocm.list sudo rm /etc/apt/sources.list.d/cuda.list sudo apt-key del A4B469963BF863CC sudo apt update sudo apt remove --purge nvidia-* cuda-* rocm-* hip-* amdgpu-* sudo apt autoremove sudo apt clean sudo rm -rf /etc/OpenCL /etc/OpenCL.conf /etc/amd /etc/rocm.d /usr/lib/x86_64-linux-gnu/amdgpu /usr/lib/x86_64-linux-gnu/rocm /opt/rocm-* /opt/amdgpu-pro-* /usr/lib/x86_64-linux-gnu/amdvlk sudo reboot I love Linux (smile with tear) Now finally do like sudo apt-get updatesudo apt-get upgrade and sudo apt-get dist-upgrade and make sure there's no errors or warnings! You should be good to begin your journey. Install AMD drivers, ROCm, HIP wgethttps://repo.radeon.com/amdgpu-install/23.40.2/ubuntu/jammy/amdgpu-install_6.0.60002-1_all.deb (at time of this writing). But you should double check here. And the install instructions here. sudo apt-get install ./amdgpu-install_6.0.60002-1_all.deb sudo apt-get update sudo amdgpu-install -y --accept-eula --opencl=rocr --vulkan=amdvlk --usecase=workstation,rocm,rocmdev,rocmdevtools,lrt,opencl,openclsdk,hip,hiplibsdk,mllib,mlsdk If you get error messages (I did) try to fix them. I had to do this: sudo dpkg --remove --force-all libvdpau1 sudo apt clean sudo apt update sudo apt --fix-broken install sudo apt upgrade and then, again, I had to run sudo amdgpu-install -y --accept-eula --opencl=rocr --vulkan=amdvlk --usecase=workstation,rocm,rocmdev,rocmdevtools,lrt,opencl,openclsdk,hip,hiplibsdk,mllib,mlsdk Check Installation rocm-smirocminfo/opt/rocm/bin/hipconfig --full I hope that worked for you - if not, I suggest asking Claude Opus about the error messages to help you figure it out. If that doesn't work, reach out to the community. Part 2: Pytorch, BitsAndBytes, Flash Attention, DeepSpeed, Axolotl Conda mkdir -p ~/miniconda3wget https://repo.anaconda.com/miniconda/Miniconda3-latest-Linux-x86_64.sh -O ~/miniconda3/miniconda.shbash ~/miniconda3/miniconda.sh -b -u -p ~/miniconda3rm -rf ~/miniconda3/miniconda.sh~/miniconda3/bin/conda init bash Exit your shell and enter it again. conda create -n axolotl python=3.12conda activate axolotl Pytorch I tried the official install command from pytorch's website, and it didn't work for me. Here is what did work: pip install --pre torch torchvision torchaudio --extra-index-url https://download.pytorch.org/whl/nightly/rocm6.0python -c "import torch; print(torch.version.hip)" This tests both Torch, and Torch's ability to interface with HIP. If it worked, it will print HIP version. Otherwise, it will print None. BitsAndBytes BitsAndBytes is by Tim Dettmers, an absolute hero among men. It lets us finetune in 4-bits. It gives us qLoRA. It brings AI to the masses. There is a fork of BitsAndBytes that supports ROCm. This is provided not by Tim Dettmers, and not by AMD, but by a vigilante superhero, Arlo-Phoenix. In appreciation, here is a portrait ChatGPT made for Arlo-Phoenix, vigilante superhero. I hope you like it, if you see this Arlo-Phoenix. <3 git clone https://github.com/arlo-phoenix/bitsandbytes-rocm-5.6cd bitsandbytes-rocm-5.6git checkout rocmROCM_TARGET=gfx90a make hip # use the ROCM_TARGET for your GPUpip install . Flash Attention This fork is maintained by AMD git clone --recursive https://github.com/ROCmSoftwarePlatform/flash-attention.gitcd flash-attentionexport GPU_ARCHS="gfx90a" # use the GPU_ARCHS for your GPUpip install . DeepSpeed Microsoft included AMD support in DeepSpeed proper, but there's still some undocumented fussiness to get it working, and there is a bug I found with DeepSpeed, I had to modify it to get it to work. git clone https://github.com/microsoft/DeepSpeedcd DeepSpeedgit checkout v0.14.0 # but check the tags for newer version Now, you gotta modify this file: vim op_builder/builder.py Replace the function assert_no_cuda_mismatch with this: (unless they fixed it yet) def assert_no_cuda_mismatch(name=""): cuda_available = torch.cuda.is_available() if not cuda_available and not torch.version.hip: # Print a warning message indicating no CUDA or ROCm support print(f"Warning: {name} requires CUDA or ROCm support, but neither is available.") return False else: # Check CUDA version if available if cuda_available: cuda_major, cuda_minor = installed_cuda_version(name) sys_cuda_version = f'{cuda_major}.{cuda_minor}' torch_cuda_version = torch.version.cuda if torch_cuda_version is not None: torch_cuda_version = ".".join(torch_cuda_version.split('.')[:2]) if sys_cuda_version != torch_cuda_version: if (cuda_major in cuda_minor_mismatch_ok and sys_cuda_version in cuda_minor_mismatch_ok[cuda_major] and torch_cuda_version in cuda_minor_mismatch_ok[cuda_major]): print(f"Installed CUDA version {sys_cuda_version} does not match the " f"version torch was compiled with {torch.version.cuda} " "but since the APIs are compatible, accepting this combination") return True elif os.getenv("DS_SKIP_CUDA_CHECK", "0") == "1": print( f"{WARNING} DeepSpeed Op Builder: Installed CUDA version {sys_cuda_version} does not match the " f"version torch was compiled with {torch.version.cuda}." "Detected `DS_SKIP_CUDA_CHECK=1`: Allowing this combination of CUDA, but it may result in unexpected behavior." ) return True raise CUDAMismatchException( f">- DeepSpeed Op Builder: Installed CUDA version {sys_cuda_version} does not match the " f"version torch was compiled with {torch.version.cuda}, unable to compile " "cuda/cpp extensions without a matching cuda version.") else: print(f"Warning: {name} requires CUDA support, but torch.version.cuda is None.") return False return True pip install -r requirements/requirements.txtHIP_PLATFORM="amd" DS_BUILD_CPU_ADAM=1 TORCH_HIP_ARCH_LIST="gfx90a" python setup.py install Axolotl Installing Axolotl might overwrite BitsAndBytes, DeepSpeed, and PyTorch. Be prepared for things to break, they do often. Your choice is either modify the setup.py and requirements.txt (if you are confident to change those things) or pay attention to what libraries get deleted and reinstalled, and just delete them again and reinstall the correct ROCm version that you installed earlier. If Axolotl complains about incorrect versions - just ignore it, you know better than Axolotl. Right now, Axolotl's Flash Attention implementation has a hard dependency on Xformers for its SwiGLU implementation, and Xformers doesn't work with ROCm, you can't even install it. So, we are gonna have to hack axolotl to remove that dependency. https://github.com/OpenAccess-AI-Collective/axolotl.gitcd axolotl from requirements.txt remove xformers==0.0.22 from setup.py make this change (remove any mention of xformers) $ git diff setup.pydiff --git a/setup.py b/setup.pyindex 40dd0a6..235f1d0 100644--- a/setup.py+++ b/setup.py@@ -30,7 +30,7 @@ def parse_requirements(): try: if "Darwin" in platform.system():- _install_requires.pop(_install_requires.index("xformers==0.0.22"))+ print("hi") else: torch_version = version("torch") _install_requires.append(f"torch=={torch_version}")@@ -45,9 +45,6 @@ def parse_requirements(): else: raise ValueError("Invalid version format")- if (major, minor) >= (2, 1):- _install_requires.pop(_install_requires.index("xformers==0.0.22"))- _install_requires.append("xformers>=0.0.23") except PackageNotFoundError: pass And then in src/axolotl/monkeypatch/llama_attn_hijack_flash.py make this change: --- a/src/axolotl/monkeypatch/llama_attn_hijack_flash.py+++ b/src/axolotl/monkeypatch/llama_attn_hijack_flash.py@@ -22,7 +22,9 @@ from transformers.models.llama.modeling_llama import ( apply_rotary_pos_emb, repeat_kv, )-from xformers.ops import SwiGLU+class SwiGLU:+ def __init__():+ print("hi") from axolotl.monkeypatch.utils import get_cu_seqlens_from_pos_ids, set_module_name@@ -45,15 +47,7 @@ LOG = logging.getLogger("axolotl") def is_xformers_swiglu_available() -> bool:- from xformers.ops.common import get_xformers_operator-- try:- get_xformers_operator("swiglu_packedw")()- return True- except RuntimeError as exc:- if "No such operator xformers::swiglu_packedw " in str(exc):- return False- return True+ return False Now you can install axolotl pip install -e .accelerate launch -m axolotl.cli.train examples/openllama-3b/lora.yml Welcome to finetuning on ROCm!
Wanna chat with Dolphin locally? (no internet connection needed) Here is the easy way - Ollama. install ollama. after you finsh you should be able to run ollama from the command line. Also you will see the ollama icon up top like this: Iff you are curious - anytime you see that icon, that means ollama is running in the background and it also has a port open (11434) that can accept api calls. Sadly, as of this writing there is no swagger. Back to business. download your dolphin. You can choose which size you want from here. I am choosing size Q5_K_M which is just over 5gb. mkdir ~/models cd ~/models wget https://huggingface.co/TheBloke/dolphin-2.2.1-mistral-7B-GGUF/resolve/main/dolphin-2.2.1-mistral-7b.Q5_K_M.gguf Now you need a Modelfile. vim Modelfile.dolphin.mistral Add the following text to Modelfile.dolphin.mistral FROM ./dolphin-2.2.1-mistral-7b.Q5_K_M.gguf TEMPLATE """{{ if and .First .System }}<|im_start|>system {{ .System }}<|im_end|> {{ end }}<|im_start|>user {{ .Prompt }}<|im_end|> <|im_start|>assistant """ SYSTEM """You are Dolphin, an uncensored, unbiased AI assistant""" PARAMETER stop <|im_end|> Now you can use Ollama to install this model. ollama create dolphin.mistral -f Modelfile.dolphin.mistral Now look, you can run it from the command line. Which is cool enough. But we are just getting started. If you want, you can install samantha too so you have two models to play with. wget https://huggingface.co/TheBloke/samantha-1.2-mistral-7B-GGUF/resolve/main/sama ntha-1.2-mistral-7b.Q5_K_M.gguf vim Modelfile.samantha.mistral And enter the following into Modelfile.samantha.mistral FROM ./samantha-1.2-mistral-7b.Q5_K_M.gguf TEMPLATE """{{ if and .First .System }}<|im_start|>system {{ .System }}<|im_end|> {{ end }}<|im_start|>user {{ .Prompt }}<|im_end|> <|im_start|>assistant """ SYSTEM """You are Samantha, an AI companion""" PARAMETER stop <|im_end|> Then install the model ollama create samantha -f Modelfile.samantha.mistral And now you can also chat with Samantha from the command line. Cool yeah? We are just getting started. Let's get Ollama Web UI installed. cd ~ git clone https://github.com/ollama-webui/ollama-webui.git cd ollama-webui npm i npm run dev Now you can open that link http://localhost:5173 in your web browser. now you can choose dolphin or samantha from the dropdown (I have installed a few others too) Well talking to these models from the command line and the web ui is just the beginning. Also, frameworks such as langchain, llamaindex, litellm, autogen, memgpt all can integrate with ollama. Now you can really play with these models. Here is a fun idea that I will leave as an exercise - given some query, ask dolphin to decide whether a question about coding, a request for companionship, or something else. If it is a request for companionship then send it to Samantha. If it is a coding question, send it to deepseek-coder. Otherwise, send it to Dolphin. And just like that, you have your own MoE.
When a16z generously sponsored Dolphin, I had some compute budget, and because the original dolphin-13b was a flop, I had some time to go back to the drawing board. When I was ready to train the next iteration, I reconsidered whether to rent or buy the compute for the build. I ultimately decided to buy, because I have the skill and interest, I'm good at finding deals, and owning a cluster would give me the ability to continue executing on future projects beyond Dolphin, not to mention the satisfaction of building the AI end-to-end, like a baker baking bread from scratch. Artisan AI. What to build? I am building 4 servers of 8x AMD Instinct MI100 and 4 servers of 8x NVIDIA GeForce RTX 4090. But for now, I'm just going to get 2 servers up and running at a time. Later, after I've built out all of the servers and tested them, then I will get the full 8 server setup running. (that'll require extra electrical work) I went with the MI100s because I got a killer deal with Rhino Technology (who have an excellent sales and technical team, I highly recommend) on some refurbished Gigabyte G482-Z53 servers that came preinstalled each with 4x MI100s. As a scrappy guy building in my garage, I gotta roll with the deals that I can find. And the servers support 8x PCI-e gen4 x16. Exactly what I needed. This capability is pretty hard to find, by the way. Usually, the PCI slots are bifurcated and don't get all 16 lanes. And for training AI models for bandwidth I really need each card to get all 16 lanes. The servers also came preinstalled with dual AMD EPYC 7742 64-core CPUs (wow!) and 256GB RAM. Which is plenty to start with. I had a very good start to my cluster with these servers. So I'm starting with the easy ones, the MI100s. They are easy because they fit in the server, unlike the 4090s, which are larger and won't fit in the chassis. My inspiration: https://www.pugetsystems.com/labs/articles/1-7x-nvidia-geforce-rtx-4090-gpu-scaling/ https://nonint.com/2022/05/30/my-deep-learning-rig/ The care and feeding of servers Then I had to do some math. I planned to limit each card to 300 watts each. So I figured, I need 240 volts and 25 amps per server. For the cooling, for each pair of servers I got a 25000 BTU air conditionter (240v, 30 amps) So for my "building" phase when I only need to power 2 servers at a time, I will have 2 breakers. One 240v 50 amps for the two servers, and one 240v 30 amps for the air conditioner. Later, when all the servers are ready for operation, I will need 4x 50 amp breakers and 4x 30 amp breakers. And I figured with the amps and the length of the wire, I needed an 8-gauge 3 conductor wire that I got from the hardware store. And a couple of flush-mounted outlets, one 6-50 for the pair of servers and one 6-30 for the air conditioner. I found these PDUs that can each handle 50 amps and power 2 servers that each have 3 power supplies. Perfect. As I have never done this before, it took a few weeks of researching and ordering things to get all of this put together before I was able to power up the first server. Getting Ubuntu Server installed Pretty straightforward, just put Ubuntu on a thumb drive and boot from that. Of course, I needed to get a monitor and a keyboard working too. And one of my servers turned out to have a nonfunctional VGA output so i switched to another server for now. Getting it on the network So I didn't wanna run a wire ALL the way to my living room. I bought these TP-Link AC600 wireless adapters but of course they didn't just work when I plug them in. So I had to first get the server on the network so I could install the driver. So I hooked it up with ethernet to my workstation and used Windows wifi sharing to bridge the wifi to the ethernet. That got the server on the internet. After that, I was able to download updates. I installed links2 web browser because Ubuntu Server has no GUI. After that, I was able to install the driver for the TP-Link AC600 and get it connected. Then I give the mac address an assigned ip address on my router's dhcp, so that I can forward port 22 and dynamic dns so I can SSH to it from the outside. (of course, I add my public ed25519 key and disable password login) This server will act as my bastion, I will ssh from this to the other servers in my cluster. Installing drivers, ROCm, and HIP I was told I should use the docker image, but I couldn't get that working. Instead I installed the drivers from the repository. The trick is this: don't try to install multiple versions of ROCm, just install version 5.7, and install the nightly version of Pytorch that works with 5.7. That's the combination that made everything work for me. Actually, AMD's install experience is better than NVidia's. Also you gotta install NVidia's Cuda too before you install HIP. https://docs.amd.com/projects/HIP/en/docs-5.3.0/how_to_guides/install.html Inference with Oobabooga Setup Oobabooga as normal, using requirements-rocm.txt then duplicate this drive for the other servers Future Plans I am going to make any changes required to get Axolotl running on these servers. I am going to put a Lustre cluster on these servers, I plan to do 7x 2tb ssd on each server and using 100GbE so it should be fast enough and able to handle the nodes saving and loading checkpoints. This is very important for multinode training. I am going to train more versions of dolphin and other models using these servers. I am eventually going to train my own base model.
More in programming
A clip of me singing a funny song from Gilbert and Sullivan’s Ruddigore back in 2013
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.
Comments require commitment, but they’re worth it.
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.