GNU bug report logs - #56521
Add 'take' list operation [PATCH]

Previous Next

Full log

View this message in rfc822 format

From: Mattias Engdegård <mattiase <at> acm.org>
To: 56521 <at> debbugs.gnu.org
Subject: bug#56521: Add 'take' list operation [PATCH]
Date: Tue, 12 Jul 2022 19:05:54 +0200

[Message part 1 (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)]

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.