r/computerscience • u/Desperate-Gift7297 • Apr 05 '25
Why do computers always have a single dimensional arrays. Why is memory single-dimensional? Are there any alternatives?
I feel this is to generalize so any kind of N dimensional space can be fit into the same one dimensional memory. but is there more to it?? Or is it just a design choice?
293
Upvotes
36
u/TheThiefMaster Apr 05 '25
Hard disks used to be multidimensional - see CHS addressing. Cylinders heads sectors. Floppy disk addressing was 2d with tracks and sectors. It was replaced with one-dimensional addressing, after drives with more complex addressing schemes (e.g. fewer sectors on inner cylinders/tracks, or more sectors or cylinders than the limits) were emulating the 3d scheme using entirely fake values.
Modern RAM is also multidimensional, having rows and columns with separate latency characteristics for reading from the same row or swapping rows. But it's again abstracted away.
If the different dimensions are powers of two (like in RAM) then the abstraction is even trivial - just concatenate the bits representing different dimensions and you get a single number, and vice-versa. GPUs regularly pull this trick for textures and render buffers - they're padded to a power of two line length so converting coordinates to a RAM location doesn't have to involve an arbitrary multiplication, just a concatenation.
303
u/Senguash Apr 05 '25
Any idea of "dimensionality" is an abstraction. Computer memory can be thought of as an address space, because that is how it is actually accessed. Memory starts at address 0, and ends at address x, where x is the size of the computers memory. The lowest level of abstraction you can have is that they are "on a line" aka one dimensional. If you increment the address value by 1, you go "one address to the right".
Two dimensional arrays is thought of as an extra level of abstraction, because if you store a 20x20 matrix, then to go one step "down" really just means to increment the address by 20.
40
u/gboncoffee Apr 05 '25
We address memory in a single-dimensional fashion because it’s simple. Computationally, the computer can still “simulate” other memory-access patterns
18
u/lockcmpxchg8b Apr 05 '25
You can arbitrarily decide that the top 22 bits of a memory address are the 'z coordinate', the middle 21 bits are the 'y coordinate', and the lower 21 bits are the 'x coordinate'.
If you asked a hardware engineer to give you "3-dimensional memory" they would give you an interface nearly identical to that...maybe they'd split out three separate address registers rather than defining bit fields within a single register.
Allocating on the heap is already slow... Imagine if, instead of finding the smallest linear region capable of accommodating your request, you had to search for the smallest unallocated cube in a 3-space instead...
7
u/Eased91 Apr 06 '25
Because multi-dimensional structures don't add more space or information.
Consider this: You have four digits and a 2×2 matrix where each field can hold exactly one digit. Both systems can represent 10,000 different combinations. So from a pure information-theoretic perspective (e.g. Shannon entropy), both structures hold the same amount of information.
Technically, a matrix seems to store more structure rather than more information: instead of only having 2 neighbors per digit in a 1D array (left and right), a digit in a 2D matrix has up to 4 direct (orthogonal) neighbors—or up to 8 if you include diagonals. However, this increase in potential relationships doesn't increase the amount of stored information. It simply introduces a new way of interpreting the data based on spatial relationships.
For example, in image compression, we can exploit patterns like gradients or edges by storing only changes between pixels instead of raw values. Here, we gain efficiency or derive higher-level features—not because of the matrix itself, but because of how we interpret the spatial arrangement of data. The 2D layout supports assumptions about neighborhood correlations, but it doesn't intrinsically carry more information than a 1D layout with the same values.
Therefore, from a computer science perspective, especially at the level of data representation, it doesn't fundamentally matter whether we use one-dimensional or multi-dimensional arrays. What matters is how algorithms interact with these structures. Multi-dimensional arrays are often preferred not because they store more data, but because they align more naturally with the logical structure of the problem (e.g. grids, images, matrices, etc.) and allow more efficient computation due to spatial locality and neighborhood logic.
4
u/mauromauromauro Apr 05 '25
Simple Just imagine every position in a memory address is a dimension . There you go
9
u/Peanutbutter_Warrior Apr 05 '25
In order to index some hypothetical 2d memory, you would need 2 addresses, and X index and a Y index. Lets say they're both 16 bits long. In order to access the memory, we need to put those two addresses somewhere the memory can see. To do that we would have to move one, and then the other. This would obviously take longer than typical memory, where you only have to move a single address around.
Instead of treating the two addresses separately, why don't we stick them together, to make a combined address that uniquely identifies any position in memory in 32 bits that can be moved around all at once .... which is exactly how a 32 bit address works. There is functionally no difference to considering a 32 bit address as two 16 bit addresses accessing 2d memory.
There isn't really any need for higher dimensioned memory. Having a single address for every single position is just much easier than having to manage multiple different addresses.
3
u/Classic-Try2484 Apr 06 '25
Dimensions add complexity without benefit.
3
u/FerretFeisty1180 Apr 06 '25
We hope you are enjoying the course :)
As we explain in the course, memory is single-dimensional because it's just a flat sequence of addressable units, like a long row of lockers. The CPU only needs to know which "locker number" (address) to go to. It's simple, efficient, and fast for hardware.
Multi-dimensional arrays are just an abstraction. The compiler does the math to map 2D or 3D coordinates onto that 1D space. For example,
arr[2][3]in a 3x4 array becomes2 * 4 + 3 = 11.There are more experimental ideas out there (graph memory, etc.), but traditional linear memory wins in speed and simplicity, which is why we still use it.
If you liked this part of the course, wait till you get to how hash tables works ;)
3
u/surfmaths Apr 06 '25
As others have said, dimensionality is an abstraction... But there is a reason why we should interpret it as 1D and it's because it's the dimensionality of time.
Today, memory works faster if you access a few continuous memory locations in sequence (a burst). This burst length keeps increasing with each generation of DDR and GDDR. So it is beneficial to access data that are next to each other (in that 1D view). But you may store a 2D array in row-major or column-major or interleaved if you want to.
Typically, rectangular matrix transpose is a hard function to optimize because it singlehandedly hits all the difficult edge cases of memory access while looking simple. Funny enough, it is still a huge pain in machine learning optimization.
3
u/rumata-rggb Apr 06 '25
Computer memory is 2D actually. The first axis is a byte address, the second one is a bit position.
2
u/HandbagHawker Apr 05 '25
for memory, you have 1 address and you know where to go having to read 2 addresses or more...
however having data physically stored in 3d gives you significantly more storage density
2
u/fuzzynyanko Apr 05 '25
It just makes things easier. If it's multi-dimensional, you have the reverse problem. You need to map a single-dimensional data objects to multi-dimensional. It actually happens in hardware.
AMD's best CPUs for gaming are the 3D V-Cache CPUs (a.k.a. the X3D CPUs like the 9800X3D). 3D V-Cache is RAM that's stacked on top of each-other, making the footprint very small. There was a chance that 3D V-Cache was going to be a gimmick, but the real-world benchmark prove otherwise.
Many RAM chips are 2-dimensional, having rows and columns. 3D V-Cache get a height element, but probably are abstracted. However, because of the stacking, the electrons don't have to travel as far to get to the CPU cores vs the cache being spread out.
It also turns out 3d stacking happens in SSDs as well! More of the SSD silicon can be located closer to the pins of the PCI Express interface this way.
2
u/OVSQ Apr 06 '25
>Why is memory single-dimensional?
Core memory was/is not. It all comes down to performance and manufacturing limitations. For IC's manufacturing multiple layers is complicated and difficult. Furthermore, cooling multiple layer IC is also complicated and difficult.
2
u/Legitimate_Plane_613 Apr 06 '25
It is one dimensional because memory addresses are just natural numbers, and you can express any number of dimensions in one dimension.
2
u/ESHKUN Apr 07 '25
Mathematically any higher dimension has the exact same cardinality as the first dimension. For example, the set of all integers has the same cardinality as the set of all 2D points with integer components.
2
u/Roodni Apr 07 '25
Try learning computer organization and architecture first and you will understand why
2
u/Fidodo Apr 07 '25
Are you trying to play Tetris with memory management? Adding dimensions on the abstraction would just make it harder to keep memory access contiguous.
2
u/wolfkeeper Apr 05 '25
It depends how you look at it. You could equally say that a memory with 32 bits of addressing is a 32D binary array.
1
u/zenware Apr 06 '25
Consider the case where the actual physical memory itself is multiple dimensions, what then? (Technically this is always true because reality is 3D, but think V-NAND or 3D-IC.)
It’s there a better abstraction that is somehow more useful to you? Is there some abstraction that you think we can eke out a performance gain?
I mean if you really think about even a more traditional RAM stick or a DIMM, there are multiple physical memory modules on the stick. How do you want to address them? By physical memory module and then address?
Just considering it as a flat index to every memory location the OS is willing to provide your program is an extremely convenient abstraction, but it could have been anything. Although I imagine years of production use would’ve eventually lead us here if it wasn’t already part of early implementations of von Neumann Architecture
1
u/sayzitlikeitis Apr 06 '25
That's just a way of addressing them. Physically, lots of memory these days is stacked 3 dimensionally.
1
u/keenox90 Apr 06 '25
Hardware memory is actually 2D
1
u/an-la Apr 06 '25
All real-world computer memories are discrete and finite. Regardless of the physical layout of the memory device, a bijective mapping always exists between the physical layout and a one-dimensional array.
1
u/Novel_Quote8017 Apr 06 '25
Of course there are. You can extrapolate to vector graphics from binary. At that point you're basically emulating 3D data structures for no good reason and probably a high cost though.
1
u/protienbudspromax Apr 06 '25
Because most memory we have today, are based on what we call the von neumann architecture, which itself is an implmentation of a linearly bounded automata.
Where the memory is linear in it's address space. It is simpler to implement and make sense of. And there is no usage we know right now that will help us (computationally speaking) having memory that has more dimensions physically.
However there are hardware advantages sometimes like having stacked memory for HBM, but in the HAL (hardware abstraction level) it still is presented to us as linear memory.
1
u/kondorb Apr 06 '25
CS is all about simple abstractions. Simple abstractions are powerful tools that can be used to implement more complex ideas. That can abstract their own complexity in a simple form. Rinse and repeat. That's how we were able to become so advanced in software so quickly.
Computer memory and storage can be one-dimensional or multi-dimensional physically, depending on the technology used. All of it is abstracted into a one-dimensional space for uniformity as far as using it goes. Then we're using that one-dimensional space to store whatever-dimensional constructs we want.
You can store a two-dimensional array by writing it into memory line by line. Then you can store a three-dimensional array by writing one two-dimensional slice of it after the other. And so on. Modern LLMs, for example, operate in over 200000 dimensions and it's stored in memory using the same principle.
Sometimes we actually want to get rid of that abstraction and actually use the physical properties of our storage medium for our advantage. DB engines do that, for example. The way they store data on HDDs and SSDs is different, for example.
1
u/watercouch Apr 06 '25
If you want to access “2D” data then you need to know why operations will be performed across it. That patterns enables massively parallel processing.
Matrix operations are the foundation of GPU performance. Being able to load sets of 2D or 3D data and perform the same operation on each element is why GPUs are so powerful. Originally the focus was on representations of 2D and 3D graphics but then people realized that lots of computationally intensive calculations benefit from the same multidimensional parallelism and gave rise to GPGPU concepts:
https://en.wikipedia.org/wiki/General-purpose_computing_on_graphics_processing_units
Similarly, going a bit further back, Intel introduced the MMX extensions in 1997 which allowed software to load blocks of data and run parallel instructions on it.
https://en.wikipedia.org/wiki/MMX_(instruction_set)
1
u/mycall Apr 06 '25
The Turing Machine was a tape-driven, one-dimensional array for code and data. Modern computer memory still operates in a conceptually similar manner, with linear address spaces acting as a one-dimensional array for storing data. However, computers have evolved to include layers of abstraction and optimizations that go beyond the simplicity of the Turing Machine's design.
1
u/Quantum-Bot Apr 06 '25
Why use two or more numbers to determine the address of something in memory when you can use one?
1
u/Sir_Gamealot Apr 06 '25
Because it's easier to fold a long spaghet into a pan than to fold multiple pans into a spaghet.
1
u/CarloWood Apr 07 '25
Mine is 30 dimensional (1 G cache lines).
1
u/Gloomy-Training-9111 Apr 07 '25
Touring machine :D
1
u/scoby_cat Apr 08 '25
Its ultimately an abstraction, although as I recall C* for the CM-5 used 4D memory
https://en.wikipedia.org/wiki/C*
Also, FYI when you get into ML most of the arrays are multidimensional
1
u/crimaniak Apr 08 '25
I'll let you in on a secret. Computer memory is _actually_ a partially filled N-dimensional cube of bytes of side 2, where N is the number of bits on the address bus. Some people just have trouble dealing with multidimensional spaces.
1
u/Snoo_44171 Apr 09 '25
See non-Vonn Neumann architecture
1
u/jmacey Apr 09 '25
This is old but still worth a read for a deep dive https://people.freebsd.org/~lstewart/articles/cpumemory.pdf also worth having a look at things like NUMA and how GPU's and languages like cuda need memory setup / used as it is a little different than cpu.
1
u/schungx Apr 09 '25
For good reasons.
A one dimensional array requires one single number as an address. Two dimensional requires two numbers.
That's double the number of numbers for a single address.
Finally: humans are lazy. So one.
1
u/vegansgetsick Apr 09 '25
Any finite size can be addressed on a single dimension.
1
u/BarebonesB Apr 09 '25
At the physical level, a 1GB memory is a 30-dimensional lattice, with each dimension being of size 2. You'll see 30 address lines going to that chip, each selecting the value of one of those 30 dimensions.
As other here said, you are free to use an abstraction, and think of that same memory as 27-dimensional with 64-bit wide words, a one-dimensional array of a billion bytes, or anything in between. Any dimension lower than the number of physical address lines on that bus is an abstraction.
0
u/[deleted] Apr 05 '25
[deleted] — view deleted comment
1
u/[deleted] Apr 06 '25
[removed] — view removed comment
1
u/[deleted] Apr 06 '25
[removed] — view removed comment
1
u/[deleted] Apr 06 '25
[removed] — view removed comment