Windows devs rerolled old code to save precious bytes

Microsoft's latest Windows update might or might not have improved performance for the company's flagship operating system, but there was a time when its engineers cared about performance. A lot. Veteran Microsoft engineer Raymond Chen on Monday hearked back to that time by telling another war story from the glory days of …

[Electronics'R'Us]

Compact code

Many years ago (early to mid 90s) I was working as a test engineer for a company that made 'smart payphones' Not what we understand that term to be now, though.

Basically a microcontroller, some memory and peripherals that acted as a payphone.

The company offered a flash memory upgrade on one particular line and as those things were very expensive at the time, it was provided in a socket.

I was tasked with writing a self test for this (so the production team could check the device was properly socketed and had no problems). Given that the function to write to the device already existed, this wasn't particularly difficult. What was difficult is that there was a total of 32kB code space (in a UV style EEPROM, microcontroller based on 65C02) and very little was available (around 50 to 60 bytes IIRC).

I managed to write a test (all 6502 assembly, of course) with walking ones and zeros for address and data (a pretty standard test) in 33 bytes. (Not all the instructions were 2 bytes).

Still ran pretty quickly (maximum internal rate for logic was 1MHz with a 4MHz crystal but as we were cheap we used a 3.58MHz NTSC colour burst crystal which were easily available and very cheap).

The days when literally every byte counted.

[ChrisC]

Re: Compact code

"The days when literally every byte counted"

Those days have never gone away for people still working in the embedded systems area - a decade after your anecdote took place, I was tasked with completing a design based around a controller with 1KB of program memory, and even just a few months ago I was working on a design with a relatively paltry 16KB.

[anothercynic]

Re: Compact code

Not just embedded systems. It seems that some mobile OS and app developers seem to have the latest and greatest, and fail to realise that some folks use the bare minimum (think 64GB storage). Some apps are bloaty, some OSes (yes, Apple, that's *you*) are too. Tighter code, less space used by the OS/app would be much appreciated by everyone.

[MiguelC]

Re: "The days when literally every byte counted"

I told this recently, as a kid I coded a game for the ZX Spectrum in Assembler and won a prize from a magazine. They then put me in contact with a professional coder to help reduce my code for 16Kb as it was not even 1 Kb over it and together we made it just that bit smaller so the magazine could publish it to be played in both the 48Kb and the 16Kb models. So I got some free coding lessons along the winning prize, and learned lots of tricks to reduce memory like using alternative instructions that used less bytes (usually just 1, but doing that many time times saves as many bytes) or re-purposing functions, making them more generic in order to allow reuse.

[Doctor Syntax]

Re: "The days when literally every byte counted"

ISTR that the Z80 had an instruction that would initialise blocks of memory. It was essentially a block copy to copy a block of memory to another bock. But if a single address, n, had the required value set then the block copy could be set to coy from the block starting at n to the block starting at n+1.

[Hawkuletz]

Re: "The days when literally every byte counted"

The beloved LDIR (although some would use LDDR, going the other way around) :)

[FifeM]

Re: "The days when literally every byte counted"

I had years of fitting software into tiny embedded systems.

We learned that every piece of software can be reduced in size, given sufficient effort. Also that all software contains at least one bug.

In the limit, all software can be reduced to a single instruction, which will be wrong.

[abend0c4]

Re: Compact code

Talking of 6502 code, the Commodore PET ROM was (in)famous for apparently jumping/calling into what appeared to be the middle of an instruction. However, the target address, whilst part of an instruction (the operand) just happened to contain a value that was a valid instruction in its own right, so you could obtain a different (and determinate) outcome depending on whether you started execution at the outer or inner instruction...

[Electronics'R'Us]

Re: Compact code

I am reminded of The Story of Mel

[DaveK23]

Re: jumping/calling into what appeared to be the middle of an instruction.

The infamous BIT $XXYY instruction. Apart from saving code space, it also helped with the fact that conditional branches had a maximum range of +128/-127(*) bytes, so you could save having to branch to a long JMP instruction sometimes.

(*) - yes, I know it looks wrong, but it ain't. Ask me why if ya don't know ;-p

[Ken Hagan]

Re: Compact code

Such tricks were well known back in the day. According to the book Windows Internals, Windows 3.0 used an x86 equivalent of the same trick. It also implemented the bitmap-fiddling BitBlt() API by pushing (argument-dependent) code onto the stack and calling it.

That would cause an access violation now, of course, but such things didn't exist in those days.

[that one in the corner]

Re: Compact code

> implemented the bitmap-fiddling BitBlt() API by pushing (argument-dependent) code onto the stack and calling it.

A trick performed earlier by the Apple Macintosh QuickDraw ROM functions. Back in the time when The Wiz was Woz (only just), those routines were designed and written by Bill Atkinson and Andy Hertzfeld.

[Sproggit]

Re: Compact code

My first full-time employment included a "side-line" in writing software for the BBC Microcomputer... another 65C02 based machine. The Beeb used memory-addressed peripherals [no pesky device drivers for you, me boy] and page-swapping to enable it to support more addressable storage than the default 64kb. The lower half of the address space was RAM, the upper half was ROM. Acorn's Operating System sat in the "top half" of the ROM address space and the lower half - i.e. memory from 32768-49151 was reserved for "paged ROMs" ...

The OS itself had a design convention that identified "system commands" through the use of an asterisk to prefix the command and anything submitted to the command line prefixed with an asterisk would first be offered to the OS; then, if it was not recognized, the OS would "page" through any installed ROMs, swapping them in to the available address space and offering them the unknown command. If it tried all available ROM's and didn't get a bite, it would issue an "unknown command" response.

So far, so good.

I was asked by my boss to take some code [written in BBC BASIC] that provided ISAM functionality to the Beeb's flat data files [basically, giving them an Indexed-Sequential Access Methodology index-retrieval system] and convert the code in to 6502 assembler so that we could shunt all the index-handling logic in to ROM to save RAM for actual "business logic". A couple of different "6502 Assembly Language Programming" books later and I had working code - able to support 3-tier indices with up to 20 keys per block [blocks aligned in size with disk sectors for IO efficiency]. Translation: it could handle 4000 records assuming 50% index density - theoretically up to 8000 records, but that would be a bit optimistic.

The catch? My code compiled down to about 10kb.

At which point my boss announced that he'd already been out and purchased a stack of 8kb EEPROMs and I'd just have to rewrite my assembler to make it more compact.

Took me about a month - and let me tell you, that remains one of the toughest programming challenges I've ever faced. The first half - getting the code from about 10kb down to about 9kb was *relatively* straightforward... I cheated a little bit as I had a couple of unfolded loops that I'd written to perform "block copy" operations when performing a "block split" of one of my index blocks... It slowed down the update operation - but I figured that since the machine was physically writing to disk and since the disk operation would be a limiting factor, I could likely get away with it, so I just folded the code back up as a loop and saved a bunch of memory.

But getting those last few bytes, down from about 8300 or 8400 bytes to something that would fit in an 8kb EEPROM... Man, that was *hard*... and to get there I ended up using solutions I find "ugly" to this day... For example, the 6502 uses different types of code branching: JMP ["Jump to memory location and start executing"] and JSR - Jump to SubRoutine - ["push your memory location on to the heap, jump to a memory location and start executing... then, when you encounter a "Return" opcode, pull the address of the heap and go back there before executing..."]. You end up writing subroutines with multiple entry points, then a common exit/return, because doing that will save you a *single byte* of RAM, since you now only need one "return" opcode.

Or you make a "declaration" that your code won't run on a BBC Micro equipped with an IEEE488 interface [used with oscilloscopes, voltmeters, logic analyzers and the like], because that would free up a tiny amount of RAM in Page Zero. And Page Zero RAM was invaluable because the hex structure for:-

LDA &40 [Load the Accumulator with the contents of memory address hex 40, which is *in* Page Zero]

took two bytes of RAM to express, while the hex structure for

LDA &1900 [Load the Accumulator with the contents of memory address hex 1900, which is not in Page Zero]

took *three bytes* of RAM to express...

I found that by rewriting my assembler to use Page Zero addresses saved me *just* enough to get my code to compile down to 8kb.

At the time I hated it... I had no experience of assembler and I really struggled. There was no "internet" to turn to and no "user group" to ask... After the first couple of weeks I convinced myself my boss would fire me in disgust, but he seemed genuinely surprised that I'd managed it.

We can look back on a 6502 today - 2MHz clock, three 8-bit registers (Accumulator, X and Y registers) and then 8 one-bit status flags (e.g. the Carry Flag) - and think of it as crude and primitive...

But learning what was needed to wring the last drop of performance out of that antique piece of silicon gave me skills that have paid me back over decades.

[G.Y.]

watch Re: Compact code

A Microsoft smart watch (1MB ROM) once ran out of ROM, 3 nanoseconds before going to silicon. There was some scrambling to be done (replace a cipher by a smaller one)

[Clausewitz4.1]

Re: Compact code

"The days when literally every byte counted"

Those days arent gone. A few years back I was writing a PIC16F(or 18F dont remember) appliance for a customer. Code did fit, but I was lacking a buffer. Got an hex editor and used a region full of zeroes. Never crashed.

[DaveK23]

Re: used a region full of zeroes. Never crashed

Not sure how I feel about this without more details. Are you saying that you had literally no idea what this bunch of zeroes was for? And you didn't know how to look it up in a .MAP file? And you just hacked that buffer in there on a wing and a prayer, and try to justify it because it "never crashed"? In your lab before release, or in the field, after this non-updateable embedded product went out to customers? Because if so, I am the opposite of impressed. That would be terrible, amateurish, unprofessional and incompetent behaviour.

If on the other hand you did know why it would be ok, none of that applies. But from your description, I just can't tell.

[42656e4d203239]

Compact HTML

Hmmm not really code, but a young dev I once had the pleasure of overseeing wrote some lovely code to display certain data in a particular format using an HTML table (yup - I know...).

Sadly this dev forgot that the letter C in CSS stood for cascading and sent the whole style sheet for every style change (an MS Word one... yet again I know; this was a customer requirement of sorts) with every cell - performance of that page was dire until he worked out (application of clue bat) that he only needed to send the styles once... and then override them if required (it wasn't always).

[may_i]

I blame Pascal

Pascal started the idea of writing programs which got compiled into instructions for a non-existent CPU and then converting that to real instructions at runtime. The dream being portability.

I thought it was a bad idea then and think C# is an equally bad idea. Sadly, there are too few of us left now who understand how a computer actually works and why treating memory and CPU cycles as the limited resources they are is still a good idea.

[Brewster's Angle Grinder]

Grrr, get off my lawn!

Ahhh, good old p-code!

As well as C#, Java and WASM do the same. Meanwhile the shaders for your GPU are sent as source and compiled in situ. Likewise, Javascript doesn't even bother sending the intermediate representation but relies on a solid JIT. (And I'm sure several other interpreted languages would like a similarly good JITs). And, at a hardware level, X86 instructions are pretty much p-code for the underlying processor, even when it's an X86 processors.

Like everything else in IT, it's a trade off. You're trading portability for a slower first run or a small (possibly-one time) overhead at start up. And it's an idea that has grown in popularity, not diminished.

[abend0c4]

Re: I blame Pascal

Pascal started the idea of writing programs which got compiled into instructions for a non-existent CPU

I'm pretty sure BCPL's O-code came before P-code...

[that one in the corner]

Re: I blame Pascal

>> Pascal started the idea of writing programs which got compiled into instructions for a non-existent CPU

> BCPL O-code...

Object code for an abstract machine, CINTCODE, was also available as the *final* output of a BCPL compiler[1]: modules in CINTCODE could be linked with libraries and the result run on a virtual machine. For example, the BBC Micro had a language ROM with the CINTCODE VM released by Acorn (not too surprising, given the Cambridge connections) with the compiler, link editor, text editor and utilities on floppy.

This *also* predated the UCSD P-system VM doing the same trick. Although I am not aware[2] of a hardware implementation of CINTCODE, unlike P-code, which had more than one (including the Three Rivers Perq or "Pascal engine running quickly"); so I'll give P-code a win on that one.

Java, of course, then borrowed the VM trick, along with many other languages, including Lua, Python etc etc; so much easier than writing a full native compiler.

Then we get into VM opcodes being JIT compiled...

>> Sadly, there are too few of us left now who understand how a computer actually works and why treating memory and CPU cycles as the limited resources they are is still a good idea.

BCPL most definitely comes from a time when everyone knew precisely how much RAM cost, how much each CPU cycle cost - and they still went with not one, but two, abstract machines!

[1] there is a passing ref to it in the Wikipedia article, ref [9] to be precise; their ref [2] is actually a description of the runtime and entire OS built on CINTCODE, from which the article only extracts the use of curly braces!

[2] hopefully someone can point us towards one?

[Anonymous Coward]

Re: I blame Pascal

Isn't that how LLVM (Clang) works too?

[Howard Long]

While extreme "spitting out 256 KB of code just to initialize 64 KB of data", in the deeply embedded world we still care about clock cycles, power consumption, and flash & RAM usage. It's not at all unusual to unroll code if the target has plenty (relatively speaking) of flash available but not much in the way of time.

The downside of this approach is that you often end up with write-only macro-fu, although nothing that a decent bit of commentary can't resolve, assuming the maintainer bothers to read it. The frustrated maintainer is also often the originator of the macro-fu, a friend tells me.

[Flocke Kroes]

If you don't have an instruction cache then fine. As we are going back to the 32-bit era there might not have been a level 2 cache but there probably were small instruction and data caches. That 256K would have come from slow main memory while taking memory bandwith away from the task of initialising the 64k of data. If there was anything useful in the instruction cache before it will all be gone after that unrolled loop. Sometimes the best strategy is to optimise the bulk of the code for space and only optimise the innermost loops for time.

[Howard Long]

"If you don't have an instruction cache then fine"

I did say "deeply embedded"!

I'm talking in terms of flash in tens of KB, and RAM a couple of KB. Oh, and mean power in terms of nanowatts, running for decades on a button cell, and running at a few kHz. I wasn't just talking about unrolling loops, I was talking in terms of (effectively) hard-coding a series of writes for potentially many dozens if not hundreds of macro-generated functions with computed calls rather than iterating a lookup table & take the hit on loop overhead and pointer/array arithmetic and indirection.

"Going back to the 32-bit era": In my ultra low power world, 32 bit isn't great for power consumption compared to 8 bit: 32 bit has lots of transistors switching that you don't need. It's application specific of course.

My "friend" does do plenty of embedded 16- and 32- bit too, and yes, as you say, you do need to be aware of I-cache and D-cache, prefetch, wait states etc. For performance, unrolling a loop is almost essential to avoid pipeline stalling: it's not just I-cache you need to be worried about.

"Sometimes the best strategy is to optimise the bulk of the code for space and only optimise the innermost loops for time."

Yes, agreed. And there's little point in unrolling something that isn't a botttleneck.

[that one in the corner]

> Sometimes the best strategy is to optimise the bulk of the code for space and only optimise the innermost loops for time.

Sometimes?!

Us humans are much better at spotting, accurately, code bloat than which bit of code needs to be sped up. The bigger the project, the wider that gap becomes ("why have you added a *third* XML parser, for pity's sake just learn how to call into an existing one!").

"Make it work. Make it right. Make it fast." In that order.

Before even *thinking* about diving into the third stage, RUN THE PROFILER! Everyone *thinks* they know where the time is spent ("that code uses Bubble Sort, for pity's sake! Let me at it!") but the profiler shows that it is only ever called twice per day, on less than 15 items; making that 100 times faster doesn't materially effect anything. But *this* code is executed umptymillion times a minute and whilst it is actually pretty good code, even a 5% speedup here will work wonders!

And ALWAYS make sure your build system can generate profiler-instrumented code from day one: during stages 1 and 2 it is invaluable to be able wave profile output in front of the dev who is spending their time "optimising this obviously slow routine" - not only can you can show them it accounts for less than 1% of the runtime *and* you are still in the stages where that particular code (any particular bit of code) may still be chucked out because it is discovered to the the wrong thing to be doing in the first place.

[Doctor Syntax]

"why have you added a *third* XML parser"

A long time ago I did just that.

The system used an XSLT step based on the Microsoft parser which could assign memory orders of magnitude bigger than the document to construct a DOM*. As the incoming documents consisted of a string of work orders there was much to gain - including memory not consumed by feeding the transform one order at a time. The answer was a SAX parser** which hard coded the expected schema to chop the string of orders into individuals which could be fed to the Microsoft parser. That stopped the Microsoft parser from blowing up when hit with production-sized data.

But there was the possibility of reusing this code for similar purposes for orders from other customers who might well have their own schemata. To enable that I wrote the SAX parser to take a schema with its own namespace. The third parser was in the SAXON XSLT application that only required a transform to be written to convert the customer's data into one that could be fed into my SAX parser. The result was that the same core code could be reused for a number of different contracts with only a new XSL having to be written.

* I don't know if this is still the case but it wouldn't surprise me if it is.

** SAX parsers don't try to construct a DOM so are much more economical of memory. SAXON, of course, is based on SAX; the cloue's in the name.

[that one in the corner]

Using SAX to cut the document into chunks the DOM creator could handle! Wow.

SAX-like parsers are what I reach for first, unless there are *good* reasons not to; then again, my first "using XML for real" job involved gigabyte-sized files (and with good reason to be that large, btw) handled on a 32-bit XP box with a whopping 256MB RAM. The "expat" parser is brilliant!

On other projects, I have so many desk dents caused reading code from devs who threw DOM parsers at everything; the worst cases were products that had multiple processes in an embedded Linux system:

Processes can come and go as needed, but there would be 1(one) XML configuration file to describe an entire installation, which can include a lot of separate computers networked together. That is ok, the operator can update the entire install by uploading one file, which then propagates by magic across all the boxes. Obviously, each process only needs to bother with the bits of XML which concern *its* parameters for *its* particular box. Any particular parameter may be needed by multiple processes, or may only be of interest to one process - all perfectly fine, the operator's XML deals in "meaningful" values and processes go fetch what they require without the operator needing to know who uses which.

So, of course, at startup, each process would read the entire XML into a DOM (as you say, needing many times the memory to do that) and then have to walk the DOM looking for anything useful, gleefully ignoring most of it. The process shuts down and is restarted as needed? Go for the DOM!

I did point out that "expat" was sitting there ready to be used, just in case they ever got the system working correctly enough to get into the "Make it fast" stage, but by then it was no longer my problem. Shame, in a way, as I had wanted to try having one shiny new process that loaded all the config for the box into a nice compact binary struct and allowed shared memory access to all the other processes, just to see if that improved things.

[Doctor Syntax]

The reason for using the DOM was that XSLT was needed and it was there out of the MS box. I suppose I could have done the entire transformation in one go with SAXON but handling the product in one g would have has its own problems.

Another benefit of doing it the way I did: I validated the XML at the 3rd stage against a schema. That was preferable to validating the entire incoming document. I had no great confidence in the abilities of the other end to get their ML right but if there was an invalid order in the incoming file that one order could be bounced rather than the entire document.

Unfortunately the other end's failure mode was to periodically sending badly formed XML instead which was reject in its entirety at the first step. What I think happened was that the S/W house they used rotated their Indian coders when their visas ran out. The newly arrived recent graduates kept coming across bits of code they didn't understand and sometimes removing it - and eventually their simplified code came across a surname such as O'Neil or O'Malley....

We had to do periodic training. Unfortunately they were too far away to do this with a 2 by 4.

[C R Mudgeon]

' "Make it work. Make it right. Make it fast." In that order.'

Alas, the Prime Directive is usually "Make it now". Time to market über Alles.

[Howard Long]

'" "Make it work. Make it right. Make it fast." In that order.'"

Somehow, that doesn't apply to AI.

[that one in the corner]

> If you don't have an instruction cache then fine

Anyone else remember when CPU cache was something you would purchase as a optional extra?

Even when the 486 was young, you had to be a rich bugger to afford all the CAM* chips to fill the empty sockets on the motherboard to get that extra layer of cached goodness.

* Content Addressable Memory, not ASRock's "Clever Access Memory"!

[Bebu sa Ware]

emulator for an unnamed processor… identify potential candidates

At a guess MIPS, Alpha, PPC — supported by NT4.

I recall one DEC Alpha workstation arrived with Win2K installed (had to switch firmware to install DEC Unix OSF1.) I suppose some of x86 driver code had to be emulated especially third party stuff.

Transcompiling from one instruction set to another has always been an interesting area — JIT is basically that with lazy rather than strict evaluation. ;)

[Sorry that handle is already taken.]

Re: emulator for an unnamed processor… identify potential candidates

Itanium is my guess

[DaveK23]

256 KB of code just to initialize 64 KB of data?

That ain't gonna fit in your icache, so you're trading off worse memory usage for worse performance. Stupid compiler!

[Hawkeye Pierce]

Compiler Optimisation

I heard this story several (more than I care to actually state) decades ago and I was a little suspicious of it back then but here goes. To set the scene, remember that this was multiple decades ago and was at least a decade old story then.

Some benchmarks were being performed on how good the code was produced by multiple Fortran compilers (may not have been Fortran but it will serve the purpose). The code consisted of a function that simply calculated Pi to a certain number of decimal places and then quit. The test was run on a couple of compilers and the resulting code then timed as it looped around multiple times to work out the answer to the stated precision. Then another compiler was tried and the code it produced was incredibly faster. When they looked at the code, they discovered that the compiler had identified that the code had no external inputs of variables and so the outcome was completely pre-deterministic. The compiler itself ran the calculation to work out the value, and the code it produced simply set the variable to the calculated value. Job done!

Then (supposedly) yet another compiler was run that produced a tiny file that ran even faster. That compiler had identified that having calculated the value of Pi, it wasn't output to anything at all and thus the whole code was completely pointless and the program produced was simply a no-op - did absolutely nothing!

[david 12]

Re: Compiler Optimisation

The Intel Fortran compiler - used for highly optimized math-intense code -- demonstrated this behavior in comparisons. But, FWIW, the Intel Fortran compiler was, like many optimizing compilers then and now, an optimizing backend with several available front ends, and would presumably demonstrate the same behavior on C comparisons or other supported languages.

[Pete Sdev]

Ellipsis

Learn to use them properly.

They're not a substitute for scare quotes.

[that one in the corner]

Re: Ellipsis

But they *are* useful for indicating where you have removed words from the sentence, such as:

that a compiler had <bleep> optimized <bleep> <bleep> <bleeeeeeeep> the code

[david 12]

Not all ... are ellipsis.

[Anonymous Coward]

A total ellipsis of the heart

[Kurgan]

The only time MS cared about efficiency

The only time MS cared about efficiency was when Bill wrote his first BASIC for the Altair 8800. That was efficient.

[Old Iron]

VAX Instruction Unroll

If I remember correctly, in some places of the VMS kernel on the VAX 11/780, single MOVQ (64 bit move) instructions were replaced by two MOVL (32 bit move) instructions. I believe the two MOVL's instructions had been found to be faster than a single MOVQ.

[abend0c4]

Re: VAX Instruction Unroll

The transition from 16-bit to 32-bit words implied a significant associated cost when memory was very expensive. A significant number of the VAX instructions were aimed at reducing code size rather than maximising performance. Similarly, the decision to allow unaligned memory access which could incur a significant penalty if the instruction and its operands were all misaligned. What you choose to optimise for today may well be the wrong trade-off tomorrow.

[Luiz Abdala]

Games need optimization too.

There is a youtuber famous for breaking games or pushing their code to the limit. Josh from "Let´s Game It Out".

He took a game called Satisfactory, and brought it to its knees. (You can still watch the whole thing, still up. The game was made in the Unreal Engine, by the way).

The devs took a look at what he did, took it as a challenge, and proceeded to optimize the code. They asked him for his save file to recreate the problem, and got to work.

They managed quite a lot of miracles, like reusing memory for assets (shocker!) and other things, and you could see IN REAL TIME the game chugging at 20 frames per second and going up to 45 or something after a patch, documented by Josh himself.

They liked so much what Josh did that they used HIS save file to take the pictures for the game on the Steam page. Not kidding, the game still uses his screenshots to this day.

[DaveK23]

Re: Best practice

The very best of best practices, as every seasoned dev knows, is this: TALK TO YOUR USERS. The Satisfactory Devs were more than just satisfactory!

[[e-mail]]

Compression

A company I worked for, developed smartcards with Java applications. When the code was almost ready, it turned out not to fit in the small ROM on the card, and no optimisations and compiler settings could shrink it enough.

I first tried some ZIP like algorithm, but the overhead of the decompressor was more than the savings.

Searching the Internet, I found an idea from the French technical university INSA, which suggested to combine often occurring sequences of bytecode to a new bytecode. The JavaCard VM uses only 182 of the 255 possible codes.

So: analyze the compiled software for combinations, write a translator (both offline processes), and adapt the VM to process the new codes. The latter did not require much extra space, mainly adding a lot of evil gotos. In the end, the program was about 30% smaller and slightly faster.