From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-3.4 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,FREEMAIL_FROM,HTML_MESSAGE,MAILING_LIST_MULTI, RCVD_IN_DNSWL_MED autolearn=ham autolearn_force=no version=3.4.4 Received: (qmail 32499 invoked from network); 16 Apr 2023 09:20:17 -0000 Received: from zero.zsh.org (2a02:898:31:0:48:4558:7a:7368) by inbox.vuxu.org with ESMTPUTF8; 16 Apr 2023 09:20:17 -0000 ARC-Seal: i=1; cv=none; a=rsa-sha256; d=zsh.org; s=rsa-20210803; t=1681636817; b=FsNRadEIj8TQwQF/0iCr31/RcYpkTfXiKqVdLPOAD6Q7hj8jQQ+u87NruiFY81ekWOqYplcqJp vgGibfCb5wWLkOeUDIktBzWFWMrtrH2fICXKRyQ9UTIr7Xya+e8HYno57YuFSZ3FiBLay9d91t pzRHRPerrlGgWUh6gjrGGkxsPHaHYsuSrPsVxWqVKEG5ykMped1uhctFYQb6At2GsquFjhgRdl obCRzS49k8NG9EXbFlni5pcBiouymFZYz2PfEq3qf7/JNFXiTuh3o0UZN4DHFFNQUQg9cu9C2t MY9FktIRlR/rRD11hqUgcvHXoVoG7nbZXbpFgsj6jlwmZg==; ARC-Authentication-Results: i=1; zsh.org; iprev=pass (mail-lj1-f177.google.com) smtp.remote-ip=209.85.208.177; dkim=pass header.d=gmail.com header.s=20221208 header.a=rsa-sha256; dmarc=pass header.from=gmail.com; arc=none ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed; d=zsh.org; s=rsa-20210803; t=1681636817; bh=f6peM1/IVhaULymGY9PBgPSMUJhSoJ5d5GOZ0cfILTU=; h=List-Archive:List-Owner:List-Post:List-Unsubscribe:List-Subscribe:List-Help: List-Id:Sender:Content-Type:Cc:To:Subject:Message-ID:Date:From:In-Reply-To: References:MIME-Version:DKIM-Signature:DKIM-Signature; b=sNcRFhYf0ThEWsECCozyFNry/8LGgJlnVVLIhPmNvLVvTRFO4hT0cO47NdqHyjoGABVcbuVBwn 90XFfzOHO5XOMaExFnWQX2ZNfWrl2b+6c8hi0YA2IDfmvUIBADMk1PMhq+2oNaPYiRKco2rTQH 0QE3yXt5DXiyTsza0jvn4as3ruuzLwv8Ci1gPmpe5Gl5y3gBnpkMj4o3gabJMeN+CkIL/iMqEf EhZzFBiVDw9G7M3BNtzEbAoPrnbsVuAvLZAAXDX+Y0OfZBf1H//U45RenmTj9vjKwq9zLQQItz IV1pO0hGi6sK8Cn0gMHVhu5GdMW4OJ9MdYpduQ2v94EAig==; DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=zsh.org; s=rsa-20210803; h=List-Archive:List-Owner:List-Post:List-Unsubscribe: List-Subscribe:List-Help:List-Id:Sender:Content-Type:Cc:To:Subject:Message-ID :Date:From:In-Reply-To:References:MIME-Version:Reply-To: Content-Transfer-Encoding:Content-ID:Content-Description:Resent-Date: Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID; bh=f6peM1/IVhaULymGY9PBgPSMUJhSoJ5d5GOZ0cfILTU=; b=StFVKGlu2TGDQOBn64QQ69ox6d QmR7bq9FG+7KuAaD/zMw3eNp+uykEXmZhKvM7lMj/BvM1c8qovhTy7hDld2ixCtBM72f6D7wJrdpP Ht8MteOGJ0HzmM/xrWQXmNvag3F6Gt2ISZCM+OxgqpYYFd3ubSkgxrXfK/E4/huloKEqIMqnMSRHf 0WCEBgE3sntUZXObEFHj6Xfx78TQP0zK0Ks8D/8C+mEL92q4q+eFoWSU5AAA9cJda7B0m7g3hG2cI 7+6QCiiuyCgEIbrjbiYz3F402EZXdoeLXmtrJZyAqOjo44sPnPRTNOc/IynutKqsAwSrjnnLvQHkF U01A5Ocg==; Received: by zero.zsh.org with local id 1pnyYS-000KW0-Ue; Sun, 16 Apr 2023 09:20:16 +0000 Authentication-Results: zsh.org; iprev=pass (mail-lj1-f177.google.com) smtp.remote-ip=209.85.208.177; dkim=pass header.d=gmail.com header.s=20221208 header.a=rsa-sha256; dmarc=pass header.from=gmail.com; arc=none Received: from mail-lj1-f177.google.com ([209.85.208.177]:41605) by zero.zsh.org with esmtps (TLS1.3:TLS_AES_128_GCM_SHA256:128) id 1pnyYF-000KCQ-Rv; Sun, 16 Apr 2023 09:20:04 +0000 Received: by mail-lj1-f177.google.com with SMTP id n22so21759596ljq.8 for ; Sun, 16 Apr 2023 02:20:03 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1681636803; x=1684228803; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=f6peM1/IVhaULymGY9PBgPSMUJhSoJ5d5GOZ0cfILTU=; b=IW7ccHnZptktiHYyBHRiLpoQKq2/OA1qSATGbJ/TflS00mSgoEc4vgtullnzOcj1jd tmZNKUbNVVE27XwVGRa0I5UWdI7s/7ZC5Pqmee+hs3eTUyutAC8uc/N11lk2pKzhVGUO 1XVrqE9nVus9Lz9TUnWJXe2Dt0dVTQsgCtGfpuzpv0AQ2cdYJ8HeRRiTg2sAgCiS/DUT 3zqOkpIHqKeXyMTdY5FWz22eHQ5TGnPILdfAav3QcUQmfEilMM90rHaVGCSfeFw4t5jK 7cbDltnEY1uEx00KEyvs9HyTs/9TJYICLCqSYkPKBFv84HQCGHtL5d19KlFI/ISdkUfX 40QA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1681636803; x=1684228803; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=f6peM1/IVhaULymGY9PBgPSMUJhSoJ5d5GOZ0cfILTU=; b=LxlfhPzy556kW7pB/ahEFH8ccLxElKnv26j7EANS+VYomWdNc+whl0i7VNfjsayRJd n9YQ3WQat4a26McT0iKJyUcB7kIyXTVPrYK6+WZsxSpnBI35/ZSIB/eboQCjgzzD69Nt QqqOKL8nas83vv4oImaWzvsiV3s2LX8TfG8nk0Ssp9tDVoJVBbw9DOPvrJQ2Q9rgTDyt +Zeh9unKK85mBECAA1hnUMTDy43/3k+/+FOKL1Anzg8Kn3nsE0y5/nClYy+SIN+TfbS0 KFt2QpCFeKWXAEJNoDvPzffv4JhZ7X+UMsXvSXo8xIUawcS7prDoRcIjWNO1MgaUwyX9 RyBQ== X-Gm-Message-State: AAQBX9cre0+y2Mbd+QruObSAOR14caBoJKzRItBdTpwGy+H++DtE3iPN l6LsoMUSqqfYhnqZxboYHlcwpp/JTpx4aAz/kk4= X-Google-Smtp-Source: AKy350Y3wUmD1PTf8waAI7MOZ8dd/WdeOel7P0LVgvsI/WpA8bhyPhHYOesUx9rGSktmwGqGstN3GvA+7l8UQzX18Nw= X-Received: by 2002:a2e:90ca:0:b0:2a8:baf7:4e60 with SMTP id o10-20020a2e90ca000000b002a8baf74e60mr913821ljg.9.1681636802789; Sun, 16 Apr 2023 02:20:02 -0700 (PDT) MIME-Version: 1.0 References: <20230416090342.dztvzcnzpbyukgfq@chazelas.org> In-Reply-To: From: Sebastian Gniazdowski Date: Sun, 16 Apr 2023 11:19:49 +0200 Message-ID: Subject: Re: accessing array by index very slow To: Roman Perepelitsa Cc: Zsh hackers list Content-Type: multipart/alternative; boundary="0000000000004586dc05f970949d" X-Seq: 51660 Archived-At: X-Loop: zsh-workers@zsh.org Errors-To: zsh-workers-owner@zsh.org Precedence: list Precedence: bulk Sender: zsh-workers-request@zsh.org X-no-archive: yes List-Id: List-Help: , List-Subscribe: , List-Unsubscribe: , List-Post: List-Owner: List-Archive: --0000000000004586dc05f970949d Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable There was badarrays branch from Mikachu in the past. it was resolving constant arrlen() calling. niedz., 16 kwi 2023, 11:10 u=C5=BCytkownik Roman Perepelitsa < roman.perepelitsa@gmail.com> napisa=C5=82: > On Sun, Apr 16, 2023 at 11:04=E2=80=AFAM Stephane Chazelas > wrote: > > > > Accessing array elements via their index is very slow, > > especially for large index values. > > Indeed, access to array elements is O(N) in zsh instead of O(1) that > one might expect. The same goes for strings, even with no_multibyte. > This makes computation-heavy code incredibly slow. If someone can fix > this, they'll have my eternal gratitude. > > On the plus side zsh has fast hashtables (closed hashing with > quadratic probing). Bash's implementation is a lot slower (it's > node-based). > > Roman. > > --0000000000004586dc05f970949d Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
There was badarrays branch from Mikachu in the past. it w= as resolving constant arrlen() calling.

niedz., 16 kwi 2023, 11:10 u=C5=BCyt= kownik Roman Perepelitsa <roman.perepelitsa@gmail.com> napisa=C5=82:
On Sun, Apr 16, 2023 at 11:04=E2=80=AFAM Stephane Chazelas<= br> <stephane@chazelas.org> wrote:
>
> Accessing array elements via their index is very slow,
> especially for large index values.

Indeed, access to array elements is O(N) in zsh instead of O(1) that
one might expect. The same goes for strings, even with no_multibyte.
This makes computation-heavy code incredibly slow. If someone can fix
this, they'll have my eternal gratitude.

On the plus side zsh has fast hashtables (closed hashing with
quadratic probing). Bash's implementation is a lot slower (it's
node-based).

Roman.

--0000000000004586dc05f970949d--