Talk:Cache

Contents

1 Cache towns 2 Merge and stuff 3 Another edit 4 pronunciation question 5 Operation section

Cache towns

Any reason why Cache, Utah and Cache, Oklahoma should be mentioned at all in the article? A search will return those as well, and you'll figure out pretty quickly which one is the article you want. Also, no offense intended to those who live there, but they seem to be pretty minor towns. (Same argument goes for Nokia -- but the connection between the company and the town should still be mentioned there.) A disambiguation page would do the trick nicely, I think.

Or let me put it this way, there are a lot of places on Earth. If we added articles on all of them and stuck a "there is also a town/lake/mountain called ..." disclamer on every colliding title things would start to be pretty cluttered. (Especially with multiple entries on many articles.) There is a better mechanism to deal with ambiguity -- disambiguation pages.

magetoo 00:25, 19 Jan 2005 (UTC)

I boldly deleted the town references now.

magetoo 02:36, 28 Apr 2005 (UTC)

You do know that the search isn't always (or even most of the time) operational, right? The proper thing to do would probably be to create a disambiguation page somewhere. Tim Rhymeless (Er...let's shimmy) 03:10, 28 Apr 2005 (UTC)

I know that now. When I wrote the first two paragraphs, it worked (and I expected it to). I'll get on with the disambiguating business now. (Ok, maybe not, since it would break links. What do you other guys think?) I still believe articles should be kept as "clean" as possible, and that we shouldn't have to work around a broken search function. magetoo 03:35, 28 Apr 2005 (UTC)

Just link to the disambiguation page at the top; saying for other uses of Cache, see [[Cache (disambiguation}]]. Tim Rhymeless (Er...let's shimmy) 03:49, 28 Apr 2005 (UTC)

---

I don't understand this part:

"... modern general-purpose CPUs inside personal computers may have a dozen [caches], each specialized to a different part of the problem of executing programs".

What does this mean? Level 1 i-cache and d-cache, level 2 cache, etc. How do you get a dozen caches in the CPU? This is way too ambiguous, and not a very good summary of CPU caches. Can someone explain and clean this up? Otherwise I'm inclined to replace this with a cleaner summary.

A dozen is too large. When I wrote that I was thinking I would treat predictors and caches as a single kind of thing. Since then, I've decided to treat them seperately.

In any case, let's count all the caches in a K8 (Athlon 64/Opteron):

• L1 Icache
• L1 ITLB
• L2 ITLB
• L1 Dcache
• L1 DTLB
• L2 DTLB
• Unified L2

Those are all the ones I know about. For completeness, here are the predictors in the K8:

• Branch direction predictor
• Branch Target Address Cache (I'll call this a predictor because I suspect it is allowed to return false information some of the time)
• Return address stack
• Data access stride predictor (issues hardware prefetches)

Some others that I don't think are in the K8 or P4 yet:

• Store-load bypass predictor
• Load hoist valid predictor (there must be a better name for this. Was in EV6.)

The difference between caches and predictors is that predictors are allowed to be wrong. Caches have coherence protocols (sometimes in software) so that the results can be trusted.

---

Moved from bug report 835659. -- Tim Starling 00:44, Nov 5, 2003 (UTC)

The page <http://en.wikipedia.org/wiki/Cache#Common_cache_implementations> links to another page under the term "LRU". But as it turns out, the page does not deal with "least recently used"-cache strategies but airline components; what is probably not what the reader wanted to know. :-)

---

The opening of this article needs work: it gives the impression that cache means CPU memory cache. A cache doesn't need to be tiny, consider the web browser cache example that is given later. A cache can also be used to store values that are expensive to compute. ( 08:25, 21 Nov 2003 (UTC)

I agree, though a note on that page suggests that it should be folded into this one. Perhaps the CPU caching section should be a subsection of cache hierarchy in a modern computer. Iain McClatchie 23:39, 18 May 2004 (UTC)

---

That is a question for the whole WikiPedia: shouldn´t a page as academic as this one on cache feature book and paper references ??? I mean the usual, non Web references. I´d like to know if there´s some written policy on this. Hgfernan 14:18, 14 May 2004 (UTC)

Merge and stuff

I've merged CPU memory cache into here (since this is what the article talks about). I've also reorganised bits (since I renamed the first section "CPU memory cache"). Some information from both articles have been removed, all of which should be here. From CPU memory cache,

Typically the fastest piece of memory on a CPU is internal flip-flops and buffers. These are not generally accessible to the programmer. Next fastest is the architecture registers. These are the registers that are accessible to the programmer (if he/she is programming in assembler). (This is irrelevant)

The level-1 cache might be between 32 kibibits and 512 kibibits, say. In a 32 bit architecture that would be between 1024 and 16384 words (each word being 32 bits). For example, an Intel 80486 has an 8-KB on-chip cache, and most Pentiums have a 16-KB on-chip level one cache that consists of an 8-KB instruction cache and an 8-KB data cache. ("word" is imprecise, and I don't think mentioning typical cache sizes is important anyway)

In general, a given instruction will require the CPU to fetch between one and two words of information, including the instruction itself and any data it may read from or write to main memory. If the required word is not in L1 cache, it is a "cache miss", and the word must be fetched from lower memory before the instruction can continue. Because of the difference in speed between the CPU and main memory, a cache miss can result in a relatively long delay. Much of the effort in cache design, then, is to first reduce the chance of a cache miss, and, second, to reduce the penalty incurred by a miss. (Some of this is already implied the article, and x86 instructions are not multiples of the word size anyway)

A cache will usually arrange data in "lines" (sometimes also called blocks), a line is a contiguous sequence of words starting at an address that is a multiple of the line size. A line might be 8 words say. So we might have 1024 lines in our cache. A "line" in main memory when accessed will end up as a line in the cache. Usually a cache will transfer data to and from memory in chunks of a whole line, this is more efficient than transferring each word individually. This is both a source of efficiency and inefficiency: if we end up accessing all of the data in a line then bring the line into cache all at once will have been more efficient than bring each word into the cache; on the other hand, if we only access one word from the line then we paid the cost of having to bring the whole line in which will be slower. This inefficiency can be reduced if the requested or "critical" word is the first to be retrieved, though this approach requires more difficult design and hardware. (Feel free to add bits in where appropriate, but the line size is generally a multiple of the memory bus width (typically 64 bits), not the "word" size (16 or 32 bits), which is just jargon anyway)

Because of the speeds at which caches operate the cost in power to drive the electronics of each line to check its contents becomes significant. (What?)

Whenever a new line is brought into the cache, a line must be removed to make room for it. Because the most recently removed line is slightly more likely to be required than a line in the next level cache, some architectures implement a victim cache, which holds that line. An L1 victim cache will be slightly slower than the L1 cache, but faster than L2. (I've never heard of a L1 victim cache, and it's easier to just renumber the caches)

And from cache,

... may have a gigabyte of main memory which takes 80 nanoseconds to access. It's processor chip will typically have a second level (or L2) cache of 512 kilobytes which takes 8 nanoseconds to access, and a primary cache (L1) of 8 kilobytes which takes 666 picoseconds to access. (I think a computer with 1 GB of memory would have faster caches. I have 512 MB, a 32+32K L1, and 256K L1 running at processor speed)

In the above diagram, and in the hardware caches of computers, theindexes and tags are numeric, but for other kinds of caches they may be other kinds of values. In a browser cache, for instance, the main memory index and cache tags are URLs, the cache entry indexes are the special hashed filenames you may have seen if you look through the browser cache directory, and the memory and cache data entries are the contents of files themselves: GIFs, HTML files, etc. (I think the only thing which isn't implied is the bit about hashing)

I'm also wondering if we should add buffer to "see also" (a buffer stores data for access now, while a cache stores data for access later).

I've pondered moving this page to Cache (computer science), but decided not to, as a very large number of pages link to here. Feel free to do that too.

--Elektron 12:32, 2004 Jun 5 (UTC)

I actually think it's fine where it is (unless the page gets twice or three times as large. This is not just a computer science concept, so I think we can leave everything here. It may need a bit of a reworking to make things flow better though. Dori | Talk 12:40, Jun 5, 2004 (UTC)

Another edit

I think "In modern days, cache most often refers to computers or computer programs storing information that is accessed frequently in a special place in order to increase performance." is superfluous, since it is mentioned in the following paragraph. Also, alternate meanings usually are separated by a ----. I also tweaked the second paragraph so it reads better (I think). --Elektron 10:52, 2004 Jun 12 (UTC)

pronunciation question

Could anyone help me verify if there is any other way to pronounce the word "cache"? I think I have heard it pronounced not as "cash" but also in a way that sounds similar to "sachet". THanks

Well, I've used (and heard) "kay-sh" in the past. magetoo 02:36, 28 Apr 2005 (UTC)

Operation section

Lain,

It appears you've removed an entire section based solely upon readability without providing a clear explanation in either the discussion nor on your talk page. Truthfully, 'readability' is rather subjective and can depend upon numerous factors such as fog index, audience, etc. I gather your simple comment, 'readability' implies you found the presentation of the content confusing. However, I don't necessarily agree since the content contained separated paragraphs, complete and clear sentences, and provided bullets to list various classifications of things. Furthermore the section, 'Operation' that I created was intended to give a high-level/theoretical discussion in simple terms on the topic of cache as a lead in to the existing content that was rather practical and quite focussed towards particular applications of cache, hence the addition of my section title, 'Applications'. It appears you marginally agreed with my description I provided in this section however, the new narrowing content under a broad topic such as cache may be inappropriate in this article.

Could you provide a more ellaborate description of why you thought the theoretical description of cache was 'unreadable' and necessitated replacement paragraphs that appear to site specifics that don't completely cover the topic of cache? Perhaps simple modification, rather than the common Wikipedia faux pas of deleting useful content would have been more appropriate particularly without justifcation for deletion of nontrivial content. As you are aware, contributors to Wikipedia are often proud of their work and may feel strongly about their content. Wikipedia is enriched through the various perspectives of numerous contributors rather than a single perspective of one frequent contributor. Im simply looking for an explanation for the deletion, since the content I had provided: all of the 'Operation' section, was largely academic in nature and conveniently referenced other existing articles on the subject where appropriate (several of which you have contributed too also). The new content refers to fewer techniques and industry advances than before. I welcome the comments from others that grasp this topic and discussion.

Should theory not be present in the cache article? Compuer cache is a broad topic, to which thousands/millions of programmers have found numerous ways to implement. Simplifying the operation from theory to a specific practice seems to be the reverse of what we may need here. 4.152.240.80 07:39, 5 Mar 2005 (UTC)

I appreciate that you're proud of your contribution. I too have had material that I added to another article (Hubbert Peak) reverted or rewritten in a manner which I thought made it less factual and worse.

I think that the idea of adding an "operation" section is a good one. But the previous entry had some weaknesses, and in the process of fixing those I rewrote most of it. Here are some of the things I had trouble with:

• "Caches, by definition, provide increased read and/or write response times on one or many data stores." No. Caches reduce read response times (latency). Writes don't have a concept of latency... caches bundle writes to reduce writeback bandwidth, and all you need for this is a store data buffer.
• "the update policy and integrity of the cache must operate to support this behavior." The integrity of the cache must operate? This sentence makes no sense to me.
• "Frequently, the volatility of the cache is a factor that is also considered while defining the update policy." I think I know what you're trying to get at, but this isn't the way to write it. First introduce the various write policies, then explain the consequences of those policies. A write-back cache has less write traffic to the backing store than a write-through cache.
• Your operation section didn't actually say how caches work, so I put that in first.
• Poor word choice: "volatility", "selected", "writeable", "key methods", "transcend", "persisted into", "modified resource", "liveliness", "lifetime", "real-time".
• "A cache without an algorithm or consideration to coherency is merely a buffer." This is a provocative distinction, but I'm not sure I agree with it. A store data buffer in a CPU, for instance, is always kept coherent.

Then there was the flowery verbiage:

• "Ostensibly, this aspect of computing will only advance further as the 21st century unfolds to meet the growing data demands of end users and other automated systems." -- zero factual content
• "As such, the cache (usually) must maintain liveliness and integrity to remain an authoritative source to accurately represent the backing data store."
• "Consequently, the lifetime of the cache is usually indefinite or may be terminal at critical events in the system (e.g. changes in the liveliness of the backing data store(s))."
• "Caches commonly exist in numerous forms, yet, 2 basic types are the LRU Cache and the LFU Cache." -- Here you are talking about replacement policy.

Theory is fine, when it explains something. Iain McClatchie 09:03, 7 Mar 2005 (UTC)

I had doubts that you would respond, kudos for referring to specific text of the original.

As a reference to other readers

Original text (http://en.wikipedia.org/w/index.php?title=Cache&oldid=10784348)

"Rewrite" (http://en.wikipedia.org/w/index.php?title=Cache&oldid=10894429)

You've managed to conjure up some reasons - of course most of which are no basis for the extermination you administered to the previous text. The previous text was structured. You've taken a notably good idea and refined it to apply to a very specific implementation of cache - quite the opposite of the purpose this section of the article should serve. The simple question is: can you describe cache without describing it in terms of a specific application or use? You've been unable to do that so far. As far as pride, admittedly I do have some pride in what I write (as Im sure you do too), but note that I haven't made the customary wikipedian response of reverting my text back as it was prior to your attempt to address this (new for you) concept. I still very much agree with what I wrote, it does need some minor cleanup - which I indicated in the history page - as does your take on this section. The original text belongs rather than your replacement. My responses (in order):

• "I too have had material that I added to another article (Hubbert Peak) reverted or rewritten in a manner which I thought made it less factual and worse." Are you citing this to present it as a reason to continue this self-absorbed and ineffective behavior? Did you know that is a logical fallacy?
• My mistake, you are correct; response times are improved by using caching. This is what I intended to convey, caches have been long known for doing this. However, you assumed that the text said that inevitable delays caused by write activities are observed by the client. I never was specific enough for you to infer that. You've made an erroneous conclusion in the absence of any evidence to support that. A simple sentence add or modify would have cleared that up - if it was necessary; reread the paragraph you'll find that it was not the purpose of the paragraph to make this specific distinction and give that level of detail so early on in the explanation.
• "...the update policy must operate to maintain integrity potentially compromised by this architecture." Simple word-smithing, minor word edit. You obviously feel what does/does not make sense to you is a basis for all understanding. Did you forget your audience?
• No you missed the point completely. It's not about bandwidth and traffic density between the cache and the backing data store(s). Volatility is something quite different. Yes, the selected cache algorithm and update policy has consequences. Volatility can coerce the selection of the update policy but does not drive it. You'll need to learn more about cache volatility.

"This isn't the way to write it." How would you know how to write it if you don't know what cache volatility is?

As you say, first introduce the various write policies. It did that, the 3 bullets draw the readers attention to three of the most basic write policies quickly yet not without providing a lead in to these write policies.

• Operation section - how caches work. Bear in mind that 'Operation' does not imply low-level functionality. If you believe that you're the wrong person for this article. Rather, operation should give a high-level concept of behavior, responsibilities, criteria, environmental conditions, etc. Realize the word you're trying to describe here: cache. The bare naked concept, nothing so specific as cpu cache, in a word, theory. BTW, nice touch ups on the CPU Cache article.
• Word choice. Vocabulary. Abstract thought and terminology. There's nothing wrong here. Simply put, this is the lexicon of theory.
• Im suprised you haven't thought of this 'provocative concept.' Try considering it more. I hope to find you have added a paragraph on it a month or so from now. If your epiphany is realized in the next few weeks, give it some time, these things need nurturing to become effective diction. Adopt this same approach as you learn about cache volatility.
• Flowery verbiage. Interesting description. Oh but don't be alarmed, the broadening of ones vocabulary only serves to educate and enrich the mind.
• Factual content. You're correct in your assessment. This particular sentence was a forecast, a prediction and thus contained very little fact other than the observation of current trends in the industry. To disregard these trends and misdirect the reader toward the specifics of cpu cache is presumptuous, short-sighted, and as a result renders no useful understanding or preparedness to the reader. The reader is coming to the cache article looking for a broad, high-level concept, various implementations of cache, examples, pitfalls, responsibilities, etc. This succinct sentence empowers the reader to begin to grasp and monitor these trends. Learning from trends lead to technological advances. Nothing wrong here.
• No comment? Reads good to me too.
• No comment? Reads good to me too.
• Very good! Replacement policy is the $1000 concept here and is one name, albeit common, yet referred to in this article as an update policy. You've mentioned write policy also. There are several in the industry. It depends on who you talk to, but they all refer to the same - a cache algorithm - one that solves the prototypical cache consistency problem, a.k.a the cache coherency problem.

Cache. Before you attempt another edit on this article, you should reread your replacement text for the Operation section. If you had a background in engineering and theory, you would quickly realize that your text is directed and focused on a particular implementation of cache. You've managed to leave out some crucial issues to which my original text addressed. Granted it didn't provide a detailed discussion on every aspect of cache. But that's not the job here. A simple overview of the inner workings, the technical aspect of many approaches to caching. As such, this article would barely accomplish anything if it presented a single perspective leading readers as prey to their defeat should they depend on the limited content of cpu caching applications. True, write-back policy as you call it (a.k.a a delayed-write policy) is applicable to nearly all caches as well as the write-through approach for cache algorithms.

Try not to be so naive by assuming that the presentation of a simple focused explanation covers the broad concept and implications of caching. Secondly, after noticing your user talk page, I see that you have a plan for several articles on wikipedia, and it appears you've established it single-handedly (are you presuming ownership?). A plan is always good, but a single-minded plan is self-defeating in light of the purpose of wikipedia - that of being a source of knowledge submitted by the masses. A single-minded approach does not lend itself to cooperation, collective research, combined knowledge - it excludes it! I've observed your activity in the wiki histories of some of these other related topics and it appears Im not the only one you've stomped on through your careless cut and replace behavior. It also appears that some of these other wikipedians/contributors have been offended by this - some have responded in restraint (in adherance to the Wikimedia Code of Conduct). I do seem to be someone (if not the only one) who recently gave any care to the quality of the content of this system as a consequence of your destructive actions.

Realize that you're probably faced with a limited background advanced only by the details of cpu caching. Perhaps you may wish to consider the collective contributions from others before "fixing and rewriting" as you describe it. I doubt caching is the only area this approach applies to. 4.152.216.127 04:59, 11 Mar 2005 (UTC)