GNU bug report logs -
#56521
Add 'take' list operation [PATCH]
Previous Next
Reported by: Mattias Engdegård <mattiase <at> acm.org>
Date: Tue, 12 Jul 2022 17:07:02 UTC
Severity: wishlist
Tags: patch
Done: Mattias Engdegård <mattiase <at> acm.org>
Bug is archived. No further changes may be made.
Full log
View this message in rfc822 format
[Message part 1 (text/plain, inline)]
Your message dated Mon, 18 Jul 2022 14:50:52 +0200
with message-id <DB0C601B-A9D3-494B-8B72-48E02520F7D1 <at> acm.org>
and subject line Re: bug#56521: Add 'take' list operation [PATCH]
has caused the debbugs.gnu.org bug report #56521,
regarding Add 'take' list operation [PATCH]
to be marked as done.
(If you believe you have received this mail in error, please contact
help-debbugs <at> gnu.org.)
--
56521: https://debbugs.gnu.org/cgi/bugreport.cgi?bug=56521
GNU Bug Tracking System
Contact help-debbugs <at> gnu.org with problems
[Message part 2 (message/rfc822, inline)]
[Message part 3 (text/plain, inline)]
A basic list operation that is often useful is 'take', that extracts the N first elements of a list. The attached patch adds 'take' as a built-in function.
We already have its complement, `drop`, under the name `nthcdr`. (I wouldn't mind adding `drop` as an alias but it's not very important.)
How would it compare to existing alternatives, or to a pure Lisp implementation? Here are relative timings (smaller is better), sans GC.
N/M means taking N elements from a list of M.
| | 5/10 | 9999/10000 | 1/10 | 1/0 |
|------------+------+------------+------+------|
| take | 1.00 | 1.00 | 1.00 | 1.00 |
|------------+------+------------+------+------|
| seq-take | 4.90 | 3.45 | 5.82 | 4.95 |
| -take | 4.01 | 4.92 | 2.86 | 1.54 |
|------------+------+------------+------+------|
| fwd | 2.89 | 3.76 | 1.77 | 1.25 |
| rev | 2.90 | 3.45 | 2.06 | 1.38 |
| cl-loop | 3.18 | 3.82 | 2.21 | 1.65 |
| butlast | 3.58 | 1.73 | 6.59 | 2.33 |
|------------+------+------------+------+------|
| ntake (el) | 0.80 | 0.20 | 1.51 | 1.40 |
| ntake (C) | 0.48 | 0.41 | 0.83 | 0.99 |
`seq-take` and `-take` are existing implementations from seq.el and dash.el respectively. `fwd`, `rev`, `cl-loop` and `butlast` are
alternative implementations in elisp. `ntake` are elisp and C implementations of a destructive take operation
A common replacement is using `butlast` but as we see that is very inefficient (worse than the table suggests since GC costs are not included). It also doesn't work for circular or dotted lists.
The C implementation would, of course, be used to implement `seq-take` for lists and speed up existing code.
Adding `ntake` as a C primitive is not quite as beneficial since the elisp implementation does fairly well. (I'm not sure why Elisp is actually faster than C in the 9999/10000 case; maybe I made a mistake, or it has something to do with `nthcdr` having its own bytecode). I included `ntake` in the patch for reference and because it's Lisp tradition to have faster destructive 'n-' variants of list functions.
The patch is just a draft; there will be tests and manual text.
There are details that can be debated. For example, we don't error on negative N. It might be useful to allow the compiler to partially evaluate calls where N<2 or LIST=nil.
[take.diff (application/octet-stream, attachment)]
[Message part 5 (message/rfc822, inline)]
> `seq-take` is first in line for a makeover.
Done. Naturally there are many more instances of code implementing `take` and `ntake` in creative ways but those will have to wait.
This bug report was last modified 2 years and 305 days ago.
Previous Next
GNU bug tracking system
Copyright (C) 1999 Darren O. Benham,
1997,2003 nCipher Corporation Ltd,
1994-97 Ian Jackson.