From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <zsh-workers-return-37251-mason-zsh=primenet.com.au@zsh.org>
Received: (qmail 8933 invoked by alias); 30 Nov 2015 03:32:26 -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: 37251
Received: (qmail 4145 invoked from network); 30 Nov 2015 03:32:25 -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-sha1; c=relaxed/relaxed; d=
	daniel.shahaf.name; h=cc:content-type:date:from:in-reply-to
	:message-id:mime-version:references:subject:to:x-sasl-enc
	:x-sasl-enc; s=mesmtp; bh=V3cKYnVtvf3XCsUc37OZclvEtR0=; b=Bi+kt5
	SqtMbATbbqIFJrgZ59QqH6oeAc313+yaF8D8C3NWCiY1K3lXrWkSGKjSUGYUWNh/
	7bOB/KJjNUggXvGgTgvNoBM4yntTyS0sKIwZciJtOtXPO/kkI3zhDmpJe+G6hAAf
	ILtds++hpkwMEy2SmrsznfBEkthnnPDbpVXSY=
DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=
	messagingengine.com; h=cc:content-type:date:from:in-reply-to
	:message-id:mime-version:references:subject:to:x-sasl-enc
	:x-sasl-enc; s=smtpout; bh=V3cKYnVtvf3XCsUc37OZclvEtR0=; b=MXMLE
	JOQMEfrbAYXayFrzRQYu1JlYqZdAtuzjom3j9YzKZADtyuYP9veMtRI4qybr6xO7
	XJso7JwijBcUiq2K5QGphWS8pt31ECdS8gsq5l4KsHPwvWdWEw9W05f2KWmu7Xts
	YunecPdy9Rs9uOGRBF9thKz9TNXT+ya6UJUTQY=
X-Sasl-enc: 348zQExizH7Uqg1M4I+yhLLZUDJ4TdugsDvcRTWASGYM 1448853632
Date: Mon, 30 Nov 2015 03:20:29 +0000
From: Daniel Shahaf <d.s@daniel.shahaf.name>
To: Peter Stephenson <p.w.stephenson@ntlworld.com>
Cc: zsh workers <zsh-workers@zsh.org>
Subject: Re: Array appends are quadratic
Message-ID: <20151130032029.GE2504@tarsus.local2>
References: <20151127073730.GI1899@tarsus.local2>
 <CAHYJk3S6_opij6An1DWt+8UDvDerooSyjkXfUfYJgBjUfNMC0Q@mail.gmail.com>
 <151127025958.ZM23933@torch.brasslantern.com>
 <20151128180517.GL2498@tarsus.local2>
 <20151128193652.777742be@ntlworld.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20151128193652.777742be@ntlworld.com>
User-Agent: Mutt/1.5.21 (2010-09-15)

Peter Stephenson wrote on Sat, Nov 28, 2015 at 19:36:52 +0000:
> On Sat, 28 Nov 2015 18:05:17 +0000
> Daniel Shahaf <d.s@daniel.shahaf.name> wrote:
> > The effort involved in implementing the redoubling allocation (for the
> > other problem indicated in 37236) would be similar: mainly having the
> > array remember the number of allocated slots.  I'll have to track done
> > all places in the code that allocate/reallocate arrays, hopefully there
> > aren't too many.
> 
> I suspect (though I haven't actually done a search) you're out of luck
> here, as there's a wide assumption that null-terminated char **'s are
> the the way to carray a fixed number of elements with generic contents
> that might get presented to the user.  See for example the number of
> uses of mkarry().

Thanks for the pointer, I shall have a look.

> Not allocating when the size hasn't changed should be much easier and is
> easy to test for.

It'll be just a local fix to setarrvalue(), and it would fix the problem
for callers that preallocate the array (by doing 'a[10000]=""').  Sounds
simple enough.  I'll look into it.

Cheers,

Daniel

> 
> pws