An Introduction to Cache-Oblivious Data Structures

Re:An Introduction to Cache-Oblivious Data Structures by fulafel on Wednesday February 07, 2018 @12:19AM (#16322391)

Trivia: Why they are called "cache-oblivious" and not "cache-aware"?

The paper that coined the term is here: http://cacs.usc.edu/education/cs653/Frigo-CacheOblivious-FOC...

Basically, there were first cache-aware algorithms that assumed certain cache sizes and other properties. "Cache-oblivious" algorithms were a refinement that worked well for many cache sizes.

All in all it's silly that the "cache-oblivious" term was the one that survived, because now cache-unaware and cache-oblivious algorithms mean the opposite things - contradicting the dictionary definition of oblivious.

[ Parent | on HN ]

Re:An Introduction to Cache-Oblivious Data Structures by egnehots on Wednesday February 07, 2018 @02:34AM (#16322846)

It all become clearer if you replace it in your head by

"cache sizes oblivious" algorithms.

[ Parent | on HN ]

Re:An Introduction to Cache-Oblivious Data Structures by philipov on Wednesday February 07, 2018 @12:56PM (#16326483)

Nope. Still sounds like "having no awareness of cache sizes and lacking a strategy for dealing with them."

No matter how you prefix it, 'oblivious' means you are missing something you are expected to be responsible for. It is a word expressing negative sentiment.

[ Parent | on HN ]

Re:An Introduction to Cache-Oblivious Data Structures by bloaf on Wednesday February 07, 2018 @01:53AM (#16322708)

I've read about this for a few mins now, and want to check if my understanding is correct.

There are these classes of algorithms:

1. Cache aware algos are tailored to specific environmental-cache behavior. They may perform poorly in other environments.

2. Cache unaware algos do not consider any cache behavior.

3. Cache oblivious algos take maximum advantage of cache behavior, regardless of what that behavior is.

4. ???? algos, when given cache behavior as input, behave as cache aware algos; are unaware otherwise.

[ Parent | on HN ]

Re:An Introduction to Cache-Oblivious Data Structures by TeMPOraL on Wednesday February 07, 2018 @05:52AM (#16323608)

4. Cache adaptive algos?

[ Parent | on HN ]

Re:An Introduction to Cache-Oblivious Data Structures by ramses0 on Wednesday February 07, 2018 @01:06AM (#16322548)

see: Clipless Pedals

[ Parent | on HN ]

Re:An Introduction to Cache-Oblivious Data Structures by Intermernet on Wednesday February 07, 2018 @07:38AM (#16323993)

Serverless computing?

[ Parent | on HN ]

Re:An Introduction to Cache-Oblivious Data Structures by 8note on Wednesday February 07, 2018 @01:08AM (#16322556)

wouldn't a cache aware data structure depend on assuming certain cache sizes and other properties to match a cache aware algorithm?

[ Parent | on HN ]