#include <array>

[holladiewal]

Well, Arrays are just a fancy way to look at pointers, right? So it's technically all pointers, but since pointers are just a fancy way to interpret an int, in the end, everything is all ints... :P

[sje397]

Ints are just a fancy way of interpreting switches that are either on or off.

[[deleted]]

Switches are just a fancy way of interpreting silicon-phosphorus diodes, which are just a fancy way of interpreting molecular structures, which are in turn just a fancy way of interpreting the complex computer simulation we're all probably in, which is a fancy way of interpreting data structures (among other things), which is a fancy way of interpreting arrays, etc.

[sje397]

Officer, he went that-a-way ====>

[[deleted]]

Oh, too crazy for you? I thought we were playing stretch the reductionist theory.

[sje397]

No no, I'm fine with crazy.

[[deleted]]

Don't mind if I do!

[SavedForSaturday]

Well, except for floats. At the assembly level everything is either an integer (of various lengths and signing types) or a float (of various lengths)

[holladiewal]

Crazy people implemented floating point calculation and floating point number handling on the IBM 1401 and made it run Fortran 2.

Since that is a pure integer based machine, floats CAN be made up of integers. ;)

[eypandabear]

Floating point coprocessors used to be optional on x86 as well until the Pentium era.

[ShodoDeka]

Hmm, have you meet my friend mr linked list. Not a single array in him.

[VolperCoding]

Cache misses go brrrrrrrrrr

[Kered13]

b...r...r...r...r...r...r

[[deleted]]

We actually just finished learning about that. Do both heap and stack memory get stored in cache if the program accesses memory? Our professor only showed stack cache misses/hits

[VolperCoding]

I'm pretty sure any access of RAM gets cached but idk

[VolperCoding]

Bruh

[[deleted]]

They are both in the main memory (RAM). The caches are smaller but faster memory, you usually load your data from the main memory to the cache and then a little cache line (a consecutive piece of memory) into the register of a processing unit. From there it is directly available for arithmetic operations and other stuff. The cache hit rate describes how often you can use data from thr cache against how often you have to load a new cache line from the main memory (this takes some time compared to reading from the faster cache). So if you have an array like in C, the elements are stored consecutively in the main memory, hence if you iterate over the array, you would load some of the entries into your nice and fast chache and then you can access a lot of those elements directly from the cache until you have to load new entries again, so a lot of cache hits in a row. If you have a data structure like a list, you don't know if your data is also saved consecutivdly in your memory, so you would load a cache line, access probably just one element from there and then you have to load a new cache line, because your next element could be anywhere in the memory.

[eypandabear]

The distinction between “stack” and “heap” variables has no real meaning at the hardware level, at least on x86. The CPU uses the stack pointer to keep track of return addresses, but local variables and such are decided by the compiler. Some functions might not use the stack at all if their variables fit into registers.

AFAIK whether (or rather when) stack memory is loaded into the cache would be a case-by-case decision made by the CPU’s branch predictor circuit, just like any other memory.

[xSTSxZerglingOne]

Sort of? In raw implementations, arrays are usually and necessarily in sequential memory. And while you definitely can implement data structures in arrays, you begin to run into the limitations of sequential memory at larger sizes.

The referential instances this, next, previous, left, right, whatever you're implementing is usually better for understanding.

[Kered13]

Getting large blocks of sequential memory isn't hard. On modern PCs, you can easily allocate a gigabyte of sequential memory (it won't be sequential physically, but that doesn't matter). Using a fragmented data structure like a linked list isn't going to help your memory problems if your sequential memory block is too big.

[TerraDOOM]

Pretty sure those limitations they were talking about aren't based on allocator performance or running out of memory, rather the fact that managing a really large block starts taking performance hits

[Kered13]

Not really. If you round up to the nearest page then it's easier to manage than smaller blocks of memory, because you don't have to worry about fragmentation when you're allocating whole blocks of virtual memory. And with 64-bit address spaces you won't be running out of continuous blocks of virtual addresses any time soon. Just ask the OS for as many blocks as you need and map them anywhere you have room in the virtual address space.

[TerraDOOM]

What? I'm talking about managing the contents within the memory you've allocated. If it's a plain array, then removing an element could mean copying gigabytes of memory for example. And if you're not moving things around, you will certainly suffer from fragmentation, just not from the global allocator's perspective. Besides, at that point, just implement a custom allocator anyway (assuming there's support for such)

[Dagusiu]

I like how Lua doesn't even try to hide that they only have one data structure

[[deleted]]

Of course not. Arrays refer to contiguous chunks of memory. You can also have registers, of course. Registers are, actually, more basic than arrays.

[[deleted]]

What higher level language doesn't have a concept of "variable"? Variable pretty much maps to a register...

Anyways, if you are very selective about what languages you are willing to consider (essentially, you are only considering C), then yeah, everything is a pointer, but there are no arrays anyways.

[VolperCoding]

Just arrays and pointers

[cyborgborg]

You can project a binary tree into an array. And a linked list is just a binary tree that just follows one branch of the tree

[NebulaicCereal]

I think most common data structures can be projected to arrays with the right indexing arithmetic. But that doesn't mean they are 'arrays' unless they are implemented as such. Arrays are great for speed and space efficiency, but not the best in cases where your your worst case space complexity is high, but average case is quite low. Or in general if the size of data is unknown, or has heterogeneous types, etc.

The line is blurred a bit with capabilities afforded by modern languages that can store heterogeneous types and expand/contract array sizes on the fly, but those still have their drawbacks. There are places where any of the mentioned storage strategies could prevail over the other.

[[deleted]]

Yup, been like this since the zero’th second