On Mon, 05 Dec 2011 22:07:09 +0100, dsimcha <[email protected]> wrote:

== Quote from Martin Nowak ([email protected])'s article
I appreciate the recursion during mark, wanted to do this myself
sometime ago but expected a little more gain.

The reason the gain wasn't huge is because on the benchmark I have that involves a deep heap graph, sweeping time dominates marking time. The performance gain for the mark phase only (which is important b/c this is when the world needs to be
stopped) is ~20-30%.

Some more ideas:
  - Do a major refactoring of the GC code, making it less reluctant
    to changes. Adding sanity checks or unit tests would be great.
    This probably reveals some obfuscated performance issues.

Not just obfuscated ones. I've wanted to fix an obvious perf bug for two years and haven't done it because the necessary refactoring would be unbelievably messy and I'm too afraid I'll break something. Basically, malloc() sets the bytes between the size you requested and the size of the block actually allocated to zero to prevent false pointers. This is reasonable. The problem is that it does so **while holding the GC's lock**. Fixing it for just the case when malloc() is called by the user is also easy. The problem is fixing it when malloc() gets
called from realloc(), calloc(), etc.

  - Add more realistic GC benchmarks, just requires adding to
    druntime/test/gcbench using the new runbench. The tree1 mainly
    uses homogeneous classes, so this is very synthesized.

I'll crowdsource this. I can't think of any good benchmarks that are < a few
hundred lines w/ no dependencies but aren't pretty synthetic.

Probably write a tool that can replay recorded allocations profiles.
But it will be difficult to fake internal pointers if they are not recorded. If we were able to enable recording in the runtime, people having performance issues with the GC could then send a file that can be used for optimizations.

  - There is one binary search pool lookup for every scanned address in
range.
Should be a lot to gain here, but it's difficult. It needs a multilevel
    mixture of bitset/hashtab.

I understand the problem, but please elaborate on the proposed solution. You've basically got a bunch of pools, each of which represents a range of memory addresses, not a single address (so a basic hashtable is out). You need to know which range some pointer fits in. How would you beat binary search/O(log N) for this?

It is possible to use a hashtable or a bitset because each pool occupies
at least PAGESIZE.
One would need to use addresses relative to the minimum address
but that still needs 256K entries per GByte, so the maintenance
overhead is likely too big.

More promising is to put pool addresses ranges in a trie.

addr[7]          [...      .     ...]
                     /     |    \
addr[6]     [...   .   ...]    [...   .   ...]
               /   |    \         /   |   \
addr[5]     pool:8             [...   .  ...]
                              /   |   \
addr[4]                  pool:8 [....] pool:5

Lookup is bounded constant time, with at maximum 8(4) memory accesses.
Maintenance is only required when adding/removing pools, little sophisticated though.

-----

alias Node Trie;

struct Node
{
   union
   {
      Type           _type;
      Pool*          _pool;
      Node[16]*   _nodes16; // uses upper 3 bits per level
      ...
      Node[256]* _nodes256; // uses  full 8 bits per level
   }

// use lower 3 bits to encode type, given guaranteed 8-byte alignment of malloc
   enum NTypeBits = 3;
   enum TypeMask = (1 << NTypeBits) - 1);
   enum PtrMask = ~TypeMask;

   enum Type { Empty, Pool, Nodes16, Nodes256 };
   static assert(Type.max <= TypeMask);

   Pool* getPool(void* p)
   {
       return getPoolImpl((cast(ubyte*)&p) + size_t.sizeof - 1);
   }

   Pool* getPoolImpl(ubyte* p)
   {
       Node* node = void;

       final switch (type)
       {
       case Type.Empty:
          return null;
       case Type.Pool:
          return pool;
       case Type.Nodes16:
          node = nodes16[*p >> 5];
          break;
       case Type.Nodes256:
          node = nodes256[*p];
          break;
       }

       if (node.type == Type.Pool)
           return node.pool;
       else
           return node.getPoolImpl(p - 1);
   }

   void insertPool(Pool* npool, uint level=0)
   {
       final switch (type)
       {
       case Type.Empty:
           pool = npool;

       case Type.Pool:
           Pool *opool = pool;
           if (opool != npool)
           {
               nodes16 = new Node[16];

               foreach (i; 0 .. 16)
               {
                   // non-trivial code here
// Needs to figure out into which subnode opool and npool // should be inserted. They can use pool.minAddr and pool.maxAddr

                   nodes16[i].insertPool(opool, level + 1);
                   nodes16[i].insertPool(npool, level + 1);
               }
           }
       }

       case Type.Nodes16:
           // count empty nodes and decide whether
           // to switch to more child nodes.
       }
   }

   void removePool(Pool* npool, uint level=0)
   {
       // reverse of above
   }

   @property Type type()
   {
       return cast(Type)(_type & TypeMask);
   }

   @property void type(Type t)
   {
       assert(t <= TypeMask);
       _type |= t;
   }

   @property Pool* pool()
   {
       return cast(Pool*)(cast(size_t)_pool & PtrMask);
   }

   @property void pool(Pool* p)
   {
       _pool = p;
       type = Type.Pool;
   }

   ... for nodesN
}

-----

  - Reduce the GC roots range. I will have to work on this for
    shared library support anyhow.

Please clarify what you mean by "reduce" the roots range.

We currently add something from etext to _end (rt.memory) as static root.
This probably contains read-only sections, data from other languages
and (unlikely) other unrelated sections.
I think some help from the compiler will be necessary to support
shared libraries anyhow, so we should be able to get a precise range.

Thanks for the feedback/suggestions.

Reply via email to