4 ms·

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 implem

by ivanb 6mo ago

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 6mo 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.
- ivanb 6mo ago
  Big-O is one thing. Big constant factor, heap fragmentation and cache locality are other useful characteristics of data structures.
  - aidenn0 6mo ago
    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.
- ivanb 6mo ago
  Btw I meant quasi-mutations of course. So every quasi-mutation conses. Alright.
  - guenthert 6mo ago
    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.
    - gibsonf1 6mo ago
      The newish SBCL parallel gc is fantastic and uses no additional memory during gc
    - aidenn0 6mo ago
      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.
classified 6mo ago
What do you call the "native implementations"? Assembler has no container types.

by ivanb 6mo ago

aidenn0 6mo 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.

ivanb 6mo ago
Big-O is one thing. Big constant factor, heap fragmentation and cache locality are other useful characteristics of data structures.
- aidenn0 6mo ago
  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.
ivanb 6mo ago
Btw I meant quasi-mutations of course. So every quasi-mutation conses. Alright.
- guenthert 6mo ago
  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.
  - gibsonf1 6mo ago
    The newish SBCL parallel gc is fantastic and uses no additional memory during gc
  - aidenn0 6mo ago
    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.

classified 6mo ago

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