level 1 cache

Write Great Code, Volume 1
by Randall Hyde
Published 6 Aug 2012

Instead, when the CPU requests data from memory, the L1 cache subsystem takes over. If the requested data is in the cache, then the L1 cache subsystem returns the data to the CPU, and that concludes the memory access. If the requested data is not present in the L1 cache, then the L1 cache subsystem passes the request on down to the L2 cache subsystem. If the L2 cache subsystem has the data, it returns this data to the L1 cache, which then returns the data to the CPU. Note that requests for the same data in the near future will be fulfilled by the L1 cache rather than the L2 cache because the L1 cache now has a copy of the data.

…

On a 1-GHz processor the L1 cache must respond within one nanosecond if the cache operates with zero wait states (some processors actually introduce wait states in L1 cache accesses, but CPU designers try to avoid this). Accessing data in the L2 cache is always slower than in the L1 cache, and there is always the equivalent of at least one wait state, and up to eight, when accessing data in the L2 cache. There are several reasons why L2 cache accesses are slower than L1 accesses. First, it takes the CPU time to determine that the data it is seeking is not in the L1 cache. By the time it determines that the data is not present in the L1 cache, the memory-access cycle is nearly complete, and there is no time to access the data in the L2 cache.

…

Secondly, the circuitry of the L2 cache may be slower than the circuitry of the L1 cache in order to make the L2 cache less expensive. Third, L2 caches are usually 16 to 64 times larger than L1 caches, and larger memory subsystems tend to be slower than smaller ones. All this adds up to additional wait states when accessing data in the L2 cache. As noted earlier, the L2 cache can be as much as one order of magnitude slower than the L1 cache. The L1 and L2 caches also differ in the amount of data the system fetches when there is a cache miss (see Chapter 6). When the CPU fetches data from or writes data to the L1 cache, it generally fetches or writes only the data requested.

The Practice of Cloud System Administration: DevOps and SRE Practices for Web Services, Volume 2
by Thomas A. Limoncelli , Strata R. Chalup and Christina J. Hogan
Published 27 Aug 2014

The cache medium simply must be faster than the main medium. A disk can cache for data that has to be gathered from a remote server because disks are generally faster than remote retrieval. For example, YouTube videos are cached in many servers around the world to conserve internet bandwidth. Very fast RAM can cache for normal RAM. For example, the L1 cache of a CPU caches the computer’s main memory. Caches are not just used to improve data lookups. For example, calculations can be cached. A function that does a difficult mathematical calculation might cache recent calculation results if they are likely to be requested again. 5.4.3 Cache Persistence When a system starts, the cache is usually empty, or cold.

…

If reading from main memory took 1 second, how long would the other operations take? For extra credit, draw your answer to resemble a calendar or the solar system. 6. Take the data table in Figure 1.10 and add a column that identifies the cost of each item. Scale the costs to the same unit—for example, the cost of 1 terabyte of RAM, 1 terabyte of disk, and 1 terabyte of L1 cache. Add another column that shows the ratio of performance to cost. 7. What is the theoretical model that describes the different kinds of scaling techniques? 8. How do you know when scaling is needed? 9. What are the most common scaling techniques and how do they work? When are they most appropriate to use?

…

More surprisingly, a loop that reads every element of an array takes approximately the same amount of time to execute as a loop that reads every 16th element of the same array. Even though the former does 1/16th of the number of operations, the number of RAM cache misses is the same for both loops. Reading blocks of memory from RAM to the CPU’s L1 (Level 1) cache is slow and dominates the run-time of either algorithm. The fact that the former runs faster is due to the fact that there are special instructions for sequentially reading memory. Above and beyond RAM, virtual memory, and disk issues, we also have to consider the effect of threads, multiple CPUs trying to access the same data, locks, and mutexes.

The Linux kernel primer: a top-down approach for x86 and PowerPC architectures
by Claudia Salzberg Rodriguez , Gordon Fischer and Steven Smolski
Published 15 Nov 2005

Let's look at their creation: ----------------------------------------------------------------------------- mm/slab.c 486 static kmem_cache_t cache_cache = { 487 .lists = LIST3_INIT(cache_cache.lists), 488 .batchcount = 1, 489 .limit = BOOT_CPUCACHE_ENTRIES, 490 .objsize = sizeof(kmem_cache_t), 491 .flags = SLAB_NO_REAP, 492 .spinlock = SPIN_LOCK_UNLOCKED, 493 .color_off = L1_CACHE_BYTES, 494 .name = "kmem_cache", 495 }; 496 497 /* Guard access to the cache-chain. */ 498 static struct semaphore cache_chain_sem; 499 500 struct list_head cache_chain; ----------------------------------------------------------------------------- The cache_cache cache descriptor has the SLAB_NO_REAP flag.

…

= next)) { 2301 next->timestamp = now; 2302 rq->nr_switches++; 2303 rq->curr = next; 2304 ++*switch_count; 2305 2306 prepare_arch_switch(rq, next); 2307 prev = context_switch(rq, prev, next); 2308 barrier(); 2309 2310 finish_task_switch(prev); 2311 } else 2312 spin_unlock_irq(&rq->lock); 2313 2314 reacquire_kernel_lock(current); 2315 preempt_enable_no_resched(); 2316 if (test_thread_flag(TIF_NEED_RESCHED)) 2317 goto need_resched; 2318 } ----------------------------------------------------------------------- Line 2288 We attempt to get the memory of the new process' task structure into the CPU's L1 cache. (See include/linux/prefetch.h for more information.) Line 2290 Because we're going through a context switch, we need to inform the current CPU that we're doing so. This allows a multi-CPU device to ensure data that is shared across CPUs is accessed exclusively. This process is called read-copy updating.

Hands-On Functional Programming in RUST
by Andrew Johnson
Published 29 May 2018

More distance (d) in one direction also means an increase in available space of quadratic (d2) or cubic (d3) scale. In other words building the fridge farther away provides more space for a larger fridge. Bringing this story back to a technical context, here are some latency numbers that every programmer should know (~2012: https://gist.github.com/jboner/2841832): Request Time L1 cache reference 0.5 ns Branch mispredict 5 ns L2 cache reference 7 ns Mutex lock/unlock 25 ns Main memory reference 100 ns Compress 1 Kb with Zippy 3000 ns Send 1 Kb over 1 Gbps network 10000 ns Read 4 Kb randomly from SSD 150000 ns Read 1 Mb sequentially from memory 250000 ns Round trip within same datacenter 500000 ns Send packet CA | Netherlands | CA 150000000 ns Here, we can see in specific numbers that if you want a donut and some coffee then you could eat 300,000,000 donuts from the fridge next to your computer before taking your first bite from a Danish.

97 Things Every Programmer Should Know
by Kevlin Henney
Published 5 Feb 2010

Modern computer systems are organized as hierarchies of physical and virtual machines, including language runtimes, operating systems, CPUs, cache memory, random-access memory, disk drives, and networks. This table shows the limits on random access time and storage capacity for a typical networked server. Access time Capacity Register < 1 ns 64 b Cache line 64 B L1 cache 1 ns 64 KB L2 cache 4 ns 8 MB RAM 20 ns 32 GB Disk 10 ms 10 TB LAN 20 ms > 1 PB Internet 100 ms > 1 ZB Note that capacity and speed vary by several orders of magnitude. Caching and lookahead are used heavily at every level of our systems to hide this variation, but they only work when access is predictable.

Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems
by Martin Kleppmann
Published 17 Apr 2017

Besides reducing the volume of data that needs to be loaded from disk, columnoriented storage layouts are also good for making efficient use of CPU cycles. For example, the query engine can take a chunk of compressed column data that fits comfortably in the CPU’s L1 cache and iterate through it in a tight loop (that is, with no function calls). A CPU can execute such a loop much faster than code that requires a lot of function calls and conditions for each record that is processed. Col‐ umn compression allows more rows from a column to fit in the same amount of L1 cache. Operators, such as the bitwise AND and OR described previously, can be designed to operate on such chunks of compressed column data directly. This techni‐ que is known as vectorized processing [58, 49].

Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems
by Martin Kleppmann
Published 16 Mar 2017

Besides reducing the volume of data that needs to be loaded from disk, column-oriented storage layouts are also good for making efficient use of CPU cycles. For example, the query engine can take a chunk of compressed column data that fits comfortably in the CPU’s L1 cache and iterate through it in a tight loop (that is, with no function calls). A CPU can execute such a loop much faster than code that requires a lot of function calls and conditions for each record that is processed. Column compression allows more rows from a column to fit in the same amount of L1 cache. Operators, such as the bitwise AND and OR described previously, can be designed to operate on such chunks of compressed column data directly. This technique is known as vectorized processing [58, 49].

The Art of UNIX Programming
by Eric S. Raymond
Published 22 Sep 2003

Here's a new one: you want the central data structures and the time-critical loops in your code never to fall out of cache. Consider your target machine as a hierarchy of memory types arranged by distance from the processor. There are the processor's own registers; its instruction pipeline; the level-one (L1) cache; the level-two (L2) cache; possibly a level-three (L3) cache; main memory (what Unix old hands still quaintly call ‘core’); and the disk drives where swap space lives. Technologies like SMP, shared-memory clusters, and non-uniform memory access (NUMA) add more layers to the picture but only widen the overall spread.

Architecting Modern Data Platforms: A Guide to Enterprise Hadoop at Scale
by Jan Kunigk , Ian Buss , Paul Wilkinson and Lars George
Published 8 Jan 2019

In this scenario, multiple threads could be running on both physical CPUs, each trying to access a location of memory that is distant for some of these threads and local to others. To improve the speed of repeated access, some of this remote memory will naturally reside in the local processor’s L3, L2, or L1 caches, but this comes at the cost of additional overhead in the coherency protocol, which now also spans the inter-processor connect. Linux provides tools and interfaces through which users and programs can influence NUMA behavior directly. Crucially, this allows for requesting an optimal mapping for applications on a given processor, which in NUMA terminology is called a NUMA node (not to be confused with a core or a thread within a processor).

Real World Haskell
by Bryan O'Sullivan , John Goerzen , Donald Stewart and Donald Bruce Stewart
Published 2 Dec 2008

This represents a string of data as a list of chunks, arrays of up to 64 KB in size. Each ByteString type performs better under particular circumstances. For streaming a large quantity (hundreds of megabytes to terabytes) of data, the lazy ByteString type is usually best. Its chunk size is tuned to be friendly to a modern CPU’s L1 cache, and a garbage collector can quickly discard chunks of streamed data that are no longer being used. The strict ByteString type performs best for applications that are less concerned with memory footprint or that need to access data randomly. Binary I/O and Qualified Imports Let’s develop a small function to illustrate some of the ByteString API.

Arriving Today: From Factory to Front Door -- Why Everything Has Changed About How and What We Buy
by Christopher Mims
Published 13 Sep 2021

The principles of computer architecture that are inherent in the design of the Kiva robotics systems (which is now the Amazon Robotics system) are fractal: these principles repeat themselves at every scale of the system, from the actions of individual robots, to the behavior of all of the robots in a fulfillment center, to the behavior of Amazon’s entire network of warehouses, which are constantly rebalancing inventory between each other as well as within themselves. Something similar happens in computer chip design. Chips have small local caches of data—known as level 1 caches—immediately accessible to processors and also caches slightly more removed both physically and temporally, including levels 2, 3, and 4, depending on their design. These caches contain copies of data that also exists in main memory (RAM) or on the computer’s (spinning or solid-state) hard drive.

Trading at the Speed of Light: How Ultrafast Algorithms Are Transforming Financial Markets
by Donald MacKenzie
Published 24 May 2021

In respect to money, Andresen said, “There’s that whole hacker ethos of ‘I’m above money,’ ” but unlike many cases in which “they affect it because it’s considered cool,” he found it to be genuine in Levine’s case: “I’d be like, ‘Josh, here’s your bonus check,’ [and] he was like, ‘Ah, give it to those guys.’ ” (“Those guys” were the programmers who had taken over much of the programming burden from Levine; email to author from Levine, September 1, 2012.) 19. See https://colin-scott.github.io/personal_website/research/interactive_latency.html, which gives an estimate of 23 nanoseconds for a level 1 “cache reference,” using the technology of 1996 (accessed January 21, 2020). I am hugely grateful to interviewee AF for pointing me to this site, which is a wonderful resource for someone interested in computing’s materiality. 20. A “two-phase commit” is the procedure by which a system writes information onto a disk or other form of memory and receives back a message acknowledging that the information has indeed been written. 21.

Algorithms to Live By: The Computer Science of Human Decisions
by Brian Christian and Tom Griffiths
Published 4 Apr 2016

If you make a library bigger, it takes longer to find a book in the library. If you have a stack of papers on your desk that’s bigger, it takes longer to find the paper you’re looking for, right? Caches are actually a solution to that problem.… For example, right now, if you go to buy a processor, what you’ll get is a Level 1 cache and a Level 2 cache on the chip. The reason that there are—even just on the chip there are two caches!—is that in order to keep up with the cycle rate of the processor, the first-level cache is limited in size. Unavoidably, the larger a memory is, the more time it takes to search for and extract a piece of information from it.