RFR: 8337217: Port VirtualMemoryTracker to use VMATree

[Afshin Zafari]

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

>> Why would the execution time grow logarithmically when we do linearly more work? When we run this with `N2` we will perform `10_000 * log(10_000, 2)` units of work, and for `N1` we will perform `1_000 * log(1_000, 2)` units of work, approximately. A closer approximation is `O(log(1)) + O(log(2)) + ... + O(log(n))` for `n = N2` or `n = N1`.
>> 
>> Let's calculate that:
>> 
>> 
>>>>> import math
>>>>> def time_it(n):
>> ...     t = 0
>> ...     for i in range(1, n):
>> ...             t  = t + math.log(i)
>> ...     return [t, 3*t] # Approximate best and worst case
>> ... 
>>>>> time_it(1000)
>> [5905.220423209189, 17715.661269627566]
>>>>> time_it(10_000)
>> [82099.71749644217, 246299.15248932652]
>>>>> def compare(a, b):
>> ...     ab, aw = a
>> ...     bb, bw = b
>> ...     return [ bb / ab, bw / aw ]
>> ... 
>>>>> compare(time_it(1000), time_it(10_000))
>> [13.902904821938064, 13.902904821938066]
>>>>> # Ouch, that's outside of our linear bound!
>> 
>> 
>> What I said previously also applies, especially the performance of `malloc` will impact this I suspect.
>
> 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).

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

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