1
\$\begingroup\$

I'm trying to improve performance for a generic function that turns a string into a multidimensional array.

Expected input:

  • A string that was generated by the function Arrays.deepToString().
  • The original array had no null values and did not contain arrays of length 0.
  • The array can have any number of dimensions from 1 to 200.
  • Sub-arrays may have different length (e.g. arr[0].length != arr[1].length)

The function converts the values into the requested data type, which may be any primitive variable or String.

private static String[] arraySeparators;
private static Class[] arrayTypes;

public static <T> Object reverseDeepToString(String str, Class<T> dataType){
    int dimensions = 0;
    while(str.charAt(dimensions) == '[')
        dimensions++;

    arraySeparators = new String[dimensions + 1];
    String separator = ", ";
    for(int x = 2; x <= dimensions; x++)
        arraySeparators[x] = separator = ']' + separator + "\\[";

    arrayTypes = new Class[dimensions + 1];
    Class temp = arrayTypes[2] = Array.newInstance(dataType, 0).getClass();
    for(int x = 3; x <= dimensions; x++)
        arrayTypes[x] = temp = Array.newInstance(temp, 0).getClass();

    str = str.substring(dimensions, str.length() - dimensions);
    Object r = createArrayRecursive(str, dimensions, dataType);

    arraySeparators = null;
    arrayTypes = null;
    return r;
}

private static <T> Object createArrayRecursive(String str, int dimension, Class<T> dataType){

    if(dimension == 1){
        String[] s = str.split(", ");
        Object result = Array.newInstance(dataType, s.length);
        for(int x = 0; x < s.length; x++){
            if(dataType == String.class) Array.set(result, x, s[x]);
            else if(dataType == int.class) Array.set(result, x, Integer.parseInt(s[x]));
            else if(dataType == double.class) Array.set(result, x, Double.parseDouble(s[x]));
            else if(dataType == float.class) Array.set(result, x, Float.parseFloat(s[x]));
            else if(dataType == long.class) Array.set(result, x, Long.parseLong(s[x]));
            else if(dataType == boolean.class) Array.set(result, x, Boolean.parseBoolean(s[x]));
            else if(dataType == short.class) Array.set(result, x, Short.parseShort(s[x]));
            else if(dataType == byte.class) Array.set(result, x, Byte.parseByte(s[x]));
            else if(dataType == char.class) Array.set(result, x, s[x].charAt(0));
        }
        return result;
    }
    String[] s = str.split(arraySeparators[dimension]);
    Object arr = Array.newInstance(arrayTypes[dimension], s.length);

    for(int x = 0; x < s.length; x++)
        Array.set(arr, x, createArrayRecursive(s[x], dimension - 1, dataType));

    return arr;
}

The problem is that these workarounds to deal with limitations of generic types are slowing down the function significantly compared to the non-generic equivalent:

private static String[] arraySeparators;

public static Object reverseDeepToString(String str){
    int dimensions = 0;
    while(str.charAt(dimensions) == '[')
        dimensions++;
    arraySeparators = new String[dimensions + 1];
    String separator = ", ";
    for(int x = 2; x <= dimensions; x++)
        arraySeparators[x] = separator = ']' + separator + "\\[";
    str = str.substring(dimensions, str.length() - dimensions);
    return createArrayRecursive(str, dimensions);
}

private static Object createArrayRecursive(String str, int dimension){

    if(dimension == 1){
        String[] s = str.split(", ");
        double[] result = new double[s.length];
        for(int x = 0; x < s.length; x++)
            result[x] = Double.parseDouble(s[x]);
        return result;
    }
    String[] s = str.split(arraySeparators[dimension]);
    int[] lengths = new int[dimension];
    lengths[0] = s.length;
    Object arr = Array.newInstance(double.class, lengths);

    for(int x = 0; x < s.length; x++)
        Array.set(arr, x, createArrayRecursive(s[x], dimension - 1));

    return arr;
}

My question is: is there a way to make a generic function as efficient as a non-generic function, or at least get very close to it?

The only alternative I have in mind is creating lots of copies of the non-generic function (one for each variable type), and have a main function choosing which non-generic function to use, but that will be a very long and ugly code that I try to avoid:

public static <T> Object reverseDeepToString(String str, Class<T> dataType){

    if(dataType == int.class) return reverseDeepToString_int(str);
    if(dataType == double.class) return reverseDeepToString_double(str);
    if(dataType == long.class) return reverseDeepToString_long(str);
    if(dataType == String.class) return reverseDeepToString_string(str);
    if(dataType == boolean.class) return reverseDeepToString_boolean(str);
    ...
}
Improve this question
\$\endgroup\$
0

2 Answers 2

Reset to default
2
\$\begingroup\$

The only option to have this really fast is to use primitive types, which in turn requires to write "non-generic" (specialised for every primitive type) function (piece of code) for every primitive type that you would like to use. By "non-generic" here I mean code that use specialised types only, without promotion. There is no other option. Conversion from primitives to Object just take time, you can save it using non-generic function.

Array.set() is generic because it takes Object as an input, thats why it promotes every primitive to Object.

Improve this answer
\$\endgroup\$
11
  • \$\begingroup\$ Casting takes a negligible amount of time even when repeated billions of times, so it doesn't matter for the optimization. \$\endgroup\$
    – potato
    Oct 16, 2018 at 3:12
  • 1
    \$\begingroup\$ Where do i said that it is the cast that causes the performance degradation? I said that conversion from primitives to Object is the source of the performance degradation, not the cast itself, do you know the difference between plain cast and promotion? \$\endgroup\$
    – Krzysztof Cichocki
    Oct 16, 2018 at 9:19
  • \$\begingroup\$ Adding to my answer, the if else chain executed for every set op takes time, you can optimize it either using a lamda in java >=8 or non-generic function for java <8 \$\endgroup\$
    – Krzysztof Cichocki
    Oct 16, 2018 at 9:28
  • \$\begingroup\$ Sorry, I used the wrong word. Anyway converting primitive types to Object has a negligible effect on performance. The function Array.set() itself was causing the biggest overhead. \$\endgroup\$
    – potato
    Oct 16, 2018 at 10:19
  • \$\begingroup\$ I think that you misattribute this performance degradation to Array.set() due to test flaw, please show the testing code and test results instead of bare words. \$\endgroup\$
    – Krzysztof Cichocki
    Oct 16, 2018 at 11:16
0
\$\begingroup\$ 
if(dataType == double.class) Array.set(result, x, Double.parseDouble(s[x]));

Using Array.set() in the line above was a mistake because it is boxing the primitive types. Using Array.setInt(), Array.setDouble(), etc improved the performance a lot, but it's still a bit slower than using a non-generic function:

if(dataType == double.class) Array.setDouble(result, x, Double.parseDouble(s[x]));

The performance can be improved further by casting the array to the needed type:

if(dataType == double.class) ((double[])result)[x] = Double.parseDouble(s[x]);

Performance test code and results: https://pastebin.com/3g37vDm4

Improved function:

private static String[] arraySeparators;
private static Class[] arrayTypes;

public static <T> Object reverseDeepToString(String str, Class<T> dataType){
    int dimensions = 0;
    while(str.charAt(dimensions) == '[')
        dimensions++;

    arraySeparators = new String[dimensions + 1];
    String separator = ", ";
    for(int x = 2; x <= dimensions; x++)
        arraySeparators[x] = separator = ']' + separator + "\\[";

    arrayTypes = new Class[dimensions + 1];
    Class temp = arrayTypes[1] = dataType;
    for(int x = 2; x <= dimensions; x++)
        arrayTypes[x] = temp = Array.newInstance(temp, 0).getClass();

    str = str.substring(dimensions, str.length() - dimensions);
    Object r = createArrayRecursive(str, dimensions);

    arraySeparators = null;
    arrayTypes = null;
    return r;
}

private static Object createArrayRecursive(String str, int dimension){

    if(dimension == 1){
        String[] s = str.split(", ");
        Class dataType = arrayTypes[1];
        Object result = Array.newInstance(dataType, s.length);
        for(int x = 0; x < s.length; x++){
            if(dataType == String.class) ((String[])result)[x] = s[x];
            else if(dataType == int.class) ((int[])result)[x] = Integer.parseInt(s[x]);
            else if(dataType == double.class) ((double[])result)[x] = Double.parseDouble(s[x]);
            else if(dataType == float.class) ((float[])result)[x] = Float.parseFloat(s[x]);
            else if(dataType == long.class) ((long[])result)[x] = Long.parseLong(s[x]);
            else if(dataType == boolean.class) ((boolean[])result)[x] = Boolean.parseBoolean(s[x]);
            else if(dataType == short.class) ((short[])result)[x] = Short.parseShort(s[x]);
            else if(dataType == byte.class) ((byte[])result)[x] = Byte.parseByte(s[x]);
            else if(dataType == char.class) ((char[])result)[x] = s[x].charAt(0);
        }
        return result;
    }
    String[] s = str.split(arraySeparators[dimension]);
    Object arr = Array.newInstance(arrayTypes[dimension], s.length);

    dimension--;
    for(int x = 0; x < s.length; x++)
        Array.set(arr, x, createArrayRecursive(s[x], dimension));

    return arr;
}

To make the performance perfectly match the non-generic function I can also avoid the casting, but this results in a longer and uglier code for a rather small difference in performance:

private static String[] arraySeparators;
private static Class[] arrayTypes;

public static <T> Object reverseDeepToString(String str, Class<T> dataType){
    int dimensions = 0;
    while(str.charAt(dimensions) == '[')
        dimensions++;

    arraySeparators = new String[dimensions + 1];
    String separator = ", ";
    for(int x = 2; x <= dimensions; x++)
        arraySeparators[x] = separator = ']' + separator + "\\[";

    arrayTypes = new Class[dimensions + 1];
    Class temp = arrayTypes[1] = dataType;
    for(int x = 2; x <= dimensions; x++)
        arrayTypes[x] = temp = Array.newInstance(temp, 0).getClass();

    str = str.substring(dimensions, str.length() - dimensions);
    Object r = createArrayRecursive(str, dimensions);

    arraySeparators = null;
    arrayTypes = null;
    return r;
}

private static Object createArrayRecursive(String str, int dimension){

    if(dimension == 1){
        String[] s = str.split(", ");
        Class dataType = arrayTypes[1];

        if(dataType == String.class){
            String[] result = new String[s.length];
            for(int x = 0; x < s.length; x++) result[x] = s[x];
            return result;
        }
        if(dataType == int.class){
            int[] result = new int[s.length];
            for(int x = 0; x < s.length; x++) result[x] = Integer.parseInt(s[x]);
            return result;
        }
        if(dataType == double.class){
            double[] result = new double[s.length];
            for(int x = 0; x < s.length; x++) result[x] = Double.parseDouble(s[x]);
            return result;
        }
        if(dataType == float.class){
            float[] result = new float[s.length];
            for(int x = 0; x < s.length; x++) result[x] = Float.parseFloat(s[x]);
            return result;
        }
        if(dataType == long.class){
            long[] result = new long[s.length];
            for(int x = 0; x < s.length; x++) result[x] = Long.parseLong(s[x]);
            return result;
        }
        if(dataType == boolean.class){
            boolean[] result = new boolean[s.length];
            for(int x = 0; x < s.length; x++) result[x] = Boolean.parseBoolean(s[x]);
            return result;
        }
        if(dataType == short.class){
            short[] result = new short[s.length];
            for(int x = 0; x < s.length; x++) result[x] = Short.parseShort(s[x]);
            return result;
        }
        if(dataType == byte.class){
            byte[] result = new byte[s.length];
            for(int x = 0; x < s.length; x++) result[x] = Byte.parseByte(s[x]);
            return result;
        }
        if(dataType == char.class){
            char[] result = new char[s.length];
            for(int x = 0; x < s.length; x++) result[x] = s[x].charAt(0);
            return result;
        }
    }
    String[] s = str.split(arraySeparators[dimension]);
    Object arr = Array.newInstance(arrayTypes[dimension], s.length);

    dimension--;
    for(int x = 0; x < s.length; x++)
        Array.set(arr, x, createArrayRecursive(s[x], dimension));

    return arr;
}
Improve this answer
\$\endgroup\$
11
  • \$\begingroup\$ You check the type and do cast for every set operation, this isn't performance wise. Instead of this if else chain you could just pass to this method an lamda expression that would handle the set operation to proper type. Also doing the cast of array to a specific type you just avoid the promotion of every primitive to Object, which as I said was the source of the significant performance degradation. \$\endgroup\$
    – Krzysztof Cichocki
    Oct 16, 2018 at 9:17
  • \$\begingroup\$ Also my answer already pointed that the source of your performance degardation was the promotion from primitive types to Object. Casting the array to specific primitive type before the set operation just avoids this promition from happening. \$\endgroup\$
    – Krzysztof Cichocki
    Oct 16, 2018 at 9:26
  • \$\begingroup\$ I think that you misattribute this performance degradation to Array.set() due to test flaw, please show the testing code and test results instead of bare words. \$\endgroup\$
    – Krzysztof Cichocki
    Oct 16, 2018 at 11:18
  • \$\begingroup\$ There you go: pastebin.com/JzTJ50Sv I also made a similar test to compare the speed of the whole generic function VS non-generic function, the results indicate that any difference between them is negligible. \$\endgroup\$
    – potato
    Oct 16, 2018 at 14:02
  • \$\begingroup\$ Array.set takes Object, if you put an int there it gets promoted to Integer in every step of for loop. As I thought you do a promotion from int to Integer, this takes time. This is a flaw in your test. You can try to construct an Integer object before the for loop and then put it to the array using array.set(), such a way you will remove the promotion from happening and the results would be more adequate. \$\endgroup\$
    – Krzysztof Cichocki
    Oct 16, 2018 at 15:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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