Birbla

Join the discussion

Write your take first — we'll ask for email only when you're ready to publish.

Sign in
  • Hacker News
  • Did you just say "just"?

    Used to be a common refrain when we were whiteboarding new features. Usually as a check on somebody's overly ambitious thinking.

    I counted 23 "just"s in the article. Bravo. Sometimes you have to _just_ plow ahead.

    by agtilden
  • > The thing is, all of our nodes are pointing to each other inside this memory block. When we realloc it with an increased size, it might get moved to a new memory address. Completely breaking all of our pointers and causing a segfault! How do we tackle this problem?

    Store indices into the arena array? You could probably even use 4-byte indices and cut down the memory usage...

    > Fib(40) literally took 12+ GIGABYTES before hitting an OOM and crashing. Why? Because it spawns approximately 1.3 Billion nodes.

    Okay, maybe you can keep 8-byte indices.

    > The mark-and-sweep garbage collector we just completed is a stop-the-world garbage collector. And the algorithm we’re running is inherently exponential.

    How about a copying collector then? The recursive Fibonacci generates a lot of garbage but IIRC its live set is actually pretty small at any single point of time. If you need a benchmark for GC when your function actually has a huge live set, then something like

        def garbage(n):
        if n == 0:
            return None
        return (garbage(n-1), garbage(n-1))
    should do the trick; if you don't have proper data structure you can simulate it with closures pretty trivially.

    > And we can do something about how we’re evaluating fib itself

    You mean "switch from recursively walking AST" or "write a non-exponential Fibonacci"?

    by Joker_vD
  • Nice, I like this style of exposition. "Let's do this one thing -> well, shit -> (loop)". Term rewriting (graph reduction as you've said) is evaluation.
    by winwang
  • I don't have it handy but in uni I was responsible for the Excel formula parser in a group project. I agonized over it for like six days until it suddenly clicked that I could just do a bunch of string matching, and rewrite the formula over and over again until it was a number.

    More precisely, I had figured out how to parse an Excel formula (keeping track of braces and commas, I recall!). For the actual math symbols, all I had to do was rewrite them as Excel formulas!

    3+6*2 -> 3+MUL(6,2) -> ADD(3,MUL(6,2))

    In order of precedence. And then just evaluate the resulting formulas inside-out:

    ADD(3,MUL(6,2)) -> ADD(3,12) -> 15

    It somehow ended up being a thousand lines of code. Another guy doing the same assignment told me he did it in 50 with regular expressions.

    In retrospect, what I did reminds me of hammering in a nail with a screwdriver.

    I ended up revisiting the idea later (just the math parser, no ADD() syntax) and it was much nicer, like 30 lines of JS (no regex either!). (Well, you can do it in one line with eval, but yea :)

    by andai
  • > Overall, I built a Graph Reduction engine

    I did the same for my performant implementation of pure functional programming language BLC/BLC2, which in 400+ lines contains a graph reduction engine for combinatory logic, to which the lambda calculus programs are converted by Kiselyov's bracket abstraction algorithm.

    [1] https://github.com/tromp/AIT/blob/master/uni.c

    by tromp
  • The "how to implement a hash table" article https://benhoyt.com/writings/hash-table-in-c/ was really helpful for me. I thought that hash tables were something that were basically impossible to make in C, but this showed that it was simpler.
    by ancientstraits
  • This reminds me of decades ago when ...wait, I was still writing code like three years ago.
    by gnarlouse
  • Greenspun's tenth rule of programming:

    > Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp.

    by CodesInChaos

Explore Birbla archives