RFR: JDK-8326586: Improve Speed of System.map [v2]

[Gerard Ziemski]

On Tue, 27 Feb 2024 07:25:54 GMT, Thomas Stuefe <stuefe at openjdk.org> wrote:

>> A small optimization that speeds up `jcmd pid System.map` by orders of magnitude by optimizing NMT cache lookup for sequential accesses. This cache is used to map NMT against System information - and the latter usually comes in sequential form, e.g. scanned from `/proc/<pid>/maps` or via VirtualQuery.
>> 
>> On Linux x64, `System.map`for a JVM with an artificially bloated process space (1 million mappings) takes:
>> 
>> before this patch: 6.3 minutes
>> with this patch: 4.2 seconds
>> 
>> which is a 87x speed improvement.
>> 
>> Ping @jdksjolen and @gerard-ziemski?
>
> Thomas Stuefe has updated the pull request incrementally with one additional commit since the last revision:
> 
>   uintx->size_t

BTW here is the truth table I used to convince myself that the code is doing the right thing, might be useful to someone (even myself) looking at this in the future:


range_intersects == MAX(from) < MIN(to)
NEW CODE: break if (to <= range.from)
OLD CODE: break if (from < _range.to)

....{..}.... from,to
[..]........ range
....<....... MAX(from)
...>........ MIN(to)
...><.......  MAX(from) < MIN(to) -> FALSE
.......}.... to
[........... range.from
[......}....  to <= range.from    -> FALSE
....{....... from
...]........ range.to
...]{.......  from < _range.to    -> FALSE

....{..}.... from,to
.[..]....... range
....<....... MAX(from)
....>....... MIN(to)
....X.......  MAX(from) < MIN(to) -> FALSE
.......}.... to
.[.......... range.from
.[.....}....  to <= range.from    -> FALSE
....{....... from
....]....... range.to
....X.......  from < _range.to    -> FALSE

....{..}.... from,to
..[..]...... range
....<....... MAX(from)
.....>...... MIN(to)
....<>......  MAX(from) < MIN(to) -> TRUE
.......}.... to
..[......... range.from
..[....}....  to <= range.from    -> FALSE
....{....... from
.....]...... range.to
....{]......  from < _range.to    -> TRUE

....{..}.... from,to
...[..]..... range
....<....... MAX(from)
......>..... MIN(to)
....<.>.....  MAX(from) < MIN(to) -> TRUE
.......}.... to
...[........ range.from
...[...}....  to <= range.from    -> FALSE
....{....... from
......]..... range.to
....{.].....  from < _range.to    -> TRUE

....{..}.... from,to
....[..].... range
....<....... MAX(from)
.......>.... MIN(to)
....<..>....  MAX(from) < MIN(to) -> TRUE
.......}.... to
....[....... range.from
....[..}....  to <= range.from    -> FALSE
....{....... from
.......].... range.to
....{..]....  from < _range.to    -> TRUE

....{..}.... from,to
.....[..]... range
.....<...... MAX(from)
.......>.... MIN(to)
.....<.>....  MAX(from) < MIN(to) -> TRUE
.......}.... to
.....[...... range.from
.....[.}....  to <= range.from    -> FALSE
....{....... from
........]... range.to
....{...]...  from < _range.to    -> TRUE

....{..}.... from,to
......[..].. range
......<..... MAX(from)
.......>.... MIN(to)
......<>....  MAX(from) < MIN(to) -> TRUE
.......}.... to
......[..... range.from
......[}....  to <= range.from    -> FALSE
....{....... from
.........].. range.to
....{....]..  from < _range.to    -> TRUE

....{..}.... from,to
.......[..]. range
.......<.... MAX(from)
.......>.... MIN(to)
.......X....  MAX(from) < MIN(to) -> FALSE
.......}.... to
.......[.... range.from
.......X....  to <= range.from    -> TRUE
....{....... from
..........]. range.to
....{.....].  from < _range.to    -> TRUE

....{..}.... from,to
........[..] range
........<... MAX(from)
.......>.... MIN(to)
.......><...  MAX(from) < MIN(to) -> FALSE
.......}.... to
........[... range.from
.......}[...  to <= range.from    -> TRUE
....{....... from
...........] range.to
....{......]  from < _range.to    -> TRUE


[ - range from
] - range to
{ - from
} - to
< - MAX(from)
> - MIN(to)

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

PR Comment: https://git.openjdk.org/jdk/pull/17984#issuecomment-1967538880