Fast Sequence Iteration in Common Lisp
6 days ago
- #Sequence Iteration
- #Performance Optimization
- #Common Lisp
- Common Lisp sequences are either linked lists or vectors, providing a unified interface for operations like search and deletion.
- The two main interfaces for sequence iteration in ANSI Common Lisp are `elt` + `length` + `loop` (slow for lists) and `reduce` (handles keywords but has overhead).
- The `do-sequence` macro is introduced to optimize sequence iteration, supporting keywords like `:start`, `:end`, `:key`, `:with-index`, and `:with-raw-elt`.
- Benchmarks show `do-sequence` outperforms `reduce` in speed across different implementations (SBCL, CCL, ECL, CLISP) and sequence types (lists, vectors).
- Performance gains are significant, especially for lists, with improvements ranging from 10% to over 200% depending on the implementation and use case.
- The `do-sequence` macro is ANSI CL compliant and can be used under the Zlib license, but be cautious of code bloat and compilation slowdown due to deep specialization.