8 ms·

Optimizing a 6502 image decoder, from 70 minutes to 1 minute

195 points by davikr 1y ago

JSR_FDED 1y ago
Good reminder to do less, rather than the same thing but optimized.
- iberator 1y ago
  Yeah. Amazing idea and execution (counting number of instructions per module).
- deleted 1y ago
  [deleted]
flanked-evergl 1y ago
If I have the "Without interpolating, we can clearly see we only have half the pixels." image entirely on screen, using Chrome, KDE with X11 on Ubuntu 24.04, then it makes my whole screen change colour. Everything becomes slightly darker or something. Very odd. I will try it on another computer.
- Cockbrand 1y ago
  Without having tried it, maybe there's some HDR content on the page, triggering the display's HDR mode?
- opello 1y ago
  I wonder if there's not some adaptive backlight automatic gain control cueing off of the moire image's black pixels, since you describe things as slightly darker.
JKCalhoun 1y ago
I kind of enjoy seeing these posts from time to time on HN. I thought it was my age (I remember this hardware) but I think a lot of engineers are enjoying practicing their craft in a more pure environment with so few (or no) layers of abstraction underneath. Refreshing at times, isn't it?
- dylan604 1y ago
  For me, it's less the abstraction vs having hard limits on things like memory. Modern software has nearly limitless memory compared to the less than 1MB typical on these projects. It was definitely a lesson I had to learn. As far as the abstraction, when does it get to a point the compiler can't undo the abstraction? At what point does one need to get to a point where something cannot be done?
  - tmoertel 1y ago
    On 6502-based systems the available memory was often less than 64 KiB, the maximum addressable by the processor directly. Still, you could squeeze a lot into that small amount of you were clever. For example, Steve Wozniak wrote in BYTE magazine about computing e to over 100K places on an Apple 2: > I first calculated e to 47 K bytes of precision in January 1978. The program ran for 4.5 days, and the binary result was saved on cassette tape. Because I had no way of detecting lost-bit errors on the Apple (16 K-byte dynamic memory circuits were new items back then), a second result, matching the first, was required. Only then would I have enough confidence in the binary result to print it in decimal. Before I could rerun the 4.5 day program successfully, other projects at Apple, principally the floppy-disk controller, forced me to deposit the project in the bottom drawer. This article, already begun, was postponed along with it. Two years later, in March 1980, I pulled the e project out of the drawer and reran it, obtaining the same results. As usual (for some of us), writing the magazine article consumed more time than that spent meeting the technical challenges. See page 392 of https://archive.org/details/byte-magazine-1981-06 https://archive.org/details/byte-magazine-1981-06.
  - HarHarVeryFunny 1y ago
    > As far as the abstraction, when does it get to a point the compiler can't undo the abstraction? The early 8-bit systems were so constrained in everything from memory to registers, instruction set, and clock speed, that using a high level language wasn't an option if you were trying to optimize performance or squeeze a lot of functionality into available memory. An 8-bit system would have a 64KB address space, but maybe only 16-32KB of RAM, with the rest used by the "OS" and mapped to the display, etc. The 6502 was especially impoverished, having only three 8-bit registers and a very minimalistic instruction set. Writing performant software for it depended heavily on using "zero-page" memory (special addressing mode to access 1st 256 bytes of memory) to hold variables, rather than passing stack based parameters to functions, etc. It was really a completely different style of programming and mindset to using a high level language - not about language abstraction, but a painful awareness of the bare metal you were running on all the time.
6510 1y ago
It is quite surreal to me that this was not the road taken. Optimizing software doesn't have the same potential as optimizing hardware but i'd say 1/70 is significant. If thousands of people would work on this indefinitely the time would drop to seconds. That code would also be completely incomprehensible. The argument that people should just buy a faster computer could just as easily have worked out the other way around, just write faster software. Going the hardware way gave us really really readable code which is great. The other direction however would have given us really really cheap devices. Receiving and sending a signal for [say] a chat application requires very little stuff. It would be next to impossible to add images, word suggestions or spell checkers. We could still bake mature applications onto dedicated chips. But until now those efforts went pretty much nowhere(?) I imagine one could quite easily bake a mail client or server, or a torrent client, irc, perhaps even a gui for windowed applications. Maybe an error console?
- dr_zoidberg 1y ago
  In the ~30 years I've used computers, they've become ~1,000,000 times faster. My daily experience with computers doesn't show it. There's someone out there who took the time to measure UI latency and has shown that, no only isn't it faster, it's actually slowed down. And yet, our hardware is 1,000,000 times faster... Edit: this is the latency project I was thinking about https://danluu.com/input-lag/ https://danluu.com/input-lag/
  - 6510 1y ago
    What beautiful table in how it is seems sorted both by time and latency with the exception of some systems that are ahead of their time in slowness. If you put a bit of load on the modern hardware things get dramatically worse. As if there is some excuse for it. I had this thought long ago that the picture on the monitor could be stitched together from many different sources. You would have a box some place on the screen with an application or widget rendered in it by physically isolated hardware. An input area needs a font and a color scheme. The text should still be send to the central processor and/or to the active process but it can be send to the display stitcher simultaneously. You could even type a text and have it encrypted without the rest of the computer learning what the words say. I look at and click around KolibriOS one time, everything is so responsive it made me slightly angry.
anyfoo 1y ago
Isn't it crazy how the image where every other pixel is black (labeled "Without interpolating, we can clearly see we only have half the pixels") sort of looks to have higher fidelity than the one after it, where the black pixels have been removed, which now looks pixelated? And yet both images have the exact amount of information, because all pixels that have been removed are simply black. The effect is so pronounced, that I wonder whether there wasn't any additional processing between the two images. Compare the window with the sky reflection between the two: In the image without black pixels, it looks distorted and aliased, while in the one with, it looks pristine. If actually only the black pixels have been removed (and the result nearest-neighbor scaled), I think the black pixel grid is a form of dithering, although neither random, nor the error diffusion kind one usually thinks of when hearing "dithering". There is no error being diffused here, and all added pixels are constant black. Maybe the black pixels allow the mind to fill in the gaps (shifting the interpolation that was also removed, prior to the black pixel image, to our brain, essentially). It is known that our brain interpolates and even straight makes up highly non-linear stuff as part of our vision system. A famous example of that is how our blind spot, the fovea where the optic nerve comes out, is "hidden" from us that way. The aliasing would "disappear" because we sort of have twice the amount of samples (pixels), leading to twice the Nyquist frequency, only that half of the samples have been made up by our vision system through interpolation. (This is a way simplified and crude way to look at it. Pun unintended.) But before jumping to such lofty conclusions, I still wonder whether nothing more happened between the two images...
- bawolff 1y ago
  If i understand, the picture without black pictures is half the resolution at 320x240. That's small enough your browser might be upscaling it
  - anyfoo 1y ago
    I just opened both pictures in separate tabs, the browser says that both are 640x480. But that's a good point nonetheless: That 640x480 picture is certainly upscaled somehow, otherwise it would be absolutely tiny on a retina display. That upscaling might certainly lead to very different results from both images. However, when I download the images and open them in Preview, I get the same result. When I zoom in, I do see individual pixels. It looks like it just did nearest neighbor upscaling, so I'm not sure upscaling is at fault here.
homarp 1y ago
Part II: https://news.ycombinator.com/item?id=45467707 https://news.ycombinator.com/item?id=45467707

195 points by davikr 1y ago

JSR_FDED 1y ago

Good reminder to do less, rather than the same thing but optimized.

iberator 1y ago
Yeah. Amazing idea and execution (counting number of instructions per module).
deleted 1y ago
[deleted]

flanked-evergl 1y ago

If I have the "Without interpolating, we can clearly see we only have half the pixels." image entirely on screen, using Chrome, KDE with X11 on Ubuntu 24.04, then it makes my whole screen change colour. Everything becomes slightly darker or something. Very odd. I will try it on another computer.

Cockbrand 1y ago
Without having tried it, maybe there's some HDR content on the page, triggering the display's HDR mode?
opello 1y ago
I wonder if there's not some adaptive backlight automatic gain control cueing off of the moire image's black pixels, since you describe things as slightly darker.

JKCalhoun 1y ago

I kind of enjoy seeing these posts from time to time on HN. I thought it was my age (I remember this hardware) but I think a lot of engineers are enjoying practicing their craft in a more pure environment with so few (or no) layers of abstraction underneath. Refreshing at times, isn't it?

dylan604 1y ago
For me, it's less the abstraction vs having hard limits on things like memory. Modern software has nearly limitless memory compared to the less than 1MB typical on these projects. It was definitely a lesson I had to learn. As far as the abstraction, when does it get to a point the compiler can't undo the abstraction? At what point does one need to get to a point where something cannot be done?
- tmoertel 1y ago
  On 6502-based systems the available memory was often less than 64 KiB, the maximum addressable by the processor directly. Still, you could squeeze a lot into that small amount of you were clever. For example, Steve Wozniak wrote in BYTE magazine about computing e to over 100K places on an Apple 2: > I first calculated e to 47 K bytes of precision in January 1978. The program ran for 4.5 days, and the binary result was saved on cassette tape. Because I had no way of detecting lost-bit errors on the Apple (16 K-byte dynamic memory circuits were new items back then), a second result, matching the first, was required. Only then would I have enough confidence in the binary result to print it in decimal. Before I could rerun the 4.5 day program successfully, other projects at Apple, principally the floppy-disk controller, forced me to deposit the project in the bottom drawer. This article, already begun, was postponed along with it. Two years later, in March 1980, I pulled the e project out of the drawer and reran it, obtaining the same results. As usual (for some of us), writing the magazine article consumed more time than that spent meeting the technical challenges. See page 392 of https://archive.org/details/byte-magazine-1981-06 https://archive.org/details/byte-magazine-1981-06.
- HarHarVeryFunny 1y ago
  > As far as the abstraction, when does it get to a point the compiler can't undo the abstraction? The early 8-bit systems were so constrained in everything from memory to registers, instruction set, and clock speed, that using a high level language wasn't an option if you were trying to optimize performance or squeeze a lot of functionality into available memory. An 8-bit system would have a 64KB address space, but maybe only 16-32KB of RAM, with the rest used by the "OS" and mapped to the display, etc. The 6502 was especially impoverished, having only three 8-bit registers and a very minimalistic instruction set. Writing performant software for it depended heavily on using "zero-page" memory (special addressing mode to access 1st 256 bytes of memory) to hold variables, rather than passing stack based parameters to functions, etc. It was really a completely different style of programming and mindset to using a high level language - not about language abstraction, but a painful awareness of the bare metal you were running on all the time.

6510 1y ago

It is quite surreal to me that this was not the road taken. Optimizing software doesn't have the same potential as optimizing hardware but i'd say 1/70 is significant. If thousands of people would work on this indefinitely the time would drop to seconds. That code would also be completely incomprehensible. The argument that people should just buy a faster computer could just as easily have worked out the other way around, just write faster software. Going the hardware way gave us really really readable code which is great. The other direction however would have given us really really cheap devices. Receiving and sending a signal for [say] a chat application requires very little stuff. It would be next to impossible to add images, word suggestions or spell checkers. We could still bake mature applications onto dedicated chips. But until now those efforts went pretty much nowhere(?) I imagine one could quite easily bake a mail client or server, or a torrent client, irc, perhaps even a gui for windowed applications. Maybe an error console?

dr_zoidberg 1y ago
In the ~30 years I've used computers, they've become ~1,000,000 times faster. My daily experience with computers doesn't show it. There's someone out there who took the time to measure UI latency and has shown that, no only isn't it faster, it's actually slowed down. And yet, our hardware is 1,000,000 times faster... Edit: this is the latency project I was thinking about https://danluu.com/input-lag/ https://danluu.com/input-lag/
- 6510 1y ago
  What beautiful table in how it is seems sorted both by time and latency with the exception of some systems that are ahead of their time in slowness. If you put a bit of load on the modern hardware things get dramatically worse. As if there is some excuse for it. I had this thought long ago that the picture on the monitor could be stitched together from many different sources. You would have a box some place on the screen with an application or widget rendered in it by physically isolated hardware. An input area needs a font and a color scheme. The text should still be send to the central processor and/or to the active process but it can be send to the display stitcher simultaneously. You could even type a text and have it encrypted without the rest of the computer learning what the words say. I look at and click around KolibriOS one time, everything is so responsive it made me slightly angry.

anyfoo 1y ago

Isn't it crazy how the image where every other pixel is black (labeled "Without interpolating, we can clearly see we only have half the pixels") sort of looks to have higher fidelity than the one after it, where the black pixels have been removed, which now looks pixelated? And yet both images have the exact amount of information, because all pixels that have been removed are simply black. The effect is so pronounced, that I wonder whether there wasn't any additional processing between the two images. Compare the window with the sky reflection between the two: In the image without black pixels, it looks distorted and aliased, while in the one with, it looks pristine. If actually only the black pixels have been removed (and the result nearest-neighbor scaled), I think the black pixel grid is a form of dithering, although neither random, nor the error diffusion kind one usually thinks of when hearing "dithering". There is no error being diffused here, and all added pixels are constant black. Maybe the black pixels allow the mind to fill in the gaps (shifting the interpolation that was also removed, prior to the black pixel image, to our brain, essentially). It is known that our brain interpolates and even straight makes up highly non-linear stuff as part of our vision system. A famous example of that is how our blind spot, the fovea where the optic nerve comes out, is "hidden" from us that way. The aliasing would "disappear" because we sort of have twice the amount of samples (pixels), leading to twice the Nyquist frequency, only that half of the samples have been made up by our vision system through interpolation. (This is a way simplified and crude way to look at it. Pun unintended.) But before jumping to such lofty conclusions, I still wonder whether nothing more happened between the two images...

bawolff 1y ago
If i understand, the picture without black pictures is half the resolution at 320x240. That's small enough your browser might be upscaling it
- anyfoo 1y ago
  I just opened both pictures in separate tabs, the browser says that both are 640x480. But that's a good point nonetheless: That 640x480 picture is certainly upscaled somehow, otherwise it would be absolutely tiny on a retina display. That upscaling might certainly lead to very different results from both images. However, when I download the images and open them in Preview, I get the same result. When I zoom in, I do see individual pixels. It looks like it just did nearest neighbor upscaling, so I'm not sure upscaling is at fault here.

homarp 1y ago

Part II: https://news.ycombinator.com/item?id=45467707 https://news.ycombinator.com/item?id=45467707