Array unshift/access broken

[plobsing]

The Array PMC breaks (segfaults) when a large number of PMCs are unshifted onto it and then are accessed. I suspect that this is in the resizing code because no such error occurs when the array is pre-allocated.

[plobsing]

simple PIR file demonstrating the issue

[kurahaupo]

Firstly, I notice that the array is always missing 1920 elements, even if I double the size to 200000.

Secondly, when I instrumented Parrot_pmc_array_unshift (by putting a "printf" in the conditional block where "start" is 0) it actually failed during the build, at

./parrot -o runtime/parrot/include/parrotlib.pbc runtime/parrot/library/parrotlib.pir

in much the same manner, after just two "unshift" chunk insertions. However since I still had runtime files from the unadulterated build, I could still run the test file.

It's possible that the instrumentation itself causes the new form of error, but I would like to investigate whether GCC is over-optimizating something.

[kurahaupo]

Sorry, it appears that using "printf" screws up freeze/thaw. I've changed it to fprintf(stderr...) and it now builds cleanly -- albeit noisily.

I'll upload a new debug profile after I've tweaked it a bit more...

[kurahaupo]

How the instrumenting was done

[kurahaupo]

Annotated output from (instrumented) "parrot -G array_unshift_test.pir"

[plobsing]

Looking around src/list.c I noticed that get_chunk() has two implementations: normal and 'SLOW_AND_BORING'. When I compile with SLOW_AND_BORING defined, the bug goes away.

The quick fix is therefore to make 'SLOW_AND_BORING' the default get_chunk() implementation. We should run benchmarks to determine how much slower (as suggested by the name) this is.

[kurahaupo]

Smallest array size exhibiting problem is 2033 (although the core dump occurs elsewhere due to memory corruption, rather than directly in the array handling code).

The "early" symptom (before the core dump) is that an unshifted sequence does not read back correctly via sequential indexing.

[kurahaupo]

I've found the key problem: , which will need a patch of about 20-30 lines. (An entire loop needs to be re-done).

Or I can include the entire work-over and refactoring I've given it while I've been trying to figure out how exactly it works.

That would include:

• fix the round-up-to-power-of-two logic so it doesn't leave unnecessary empty space
• unify handling of several different chunk types (therefore fewer tests & code paths)
• make chunk grouping work with any size chunks, not just power-of-two
• separate the handling of "sparsity" and "grouping" (there would still be some interaction in the allocation policy)
• reorder functions to make inlining available

Any preferences for the "short" patch or the "full" patch?

[darbelo]

Replying to kurahaupo:

I've found the key problem: , which will need a patch of about 20-30 lines. (An entire loop needs to be re-done).

Any preferences for the "short" patch or the "full" patch?

If the short one is already 20+ lines, let's start with that one. Reviewing a full refactor of Array will take significantly longer and that might delay the bugfix going in.

[kurahaupo]

Okay, I'll concentrate on that first. (Either way is going to need some work: (a) extract minimal bugfix changeset, or (b) complete the refactoring to a suitable coding standard.)

[kurahaupo]

Yesterday I found an even weirder problem: unshift 17 items, shift 1, push 2, and it dies. Actually, I guessed this one based on code inspection.

Today, however, it appears this all goes away: Array PMC has been removed after a deprecation cycle. (Darn, I wish I'd remembered that before burning so much time debugging it.)

Ticket can be closed.

[kurahaupo]

See ArrayTasklist for plans related to arrays of various sorts.

[bacek]

I would like to reject this ticket as original issue isn't applicable anymore due Array removal.

We can create separate ticket for refactoring various *Array PMCs.

-- Bacek

[whiteknight]

Array PMC is removed in r43695. Closing ticket.