From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 12406 invoked by alias); 3 Dec 2015 23:36:09 -0000 Mailing-List: contact zsh-workers-help@zsh.org; run by ezmlm Precedence: bulk X-No-Archive: yes List-Id: Zsh Workers List List-Post: List-Help: X-Seq: 37297 Received: (qmail 16841 invoked from network); 3 Dec 2015 23:36:08 -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=content-transfer-encoding:content-type :date:from:in-reply-to:message-id:mime-version:references :subject:to:x-sasl-enc:x-sasl-enc; s=mesmtp; bh=MuBq/FLZ20mcGMuJ Z6ACqKFOtKQ=; b=0aZ9Zm1BawJ6AUBy4j2/DXxUr1WXPdTR+uz4eSqYTnnJQi3c iOHjsv8lNplSonJijZISItoWix6fDBZWJDQBj1fVm0hZLOEcLfBO15zDpQ4e0j91 cRGJkRa5PFga1VWe7a1a8781jgTYEnMpmiYpUokENdrVs31L3XNY39dYpY8= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d= messagingengine.com; h=content-transfer-encoding:content-type :date:from:in-reply-to:message-id:mime-version:references :subject:to:x-sasl-enc:x-sasl-enc; s=smtpout; bh=MuBq/FLZ20mcGMu JZ6ACqKFOtKQ=; b=VdGThft0v+NIDBsLEhg0kKM9TAk9hKNoZT/ycNIssr2SfgS yQVIakH/aG3q59BtXkeemG7jpMlLwZBkYh8sso0iGQZ2ZGpU3GVH3ydR/Be6V65t Z0rY3S082qC/3JKSucfgjxHDQVlimAXJduLCOH5sbuMF/KDsIDl3qU0KpTz4= X-Sasl-enc: 7pnTKOfehKlDdvF8CuydbIoBbM44GuOJd/Fu9UXVl9Qj 1449185766 Date: Thu, 3 Dec 2015 23:36:04 +0000 From: Daniel Shahaf To: zsh-workers@zsh.org Subject: Re: Array appends are quadratic Message-ID: <20151203233604.GD1955@tarsus.local2> References: <20151127073730.GI1899@tarsus.local2> <151127025958.ZM23933@torch.brasslantern.com> <20151128180517.GL2498@tarsus.local2> <20151128193652.777742be@ntlworld.com> MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 8bit 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 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(). I'm not sure I see the problem. Doubling reallocations would require the array to track its allocated size (the N in «pm->u.arr = alloc(N * sizeof(void*))», which is strictly greater than its arrlen). I assume only affect places that modify the array would be affected: that is, places that modify pm->u.arr directly (list below) and places that call setfn. So, I think doubling allocations can be made to work, if each place that modifies the array knows what arrlen() would be after the modification, in order to be able to cheaply determine whether its smaller than the allocated length. So maybe it's better to first teach arrays to know their arrlen in O(1), before investigating doubling allocations. (Mikael had investigated this direction.) Daniel typeset_single:Src/builtin.c:2428: tdp->arrptr = &altpm->u.arr; bin_unset:Src/builtin.c:3379: if (start < arrlen(vbuf.pm->u.arr)) { restore_params:Src/exec.c:3898: tpm->gsu.a->setfn(tpm, pm->u.arr); copyparam:Src/params.c:1028: tpm->u.arr = zarrdup(pm->gsu.a->getfn(pm)); arrgetfn:Src/params.c:3341: return pm->u.arr ? pm->u.arr : &nullarray; arrsetfn:Src/params.c:3350: if (pm->u.arr && pm->u.arr != x) arrsetfn:Src/params.c:3351: freearray(pm->u.arr); arrsetfn:Src/params.c:3354: pm->u.arr = x; scanendscope:Src/params.c:5096: pm->gsu.a->setfn(pm, tpm->u.arr); paramsubst:Src/subst.c:2499: pm->u.arr = aval;