kcl

The differential equations course was one of the most baffling experiences I ever had. The professor on the first day told us the course would be rote, as opposed to proofs, and every day he copied the methods to the chalkboard. He specifically instructed us to copy them verbatim into our notebooks. In this way there was not a lot to discuss, and from time to time the professor would gently steer us back to merely copying and memorizing the methods, even though no one had questioned him out loud. The methods were entirely disconnected. I had no indication of how they were derived or what the original motivation might be. What a differential equation was or why I wanted to "solve" one---this generated a second equation---was a mystery. None of the problem in the physics sequence looked like this. The engineering students claimed to have them, but reminded me that "this was all done by computers now." In the textbook there were no word problems, only formulas, and so I was never able to infer what this might all be about. The problems gave no opportunity for insight beyond recognizing the form. On the homework I manipulated one formula into another. On the test I did the same thing. Through memorization, I got an A in the course. I never encountered a differential equation before or since.

numbers (and other sorts of mathematics) do not pre-exist reality. Numbers are abstractions of regularities we see in nature.

This is an open and ancient question. I don't suppose to have the answer. I will say, the case for mathematics pre-existing is stronger than what you refute here.

There is an entire world here beyond registering for a signal that comment seems unaware of. Even the simplest of preliminaries: registering for a signal is arguably non-trivial and incorrectly specified in many places since sigaction() supersedes signal().

it's not rocket science to handle it in a sane fashion even in a multi-threaded application. Modern languages make this trivial. The author makes it sound like some dark art

Which language? I'll specify one so we can begin the process of picking each apart. Python? There is a sibling thread indicating Python issues. I don't know what the actual internal status is with Python signal handling but I am guessing the interpreter actually doesn't handle it correctly if I spent any time digging. Do you mean apps implemented in Python? They will almost certainly not be internally data-consistent. Exposing a signal handling wrapper means very little particularly when they frequently do this by ignoring all of the bad implications. I just checked Python's docs, and not surprisingly, Python guarantees you'll be stuck in tight loops: https://docs.python.org/3/library/signal.html That's just one gotcha of many that they probably aren't treating. This dialogue is going to play out the same way regardless of which language you choose.

Do you mean Postgres? I haven't used it recently but the last comment I read on HN seemed to indicate you needed to kill it in order to stop ongoing queries in at least some situations. If by a stroke of luck it does support SIGINT recovery (which would be great), what about the hundreds of other db applications that have appeared recently? You can't just call the signal handler wrapper and declare victory.

It is true this improves the bad path. It ignores desired happy path cases: downstream processes, custom debugging, graceful shutdown, preserved workspaces, and so on.

The way exceptions are handled as a result of siglongjmp'ing out of a signal handler is currently platform-inconsistent and one of the many dark areas I alluded to. It isn't even consistent on Linux between compilers.

This conversation is silly. You are snapshotting the transformative window. If you snapshotted the internet in the 70s or 80s you'd get a much more mundane picture.

I don't know if I think cryptocurrency will be as transformative as the internet or the mobile phone, but I think it will be within a level or two of that scale. It makes good on its promise year after year. NFTs just became popular in the last few years, and that is only one example of many. Are you going to bet against NFTs in the long run? I certainly wouldn't. We don't even know all the technologies crypto is going to enable yet.

GC researchers insist on conflating GC with all of automatic memory management. The public doesn't do this and neither does the article.

Secondly, you know what's cheaper... Not doing anything at all.

These techniques are on the level of resetting a stack pointer or calling `sbrk()`. Incorporating them doesn't produce more-advanced GC schemes, it just means you neglected to consider similar allowances for RC.

The line of contention is at traversing the object graph and pausing threads.

Your comment is radically naive. You can't literally believe what a business writes in its PR spin. The only thing you can take away from this is that Visa intends to tip the balance towards merchants and away from consumers when it comes to chargebacks. The problem with this is chargebacks just barely work as is.

Punishing honest consumers is not the right way to go about this.

Your approach will not work. Either continue attempting proofs or give up. It's fine to read the answers after you've tried.

I've heard many many times that you can only learn math by doing it, which is certainly true

yes

and is akin to saying that you can only learn a language by...

no. this is you evading the main point.

Taking a graded class with homework can help. So can finding an elementary book on a subject that interests you (topology, combinatorics, algebra, ...). Linear is dry, that may be your issue.

I don't know where this method of argumentation came from, but it's obnoxious and I'm over it. There are even soyjaks for this. Either you don't know and you're being lazy (I don't think this is the case), or you do know and you've generated an asymmetric work request for op that you could've answered and that left unanswered by him casts doubt on his argument. If you have a case to make, make it, instead of this nonsense DoS attack. This is not a defense of op's position.

Right, you are the cop-out I am complaining about. Linus is the premier figurehead of the premier open-source project. When a build tool he made for that project goes viral it isn't an accident. If it was anybody else's pet versioning control system would we even be talking about it?

Git's UI/UX is one of the worst engineering sins to be committed in the last two decades, and this website shows why. Literally nothing about git is intuitive and the "underlying model" is entirely ad-hoc. Instead of celebrating how Linus built git in only a few days he should be castigated for knowingly setting up ill-conceived software to go viral.

The problem with concurrent computing is not a lack of Erlang awareness or message passing awareness. If either was the solution we wouldn't be having this discussion since they both pre-date the 90s.

There ought to be a codeword where you can invoke the shortcomings of Erlang without getting dragged into a conversation with someone desperate to talk about Erlang. Next time I will rot13 it.

I've written on this problem before: https://kevinlawler.com/parallel

One issue is that the pthread model is too low level (think AND and OR gates), but you must include it for completeness.

I agree with the comments here that say higher-level multithreading support needs to be "baked in" to the language. Grand Central Dispatch did a good job of raising the bar here, but has its own problems, and is arguably too low level.

Another issue is that existing, widespread languages are too old to have cooked higher-level threading support in. You really have to do it from the start. C++ bolt-on parallelism might as well be syntactic sugar. Newer languages, like Rust, have attempted to solve concurrency problems but failed - it's not clear that the designers genuinely understand concurrency at all. Goroutines solve one limited issue of many and seem about as difficult as asking programmers to write threaded programs.

To do this correctly you need a new language that cooks it in from the start. There is a laundry list of things that have to be done precisely. It might be possible to do this by rewriting a reference implementation of an existing popular language, but the development overhead and performance concerns involved in backwards-compatibility make that probably infeasible. (Python can't even escape it's global-interpreter lock.) So likely the language that solves this problem is either unwritten or unknown.

Other mentions in the comments here:

ThreadSanitizer: It's not very good, nor can it be.

Erlang: solves the problem, but the actor formulation is too awkward for all but Erlang-specific use-cases.

I've run this experiment with friends and it was trivial to distinguish reds from whites with table wines. Whatever wines they use in these studies to stump experts must be more close in flavor.

Is Joel a supervillain? Why is Joel writing this and, given his obvious conflict of interest, addressing it to developers as if it were friendly advice, when it is not?

I advise people not to work for Joel or his companies. This is developer-hostile advice from someone who should know better. You don't want to work for a guy like this or his companies.

I think it is true. We head off discussion here by referring to the naive approach, but what you're doing is past naive coupon collector's and past the technical scope of the context.

There are several steps where your method could (will) fail. Since you don't introduce any machinery for the hand, you imply an O(k^2) checking algorithm. You also imply an unsorted hand. If you generate the hand in random order, then you fall to an O(k*lg(k)) sort. "Sorted" is an implicit requirement that we initially omit, but revisit later, because introducing it early makes the discussion harder to follow.

If you try to introduce machinery like a hashtable, the next thing you might suggest, you violate an implicit O(1) additional space requirement, which I've grudgingly reintroduced to the more-formal description ("why is this here?"). This conversation keeps going, but other failure paths we leave unexamined.

I've changed "center" to read "interior". I meant "center" as the complement of the surface.

This is too cool not to try and incorporate.

If you can show that ancient placer deposits were the result of meteor strikes and not volcanic activity I'll change the article. Everything I read pointed to volcanic activity.

If you mean modern mining activity, not germane.

Ancient Greece is still an age or two away. I am interested in your pigment argument, however. If I get into specifics about what makes gold good art I'll check into that. It would be interesting to look into, say, the price of gold versus purple dye in Ancient Rome.

We all know that gold has industrial uses. But those won't appear for thousands of years. Mentioning that you can use gold in integrated circuits does nothing to explain gold in the Stone Age.

I've committed a Linux version that for sure uses libedit. It is decidedly not my intention to use libreadline.

The OSX version links against libedit. The Linux version is supposed to as well so if it isn't that's an oversight. Let me take a look.

Linux linking: I wasn't doing anything special with the linking. The Linux binary was compiled on a VirtualBox instance of Mint and stripped and compressed, so it's possible your tools are misreporting, or I did something I wasn't expecting. At any rate, I haven't made that as a conscious design choice, and it's easy to change (fix?) compilation styles in a future build.

SQL engine: all from scratch

If you want an unrestricted version send me an email at k.concerns@gmail.com (this goes for anyone here)

You might give Kerf a try: https://github.com/kevinlawler/kerf

The author uses NP-complete correctly. Section 2.2 of the paper establishes the problem is in NP and not merely NP-hard.

Your intuition about verifying optimal solutions has misled you here. Interesting optimization questions such as "shortest" or "best" are conventionally reformulated as decision questions about a particular bound. The verification then becomes easy: check to see, for instance, that the certificate path works and is shorter than the specified bound. A log-time search with such a verifier as a subroutine produces a polynomial verifier for the original optimality question.

I stop short of recommending B-trees as the only tree structure you need to know. I think if it matters at all what kind of tree you're using, you're deep enough in the guts that it pays to know the differences between B-trees and basic trees.

To me, this is especially relevant today, since if you need a "B-tree", you probably need a standard relational database (MySQL/PostgreSQL/SQLite), and if that doesn't work for you, you'd be advised to know what the tradeoffs are with a regular tree. There are scenarios where B-trees are suboptimal.

Cache-obliviousness, which is still new, is also changing how we look at trees, since in one sense a B-tree is a hack on the basic tree structure to exploit locality. Representation matters more today as well. This is a longer conversation. Suffice to say I think this is an area of active and useful research, and wouldn't rule out either class of tree.

This is a valuable article that I read thoroughly when I was re-reviewing search trees. Nobody wants to spend 60 hours learning a new tree only to have it fail to live up to its promise. I'll summarize what I know (or think I know) about trees here, since it may be of use to anyone who had enough of an interest to check out the above article.

Sedgewick claims that LLRB trees are simpler, but this is hotly contested. Most of the sources I read said that LLRB trees were more complicated, often a lot more, than regular RB trees. All of the timings I found suggested that LLRB trees were slower than RB trees. Looking at the code, and at the detailed timings, I tend to agree that LLRB trees are slower and more complicated. If there is an explanation/implementation which realizes Sedgewick's promise of simplicity I have not seen it, and it isn't in the published LLRB material.

If you need a tree that is slower and simpler than an RB tree, with a similar implementation, you could look at AA trees instead.

My opinion however is that, in terms of practical applications, there is no reason to learn RB trees today instead of AVL trees. If you do research in data structures, RB trees may be worth knowing. I think the prevalence of RB trees is due to several factors:

1. RB trees are featured in the common Cormen algorithms book in lieu of AVL trees (a mistake). RB trees are also featured in the Sedgewick book.

2. The Cormen book shows how to implement delete for RB trees. Knuth's AVL description, and indeed most AVL descriptions, omit the delete method, which is a serious oversight. This has caused many tree implementations to avoid deletes or avoid AVL altogether. You can verify this via Google or GitHub. While Knuth initially had good reason, ultimately omitting delete was a mistake.

3. Plenty of theoretical conjecture predicts RB trees are faster. Actual benchmarks show that AVL trees perform better, or at worst, about the same. (If anyone has data that shows scenarios where this is not the case, I would be interested to see it.)

This is an unfortunate state of affairs, as the AVL tree appears to be a strictly better tree than the RB tree. The height is bounded at about 1.5x optimal instead of 2x optimal. You could argue the AVL tree is roughly as difficult to understand and code, though I would say it is simpler and more natural. The AVL tree performs generally better in actual benchmarks, and substantially better in certain important cases (sorted inserts).