Memory Requirements for a Program

Fun Fact: There is contention on the number of bits in a megabyte and gigabyte. Computer Scientists believe that there is $2^{20}$ bytes in a megabyte and $2^{30}$ bytes in a gigabyte, whereas the national institute of standards and technology defines a megabyte as 1 million bytes and a gigabyte as 1 billion bytes.

Typical memory usage for primitive types and arrays (Java)

Primitive Types

type	bytes
boolean	1
byte	1
char	2
int	4
float	4
long	8
double	8
One dimensional arrays

type	bytes
char[]	$2N + 24$
int[]	$4N + 24$
double[]	$8N + 24$
Two dimensional array

type	bytes
char[][]	~$2MN$
int[][]	~$4MN$
double[][]	~$8MN$

Typical memory usage for objects in Java

• Object overhead 16 bytes
• Reference 8 bytes
• Padding 8 bytes Total 32 bytes

Date Object represented by 32 bytes

String Object represented by $2N + 64$ bytes

Summarising Memory Usage

Once we understand the nature of our program and what’s required we calculate our total memory by taking into account.

• Total primitive types and bytes used
• Object references (8 bytes per reference)
• Arrays: 24 Bytes + memory for each array entry
• Objects: 16 Bytes + memory for each instance variable + 8 bytes if inner class (for pointer to enclosing class)
• Padding: round up to multiple of 8 bytes.

Real example

Q. How much memory does our WeightedQuickUnionUF class use asa function of N? (Tilde notation)

public class WeightedQuickUnionUF
  {
    private int[] id;
    private int[] sz;
    private int count;

    public WeightedQuickUnionUF(int N)
    {
      id = new int[N];
      sz = new int[N];
      for (int i = 0; i < N; i++) id[i] = i;
      for (int i = 0; i < N; i++) sz[i] = 1;
    }
  ...
}

My Answer / Working

• Object WeightedQuickUnionUF = 16 bytes
• each private is a reference therefore
  • private int[] id = $8 + 4N + 24$
  • private int[] sz = $8 + 4N + 24$
  • private int count = $8 + 4$
• padding = 4

Largest constant = 8N

Answer = ~8N