If nmethods with "old" redefined Methods are saved in a table, this table can be walked instead of the entire code cache.

For Kitchensink, this seems to make a difference:

Before:
grep "cleanup live ClassLoaderData metaspaces" `find . -name gc.log`
[31.711s][1553115674958ms][info ][safepoint,cleanup     ] cleanup live ClassLoaderData metaspaces, 0.0118260 secs
[62.724s][1553115705971ms][info ][safepoint,cleanup     ] cleanup live ClassLoaderData metaspaces, 0.0427590 secs
[183.873s][1553115827120ms][info ][safepoint,cleanup     ] cleanup live ClassLoaderData metaspaces, 0.0178441 secs
[214.323s][1553115857570ms][info ][safepoint,cleanup     ] cleanup live ClassLoaderData metaspaces, 0.0281579 secs
[396.305s][1553116039552ms][info ][safepoint,cleanup     ] cleanup live ClassLoaderData metaspaces, 0.0171240 secs
[1245.064s][1553116888311ms][info ][safepoint,cleanup     ] cleanup live ClassLoaderData metaspaces, 0.0339398 secs
[1717.678s][1553117360925ms][info ][safepoint,cleanup     ] cleanup live ClassLoaderData metaspaces, 0.0223587 secs
[1760.353s][1553117403600ms][info ][safepoint,cleanup     ] cleanup live ClassLoaderData metaspaces, 0.0238709 secs

After:
grep "cleanup live ClassLoaderData metaspaces" `find . -name gc.log`
[30.268s][1553113535295ms][info ][safepoint,cleanup     ] cleanup live ClassLoaderData metaspaces, 0.0009381 secs
[568.405s][1553114073432ms][info ][safepoint,cleanup     ] cleanup live ClassLoaderData metaspaces, 0.0004220 secs
[577.033s][1553114082060ms][info ][safepoint,cleanup     ] cleanup live ClassLoaderData metaspaces, 0.0010892 secs
[819.540s][1553114324567ms][info ][safepoint,cleanup     ] cleanup live ClassLoaderData metaspaces, 0.0018096 secs
[1305.093s][1553114810120ms][info ][safepoint,cleanup     ] cleanup live ClassLoaderData metaspaces, 0.0008552 secs
[1625.169s][1553115130196ms][info   ][safepoint,cleanup     ] cleanup live ClassLoaderData metaspaces, 0.0006562 secs

Long term plan is to make the cleanup outside the safepoint cleanup actions, and concurrent with ZGC with a handshake.
  // Needs to be done single threaded by the VMThread.  This walks
  // the thread stacks looking for references to metadata before
  // deciding to remove it from the metaspaces.
  if (ClassLoaderDataGraph::should_clean_metaspaces_and_reset()) {
    const char* name = "cleanup live ClassLoaderData metaspaces";
    TraceTime timer(name, TRACETIME_LOG(Info, safepoint, cleanup));
    ClassLoaderDataGraph::walk_metadata_and_clean_metaspaces();
  }