Hacker News new | ask | show | jobs
by aidenn0 54 days ago
1. Each operation lists the big-O complexity; most operations are O(lg N).

2. There are no mutations

3. I think it would be rather redundant to mention that every operation that returns a new object conses.

2 comments

Btw I meant quasi-mutations of course. So every quasi-mutation conses. Alright.
Yeah, clojure gets away with it thanks to the high performance of the available gc in the JVM. In the Common Lisp world the compiler puts quite some effort into avoiding heap allocation ("consing"); the language was designed with that in mind. Not sure where it's now, but not too long ago SBCL's gc wasn't its strong point.
SBCL's gc is historically overly optimized for throughput at the expense of everything else. It also predates common availability of parallel systems. There's a new GC that addresses those things.

That being said, for batch processing in single-threaded applications, the older SBCL gc is actually pretty good.

The newish SBCL parallel gc is fantastic and uses no additional memory during gc
Big-O is one thing. Big constant factor, heap fragmentation and cache locality are other useful characteristics of data structures.
Most lisp implementations use a moving collector of some kind, so heap fragmentation is less of a concern.

As far as constant factors go, this library is a middle ground; they strive for low constant factors in their algorithms, but it relies almost entirely on generic functions, so that alone is going to limit the maximum speed in e.g. tight loops.