Have you ever had a problem with your computer,
and someone told you to fix it by clearing your browser cache or your DNS cache? Chances are you've heard of these, but what
is a cache? Simply put, caching means to store frequently
demanded things closer to those asking for it. And by doing that, you increase the access
speed. The book "Algorithms to Live By" gives a simple
explanation. Imagine you're doing research for writing
a paper or making a video, and that you need to consult a book from the library. You could go to the library every time you
need a piece of information, but instead, you will most likely take the book home with
you and put it on your desk for faster access. In this example, your desk became a cache. Instead of making round trips to the library,
which would slow down your progress, you can now grab the book straight from your desk. You intuitively understand why caching is
much faster, but also that it's more limited. You don't have as much space on your desk
as the library has in its stacks. You can only keep a limited amount of books
in your cache. More on that later! Let's first look at how caches are used in
computers. For example, your web browser caches resources
from frequently visited websites. The first time you visit YouTube.com, your
browser knows nothing about it, so it downloads all of the resources that make up YouTube. The logo, icons, fonts, scripts, and all the
thumbnails. On subsequent visits, however, all of this
can be retrieved from cache. Making the webpage load much faster because
your browser only needs to download newer content that it hasn't seen before. On YouTube, that might be only the thumbnails
of videos uploaded after your last visit. In this case, your browser cache is storing
internet resources on your local computer. It's much faster to retrieve them from your
SSD or hard drive than to download them from the internet. This is also the reason why clearing your
cache can fix certain problems. Sometimes, websites update their designs or
scripts, but your browser will keep using the older versions in its cache. But it's not just browsers that have a cache. Modern devices have tons of caches. On the hardware side: processors, GPUs, hard
drives, SSD's all have caches. This creates a memory hierarchy. At the top, you'll find the memory embedded
in processors, which is super fast but very small. At the bottom, you'll find things like SSD's
and hard drives, which have huge capacities but are very slow compared to what's at the
top of this hierarchy. You find a similar structure in the library. Frequently checked out books might be kept
in a small cabinet near the front desk, where it's super fast to retrieve them. Less popular books will be moved to the stacks. There's much more space there compared to
the front desk, but it requires a bit of searching to find the book you're after. And finally, you'll have old books that are
rarely checked out and moved to off-site storage. While this archive is probably the largest
of all, it's also the slowest to access. It requires you to ask a staff member to retrieve
them for you, potentially taking a few days. On the software side, caches are also everywhere:
operating systems, browsers, DNS, databases, and web servers all use caches. And every time for the same purpose: store
data in fast memory so it can be retrieved quicker. But let's go back to the book cache on your
desk. At some point, your desk will be filled up
with books. So, what do you do when your cache is full? How do you determine which books or which
items to keep in your cache and which to remove? This is called a cache eviction strategy. Instinctively, you might return the books
that you haven't used in a while. This is called Least Recently Used or LRU
for short, and it's an effective and easy to implement strategy. It does require you to keep track of when
items in your cache were last accessed, which does slow it down a tiny bit. Another eviction strategy is random replacement. This one is a bit weird as it doesn't try
to be smart. Instead, when the cache full, it just removes
a random item. While this does sound like a bad strategy,
in practice, it's actually not far off LRU, and it's much simpler to implement. That's why it's used in small ARM processors
to keep their designs simple. But what fascinated me the most about caching
was that it was invented in 1965 by Maurice Wilkes, a British computer scientist. In his paper, he wrote that cache memory should
automatically fill itself with data from a slower main memory to speed up subsequent
requests. Amazing to see that technologies invented
over 55 years ago are still being used and perfected to this day. Thanks for watching this video. I hope you liked it, and if you did, please
consider subscribing. And I'll see you in the next video!
