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,MAILING_LIST_MULTI,RCVD_IN_DNSWL_MED autolearn=ham autolearn_force=no version=3.4.4 Received: (qmail 32127 invoked from network); 16 Apr 2023 09:10:44 -0000 Received: from zero.zsh.org (2a02:898:31:0:48:4558:7a:7368) by inbox.vuxu.org with ESMTPUTF8; 16 Apr 2023 09:10:44 -0000 ARC-Seal: i=1; cv=none; a=rsa-sha256; d=zsh.org; s=rsa-20210803; t=1681636244; b=FLgJIzFyMe4bI5P1jhxh4D1FeFQ7VM7la5IpFI3WXymNhh/CGW3IgRYQ1ka9JeEA+koEUXbJmh V5cw4E9TH60rJXdcSskluN3lx14En8TYP3JjId2/cpBJHC0AtWnn+Zofv34IXNiz9CgI0kc4OJ SpagrIKm9Nz2nmMOnIJZkWNcWMLr3C+ZdPdwP1/B14JCGRwkKDWGYN6QIow1iNNcSkBAs22Tzj /UhdTexoy9J3h2lJRDUTUOk6RzVy2uXnlOFJ0G6pAPbUzGwnUIkND0Y/Ww9txFl0aeOlw+BjDd p3sISVkkh9GKGzP+Jxh4iBIsyeOGRpJ7W0P7uaDV1Ml9PQ==; ARC-Authentication-Results: i=1; zsh.org; iprev=pass (mail-lj1-f179.google.com) smtp.remote-ip=209.85.208.179; 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=1681636244; bh=jU0q2dfSOyUN+PEJfJ4Xefr87XRx9C5j05hTSF7I5og=; h=List-Archive:List-Owner:List-Post:List-Unsubscribe:List-Subscribe:List-Help: List-Id:Sender:Content-Transfer-Encoding:Content-Type:To:Subject:Message-ID: Date:From:In-Reply-To:References:MIME-Version:DKIM-Signature:DKIM-Signature; b=U6XMu+jkbmXxbRzGNnCs6sh1dN8wwkmCsibBETba5w9HPRRd/xMnjUIgS9U52tbQJghqpJMdWC e4waBtXQiA0E8vGMAMQb55umGZ1hQcOo/gatQOTxku9yTyEmnYgVvVSTquCGmUcB8k+0FRvVz9 l7LvIBVqpxieXSJfRRcYGlcvLxqytYYfRZvAw+XYRLCsLv2rhz+X9INcB8u1GxGhtTj8X0BhH0 QF/H07WrJhRiB//Nyo6X0x6Um731/BxonsfUQCUtpg66H5cQq0f2QDlktEQPgIEbs5cxB1qiTz YuiZdJBvWv7br5iskeEEVRmwrpROmUsXoldfsTqIzVmoZw==; 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-Transfer-Encoding: Content-Type:To:Subject:Message-ID:Date:From:In-Reply-To:References: MIME-Version:Reply-To:Cc:Content-ID:Content-Description:Resent-Date: Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID; bh=jU0q2dfSOyUN+PEJfJ4Xefr87XRx9C5j05hTSF7I5og=; b=r4DZBL/rJDXarV7iDHCzuZHPwE guP5K7LOBORgSv59frHAfawAlBpKQlh6w4GtLonPEQQamW5TeXj1QXr051M3kUPrYpJfw+rnvfAAD VCPZNXb+mgio5qcsYe512UJpUqCEXcrm/3wFfl79SLfXRtQbTVElmI0IalmxILhXhbRbicApwmbRs HBv7DqGfQ8d8B6xycHQlViX/uJd9HrpyGWkbK8XqDjjZMzj+Mg9eynvUs400SyqgjIlrc+JLtfuMA jIJTV0nMYyHc5Wa7EKY1uFDx13LsgrFf2rVP2nN/FEEVUVJNiJWPbDlCGTIxVG0GkZPRXP0Gldt4V 1DJESI/g==; Received: by zero.zsh.org with local id 1pnyPE-000Jhx-1u; Sun, 16 Apr 2023 09:10:44 +0000 Authentication-Results: zsh.org; iprev=pass (mail-lj1-f179.google.com) smtp.remote-ip=209.85.208.179; 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-f179.google.com ([209.85.208.179]:43650) by zero.zsh.org with esmtps (TLS1.3:TLS_AES_128_GCM_SHA256:128) id 1pnyOv-000JOQ-25; Sun, 16 Apr 2023 09:10:27 +0000 Received: by mail-lj1-f179.google.com with SMTP id j11so11029710ljq.10 for ; Sun, 16 Apr 2023 02:10:24 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1681636224; x=1684228224; h=content-transfer-encoding:to:subject:message-id:date:from :in-reply-to:references:mime-version:from:to:cc:subject:date :message-id:reply-to; bh=jU0q2dfSOyUN+PEJfJ4Xefr87XRx9C5j05hTSF7I5og=; b=MEtOUK7evy+mgM0Y6hiX8cEiEDMadtWVPzRVIrxnBwxHLbF/+Fz9cXzjqaby2Yi8fs hsydq45kuNTIdD3teGhn6ZlYfVRRQUFYgEk11KmM0BEqdLbaF/s8iEUB+Be2zXb2XWrW l/BrZFnyRG7/Rl+sSUz8VisjG5q7VWRiKc6CkoK81tKtXuLqYMHKwdPG3O7OTaPJlxxx 56Tyr46rULNZ5O34zfekPmG/V/YFDzGrvDxpUGGUeZK+ExDXDObuhCpSQMZXOPZToISP EcAM8xQTARElNseNUtQz5dWDHLu9h7obTS75MQpoz5mRfpT7JRP6PbRF+YLiCxunLaZ1 RAUw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1681636224; x=1684228224; h=content-transfer-encoding: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=jU0q2dfSOyUN+PEJfJ4Xefr87XRx9C5j05hTSF7I5og=; b=d8F+YkPvDOQAiVPaMartDLeO5guKKE5+Dfrp4wLh+J0vh8YCHclOjc+p+YWpJAQ4/t 491nIO4cU/mOQ6zaDgha26QAgqa8RvdJ+Wr/h/XJAEGj93Jr1NA49HuVHNwT5aWMZfx7 07FJCkxO0nAdUEqQ4jyqPVZIhrnpqlgJN83ngQfWy7zrXReCksAPadHb/gf7JALynqzU 4mnFC5CkRHDmbsNQJVQk7uOjOuZ4ARNlc9JVF4Y3E+pxmkszCKkrrsu9KVBP+6SqitR9 gDvmtVHXU6Bpbro7kHzB5inYJNUAi1DB5ZsthW/lVr6Vh9px0yMqYkKNiAzk7YRxvb22 PbOA== X-Gm-Message-State: AAQBX9fay1xn7GNxIgK/z6IEBxcdma+cJqQSNb+7oc27+rfqi3u8oXo8 twelqTZXJh8FrphVEqPyZwgo2C2ZZItMEaI5ky1qKKu+ X-Google-Smtp-Source: AKy350ayfQHLJan3dy/DnHOBv3VD73ur0cu2SyOwhZy9G7NCL7Dkhz/+vM2KLLwFZM4FLunJtKR+4uVc/pv7jUn2gwM= X-Received: by 2002:a2e:a0d2:0:b0:2a8:bbd9:1a07 with SMTP id f18-20020a2ea0d2000000b002a8bbd91a07mr779426ljm.2.1681636223740; Sun, 16 Apr 2023 02:10:23 -0700 (PDT) MIME-Version: 1.0 References: <20230416090342.dztvzcnzpbyukgfq@chazelas.org> In-Reply-To: <20230416090342.dztvzcnzpbyukgfq@chazelas.org> From: Roman Perepelitsa Date: Sun, 16 Apr 2023 11:10:12 +0200 Message-ID: Subject: Re: accessing array by index very slow To: Zsh hackers list Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Seq: 51659 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: 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.