Stories
Slash Boxes
Comments
NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

All the Perl that's Practical to Extract and Report

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
 Full
 Abbreviated
 Hidden
More | Login | Reply
Loading... please wait.
  • Why do you need to remove anything from the flag array? Nodes are not freed until after the final pass over the list, so it would appear that there is no reason to make sure that array indices continue to correspond to list positions after freeing.

    • I presume you're talking about the card-marking scheme. I don't believe there's any need to add or remove entries, as each bit in the bitmap represents one header in the pool.

      (I know Aristotle understand this, but if anyone else finds this idea confusing, think of the most space-compact way to store a list of used telephone numbers within a prefix. You only need 10,000 bits to store all of the available numbers from 989-0000 to 989-9999.)

      • Yes, I was talking about the card-marking scheme. (Well, it would be two bits per pool header in this case.)

        So if there is indeed no need to remove entries from the bitmap, why did Andrew mention bit-shifting it?

        • So if there is indeed no need to remove entries from the bitmap, why did Andrew mention bit-shifting it?

          I don't know; I think there was some miscommunication about that part. I'm following up with him now.

          • Good comments, all. Let me see if I can better explain what I meant, and in the process not expose myself to be a complete buffoon.

            First to terminology: In my post, as well as here in this comment, I'm generally referring to "headers" as a simple linked-list header object that is used internally to the GC to keep track of the memory objects that we see and mark. The "PMC header", defined as "struct PMC" will be referred to as just a "PMC". The current GC uses a structure "Gc_gms_hdr" as a header, defined in
            --
            Andrew Whitworth
            • There was no communication issue, it was clear what you meant.

              My point is: deleting Obj_C does not change the order of the following elements; you do not iterate over the bitmap another time after the deallocation pass; on the next GC cycle you reinitialise the bitmap to all-white. So in fact there is no need to do anything about holes at all.

              If there is some reason that you actually do need to resynchronise the bitmap with the list, then you could exploit the fact that you use two bits but only have th

              • This whole conversation has pointed out to me a conceptual error on my part, and I thank you for that. Two facts occur to me that I hadn't really considered:

                1) If we can identify a dead object from the list before the end of the GC run and can remove it from the list at that point, there is no sense flagging it at all: It's position inside the list serves as an implicit flag that the object is not dead.

                2) We don't identify an object as "dead" until the GC run is finished. This means that the lists are not being manipulated through additions or deletions before the end of the GC run. Hence, the order of the nodes stays the same, the order of the flags stays the same, and nothing needs to be moved around.

                I was trying to allow for a possibility where the GC operated in increments, and a run would not need to be completed in one shot but a partial-run could happen and then be resumed at a later time. However, in this situation we can assume that objects that are created before a GC run has completed can be stored separately from the objects which are currently being marked. There are certainly a lot of other problems with doing things this way, however, and I may need to reconsider it entirely.
                --
                Andrew Whitworth
                • However, in this situation we can assume that objects that are created before a GC run has completed can be stored separately from the objects which are currently being marked.

                  We probably have to assume that in any incremental scheme, which suggests to me that all new GCable entities created while a GC run is active need to go on the live list automatically as soon as they get pulled off of the free list.