From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED.blaine.gmane.org!not-for-mail From: Alex Gramiak Newsgroups: gmane.emacs.devel Subject: Using SMALL_LIST_LEN_MAX for memq and list_length (was: [RFC] Some new vector procedures (vector-{memq, apply, to-string, ...})) Date: Sat, 20 Apr 2019 21:01:13 -0600 Message-ID: <8736mc6ozq.fsf_-_@gmail.com> References: <8736md90v0.fsf@gmail.com> <83lg05b1jk.fsf@gnu.org> <87lg047h9n.fsf@gmail.com> <83y344a97a.fsf@gnu.org> <87bm107d7q.fsf@gmail.com> <83tvesa3w1.fsf@gnu.org> Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" Injection-Info: blaine.gmane.org; posting-host="blaine.gmane.org:195.159.176.226"; logging-data="262829"; mail-complaints-to="usenet@blaine.gmane.org" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.2 (gnu/linux) Cc: Eli Zaretskii , emacs-devel@gnu.org To: Paul Eggert Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sun Apr 21 05:06:19 2019 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([209.51.188.17]) by blaine.gmane.org with esmtps (TLS1.0:RSA_AES_256_CBC_SHA1:256) (Exim 4.89) (envelope-from ) id 1hI2o7-0016EH-1Z for ged-emacs-devel@m.gmane.org; Sun, 21 Apr 2019 05:06:19 +0200 Original-Received: from localhost ([127.0.0.1]:48131 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1hI2o5-0007dQ-SH for ged-emacs-devel@m.gmane.org; Sat, 20 Apr 2019 23:06:17 -0400 Original-Received: from eggs.gnu.org ([209.51.188.92]:58955) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1hI2ny-0007ck-0U for emacs-devel@gnu.org; Sat, 20 Apr 2019 23:06:10 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1hI2jE-00052k-1A for emacs-devel@gnu.org; Sat, 20 Apr 2019 23:01:16 -0400 Original-Received: from mail-pg1-x533.google.com ([2607:f8b0:4864:20::533]:37871) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1hI2jD-000524-OF; Sat, 20 Apr 2019 23:01:15 -0400 Original-Received: by mail-pg1-x533.google.com with SMTP id e6so4316333pgc.4; Sat, 20 Apr 2019 20:01:15 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:references:date:in-reply-to:message-id :user-agent:mime-version; bh=PyeghYQ2Qi217gbc2BrW0V4se5plV8QLztsybT+z/hw=; b=GodiJzoZS0OTOxnNvvr4ucrYStNGnCsCrZf6Q9z0q7sJB0MEcrboN5bM3uf7QAuCtE dI0p8bcSbbXhZSxNNQtsg/xxohHsVtdwgSrBRoE+inSxPO6ST83jxCxaL+JDnWSHYRh4 Zt0O6JUw8iLIuktDTo9Ifg0Fpe0HSacEa9it8ouqCKzMRcUYSVBH08AAMXCWCp+b/nrw 1WV09MF+iF/6+3d5SMGdV1JKQOdWroTmVXHCebxIyJf0uAE69qeGpmky5qf2cLRw95na v/9ziFpGpmQXrXUawOze+Kx6CbnzWvQ0+cLUtQPBwaqj7Md2eL/+sXJfesAaW3MpI8jW gM9Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:references:date:in-reply-to :message-id:user-agent:mime-version; bh=PyeghYQ2Qi217gbc2BrW0V4se5plV8QLztsybT+z/hw=; b=ZPjqAORnC038xHoOm/LyJQ8BfC3K1TsvHdn+MTnN1/yglEzOVP7IcxVnJsLLXFu75y yMx0ZiBCYuJ616iievIDrBjaYiqxvkaAPp5cSDoAtkxfGRt87lHONJfA/4VLff2vmElJ 1HxG9zqgY8Go5sf97XVos2V3togmlJql9DEqTMOER1Z2732uHZFtkljouIgrq5Lf+ciZ 5N06F+dKNDhnO6PPnxoFSjHB3uFrENFcQX9My5i+VjXoyinJQt+Ai7v+/wBY8iAsAAkP qC5NF6/kW9V0Lx8Hv/WUOypNgrdJ+jxQTCsiu6xOQqIgfAtYAD7WGroeTKrtvNVTVbW2 GkVg== X-Gm-Message-State: APjAAAWYqjsqHTgxgRT893OufxMb3v7KelHo2I0AsxyHFH+OMzDmQDry +gAKm8qlNNhpzFDaeXgzheaNFMZl X-Google-Smtp-Source: APXvYqzLa7UuCC0glwTMJWIUtix/M+J393NOZLV69vLHD6hDdGqzbD4UN3yoPj3ykvM3TQiGqtyDpA== X-Received: by 2002:a63:f64f:: with SMTP id u15mr3673815pgj.192.1555815673744; Sat, 20 Apr 2019 20:01:13 -0700 (PDT) Original-Received: from lylat ([2604:3d09:e37f:1500:1a72:4878:e793:7302]) by smtp.gmail.com with ESMTPSA id 17sm15917318pfw.65.2019.04.20.20.01.11 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Sat, 20 Apr 2019 20:01:12 -0700 (PDT) In-Reply-To: (Paul Eggert's message of "Sat, 20 Apr 2019 15:54:50 -0700") X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 2607:f8b0:4864:20::533 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:235723 Archived-At: --=-=-= Content-Type: text/plain Paul Eggert writes: > We could probably speed up the cycle checking somewhat, but that's a different > topic. On that topic, I recently tried using SMALL_LIST_LEN_MAX for memq and list_length similarly to nth/elt. WDYT? For small lists it seems to be faster, but for longer lists it seems to be slower (maybe that's due to the branch predictor in my simple benchmark-run-compiled tests). --=-=-= Content-Type: text/x-patch Content-Disposition: attachment; filename=memq-small.diff Content-Description: memq diff --git a/src/fns.c b/src/fns.c index c3202495da..267bd2c40f 100644 --- a/src/fns.c +++ b/src/fns.c @@ -1557,9 +1557,18 @@ The value is actually the tail of LIST whose car is ELT. */) (Lisp_Object elt, Lisp_Object list) { Lisp_Object tail = list; + for (int i = 0; i < SMALL_LIST_LEN_MAX; ++i, tail = XCDR (tail)) + { + if (!CONSP (tail)) + goto end; + else if (EQ (XCAR (tail), elt)) + return tail; + } + FOR_EACH_TAIL (tail) if (EQ (XCAR (tail), elt)) return tail; + end: CHECK_LIST_END (tail, list); return Qnil; } --=-=-= Content-Type: text/x-patch Content-Disposition: attachment; filename=list_length.diff Content-Description: list_length diff --git a/src/fns.c b/src/fns.c index c3202495da..b7f25d4cba 100644 --- a/src/fns.c +++ b/src/fns.c @@ -97,6 +97,11 @@ ptrdiff_t list_length (Lisp_Object list) { intptr_t i = 0; + for ( ; i < SMALL_LIST_LEN_MAX && CONSP (list); ++i, list = XCDR (list)) + ; + if (i < SMALL_LIST_LEN_MAX) + return i; + FOR_EACH_TAIL (list) i++; CHECK_LIST_END (list, list); --=-=-=--