I am soooo tired of that quote. Especially because it’s BS. In 30+ years in the industry, I’ve never seen it happen. Not once. And I’ve never seen anyone demonstrate it convincingly on a real, large-scale commercial project either.
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.
When I was in university, hash tables were definitely among the things we had to learn about and then implement in C, probably in first year. Per Wikipedia, the concept dates to 1953 (with an implementation in assembly); of course people made them in C once that was an option.
I always liked that idea of just doing a linear wrap-around sweep through an array that holds (key, value) pairs, until you find the pair with the key you're looking for (for 'get' or 'contains?') or an empty spot (for 'put'). The trick to make this fast is that the hash function (key -> int) tells you at which index to start the sweep.
No secondary data structures, super simple to implement, and it works great for small use cases.
This isn't great though if you need to find out if an element exists in the table, and you have the ability to remove elements from it. I suppose you could optimize the hash table after deletions, but that again would be slow.. ?
Btw, this reminds me a bit of Cuckoo hashes. Never used them but seems like a nice idea.
The expected or amortized complexity of the standard hash table operations (put, get, contains, remove) are all O(1) for linear probing (under the usual assumptions for the hash function and as long as the table does not get too full). Of course that doesn't shield a single operation from being O(n) in the worst case.
The standard hash table has buckets, though, not just a single array that is probed through in case there's no space for a value in the slot determined by the hash function?
Right, that's the beauty of this simple approach: there's only one array and it doubles as the storage for buckets. But yes, the table will have a maximum size after which you cannot add more entries. That is, in practice you would create a new hashtable with a larger capacity and rehash all the existing entries into the new, bigger table (in practice, you would do that even sooner than that, namely when a certain load factor is passed - see my previous comment where I alluded to the role of the load factor).
The cool thing, however, is: if the size of the new hashtable is double the size of the old hashtable, your amortized insertion costs are still only O(1)!
(And you don't just have to take my word for it: take my original comment and paste it into the AI interface of your choice and have it create a concrete implementation. Ask it to add a remove operation, and an automatic doubling of the array size + rehashing when the table reaches a load factor of, say, 0.7 -- the resulting code should be very manageable, and then you can run your own tests and measure times!
This is maybe not the smartest way to do hashing, but its appeal lies in its simplicity and hence compactness of implementation. There are many cases where you don't even need a 'remove' operation, and where you never have to worry about growing the array because you know that you're only ever going to hash a certain number of elements at most.)
Let's say we have removed all elements from the hash. Then all following contains -calls will need to be O(n), if I understood correctly? They need to check every slot in the array to confirm inexistence, rather than just one bucket.
There are different ways on how to implement remove, but one way to do it is to overwrite the (key, value) pair to be removed with a special "tombstone" symbol that is different from null. Another way is to shift all elements with the same hash value as the one to be removed one index to the left, and null the final position.
There are cases where contains or get would have to iterate over the whole array, basically when all the previously added elements hash-collide, i.e., are mapped to the same start-index. But every hash-implementation has pathological cases where the access methods get slow -- but if the keys are sufficiently random, you don't expect such cases to occur in practice.
If hash tables were impossible to make in C, then it would be impossible to make them in Python, because it is a higher level language than C.
(Almost by definition, anything doable in a higher level language is doable in a lower level language, but not necessarily vice versa. In fact, many higher level languages are themselves written in lower level languages, e.g. Python is written in C.)
But Python has got dicts built into it, which are nothing but hash tables, and they are almost certainly written in C.
Google for some videos by Raymond Hettinger about Python dictionaries.
Or look at the source code of the Python interpreter.
> But Python has got dicts built into it, which are nothing but hash tables, and they are almost certainly written in C.
In CPython they are written in C (at the moment). Other Python implementations are written in other languages.
> (Almost by definition, anything doable in a higher level language is doable in a lower level language, but not necessarily vice versa. In fact, many higher level languages are themselves written in lower level languages, e.g. Python is written in C.)
It depends on what you mean by 'anything doable'. Eg Haskell compilers can in principle do lots of crazy optimisations that a C compiler would not be able to safely do, just because they don't have enough information. Even more so for Lean compilers, which can _know_ which of your loops are terminating, instead of making crude assumptions like C compilers.
Btw, higher level languages being implemented in lower level languages is mostly something for interpreters. Writing a C interpreter in Python is pretty much futile, if you care about speed. But writing a C compiler in Python is perfectly fine. And writing a Python compiler in Python is also fine. Many languages self-host (at least some of) their compilers.
The article says the last release of Jython was 2 years ago. I wonder how much it is used these days. It did seem like a good idea when it was first released. I had only tried it out a little at that time.
>It depends on what you mean by 'anything doable'. Eg Haskell compilers can in principle do lots of crazy optimisations that a C compiler would not be able to safely do, just because they don't have enough information. Even more so for Lean compilers, which can _know_ which of your loops are terminating, instead of making crude assumptions like C compilers.
Interesting. What are some of those optimisations that Haskell and Lean can do, that a C compiler would not be able to safely do?
A very simple one: in Haskell the compiler has knowledge about which functions cause side-effects and which don't. The compiler can skip calling pure functions whose return value ain't used; similarly, the compiler can call a pure function multiple times, instead of saving the return value in memory.
The Haskell compiler can also fairly freely re-arrange in what order things are computed.
A fairly common idiom in Haskell is to just return a tuple of two values, if they are 'thematically' linked; even if computing one is much more expensive than the other. The compiler is smart enough, to only compute one of the values, if you only use one of them. (When I say 'tuple', it could be literally (a, b), or it could be in a struct or whatever.)
Lean knows even more about your code, so you could do more optimisations. But you need to ask Claude for details, I haven't used it as much nor thought as much about it.
IIRC, the first edition of the book "The C Programming Language" (aka K&R), by Kernighan and Ritchie, had a simple example of how to create a hash table in C, including with buckets to handle collisions. It was a simple algorithm. It simply added up the ASCII values of all the characters in the key, modulo some number.
Yeah it's a strange assumption, as this was taught in basic data structures class years ago and any language can implement any data structure, technically speaking. C especially is a weird assumption because lots of foundational software is written in C including hash tables.
Arrays are hash tables. You can implement a very simple hash table from a tutorial, but can you implement a sophisticated one? What about a concurrent hash table?
Yeah, I'm pretty sure we made hash tables in the first C class I took in college in my second semester freshman year. If you can make a linked list, and then make an array of them, and a function to map keys to array indexes, you have a hash table. Whether it's actually performant is entirely a separate question, but a naive hash table is still a hash table.
Hash tables are awesome. They are both an incredibly simple data structure and a seriously deep rabbit hole. Most of the complexity comes from collision resolution [1], and how you handle resolution largely determines what kind of hash table you have. There are at least dozens of collision resolution approaches. The simplest, and probably the one you implemented in your undergrad C class was open addressing. That’s also what I implemented as an undergrad. But there are many more approaches, some quite a bit more complicated, and many of them let you continue to shave off asymptotic costs when you run collision resolution, or they improve locality for typical lookups, allowing better cache utilization, etc. Hash tables are super fun to play with, and for full effect, you really do need to implement them in something like C.
I only skimmed the linked article, but I do wonder whether the author ever realized that they needed to think about scope rules. I searched for the word “scope” but never found it. Closures seriously complicate language design and things get painful and counterintuitive unless you use lexical scope (or… you know… you like pain).
Yeah, I learned about a bunch of the other algorithms later (forgetting the names, but stuff like "move to the next slot rather than putting collisions into buckets" and "hash a second time if you hit a collision"; I'm sure I'm forgetting some of the nuances).
> Closures seriously complicate language design and things get painful and counterintuitive unless you use lexical scope (or… you know… you like pain)
Well if you like both lexical scope and pain, there's always lisp!
You might end up founding one of the first e-commerce sites, sell it for a handsome payday, and then create the first startup accelerator and make insane amounts of money while transforming the industry.
Maybe in JavaScript... but there is a topic called datastructures, where arrays are arrays, and hashtables are hastables. If people say this without a flip of an eye I'm not surprised why people write stuff like
> I thought that hash tables were something that were basically impossible to make in C
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.
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 :)
> 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"?
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.
I once invented a programming language where EVERYTHING was an object. No message keywords. 1 is an object. + is an object. You can send an object to another object - you get back an object. Example 1+ is an object. Its is the result of sending + to 1. If you send 1+ the object 1, you get 2. If you send 1+ the object + you get a run-time type error. You can also go left to right. +1 is an object. If you send +1 to 2, you get 3. It gets nice when you add list objects. (1,2,3,4,5)+1 => (1+,2+,3+,4+,5+) 1 => (2,3,4,5,6). And so on.
Yeah, the Smalltalk and Self family take this "everything is an object" approach, sometimes to extremes.
Another relatively well known language in this space for its use as an alternative to especially Lua in embedding situations is Io: https://iolanguage.org/
It does. Parenthesis are allowed - they are syntax for lists so that a * (b + c) will compute the contents of the list before sending the resulting object to a*. The inspiration is the idea of Currying in Lambda Calculus, although it requires postfix notation. Now you have me thinking about whether I could alaso make parenthesis and commas into objects. So (1+2) for example for do this: ( is sent the object 1. That yields the object (1 That is, an object that is not ready to be sent on. The "(" bounded object would only be released when it received a ")". Thanks for the thought!
It's tempting to go down the rabbit hole of getting creative with
memory management as the author does, and maybe worthwhile for
educational purposes, but has anyone here observed any noticeable
performance gain from it? My impression is that libraries like
mimalloc and tcmalloc are painstakingly optimized by specialists and
unlikely to benefit from any casual embellishments beyond using the
supported malloc and free functions for everything. What does the HN
braintrust recommend?
In my experience, it depends. 99% of the time, malloc/free is your best bet: fast enough, battle-tested, everything already uses it, etc.
In the 1%, though, you'll have needs that malloc/free don't fit. Complex object graphs don't really have a single point of ownership or requiring that you free something in all the places that it might be released is too much to handle. In this case you can reach for a garbage collector (including, for example, implementing reference counting). Other times, you may need to make a lot of allocations in a short time where they can all be freed at once. Request processing in a network server is a common example of this: once the request is complete, everything allocated can be dropped, and you generally want minimal latency.
All of this comes with tradeoffs, though. With a GC, you lose predictability and performance changes; sometimes for the better and sometimes for the worse. Depending on the GC, you may not be able to have stable pointers, and you may lose the ability to finalize objects. With an arena, you can't free or reallocate, so you need to scope the arena to a small region of execution (this is where the author went wrong, for example).
Finally, regardless of which approach you use, you're going to need to thread the allocator through the application; probably implement your own datastructures, etc. Depending on how complex your memory management model is, you may need more than one allocator at any given point (e.g., a GC for the persistent data and an arena per connection and per request). If you're implementing your own allocator, you'll also likely have bugs, and allocator bugs tend to be insidious and obnoxious to debug.
If you can avoid going down that route, I recommend it. Sometimes, though, you have enough constraints that you need to brave the jungle.
1+1 using common math ordering is 2. but you are writing a language, so you can write 1+1=3 and make sense of this.
but my guess it wont help, just disrupt.
I'm not sure whether someone else has commented on this. I am yet to read the comments. Maybe I will read them soon enough.
Anyways and however, speaking in strict mathetical sense, the model of a tree actually breaks the classical mathematical model of operator precedence.
1 + 1 + 1 evaluates to:
(+)
/ \
(+) (1)
/ \
(1) (1)
The above will be correct, mathematically, but will break once you involve multiple mathematical operators in the statement. Because, mathematically, operators have precedence.
The operators are essentially ordered based on their depth into the right of the question / statement but unless I am terribly wrong, this is not the case in mathematics and some operators have higher precedence regardless of their position in the statement.
Then the author fixed the left-recursion and precedence (which also looks good,) but then complains about the fixed version - "the “shape” of expressions feels completely lost in this new formulation." :
Expr =
Factor
| Expr '+' Factor
...
Then the author takes us through Pratt parsing and ends up at:
fn expr_bp(lexer: &mut Lexer, min_bp: u8) -> S {
let mut lhs = match lexer.next() {
Token::Atom(it) => S::Atom(it),
t => panic!("bad token: {:?}", t),
};
loop {
let op = match lexer.peek() {
Token::Eof => break,
Token::Op(op) => op,
t => panic!("bad token: {:?}", t),
};
...
Yikes! I think he criticised the wrong code. I'll take the '{expression} is a {factor} or an {expression plus a factor}' formulation over the 'mut-loop-peek-panic-lexer-next' approach any day!
Turns you have a fairly, if not a very complicated tree for a simple problem. But, fair, enough, you can always get AI to write the code for this and probably, the code will be reused over and over.
But, is it just me or does someone else think that having to rebalance or re-order the tree might be a good breaking point for the camels back?
If you want to have the full operation recorded this is the way to do it. Either this or a non-binary tree in where multiple operators with the same operand and level are all together:
If you transform the mathematical operation to lisp terms you will have the tree explicitly written.
The only way that I can think of to make it simpler is to go the array language route of going right to left and ignore precedence, or some similar way of working.
The code to create the tree should not complex, so yes, AI could be used, but most competent coders should be able to create a basic version and test it in an afternoon.
If you are parsing left to right it can be quite easy to balance things, you should not need rebalancing at all. When you are in an operation node and you have to add an operation of the same level of priority, you always get the existing operation and subtree, put it on the left of the new operation, and continue from there.
With this if you try to do - next to a - or +, or a / to a / or *, you'll be preserving the order of the operations, and the calculation will be correct. Try it with 2*3/4.
(*)
/ \
(2) (3)
(/)
/ \
(*) (4)
/ \
(2) (3)
If you add some more operations to the right (*2/5*12/7) you keep growing the tree. It will not be balanced, but it doesn't need to be.
>The code to create the tree should not complex, so yes, AI could be used, but most competent coders should be able to create a basic version and test it in an afternoon.
I generally tend to find the idea of 'competent' coders misleading. For the most part, I have been developing or writing code in a certain language for while, then it turns out that I am competent coder? Because, yeah, I've been using C or Python for a while and can easily solve a lot of "complex" problems in C but with all due respect, I am obviously not a competent coder. It's like a situation where you frequent a certain part of town that you're very familiar with it and the people living there but then at the same time you don't live there - lol.
Anyways, for this problem I would parse this statement but definitely not into a tree. I'd assign the integrals to objects. I would then parse or go through the statement again executing the operands.
I'm not saying that competent coders will see the problem and think about doing trees and code it that way. I'm saying that if you have that problem and want to solve it with trees (so knowing the problem and a solution) they should be able to program it.
And in a way you are solving it the same way, if I understood you correctly.
Assuming you mean that you'd have classes, and create objects with the operations, it's the same as a tree.
1+2*3^(4+1)+2/3 -> plus( plus(1, mul(2, power(3, plus(4,1)))), div (2/3)) would be the object hierarchy created.
OTOH if you are parsing it and doing the operations that can be done because all the operands are known:
You'd be, once again, doing the tree but instead of having it as an structure you'd be directly parsing the leafs than can be operated and act on them. This way would maybe be faster for simpler expressions (no need to construct the tree), but probably be more expensive than tree construction and resolution for more complex ones.
I'm absolutely stuck on your comment that trees are the wrong approach, or that trees are somehow incompatible with precedence. They encode the precedence more explicitly and unambiguously than the original string itself.
Trees being incompatible with precedence is like parentheses being incompatible with precedence.
>I'm absolutely stuck on your comment that trees are the wrong approach, or that trees are somehow incompatible with precedence. They encode the precedence more explicitly and unambiguously than the original string itself.
Trees being incompatible with precedence is like parentheses being incompatible with precedence.
IMO, trees are not incompatible with precedence but I just prefer a more barebones approach to this fairly simple problem.
What's more barebones than a simple tree structure as used by essentially every compiler and interpreter, at least for one stage as an intermediate representation, out there today? (If they cover precedence, Forth implementations for instance don't care about it so don't need to use an AST even for an intermediate representation.)
Operators not only have precedence, but also associativity. Building a parser that works for arbitrary precedence and associativity is a standard school project that takes only a few lines more code than a parser that deals with operators with a single precedence level.
Here is an example in Haskell for operator parsing that uses nothing no more than the standard library: https://hackage-content.haskell.org/package/parser-combinato... Excluding comments it’s less than 50 lines of code, and it handles arbitrary precedence, prefix and postfix, ternary operators, infix operators with all three kinds of associativity.
One of the few homework assignments I took in the line cs class I took was to write a calculator program that could store data in variables a–z. I wrote a simple algebraic solver instead with arbitrary length variable names.
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.
Someday HN will go 24 hours without seeing this tired old quote, but today is not that day.
I am soooo tired of that quote. Especially because it’s BS. In 30+ years in the industry, I’ve never seen it happen. Not once. And I’ve never seen anyone demonstrate it convincingly on a real, large-scale commercial project either.
Huh, really?
This reminds me of decades ago when ...wait, I was still writing code like three years ago.
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.
You can also look at how CPython implements hash tables in C. The implementation is surprisingly approachable for a real world one.
SDL3's properties API uses an internal hashtable I'm waiting for them to make public.
I also like https://github.com/tidwall/hashmap.c for general use.
Yep.
https://news.ycombinator.com/item?id=49913084
Why? The only thing missing is the proper data structures and algorithms background.
Which during my degree, the lab deliverables were 100% C code.
Here, one possible book:
Data Structures, Algorithms, and Software Principles in C (1994 edition)
https://www.amazon.com/dp/0201591189
When I was in university, hash tables were definitely among the things we had to learn about and then implement in C, probably in first year. Per Wikipedia, the concept dates to 1953 (with an implementation in assembly); of course people made them in C once that was an option.
I always liked that idea of just doing a linear wrap-around sweep through an array that holds (key, value) pairs, until you find the pair with the key you're looking for (for 'get' or 'contains?') or an empty spot (for 'put'). The trick to make this fast is that the hash function (key -> int) tells you at which index to start the sweep.
No secondary data structures, super simple to implement, and it works great for small use cases.
This isn't great though if you need to find out if an element exists in the table, and you have the ability to remove elements from it. I suppose you could optimize the hash table after deletions, but that again would be slow.. ?
Btw, this reminds me a bit of Cuckoo hashes. Never used them but seems like a nice idea.
The expected or amortized complexity of the standard hash table operations (put, get, contains, remove) are all O(1) for linear probing (under the usual assumptions for the hash function and as long as the table does not get too full). Of course that doesn't shield a single operation from being O(n) in the worst case.
The standard hash table has buckets, though, not just a single array that is probed through in case there's no space for a value in the slot determined by the hash function?
Right, that's the beauty of this simple approach: there's only one array and it doubles as the storage for buckets. But yes, the table will have a maximum size after which you cannot add more entries. That is, in practice you would create a new hashtable with a larger capacity and rehash all the existing entries into the new, bigger table (in practice, you would do that even sooner than that, namely when a certain load factor is passed - see my previous comment where I alluded to the role of the load factor).
The cool thing, however, is: if the size of the new hashtable is double the size of the old hashtable, your amortized insertion costs are still only O(1)!
(And you don't just have to take my word for it: take my original comment and paste it into the AI interface of your choice and have it create a concrete implementation. Ask it to add a remove operation, and an automatic doubling of the array size + rehashing when the table reaches a load factor of, say, 0.7 -- the resulting code should be very manageable, and then you can run your own tests and measure times!
This is maybe not the smartest way to do hashing, but its appeal lies in its simplicity and hence compactness of implementation. There are many cases where you don't even need a 'remove' operation, and where you never have to worry about growing the array because you know that you're only ever going to hash a certain number of elements at most.)
Let's say we have removed all elements from the hash. Then all following contains -calls will need to be O(n), if I understood correctly? They need to check every slot in the array to confirm inexistence, rather than just one bucket.
There are different ways on how to implement remove, but one way to do it is to overwrite the (key, value) pair to be removed with a special "tombstone" symbol that is different from null. Another way is to shift all elements with the same hash value as the one to be removed one index to the left, and null the final position.
There are cases where contains or get would have to iterate over the whole array, basically when all the previously added elements hash-collide, i.e., are mapped to the same start-index. But every hash-implementation has pathological cases where the access methods get slow -- but if the keys are sufficiently random, you don't expect such cases to occur in practice.
If hash tables were impossible to make in C, then it would be impossible to make them in Python, because it is a higher level language than C.
(Almost by definition, anything doable in a higher level language is doable in a lower level language, but not necessarily vice versa. In fact, many higher level languages are themselves written in lower level languages, e.g. Python is written in C.)
But Python has got dicts built into it, which are nothing but hash tables, and they are almost certainly written in C.
Google for some videos by Raymond Hettinger about Python dictionaries.
Or look at the source code of the Python interpreter.
> But Python has got dicts built into it, which are nothing but hash tables, and they are almost certainly written in C.
In CPython they are written in C (at the moment). Other Python implementations are written in other languages.
> (Almost by definition, anything doable in a higher level language is doable in a lower level language, but not necessarily vice versa. In fact, many higher level languages are themselves written in lower level languages, e.g. Python is written in C.)
It depends on what you mean by 'anything doable'. Eg Haskell compilers can in principle do lots of crazy optimisations that a C compiler would not be able to safely do, just because they don't have enough information. Even more so for Lean compilers, which can _know_ which of your loops are terminating, instead of making crude assumptions like C compilers.
Btw, higher level languages being implemented in lower level languages is mostly something for interpreters. Writing a C interpreter in Python is pretty much futile, if you care about speed. But writing a C compiler in Python is perfectly fine. And writing a Python compiler in Python is also fine. Many languages self-host (at least some of) their compilers.
>In CPython they are written in C (at the moment). Other Python implementations are written in other languages.
True. E.g.:
1. PyPy:
https://en.wikipedia.org/wiki/PyPy
>The PyPy interpreter itself is written in a restricted subset of Python called RPython (Restricted Python).
2. Jython:
https://en.wikipedia.org/wiki/Jython
>Implementation language: Python, Java
The article says the last release of Jython was 2 years ago. I wonder how much it is used these days. It did seem like a good idea when it was first released. I had only tried it out a little at that time.
>It depends on what you mean by 'anything doable'. Eg Haskell compilers can in principle do lots of crazy optimisations that a C compiler would not be able to safely do, just because they don't have enough information. Even more so for Lean compilers, which can _know_ which of your loops are terminating, instead of making crude assumptions like C compilers.
Interesting. What are some of those optimisations that Haskell and Lean can do, that a C compiler would not be able to safely do?
A very simple one: in Haskell the compiler has knowledge about which functions cause side-effects and which don't. The compiler can skip calling pure functions whose return value ain't used; similarly, the compiler can call a pure function multiple times, instead of saving the return value in memory.
The Haskell compiler can also fairly freely re-arrange in what order things are computed.
A fairly common idiom in Haskell is to just return a tuple of two values, if they are 'thematically' linked; even if computing one is much more expensive than the other. The compiler is smart enough, to only compute one of the values, if you only use one of them. (When I say 'tuple', it could be literally (a, b), or it could be in a struct or whatever.)
Lean knows even more about your code, so you could do more optimisations. But you need to ask Claude for details, I haven't used it as much nor thought as much about it.
Thanks.
IIRC, the first edition of the book "The C Programming Language" (aka K&R), by Kernighan and Ritchie, had a simple example of how to create a hash table in C, including with buckets to handle collisions. It was a simple algorithm. It simply added up the ASCII values of all the characters in the key, modulo some number.
> I thought that hash tables were something that were basically impossible to make in C,
Why would you believe this in the first place?
Yeah it's a strange assumption, as this was taught in basic data structures class years ago and any language can implement any data structure, technically speaking. C especially is a weird assumption because lots of foundational software is written in C including hash tables.
Arrays are hash tables. You can implement a very simple hash table from a tutorial, but can you implement a sophisticated one? What about a concurrent hash table?
Yeah, I'm pretty sure we made hash tables in the first C class I took in college in my second semester freshman year. If you can make a linked list, and then make an array of them, and a function to map keys to array indexes, you have a hash table. Whether it's actually performant is entirely a separate question, but a naive hash table is still a hash table.
Hash tables are awesome. They are both an incredibly simple data structure and a seriously deep rabbit hole. Most of the complexity comes from collision resolution [1], and how you handle resolution largely determines what kind of hash table you have. There are at least dozens of collision resolution approaches. The simplest, and probably the one you implemented in your undergrad C class was open addressing. That’s also what I implemented as an undergrad. But there are many more approaches, some quite a bit more complicated, and many of them let you continue to shave off asymptotic costs when you run collision resolution, or they improve locality for typical lookups, allowing better cache utilization, etc. Hash tables are super fun to play with, and for full effect, you really do need to implement them in something like C.
I only skimmed the linked article, but I do wonder whether the author ever realized that they needed to think about scope rules. I searched for the word “scope” but never found it. Closures seriously complicate language design and things get painful and counterintuitive unless you use lexical scope (or… you know… you like pain).
[1] https://en.wikipedia.org/wiki/Hash_table#Collision_resolutio...
Yeah, I learned about a bunch of the other algorithms later (forgetting the names, but stuff like "move to the next slot rather than putting collisions into buckets" and "hash a second time if you hit a collision"; I'm sure I'm forgetting some of the nuances).
> Closures seriously complicate language design and things get painful and counterintuitive unless you use lexical scope (or… you know… you like pain)
Well if you like both lexical scope and pain, there's always lisp!
Be careful with Lisp!
You might end up founding one of the first e-commerce sites, sell it for a handsome payday, and then create the first startup accelerator and make insane amounts of money while transforming the industry.
Safer to stick to Blub.
I'd need to solve time travel first for that, but I guess lisp is as good a language as any for figuring that out
> Arrays are hash tables.
Maybe in JavaScript... but there is a topic called datastructures, where arrays are arrays, and hashtables are hastables. If people say this without a flip of an eye I'm not surprised why people write stuff like
> I thought that hash tables were something that were basically impossible to make in C
In a trivial sense, arrays are hash tables with a hash function of the identity f(x)=x.
It’s just not particularly common (or helpful) to view them that way.
In LeetCode, it's a very common optimization. If your key values are dense, you use an array. If your key values are sparse, you use a dict.
Besides the sibling comment, you can used closed hash tables algorithm (open addressing), which is fully based on a single array.
https://en.wikipedia.org/wiki/Open_addressing
> 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
The function named clapp was likely a beast to debug.
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 :)
> 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
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"?
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.
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.
I once invented a programming language where EVERYTHING was an object. No message keywords. 1 is an object. + is an object. You can send an object to another object - you get back an object. Example 1+ is an object. Its is the result of sending + to 1. If you send 1+ the object 1, you get 2. If you send 1+ the object + you get a run-time type error. You can also go left to right. +1 is an object. If you send +1 to 2, you get 3. It gets nice when you add list objects. (1,2,3,4,5)+1 => (1+,2+,3+,4+,5+) 1 => (2,3,4,5,6). And so on.
This sounds a bit like Smalltalk! But with partial application…
It also reminds me of the Emily programming language: https://github.com/mcclure/emily/blob/stable/doc/tutorial.md
Yeah, the Smalltalk and Self family take this "everything is an object" approach, sometimes to extremes.
Another relatively well known language in this space for its use as an alternative to especially Lua in embedding situations is Io: https://iolanguage.org/
Does that imply no support for operator precedence?
It does. Parenthesis are allowed - they are syntax for lists so that a * (b + c) will compute the contents of the list before sending the resulting object to a*. The inspiration is the idea of Currying in Lambda Calculus, although it requires postfix notation. Now you have me thinking about whether I could alaso make parenthesis and commas into objects. So (1+2) for example for do this: ( is sent the object 1. That yields the object (1 That is, an object that is not ready to be sent on. The "(" bounded object would only be released when it received a ")". Thanks for the thought!
So not everything then
It's tempting to go down the rabbit hole of getting creative with memory management as the author does, and maybe worthwhile for educational purposes, but has anyone here observed any noticeable performance gain from it? My impression is that libraries like mimalloc and tcmalloc are painstakingly optimized by specialists and unlikely to benefit from any casual embellishments beyond using the supported malloc and free functions for everything. What does the HN braintrust recommend?
In my experience, it depends. 99% of the time, malloc/free is your best bet: fast enough, battle-tested, everything already uses it, etc.
In the 1%, though, you'll have needs that malloc/free don't fit. Complex object graphs don't really have a single point of ownership or requiring that you free something in all the places that it might be released is too much to handle. In this case you can reach for a garbage collector (including, for example, implementing reference counting). Other times, you may need to make a lot of allocations in a short time where they can all be freed at once. Request processing in a network server is a common example of this: once the request is complete, everything allocated can be dropped, and you generally want minimal latency.
All of this comes with tradeoffs, though. With a GC, you lose predictability and performance changes; sometimes for the better and sometimes for the worse. Depending on the GC, you may not be able to have stable pointers, and you may lose the ability to finalize objects. With an arena, you can't free or reallocate, so you need to scope the arena to a small region of execution (this is where the author went wrong, for example).
Finally, regardless of which approach you use, you're going to need to thread the allocator through the application; probably implement your own datastructures, etc. Depending on how complex your memory management model is, you may need more than one allocator at any given point (e.g., a GC for the persistent data and an arena per connection and per request). If you're implementing your own allocator, you'll also likely have bugs, and allocator bugs tend to be insidious and obnoxious to debug.
If you can avoid going down that route, I recommend it. Sometimes, though, you have enough constraints that you need to brave the jungle.
I recommend fun (and also learning! Learning is fun!)
But do you recommend [Fun](https://dwarffortresswiki.org/index.php?title=DF2014:Fun&red...)?
[dead]
See also https://perl.plover.com/yak/lambda/ from 1999.
> Perl Contains the Lambda Calculus
> (How to write a 163 line program to compute 1+1)
> Length: 90 minutes
Prerequisites: None.
https://tomstu.art/programming-with-nothing
This is also a fun introduction to building up lambda calculus. And it gets up to fizzbuzz!
Relatable. Spent a week optimizing a query that runs twice a year for a report nobody reads. The rabbit hole is real.
Totally relatable. My spreadsheet was slow, so I ended up building a custom columnar database.
1+1 using common math ordering is 2. but you are writing a language, so you can write 1+1=3 and make sense of this. but my guess it wont help, just disrupt.
Fascinating read.
When I was in my early teens, I experimented with created programming languages, I distinctly remember one I made on https://esolangs.org
Fun stuff. I should get back into it.
I'm not sure whether someone else has commented on this. I am yet to read the comments. Maybe I will read them soon enough.
Anyways and however, speaking in strict mathetical sense, the model of a tree actually breaks the classical mathematical model of operator precedence.
1 + 1 + 1 evaluates to:
The above will be correct, mathematically, but will break once you involve multiple mathematical operators in the statement. Because, mathematically, operators have precedence.The operators are essentially ordered based on their depth into the right of the question / statement but unless I am terribly wrong, this is not the case in mathematics and some operators have higher precedence regardless of their position in the statement.
Any comments on this?
Operator precedence needs to get applied at parsing time, before you get a tree. 1 + 2 * 1 needs to get parsed to
The tree representation is unambiguous and once you get that there's no need to think about precedence.There's many ways to do this parsing, e.g. https://matklad.github.io/2020/04/13/simple-but-powerful-pra...
Agree with 'solve it during parsing'.
I had a look at the link. The BNF looked good:
Then the author fixed the left-recursion and precedence (which also looks good,) but then complains about the fixed version - "the “shape” of expressions feels completely lost in this new formulation." : Then the author takes us through Pratt parsing and ends up at: Yikes! I think he criticised the wrong code. I'll take the '{expression} is a {factor} or an {expression plus a factor}' formulation over the 'mut-loop-peek-panic-lexer-next' approach any day!We could give weight to operators. Operators that are heavier go further down the three (have precedence) while the lighter ones float.
1+2*3^(4+1)+2/3
We start the evaluation with 1+, the chain would be on (+) for now.
The next operator is (*), and because this one is heavier it falls down, bringing 2 with it. Now checking the next operator (^), once again heavier, goes down the three. The next operation is between parenthesis, that takes precedence and goes down, but the pointer comes up after the operation has taken place. Next operation is (+), this one floats, and as it's the same weight at the root it doesn't matter its relationship with it, so we put it higher. Finally we got the division, which is heavier again. Did this on the fly, so it might have edge cases, but it works well as a starting point.Thank you!
Turns you have a fairly, if not a very complicated tree for a simple problem. But, fair, enough, you can always get AI to write the code for this and probably, the code will be reused over and over.
But, is it just me or does someone else think that having to rebalance or re-order the tree might be a good breaking point for the camels back?
:-)
If you want to have the full operation recorded this is the way to do it. Either this or a non-binary tree in where multiple operators with the same operand and level are all together:
If you transform the mathematical operation to lisp terms you will have the tree explicitly written.The only way that I can think of to make it simpler is to go the array language route of going right to left and ignore precedence, or some similar way of working.
The code to create the tree should not complex, so yes, AI could be used, but most competent coders should be able to create a basic version and test it in an afternoon.
If you are parsing left to right it can be quite easy to balance things, you should not need rebalancing at all. When you are in an operation node and you have to add an operation of the same level of priority, you always get the existing operation and subtree, put it on the left of the new operation, and continue from there.
With this if you try to do - next to a - or +, or a / to a / or *, you'll be preserving the order of the operations, and the calculation will be correct. Try it with 2*3/4.
If you add some more operations to the right (*2/5*12/7) you keep growing the tree. It will not be balanced, but it doesn't need to be.>The code to create the tree should not complex, so yes, AI could be used, but most competent coders should be able to create a basic version and test it in an afternoon.
I generally tend to find the idea of 'competent' coders misleading. For the most part, I have been developing or writing code in a certain language for while, then it turns out that I am competent coder? Because, yeah, I've been using C or Python for a while and can easily solve a lot of "complex" problems in C but with all due respect, I am obviously not a competent coder. It's like a situation where you frequent a certain part of town that you're very familiar with it and the people living there but then at the same time you don't live there - lol.
Anyways, for this problem I would parse this statement but definitely not into a tree. I'd assign the integrals to objects. I would then parse or go through the statement again executing the operands.
Well...
I'm not saying that competent coders will see the problem and think about doing trees and code it that way. I'm saying that if you have that problem and want to solve it with trees (so knowing the problem and a solution) they should be able to program it.
And in a way you are solving it the same way, if I understood you correctly.
Assuming you mean that you'd have classes, and create objects with the operations, it's the same as a tree.
1+2*3^(4+1)+2/3 -> plus( plus(1, mul(2, power(3, plus(4,1)))), div (2/3)) would be the object hierarchy created.
OTOH if you are parsing it and doing the operations that can be done because all the operands are known:
1+2*3^(4+1)+2/3 -> 1+2*3^5+0.66 -> 1+2*243+0.66 -> 1+486+0.66 -> 487.66
You'd be, once again, doing the tree but instead of having it as an structure you'd be directly parsing the leafs than can be operated and act on them. This way would maybe be faster for simpler expressions (no need to construct the tree), but probably be more expensive than tree construction and resolution for more complex ones.
I'm absolutely stuck on your comment that trees are the wrong approach, or that trees are somehow incompatible with precedence. They encode the precedence more explicitly and unambiguously than the original string itself.
Trees being incompatible with precedence is like parentheses being incompatible with precedence.
>I'm absolutely stuck on your comment that trees are the wrong approach, or that trees are somehow incompatible with precedence. They encode the precedence more explicitly and unambiguously than the original string itself. Trees being incompatible with precedence is like parentheses being incompatible with precedence.
IMO, trees are not incompatible with precedence but I just prefer a more barebones approach to this fairly simple problem.
What's more barebones than a simple tree structure as used by essentially every compiler and interpreter, at least for one stage as an intermediate representation, out there today? (If they cover precedence, Forth implementations for instance don't care about it so don't need to use an AST even for an intermediate representation.)
Operators not only have precedence, but also associativity. Building a parser that works for arbitrary precedence and associativity is a standard school project that takes only a few lines more code than a parser that deals with operators with a single precedence level.
Here is an example in Haskell for operator parsing that uses nothing no more than the standard library: https://hackage-content.haskell.org/package/parser-combinato... Excluding comments it’s less than 50 lines of code, and it handles arbitrary precedence, prefix and postfix, ternary operators, infix operators with all three kinds of associativity.
- 404? on blog page
- https://hereticpleb.vercel.app/blog
Ah shit. I'll have it redirect to / ig. I vibecoded the website I didn't really wanna write javascript or deal with frameworks
totally understandable
My weekend project started as "parse a log file" and now it's a microservice mesh. Relatable.
Isn't this what every first grade CS student goes through?
One of the few homework assignments I took in the line cs class I took was to write a calculator program that could store data in variables a–z. I wrote a simple algebraic solver instead with arbitrary length variable names.
* …I did in the lone CS class…