2
\$\begingroup\$

Java's largest array length is 2^31 – 8 = 2,147,483,639, which is an int consisting of 32-bits. In the case where we want to store more elements, we are better off creating multiple 1-D arrays or use a 2-D array which is an array of arrays.

A program is coded to accept a length (typically larger than 2^31 – 8) to create a 2-D array with the appropriate number of cells. It has the methods get(long index) and set(long index, byte value) to get and set a specific index, respectively. Here, the type long is used which is a 64-bit whole number.

  • Given the number of elements as size, create the correct number of 1-D arrays containing exactly size number of cells in total
  • Given some element at index, find the appropriate 1-D array containing that element as well as find it in that array
  • Since we are creating arrays taking Gigabytes of RAM, the type byte, which is an 8-bit number, is used
  • For testing, the sequence 0, 1, ..., 126, 127, 0, 1, ... is stored in the large array
    • A for loop is then executed to loop through each cell and ensure the sequence follows though
    • The program has been tested for days without encountering any bugs

There are two tests:

  • The first to ensure the lengths of the 1-D arrays are created correctly
    • The data structure used is a 1-D where each cell represent the length of that 1-D array at the ith index
    • This will eliminate the need of Terabytes of RAM
  • The second is a complete implementation where the get and set methods are implemented properly but requires multiple Gigabytes of RAM to run

The request: Are there any bugs that have not been taken care of? Are there any improvements that can be applied?

Edit 1: Some wonder what is the purpose of this. This is not a coding question but an implementation to improve upon an M.Sc. thesis implementation that deals with finding the minimum distance of a Linear Codes, an NP-Hard type of a problem. Essentially, a large number (2^40 or more) of vectors, represented as longs, is required to be stored inside of some data structure to perform operations on. Such problems use hundreds of Gigabytes and are executed on servers. The idea of using compression algorithms and writing to disk are not practical options they consume extra unneeded time (at least in my case). fastutil implemented something like this via BigArrays but the implementation here is tailored to a specific case to maximize the performance and is not based fastutil's implementation.

import java.util.Arrays;

/**
 * Uses a 1-D array where each cell stores the number of elements that needs
 * to be stored there.
 */
public class SimpleTest {
    /**
     * The structure used to store the data.
     */
    private int[] array;

    /**
     * The amount of cells that are excluded from an array because VMs reserve
     * some header words in an array which reduces the <em>true</em> maximum
     * value. It could be at least 8 but 16 is used for extra precaution.
     */
    private static byte offset = 16;

    /**
     * The number of cells in the array.
     */
    private long size;

    /**
     * The number of 1-D arrays required.
     */
    private int segments;

    /**
     * The maximum size of each 1-D array.
     */
    private static int maxSegmentLength = Integer.MAX_VALUE - offset;

    /**
     * The size of last segment which is between {@code 1} and {@code
     * maxSegmentLength} (both inclusive).
     */
    private int ancillarySegmentLength;

    public SimpleTest(long size) {
        if (size <= 0) {
            throw new RuntimeException("Size cannot be less than 1");
        }
        this.size = size;

        //number of 1-D arrays with full capacity
        segments = (int) (size / (maxSegmentLength));//can be zero or larger

        //number of cells in the last 1-D array
        //or there will be only a single 1-D array if size < maxSegmentLength
        if ((int) (size % (maxSegmentLength)) != 0) {
            segments++;
            ancillarySegmentLength = (int) (size % (maxSegmentLength));
        } else {//Last 1-D array is full (all 1-D arrays are perfectly full)
            ancillarySegmentLength = maxSegmentLength;
        }
        array = new int[segments];

        if (segments == 1) {//a single 1-D array required
            array[0] = (int) size;
        } else {//
            for (int i = 0; i < segments - 1; i++) {
                array[i] = maxSegmentLength;
            }
            if (ancillarySegmentLength != 0) {
                array[segments - 1] = ancillarySegmentLength;
            }
        }

        System.out.println("==========");
        System.out.println("Size: " + size);
        System.out.println("Total Arrays needed: " + segments);
        System.out.println("Size of last array: " + ancillarySegmentLength);
        System.out.println("==========");
    }

    public String toString() {
        return Arrays.toString(array);
    }

    public static long power(long x, long n) {
        long result = 1;
        for (byte i = 0; i < n; i++) {
            result = result * x;
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println("Running CompleteTest...");
        //extra is a value between 0 and maxSegmentLength, including both
        long extra = (long) (Math.random() * (maxSegmentLength + 1));
        long size = maxSegmentLength * 1L + extra;//
        SimpleTest data = new SimpleTest(size);
        System.out.println("Printing the array: ");
        System.out.println(data);
        System.out.println("Run completed.");
    }
}

/**
 * A data structure for storing a large 1-D array into smaller 1-D array
 * stored inside a 2-D array.
 */
public class CompleteTest {
    /**
     * The structure used to store the codewords of the code.
     */
    public byte[][] array;

    /**
     * The amount of cells that are excluded from an array because VMs reserve
     * some header words in an array which reduces the <em>true</em> maximum
     * value. It could be at least 8 but 16 is used for extra precaution.
     */
    private static byte offset = 16;

    /**
     * The number of cells in the array.
     */
    private long size;

    /**
     * The number of 1-D arrays required.
     */
    private int segments;

    /**
     * The maximum size of each 1-D array.
     */
    private static int maxSegmentLength = Integer.MAX_VALUE - offset;

    /**
     * The size of last segment which is between {@code 1} and {@code
     * maxSegmentLength} (both inclusive).
     */
    private int ancillarySegmentLength;

    public CompleteTest(long size) {
        //assume size >= 1
        this.size = size;

        //number of 1-D arrays with full capacity
        segments = (int) (size / (maxSegmentLength));//can be zero or larger

        //number of cells in the last 1-D array
        //or there will be only a single 1-D array if size < maxSegmentLength
        if ((int) (size % (maxSegmentLength)) != 0) {
            segments++;
            ancillarySegmentLength = (int) (size % (maxSegmentLength));
        } else {//Last 1-D array is full (all 1-D arrays are perfectly full)
            ancillarySegmentLength = maxSegmentLength;
        }

        array = new byte[segments][];
        //The last segment: if ancillarySegmentLength is 0, it's the same
        //as the other segments. Otherwise, allocate ancillarySegmentLength
        //cells where ancillarySegmentLength < maxSegmentLength
        if (ancillarySegmentLength == 0) {
            array[segments - 1] = new byte[maxSegmentLength];
        } else {
            array[segments - 1] = new byte[ancillarySegmentLength];
        }

        if (segments == 1) {//a single 1-D array required
            array[0] = new byte[(int) size];
        } else {
            //populate all the segments except the last one
            for (int i = 0; i < segments - 1; i++) {
                array[i] = new byte[maxSegmentLength];
            }
            //populate the last 1-D array
            if (ancillarySegmentLength != 0) {
                array[segments - 1] = new byte[ancillarySegmentLength];
            }
        }
    }

    /**
     * Returns a specific element in the combination array.
     *
     * @param index the index of the element
     * @return the element in the index specified
     */
    public long get(long index) {
        int s = (int) (index / maxSegmentLength);
        int i = (int) (index % maxSegmentLength);
        return array[s][i];
    }

    /**
     * Sets the value specified at the appropriate index.
     *
     * @param index the index of the element to set
     * @param value the value to be assigned to
     */
    public void set(long index, byte value) {
        int s = (int) (index / (long) maxSegmentLength);
        int i = (int) (index % maxSegmentLength);
        array[s][i] = value;
    }

    /**
     * Returns the number of elements.
     *
     * @return the number of elements
     */
    public long length() {
        return size;
    }

    /**
     * Checks if the value specified is exists in the combination array.
     *
     * @param value the value to look for
     * @return {@code true} if the value exists, {@code false} otherwise
     */
    public boolean contains(long value) {
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[i].length; j++) {
                if (array[i][j] == value) return true;
            }
        }
        return false;
    }

    /**
     * Prints the elements in the combination array on screen. The values
     * will be printed in base 10.
     */
    public void print() {
        long counter = 0;
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[i].length; j++) {
                System.out.format("(%d, %d) = %d \n", i, j, get(counter));
                counter++;
            }
            System.out.println();
        }
    }

    /**
     * Executes the program.
     *
     * @param args the arguments specified but will be ignored
     */
    public static void main(String[] args) {
        System.out.println("Running CompleteTest...");
        //extra is a value between 0 and maxSegmentLength, including both
        long extra = (long) (Math.random() * (maxSegmentLength + 1));
        long size = maxSegmentLength * 1L + extra;//
        CompleteTest array = new CompleteTest(size);
        System.out.println("Size: " + array.size);
        for (int i = 0; i < array.array.length; i++) {
            System.out.println(array.array[i].length);
        }
        //store the sequence 0, 1, ..., 126, 127, 0, 1, ... in the array
        for (long i = 0; i < size; i++) {
            array.set(i, (byte) (i % 128));
        }

        //check each cell to ensure the above sequence is present
        for (long i = 0; i < size; i++) {
            if (array.get(i) != (byte) (i % 128)) {
                System.out.println(
                        "i = " + i + ", " +
                                "value stored = " + array.get(i) + ", " +
                                "correct value = " + (byte) (i % 128)
                );
            }
        }
        //array.print();
        System.out.println("Run completed.");
    }
}
\$\endgroup\$
4
  • 3
    \$\begingroup\$ Why was this code written? Is it an interview question or home work? The description doesn't make a lot of sense and I'm thinking something is getting lost in translation... \$\endgroup\$ Apr 12 at 4:26
  • \$\begingroup\$ @TorbenPutkonen: Thank you for the feedback. Please see the edit. \$\endgroup\$ Apr 12 at 10:04
  • \$\begingroup\$ What version of Java is allowed? JDK 18 has MemorySegment which doesn't have the limits of arrays. Perhaps it offers a much simpler implementation. openjdk.java.net/jeps/419 docs.oracle.com/en/java/javase/18/docs/api/… \$\endgroup\$
    – swpalmer
    Apr 12 at 19:31
  • \$\begingroup\$ @swpalmer Thank you for this, I didn't know it existed. I am currently using Java 8. \$\endgroup\$ Apr 12 at 19:40

1 Answer 1

3
\$\begingroup\$

Since the first class seems to be a proof of concept for the array partitioning and the point of the code is to remove every unnecessary piece of the code in order to maximize performance, I will only point out the issues in the coding style of the latter class. I do not even think about reusability here.

Why make a proof of concept using bytes if your implementation will use long values? When you switch to long values, the memory allocations grow eight fold unless you change the segment size. The fastutil you mentioned deliberately tries to keep the memory allocations themselves below 2^31 and they align the allocation sizes to 2^X. Have you made sure your deviation from their example produces a performance gain?

The offset variable should be a constant. And since it doesn't describe any offset that is meaningful to your code, you should name it private static final int JVM_OVERHEAD = 16; or something similar. In my opinion "this should be a big enough safeguard" never is in the long run, but I suppose your code will not be used as a generic library so I'll let it slide.

The ancillarySegmentLengt variable is redundant. It is not used in the code and it can be calculated from size and maxSegmentLength should you ever need it.

The last segment isn't really ancillary data, it's just the last segment. Even though it's purpose can be easily figured out, calling it ancillary just adds unnecessary cognitive load.

The maxSegmentLength should be a constant.

As long as you calculate the number of segments correctly, the whole segment allocation can be boiled down to this:

long sizeLeft = size;
for (int i = 0; i < array.length; i++) {
    array[i] = new byte[(int) Math.min(MAX_SEGMENT_LENGTH, sizeLeft)];
    sizeLeft -= MAX_SEGMENT_LEFT;
}

Make the get and set methods final. That way you give the compiler the best start to optimizing the code. While at it, you should make every field, parameter and variable final, unless you really intend to change them during their lifetime. As said, it helps the compiler and it also helps the reader when following your code.

You cast maxSegmentLength to long in set but not in get. Inconsistency creates confusion.

\$\endgroup\$
1
  • \$\begingroup\$ Thank you for all of the time you have put! I do appreciate it! For the allocation size, I chose 2^31 - 16 because it made sense to me to fill an array up to its maximum. I don't think there is a performance gain but I didn't test this. My objective is to ensure correctness first rather than optimization. You are correct, this isn't a generic library. I also agree that the last segment isn't 'ancillary' but might be of different size. The sentence "As long as you calculate the number of segments correctly" is what I am afraid of. Have I done it correctly? Thank you for the modified loop. \$\endgroup\$ Apr 12 at 19:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.