In terms of the textures - you do get a small speedup from using fewer colours in the source texture but its a small effect so I'm not sure that it's worth designing whole levels that way. I did some tests for 64 cols vs 256 cols per source texture and found a very small but consistent gain. I didn't try with 8 colours though
Most of the cost comes from geometry - particularly height differences between sectors.
In order of approx (descending) cost these are important in design:
- number of line-height-differences in view at any time (it is per line!)
- number of visible 'front walls' (lower/upper) from these height diffs
- number of state changes between sectors (light, texture)
- number of lines visible generally
Solid walls stop view-recursion - nothing happens behind them. Transparent midwalls or junctions require recursion through those holes which continues until something solid is encountered (or in BM, until the upper and lowers 'cross' or meet to block the view, like a door closing). This happens at a per-pixel-column level of accuracy. The engine will happily view-recurse through a gap one pixel wide.
I'll do a better writeup on performance design for BM levels on a separate page when I get a bit of time.
[EDIT]
BTW I can produce special builds for level builders, which show a metrics hud overlaid on the game window - it prints all the counts for textures, walls, sprites and details which affect performance. Can be handy for debugging slow areas. I used it to help optimize the engine but it can be used also for designing levels.