[ivanb]

Balancing trade-off is crucial in software design. It would be nice if the documentation listed the trade-offs of the structures compared to their native implementations. I imagine at least every mutation is consing? There are also larger fixed and slow-growing overheads in various operations.

[aidenn0]

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.

[ivanb]

Btw I meant quasi-mutations of course. So every quasi-mutation conses. Alright.

[guenthert]

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.

[aidenn0]

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.

[gibsonf1]

The newish SBCL parallel gc is fantastic and uses no additional memory during gc

[ivanb]

Big-O is one thing. Big constant factor, heap fragmentation and cache locality are other useful characteristics of data structures.

[aidenn0]

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.

[classified]

What do you call the "native implementations"? Assembler has no container types.