Array PMC freeze/thaw/visit broken

[cotto]

r29183 adds a test to t/pmc/array.t that exposes some brokenness in the Array PMC's freeze/thaw code path. I added the test because it looked like Array's freeze/thaw/visit code had no test coverage. It turns out that list_visit also never gets called (at least according to make cover). I don't have the tuits to fix this for now, hence the ticket and the failing test.

To repo, just prove t/pmc/array.t. If everything passes, you win!

[coke]

(a #parrotsketch followup from 15JUL08)

As a note to whomever fixes this, the sparseness of the Array PMC is its
only remaining useful feature. Fixing freeze/thaw/visit is valuable
because it will make implementing sparseness in
{Fixed|Resizable}{PMC|Integer|Boolean|Float|String}Array easier. Once
those PMCs are sparse, the Array PMC can go away.

[coke]

Originally opened as  http://rt.perl.org/rt3/Ticket/Display.html?id=56718

[whiteknight]

Sparse array algorithms represent a tradeoff: More efficient memory storage for arrays that contain mostly default values in exchange for more-expensive field access.

A sparse array is only a benefit in terms of storage space if the following conditions are met:

• The array is very large
• The majority of items in the array are a default value

Even when it's a win in terms of storage efficiency, it's still going to be more expensive _in all cases_ to access, modify, add, and remove items from the array. If the storage is managed aggressively, it may be performance neutral (or even a slight improvement in some cases) to do copies and comparisons.

The Array PMC as it is implemented right now uses a linked list of List_Chunk objects to implement it's storage. These List_Chunks are GCable items, so the number of items in an array translates directly to increased GC pressure. This is all not to mention that the Array PMC code is a large example of how not to write a PMC following best practices.

If we are going to add sparse behavior to existing array types, I suggest we:

• Not make sparse behavior the default.
• Add an "opt-in" ability to specify that an array should be treated as sparse (buyer beware)
• Add an ability to check whether the array is currently in "sparse mode" or "normal mode".
• Add a routine to check whether a given array would benefit from sparseness

[whiteknight]

Array PMC is removed in r43695. Closing ticket.