From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <zsh-workers-return-37240-mason-zsh=primenet.com.au@zsh.org>
Received: (qmail 29479 invoked by alias); 27 Nov 2015 10:59:44 -0000
Mailing-List: contact zsh-workers-help@zsh.org; run by ezmlm
Precedence: bulk
X-No-Archive: yes
List-Id: Zsh Workers List <zsh-workers.zsh.org>
List-Post: <mailto:zsh-workers@zsh.org>
List-Help: <mailto:zsh-workers-help@zsh.org>
X-Seq: 37240
Received: (qmail 8523 invoked from network); 27 Nov 2015 10:59:43 -0000
X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on f.primenet.com.au
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,T_DKIM_INVALID
	autolearn=ham autolearn_force=no version=3.4.0
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=brasslantern-com.20150623.gappssmtp.com; s=20150623;
        h=from:message-id:date:in-reply-to:comments:references:to:subject
         :mime-version:content-type;
        bh=r7ssOEprUxID1H4/iJK+P+2Rg665qElc8C0HY7Fj0pk=;
        b=NlSmmAdPh2mZreJMqEoYq2kcb/BEhfLfq+nivYDqZwNrAB1KRQJAaMvtT0qafgXtgm
         39D8NI2s1Yvm333GFs3/LG/21RbUynPlPHstLrCJ5hjWa4saSiYoWh4k+sVcBwUWdqHf
         929xyuG3BZSdUBQwGYmT1ZyoTYP1ZAc4/MFYHk7uwid4e6S5oRWMlYkCGQW7cEh/8GQm
         zXME+yhv/22RlAQNuyE3j15KYNu9EN8cXl00uSv+8ltn8mEZABj9Zwh+HNTs3rFLI2Sv
         rjPp38VHG6WA4lNpRDmV4QfeO3EYXE7Gvw/0Rhhe3CtnIru2dOHw7C9tyyW8ad8XyQac
         vcSA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=1e100.net; s=20130820;
        h=x-gm-message-state:from:message-id:date:in-reply-to:comments
         :references:to:subject:mime-version:content-type;
        bh=r7ssOEprUxID1H4/iJK+P+2Rg665qElc8C0HY7Fj0pk=;
        b=grFXChMzQoMrs+CYxhHeu2pXYX3tqKT96xLf3NeDGKgXC1RSlZ+2Lv6Xe3cFfPAoLT
         hNQGhehOutZSTud125YgMF4dmmjBOn8vJJvQSETD2nCUZIIK+VgfLmkN3P0YQilFQgYI
         r1aBXHdwcqjUZj2jlgzpVBxJPvd0w1WWpmvATa+pB1WP+R/jk12BSH0ycOqnVVsy0C4e
         c7LQr5d4mzRiHr8FLfpLGQEllzkfaaTMv9OgX/ZFnu0FM8YfiUyIGOdTe+VOrdfed1Og
         iaBUbEVEvQDC5BQh9NegNrQh57wtjlREIQ1j7BZQuWRP/4WE+PbNIBspu0Z64Evmn3tX
         T5Ow==
X-Gm-Message-State: ALoCoQmFFkisu9bMQgOJLg8zTWjMmt7znF90dMHz/oEDojoVRVSEmnuomw5VgS11b/VxPzcmjKTU
X-Received: by 10.98.86.210 with SMTP id h79mr47204808pfj.87.1448621982227;
        Fri, 27 Nov 2015 02:59:42 -0800 (PST)
From: Bart Schaefer <schaefer@brasslantern.com>
Message-Id: <151127025958.ZM23933@torch.brasslantern.com>
Date: Fri, 27 Nov 2015 02:59:58 -0800
In-Reply-To: <CAHYJk3S6_opij6An1DWt+8UDvDerooSyjkXfUfYJgBjUfNMC0Q@mail.gmail.com>
Comments: In reply to Mikael Magnusson <mikachu@gmail.com>
        "Re: Array appends are quadratic" (Nov 27,  9:26am)
References: <20151127073730.GI1899@tarsus.local2> 
	<CAHYJk3S6_opij6An1DWt+8UDvDerooSyjkXfUfYJgBjUfNMC0Q@mail.gmail.com>
X-Mailer: OpenZMail Classic (0.9.2 24April2005)
To: zsh workers <zsh-workers@zsh.org>
Subject: Re: Array appends are quadratic
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii

On Nov 27,  9:26am, Mikael Magnusson wrote:
} Subject: Re: Array appends are quadratic
}
} According to your debug prints, the array is reallocated every time it
} is assigned to, even when the required element is already allocated.
} Doubling the allocation size would do nothing to fix that, presumably.

Right, this is generic code to handle array splicing, so starting from
an array with 200 elements,

    a[100]=foo

and

    a[50,150]=(foo)

use the same loop even though the former does not change the size of
the resulting array and the latter will waste 100 slots at the top.
I vaguely recall a conversation in which we decided that fewer code
branches was better than attempting to efficiently re-use array slots.


} % a[100]=foo
}  params.c:2585: setarrvalue: Reallocating 'a' to size 100
} % a[5]=bar
}  params.c:2585: setarrvalue: Reallocating 'a' to size 101
} % a[10]=bar
}  params.c:2585: setarrvalue: Reallocating 'a' to size 101
} 
} Do we have an... off-by-two bug somewhere?

No, it just always allocates 1 more than the largest occupied array
index position if the array isn't empty to begin with.