From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Pip Cet Newsgroups: gmane.emacs.devel,gmane.emacs.diffs Subject: Re: [Emacs-diffs] master eb83344: Speed up (nthcdr N L) when L is circular Date: Tue, 21 Aug 2018 06:36:06 +0000 Message-ID: References: <20180820230135.12359.43125@vcs0.savannah.gnu.org> <20180820230136.541D8204F3@vcs0.savannah.gnu.org> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset="UTF-8" X-Trace: blaine.gmane.org 1534833330 854 195.159.176.226 (21 Aug 2018 06:35:30 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Tue, 21 Aug 2018 06:35:30 +0000 (UTC) Cc: emacs-diffs@gnu.org To: emacs-devel@gnu.org, eggert@cs.ucla.edu Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Tue Aug 21 08:35:26 2018 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 1fs0GD-0008RK-9d for ged-emacs-devel@m.gmane.org; Tue, 21 Aug 2018 08:35:25 +0200 Original-Received: from localhost ([::1]:51048 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fs0IH-0007Yt-Ui for ged-emacs-devel@m.gmane.org; Tue, 21 Aug 2018 02:37:33 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:54058) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fs0HX-0007Yn-2Q for emacs-devel@gnu.org; Tue, 21 Aug 2018 02:36:47 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1fs0HW-0005xL-9N for emacs-devel@gnu.org; Tue, 21 Aug 2018 02:36:47 -0400 Original-Received: from mail-lf1-x12c.google.com ([2a00:1450:4864:20::12c]:34236) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1fs0HW-0005uu-1W; Tue, 21 Aug 2018 02:36:46 -0400 Original-Received: by mail-lf1-x12c.google.com with SMTP id g9-v6so7503336lfh.1; Mon, 20 Aug 2018 23:36:45 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=iu/If4E+MOoJb+lj9i/9Ui3vrgLljxI4ZeWnQeoZK5A=; b=oopR+Avt0hlWhjpGs+f/twk2iL/Goc91bbZv/WnNs3OVQ7+bg8UwlvjNtsqttmX0RU sGNhq3ZarC2rj4mGsb+fdl+0lPAFIHUVfTlr1+1gGVowHsVb1App+sPpZuNEj07AJSKH zPxfvRgZ3mPnaq8+L9+kDn1ga0O7LPZQg6G2wTtqf74W3sx9FWYBGD0ko+Od7Ud17bD3 Y2yFL4UAVhlz5oz5XIVrnFFp7BK2C+uHK2p2FFvwEZmZrIjZUjFRElmctCxZCOIbbd5f DuHAin352Mc2I1jb3keUbp/YgoX9Z8fhw8KRu0nCW6cbbeloWjhzbHUeiYWCfv752JS8 UpIg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=iu/If4E+MOoJb+lj9i/9Ui3vrgLljxI4ZeWnQeoZK5A=; b=DlYSJaug3GcEPiapzJdVKGEIotjG/90RrdjlvCuJgzm4GEXR2itK2KlLSFAOLUiW2T T06pkO1dkSURzYdQ7qQZ6Br/CTLK034On0u1WULZ4wAQAdNJ0BMtFXFazGkheZw4RpjV rVsNBK0OF29p7XpE6cpWjAUHyUP6goNQiuTfkL9iVsfBmaTMxywyGdlQIfATwIevaf0O wjUCyeT6waURv8fowWZW8NgzzRmL69MwCxxzGaCfOWtGRhYxvG8W0cqmi3VClYK5mG07 OEVlNJcX0I1vNqdbHhX4graJFCT7FwgbGqd0kCpObWGxamDl+FzAF0u1uDQYk2cuipFg 0IxQ== X-Gm-Message-State: AOUpUlGOOokGNXtpqcDRNTofZihxHcYc8iGWmXSucFSlhxi64RxaFYCy Hqab01ZeKIJSY9LUx8SMUQnRPFsbvv4C16qpSEqRr1YA X-Google-Smtp-Source: AA+uWPx4Jbg/84wrOv4KHtGqITMPnhUqfq9D3GqbhTxF1fp6Bc/dJYpqTRsDcLD7DIBcWLJOAGph5OGvSOwhUtrdDxA= X-Received: by 2002:a19:d204:: with SMTP id j4-v6mr30050739lfg.139.1534833404096; Mon, 20 Aug 2018 23:36:44 -0700 (PDT) In-Reply-To: <20180820230136.541D8204F3@vcs0.savannah.gnu.org> X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 2a00:1450:4864:20::12c 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:228778 gmane.emacs.diffs:146725 Archived-At: On Mon, Aug 20, 2018 at 11:01 PM Paul Eggert wrote: > Speed up (nthcdr N L) when L is circular ...but slow it down when it isn't. May I suggest we fall back to the old implementation for small n, maybe n <= 128 or something like that? > + if (tail == li.tortoise) > + tortoise_num = num; I would prefer EQ (tail, li.tortoise) in the condition. > + /* TAIL is part of a cycle. Reduce NUM modulo the cycle length to > + avoid going around this cycle repeatedly. */ > + intptr_t cycle_length = tortoise_num - num; I'm unsure about this line. I might be being stupid, but it seems to me tortoise_num is always num + 1, given the code above: FOR_EACH_TAIL_SAFE (tail) { if (num <= 0) return tail; if (tail == li.tortoise) tortoise_num = num; saved_tail = XCDR (tail); num--; rarely_quit (num); } We exit this loop if EQ (tail, li.tortoise), in which case tortoise_num = num + 1, or if !CONSP (tail), in which case we have returned by the time we assign to cycle_length.