It does pretty well considering the obstacles holding it back, garbage collection and implicit typing are rather hefty lodestones to work around, but Chez has a quite sophisticated compiler which can do some impressive optimizations. Of course certain Common Lisp implementations like SBCL still outshine Chez, but for a Scheme implementation it's rather impressive.
Of course if you want something really fast you let a genius who knows the target system inside and out write some hand-optimized assembly, but for a program that only needs to run once (or that has no direct or indirect connection to an end user) Chez is roughly fast enough.
On carefully-written programs on some domains with full optimization, both Chez and Gambit have been observed to produce object programs that run at speeds comparable to those of their C equivalents. This isn't new. I think it was Guy Steele who observed circa 1970 that some Maclisp programs ran faster than Fortran equivalents.
Another "post-modern" natively compiling Scheme is Gerbil Scheme [0]. It's seeing a lot of attention/enhancements lately, including some bounties to implement features.
Thanks - worthwhile features for sure and being decentralized.
I was hoping to find that information on the site itself, I was looking for an about page or similar. Couldn't find it. Hence why it was confusing for a first time user. Or maybe I just missed it.
I think it's because people (rightfully) associate interactive programming with Lisp, and (wrongfully) associate interpreting with interactive programing, since loading compiled machine code into a running program is foreign to most people who do not use Lisp.
Chez Scheme outperforms Gambit in the benchmarks cited in a commment above.
Chez Scheme has a few interesting features that most compilers do not have, for any language:
"A source file can also be precompiled into a stored binary form and automatically recompiled when its dependencies change. Whether compiling on the fly or precompiling, the compiler produces optimized machine code, with some optimization across separately compiled library boundaries. The compiler can also be directed to perform whole-program compilation, which does full cross-library optimization and also reduces a program and the libraries upon which it depends to a single binary."
I am not a big direct Chez Scheme user, so that was news to me. Thank you! There is this tool that apparently makes it easier and creates a single file.
A few years ago Racket switched to using Chez for its implementation. The lead for Racket (Matthew Flatt) seems pretty happy with the new Chez base: he and the team were able to reduce the total amount of code while at the same time improving performance. Here's the experience report from a few years ago:
1) Clojure is secretly a compiled language. A lot of routine errors in Clojure dev are compiler errors.
2) Clojure aims for super-native performance. Immutability in practice gives weird benefits. The obvious example is copying a large object but making a small change. As a native operation in C that is very expensive. In Clojure, the cost is roughly equivalent to the cost of making the small change, because the structure of the big object can be safely reused (everything is immutable, why not?). It enables completely different styles of coding, it is a very practical benefit of Clojure.
To drill down into this, adding or removing from a vector or hashset in clojure is O(logn). This also means that random access is also O(logn).
Most operations on clojure persistent data structures are an order of magnitude less efficient than they are on the mutable equivalents, excepting a full copy which free due to it being unnecessary.
> Most operations on clojure persistent data structures are an order of magnitude less efficient than they are on the mutable equivalents
It's not really clear what you mean by "order of magnitude" here. The notation you're using suggests that you're thinking in terms of asymptotic algorithmic resource requirements, which are most often characterized by polynomial degree; an order of magnitude ("factor of 10") is invisible in those terms.
But a factor of log n, while not invisible, is nearly so. If you're thinking in terms of polynomial degree, a factor of log n is literally an infinitesimal value - it's more than 0, but less than all positive real numbers.
Hickey has made the point that in real world (not asymptomatic) uses, the constants and depths make a difference he cares about. 10x takes seconds to a minute.
Only in theory, with branching factors of 32, they are not remotely equivalent unless you have a supercomputer counting atoms in a universe or something.
You know this would mean that a change to a vector under 32 elements is O(n) right? (Which it isn't quite in all cases, because the actual implementation is a bit more complex)
But this doesn't apply to hashset because hashmaps are sparse, and stored as pairs, meaning that they're effectively base 16. Also the clojure implementation of sets is just hashmaps where the key is the same as the value.
> You know this would mean that a change to a vector under 32 elements is O(n) right?
Technically true, but only because a change to a vector of under 32 elements is O(1) by definition (as long as the algorithm is deterministic) and O(n) includes O(1). It's equally true that a change to a vector of under 32 elements is O(n!).
The notation you're using is not meaningful in the context of bounded input. Big-O notation is not concerned with any behavior except the behavior at infinity.
This is not generally the case. Practically speaking, big O notation is almost always bounded. The clojure vector implementation has a maximum count of 2^32, therefore the behaviour at infinity is O(SomeException)
An order of magnitude is not necessarily a factor of 10. Otherwise we would always just say, "factor of 10" which has fewer syllables. The difference between O(logn) to O(1) is often referred to as an order of magnitude. As is O(logn) to O(n).
I taught algorithms and data structures a lot. We never referred to differences in complexity as orders of magnitude, though you might say that Algorithm A's running time differs from B's running time on the same data by an order of magnitude.
Also, the point about logarithmic time is that it grows much more slowly than even linear time: log2(128) is only 7, and log2(1024) is only 10.
> The difference between O(logn) to O(1) is often referred to as an order of magnitude. As is O(logn) to O(n).
That isn't good usage, but there was enough context in your comment to guess that that was what you meant.
The main problem I was pointing out is that the difference between O(log n) and O(1) is much, much, much, much, much, much smaller than the difference between O(log n) and O(n), so it doesn't make sense to describe those two differences the same way.
I am with you on the point about order of magnitude but I don’t understand what you mean by log n being smaller than all positive real numbers. We are talking about asymptotics, since we are talking about O(f(n)) for some function f, right? Doesn’t log n go to infinity then since n goes to infinity?
Mostly we worry about algorithms that can run in polynomial time. It's easy to show that when m < n, xᵐ = o(xⁿ), and that when a polynomial's degree is n, the whole polynomial is O(xⁿ), and this leads us to divide up the polynomial-runtime space according to the degree of a representative polynomial. It's very normal to talk about "linear" time requirements -- meaning ϴ(x¹), "constant" requirements [ϴ(x⁰)], "quadratic" requirements [ϴ(x²)], "cubic" requirements [ϴ(x³)], etc. (OK, it's less common to talk about higher degrees, but the concept stays relevant there.)
So once you're thinking that way, you can ask where the function f(x) = log x belongs. It isn't a polynomial, but it is asymptotically limited by polynomials and so it's present within the polynomial-runtime space. If you represented the growth rate of the function f(x) = log x by a polynomial approximation, F(x) = xᵏ, what would the value of k be?
The answer is that k must be a positive value that is greater than zero but less than all positive real numbers, an infinitesimal. If you're calibrated against polynomials, a logarithmic time requirement is "not constant, but so close to being constant that it's impossible to see the difference".
Useful to specify that it is log32N, not log2N since that makes an enormous different in practice.
Also, if you care about that then you can use transients (if no one knows you mutated the data structure then it still counts as immutable) or mutable structures - both of which are pretty simple.
Hmm, when I search racket compilation, the top option is to compile to bytecode. Since the term "bytecode" is used, I thought that was different from Chez's machine code generation?
When I was creating https://github.com/GrantMatejka/rasm I initially wanted to add a Wasm target to the Chez Scheme backend for Racket. Ultimately didn’t work out, but the paper goes over the process a bit
60 comments
[ 4.0 ms ] story [ 277 ms ] threadOf course if you want something really fast you let a genius who knows the target system inside and out write some hand-optimized assembly, but for a program that only needs to run once (or that has no direct or indirect connection to an end user) Chez is roughly fast enough.
Meh, my genius works at electro magnetic level. His mum works at the quantum level but she is outside our budget
On carefully-written programs on some domains with full optimization, both Chez and Gambit have been observed to produce object programs that run at speeds comparable to those of their C equivalents. This isn't new. I think it was Guy Steele who observed circa 1970 that some Maclisp programs ran faster than Fortran equivalents.
[0]: https://cons.io
https://www.call-cc.org/
It compiles to C, and from that to binary program
Minor Gerbil version as an example. (export main)
(def (fib n) (if (fx<= n 1) n (+ (fib (fx- n 1)) (fib (fx- n 2)))))
(def (main) (display (fib 47)) (newline))
Compiled with gxc -O -exe -o gerbil.fib
Similar results on x86_64
Anyway, would have been nice for the article to link to Chez Scheme's project page, which seems to be this one:
https://github.com/cisco/ChezScheme
Also not clear why should folks use Chez? The article barely covered the why or what successful apps have been written in Chez.
YakiHonne is a Nostr-based decentralized content media protocol, which supports free curation, creation, publishing, and reporting by various media.
https://yakihonne.com/article/naddr1qq2njnfcdpsngu3sdev4wjn3...
I was hoping to find that information on the site itself, I was looking for an about page or similar. Couldn't find it. Hence why it was confusing for a first time user. Or maybe I just missed it.
[0] https://sbcl.org
It's a cultural oddity how strongly people seem to associate them with interpreted code.
If you want native code from Scheme, using Gambit.
User didn't want to talk about Common Lisp.
Other user pointed out that the title of the article says "lisp".
My comment points out that the article also says "scheme".
Scheme is a Lisp. Not all Lisps are Scheme.
Hope that clarifies.
Chez Scheme has a few interesting features that most compilers do not have, for any language:
https://github.com/rschardt/chez-exe
https://ecraven.github.io/r7rs-benchmarks/
A few years ago Racket switched to using Chez for its implementation. The lead for Racket (Matthew Flatt) seems pretty happy with the new Chez base: he and the team were able to reduce the total amount of code while at the same time improving performance. Here's the experience report from a few years ago:
https://users.cs.utah.edu/~mflatt/tmp/rkt-on-chez.pdf
https://en.m.wikipedia.org/wiki/Larceny_(Scheme_implementati...
Are you trying to make a (crime) racket/larceny pun? From what I've heard, they named it Racket because a racket is an organized group of schemers.
1) Clojure is secretly a compiled language. A lot of routine errors in Clojure dev are compiler errors.
2) Clojure aims for super-native performance. Immutability in practice gives weird benefits. The obvious example is copying a large object but making a small change. As a native operation in C that is very expensive. In Clojure, the cost is roughly equivalent to the cost of making the small change, because the structure of the big object can be safely reused (everything is immutable, why not?). It enables completely different styles of coding, it is a very practical benefit of Clojure.
Most operations on clojure persistent data structures are an order of magnitude less efficient than they are on the mutable equivalents, excepting a full copy which free due to it being unnecessary.
It's not really clear what you mean by "order of magnitude" here. The notation you're using suggests that you're thinking in terms of asymptotic algorithmic resource requirements, which are most often characterized by polynomial degree; an order of magnitude ("factor of 10") is invisible in those terms.
But a factor of log n, while not invisible, is nearly so. If you're thinking in terms of polynomial degree, a factor of log n is literally an infinitesimal value - it's more than 0, but less than all positive real numbers.
But this doesn't apply to hashset because hashmaps are sparse, and stored as pairs, meaning that they're effectively base 16. Also the clojure implementation of sets is just hashmaps where the key is the same as the value.
Technically true, but only because a change to a vector of under 32 elements is O(1) by definition (as long as the algorithm is deterministic) and O(n) includes O(1). It's equally true that a change to a vector of under 32 elements is O(n!).
The notation you're using is not meaningful in the context of bounded input. Big-O notation is not concerned with any behavior except the behavior at infinity.
Also, the point about logarithmic time is that it grows much more slowly than even linear time: log2(128) is only 7, and log2(1024) is only 10.
That isn't good usage, but there was enough context in your comment to guess that that was what you meant.
The main problem I was pointing out is that the difference between O(log n) and O(1) is much, much, much, much, much, much smaller than the difference between O(log n) and O(n), so it doesn't make sense to describe those two differences the same way.
Mostly we worry about algorithms that can run in polynomial time. It's easy to show that when m < n, xᵐ = o(xⁿ), and that when a polynomial's degree is n, the whole polynomial is O(xⁿ), and this leads us to divide up the polynomial-runtime space according to the degree of a representative polynomial. It's very normal to talk about "linear" time requirements -- meaning ϴ(x¹), "constant" requirements [ϴ(x⁰)], "quadratic" requirements [ϴ(x²)], "cubic" requirements [ϴ(x³)], etc. (OK, it's less common to talk about higher degrees, but the concept stays relevant there.)
So once you're thinking that way, you can ask where the function f(x) = log x belongs. It isn't a polynomial, but it is asymptotically limited by polynomials and so it's present within the polynomial-runtime space. If you represented the growth rate of the function f(x) = log x by a polynomial approximation, F(x) = xᵏ, what would the value of k be?
The answer is that k must be a positive value that is greater than zero but less than all positive real numbers, an infinitesimal. If you're calibrated against polynomials, a logarithmic time requirement is "not constant, but so close to being constant that it's impossible to see the difference".
(Note that if k is not an integer this isn't really a polynomial.)
Also, if you care about that then you can use transients (if no one knows you mutated the data structure then it still counts as immutable) or mutable structures - both of which are pretty simple.
Apparently Racket Chez will merge into Cisco Chez and all will be well.