Hi,
> -----Original Message-----
> From: Andi Gutmans [mailto:andi@zend.com]
> Sent: Thursday, July 12, 2007 9:06 PM
> To: David; Scott MacVicar
> Cc: Stas Malyshev; Sebastian Bergmann; internals@lists.php.net
> Subject: RE: [PHP-DEV] Mid-term Update for Cycle Collector (Google
> Summer of Code Project)
>
> Hi David,
>
> Isn't finding cycles an NP-complete problem? :) How can you know there
> are no cycles without actually looking for them?
That's right. =P I do traverse all objects for which it is possible to have
cycles. The time-saving observation is that a cycle that has no external
references to it can only be formed when the reference count for one of the
objects in the cycle is decremented to a non-zero value. I take those
objects and buffer them to look at later (the algorithm used to then mark
and sweep these cycles is more efficient when operated on a large buffer).
Is that what you mean?
> As for the additional if() statements you can try and use branch
> prediction hinting to the compiler in order to keep the non-gc version
> fast.
I haven't heard of that before... Is it some sort of compiler optimization
setting? Could you recommend to me some reference that would describe how
this can be done? It might help a lot.
> Btw, one of the challenges I found in the past is knowing which hash
> tables to actually traverse because some variables/hash tables in PHP
> are saved outside the symbol tables. Are you really successful in
> traversing all of them? Are you saving their addresses during
> allocation? If so, how do you know they are intact when you traverse?
Those are some tough questions! Here's what I decided to do in my
implementation: I decided to assume the cycles can only be formed with the
following types of nodes: zvals that are arrays, zvals that point to objects
that use the standard handler table, and objects in the objects store that
use the standard handler table. Of course, it's conceivable that some custom
object will form a reference cycle, but for custom objects, there's really
no good way for me to figure out what zvals they reference. I used to try to
use the get_properties handler, but for example, the SimpleXML extension
actually dynamically generates zvals on each invocation of get_properties.
On each collection cycle, I can traverse a node up to three times, and that
obviously would be pretty disgusting. I decided to just stick with standard
Zend objects.
For array nodes, I just traverse its hash table. For zvals that point to
objects, I just skip to the object it points to. For objects, I traverse its
hash table of properties.
How do I know these nodes are intact? I really don't, but I'm assuming if
they're still referenced, they are intact. Unless they are freed with a
reference count above zero (which does not appear to happen), that
assumption is true. I DO know that my starting points (the buffered nodes)
are intact because I remove them from my buffer when they are destroyed.
(Assumption here is that zval_dtor will be called on any zval before its
memory is freed).
> Do
> you start traversal only when we're supposedly in a stable state?
> (re-entrancy problems?)
A bad state to start traversal in would be one in which traversal will make
me wander into addresses that are bad. I only start collection when the user
explicitly invokes it, or when I detect a possible root. I only check for a
possible root when a reference to an object in object store is removed, or a
couple places in zend_execute, when a zval is assigned to (and overwritten)
and zval_ptr_dtor. This should catch all cycles and these places are
controlled places inside the Zend engine which are stable.
> Also the additional size of zval can be quite an issue. In fact, with
> the whole 16bit->32bit transition we made for refcount we reduced
> performance. Maybe we can figure out a creative way to keep this down?
I've been wracking my brain for a solution to this problem. There are two
primary possibilities I can think of right now. One is to have a new struct
called zval_gc. Every allocation (and zval on the stack and in temporary
storage) will actually allocate the zval_gc which will be exactly the same
as zval, only with the two things I need tacked on the end. Then Zend will
only copy the zval part around and leave the gc part alone (that part
shouldn't be copied anyway) and speed will theoretically be the same.
However, this solution has plenty of its own complications I'm trying to
work out.
The second possibility is to stash the gc variables in the things that the
zvals point to. For arrays, it'd be the hash table. For objects, well,
that's the problem. Multiple zvals can point to the same object. Still
thinking about this one.
Ruled out possibility: Storing the gc information in the unused bits of
refcount and/or is_ref. This one SOUNDS great but for some reason, bitwise
operations are REALLY, REALLY SLOW. This still eludes me. For some reason,
(zval->is_ref > 0x80) is much faster than (zval_isref & 0x80). zval->is_ref
= 0 is also much, much faster than zval->is_ref &= 0x7f. I know the second
one requires both a memory read and write, but should it be so slow as to
more than wipe out any difference eliminating three bytes from the zval
struct made? Derick suggested this one and I still don't understand why it
didn't work. It would've been perfect. If I sound a bit frustrated here, I
am. =P
> Do you mind posting a patch against your baseline to make it easier for
> us to look at your work?
Give me a day or so... I want to work out a patch that macroizes refcount
manipulation for PHP 5.2 in CVS, then I'll post a patch that patches against
THAT.
> This can end up being a good thing if we manage to make it work well.
> The problem with this stuff though is that the last 5-10% is 95% of the
> work :)
Don't I know it!
David
