otool tells me the assembly routine is 74 instructions (279 bytes, if I’m counting correctly)
I wouldn't call it fluff: even assuming no debugging info (which you won't have in your avr object file) it has info needed at runtime (program start time) such as where to load what into memory, how much initial uninitialised memory to allocate when starting up, etc. It all gets used.
If I dig into the .text segment of the optimized executable, only 235 bytes belong to the main function (others are stuff like __libc_csu_init and register_tm_clones). Looking at the assembly the loop would be about 123 bytes.
So lots of overhead, but I wouldn't say it is in the nested loop.
You have to be careful, a lot of those 8000 bytes might well be printf().
If it was a statically linked executable, it would be far bigger than 8K.
Compilation takes 0.064 seconds, produces 8480 byte executable
I am experienced with Asm so I can come up with an instinctive order-of-magnitude estimate, but even those who aren't should try to roughly estimate how many machine instructions are required to implement that code, and come to the conclusion that over 8000 bytes for three nested loops with not much in them, a comparison, some arithmetic, and a handful of library function calls seems rather excessive. Even 800 would be on the high side --- somewhere around 100-200 bytes is my estimate.
Also, watch this 4k demo (everything you see and hear is generated in realtime by a 4096-byte executable):
https://www.youtube.com/watch?v=jB0vBmiTr6o