Slash Boxes
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.
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 Parrot/smallobject.h.

            The GC headers form a linked-list with a definite, if arbitrary, order. The flags that I was envisioning (and this could easily have been a point of miscommunication) would follow the ordering of the GC headers, not the PMC headers. This has a few benefits that I can think of, most importantly that the solution can be carried across all pools uniformly, without having to edit fields in half a dozen different header structures.

            Let's say we have 5 memory objects with GC headers:

            | Obj_A | Obj_B | Obj_C | Obj_D | Obj_E |

            And a 10-bit bitmap with corresponding flags:

            | FA | FB | FC | FD | FE |

            During a GC run, we find element C to be dead, so we deallocate the storage. We could possibly add it to the Arena's free list, or we could even return the memory to the operating system. Either way, the space is not to be managed by the GC anymore, so the GC header is deallocated (or recycled, or whatever). So, we can remove the header from the list:

            | Obj_A | Obj_B | Obj_D | Obj_E |

            Our flags now are messed up, because we have 5 flags corresponding to 4 nodes in our list, and a "hole" where the flag for object C used to be:

            | FA | FB | XX | FD | FE |

            We either leave the hole as is and attempt to fill it later by inserting a newly created node where object C's header used to be (1), or we bit-shift the flags FD and FE forward by two bits to fill the hole (2):

            1) | FA | FB | FG | FD | FE |

            2) | FA | FB | FD | FE |

            If the cardmarking we are doing is in relation to the PMC headers and not the GC headers as I had supposed, then we obviously need to use a different system entirely, one where we likely don't need to rearrange flags at all.

            If I'm thinking of things in an exactly opposite way to how other people are thinking about it, maybe some more clarification is needed on my part.
            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 b
                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.