Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Modern Common Lisp with FSet

fset.common-lisp.dev

Post reply on HN
Print view View original

21–30 of 30 posts

Re: Modern Common Lisp with FSet

#21

Post by guenthert »

ivanb wrote: post #19
aidenn0 wrote: post #17

Earlier quoted context omitted.

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.

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.

Re: Modern Common Lisp with FSet

#22

Post by jvillasante »

I think the website is weird to navigate. "Next" links go to top-level headers instead of the "logical" next. For example, if I'm on "1.1 Fset Tutorial" clicking "Next" takes me to "1.2 Using Fset" instead of "1.1.1 The Major FSet Types".

At a conceptual level, do these data-structures store what in other languages would be pointers and so every access would mean paying for the pointer indirection or do they store objects themselves and they are cache friendly data-structures?

Re: Modern Common Lisp with FSet

#23

Post by gibsonf1 »

guenthert wrote: post #21
ivanb wrote: post #19

Earlier quoted context omitted.

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.

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

Re: Modern Common Lisp with FSet

#24

Post by classified »

ivanb wrote: post #15

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.

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

Re: Modern Common Lisp with FSet

#25

Post by beepbooptheory »

jvillasante wrote: post #22

I think the website is weird to navigate. "Next" links go to top-level headers instead of the "logical" next. For example, if I'm on "1.1 Fset Tutorial" clicking "Next" takes me to "1.2 Using Fset" instead of "1.1.1 The Major FSet Types". At a conceptual level, do these data-structures store what in other languages would be pointers and so every access would mean paying for the pointer indirection or do they store ob…

I guess this might just be emacs Info-mode bias on my part (and the bias of someone who generally lives inside old documentation like this instead whatever the newfangled stuff is like I guess), but this behavior is precisely what I expect. For "next" to either mean jumping to the next in a sequence or jumping down a hierarchical level, depending on context, seems like "bad design" to me, or at the very least, trying to push the book metaphor to a fault.

The relation of 1.1.1 to 1.1 is about drilling down into detail if you want that, where you can still peruse through at the given upper level.

Picking another random other manual, it is the same: https://www.gnu.org/software/guile/manual/html_node/index.ht...

Re: Modern Common Lisp with FSet

#26

Post by massysett »

jvillasante wrote: post #22

I think the website is weird to navigate. "Next" links go to top-level headers instead of the "logical" next. For example, if I'm on "1.1 Fset Tutorial" clicking "Next" takes me to "1.2 Using Fset" instead of "1.1.1 The Major FSet Types". At a conceptual level, do these data-structures store what in other languages would be pointers and so every access would mean paying for the pointer indirection or do they store ob…

This is how Texinfo (which this uses) works. It's the same if you navigate it with an Info reader: "n" goes to the "next" node, which behaves as you point out.

When I'm reading in an Info reader (almost always in GNU Emacs) I always hit the spacebar when reading. This scrolls down a page and, if it's at the end of a page and, if at the bottom, goes to the next subnode - in other words, what "makes sense." (Actually the binding for this is "Info-scroll-up".)

That doesn't help when you're on a website, but for me Texinfo websites have a distinctive look and when I see them, I immediately know what clicking "Next" will do, and I know to instead go to the bottom of the page and go to the subnodes if that's what I want, which it typically is.

I agree that it's weird...but maybe understanding the overall weirdness of Texinfo helps it all make sense?? A more coherent weirdness?

Re: Modern Common Lisp with FSet

#27

Post by aidenn0 »

guenthert wrote: post #21
ivanb wrote: post #19

Earlier quoted context omitted.

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.

Re: Modern Common Lisp with FSet

#28

Post by aidenn0 »

ivanb wrote: post #18
aidenn0 wrote: post #17

Earlier quoted context omitted.

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.

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.

Re: Modern Common Lisp with FSet

#29

Post by ScottBurson »

jvillasante wrote: post #22

I think the website is weird to navigate. "Next" links go to top-level headers instead of the "logical" next. For example, if I'm on "1.1 Fset Tutorial" clicking "Next" takes me to "1.2 Using Fset" instead of "1.1.1 The Major FSet Types". At a conceptual level, do these data-structures store what in other languages would be pointers and so every access would mean paying for the pointer indirection or do they store ob…

I did think about cache-friendliness and made them as much so as I reasonably could, mostly by trying to minimize levels of indirection; but pointers are inescapably involved, and there are limits to how cache-friendly such data structures can be.

For instance, each CHAMP node is a single CL vector; the header occupies the first few slots rather than being a separate allocated ooject.

Re: Modern Common Lisp with FSet

#30

Post by ScottBurson »

LeCompteSftware wrote: post #11

Just FYI, this section at the end about R6RS Scheme is a little confused: https://fset.common-lisp.dev/Modern-CL/Top_html/Scheme-_0028... Strings are immutable [in Scheme]. Functional point update operations are not provided, presumably out of time complexity concerns, but string-append and substring are provided, and there are functions to convert to and from lists of characters; I guess the idea is that fine-graine…

Why is it too strong to say that functional point update operations on strings are not provided, when you seem to confirm that the supported way to manipulate strings functionally is to convert them to lists first?
Post reply on HN