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.