CODEWITHSUNDEEP
algorithmseekcache-oblivious
san
san

Reputation: 4254

Just as there are cache oblivious and cache optimal algorithms, are there seek optimal algorithms?

Do cache (oblivious|optimal|aware) algorithms typically consider seek time in their model. If not are there examples of models that do consider seek time, and are there analysis of algorithms in this model.

Upvotes: 3

Views: 132

Answers (1)

Sophit
Sophit

Reputation: 511

Yes, I've personally written seek sensitive algorithms. File systems certainly use seek sensitive data structures (which are analogous to algorithms).

For example, NTFS (and many other filesystems) store data in B-tree format to minimize seeks and optimize for sequential reads.

Unfortunately, you're asking this question in 2014 when solid state drives and other technology are on the verge of displacing rotating media entirely. SSDs do suffer some seek penalty, but they can handle tens of thousands of seeks per second compared to rotating HDDs which probably can't handle even 100 seeks per second. This makes seeks much less of a problem than in years past.

A similar and more relevant problem is cache-line coherency on the CPU. RAM speed has not kept up with CPU speed, and multicore CPUs have made NUMA a real performance concern. To optimize performance, many algorithm implementations are pushed to use as little memory as possible, and to use nearby memory more often than far memory.

For example, a heap data structure is far more cache friendly than a tree. Performance sensitive code will choose to use heaps over trees when that's a practical choice.

This cache problem has been an overriding performance concern for the last decade at least. Almost all non-trivial programs run faster when optimized for size rather than speed, and cache misses are the cause.

Upvotes: 4

Related Questions