RFR: 8337217: Port VirtualMemoryTracker to use VMATree

[Afshin Zafari]

On Tue, 6 Aug 2024 07:12:13 GMT, Johan Sjölen <jsjolen at openjdk.org> wrote:

>> 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.

The big O is a _notation_ and is not a math function. So `O(a * b)` is not always same as `O(a) * O(b)`.
Stick to this _definition_: "when an algorithm has time-complexity of O(`g(n)`), it means if the input grows `n` times the time of executing the algorithm grows `g(n)` times." Where `g()` is `log()` in our case.
IOW, the big O answers the following question:
$t_1$ = time for running `f()` for $n_1$ items
$t_2$ = time for running `f()` for $n_2$ items
if we know $\Large{\frac{n_2}{n_1} = n}$ what is expected value of $t_2$?

A detailed description can be found [here](https://en.wikipedia.org/wiki/Big_O_notation).

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

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