From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Noam Postavsky Newsgroups: gmane.emacs.devel Subject: Re: Binary Search Tree and Treap Functions bst-assq and treap-put Date: Sun, 22 Oct 2017 12:35:30 -0400 Message-ID: References: NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset="UTF-8" X-Trace: blaine.gmane.org 1508690177 20882 195.159.176.226 (22 Oct 2017 16:36:17 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sun, 22 Oct 2017 16:36:17 +0000 (UTC) Cc: Emacs developers To: Stefan Monnier , Andy Sonnenburg Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sun Oct 22 18:36:13 2017 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1e6JEM-00041y-6j for ged-emacs-devel@m.gmane.org; Sun, 22 Oct 2017 18:36:06 +0200 Original-Received: from localhost ([::1]:33576 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1e6JET-0003zr-Hm for ged-emacs-devel@m.gmane.org; Sun, 22 Oct 2017 12:36:13 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:45388) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1e6JDp-0003zj-HY for emacs-devel@gnu.org; Sun, 22 Oct 2017 12:35:34 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1e6JDo-0004om-L9 for emacs-devel@gnu.org; Sun, 22 Oct 2017 12:35:33 -0400 Original-Received: from mail-wr0-x22d.google.com ([2a00:1450:400c:c0c::22d]:45345) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1e6JDo-0004oV-EB for emacs-devel@gnu.org; Sun, 22 Oct 2017 12:35:32 -0400 Original-Received: by mail-wr0-x22d.google.com with SMTP id y9so2914961wrb.2 for ; Sun, 22 Oct 2017 09:35:32 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:sender:in-reply-to:references:from:date:message-id :subject:to:cc; bh=4nxDkodAFJQWc23f8XgML6WWpMeb75c5pqtD5ew4pnI=; b=BdyxHxX8hgRATP9qng9VydX3cbShwjTQDuMcESu5tsl52/xdLmruQstLmDd2zBztol okYSsfT5A8yiKSEvbnkIaml4p1cseH8SiuowGVHW5UDILeIdSDmD6sF6BM7/o9YkBvVl KuQKrvsJTI/X/3ey+Rf4DGlaE3+l9WJ6mCI3nObXVW4cg28BKuWq9zzmtvDCOEijpIlc 4O0yFp0gV46mUCEWZ9XNaYclmR+YzV88RIaaJaLLOVnNoS1dzt9jlKrNLJLkG7RjtYqD OwMoIL03aicGN0HLRL5EbZkWIA5I3dksI6kPZgdQIc9iLdNhyFC5cOIjDqmHe5M8JcIn VmIg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:sender:in-reply-to:references:from :date:message-id:subject:to:cc; bh=4nxDkodAFJQWc23f8XgML6WWpMeb75c5pqtD5ew4pnI=; b=oUKwF15aLtE9fCeX+crHb8ZNS0LwAmp8hR8M3s/Bv7Xyg43tC11Y0c1f75DG3P0u8I RvYZIsB+aZ+kgWCIUwNaOV0grQhY2kGwH4ZroHp/5F6w0zalWoFbfB2+dUtEq5h1tcEo NAY0Ru/sWtj7VtmehbsKL6KjD7wGvQp12AdxaRvT2dgZ6K6qq7SADyPOC9BhtqT5SwD+ fUpBWxFx7tUEIyCVlSVHuIWRv14Jm+DxgPMpDZU5pLxSYb7wXZifRuApYZbdXsdn882l /Ut8DgqDVknK/YVxL3o88aVVc4D6aOAXcYlEMxIM9MUw6pIx3y2tWg6G53d0mZ0wchXx 5zRQ== X-Gm-Message-State: AMCzsaVUwpoxtezxafbjQhNvW8aTa5PDvab0wW/bRjWuz6VFihKMTqRh zvSh3agpWOPLN/+UiHC0MmfkcZHU1FGzocB+LoA= X-Google-Smtp-Source: ABhQp+T4BI0bJKDKj6+Yga7U/q3jVODUEerih54bxK+CYGOncSfRIwAX9pYRyMCs5pafeAz+3j/lWUDJLXu3TfNNSYQ= X-Received: by 10.223.133.142 with SMTP id 14mr6932819wrt.94.1508690131455; Sun, 22 Oct 2017 09:35:31 -0700 (PDT) Original-Received: by 10.223.146.227 with HTTP; Sun, 22 Oct 2017 09:35:30 -0700 (PDT) In-Reply-To: X-Google-Sender-Auth: kxwkyjdxwqHJ72Ffl4aBfCLS-Ew X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 2a00:1450:400c:c0c::22d X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.org gmane.emacs.devel:219678 Archived-At: On Sat, Dec 3, 2016 at 11:33 PM, Stefan Monnier wrote: >> now. I intend to use these functions to make lexically-scoped variable >> lookup average case O(log(n)) instead of the current O(n). > > AFAIK it's O(1) currently (for byte-compiled code only, but performance > of non-byte-compiled code should be of no importance). There is one case where interpreted code performance matters: during boostrap. I wonder if bootstrap-emacs could load these functions as a module to make bootstrapping with .el files go faster...