9 ms·

The Myth of RAM (2014)

104 points by jchook 3y ago

H8crilA 3y ago
This also applies when you scale up to the multi petabyte RAM range via distributed computing/cloud. I wonder if we could actually continue the (very rough) linear fit on a log-log plot.
dist-epoch 3y ago
It's even worse on GPUs. There memory access speed depends not only on N as described in this article, but also on the order in which you access the little bits of N, like CPU cache locality, but also different in important ways.
kristianp 3y ago
There's a good discussion from 2016 here: https://news.ycombinator.com/item?id=12383012 https://news.ycombinator.com/item?id=12383012
- dang 3y ago
  Thanks! Macroexpanded: The Myth of RAM (2014) - https://news.ycombinator.com/item?id=12383012 https://news.ycombinator.com/item?id=12383012 - Aug 2016 (277 comments)
blagie 3y ago
FYI: This article sucks (in relative terms) if you read Part I in isolation. Click on Part II to get to the really good parts. From there on, it gets weaker. If you're busy, you can skip / skim parts III and IV. My hope is this post saves someone some time. Part 1: Empirical. Good. Part 2: Theoretical limit. Really motivates Part 1 and gives an interesting perspective. Part 3: Implications. Weaker overall. Part 4: Clarifications / definitions / etc. Only helpful if you have questions or didn't understand something. Missing: Showing best-case is O(log N) and not O(N) simply due to addressing. If I want to address a petabyte, I need 50 bits, and a kilobyte, only 10. That's also good theoretical limit as to why it's not O(N), although not nearly as nice as the authors'.
- dragontamer 3y ago
  Hmmm... O(log(n)) confuses me. I could have sworn that the "Center-of-spherical library" thought experiment proves that its O(cube-root(n)) in 3-dimensional space, and O(square-root(n)) for 2-dimensional space. That is: all memory has a physical shape, and the worst-case speed is related to the distance away from the center (aka: CPU Core) and whatever "book" or memory-cell you're looking for. For a 2d space, the optimal organization of books (or memory cells), is a perfect circle: each book is exactly R (radius) distance away from the center, meaning all books can be fetched under equal time. This leads to O(sqrt(n)) performance, as the more memory you have (assuming memory is the same "shape"), the larger the circle _must_ become. For 3d space, the optimal organization of books is a perfect sphere. Same-same really, except we can fly now. Real-world chips are largely 2d technologies, but given the shear number of layers available on modern chips (hundreds of layers for Flash and other tech), maybe spherical / 3d perspectives are a better theory to work off of. Transitioning between layers is always fraught with problems (vias in physical chips / boards have inductances and other parasitics after all), so we're somewhere between 2-dimensions and 3-dimensions in practice (with more and more tricks to get us towards the 3d side). ------------ In the real world: chips are limited by these parasitic elements (inductances and capacitances), which slow down the electrical signal. But these are primarily related to distance (more inductance the longer a trace is, and more capacitance the more ground-is-parallel to that trace). So this theory ends up working out as a physical model of the electrons moving at the chip level to fetch data and communicate.
  - bee_rider 3y ago
    The article makes an argument about black holes to get to r^2 instead of r^3. It seems a bit surprising, but then I don’t know that type of physics. Thinking of the more classical geometrical point of view, I agree that between 2D and 3D seems right. If nothing else, I’d imagine there aren’t many wires going diagonally through the layers, haha. Maybe a cylinder would be the right model.
  - blagie 3y ago
    Let me clarify: This wasn't intended to contradict the root-n limit. Both limits exist. * The root-n limit is based on physics of a 3d universe. * A log n limit is based on computation, and would apply even in a infinite-dimensional universe, where everything is one unit away. The root-n is a stronger limiting factor, obviously, but both are helpful to know since they talk about different limits from different premises. Both disprove O(1). Both are (1) quite theoretical (2) not the limiting factor in most scenarios in practical terms (3) still apply in a limited set of cases. The log n argument is helpful, for example, for network addressing for the internet and network topologies (and issues like 32 bit versus 128 bit addresses, NAT, etc.), were distances are well above the limits of physics, and the root-n argument doesn't apply. It's also helpful to know since it also applies to storage, and not just speed. If I have twice as much storage, my pointers all get longer by a bit. (I'm intentionally omitting square root versus cube root, since that's tangential to the above, and a rabbit hole I don't want to go down right now; perhaps another post)
38321003thrw 3y ago
This article has a strange take on algorithmic scaling. L1, L2, LL, MM, Disk, NetDisk ..., GalacticRAM. Wow, you actually expected traversing ‘system boundaries’ with distinct access costs and maintain theoretical scaling? An algorithm that is O(n) will be O(n) in L1, O(n) in L2, ,..., and yes O(n) in GalacticRAM. Each (sub-)system traversal is due to exceeding capacity limits. There is likely a more interesting mathematical result buried in here, since we see that a series of sub-systems with relative constant order of magnitude increases in access costs in aggregate transforms f -> f’ with this interesting n^.5 term showing up instead of the logs.
- karmakaze 3y ago
  This is the 2nd post I've seen recently submitted to HN that plays fast and loose with big-O notation. It has a defined meaning. If someone wants to talk about something else, great use different notation. People already seem to have some trouble grokking big-O and we don't need to muddy it with 'ad-hack' usages.
  - Dylan16807 3y ago
    According to the exact literal meaning, every algorithm you ever run on your computer is O(1), because your computer is finite. The same can be applied to the reachable universe. Context is inevitable.
    - karmakaze 3y ago
      ...which becomes meaningless and not useful. There is a whole area of mechanical sympathy and cache aware or cache oblivious algorithms that are well worth discussing and learning, but we don't need to use big-O notation to do so.
      - Dylan16807 3y ago
        It's useful notation even when we're not dealing with mathematical infinities. Unless you have a better alternative for the same purpose, "don't use it" is a pretty bad answer. It's being used for pretty much the same meaning. Not meaningless at all.
cuno 3y ago
Funnily enough I published something similar as part of my PhD (2010). Essentially communication costs dominate over computation costs - an addition operation is practically free compared to the time and energy of moving data within a chip to the ALU to do the addition, let alone between chips. This is now the reverse situation to historical VLSI - whereby the computation was slow and expensive compared to practically "fast and free" on-chip communication. The implications extend far beyond just RAM. But yes, depending on the access patterns involved and the (physical) spatial arrangement of data, binary tree traversal (on 2D CMP or 2D cross-chip layout) is O(sqrt(N)) or O(log(N)sqrt(N)), and this result is not dependent on the system boundaries of memory hierarchies - it is true for dedicated on-chip scratchpad memories as it is for giant wafer-scale chips (such as Cerebras) as well. There are some special cases where it can be O(1) or O(log(N)) on average that I won't go into, but you can read more here if interested (sections 2.1 and 8.3): https://www.cl.cam.ac.uk/~swm11/research/greenfield.html https://www.cl.cam.ac.uk/~swm11/research/greenfield.html A key way to think about things is that algorithms are not really running in some Platonic realm, each executed instruction occurs at some physical location and time, and data needs to move from one place and time to another place and time. To this end both physical wiring (or networks) are required to move the data spatially, and memory is used to move the data temporally. Together an algorithm's executed instructions are situated somewhere spatio-temporally and RAM (both on-chip and off-chip) serves as a temporal interconnect, but one that itself takes up physical space.
- ChuckMcM 3y ago
  I like to think of this as level 2 systems analysis. It is implied in some of Feynman's papers on computation as well. It gets even more interesting (to me) when you consider semantic entanglement of data in non-platonic spaces. When you treat 'time to data access' as a fourth dimension and the state transition vector of an algorithm as the path one can show that Ft(O(path(n))) (Ft being the function that converts the complexity of a path into the time such a path takes to transit) for some arbitrary n is rather difficult to nail down. It can also pop out the result that the lowest complexity path(algorithm) is not faster than a high complexity path(algorithm) if the entangled elements(data) are in a slow space. Crazy I know but it is a pretty straight forward path from Amdahl's law to this sort of analysis.
GuB-42 3y ago
There is also a simple, weaker argument about why memory addressing is not O(1). To address memory of size N, you need a log(N) sized addresses. Operations on log(N) sized numbers are not constant time, so addressing memory of an arbitrary size can't be constant time. We usually take operations like addition as if they were constant time because we assume a certain number of bits, and indeed, 32 or 64 bit addition is constant time, but not the addition of arbitrary sized numbers (aka. bignum). Retrieving data from memory, even magic memory that doesn't care about the laws of physics is actually a kind of binary search. You take the most significant bit of the address, which tells you in which half of the memory bank it is, then the next bit gives you the next half, then the next, etc... until you get to the cell containing your data. That's O(log(N)), not O(1). My argument is weaker that the one in the article, because it doesn't take the laws of physics in consideration so it only puts memory operations at O(log(N)) and not O(sqrt(N)), but the idea is similar in that memory operations are not constant time. It is also the reason why I think that log(N) in big-O notation is the limit of practicality. That is, further than that and big-O becomes meaningless and one needs to take the actual machine in consideration. Maybe, after reading the article, O(sqrt(N)) should be the limit instead.
- jplrssn 3y ago
  I’m struggling to understand this argument. The size of memory that you can address on any particular hardware is fixed, just like the word size for additions. Restricting yourself to a smaller part of that address space in software won’t change anything about how the address is decoded.
  - mikebenfield 3y ago
    Big O notation deals with asymptotic behavior of a function - in other words, as N goes to infinity. If we're accepting the premise that N has an upper bound, the rest of the discussion is meaningless. Presumably the argument is an abstract one, not applying to any particular machine that actually exists.
    - charcircuit 3y ago
utopcell 3y ago
The author took the time to write four long blog posts on the subject but apparently din't bother to look up cache-oblivious algorithms [1], i.e. the field that deals with designing algorithms that work well in the presence of memory hierarchies. [1] https://en.wikipedia.org/wiki/Cache-oblivious_algorithm https://en.wikipedia.org/wiki/Cache-oblivious_algorithm
- anonymoushn 3y ago
  These seem minimally useful in the sense that once one needs to whip out the SIMD intrinsics and software prefetches one probably actually cares about the 30% or 100% speedup one can get by writing cache-aware algorithms instead.
  - utopcell 3y ago
    The opportunity from designing cache-aware algorithms is much larger than a 2X speedup. As a rule of thumb, main memory : L1 access times are ~ 100 : 1. The canonical example of a cache-aware algorithm is scanning a 2D array as it is laid out on RAM vs in cache-hostile strides. The perf diff varies per architecture, but on my Broadwell server, the former is ~6.7X faster than the latter for a 10000 x 10000 int array. Of course there is a large perf opportunity in vectorizing code, but that was not in scope for this blog post.
    - deleted 3y ago
      [deleted]
    - tsimionescu 3y ago
      The so called cache-oblivious algorithms are exactly designed to account for the speed difference between cache levels. The term cache-oblivious refers to the fact that these algorithms don't take into account the exact sizes of the various cache levels.
metadat 3y ago
How did the author ensure the memory allocations were not contiguous? I suppose in C/C++ it's relatively straightforward since you could allocate a bunch, then free 99% of it, repeatedly. Not sure how to do this in Java, Go, or Rust.
- gizmo686 3y ago
  Code is here: https://github.com/emilk/ram_bench/blob/master/list_traversal.c https://github.com/emilk/ram_bench/blob/master/list_traversa... The author makes 2 allocations: Node* memory = (Node*)malloc(N * sizeof(Node)); Node** nodes = (Node**)malloc(N * sizeof(Node*)); Of those, only the first one (memory) is actually used during measurement, The seconds one (nodes) is just there to help shuffle the linked list, and is freeded before the actual test: free(nodes); // Free up unused memory before meassuring: // Do the actual measurements: Int start = clock(); ... Since the linked list is shuffeled, the nodes will be linked in a random order. However, since the total memory is contigous, that is the only factor (instead of having every node be a separate allocation, which could allow the system to put every node on a separate page)
- tsimionescu 3y ago
  The same trick should work in Rust as in C or C++. In Java you could create a linked list class, pin the nodes in memory so that the GC doesn't compact them , then apply the same shuffling. In Go you can go back to the C trick, since Go's garbage collector doesn't do any kind of compaction.
greesil 3y ago
Cache lines, are like a thing, man. Unless you're on an embedded processor.
dahart 3y ago
> The blue line corresponds to a O(√N) cost of each memory access. Seems like a pretty good fit, no? Kind-of obvious, and I’m sure I’ve bumped into this before, but it suddenly surprised me again looking at this: a sqrt(N) line on a log-log graph is a straight line, so at a glance looks identical to the linear N aside from slope, and without a reference point N, and with two axes of differing units and differing spacing, it’s pretty hard to see whether a line is sqrt(N), or how far away from N it is.
- nwallin 3y ago
  I think you've rediscovered Mar's law. "Everything is linear if plotted log-log with a fat magic marker."
lionkor 3y ago
A better way to ensure non-contiguous memory is allocating 2, maybe 3x the memory you need by repeatedly calling mmap(), then picking random points in that memory, and using those. Otherwise chances are your memory is still contiguous

104 points by jchook 3y ago

This also applies when you scale up to the multi petabyte RAM range via distributed computing/cloud. I wonder if we could actually continue the (very rough) linear fit on a log-log plot.

dist-epoch 3y ago

It's even worse on GPUs. There memory access speed depends not only on N as described in this article, but also on the order in which you access the little bits of N, like CPU cache locality, but also different in important ways.

kristianp 3y ago

There's a good discussion from 2016 here: https://news.ycombinator.com/item?id=12383012 https://news.ycombinator.com/item?id=12383012

dang 3y ago
Thanks! Macroexpanded: The Myth of RAM (2014) - https://news.ycombinator.com/item?id=12383012 https://news.ycombinator.com/item?id=12383012 - Aug 2016 (277 comments)

blagie 3y ago

FYI: This article sucks (in relative terms) if you read Part I in isolation. Click on Part II to get to the really good parts. From there on, it gets weaker. If you're busy, you can skip / skim parts III and IV. My hope is this post saves someone some time. Part 1: Empirical. Good. Part 2: Theoretical limit. Really motivates Part 1 and gives an interesting perspective. Part 3: Implications. Weaker overall. Part 4: Clarifications / definitions / etc. Only helpful if you have questions or didn't understand something. Missing: Showing best-case is O(log N) and not O(N) simply due to addressing. If I want to address a petabyte, I need 50 bits, and a kilobyte, only 10. That's also good theoretical limit as to why it's not O(N), although not nearly as nice as the authors'.

dragontamer 3y ago
Hmmm... O(log(n)) confuses me. I could have sworn that the "Center-of-spherical library" thought experiment proves that its O(cube-root(n)) in 3-dimensional space, and O(square-root(n)) for 2-dimensional space. That is: all memory has a physical shape, and the worst-case speed is related to the distance away from the center (aka: CPU Core) and whatever "book" or memory-cell you're looking for. For a 2d space, the optimal organization of books (or memory cells), is a perfect circle: each book is exactly R (radius) distance away from the center, meaning all books can be fetched under equal time. This leads to O(sqrt(n)) performance, as the more memory you have (assuming memory is the same "shape"), the larger the circle _must_ become. For 3d space, the optimal organization of books is a perfect sphere. Same-same really, except we can fly now. Real-world chips are largely 2d technologies, but given the shear number of layers available on modern chips (hundreds of layers for Flash and other tech), maybe spherical / 3d perspectives are a better theory to work off of. Transitioning between layers is always fraught with problems (vias in physical chips / boards have inductances and other parasitics after all), so we're somewhere between 2-dimensions and 3-dimensions in practice (with more and more tricks to get us towards the 3d side). ------------ In the real world: chips are limited by these parasitic elements (inductances and capacitances), which slow down the electrical signal. But these are primarily related to distance (more inductance the longer a trace is, and more capacitance the more ground-is-parallel to that trace). So this theory ends up working out as a physical model of the electrons moving at the chip level to fetch data and communicate.
- bee_rider 3y ago
  The article makes an argument about black holes to get to r^2 instead of r^3. It seems a bit surprising, but then I don’t know that type of physics. Thinking of the more classical geometrical point of view, I agree that between 2D and 3D seems right. If nothing else, I’d imagine there aren’t many wires going diagonally through the layers, haha. Maybe a cylinder would be the right model.
- blagie 3y ago
  Let me clarify: This wasn't intended to contradict the root-n limit. Both limits exist. * The root-n limit is based on physics of a 3d universe. * A log n limit is based on computation, and would apply even in a infinite-dimensional universe, where everything is one unit away. The root-n is a stronger limiting factor, obviously, but both are helpful to know since they talk about different limits from different premises. Both disprove O(1). Both are (1) quite theoretical (2) not the limiting factor in most scenarios in practical terms (3) still apply in a limited set of cases. The log n argument is helpful, for example, for network addressing for the internet and network topologies (and issues like 32 bit versus 128 bit addresses, NAT, etc.), were distances are well above the limits of physics, and the root-n argument doesn't apply. It's also helpful to know since it also applies to storage, and not just speed. If I have twice as much storage, my pointers all get longer by a bit. (I'm intentionally omitting square root versus cube root, since that's tangential to the above, and a rabbit hole I don't want to go down right now; perhaps another post)

38321003thrw 3y ago

This article has a strange take on algorithmic scaling. L1, L2, LL, MM, Disk, NetDisk ..., GalacticRAM. Wow, you actually expected traversing ‘system boundaries’ with distinct access costs and maintain theoretical scaling? An algorithm that is O(n) will be O(n) in L1, O(n) in L2, ,..., and yes O(n) in GalacticRAM. Each (sub-)system traversal is due to exceeding capacity limits. There is likely a more interesting mathematical result buried in here, since we see that a series of sub-systems with relative constant order of magnitude increases in access costs in aggregate transforms f -> f’ with this interesting n^.5 term showing up instead of the logs.

karmakaze 3y ago
This is the 2nd post I've seen recently submitted to HN that plays fast and loose with big-O notation. It has a defined meaning. If someone wants to talk about something else, great use different notation. People already seem to have some trouble grokking big-O and we don't need to muddy it with 'ad-hack' usages.
- Dylan16807 3y ago
  According to the exact literal meaning, every algorithm you ever run on your computer is O(1), because your computer is finite. The same can be applied to the reachable universe. Context is inevitable.
  - karmakaze 3y ago
    ...which becomes meaningless and not useful. There is a whole area of mechanical sympathy and cache aware or cache oblivious algorithms that are well worth discussing and learning, but we don't need to use big-O notation to do so.
    - Dylan16807 3y ago
      It's useful notation even when we're not dealing with mathematical infinities. Unless you have a better alternative for the same purpose, "don't use it" is a pretty bad answer. It's being used for pretty much the same meaning. Not meaningless at all.

cuno 3y ago

Funnily enough I published something similar as part of my PhD (2010). Essentially communication costs dominate over computation costs - an addition operation is practically free compared to the time and energy of moving data within a chip to the ALU to do the addition, let alone between chips. This is now the reverse situation to historical VLSI - whereby the computation was slow and expensive compared to practically "fast and free" on-chip communication. The implications extend far beyond just RAM. But yes, depending on the access patterns involved and the (physical) spatial arrangement of data, binary tree traversal (on 2D CMP or 2D cross-chip layout) is O(sqrt(N)) or O(log(N)sqrt(N)), and this result is not dependent on the system boundaries of memory hierarchies - it is true for dedicated on-chip scratchpad memories as it is for giant wafer-scale chips (such as Cerebras) as well. There are some special cases where it can be O(1) or O(log(N)) on average that I won't go into, but you can read more here if interested (sections 2.1 and 8.3): https://www.cl.cam.ac.uk/~swm11/research/greenfield.html https://www.cl.cam.ac.uk/~swm11/research/greenfield.html A key way to think about things is that algorithms are not really running in some Platonic realm, each executed instruction occurs at some physical location and time, and data needs to move from one place and time to another place and time. To this end both physical wiring (or networks) are required to move the data spatially, and memory is used to move the data temporally. Together an algorithm's executed instructions are situated somewhere spatio-temporally and RAM (both on-chip and off-chip) serves as a temporal interconnect, but one that itself takes up physical space.

ChuckMcM 3y ago
I like to think of this as level 2 systems analysis. It is implied in some of Feynman's papers on computation as well. It gets even more interesting (to me) when you consider semantic entanglement of data in non-platonic spaces. When you treat 'time to data access' as a fourth dimension and the state transition vector of an algorithm as the path one can show that Ft(O(path(n))) (Ft being the function that converts the complexity of a path into the time such a path takes to transit) for some arbitrary n is rather difficult to nail down. It can also pop out the result that the lowest complexity path(algorithm) is not faster than a high complexity path(algorithm) if the entangled elements(data) are in a slow space. Crazy I know but it is a pretty straight forward path from Amdahl's law to this sort of analysis.

GuB-42 3y ago

There is also a simple, weaker argument about why memory addressing is not O(1). To address memory of size N, you need a log(N) sized addresses. Operations on log(N) sized numbers are not constant time, so addressing memory of an arbitrary size can't be constant time. We usually take operations like addition as if they were constant time because we assume a certain number of bits, and indeed, 32 or 64 bit addition is constant time, but not the addition of arbitrary sized numbers (aka. bignum). Retrieving data from memory, even magic memory that doesn't care about the laws of physics is actually a kind of binary search. You take the most significant bit of the address, which tells you in which half of the memory bank it is, then the next bit gives you the next half, then the next, etc... until you get to the cell containing your data. That's O(log(N)), not O(1). My argument is weaker that the one in the article, because it doesn't take the laws of physics in consideration so it only puts memory operations at O(log(N)) and not O(sqrt(N)), but the idea is similar in that memory operations are not constant time. It is also the reason why I think that log(N) in big-O notation is the limit of practicality. That is, further than that and big-O becomes meaningless and one needs to take the actual machine in consideration. Maybe, after reading the article, O(sqrt(N)) should be the limit instead.

jplrssn 3y ago
I’m struggling to understand this argument. The size of memory that you can address on any particular hardware is fixed, just like the word size for additions. Restricting yourself to a smaller part of that address space in software won’t change anything about how the address is decoded.
- mikebenfield 3y ago
  Big O notation deals with asymptotic behavior of a function - in other words, as N goes to infinity. If we're accepting the premise that N has an upper bound, the rest of the discussion is meaningless. Presumably the argument is an abstract one, not applying to any particular machine that actually exists.
  - charcircuit 3y ago

utopcell 3y ago

The author took the time to write four long blog posts on the subject but apparently din't bother to look up cache-oblivious algorithms [1], i.e. the field that deals with designing algorithms that work well in the presence of memory hierarchies. [1] https://en.wikipedia.org/wiki/Cache-oblivious_algorithm https://en.wikipedia.org/wiki/Cache-oblivious_algorithm

anonymoushn 3y ago
These seem minimally useful in the sense that once one needs to whip out the SIMD intrinsics and software prefetches one probably actually cares about the 30% or 100% speedup one can get by writing cache-aware algorithms instead.
- utopcell 3y ago
  The opportunity from designing cache-aware algorithms is much larger than a 2X speedup. As a rule of thumb, main memory : L1 access times are ~ 100 : 1. The canonical example of a cache-aware algorithm is scanning a 2D array as it is laid out on RAM vs in cache-hostile strides. The perf diff varies per architecture, but on my Broadwell server, the former is ~6.7X faster than the latter for a 10000 x 10000 int array. Of course there is a large perf opportunity in vectorizing code, but that was not in scope for this blog post.
  - deleted 3y ago
    [deleted]
  - tsimionescu 3y ago
    The so called cache-oblivious algorithms are exactly designed to account for the speed difference between cache levels. The term cache-oblivious refers to the fact that these algorithms don't take into account the exact sizes of the various cache levels.

metadat 3y ago

How did the author ensure the memory allocations were not contiguous? I suppose in C/C++ it's relatively straightforward since you could allocate a bunch, then free 99% of it, repeatedly. Not sure how to do this in Java, Go, or Rust.

gizmo686 3y ago
Code is here: https://github.com/emilk/ram_bench/blob/master/list_traversal.c https://github.com/emilk/ram_bench/blob/master/list_traversa... The author makes 2 allocations: Node* memory = (Node*)malloc(N * sizeof(Node)); Node** nodes = (Node**)malloc(N * sizeof(Node*)); Of those, only the first one (memory) is actually used during measurement, The seconds one (nodes) is just there to help shuffle the linked list, and is freeded before the actual test: free(nodes); // Free up unused memory before meassuring: // Do the actual measurements: Int start = clock(); ... Since the linked list is shuffeled, the nodes will be linked in a random order. However, since the total memory is contigous, that is the only factor (instead of having every node be a separate allocation, which could allow the system to put every node on a separate page)
tsimionescu 3y ago
The same trick should work in Rust as in C or C++. In Java you could create a linked list class, pin the nodes in memory so that the GC doesn't compact them , then apply the same shuffling. In Go you can go back to the C trick, since Go's garbage collector doesn't do any kind of compaction.

greesil 3y ago

Cache lines, are like a thing, man. Unless you're on an embedded processor.

dahart 3y ago

> The blue line corresponds to a O(√N) cost of each memory access. Seems like a pretty good fit, no? Kind-of obvious, and I’m sure I’ve bumped into this before, but it suddenly surprised me again looking at this: a sqrt(N) line on a log-log graph is a straight line, so at a glance looks identical to the linear N aside from slope, and without a reference point N, and with two axes of differing units and differing spacing, it’s pretty hard to see whether a line is sqrt(N), or how far away from N it is.

nwallin 3y ago
I think you've rediscovered Mar's law. "Everything is linear if plotted log-log with a fat magic marker."

lionkor 3y ago

A better way to ensure non-contiguous memory is allocating 2, maybe 3x the memory you need by repeatedly calling mmap(), then picking random points in that memory, and using those. Otherwise chances are your memory is still contiguous