The NES supports a 4-screen screen memory or "nametable", and the PPU, or graphics chip, can be programmed with one or two register writes to basically display any position within that 4 screens. Scrolling is just updates to the scroll registers and populating new video data on the incoming edge (which has to happen during VBLANK).
Whereas the C64's VIC-II can only select a few fixed places to start reading video memory to render the screen (2k boundaries for text mode). It can finely shift the screen left or right up to 8 pixels, but scrolling past that requires a many, many cycle recopy of RAM to video memory. Throw in the need to recopy color memory as well and that puts the C64 at a serious disadvantage.
Looks like this game on the C64 used some really advanced technique called VSP, which tells the VIC to I guess read from arbitrary memory addresses instead of the fixed ones it normally supports. This apparently exposed a VIC-II hardware bug that can corrupt RAM (since VIC-II is responsible for DRAM refresh). Really interesting. Seems some systems are more susceptible to this hardware bug than others, and there's difficult software workarounds for it.
For that matter you could double buffer and spread the copying of the tiles (not the colors) over multiple frames. The normal approach if you for whatever reason could find a way to copy what you needed, though, was simply constraining the amount of the screen you used a bit and e.g. putting extra decoration top/bottom.
But really, Mario should not be a challenge to do this for - the C64 had tons of platform games of similar complexity. Especially Giana Sisters - put this video of Giana Sisters side by side with the Mario version above from the start of level 1, and see why Nintendo threatened the publishers:
https://www.youtube.com/watch?v=8teXm6723-g
(EDIT: I've not checked, but e.g. the clouds in Giana Sisters in some of the levels looks like they might be sprites - using sprites for some of the "background" objects, especially if mostly vertically separated from the main game area was certainly a common method of reducing the amount of background that needed to be copied; notice how the levels without clouds mostly have several lines worth of tiles that doesn't require colour updates near the top and bottom, and often hardly ever requires any copying at all - e.g. mostly unbroken runs of floor tiles; many of the levels requires pretty much no colour updates anywhere)
The only reason I can see for using VSP here is because it means less need to actually figure out how to do the copying efficiently.
Especially not as Giana Sisters was rather simplistic compared to many other scrollers on the C64 as well.
Videos of this game in action beg to differ. The only time the game seems to slow down is when there are two or more animated sprites, usually enemies, on screen at once.
This is compounded by tile-based scrolling being available in NES' hardware but not the C64, so scrolling is a costly operation — AND there are more enemies on screen at any time.
On top of this, the NES could have 64 sprites on screen at once, fully animated at full speed (barring any other slowdown). The C64 can only have 8. That's not a negligible difference. With certain tricks you can display more, but the performance of this needs to be balanced against the rest of the game: SMB already has more complicated physics and more visible items on screen at a time.
Giana Sisters was developed with the limitations of the C64 in mind. There's usually not more than one enemy on screen, the enemy typically moves slower, and animations equivalent to those on in SMB either have fewer frames or none at all.
That says much about this game than about C64 games in general.
Compare to e.g. R-Type (that also has much more complicated scrolling) that has no such problems:
https://www.youtube.com/watch?v=Bft5BhWIzTU
> This is compounded by tile-based scrolling being available in NES' hardware but not the C64, so scrolling is a costly operation
It's not a particularly costly operation because you scroll character buffers, and can chase the raster beam and/or flip character buffers to amortise the scrolling (in the former case to <1000 bytes to copy for ~2 frames when you need to reset the pixel shift, so for every 8 pixel move of the playfield; less with even the slightest optimization such as e.g. keeping colours the same on parts of the screen, or filling parts of the screen with features displayed as sprites). In any case, this game doesn't even have that excuse as it uses VSP to scroll larger screen regions without copying, just by manipulating some registers.
> The C64 can only have 8.
Not true. It can only have 8 visible at any given scan-line. Lots of C64 games use a lot more by updating the sprite registers using the raster interrupt. See e.g. R-Type above, or Delta:
https://www.youtube.com/watch?v=AeLi01dpME0
Or Katakis: https://www.youtube.com/watch?v=zAtW-3sx_1s
But even when that is too little, the "workaround" is simply to use characters and spend a few extra slots on the character set on slightly offset versions of the "tiles" to make it move smoother. E.g. the boss coming up here in Shadow of the Beast is using characters rather than sprites (and many of the stationary enemies in the games above as well):
https://www.youtube.com/watch?v=R_GdJiEjSho&t=78s
So while 8 sprites per scan-line sometimes creates extra effort, it's was not that much of a practical limitation.
> There's usually not more than one enemy on screen
That's just not true, as I confirmed by skimming through the longplay on youtube just now. Even so, see the other examples for why that's a poor excuse.
> the enemy typically moves slower
Speed makes minimal difference to CPU cost of moving the sprites unless you entirely skips updates on some frames - every time you update the location costs as much whether you're moving it one pixel or two, and we're talking a handful of cycles per frame per sprite.
> and animations equivalent to those on in SMB either have fewer frames or none at all.
Number of frames equally makes minimal difference to performance; it's a handful of cycles per frame per sprite, as you change the memory position it reads the sprite data from, you don't overwrite the sprite contents.
Well, it's impressive that it works without being always painfully slow, then. How is this done?