Zsh Mailing List Archive
Messages sorted by:
Re: Array appends are quadratic
- X-seq: zsh-workers 37251
- From: Daniel Shahaf <d.s@xxxxxxxxxxxxxxxxxx>
- To: Peter Stephenson <p.w.stephenson@xxxxxxxxxxxx>
- Subject: Re: Array appends are quadratic
- Date: Mon, 30 Nov 2015 03:20:29 +0000
- Cc: zsh workers <zsh-workers@xxxxxxx>
- 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=
- In-reply-to: <firstname.lastname@example.org>
- List-help: <mailto:email@example.com>
- List-id: Zsh Workers List <zsh-workers.zsh.org>
- List-post: <mailto:firstname.lastname@example.org>
- Mailing-list: contact zsh-workers-help@xxxxxxx; run by ezmlm
- References: <20151127073730.GI1899@tarsus.local2> <CAHYJk3S6_opij6An1DWt+8UDvDerooSyjkXfUfYJgBjUfNMC0Q@mail.gmail.com> <151127025958.ZM23933@torch.brasslantern.com> <20151128180517.GL2498@tarsus.local2> <email@example.com>
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@xxxxxxxxxxxxxxxxxx> 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=""'). Sounds
simple enough. I'll look into it.
Messages sorted by: