RFR: 8337217: Port VirtualMemoryTracker to use VMATree

[Johan Sjölen]

On Mon, 5 Aug 2024 17:23:46 GMT, Afshin Zafari <azafari at openjdk.org> wrote:

>> It is considered that `malloc` or other external events are the same for two cases. If we know that there might be some noise for one or another, we should check and disable them. This is the approach I have talked. How can we avoid noise from `malloc` side?
>
> When it is said that an algorithm has the log(n) time-complexity, it means that if the input grows n times, the times grows log(n) times. The tree data-structure has log(n) time-complexity. VMATree may have not exactly log(n) response times due to self-balancing costs. But it is still expected to be less than O(n).

Hi Afshin, could we take a step back and do some asymptotic time complexity analysis of this problem?

The test is measuring the following code:

```c++
for (int i = 0; i < n; i++) {
  int a = (os::random() % n) * 100;
  treap.upsert(a, 0);
}


So this algorithm is the tme complexity which we are trying to understand. First, let's simplify the code slightly:

```c++
auto f = [&](auto n) { int a = (os::random() % n) * 100;  treap.upsert(a, i); };
for (int i = 0; i < n; i++) {
  f(i);
}


Clearly, `f(n)` is executed `n` times, agreed? Then the time complexity of the whole program must be `O(n*f(n))`, correct? It's the time complexity of `f(n)` performed `n` times.

Let's replace `f` with something else to see if we can understand the time complexity of the whole code snippet again.

```c++
int arr[n];
auto f = [&](auto n) { arr[n] = 0; };
for (int i = 0; i < n; i++) {
  f(i);
}


Now, we both agree that assigning to an array has time complexity `O(1)`, correct? Then, if we fill that in in our expression `O(n * f(n))` we receive `O(n * 1) = O(n)`, correct? In other words, the time complexity of the algorithm the test is measuring is *linear*, and we ought to expect that with an array the time taken for the array should be 10x longer with 10k elements as compared to 1k elements.

OK, now let's *assume* that `f(n)` has time complexity `O(log n)`, then shouldn't the algorithm we're measuring have time complexity `O(n * log n)`, that is actually *slower* than `O(n)`.

In conclusion: if `treap.upsert()` has time complexity `O(log n)` then the whole algorithm should have time complexity `O(n * log n)` and the measurements we're seeing are as expected *and the test shouldn't fail*.

Have I missed anything or made any mistakes? Please let me know.

-------------

PR Review Comment: https://git.openjdk.org/jdk/pull/20425#discussion_r1705025716