Skip to main content
Share Your Experience: Take the 2024 Developer Survey
42 votes
Accepted

Understanding serialization

If you have a complicated data structure, its representation in memory might ordinarily be scattered throughout memory. (Think of a binary tree, for instance.) In contrast, when you want to write it ...
D.W.'s user avatar
  • 161k
40 votes
Accepted

Why we still need Short Term Memory if Long Term Memory can save temporary data?

There's two simple reasons, one fundamental and one related to our current technology. First the technical one: volatile storage is (generally) faster than non-volatile storage. It has fewer ...
orlp's user avatar
  • 13.6k
30 votes

Understanding serialization

The trouble I have is: aren't all variables (be it primitives like int or composite objects) already represented by a sequence of bytes? (Of course they are, because they are stored in registers, ...
Dai's user avatar
  • 441
21 votes

Why we still need Short Term Memory if Long Term Memory can save temporary data?

@orlp is already discussed speed. There's probably more than could be added (e.g., about latency vs. bandwidth), but let's leave that aside for now. Write Endurance Instead, let's start by considering ...
Jerry Coffin's user avatar
16 votes

What course in CS deals with the study of RAM, CPU, Storage?

The subject you're describing often goes under the names computer architecture, computer systems, computer organization and design, and the like. One example is Elements of computing systems, based on ...
Yuval Filmus's user avatar
16 votes

Understanding serialization

The tricky is actually already described in the word itself: "serialization". The question is basically: how can I represent an arbitrarily complex interconnected cyclic directed graph of arbitrarily ...
Jörg W Mittag's user avatar
13 votes

Understanding serialization

The other answers already address complex object graphs, but it's worth pointing out that serializing primitives is also non-trivial. Using C primitive type names for concreteness, consider: I ...
Useless's user avatar
  • 231
11 votes
Accepted

Why does RAID-5 require an additional disk for parity blocks?

I think you've misunderstood what the parity data is. They're not parity checks, so it's not true that "each parity block is specific to each disc it belongs to." The parity data is to allow recovery ...
David Richerby's user avatar
9 votes

Why we still need Short Term Memory if Long Term Memory can save temporary data?

Others have talked about different technologies, like L1 caches, etc. so I thought I'd give a more theoretical explanation. Memory access time scales with square root of capacity, i.e. random access ...
Warbo's user avatar
  • 622
6 votes

Understanding serialization

In addition to what the other answers have said: Sometimes you want to serialise things that are not pure data. For instance, think of a file handle or a connection to a server. Even though the file ...
Artelius's user avatar
  • 676
6 votes

Understanding serialization

There are multiple aspects: Readability by the same program Your program has stored your data somehow as bytes in the memory. But it might be arbitrarily scattered across different registers, with ...
Frank Hopkins's user avatar
6 votes
Accepted

Could a standardized ternary system be more efficient than the binary system?

Whether this is more efficient depends on the physical properties of the medium, not on any fundamental principle of computer science. And of course there's no reason to limit yourself to ternary ...
D.W.'s user avatar
  • 161k
5 votes

Why did the concept of "write-protecting" not carry over from floppy disks to USB memsticks and especially external USB HDDs?

I'm not entirely sure that this question is on topic, but nonetheless, I suspect it has a simple answer. Physical write protection mechanisms predate floppy disks. At my school holiday job in the ...
Pseudonym's user avatar
  • 22.2k
4 votes
Accepted

Is there a name for "density" of information?

The classical measure of information is the entropy. Entropy measures the information content of a random source. Consider the case of text files: someone has generated some text, and she wants to ...
Yuval Filmus's user avatar
4 votes

Why we still need Short Term Memory if Long Term Memory can save temporary data?

According to Google, the fastest SSD drive in 2020 has a 45 microsecond read access time. RAM access time is about 10 ns, that is 4,500 times faster. A factor of 4,500 is enough to make SSD without ...
gnasher729's user avatar
  • 30.4k
4 votes
Accepted

A data structure for an allocation-free dynamic sample rate buffer

The best name I can think of is derandomized or deterministic reservoir sampling. I don't know of any ready-made implementations.
orlp's user avatar
  • 13.6k
3 votes

time efficient key value store for fast lookup

Make a table with 2^22 entries to lookup the highest 22 bits of the key. Each entry is responsible for one value on average (but may contain up to 1024). Entry #i in the table, which is responsible ...
gnasher729's user avatar
  • 30.4k
3 votes

time efficient key value store for fast lookup

Since the data structure is only created once, you can simply use an array ordered by the key. Each element in the array contains the key-value pair. Sorting the array is ...
BMiner's user avatar
  • 271
3 votes

Understanding serialization

Let's define what a sequence of bytes actually is. A sequence of bytes consists of an non-negative integer called the length and some arbitrary function/correspondence that maps any integer i that is ...
David Grayson's user avatar
3 votes
Accepted

How are the number of bytes less than the number of pixels in an image?

A colour image is typically digitalized using 256 levels for each of the 3 RGB channels. That gives 3 bytes per pixel. The trick to attain smaller file size is to apply some compression, to take ...
leonbloy's user avatar
  • 256
3 votes

Why we still need Short Term Memory if Long Term Memory can save temporary data?

When we talk about speed, we need to distinguish between latency and throughput. Latency is fundamentally restricted by physics; for example DRAM can be accessed in about 10 ns, flash can be accessed ...
Nayuki's user avatar
  • 881
3 votes
Accepted

Using B+Tree to implement index, when the index-key size and the data-block size are of the same order

Note: In what follows, I'm going to use the term "B-tree" to refer to the general idea of B-trees regardless of the variant, and "B+-trees" to refer specifically to B+-trees. You'...
Pseudonym's user avatar
  • 22.2k
3 votes
Accepted

When a CPU copies instructions from storage into RAM how does it jump to instructions no longer in RAM?

You have many memory pages - thousands 20 years ago, possibly millions today. When the next instruction is not in RAM, it is loaded for example from disk. Some other page of memory will be thrown out. ...
gnasher729's user avatar
  • 30.4k
2 votes
Accepted

Most Efficient Way to List All $n$-bit Permutations

Since $n$ is known from the start, you know that there are exactly $2^n!$ possible lists. Calculate the index of your list in a lexical ordering of all permutations, and then write that number using $...
Matt Timmermans's user avatar
2 votes

Understanding serialization

The trouble I have is: aren't all variables (be it primitives like int or composite objects) already represented by a sequence of bytes? Yes, they are. The problem here is the layout of those bytes. ...
Agent_L's user avatar
  • 213
2 votes

Understanding serialization

The intricacies reflect the intricacies of data and objects themselves. These objects can be real world objects, or computer only objects. The answer is in the name. Serialisation is the linear ...
Paul Uszak's user avatar
  • 1,602
2 votes

time efficient key value store for fast lookup

The minimum possible size for such any such data structure is $\log_2{ 2^{32} \choose 4\times 10^6} \approx 4.6\times10^7$ bits, or around 5.5MB. An array of 4 million 32-bit numbers is only 15.25MB. ...
Pseudonym's user avatar
  • 22.2k
2 votes

What is the minimum required storage for a sparse, depth-first octree?

The number of octrees with $n$ nodes is OEIS sequence A007556: $$T(n) = {8n \choose n}/(7n+1)$$ I worked this out, incidentally, by writing a short program to generate the first few values of $T(n)$ ...
Pseudonym's user avatar
  • 22.2k
2 votes
Accepted

How is the data stored in AVL tree in a memory?

If I wanted to be really pedantic, the question would be unanswerable, as it depends on the particular implementation. In most cases, however, the individual nodes of the tree are stored in one ...
John Doe the Righteous's user avatar
2 votes

Is ROM primary memory or secondary memory?

The terms “primary memory” and “secondary memory” are intended to distinguish between memory that is directly accessible from the main processor and memory that isn't. The basic idea is that the ...
Gilles 'SO- stop being evil''s user avatar

Only top scored, non community-wiki answers of a minimum length are eligible