Once I got very confused when exactly this kind of 10k x speed up I demonstrated for a problem introduced to me as a business bottleneck then got ignored (I wasn’t on this team, though, but it’s still hard to understand the mentality and incentives there).

My rule of thumb is that as long as it doesn’t really complicate or convolute the code, write with performance in mind.

My expertise is in C# and sometimes this is as simple as using a hash set or dictionary instead of a plain list.

Other times it’s having a decent understanding of how EF (an ORM) actually works (the static typing benefits of them in C# makes ORMs very valuable when used appropriately) and the cost of round trips to any network host (including a DB).

To you, 2x faster means 2x the work done in the same time, but 25% faster means 1.33x the work done in the same time.

I see this a lot - in software people interpret 50% faster as a 50% reduction in time taken.

If a car is 50% faster, I hope people would universally interpret that as e.g. 20 to 30 mph. But if I asked people how long would a 1 hour journey take if it were 50% faster, I bet a lot would say 30 mins, because it kind of seems like that's what I mean.

Calling everyone who downvotes you "incels" is very much against site rules. You've certainly been here long enough to know that. Knock it off.

There was also a heavy emphasis on games being "cinematic" which necessitates photorealistic rendering.

AAA games have been pretty artless for a while now baring a couple exceptions.

Crysis 3 is over a decade old, still looks great and ran on hardware that wouldn't suffice for web browsing today. I haven't seen anything in games since then that justified a significant increase in system requirements.

So your argument is that game engines will just decay.

Btrees are O(log n) random access, O(log n) cons and use O(log n) excess space.

Unrolled linked lists are still O(n) random access because we ignore the constant factor of block size. They also use O(n) excess space for pointers, but have O(1) cons.

RAOTS are O(1) random access, O(1) amortized cons [O(√n) worse case], and use O(√n) excess space.

RAOTS is basically a tree of depth 1. The root is an "index block" of pointers to data blocks which grow in size proportional to the square root of the data length (similar to Hashed Array Trees, but doesn't require restructuring on each power of 2). The index block has length ~√n.

The square root is an approximation - the structure grows in "superblocks" where each superblock has `~√n` blocks of size `~√n` The pattern is: [1x1, 1x2, 2x2, 2x4, 4x4, 4x8, 8x8, 8x16, 16x16, 16x32, ...] Even indexed superblocks double the data block size, odd indexed superblocks double the number of blocks per superblock. It doesn't use an actual `sqrt()` call uses but some bit tricks via `clz`.

A simpler trick, which has no single name but have been known as "segmented lists", is where the index block points to blocks increasing in size geometrically, essentially like a dynamic array but where we don't need to `realloc`. The index block is length 1+log₂n and each index i points to a block of length 2⁽ⁱ⁻¹⁾. These have O(1) random access, O(1) amortized cons [O(n) worst case] and waste O(n) space [with constant factor of 1/2]. The random access is very efficient as it's only two dereferences and a few bit tricks:

    index_block[bit_width(idx)][idx - bit_floor(idx)]

There's also Bagwell's VList[2] which is like a mashup of the "segmented list" and an unrolled list - the blocks grow geometrically in size, but still contain the pointer the the next block rather than them being in a separate index block.

[1]:https://cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf

[2]:https://dl.acm.org/doi/10.5555/1756972.1756975