How to minimize object size of a large list of strings

Question

Update:

The discussion below was based on a made up example when objects are created in session. C.E. was absolutely right to point out that Mathematica can do the same trick and share objects. However, the question is inspired by reading large datasets from files. In this case, both MemoryInUse and ByteCount will show the same result. Suppose we create a matrix of strings:

m1 = MemoryInUse[];
x=Table["String", {10000}, {100}];
ByteCount@x
MemoryInUse[] - m1

(* 49040080 *)
(* 9042656 *)

Obviously, the trick with memory sharing works. Let's write this to file and read it back.

Export["mat.csv", x, "CSV"];
m1 = MemoryInUse[];
x1 = Import["mat.csv", "CSV"];
MemoryInUse[] - m1
ByteCount@x1
x1===x

(* 49044432 *)
(* 49040080 *)
(* True *)

Apparently, Mathematica is using full space now (and even more for something else??) to store the matrix in memory. Any ideas how to force Mathematica to be less greedy after reading from file?

Original post:

I am trying to figure out the right way to work with large datasets. The problem is a huge memory overhead associated with a list of repeated strings in Mathematica. Specifically, I am comparing the memory management with R and it looks like Mathematica is far more greedy. Example: let's make a vector (or list) of one element which is a string of one character.

R

object.size(rep("1",1)) is 96 bytes

Mathematica

ByteCount@{"1"} is 88 bytes

So we are good here. But let's see what happens when you do 100 elements.

R

object.size(rep("1",100)) is 888 bytes

Mathematica

ByteCount@Table ["1", 100] is 4896 bytes

So we are using lot more memory in Mathematica now. Pushing it to the limits, let's do 1,000,000

R

object.size(rep("1",1e6)) is 8,000,088 bytes

Mathematica

ByteCount@Table ["1", 1*^6] is 48,000,080 bytes

All in all, Mathematica wants about 6 times more memory to store this simple list than R. What happens if we make the string longer? Let's do a 100 character string.

R

object.size(rep(strrep("1",100),1e6)) is 8,000,208 bytes

Mathematica

ByteCount@Table[StringJoin[Table["1", 100]], 1*^6] is 144,000,080 bytes

Now R uses almost the same amount of memory as for the short string, but Mathematica uses an order of magnitude larger. Apparently, R understand that this is a repeating object and simply stores just one instance, while Mathematica stores all of them.

For datasets and list of lists it is very important as usually there is a fixed list of string elements you use (names of categories, states, other features) and they are repeated many times. When importing such data set in R, it explicitly uses factor type, when the list of all instances is stored ones, and then the vector is simply a list of indices in that list. However, even when we are not using factor type in R, we have just seen that it still uses the same logic and stores such vectors much more efficiently.

Can we emulate this in Mathematica? The problem is that of course, I don't want a brute force method when I read all the elements, make a unique list, and then make my own index. This would make dataset convenience go away. I would like to have a solution which works relatively seamlessly when used -- in other words I still have a sort of association or a dataset with multiple columns (some strings, some numbers etc.) that is memory optimized.

Answer 1

The documentation for ByteCount states that

ByteCount does not take account of any sharing of subexpressions. The results it gives assume that every part of the expression is stored separately. ByteCount will therefore often give an overestimate of the amount of memory currently needed to store a particular expression. When you manipulate the expression, however, subexpressions will often stop being shared, and the amount of memory needed will be close to the value returned by ByteCount.

So what you are measuring is what the byte count would be if repetition is not taken into account, but it does not tell you how much memory Mathematica actually allocates. For that we can use a different approach:

Clear[data];
mem = MemoryInUse[];
data = Table["1", 1*^6];
MemoryInUse[] - mem

8002664

Which is almost the same as R's 8,000,208 bytes.

If you explicitly tell Mathematica that this is a list a repeated elements you can save some more memory, but not a lot in this case:

Clear[data];
mem = MemoryInUse[];
data = ConstantArray["1", 1*^6];
MemoryInUse[] - mem

7999080

Answer 2

If the strings are repeated frequently and the order of the data is not critical, store the Tally of the data.

mem = MemoryInUse[];
data = Transpose[{Table["1", 5*^5], Table["2", 5*^5]}] // Flatten;
MemoryInUse[] - mem

(*  8003392  *)

mem = MemoryInUse[];
tally = Tally[data];
MemoryInUse[] - mem

(*  2656  *)

The sorted data can be reconstructed from the Tally

Flatten[Table @@@ tally] === (data // Sort)

(*  True  *)