Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8309639

GenShen: Regression in LRU cache benchmark



    • gc


      From Christine Flood, see https://github.com/openjdk/jdk/pull/14185#issuecomment-1579278537 :

      I wrote an LRU program back in 2017 which allocates trees and stores them in an array in a round robin fashion, freeing the last allocated. At the time this was written it's purpose was to show how generational GCs can hit the wall and start performing very badly. I ran this on a clean openjdk build, a genshen build in generational mode and a genshen build in non-generational mode. These results are repeatable for me.

      I would like to understand where the degradation is coming from before moving forward with this patch since it appears to penalize those who wish to just run traditional Shenandoah.

      cflood@fedora java_programs]$ ~/genshen/cleanjdk/build/linux-x86_64-server-release/images/jdk/bin/java -XX:+UnlockExperimentalVMOptions -XX:+UseShenandoahGC LRU 1000 1000
      Took 341892ms to allocate 1000000 trees in a cache of 1000

      Genshen generational (we expect this to be bad)
      [cflood@fedora java_programs]$ ~/genshen/jdk/build/linux-x86_64-server-release/images/jdk/bin/java -XX:+UnlockExperimentalVMOptions -XX:+UseShenandoahGC -XX:ShenandoahGCMode=generational LRU 1000 1000
      Took 442012ms to allocate 1000000 trees in a cache of 1000

      Genshen non-generational (shows what I feel is a significant degradation from the clean build)
      [cflood@fedora java_programs]$ ~/genshen/jdk/build/linux-x86_64-server-release/images/jdk/bin/java -XX:+UnlockExperimentalVMOptions -XX:+UseShenandoahGC LRU 1000 1000
      Took 395679ms to allocate 1000000 trees in a cache of 1000

      I think that generational Shenandoah can be a big win for some applications, but I want to fully understand the cost for all applications.

      I can't attach a .java file so here it is inline in the post.

      class TreeNode {
        public TreeNode left, right;
        public int val;

      public class LRU {
      static int cache_size;
      static int reps;
      static int tree_height=16;

      private static TreeNode[] trees;

      private static int getIndex(int i) {return i % cache_size;}
      private static TreeNode makeTree(int h) {
          if (h == 0) { return null;}
          else {
          TreeNode res = new TreeNode();
          res.left = makeTree(h - 1);
          res.right = makeTree(h - 1);
          res.val = h;
          return res;

      public static void main(String[] args) {
          if (args.length != 2) {
              System.err.println("LRU requires args: cache_size reps");
          cache_size = Integer.parseInt(args[0]);
          reps = Integer.parseInt(args[1]) * cache_size;
          trees = new TreeNode[cache_size];

          long start = System.currentTimeMillis();
          for (int i = 0; i < reps; i++)
              trees[getIndex(i)] = makeTree(tree_height);
          long end = System.currentTimeMillis();
          long ms = end - start;

          System.out.println("Took " + ms + "ms to allocate " + reps + " trees in a cache of " + cache_size);


        Issue Links



              wkemper William Kemper
              ysr Y. Ramakrishna
              0 Vote for this issue
              4 Start watching this issue