False Optimization VS. REAL LIFE?

I have such a fun challenge for you. This just made my day!
Heck, even a week. I hope it makes your day too!

The story is fabricated by many hackers — the problem is real! Any relation to persons living or undead is completely coincidental.   - Disclaimer by Despicable Gru of Despicable Me. (Hacker Lore — The Newly Unpublished Hacker Dictionary, 2024) Expand for a classic hacker scene trope full of traditional characters! Absurdly impossible in real life…​ dark humor notwithstanding. Mr. Suit — a corporate type hackers love to interact with. Has money. (CATB Jargon File, 2003) Random — Joe Random Hacker, an unremarkable specimen on the real scene. the living — all makers, including hackers, that 'live' in creating real value through perpetual learning. (The Newly Unpublished Hacker Dictionary, 2022) the undead — opposite to living, imitators. Black Mercedes, no plates. Apple Watch. (The Newly Unpublished Hacker Dictionary, 2022)

An Executive, Mr. Suit, is talking with J. Random Hacker (R):

Mr. Suit: You know, in statistics, there’s a sliding window to calculate averages?
R: Yes, I’m aware. Most-widely used for metrics, positioning, etc.
Mr. Suit: How would you do it? Say in Databricks or Kafka, you have a stream. How’d calculate?
R: It’s trivial. Add up the numbers in the window and divide by width.
Mr. Suit: Yes, yes, I know. But what if you want to make it FASTER! What can you do?
R: You are pushing me to memoise the accumulator. BUT!
  This only works if arithmetically there is a save. There is no save here!
Mr. Suit: Well, you could add up all values one time.
  And then just add one and remove one before dividing.
  So, you don’t need to add them all again.
  And your algorithm is much faster. That’s the optimal solution.
  We benchmarked it — on the whiteboard.
R: Sure, sure. Why not?!

I nodded — I had a repo to write.

One of us walked out of that room wrong.
Wanna bet which one? Run my code. Or make your own.

How can NOT memoizing previously added sum be SLOWER?!

Oh, but this is beautiful! Let us understand?

(The repo is here…​)

The Problem:

What is running average (the moving average) and where is it used?

Figure 1. A sliding window: width 3, stride 1

 

7, 2, 3, 4, 8, 6, 1

   4, 3, 5, 6, 5

Notice what happened: the array got smaller and "smoothed out."

Do developers do this in real work? NO! We use statistical libraries for much larger functions. But I have done this just a couple of years ago on smart weapon-systems. Here is a practical example:

Figure 2. Jittery readings smoothed: window 13, stride 3

 

window=13 and stride=3 is a real life example — this is what a reconnaissance drone wants to know over a rough terrain it would be offset over. This is one of the most often used statistical tools.

The 'Textbook' Optimization from Academia:

In our earlier conversation Mr. Suit thought "Memoise to Optimize" makes sense:

1. 13 is a lot of numbers to add! I need to add 12 times.

2. Then I slide 3 numbers — but 10 are the same!

3. I would have to add 12 times again.

4. But I can remember my sum of 13 from before! memoise

5. On slide: I can subtract 3 dropping off and add 3 showing up.

6. I save a lot of time — less to calculate!

7. Oh, and it’s cool to stream — so, we also stream.

Sounds reasonable? Why not!^[1]
Let’s see what actually happens when we implement the academic False Optimization?

Figure 3. "But what about us? Should we just apply toilet water on it?" — Idiocracy (2006)

 

Median (min) of 10 warmed-up, timed runs over 4,000,000 integers,

window=13, stride=3 (see test sources here)
  — LinearSliderTest.massiveArrayPerformanceComparison

	Memoised accumulator	Brute-force add
Streaming	224.94 ms (217.68 ms)	105.57 ms (103.75 ms)
Array	5.63 ms (5.56 ms)	5.20 ms (5.12 ms)

Figure 4. Brute force wins both rows — note the Array panel is zoomed 40×

 

WHOA! The 'optimization' is slower in calculation. And A LOT slower in streams!
But why?! Where did the whiteboard part ways with the machine?

---

Real Life: Pandas — academia’s toy — runs the False Optimization. Engineers RIP IT OUT!^[1]
pola-rs/polars — humiliates academia publicly: 94x faster IN PRODUCTION — But why?!^[2]
(Docs explicitly forbid, chastise, and architecturally block "iteration-carried dependence.")

Curious?

---

Real Life Engineering:

Understanding what’s going on here is a-must for a practicing software engineer. Just to make sure, I first peeked into the implementations of most popular statistical libraries — YEP!
Exactly what I expected. (See pola-rs/polars above.)
But those don’t help me explain it as if I am 5 — my hard rule.
So, I made a little bit of code for us to play with and explain.

(In reverse order now, for simplicity.)

#4 calculates resulting array and jumps adding everything every time: brute force.

Fourth IntArray.runningAverageBruteForceNaive sums every time. (5.20ms)

override fun IntArray.runningAverageBruteForceNaive(windowSize: Int, stride: Int): IntArray {
    val result = IntArray((size - windowSize) / stride + 1)
    for (out in result.indices) {
        val start = out * stride
        var sum = 0
        for (i in start until start + windowSize) sum += this[i]
        result[out] = sum / windowSize
    }
    return result
}

#3 remembers (memoise) sum outside the loop now — adds and subtracts.

Third IntArray.runningAverageNaive is accumulating outside the loop. (5.63ms)

override fun IntArray.runningAverageNaive(windowSize: Int, stride: Int): IntArray {
    val result = IntArray((size - windowSize) / stride + 1)
    var sum = 0                                                 // <- ACCUMULATOR! (ACC)
    for (i in 0 until windowSize) sum += this[i]
    result[0] = sum / windowSize
    for (slide in 1..size - windowSize) {
        sum += this[slide + windowSize - 1] - this[slide - 1]   // Compound-messing with ACC
        if (slide % stride == 0) result[slide / stride] = sum / windowSize
    }
    return result
}

Notice, the third above didn’t get "much faster" as the whiteboard promised — it’s a little bit slower.

#2 simply slides a stream and adds — notice the simplicity of code here.

Second uses stream’s own windowed() to slide a window and then it.sum(). (105.57ms)

override fun IntArray.runningAverageBruteForce(windowSize: Int, stride: Int): IntArray = asSequence()
    .windowed(windowSize, stride, false) { it.sum() / it.size }
    .toArray((size - windowSize) / stride + 1, ArrayKind.Ints)

Simulation of real streams is by asSequence() which are synchronous and blocking.

#1 finally bolts an accumulator to memoise the mutable dependency
(remember these two words for later please).

First stream IntArray.runningAverage is still functional recalculating accumulation along. (224.94ms)

override fun IntArray.runningAverage(windowSize: Int, stride: Int): IntArray =
    asSequence()
        .drop(windowSize)
        .zip(asSequence()) { entering, leaving -> entering - leaving }
        .runningFold(take(windowSize).sum()) { sum, delta -> sum + delta }
        .filterIndexed { index, _ -> index % stride == 0 }
        .map { it / windowSize }
        .toArray((size - windowSize) / stride + 1)
        .toIntArray()

Claude Fable 5 NEEDS KDocs to properly explain this code! I didn’t include comments for brevity. You should follow this code along in your IDE from my GitHub source project: I have added KDocs on the interfaces and methods — without those Claude won’t follow, 'understand', or properly explain this simple zip and fold. It seems to explain imperative code rather well. Fluent functional — not so much; perhaps a smaller training set. Good documentation and comments fix that.

Riddler! - What about boxing/unboxing?

Yes, indeed: collections versus memblocks.

If you are interested here is how I covered that:

The cost to both streaming tests must be identical or comparable.

Thus, here is the collection to memblock

sealed interface ArrayKind<T : Any, A : Any> {
    fun create(size: Int, next: () -> T): A

    data object Ints : ArrayKind<Int, IntArray> {
        override fun create(size: Int, next: () -> Int) = IntArray(size) { next() }
    }
    @Suppress("unused")
    data object Floats : ArrayKind<Float, FloatArray> {
        override fun create(size: Int, next: () -> Float) = FloatArray(size) { next() }
    }
}

@Suppress("UnusedReceiverParameter") // just for unlinked code scanner
fun <T : Any, A : Any> Sequence<T>.toArray(size: Int, kind: ArrayKind<T, A>): A {
    val iter = iterator()
    return kind.create(size) { iter.next() }
}

Or, a direct cast to use in your own tests:

@Suppress("UnusedReceiverParameter") // just for unlinked code scanner
inline fun <reified T> Sequence<T>.toArray(size: Int): Array<T> {
    val iter = iterator()
    return Array(size) { iter.next() }
}

 

THE TEST

And before we explain anything — here’s the TEST:

@Test
fun massiveArrayPerformanceComparison() = with(LinearSlider()) {
    assertEquals(massive_array_size, massiveArray.size, "Massive array performance comparison over stream of 4_000_000 integers.")
    val repetitions = 10
    var guard = 0
    fun timed(description: String, slideAverage: IntArray.() -> IntArray) {
        repeat(3) { guard += massiveArray.slideAverage().size }
        val times = (1..repetitions).map {
            measureTime { guard += massiveArray.slideAverage().size }
        }
        logger.info { "$description: median ${times.sorted()[repetitions / 2]}, min ${times.min()}" }
    }
    timed("Streaming  Accumulator Slider") { runningAverage(13, 3) }
    timed("Streaming  Dumb Window Slider") { runningAverageBruteForce(13, 3) }
    timed("Imperative Accumulator Slider") { runningAverageNaive(13, 3) }
    timed("Imperative Dumb Window Slider") { runningAverageBruteForceNaive(13, 3) }
    assertEquals(number_timing_ops, guard, "Guard fired for all the cache lining operations.")
}

But Why? The Explanation:

So where did the whiteboard go wrong? Nowhere — in 1979.

Does the algorithm save calculation?
On long window and short stride this DOES save calculation on primitive level.
In fact, in 1979 on 8088 CPU it would have brought a real, measurable save.
Please, keep in mind that 8088 already had register-memory instructions implemented.
But since 1997 with introduction of MMX (extension to 1966 SIMD^[3]) this is useless.

Every practicing software engineer MUST understand what comes next!

The algorithm attempts to save human calculation - it does NOT save compute.
Far more importantly — it BLOCKS any clever gains by a mutable interdependency!

Outside a deeply flawed algorithm three things here make all the difference:

1. Single Instruction Multiple Data (SIMD) — 2026 is generation 7 (SEVEN)
   MMX (1) → SSE (2) → SSE2–SSE4 (3) → AVX (4) → AVX2 (5) → AVX-512 (6) → AVX10
   AVX10.2 is about to drop — generation 8, methinks; Intel doesn’t number them, I slopped.

2. In-CPU Integrated Memory Controller — on-die since 2003: direct page-lining.

3. Kotlin K2 compiler IR with @Metadata engine: All compilers align hints now.

In order of effect on code. Most important is the algorithm flaw I’ll cover last!
The flaw is the crime — the three above are its victims.

Single Instruction Multiple Data (SIMD):

This is WHY certain operations are ALWAYS performed in parallel! Break down:

1. Each clock cycle only marks time to MOVE data in and out of SL1 cache;

2. Arithmetic-Logic Unit (ALU) is a reactive circuit — it performs 4 - 7 saturation per clock cycle; Just like JK-FlipFlop it will keep flipping until it finally settles on completed calculation;

3. ALU has many Op-Channels (212+) and is able to perform simultaneous calculations on adjacent IMMUTABLE values

4. SL1 cache is directly addressable — all OpChannels operate directly on SL1 and registers;

5. Virtual Ultra-wide Registers (Vectors) — SL1 sits in the same silicon neighborhood as the registers: latency-wise almost one thing;

What does this all mean?! When:

• Data is IMMUTABLE,

• Data is Adjacent,

• Data is Uniform,

CPU will perform many operations in parallel and even cache intermediate values (16 or 32 integers, etc.) This means if I wrote a piece of code that iterates an array and adds all the values — the CPU will automatically add them IN PARALLEL several times per single clock-cycle. Add a range, add another range in neighboring memory in the same memory page at the same time, and 1/4 of clock-cycle later add the results of the ranges together — just go till page-fault signal.

So, adding a pair of values in the array or a bunch of them takes exactly the same time — 1 tic.
It’s been this way since 1997! Just must be immutable!

Integrated Memory Controller: Speculative Execution / Cache Lining:

When the memory controller (MMC) was moved into the CPU in 2003 it gained the ability "to see" where "the page" is going. Because the page-lining is cascading: fast between SL1-SL2, slower between SL2-SL3, and dog-slow between SL3-MainMemory — MMC gained A LOT of computational ability to:

1. Line caches speculatively expecting some memory space needed soon;

2. Understand branches (if-else) thus loading both spaces together;

3. Dispatch early page locks over spans of pages.

This is done because misses cost a ladder. Not in SL1? — a cache-miss — hardware quietly fetches from the next level, tens of tics, nobody else notices. Not in RAM at all? — THAT is the page-fault (MPF) — and now the OS itself must step in: insanely expensive. On one classic RISC the ladder reads: 1 tic in SL1, 8 tics from main memory, 400,000 tics on MPF. Perfect world: right next page.

That endless array predictively aligned will always be the next page.

On MPF everything just stops! Linux or UNIX will not try to salvage the situation AT ALL. Because it is much cheaper to flop the entire page which could be a different place in your program or an entirely different program. While the CPU is working on that different next area the MMC will attempt to "figure out" the page-fault situation we’d caused in the background. It will not mark the page queued for execution again until ALL the symbol table references are resolved in its entire span.

So, to go fast, you need to stay on the page as long as possible. And your code MUST be predictable for MMC to load enough segments and branches to keep CPU running as long as possible — the scheduler favors alignable code.

Oh, and one more thing — execution is NEVER in order you wrote your program! The else condition may be executed before your if condition provided it has all the data needed to line the cache. Even if the else condition becomes a throwaway.

And, Compiler Metadata — Code Using Best Practices:

Not much I need to say here — we’re getting long already. Except that modern compilers are well aware of computational nature. Since 1998 prefetch compilers hint heavily to MMC reducing dead-loads by a lot.

Flawed Algorithm!

Now that we see that computation works very differently from human-logic ADD and SUBTRACT — there is one critical point to make here! People who code regularly sooner or later come across "programming best practices" knowledge. Among many suggestions there one stands out:

Code Functional — No Side Effects!

This means "never keep writing to the value you need next!" In other words:
Use val not var. When you need to change things — spit them OUT.

The algorithm depends on the accumulator it uses immediately
  — a cargo-cult optimization: the form of speed, none of the function. Frum!
When you look at the way accumulators are actually written in Functional Programming of Scala, Kotlin, Python, etc. — You’ll notice that they ALL append for later construct use. No Frum.

This type of accumulator is known as transient value — a type of dependency.
And a very well documented antipattern.^[2] The "iteration-carried dependence."

If time permits, I will later spend another hour and write a ParallelSlider that’s suspending — Kotlin’s native stackless concurrency — the fastest way to compute anything. And that will clearly demonstrate how intermediate dependency simply BLOCKS any optimization by parallelism.

Best Kept Secret!!!

"Hey Riddler — how does one learn such things?" And what’s the secret?

The secret is — code real software daily — not "Hello World" from random classes.

And the secret is this: a couple of years ago I’d prepared my preteen son for engineering. Within a year he’s quickly gotten himself to Codeforces Candidate Master. That’s division 1/2. Then he wanted ML. Then he built game modes. Then got bored. The point is, if a curious teenager can figure it out for fun, then software engineers certainly can for a calling.

You get there by understanding algorithms (at first):

Search for the Codeforces Catalog (Orcs block it sometimes).
cp-algorithms.com is the same school in book form — never blocked.
leetcode.com is America-friendly alternative.

But this is where the algos alone and division 2 end — division 1 begins.

When you look at the judge times Grandmasters submit — that is IMPOSSIBLE without thorough and deep understanding of:

1. Hardware — the scheduling and computational nature of the machine;

2. POSIX OS — the process zero and process management of the machine.

What I’d shared here is but a drop in the bucket.
So, keep coding — and have fun doing it!

NOW you get my code. Figure out how the transient dependency completely hoses the stream — what’s different about a stream compared to a huge local array of neatly arranged pages? And, is there ANYTHING you can do about it?

Hint: Yes there is 😉

---

Easter-Egging Ideas

1. Make the numbers falsifiable-by-participation. What’s different on your box? Why?

2. Shorten stride, grow window: make parametrized load test. Any inflex points? Why?

3. Make ParallelSlider! Teach the old wizard a thing or two. (I am always much obliged)

---

Postproduction and Feedback

Short on time, I’d posted this article as a draft. And I got fierce engagement in my Discord communities. Somehow it hit a nerve in just the right way. Let me share with you how it went.

What Hackers Loved:

1. How there are many plausible solutions — all questionable and fiercely debated;
   And, only ONE wrong solution: The Carried Accumulator Optimisation.

2. How there is a lot of room to play and I didn’t add direction-setting code (ParallelSlider).

3. How there’s so much to learn and play with in AVX10, and when Vectorisation kicks in automatically, or even despite compiler flags, and how JIT causes extreme jitter run-to-run.

4. The opinionated way I simulated streaming hinting at yet another related antipattern.

What Hackers didn’t Love:

1. How Mr. S read too much like a person. Fixed: he is Mr. Suit now — see the disclaimer.

2. How my frustration with the problem seeped through: I applied all the language corrections.

3. How I stopped short on the streaming topic. I pushed back, and it was accepted: that’s a book.
   (Also: the champions are still fuming over it on Discord — and I will not hand down some wizard’s verdict that ends a fight this good. Besides, I expect I’ll learn from the champs!)

4. How I was way too nice to Mr. Suit: c’mon guys, seriously?!
   Mr. College didn’t work. Mr. S didn’t work. Every hacker’s villain is a suit.
   Y’know?! I’ve been a suit signing hackers' paychecks!

---

1. Devil’s Advocate: Mr. Suit learned it fair and square. Since I point you to so many wizard hackers fuming over "loop-carried dependence" blocking half of the MMX, I should also explain how it comes to be. Get this! — Every algo curriculum teaches this exact move — USACO Guide: Sliding Window spells it out: "sliding the range forward removes one element and adds another." In the whiteboard model, where every ADD costs 1 and memory is free, it IS OPTIMAL. The model is the problem. And THE problem all too common — on many occasions I found myself "unteaching" this to young engineers, who were resisting fiercely, until I assigned a code-benchmarking problem with a "Lucy, 'splain!" as the pointed deliverable.

2. Compiler folks call it a loop-carried dependence — each iteration needs the previous one’s write; the chain serializes everything. The fun part: the same trick the algo school teaches, the hardware school spends chapters ripping out: Algorithmica: Prefix Sum with SIMD, or the comment thread of Lemire: dot product, where a single accumulator runs 8x under the machine’s add capacity. Start there and follow the citations.

3. 1966 is Flynn’s taxonomy ("Very high speed computers") — the paper that classified and named SIMD. The first working SIMD iron, ILLIAC IV, was built in 1972 and operational from 1974.