Clojurians Log v2

have you tried (fib 35) in clojure? A naive implementation is a classic example of algo design

Actually not really, let me try this real quick, I figured native clojure would be much faster anyway, will check now!

it’s not language execution speed that is the bottleneck

(dotimes [_ 10] (time (fib 35)))
"Elapsed time: 1867.753 msecs"
"Elapsed time: 1729.861959 msecs"
"Elapsed time: 1724.8485 msecs"
"Elapsed time: 1720.11475 msecs"
"Elapsed time: 1781.608542 msecs"
"Elapsed time: 1804.215666 msecs"
"Elapsed time: 1854.636709 msecs"
"Elapsed time: 1814.996458 msecs"
"Elapsed time: 1721.787875 msecs"
"Elapsed time: 1912.959875 msecs"

> it’s not language execution speed that is the bottleneck Can you tell me more? with my limited knowledge, I’d say it’s the repeated structure interpretation that is slow

what’s the definition of fib you are using? i’m wondering how many recursive calls it makes. possible to make this have 35 calls or 2^35 calls

(defn fib [n]
    (if (<= n 1)
      n
      (+ (fib (- n 1)) (fib (- n 2)))))

(def call-count (atom 0))
(defn fib [n]
  (swap! call-count inc)
  (if (<= n 1)
    n
    (+ (fib (- n 1)) (fib (- n 2)))))
#'user/call-count
user=> 
#'user/fib
user=> (fib 35)
9227465
user=> @call-count
29860703

it’s a lot of work

right! it is indeed

So, fib is not the best comparison benchmark for this right?

it’s perhaps measuring other stuff

here are the callcounts per argument for fib 35

user=> @call-count
{0 5702887,
 7 514229,
 20 987,
 27 34,
 1 9227465,
 24 144,
 4 2178309,
 15 10946,
 21 610,
 31 5,
 32 3,
 33 2,
 13 28657,
 22 377,
 29 13,
 6 832040,
 28 21,
 25 89,
 34 1,
 17 4181,
 3 3524578,
 12 46368,
 2 5702887,
 23 233,
 35 1,
 19 1597,
 11 75025,
 9 196418,
 5 1346269,
 14 17711,
 26 55,
 16 6765,
 30 8,
 10 121393,
 18 2584,
 8 317811}

(fib 2) was computed 5.7 million times!

Ahahaha yeah that is a lot, memoization would solve this, but that’s changing the algorithm and not the runtime

well maybe it is a good jump into your code, but it’s a pretty brutal metric to start with

exactly!

Hummm interesting

the solutions to this are algo changes more than runtime changes. but you are seeing the benefits of the jvm inlining stuff most probably. So levels of optimization that are probably pretty far down your roadmap

Okay, yeah that clarifies things a bit, I should probably stop chasing this rabbit hole for now and come back when I have more knowledge

Thanks a lot for the replies @dpsutton! I appreciate it gratitude

keep doing the project! it sounds super interesting and is just a cheat code to force learning a lot of stuff. ask questions! i enjoyed this as well

Perhaps worth comparing with #squint to see what its raw compiled-to-js performance is...

Great suggestion!! I will do this today! it’s a good opportunity to learn more about squint

Okay I’ve ran a small experiment here @seancorfield A lot of things became clear, the compiled-to-js approach beats my interpreter by a huge margin, and it’s understandable why Looking at https://squint-cljs.github.io/squint/ If you compile just

(defn fib [n]
    (if (<= n 1)
      n
      (+ (fib (- n 1)) (fib (- n 2)))))

globalThis.user = globalThis.user || {};
var fib = function (n) {
  if (n <= 1) {
    return n;
  } else {
    return globalThis.user.fib(n - 1) + globalThis.user.fib(n - 2);
  }
};

vanilla JS           avg: 0.088s 
 squint (compiled)    avg: 0.093s 
 my interpreter       avg: 19.0s 

Any sort of interpreter or VM you build on top of JS is going to run your language much slower than compiling to JS. But as a learning exercise, writing an interpreter, writing a VM, and writing a compiler to either intermediate code (for your VM) or directly to JS, are all good things to do...

Yes this makes perfect sense, I’m learning a ton by building this, but still… it’s kinda hard for me to reconcile the fact that by going through the compiled route we kind of lose a lot of the dynamic properties of the runtime, you can’t just evaluate a user-provided string with a compiled code, load a file on the runtime, we lose the ability to introspect the environment at runtime because all the metadata is gone and to make it really fast like Squint’s approach, we also end up inheriting Js’s weird numeric handling, those unintended coercions start to appear at unexpected places… Anyway, this is just me learning about some hard truths, thanks a lot for taking the time to advice me @seancorfield 🙏 gratitude

Yeah, there's often a trade off between the language you're building and the target host semantics. In some situations that matters more than in others...

i don't have a ton of experience with pl design, but i would suggest Crafting Interpreters by Robert Nystrom, lead dev of Dart and all-around great dude

sounds like you have roughly the first half of the book built (an AST-walking interpreter that is very slow) and then the second half he/you builds a bytecode vm

i don't think it'll answer this specific question for you, but it might expose you to some ideas for how to approach programming language creation/vm design

Now that’s awesome! I will definitely get my hands on this book! Dart is an awesome language Yeah the original question was just to get started talking, I still need to understand what the VM implementation looks like in practice, the book will probably show me something I can use!! Tks for the recommendation!

I happen to be working on a vaguely similar project (compiling Lisp to JS) in Scheme rn and perhaps you would be interested to read this https://www.gnu.org/software/guile/manual/html_node/Compiler-Tower.html @reginaldo.junior696

Nice!! I have never seen this before, great material @bhlieberman93!! First time hearing about guile too At first sight, this seems more advanced than what I currently understand, will take some time to read it carefully, appreciate you sharing 🙏

it's somewhat over my head as well, but I am gradually figuring it out. Guile is an awesome language.