]> git.eshelyaron.com Git - emacs.git/commit
Speed up (nthcdr N L) when L is circular
authorPaul Eggert <eggert@cs.ucla.edu>
Mon, 20 Aug 2018 22:52:29 +0000 (15:52 -0700)
committerPaul Eggert <eggert@cs.ucla.edu>
Mon, 20 Aug 2018 23:01:31 +0000 (16:01 -0700)
commiteb83344fc7c08ec08b51e7700f1ac2632afa462c
tree69c96f89acf42957ed98dc7ce189cb49d04abecd
parent36de7bd7b0b9fcd038c440b4705e9186bfbaaa41
Speed up (nthcdr N L) when L is circular

Also, fix bug when N is a positive bignum, a problem reported
by Eli Zaretskii and Pip Cet in:
https://lists.gnu.org/r/emacs-devel/2018-08/msg00690.html
* src/fns.c (Fnthcdr): If a cycle is found, reduce the count
modulo the cycle length before continuing.  This reduces the
worst-case cost of (nthcdr N L) from N to min(N, C) where C is
the number of distinct cdrs of L.  Reducing modulo the cycle
length also allows us to do arithmetic with machine words
instead of with GMP.
* test/src/fns-tests.el (test-nthcdr-circular): New test.
src/fns.c
test/src/fns-tests.el