Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > gnu.bash.bug > #16172
| Path | csiph.com!goblin1!goblin.stu.neva.ru!usenet.stanford.edu!not-for-mail |
|---|---|
| From | George Jones <fooologist@gmail.com> |
| Newsgroups | gnu.bash.bug |
| Subject | speeding up hash_search? |
| Date | Sun, 19 Apr 2020 10:53:59 -0400 |
| Lines | 12 |
| Approved | bug-bash@gnu.org |
| Message-ID | <mailman.680.1587308057.3066.bug-bash@gnu.org> (permalink) |
| References | <CALv3B7aiTbhpyUL17Eg5prH39EgMP8uSDdD554OdND3LFETAQg@mail.gmail.com> |
| NNTP-Posting-Host | lists.gnu.org |
| Mime-Version | 1.0 |
| Content-Type | text/plain; charset="UTF-8" |
| X-Trace | usenet.stanford.edu 1587308057 15744 209.51.188.17 (19 Apr 2020 14:54:17 GMT) |
| X-Complaints-To | action@cs.stanford.edu |
| To | bug-bash@gnu.org |
| Envelope-to | bug-bash@gnu.org |
| DKIM-Signature | v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:from:date:message-id:subject:to; bh=h3i7griIQ4BKuObL6zFst3AJaCs+qlgYQrXFmT2tsws=; b=IB2pT13QboIFgw3uQztwHms4bdBOs6e8xRaSHUesed67/kLQLP6ZGzzWze5hEWstof Vxah700SakqyFVdyc+m+5pB6KX6qd5jv+q05QoKEeDy9li1/Nwjg/0vikepJlRjRrN3E 0ZcoiO2GD8je1zz/Sr1EXBm2eYZu0ma8YBsKhBA4EO0cE9SeHRnkbsR8C30rEDbHfxSK W0rDY8pIt8sNrMXBeWGRayqf9SXHwdg+iQGdiGLBkpI6INzvkExWuQtLNON4LivtE94L /utQu7CN0C8n6vvCfzW/Q/iGWYTGcagvMqOe3zs4LkTrDnzxEIpJVs1P+pTp+Hyuo0t5 SICw== |
| X-Google-DKIM-Signature | v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=h3i7griIQ4BKuObL6zFst3AJaCs+qlgYQrXFmT2tsws=; b=kdp5jynCiZggHsAeU7oucZrcSuHAvFcqRS2B9yAOJHjz3K8eCTKjROgM7gsovYbiBP xYQRVBJYKXAmlG8tm0MtEKYi8d09gbIlz6AwnbRRhdX8Fuu9JyntO6So5Db1zw7YvPmq cN1dWWJxFCiAcl1TjwsKJlhSm+j9ne9t+CJW1OUEC0ZXJZA4yYHl6tqwnY/jUJuj8rj4 rZAMOe1GhJvLlDntEFjRyeaJLTtVmb0po9hd7ptWZViSDvdBM+JZHQNPSPWRrW3lLEQh Vju2tNjXczFYUnETj1xDAfvq9V3eajL0e9BCuGmaX6zNJHZY8Kkm6J/z1413PuGWB0sa P6JA== |
| X-Gm-Message-State | AGi0PubmNCHxHxylOJ3PpPu4FN/ywNWo8D31wQSf20lgxTAzibNMNbAT TWMk5sCYC74yra9dlfJTlVLx15qkN4fIOXGMkw0nOQ== |
| X-Google-Smtp-Source | APiQypLsKK0uhvlc+yjC631jiyOxfBt4SncnZmAnxxu5BBGk/pqCy3v780ke1x6pkhtdp5+9Mpa/IGqBA5XFcm/+JNg= |
| X-Received | by 2002:aca:f50e:: with SMTP id t14mr7745344oih.156.1587308052546; Sun, 19 Apr 2020 07:54:12 -0700 (PDT) |
| Received-SPF | pass client-ip=2607:f8b0:4864:20::236; envelope-from=fooologist@gmail.com; helo=mail-oi1-x236.google.com |
| X-detected-operating-system | by eggs.gnu.org: Genre and OS details not recognized. |
| X-Received-From | 2607:f8b0:4864:20::236 |
| X-Content-Filtered-By | Mailman/MimeDel 2.1.23 |
| X-BeenThere | bug-bash@gnu.org |
| X-Mailman-Version | 2.1.23 |
| Precedence | list |
| List-Id | Bug reports for the GNU Bourne Again SHell <bug-bash.gnu.org> |
| List-Unsubscribe | <https://lists.gnu.org/mailman/options/bug-bash>, <mailto:bug-bash-request@gnu.org?subject=unsubscribe> |
| List-Archive | <https://lists.gnu.org/archive/html/bug-bash> |
| List-Post | <mailto:bug-bash@gnu.org> |
| List-Help | <mailto:bug-bash-request@gnu.org?subject=help> |
| List-Subscribe | <https://lists.gnu.org/mailman/listinfo/bug-bash>, <mailto:bug-bash-request@gnu.org?subject=subscribe> |
| X-Mailman-Original-Message-ID | <CALv3B7aiTbhpyUL17Eg5prH39EgMP8uSDdD554OdND3LFETAQg@mail.gmail.com> |
| Xref | csiph.com gnu.bash.bug:16172 |
Show key headers only | View raw
It looks like hash_search just does a linear walk if array entries to find elements in a list. This slows down (order N?) new inserts when the number of entries gets large. Would there be any interest in merging a patch to add an option for making this faster (maybe using b-trees?) My analysis here https://eludom.github.io/blog/20200418/ Thanks, ---george jones
Back to gnu.bash.bug | Previous | Next | Find similar
speeding up hash_search? George Jones <fooologist@gmail.com> - 2020-04-19 10:53 -0400
csiph-web