From: Eric Mahurin <eric.mahurin@...>
Date: 2006-09-25T08:50:21+09:00
Subject: Re: Array shift bug

------=_Part_10365_7840559.1159141818514
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

On 9/24/06, Jeremy Kemper <jeremy@bitsweat.net> wrote:
>
> On 9/24/06, Hal Fulton <hal9000@hypermetrics.com> wrote:
> >
> > That sounds like a performance issue, but this thread title
> > says 'bug.' Is there really a bug or not?
>
>
> Eric demonstrated a memory leak in code that shouldn't. Terminology-wise,
> I
> think that safely falls under the 'bug' rubric.
>
> His algorithmic improvements are cool & welcome but are only related to
> this
> bug inasmuch as they were introduced in the same patch.
>
> jeremy
>
>
Yep.  I'd call something that takes O(n**2) memory to hold O(n) items a
memory leak, but some may argue.   The problem is the copy-on-write
algorithm that is used currently.  You can easily make it so that a small
slice of a few elements can reference a large (O(n) size) array where none
of the other elements are used anymore.

The reason these 2 changes were rolled into one patch was that data
structure changes were needed for both.  I came up with a solution that
attacked both and didn't increase the baseline memory requirements.  I think
it is better to consider both of these issues at the same time.
Unfortunately when you look at the patch, it is a significant rewrite of
array.c (and a bit of gc.c).  This is likely why this patch wasn't taken -
too many changes.  As soon as I made datastructure changes, it required a
lot of changes.

The same techniques could be applied to strings.

------=_Part_10365_7840559.1159141818514--