Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

# Tag Info

40

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 to disk, you probably want to have a representation as a (hopefully short) sequence of contiguous bytes. That's what serialization does for you.

27

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, memory, disk, etc.) So what makes serialization such a deep topic? To serialize a variable, can't we just take these bytes in memory, and write them to a file? ...

15

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 complex objects as a linear sequence of bytes? Think about it: a linear sequence is kind-of like a degenerate directed graph where every vertex has exactly ...

13

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 serialize a long. Some time later I de-serialize it, but ... on a different platform, and now long is int64_t rather than the int32_t I stored. So, I need to either ...

12

The general case is indeed a bit complicated. However, in the case of 4 disks you can simplify it a lot; you do not really need to know any fancy math. You only need to know how to store 4 bits redundantly, and then you already know everything; just repeat the same scheme for each group of 4 bits that you need to store. We can represent the scheme as 4 x 4 ...

11

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 from a failed disc. Let's go back to RAID-4 for a second, and assume we have three discs: discs $0$ and  $1$ are data and disc $2$ is parity. "Parity"...

8

Some languages, such as C, support ragged arrays: two-dimensional arrays where the rows have different lengths. That lets you avoid the redundancy of representing a symmetric function in a square array.

8

Short answer: Depends on implementation. Long answer: Ties could be broken randomly, or some fixed direction might be preferred. A popular strategy is to select that position first which does not require the head to change direction (since changing direction could take more time). So suppose that the head has moved from 20 to 25, it might prefer 45 next ...

7

The computation for $Q$ is definitely more difficult than the XOR computation needed for $P$ though it is in one sense the same kind of calculation: a polynomial evaluation. Stripped of the detailed computational techniques described in the link, the idea is to regard the $n$ data bytes/drives $D_0$, $D_1, \ldots, D_{n-1}$ as the coefficients of a ...

7

Sure, you can put all information (of half a table) in a linear array, and use a formula to compute the new position given the original arguments. That formula is quadratic, and you are basically changing space for speed. The best thing to do however is looking for two tables that are symmetric (commutative operations) and of the same size, and share the ...

6

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 pointers going back and forth between its smaller pieces [edit: As commented, physically the data is more likely in main memory than a data register, but that ...

6

I think the term inode is misplaced here. I am unaware of any way in which Inodes have anything to do with optimizations to reduce disk fragmentation. The term inode goes back to Unix Version 1 from 1971. It was not until the Berkeley Fast File System in BSD 4.2 in 1983 that anything significant was done to combat disk fragmentation. In Unix systems the ...

6

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 handle or socket is an int, this number is meaningless the next time the program runs. To properly recreate objects that contain handles to such things, you ...

6

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 systems; we can consider systems with $k$ levels, where $k$ is any integer with $k \ge 2$ (it doesn't have to be limited to $k=2$ or $k=3$). For instance, Wifi ...

5

There are two possible criticisms here, which should actually be leveled at the operating system, more accurately the file system: Why does the OS not superficially erase data when a file is erased? Why does the OS not thoroughly erase data when a file is erased? Regarding point 1, historically speaking, you don't want to do this, since you might change ...

4

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 communicate this text to you. Since you know that the text is in English, there is no need for her to spell out all the words in full; instead, she can replace ...

4

The asymptotic complexity will not change with relation to how the matrices are laid out in memory, but the actual running time of the matrix multiplication will be very dependent upon the memory layout. There are two papers that I know of that go into detail about this, one by McKellar in 1969 and another by Prokop in 1999. Prokop's paper defines the ...

4

No, the complexity remains the same. The main difference between row-major and column-major order is memory access patterns - for example if you iterate by column then row-major order would be jumping around memory, which is bad for CPUs because they cannot read-ahead/cache memory. This is because transferring data from RAM to the CPU on modern processors ...

4

I am guessing that overheads P, S, and T exclude per page/segment overheads and are per-process overheads (if they are per-system overheads, the adjustments are obvious), so the overhead of each process would be P + page_count * 4 bytes for paging, S + segment_count * 8 bytes for segmentation, and T + segment_count * 8 bytes + page_count * 4 bytes for ...

4

I want to expand on the other answers and give a concrete example of the 2-D index map to 1-D index. Let $N = \{0,1,2,3,...\}$. Call our one-to-one map $f \colon N \times N \rightarrow N$. First, let us list out some desirable properties $f$ should have. $f$ is commutative. We want [x][y] and [y][x] to use same position in memory. Small index maps to ...

3

Media is what holds the information, e.g. disk platen, CD, magnetic stripe. Device is what uses the media and provides a physical interface. For devices that have removable media, such as CD/DVD players the distinction is easy. For other devices where the media is an integral part of the device, the distinction is not so easy because the media is not ...

3

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 at least zero and less than length to a byte value (an integer from 0 to 255). Many of the objects you deal with in a typical program are not in that form, ...

3

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 for 0 to 1024 values with keys from 1024i to 1024i + 1023, contains the following: 1. The number of keys in that range. 2. If there are 0 keys, the value of the ...

2

There are two ways to interpret your dataset generating process. The first produces all even numbers between $2$ and your bound: $2$, $4$, $6$, $8$, …; the second produces all powers of $2$ between $2$ and your bound: $2$, $4$, $8$, $16$, … An integer $N$ requires roughly $\log_{256} N$ bytes to store. Therefore, if your bound is $N$, the first ...

2

The three disk raid-6 is trivial: Just store the same information on disk 1, disk 2 and disk 3. Any two disks may fail and you can still recover the data. So a three disk raid-6 is basically just a three disk raid-1. In the four disk case, there are two data "disks" (let's call them $A$ and $B$) and two parity "disks" (let's call them $P$ and $Q$). ...

2

We can calculate 100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000. You can store this in any way you want: as 100!, as the ASCII string ...

2

The data may well still be there, the problem is that there is no (reasonable) way to get an electrical signal into or out of the data cells. When you crack a chip you are cracking wires. The minimum feature size in many chips made these days is around 20nm=200 Angstroms. I suppose that if you (a) had an electron microscope, (b) knew exactly how the ...

2

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 $\lceil log_2(2^n!)\rceil$ bits. In practice, you can come arbitrarily close to this bound using arithmetic encoding, without having to manipulate very large ...

2

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 advantage of the redundacy (neighbouring pixels tend to have similar colours). That depends on the image format. For example, PNG format applies a "lossless" ...

2

3 different voltage levels makes building circuits harder and it is easier for little errors to occur in the signals. Circuits need complex logic instead of the easy boolean logic which works perfectly. Ternary is not compatible with binary that all computers use.

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