title: Implementing thread-safe HashMaps of very large size
body: <p>I'm coding a voxel game currently and have stumbled across following problem: While reading my quads from a large (and also volatile!) <code>ConcurrentHashMap</code> I get a flickering effect on my screen and on rare occasions my getter function just returns <code>null</code>. This <code>HashMap</code> uses integers (represented by class <code>GLTexture</code>) to store texture IDs as keys and has <code>ArrayList</code> objects holding <code>Quad</code> objects as values. These lists can reach a total capacity of up to 40000. The GPU handles this fine as I am using very basic (but very effective!) instanced rendering but the chunk generation (which runs on a separate thread, hence the reason for this post) seems to be having problems writing to this map while the renderer is trying to read from it. </p>
  
  <pre><code>public class ChunkMeshGenerator {
  
      private static volatile Map&lt;Chunk, Map&lt;GLTexture, List&lt;Quad&gt;&gt;&gt; quads;
      private static volatile Map&lt;GLTexture, List&lt;Quad&gt;&gt; renderables;
  
      static {
          quads = new ConcurrentHashMap&lt;Chunk, Map&lt;GLTexture, List&lt;Quad&gt;&gt;&gt;();
          renderables = new ConcurrentHashMap&lt;GLTexture, List&lt;Quad&gt;&gt;();
      }
  
      public static void genChunk (Chunk chunk) {
          List&lt;Quad&gt; temp = new ArrayList&lt;Quad&gt;();
  
          Chunk x0 = null;
          Chunk x1 = null;
          Chunk z0 = null;
          Chunk z1 = null;
  
          synchronized (quads) {
              for (Chunk neighbor : quads.keySet()) {
                  if (neighbor.getAbsoluteX() == chunk.getAbsoluteX()-16 &amp;&amp; neighbor.getAbsoluteZ() == chunk.getAbsoluteZ()) {
                      x0 = neighbor;
                  } else if (neighbor.getAbsoluteX() == chunk.getAbsoluteX()+16 &amp;&amp; neighbor.getAbsoluteZ() == chunk.getAbsoluteZ()) {
                      x1 = neighbor;
                  } else if (neighbor.getAbsoluteX() == chunk.getAbsoluteX() &amp;&amp; neighbor.getAbsoluteZ() == chunk.getAbsoluteZ()-16) {
                      z0 = neighbor;
                  } else if (neighbor.getAbsoluteX() == chunk.getAbsoluteX() &amp;&amp; neighbor.getAbsoluteZ() == chunk.getAbsoluteZ()+16) {
                      z1 = neighbor;
                  }
              }
          }
  
          for (int x = 0; x &lt; Chunk.CHUNK_SIZE; x++) {
              for (int y = 0; y &lt; Chunk.CHUNK_HEIGHT; y++) {
                  for (int z = 0; z &lt; Chunk.CHUNK_SIZE; z++) {
                      if (chunk.getCube(x, y, z).getType() == BlockType.AIR) continue;
                      if (x == Chunk.CHUNK_SIZE-1) {
                          if (x1 != null &amp;&amp; x1.getCube(0, y, z).getType() == BlockType.AIR) {
                              temp.add(chunk.getCube(x, y, z).getFace(Cube.RIGHT));
                          }
                      } else if (chunk.getCube(x+1, y, z).getType() == BlockType.AIR) {
                          temp.add(chunk.getCube(x, y, z).getFace(Cube.RIGHT));
                      }
                      if (x == 0) {
                          if (x0 != null &amp;&amp; x0.getCube(Chunk.CHUNK_SIZE-1, y, z).getType() == BlockType.AIR) {
                              temp.add(chunk.getCube(x, y, z).getFace(Cube.LEFT));
                          }
                      } else if (chunk.getCube(x-1, y, z).getType() == BlockType.AIR) {
                          temp.add(chunk.getCube(x, y, z).getFace(Cube.LEFT));
                      }
                      if (y == Chunk.CHUNK_HEIGHT-1) {
                          temp.add(chunk.getCube(x, y, z).getFace(Cube.TOP));
                      } else if (chunk.getCube(x, y+1, z).getType() == BlockType.AIR) {
                          temp.add(chunk.getCube(x, y, z).getFace(Cube.TOP));
                      }
                      if (y != 0 &amp;&amp; chunk.getCube(x, y-1, z).getType() == BlockType.AIR) {
                          temp.add(chunk.getCube(x, y, z).getFace(Cube.BOTTOM));
                      }
                      if (z == Chunk.CHUNK_SIZE-1) {
                          if (z1 != null &amp;&amp; z1.getCube(x, y, 0).getType() == BlockType.AIR) {
                              temp.add(chunk.getCube(x, y, z).getFace(Cube.BACK));
                          }
                      } else if (chunk.getCube(x, y, z+1).getType() == BlockType.AIR) {
                          temp.add(chunk.getCube(x, y, z).getFace(Cube.BACK));
                      }
                      if (z == 0) {
                          if (z0 != null &amp;&amp; z0.getCube(x, y, Chunk.CHUNK_SIZE-1).getType() == BlockType.AIR) {
                              temp.add(chunk.getCube(x, y, z).getFace(Cube.FRONT));
                          }
                      } else if (chunk.getCube(x, y, z-1).getType() == BlockType.AIR) {
                          temp.add(chunk.getCube(x, y, z).getFace(Cube.FRONT));
                      }
                  }
              }
          }
  
          List&lt;Chunk&gt; neighbors = new ArrayList&lt;Chunk&gt;();
          neighbors.add(x0);
          neighbors.add(x1);
          neighbors.add(z0);
          neighbors.add(z1);
  
          updateNeighbors(chunk, neighbors);
  
          Map&lt;GLTexture, List&lt;Quad&gt;&gt; map = quads.get(chunk);
          if (map == null) {
              map = new ConcurrentHashMap&lt;GLTexture, List&lt;Quad&gt;&gt;();
              quads.put(chunk, map);
          }
  
          for (Quad quad : temp) {
              List&lt;Quad&gt; batch = map.get(quad.getTexture());
              if (batch == null) {
                  batch = new ArrayList&lt;Quad&gt;();
                  map.put(quad.getTexture(), batch);
              }
              batch.add(quad);
          }
          genRenderables();
      }
  
      private static void updateNeighbors (Chunk chunk, List&lt;Chunk&gt; neighbors) {
          Chunk x0 = neighbors.get(0);
          Chunk x1 = neighbors.get(1);
          Chunk z0 = neighbors.get(2);
          Chunk z1 = neighbors.get(3);
  
          for (int x = 0; x &lt; Chunk.CHUNK_SIZE; x++) {
              for (int z = 0; z &lt; Chunk.CHUNK_SIZE; z++) {
                  for (int y = 0; y &lt; Chunk.CHUNK_HEIGHT; y++) {
                      if (x0 != null &amp;&amp;
                          x0.getCube(Chunk.CHUNK_SIZE-1, y, z).getType() != BlockType.AIR &amp;&amp;
                          chunk.getCube(0, y, z).getType() == BlockType.AIR) {
  
                          Map&lt;GLTexture, List&lt;Quad&gt;&gt; chunkQuads = quads.get(x0);
                          if (chunkQuads == null) {
                              chunkQuads = new ConcurrentHashMap&lt;GLTexture, List&lt;Quad&gt;&gt;();
                              quads.put(x0, chunkQuads);
                          }
  
                          Quad face = x0.getCube(Chunk.CHUNK_SIZE-1, y, z).getFace(Cube.RIGHT);
                          List&lt;Quad&gt; batch = chunkQuads.get(face.getTexture());
                          if (batch == null) {
                              batch = new SyncList&lt;Quad&gt;();
                              chunkQuads.put(face.getTexture(), batch);
                          }
                          batch.add(face);
                      }
                      if (x1 != null &amp;&amp;
                          x1.getCube(0, y, z).getType() != BlockType.AIR &amp;&amp;
                          chunk.getCube(Chunk.CHUNK_SIZE-1, y, z).getType() == BlockType.AIR) {
  
                          Map&lt;GLTexture, List&lt;Quad&gt;&gt; chunkQuads = quads.get(x1);
                          if (chunkQuads == null) {
                              chunkQuads = new ConcurrentHashMap&lt;GLTexture, List&lt;Quad&gt;&gt;();
                              quads.put(x1, chunkQuads);
                          }
  
                          Quad face = x1.getCube(0, y, z).getFace(Cube.LEFT);
                          List&lt;Quad&gt; batch = chunkQuads.get(face.getTexture());
                          if (batch == null) {
                              batch = new SyncList&lt;Quad&gt;();
                              chunkQuads.put(face.getTexture(), batch);
                          }
                          batch.add(face);
                      }
                      if (z0 != null &amp;&amp;
                          z0.getCube(x, y, Chunk.CHUNK_SIZE-1).getType() != BlockType.AIR &amp;&amp;
                          chunk.getCube(x, y, 0).getType() == BlockType.AIR) {
  
                          Map&lt;GLTexture, List&lt;Quad&gt;&gt; chunkQuads = quads.get(z0);
                          if (chunkQuads == null) {
                              chunkQuads = new ConcurrentHashMap&lt;GLTexture, List&lt;Quad&gt;&gt;();
                              quads.put(z0, chunkQuads);
                          }
  
                          Quad face = z0.getCube(x, y, Chunk.CHUNK_SIZE-1).getFace(Cube.BACK);
                          List&lt;Quad&gt; batch = chunkQuads.get(face.getTexture());
                          if (batch == null) {
                              batch = new SyncList&lt;Quad&gt;();
                              chunkQuads.put(face.getTexture(), batch);
                          }
                          batch.add(face);
                      }
                      if (z1 != null &amp;&amp;
                          z1.getCube(x, y, 0).getType() != BlockType.AIR &amp;&amp;
                          chunk.getCube(x, y, Chunk.CHUNK_SIZE-1).getType() == BlockType.AIR) {
  
                          Map&lt;GLTexture, List&lt;Quad&gt;&gt; chunkQuads = quads.get(z1);
                          if (chunkQuads == null) {
                              chunkQuads = new ConcurrentHashMap&lt;GLTexture, List&lt;Quad&gt;&gt;();
                              quads.put(z1, chunkQuads);
                          }
  
                          Quad face = z1.getCube(x, y, 0).getFace(Cube.FRONT);
                          List&lt;Quad&gt; batch = chunkQuads.get(face.getTexture());
                          if (batch == null) {
                              batch = new SyncList&lt;Quad&gt;();
                              chunkQuads.put(face.getTexture(), batch);
                          }
                          batch.add(face);
                      }
                  }
              }
          }
      }
  
      public static void removeChunk (Chunk chunk) {
          quads.remove(chunk);
          genRenderables();
      }
  
      public static Map&lt;GLTexture, List&lt;Quad&gt;&gt; getMesh () {
          return renderables;
      }
  
      private static void genRenderables () {
          renderables.clear();
          for (Chunk chunk : quads.keySet()) {
              for (GLTexture texture : quads.get(chunk).keySet()) {
                  renderables.putIfAbsent(texture, new ArrayList&lt;Quad&gt;());
                  renderables.get(texture).addAll(quads.get(chunk).get(texture));
              }
          }
      }
  }
  </code></pre>
  
  <p>The main point here is not the functionality of these methods, but rather the parts where I actually modify the <code>quads</code> and <code>renderables</code> maps.</p>
  
  <p>As you can see, I write all of the <code>Quad</code> objects that I generate to the <code>quads</code> map.
  The modifying functions always end with a call to <code>genRenderables()</code>. This ensures that it takes as little time as possible to write to the map.</p>
  
  <p>I want to make very clear that synchronizing the reading is <b>NOT</b> an option, as that would slow down my rendering. I'd rather have the computation time required to go into the chunk generation thread than the rendering thread (in this case the "main" thread).</p>
  
  <p>Any help is greatly appreciated, thanks!</p>
  
  <p>EDIT:
  My renderer runs steadily at 60 fps but seems to randomly just freeze up and travel down to 1 fps from time to time, I think these issues are related and any input regarding this is also great.</p>
  
  <p>EDIT:
  I just realized that <code>renderables</code> is effectively immutable. I clear it and put all of the contents of <code>quads</code> into it.</p>
  
  <p>SOLVED:
  I implemented a backupMap which I clear after updating <code>renderables</code> and add all the current quads. I then wrapped this in a <code>synchronized</code> block and did the same for the getter. Flickering is gone as well as weird null pointer exception. Leaving questions open for answers to EDIT #1.</p>