0

I have a function that sorts a given array using the merge sort algorithm. That algorithm calls itself to solve the problem.

public class MergeSort {
    
    public static void mergeSort(int[][] arr, int left, int right) {
        // merge two parts
        merge(arr, left, mid, right);
        
        // sort the left part
        mergeSort(arr, left, mid);
        // sort the right part
        mergeSort(arr, mid, right);
    }   
}

Can I reach performance if I encapsulate the arr parameter in the class? Consider:

public class MergeSort {
    int[][] arr;
    
    public void mergeSort(int left, int right) {
        // merge two parts
        merge(left, mid, right);
        
        // sort the left part
        mergeSort(left, mid);
        // sort the right part
        mergeSort(mid, right);
    }
}

So, the arr parameter is not passing to the stack.

Mark Rotteveel
  • 100,966
  • 191
  • 140
  • 197
Arkady
  • 33
  • 7
  • Arrays are - in general - allocated on the heap, not on the stack. The only thing that will be on the stack in your first code is the reference to the array of `arr`, not the array itself. The fact you pass the reference to the array as a parameter might actually be better for performance than using a field. Also, making this a field could introduce all kinds of issues if you don't use instances of `MergeSort` correctly. – Mark Rotteveel Jan 11 '23 at 16:42
  • yes, it will be better than pass it on the stack with every call. – Khanna111 Jan 11 '23 at 16:42
  • @Khanna111 That is unlikely. – Mark Rotteveel Jan 11 '23 at 16:42
  • @MarkRotteveel I see. So if the arr is a local variable defined in the method itself, it would still be in the heap and only a reference would be passed? – Khanna111 Jan 11 '23 at 16:43
  • The array is on the heap, `arr` is just a reference to that array. And although each method invocation may add yet another reference to that same array on the stack, that is trivial (and possibly this might be optimized away). – Mark Rotteveel Jan 11 '23 at 16:45
  • @MarkRotteveel Rotteveel yes, but it is a reference. It takes memory. – Arkady Jan 11 '23 at 16:45
  • @Arkady Those four bytes are nothing, and the locality of the reference on the stack may make it faster than having to access the field of the instance. – Mark Rotteveel Jan 11 '23 at 16:46
  • If you want to be sure though, consider writing a JMH test, see also [How do I write a correct micro-benchmark in Java?](https://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java) – Mark Rotteveel Jan 11 '23 at 16:47
  • @MarkRotteveel then the parameter will be removed from the stack and placed again. But the class field will stand still until the end – Arkady Jan 11 '23 at 16:49
  • Yes, but the method needs to access the field on each use, which is generally more expensive than accessing a local variable on the stack. – Mark Rotteveel Jan 12 '23 at 08:19
  • 2
    Perhaps, you should first *implement an actual working* version of MergeSort, before asking about the performance of a tiny detail, that becomes irrelevant anyway, given how mergesort works. – Holger Jan 12 '23 at 08:56
  • @MarkRotteveel tell me please, how is field accessing implemented. When we are creating an object the field data is initializing to the local stack. What prevents a function from fast accessing a class field as its parameter on the stack? – Arkady Jan 12 '23 at 13:01
  • André LaMothe says in his book that to make calling a function fast, you can use global variables as method parameters. The book is very old. – Arkady Jan 12 '23 at 13:04
  • @Holger it's not about the sorting algorithm. I am trying to understand how can I make function calls faster. – Arkady Jan 12 '23 at 13:08
  • 2
    Well, then you should probably implement *anything* working, before worrying about the performance of the thing with the least impact on the overall performance. If you have something real, you can ask whether there are opportunities to optimize it. – Holger Jan 12 '23 at 14:35

1 Answers1

0

variables reserve a reference to use from ram. It doesn't matter where you define it, if you're using 1 byte of ram it's the same everywhere.

The important thing is that if the developer wants to use this variable in the program, he can use it easily and separate it from other variables.

If you say why parameters are used, it is necessary to understand why functions are used. The simplest functions are to separate the codes you wrote from other codes and to access these codes easily. That's why the parameters exist.

Arafin
  • 37
  • 6