[HN Gopher] How much slower is random access, really?
___________________________________________________________________
How much slower is random access, really?
Author : sestep
Score : 106 points
Date : 2025-06-23 14:49 UTC (4 days ago)
(HTM) web link (samestep.com)
(TXT) w3m dump (samestep.com)
| Adhyyan1252 wrote:
| Love this analysis! Was expecting random to be much slower. 4x is
| not bad at all
| Nevermark wrote:
| There has to be some power hit for all those extra cache fills.
| No idea if it would be measurable.
| andersa wrote:
| Note this is not true random access in the manner it occurs in
| most programs. By having a contiguous array of indices to look
| at, that array can be prefetched as it goes, and speculative
| execution will take care of loading many upcoming indices of the
| target array in parallel.
|
| A more interesting example might be if each slot in the target
| array has the next index to go to in addition to the value, then
| you will introduce a dependency chain preventing this from
| happening.
| jiggawatts wrote:
| This is why array random access and linked-list random access
| have wildly different performance characteristics.
|
| Another thing I noticed is that the spike on the left hand side
| of his graphs is the overhead of file access.
|
| Without this overhead, small array random access should have a
| lot better per-element cost.
| sestep wrote:
| To be clear, the overhead on the left part is only due to
| file access for the last two graphs (the "direct" summation
| ones with just one blue line). For all the charts with both
| blue and yellow lines, there is no file access happening on
| the left hand side of the graphs, since the file gets read
| into memory first and then the measurements are run.
| wtallis wrote:
| > A more interesting example might be if each slot in the
| target array has the next index to go to in addition to the
| value, then you will introduce a dependency chain preventing
| this from happening.
|
| However, on some processors there's a data-dependent prefetcher
| that will notice the pointer-like value and start prefetching
| _that_ address before the CPU requests it.
| deepsun wrote:
| Could probably overcome that by using integers, but
| converting them to a pointer after accessing (like '0'+1 is
| '1').
| wtallis wrote:
| Do you mean storing the next index/offset and having the
| pointer value calculated as late as possible by adding the
| starting address (and maybe multiplying the index by
| sizeof)? That would _probably_ defeat /mislead Intel's
| prefetcher, as described at https://www.intel.com/content/w
| ww/us/en/developer/articles/t...
| less_less wrote:
| The data-dependent prefetcher is a cool feature, though you
| do have to be careful with side-channel issues, so some of
| them can disable it with the Data-Independent Timing bit or
| similar.
|
| At this point I'm kinda expecting CPU vendors to stop putting
| as many Spectre mitigations in the main core, and just have a
| small crypto core with full-fat arithmetic, less hardware for
| memory access, less speculation, and careful side-channel
| hardening. You still have to block Meltdown and other large
| vulnerabilities on the main cores, but if someone wants to
| protect elliptic curves from weird attacks? Try to set the
| DIT bit, trap into the OS, and get sent to the hardened core.
| gpderetta wrote:
| Even if the prefetcher was capable of traversing pointers, it
| wouldn't help. The hypothetical benchmark wouldn't do
| anything other chasing pointers, and the prefetcher can't
| really do that any quicker. A traversing prefetcher is useful
| if the code actually does work for each traversed node, then
| the prefetcher (or the OoO machinery) could realistically run
| ahead.
| hansvm wrote:
| Fun fact, that's part of why parsing protobuf is so slow.
| elcritch wrote:
| Indirection kills performance nowadays. I did a bunch of
| benchmarking a couple years back and found that you can parse
| MessagePack and CBOR faster than Protobuf if you know the
| types and serialize directly into them. Even if field order
| isn't known and you use non-allocated field strings.
|
| Well in a language that allows you to generate compile time
| specialized serde code like Nim or Zig. Maybe C++ has enough
| compile time reflection to do it now as well?
|
| I don't know enough about Rust's serde, but it seems like
| there'd be a lot of performance overhead with it's design and
| the limits of Rust's macro and compiler system.
| Retr0id wrote:
| By the way, DAG-CBOR and dCBOR enforce sorted map keys*, in
| which case you always know the field order.
|
| *maddeningly, with mutually incompatible sorting rules.
| delusional wrote:
| > By having a contiguous array of indices to look at, that
| array can be prefetched as it goes
|
| Does x86 64 actually do this data dependent single deref
| prefetech? Because in that case I have a some design
| assumptions I have to reevaluate.
| phi-go wrote:
| Hardware definitely supports this but it might need compiler
| support, as in adding instructions to do prefetching. Which
| might be done automatically or requires a pragma or calling a
| builtin. So it can be implemented in any case.
| shakna wrote:
| The compiler probably does [0].
|
| [0] https://gcc.gnu.org/projects/prefetch.html
| delusional wrote:
| That list doesn't include any current mainline processors.
| It's all Itanium, 3DNow!, and MIPS.
| wtallis wrote:
| Intel added PREFETCHW to their Broadwell processors
| launched in 2014, years after AMD dropped all 3DNow!
| instructions except the prefetch instructions. That
| timeline strongly suggests that the instructions aren't
| no-ops and likely are used by some popular software.
| alain94040 wrote:
| On modern cpus? Most likely. Those kinds of optimizations are
| done by the core with no compiler magic needed.
|
| CPU implementation has become too complex to grasp. The only
| sure way to know how a CPU will behave for a given workload
| is to run the workload. It's good to have some basic
| expectations of performance, instructions/cycle, memory
| bandwidth, to detect if something is off. I guess I'm trying
| to say it's hard to keep in your head all the details of what
| ~1B transistors are doing together to run your code. It's
| just too big.
| jltsiren wrote:
| If the next index is stored in the target array and the indexes
| are random, you will likely get a cycle of length O(sqrt(n)),
| which can be cached.
|
| You can avoid this with two arrays. One contains random query
| positions, and the target array is also filled with random
| values. The next index is then a function of the next query
| position and the previous value read from the target array.
| eru wrote:
| You could sample from a different random distribution.
|
| Eg start with every element referencing the next element
| (i.e. i+1 with wrap-around), and then use a random shuffle.
| That way, you preserve the full cycle.
| jltsiren wrote:
| You can do that, but it's inefficient with larger arrays.
| Iterating over 10 billion elements in a random order can
| take up to an hour. Which is probably more than what you
| are willing to wait for a single case in a benchmark. On
| the other hand, you will probably find a cycle in a
| uniformly random array of 10 billion elements within 0.1
| seconds, which is not enough to mitigate the noise in the
| measurements. So you need a way of generating unpredictable
| query positions for at least a few seconds without wasting
| too much time setting it up.
| eru wrote:
| You could also use group theory to help you.
|
| Basically, pick a large prime number p as the size of
| your array and a number 0 < x < p. Then visit your array
| in the order of (i*x) modulo p.
|
| You can also do something with (x^i) modulo p, if your
| processor is smart enough to figure out your additive
| pattern.
|
| Basically, the idea is to look into the same theory they
| use to produce PRNG with long cycles.
| kortilla wrote:
| The article very clearly compares using randomized indexes and
| sequential. It's kinda the point of the article.
| cb321 wrote:
| You seem to misunderstand @andersa's point which I think is
| well expressed - it doesn't matter if the indices are
| randomized if the CPU can pre-fetch what they will be. The
| power of CPU speculative execution to hide latency can be
| quite surprising the first time you see it.
|
| This is a very small Nim program to demonstrate for "show me
| the code" and "it must just not be 'random enough'!"
| skeptics: https://github.com/c-blake/bu/blob/main/memlat.nim
| It uses the exact dependency idea @andersa mentions of a
| random cycle of `x[i] = i` that others else-sub-thread say
| some CPUs these days are smart enough to "see through". On
| Intel CPUs I have, the dependency makes things 12x slower at
| the gigabyte scale (DIMMs).
|
| EDIT: This same effect makes many a naive hash table
| microbenchmark { e.g., `for key in keys: lookup(key)` }
| unrepresentative of performance in real programs where each
| `key` is often not speculatively pre-computable.
| gpderetta wrote:
| In the end it depends exactly what you want to measure. Of
| course a load-load dependency will make everything as slow
| as the latency of the cache level you are accessing as that
| becomes the bottleneck.
|
| Traversing a contiguous list of pointers in L1 is also
| slower than accessing those pointers by generating their
| address sequentially, so adding a load-load dependency is
| not a good way to benchmarking random access vs sequential
| access (it is a good way to benchmark vector traversal vs
| list traversal of course).
|
| At the end of the day you have to accept that like caching
| and prefetching speedup sequential access, OoO execution[1]
| will speedup (to a lesser extent) random access. Instead of
| memory latency, in this case the bottleneck would be the
| OoO queue depth, or more likely the maximum number of
| outstanding L1/L2/L3 (and potentially TLB) misses. As long
| as the maximum number of outstanding misses is lower than
| the memory latency for that cache level, then, in first
| approximation, the cpu can effectively hide the sequential
| vs random access cost for independent accesses.
|
| Benchmarking is hard. Making sure that that a
| microbenchmark represents your load effectively, doubly so.
|
| [1] Even many in-order CPUs have some run-ahead
| capabilities for memory.
| cb321 wrote:
| All true. No real disagreement and I'm often saying "it
| all depends.." myself. :-) In this case, there is also
| some vagueness around "random" (predictable to _what_
| subsystem _when_ ).
|
| I still suspect @kortilla is one of today's lucky 10,000
| (https://xkcd.com/1053/) or just read/replied too
| quickly. :-)
|
| There is a _lot_ written that indicates that the
| complexity of modern CPUs is ill-disseminated. But there
| is also wonderful stuff like https://gamozolabs.github.io
| /metrology/2019/08/19/sushi_roll... { To add a couple
| links to underwrite my reply in full agreeance. :-) }
| sestep wrote:
| Great point thanks, and I agree! I thought about also including
| another experiment for this "linked list"-style access pattern
| to see what the difference in performance is, but didn't get
| around to it. Maybe I'll write a followup post doing that.
| forrestthewoods wrote:
| Here's an older blog post of mine on roughly the same topic:
|
| https://www.forrestthewoods.com/blog/memory-bandwidth-napkin...
|
| I'm not sure I agree with the data presentation format. "time per
| element" doesn't seem like the right metric.
| klank wrote:
| What are your qualms with time per element? I liked it as a
| metric because it kept the total deviation of results to less
| than 32 across the entire result set.
|
| Using something like the overall run length would have such
| large variations making only the shape of the graph
| particularly useful (to me) less so much the values themselves.
|
| If I was showing a chart like this to "leadership" I'd show
| with the overall run length. As I'd care more about them
| realizing the "real world" impact rather than the per unit
| impact. But this is written for engineers, so I'd expect it to
| also be focused on per unit impacts for a blog like this.
|
| However, having said all that, I'd love to hear what your
| reservations are using it as a metric.
| forrestthewoods wrote:
| It's not wrong per se. I'm just very wary of nano-scale
| benchmarks. And I think in general you should advertise
| "velocity" not "time per".
|
| Perhaps it's a long time inspiration from this post:
| https://randomascii.wordpress.com/2018/02/04/what-we-talk-
| ab...
|
| I also just don't know what to do with "1 ns per element".
| The scale of 1 to 4 ns per element is remarkably imprecise.
| Discussing 1 to 250 million to 1 billion elements per second
| feels like a much wider range. Even if it's mathematically
| identical.
|
| Your graphs have a few odd spikes that weren't deeply
| discussed. If it's under 2ns per element who cares!
|
| The logarithmic scale also made it really hard to interpret.
| Should have drawn clearer lines at L1/L2/L3/ram limits.
|
| On skim I don't think there's anything wrong. But as
| presented it's a little hard for me as an engineer to extract
| lessons or use this information for good (or evil).
|
| There shouldn't be a Linux vs Mac issue. Ignoring mmap this
| should be HW.
|
| I dunno. Those are all just surface level reactions.
| sestep wrote:
| Haha, it seems you may have thought the person you were
| responding to is the post author :) but actually that would
| be me.
|
| Agreed that the odd spikes don't matter, that's why I
| didn't bother discussing them; I was more interested in the
| data after the array got large enough that random access
| was actually slower. It looked like all those weird spikes
| were for arrays small enough to fit in cache anyways.
|
| I agree that it could have been helpful if I'd drawn lines
| at L1/L2/L3/RAM limits, but I didn't do that because I
| don't think it's entirely clear where those lines should
| have been drawn. Specifically because there are two arrays.
| Should the line show just where the floating-point array is
| small enough to fit in cache, or where both arrays together
| are?
|
| Not sure I quite follow what you're saying about mmap on
| Linux vs Mac; only one of the three sets of experiments
| used mmap, and the third was explicitly to try to tease out
| that effect. Especially for the first experiment, I agree
| that there should be no difference for arrays small enough
| to fit in RAM, since the whole file gets read into memory
| first.
| alain94040 wrote:
| From your blog post:
|
| > Random access from the cache is remarkably quick. It's
| comparable to sequential RAM performance
|
| That's actually expected once you think about it, it's a
| natural consequence of prefetching.
| delusional wrote:
| If that wasn't the case the machine would have to prefetch to
| register file. I don't know of any CPU that does that.
| forrestthewoods wrote:
| Heh. That line often gets called out.
|
| Lots of things are expected when you deeply understand a
| complex system and think about it. But, like, not everyone
| knows the system that deeply nor have they thought about it!
| petermcneeley wrote:
| Whats most misleading is the data for the smaller sizes (1k)
| sestep wrote:
| Great post, thanks for the link! I think you and I were just
| focusing on different things. You gave a broader discussion of
| the topic from a few different angles, with more specific basic
| numbers about CPUs as well as more realistic benchmarks than
| what I have here. I just wanted to focus on the simplest
| example I could think of, and run it on as wide a range of
| different array sizes as I could.
|
| The reason I chose "time per element" then follows from that
| different goal, because I was comparing across vastly different
| array sizes, so no other metric I could think of would have
| really worked for the charts I was drawing.
| porcoda wrote:
| The RandomAccess (or GUPS) benchmark (see:
| https://ieeexplore.ieee.org/document/4100365) was looking at
| measuring machines on this kind of workload. In high performance
| computing this was important for graph calculations and was one
| of the things the Cray (formerly Tera) MTA machine was
| particularly good at. I suppose this benchmark wouldn't be very
| widely known outside HPC circles.
| jandrewrogers wrote:
| I worked on the MTA architectures for years among several other
| HPC systems but I don't remember this particular benchmark. I
| suspect it was replaced by the Graph500 benchmark. Graph500
| measures something similar and was introduced only a few years
| after GUPS.
| porcoda wrote:
| The HPCS benchmarks predated Graph500. They were talked about
| at SC for a few years in the early 2000s but mostly faded
| into the background. It's hard to dig up the numbers for the
| MTA on RandomAccess, but the Eldorado paper from '05 by Feo
| and friends (https://dl.acm.org/doi/10.1145/1062261.1062268)
| mentions it and you can see the MTA beating the other popular
| architectures of the time in one of the tables.
| jandrewrogers wrote:
| Feo was a major MTA stan and proponent, even years later.
| Honestly, it is probably my favorite computing architecture
| of all time despite the weaknesses of the implementation.
| It was extraordinarily efficient in some contexts. Few
| people could design properly optimized code for them
| though, which was an additional problem.
|
| There were proofs of concept by 2010 that the latency-
| hiding mechanics could be implemented on CPUs in software,
| which while not as efficient had the advantage of cost and
| performance, which was a death knell for the MTA. A few
| attempts to revive that style of architecture have come and
| gone. It is very difficult to compete with the economics of
| mass-scale commodity silicon.
|
| I hold out hope that a modern barrel processor will become
| available at some point but I'm not sanguine about it.
| FpUser wrote:
| I did another type of experiment which evaluates benefits of
| branch prediction on AMD 9950X on contiguous array with 1,000,000
| elements. Calculated sum adding element if it is bigger than 125
| (50% of 256). Difference between random and sorted was 10 times.
| I guess branch prediction plays a huge role as well.
| Andys wrote:
| Thanks for sharing that.
|
| Presumably if you'd split the elements into 16 shares (one for
| each CPU), summed with 16 threads, and then summed the lot at
| the end, then random would be faster than sorted?
| bee_rider wrote:
| I don't think random should be faster than contiguous access,
| if you parallelize both of them.
|
| Although, it looks like that chip has a 1MB L2 cache for each
| core. If these are 4 Bytes ints, then I guess they won't all
| fit in one core's L2, but maybe they can all start out in
| their respective cores' L2 if it is parallelized (well,
| depends on how you set it up).
|
| Maybe it will be closer. Contiguous should still win.
| o11c wrote:
| Hm, no discussion of cache line size, page size, or the limits of
| cache associativity?
| sestep wrote:
| Fair, it probably would have been useful for me to include a
| link to a page discussing those ideas. Since those
| theoretical/qualitative ideas are already covered in plenty of
| places online, I didn't bother to talk about them here since
| they're easy to look up; I just wanted to focus on quantitative
| data from actual measurements. But again, I agree I should have
| at least mentioned them or linked somewhere.
| Animats wrote:
| If, of course, you have the CPU and its caches all to yourself.
| tiluha wrote:
| This is something i have been thinking about lately. How well
| do these performance optimizations work in the cloud on a
| shared system?
| beng-nl wrote:
| It's fair to assume that on a vm in the cloud the cores you
| get are dedicated to you - otherwise the CSP is risking
| exposure to headline making security problems.. (In the
| unpleasant event that someone exploits an unmitigated cpu
| bug.)
|
| And of course the headline of getting a cpu you can't fully
| use.
| tiluha wrote:
| Im pretty sure this is not the case on most providers,
| where "dedicated" VPSs demand a significant premium over
| the default "shared" VPSs
| JonChesterfield wrote:
| Random access is catastrophically slower because of the
| successive cache misses when the prefetcher fails to guess what
| you're doing.
|
| One hint in the same article that random access is not cheap, in
| contrast with the conclusion, was noticing that the shuffle was
| unacceptably slow on large data sets.
|
| Still, good to see peformance measurements, especially where the
| curves look roughly like you'd hope them to.
| sestep wrote:
| The shuffle was only unacceptably slow for data too big to fit
| in memory. For data that fits in memory, Fisher-Yates is
| totally fine; this is why it's fine for the two-pass shuffle to
| use buckets that fit in RAM but not in cache.
| Surac wrote:
| is this not just a memory test for the burst capacitiy and access
| strategy of the dram controller?
| b0a04gl wrote:
| longtime back ran a model scoring job where each row did feature
| lookups across diff memory regions. access pattern changed every
| run since it depended on prev feature values. avg latency stayed
| fine but total run time kept jumping sometimes 6s, sometimes 8s
| on same input. perf counters looked flat but thread scheduling
| kept shifting. reordered the lookups to cut down mem jumps. after
| that threads aligned better, scheduler ran smoother, run time got
| stable across batches. gain wasn't from faster mem, imo i
| observed it's not the memory is slower but rather how less
| predictable it's
| anonymousDan wrote:
| Would a better benchmark not just use some kind of pseudo
| randomly generated sequence to avoid having two arrays?
| sestep wrote:
| Unclear if that'd be "better" but definitely something to
| compare against! Here's a related post by someone else that
| measures more of what you're talking about:
| https://lemire.me/blog/2018/03/24/when-shuffling-large-array...
| archi42 wrote:
| What surprises me is the 24 GB of DDR4 DRAM on a dual channel
| memory controller? AFAIK there are only 8 GB or 16 GB modules, no
| 12 GB modules. At least I can only find 12 GB DDR5 modules
| listed, but not DDR4.
|
| This means: The system likely uses 3x 8 GB modules. As a result,
| one channel has two modules with 16 GB total, while the other
| channel has only a single 8 GB module.
|
| Not sure how big this impact is with the given memory access
| patterns and assuming [mostly] exclusive single-threaded access.
| It's just something I noted, and could be a source of unexpected
| artifacts.
| CodesInChaos wrote:
| Could be 2x8 + 2x4. Mine has 2x32 + 2x8, since I upgraded from
| 16 to 80 instead of 64.
| sestep wrote:
| Yes, sorry for not being more explicit! It's 3x8GiB. Originally
| 4x, but one of my RAM sticks broke and I never bothered to
| replace it.
| archi42 wrote:
| I'm not deep into the details of the AMD DRAM controller, but
| this detail could cause some of your anomalies. If this was
| an academic paper, the findings would be borderline invalid.
| You might want to remove the extra module and run the
| benchmarks again.
|
| At least once the tests become big enough to have some data
| in both partitions, the bandwidth will start to matter.
| sestep wrote:
| Thanks, I may try that.
|
| Out of curiosity, what do you see when running the same
| code on your machine?
| Cold_Miserable wrote:
| Worst case scenario for random access is a multiple level TLB
| miss, a memory refresh cycle and then a system management mode
| interrupt all occurring consecutively.
___________________________________________________________________
(page generated 2025-06-27 23:01 UTC)